第1章 绪论 答案
一、选择题 1.B 2.C 12.D 二、判断题 1. × 11.× 2. × 12. √ 3.× 13. × 4.× 14. × 5. √ 6. × 15. × 16. √ 7. × 8. √ 9.× 10.× 17. √ 3.1C 3.2B 4.B 5.D 6.C 7.C 8.D 9.D 10.C 11.C 13.A 14.A 15.C 16. C 17.D 18.B 19A 20.B 三.填空题
1.数据元素 数据元素间关系 2.集合 线性结构 树形结构 图状结构或网状结构。 3.数据的组织形式,即数据元素之间逻辑关系的总体。
4.表示(又称映像)。 5.(1)逻辑特性 (2)在计算机内部如何表示和实现 (3)数学特性。 6.算法的时间复杂度和空间复杂度。7.(1)逻辑结构(2)物理结构(3)操作(运算)(4)算法。 8.(1)有穷性 (2)确定性 (3)可行性。
3
9.1+(1+2++(1+2+3)+…+(1+2+…+n)=n(n+1)(n+2)/6 O(n)
10. log2n 11. nlog2n 12. log2n2 13. (n+3)(n-2)/2 14. O(n) 15. ① (1)1 (2)1 (3)f(m,n-1) (4)n ② 9 16. n(n-1)/2 17. 集合 线性结构 树形结构 图形结构 非线性结构 18.顺序存储 链式存储 19.一对一 一对多 20.没有
一
21.任意多个 任意多个 22.有穷性 确定性
四.应用题
1.将学号、姓名、平均成绩看成一个记录(元素,含三个数据项),将100个这样的记录存于数组中。因一般无增删操作,故宜采用顺序存储。 typedef struct {int num;//学号
char name[8];//姓名 float score;/平均成绩 }node;
node student[100];
2.对算法A1和A2的时间复杂度T1和T2取对数,得nlog2和2logn。显然,算法A2好于A1。 3. struct node
{int year,month,day; };
typedef struct {int num;//帐号
char name[8];//姓名
struct node date;//开户年月日
int tag;//储蓄类型,如:0- 零存,1- 一年定期…… float put;//存入累加数; float interest;//利息 float total;//帐面总数 }count;
6
索引存储 多对多
散列存储
没有 多个 输入
输出
可行性
4.第一层FOR循环判断n+1次,往下执行n次,第二层FOR执行次数为(n+(n-1)+(n-2)+…+1),第三层循环体受第一层循环和第二层循环的控制,其执行次数如下表: i= 1 2 3 … n j=n n n n … n j=n-1 n-1 n-1 n-1 … … … … …
j=3 3 3 j=2 2 2 j=1 1
执行次数为(1+2+…+n)+(2+3+…+n)+…+n=n*n(n+1)/2-n(n2-1)/6。在n=5时,f(5)=55,执行过程中,输出结果为:sum=15,sum=29,sum=41,sum=50,sum=55(每个sum= 占一行,为节省篇幅,这里省去换行)。
n/22
5.O(n),m的值等于赋值语句m=m+1的运行次数,其计算式为i?12
3
?(n?2i?1)?2
n24
6.(1)O(1) (2)O(n) (3)O(n) 7.(1)O(n) (2)O(n)
?2n????1/22335n/2nn???8.从小到大排列为:logn, n+logn, n, nlogn, n+logn,n, n-n+7n, 2, (3/2), n!,
9.试分析下列程序段的时间复杂度
(1)O (n*m) (2)O (n) (4)O (sqrt (n) )
(3)O (n2)
7