答题：

A. B. C. D. （已提交）

参考答案： C

问题解析：

17. ( 单选题 )如果从无向图的任一顶点出发进行一次深度优先遍历即可访问 所有顶点，则该图一定是（） A. 完全图 B. 连通图 C. 有回路 D. 一棵树

答题： A. B. C. D. （已提交）

参考答案： B

问题解析：

18. ( 单选题 ) 以下叙述中错误的是（ ）。

A. 图的遍历是从给定的初始点出发访问每个顶点且每个顶点仅访问一次 B. 图的深度优先遍历适合无向图 C. 图的深度优先遍历不适合有向图 D. 图的深度优先遍历是一个递归过程

答题：

A.

B. C. D. （已提交）

参考答案： C

问题解析：

19. ( 单选题 ) n 个顶点的连通图的生成树有A. n-1 （ B. n C. n+1 D. 不确定

）个顶点。

答题：

A. B.

C.

D. （已提交）

参考答案： B 问题解析：

20. ( 单选题 ) n 个顶点的连通图的生成树有（

A. n B. n-1 C. n+1 D. 不确定

）条边。

答题：

A. B. C. D. （已提交）

参考答案： B 问题解析：

第八章 动态存储管理

1. ( 单选题 )在采用顺序查找方法查找长度为 n 的线性表时，不成功情况下的 平均比较次数为（）。 A. n B. п/2

C. (n+1)/2

D. (n-1)/2

答题：

A. B. C. D. （已提交）

参考答案： A

问题解析：

2. ( 单选题 ) 在对线性表进行折半查找时，要求线性表必须（

А . 以顺序方式存储 B. 以链接方式存储

C. 以顺序方式存储，且结点按关键字有序排序 D. 以链表方式存储，且结点按关键字有序排序

）。

答题： A. B. C. D. （已提交）

参考答案： C 问题解析：

3. ( 单选题 )有一个长度为 12 的有序表 R[0..11] ，按折半查找法对该表进行 查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（

A. 35/12 B. 37/12 C. 39/12 D. 43/12

）

答题：

A. B.

C. D. （已提交）

参考答案： B

问题解析：

4. (单选题) 有一个有序表为 {1,3,9,12,32,41,45,62,75,77,82,95,99}

82 的元素时，（ 用折半查找法查找关键字为 ）次比较后查找成功。

A. 1 B.2

С . 4 D. 8

，当采

答题：

A. B. C. D. （已提交）

参考答案： C 问题解析：

5. ( 单选题 ) 在含有 27 个结点的二叉排序树上查找关键字为 35 的结点，则依 次比较的关键字有可能是（ ）。

A. 28, 36, 18, 46, 35

C. 46, 28, 18, 36, 35

B. 18, 36, 28, 46, 35 D. 46, 36, 18,

C.

28, 35

答题：

A. B.

D. （已提交）

参考答案： D

问题解析：

6. ( 单选题 ) 一棵二叉排序树是由关键字集合 {18, 43, 27, 77,

构建的，其先序遍历序列是（ ）。

A. 树形未定，无法确定 B. 18, 43, 27, 77, 44, 36, 39

44, 36, 39}

C. 18, 27, 36, 39, 43, 44, 77 D. 77, 44, 43, 39, 36, 27, 18

答题： A. B. C. D. （已提交）

参考答案： C 问题解析：

第九章 查找表

1. (单选题) 次关键字。

A. n-1

对有 n 个记录的表进行直接插入排序， 在最坏情况下需比较（

）

B. n+1

C. n/2

D. n(n-1)/2

答题：

A. B.

C.

D. （已提交）

参考答案： D 问题解析：

数据序列 {8,9,10,4,5,6,20,1,2} 2. (单选题) 只能是（ ）算法的两趟排序

后的结果。

A. 简单选择排序 B. 冒泡排序 C. 直接插入排序 D. 快速排序

答题：

A. B. C. D. （已提交）

参考答案： C 问题解析：

3. ( 单选题 ) 在以下排序方法中， （ ）在初始序列基本有序的情况下，排序效率最高。

A. 冒泡排序 B. 直接插入排序 C. 快速排序 D. 希尔排序

答题：

A. B. C. D. （已提交）

参考答案： B

问题解析：

4. ( 单选题 ) 在以下排序方法中， （ ）在最后一趟排序结束之前所有元素可

能都没有放至其最终位置上。

A. 快速排序 B. 希尔排序 C. 直接插入排序 D. 冒泡排序

答题：

A. B.

C.

D. （已提交）

参考答案： B 问题解析：

5. ( 单选题 ) 对数据序列 (8,9,10,4,5,6,20,1,2) 进行递增排序，采用每趟冒出 一个最小元素的冒泡排序算法，需要进行的趟数至少是（ ）。

А.3 В. 4 C.5 D. 8

答题：

A. B. C. D. （已提交）

参考答案： C

问题解析：

6. ( 单选题 )对 8 个元素的顺序表进行快速排序，在最好情况下，元素之间的 比较次数为（）次。

А.7 B. 8 C. 12 D. 13

答题：A. 参考答案： D 问题解析：

B.C.

D. （已提交）

7. (单选题) 对数据序列 {28, 16, 32, 12, 60, 2, 5, 72} 进行快速排序，第 一趟从小到大一次划分的结果为（ ）。

72)В. (5, 16, 2, 12) 28 (60, 32, 72) A. (2, 5, 12, 16) 26 (60, 32,

C. (2, 16, 12, 5 ) 28 (60, 32, 72) D. (5, 16, 2, 12) 28 (32, 60, 72)

答题：

A. B.

C.

D. （已提交）

参考答案： B

问题解析：

数据序列 {3, 2, 4, 1, 5, 6, 8, 7} 8. (单选题) 是第一趟递增排序后的结果，

则采用的排序方法能是（ ）。

A. 快速排序 B ．冒泡排序 C. 直接插入排序 D. 简单选择排序

答题：

A. B. C. D. （已提交）

参考答案： A 问题解析：

9. ( 单选题 ) 以下关于快速排序的叙述正确的是（ ）

A. 快速排序在所有排序方法中最快，而且所需辅助空间最少 B. 在快速排序中，不可以用队列替代栈 C．快速排序的空间复杂度为 O(n))

D. 快速排序在待排序的数据随机分布时效率最高

答题： 问题解析：

A. B. C. D. （已提交）

参考答案： D

10. ( 单选题 ) 在下列排序方法中，（ ）在一趟结束后不一定能选出一个元素放在其最终位置上。