云南财经大学信息学院
《数据结构》习题及参考答案
《数据结构》课程建设小组
第 1 章 绪 论
基础知识题
1.1 ① 简述下列术语：数据、数据元素、数据对象、存储结构、数据类型、和抽象数据类型。
1.2 ② 试描述数据结构和抽象类型的概念与程序设计语言中数据类型概念的区别。 1.3 ③设有数据结构（D，R），其中
D={d1,d2,d3,d4},R={r},r={(d1,d2),(d2,d3),(d3,d4)}。 试按图论中的画法惯例画出其逻辑结构图。
1.4 ②试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有
理数是其分子，分母均为自然数其分母不零的分数）。 1.5 ②试画出与下列程序段等价的框图 （1） product=1 ; i=1;
while (i<=n){ product * = i;
i++; }
(2) i=0 ;
do { i++
} while ((i !=n )&&(a[i]!=x));
(3) swith {
case x case x=y : z =abs(x * y);break ; defult : z= (x – y) /abs (x) * abs (y); } 1.6 ② 在程序设计中，常用下列三种不同的出错处理方式： （1） 用exit 语句终止执行并报告错误； （2） 以函数的返回值区别正取返回或错误返回； （3） 设置一个整型变量的函数参数以区别正取返回或错误返回； 试讨论这三种方法各自的优点 1.7 ③ 在程序设计中，可采用下列三种方法实现输出和输入： （1） 通过 scanf和printf 语句； (2) 通过函数的参数显示传递； （3） 通过全局变量隐式传递。 试讨论这三种方法的优缺点。 1.8 ④ 设 n 为正整数。试确定下列各程序段中前置以记号@的语句的频度： (1) i = 1; k = 0; While (i<=n - 1) { @ k + = 10 * I ; i ++; } (2) i = 1; k = 0; do (i<=n - 1) { @ k + = 10 * I ; i ++; } while (I< = n - 1); (3) i = 1; k = 0; While (i<=n - 1) { i ++; @ k + = 10 * i ; } (4) k = 0; for ( i = 1;i<=n ;i++) { for ( j = i;j<=n ;j++) @ k + +; } (5) for ( i = 1;i<=n ;i++) { for ( j = i;j<=n ;j++) { for ( k = 1;k<=j ;k++) @ x + = delta; } (6) i=1;j=0; While (i+j<= n){ @ if (i>j) j++; else i++; } (7) x= n; y= o; while (x>=(y+1) * (y + 1)){ @ y ++; } (8) x= 91; y= 100; while (y>0){ @ if (x>100){x-=10; y - -; } else x ++ ; } 1.9 ③ 假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值 （以的函数形式表示）。 int Time( int n){ Count=0;x=2; While (x return (count) } // Time 1.10 ② 按增长率由小到大的顺序排列下列各函数： 2100 (3/2)n (2/3)n (4/3)n nn n 3/2 n 2/3 n! n, log2 n log22 n log2 ( log2 n) nlog2 n n log 2n 1.11 ③ 已知有现实同一功能的两个算法，其时间复杂度分别为O（2n）和O（n10）， 假设现实计算机可连续运算的时间为 107 秒（100多天），又每秒可执行基本操 5 作（根据这些操作来估算算法时间复杂度）10 次。试问在此条件下，这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由。 1.12 ③ 设有以下三个函数： f (n) = 21n4 + n2 + 1000 g(n) = 15n4 + 500n3 h(n)=5000 n3.5 +nlogn 请判断以下断言正确与否： （1）f (n)和 O(g (n)) (2) h(n) 和O(f (n)) (3) g(n) 和O(h (n)) (4) h (n) 和O(n3.5) (5) h(n) 和O(nlogn) 1.13 ③ 试设定若干n的值，比较两函数n2 和50nlog2n 的增长趋势，并确定n在什 么范围内，函数n2 的值大于 50nlog2n 的值 1.14 ③ 判断下列各对函数f (n) 和g (n) ,n趋进于∞时，哪个函数增长更快？ 1.15 试用数学归纳法证明： 算法设计题 1.16 ② 试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。 1.17 ③已知k阶裴波那契序列的定义为： 试编写k阶裴波那契序列的第 项值的函数算法，k和m均以值调用的 形式在函数参数表中出现。 1.18 ③ 假设有A，B，C，D，E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为： 项目名称 性 别 校 名 成 绩 得 分 编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。 1.19④ 试编写算法，计算 i !. 2i 的值并存入数组a[0…arrsize - 1] 的第i- 1个分量中（I= 1,2,….,n）。假设计算机中允许的整数最大值为maxint, 则当n>arrsize 或对某个k(1≤k≤n)使 k!. 2k >maxint 时，应按出错处理，注意选择你认为较好的出错处理方法。 1.20④ 试编写算法求一元多项式的值 的值Pn(x0) 并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为 aj (i= 0, 1,…..n) x0 和n,输出为 Pn(x0) 。