数据结构课程（本科）第九章试题
一、单项选择题
1. 若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（
A. 直接插入排序
B. 快速排序
C. 归并排序
D. 直接选择排序
）方法比较次数最少。
2. 如果只想得到 1024 个元素组成的序列中的前 5 个最小元素，那么用（
A. 起泡排序
B. 快速排序
C. 直接选择排序
A. 8
B. 10
C. 15
D. 25
）次比较？
5. 如果输入序列是已经排好顺序的，则下列算法中（
）算法最快结束？
A. 起泡排序
B. 直接插入排序
C. 直接选择排序
D. 快速排序
6. 如果输入序列是已经排好顺序的，则下列算法中（
）算法最慢结束？
A. 起泡排序
B. 直接插入排序
C. 直接选择排序
D. 快速排序
8. 在堆排序中， 如果 n 个对象的初始堆已经建好， 那么到排序结束， 还需要从堆顶结点出发调用 ________ 次调整算法。
9. 在堆排序中，对任一个分支结点进行调整运算的时间复杂度为
O(________) 。
10. 对 n 个数据对象进行堆排序，总的时间复杂度为
O(________) 。
11. 给定一组数据对象的排序码为 ________。
13. 在下列排序算法中， （ A. 锦标赛排序 C. 基数排序
）算法使用的附加空间与输入序列的长度及初始排列无关。 B. 快速排序 D. 归并排序
4 } ，采用快速排序（以位于最左位置的对象为基准而） 得到的第一次划分结果为：
18. 在 n 个数据对象的二路归并排序中，整个归并的时间复杂度为
O(________) 。
参考答案： 1 . 插入 4. 两路归并 7. n/2 10. nlog 2n 13. n 2 16. [40 38] 46 [79 56 84]
2. 直接选择 5. n 2 8. n-1 11. 84, 79, 56, 38, 40, 46 14. log 2n 17. n
）
算法最快。
A. 归并排序 C. 快速排序
B. 希尔排序 D. 基数排序
参考答案：
1. A 6. D 11. D
2. D 7. D 12. C
3. C 8. C 13. C
4. B 9. C 14. C
5. A 10. C 15. D
二、填空题
1. 第 i (i = 1, 2 , … , -n1) 趟从参加排序的序列中取出第 i 个元素，把它插入到由第 0 个～第 i - 1 个元素组
15. 快速排序在最坏情况下的空间复杂度为 O(________) 。
16. 给定一组数据对象的排序码为 { 46, 79, 56, 38, 40, 84} ，对其进行一趟快速排序，结果为 ________。
17. 在 n 个数据对象的二路归并排序中，每趟归并的时间复杂度为
O(________) 。
A. 5
B. 6
5 个互异的整数进行排序，至少需要（
C. 7
D. 8
）次比较。
10. 下列算法中（ 排序。 A. 起泡排序 C. 快速排序
）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成
B. 希尔排序 D. 直接选择排序
-
11. 使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过
A. { 38, 46, 79, 56, 40, 84 }
B. { 38, 79, 56, 46, 40, 84 }
C. { 40, 38, 46, 79, 56, 84 }
D. { 38, 46, 56, 79, 40, 84 }
15. 如果将所有中国人按照生日 （不考虑年份， 只考虑月、 日）来排序， 那么使用下列排序算法中 （
3. 交换 6. n 9. log 2 n 12. nlog 2n 15. n 18. nlog 2n
O(nlog 2n)，必须做到（
）。
A. 每次序列的划分应该在线性时间内完成
B. 每次归并的两个子序列长度接近
C. 每次归并在线性时间内完成
D. 以上全是
12. 在基于 排序码 比较的排序算法中， （ A. 起泡排序 C. 归并排序
）算法的最坏情况下的时间复杂度不 B. 希尔排序 D. 快速排序
高 于 O(nlog 2n)。
4. 每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做
________ 排序。
5. 在直接选择排序中，排序码比较次数的时间复杂度为
O(________) 。
6. 在直接选择排序中，数据对象移动次数的时间复杂度为
O(________) 。
欢迎下载
2
-
7. 在堆排序中，对 n 个对象建立初始堆需要调用 ________次调整算法。
7. 下列排序算法中（ A. 起泡排序 C. 基数排序
）算法是不稳定的。 B. 直接插入排序 D. 快速排序
8. 假设某文件经过内部排序得到
则应取的归并路数至少是（
A. 3
B. 4
100 个初始归并段， 那么如果要求利用多路平衡归并在
）。
C. 5
D. 6
3 趟内完成排序，
9. 采用任何基于排序码比较的算法，对
D. 堆排序
）方法最快。
3. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，
直到子序列为空或只剩一个元素为止。这样的排序方法是（
）。
A. 直接选择排序
B. 直接插入排序
C. 快速排序
D. 起泡排序
4. 对 5 个不同的数据元素进行直接插入排序，最多需要进行（
{ 46, 79, 56, 38, 40, 84 } ，则利用堆排序方法建立的初始堆 （最大堆） 为
12. 快速排序在平均情况下的时间复杂度为 O(________) 。
13. 快速排序在最坏情况下的时间复杂度为 O(________) 。
14. 快速排序在平均情况下的空间复杂度为 O(________) 。
成的有序表中适当的位置，此种排序方法叫做
________排序。
2. 第 i (i = 0, 1,
- 2…) ,趟n从参加排序的序列中第 i 个 ～ 第 n- 1 个元素中挑选出一个最小（大）元素，把
它交换到第 i 个位置，此种排序方法叫做 ________排序。
3. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列，就交换它们的位置，这种排序方法叫 做 ________排序。