2024年1月4日发(作者：)

客观题答案

习题1

一、

1. A

2. C

3. C

4. A

5. C

6. B

7. B

8. C

9. D

10. C

11. A

12. B

13. C

14. D

二、

1. 集合；线性结构；树形结构；图形结构

2. 集合；线性结构；树形结构；图形结构

3. 有穷性；确切性；输入；输出；可行性

4. 时间和空间复杂度

5. 一对一；一对多；多对多

6. 逻辑关系

7. 没有；一

8. 一个；一个；后继；任意个

9. 任意个

10. 物理

11. 时间复杂度；空间复杂度

12. 问题规模

习题2

一、

1. B

2. A

3. C

4. C

5. B

6. B

7. A

二、

1. n+1；n

2. 顺序；链式

3. O(n)；O(n)

4. O(1)；O(1)

5. O(n)；O(1)

6. O(1)；O(1)

7. O(1)；O(n)

习题3

一、

1. B

2. B；A； B； D； C

3. B

4. A

5. D

6. C

7. D

8. B

9. D

10. D

11. D

12. C

13. B

14. B

15. B

二、

1. 线性；任何；栈顶；队尾；队首

2. 栈顶；栈底

3. 队列

4. 前一个

5. n-1

6. 移动栈顶指针；存入元素

7. 移动队首指针；取出元素

8. if(top!=n)data[++top]=x;

9. 23 12 3 * 2 - 4 / 34 5 * 7 / + +108 9 / +

10. 假上溢

习题4

一；

1. B

2. B

3. D

4. A

5. B

6. H；C；E；A；F

7. L；J；C；I

二、

1. 空串；空白串

2. 20；3

3. 被匹配的串；子串

4. 行下标；列下标；元素值

5. 6

6. (n-m+1)*m

7. 288B；1282；1072（这个空没划出来）；1276

8. 8950

习题5

一、

1. D

2. D

3. B

4. C

5. B；C；A

6. D

7. A

8. B

9. A

10. B

二、

1. 一个且只有一个；互不相交

2. 度；孩子；双亲

3. 2i-1；(n+1)/2；(n-1)/2

4. 2h-1；2h-1

5. 2k-1

6. 50

7. 12

8. CDBGFEA

9. 2n；n-1；n+1

10. n；n-1

习题6

一、

1. A

2. C；D

3. B

4. B

5. C

6. A

7. A

二、

1. 0；n(n-1)/2；0；n(n-1)

2. 图本身

3. 邻接矩阵；邻接表

4. O(n+e)

5. 求第j列的所有元素之和

6. 出度

7. 前序；栈；层次；队列

8. O(n2)；O(elog2e)

9. 回路

10. vi vj vk

11. 2

12. n；环状

13. n-1

14. n*n

15. 不唯一；n-1

16. 9

习题7

一、

1. （1）DC（2）ADF（3）B（4）ACF BDE

2. D

3. A

4. C

5. C

6. C

7. D

8. A

9. C

10. D

11. C

12. C

二、

1. 索引表；块；查找索引表的平均长度和查找相应块的平均长度的和

2. 稳定；不稳定

3. 内部；外部

4. 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率

5. n(n-1)/2

习题8

一、

1. A

2. B

3. B

4. B

5. D

6. C

7. B

8. A；B

9. D

10. A

11. D

12. C

二、

1. 平均查找长度

2. 集合

3. 50；100

4.

⌊