题目

1、对具有 n 个元素的任意序列采用选择排序，排序趟数为（ ）。
A. n - 1
B. n
C. n + 1
D. ⌊log₂n⌋

2、堆是完全二叉树，完全二叉树不一定是堆。（ ）

3、以下序列不是堆（大根堆或小根堆）的是（ ）。
A. {100, 85, 98, 77, 80, 60, 82, 40, 20, 10, 66}
B. {100, 98, 85, 82, 80, 77, 66, 40, 20, 10}
C. {10, 20, 40, 60, 66, 77, 80, 82, 85, 98, 100}
D. {100, 85, 40, 77, 80, 60, 66, 98, 82, 10, 20}

4、已知关键字序列 {5, 8, 12, 19, 28, 20, 15, 22} 是小根堆，插入关键字 3，调整后得到的小根堆是（ ）。
A. 3, 5, 12, 8, 28, 20, 15, 22, 19
B. 3, 5, 12, 19, 20, 15, 22, 8, 28
C. 3, 8, 12, 5, 20, 15, 22, 28, 19
D. 3, 12, 5, 8, 28, 20, 15, 22, 19

5、已知序列 {21, 41, 7, 43, 58, 63, 29, 8}，判断该序列是否为堆。若不是，将其调整为小根堆，画出调整完的小根堆。

6、将初始关键字序列 {51, 12, 55, 23, 49, 07, 60, 36, 72, 12'}，写出归并排序算法的每一趟结果。

7、给出关键字序列 {112, 204, 312, 902, 156, 712, 451, 623, 643, 834} 进行基数排序时每一趟的结果。

8、在最好和最坏情况下的时间复杂度均为 O (nlog₂n) 且稳定的排序方法是（ ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 基数排序

9、在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下_______最快，其时间复杂度为_______。

10、下列排序算法中，第一趟排序结束后，其最大或最小元素一定在其最终位置上的算法是（ ）。
A. 归并排序
B. 直接插入排序
C. 快速排序
D. 冒泡排序

答案

1、A

2、正确

3、D

4、A

5、不是堆

6、

7、

8、C

9、快速排序；O (nlog₂n)

10、D