* *
数据结构课程（本科）第九章试题
一、单项选择题
1. 若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（ ）方法比较次数最少。
A. 直接插入排序 C. 归并排序
B. 快速排序 D. 直接选择排序
2. 如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（ ）方法最快。
A. 起泡排序
B. 快速排序 D. 堆排序
C. 直接选择排序
3. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，
直到子序列为空或只剩一个元素为止。这样的排序方法是（ ）。
A. 直接选择排序 C. 快速排序
4. 对5个不同的数据元素进行直接插入排序，最多需要进行（ ）次比较？
A. 8 C. 15
5. 如果输入序列是已经排好顺序的，则下列算法中（ ）算法最快结束？
A. 起泡排序
B. 直接插入排序
B. 10 D. 25
B. 直接插入排序 D. 起泡排序
* *
C. 直接选择排序
D. 快速排序
6. 如果输入序列是已经排好顺序的，则下列算法中（ ）算法最慢结束？
A. 起泡排序
B. 直接插入排序 D. 快速排序
C. 直接选择排序
7. 下列排序算法中（ ）算法是不稳定的。
A. 起泡排序 C. 基数排序
B. 直接插入排序 D. 快速排序
8. 假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排
序，则应取的归并路数至少是（ ）。
A. 3
9. 采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（ ）次比较。
A. 5
10. 下列算法中（ ）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成
排序。
A. 起泡排序 C. 快速排序
11. 使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（ ）。
B. 希尔排序 D. 直接选择排序
B. 6
C. 7
D. 8
B. 4
C. 5
D. 6
* *
A. 每次序列的划分应该在线性时间内完成 B. 每次归并的两个子序列长度接近 C. 每次归并在线性时间内完成 D. 以上全是
12. 在基于排序码比较的排序算法中，（ ）算法的最坏情况下的时间复杂度不高于O(nlog2n)。
A. 起泡排序 C. 归并排序
13. 在下列排序算法中，（ ）算法使用的附加空间与输入序列的长度及初始排列无关。
A. 锦标赛排序 C. 基数排序
14. 一个对象序列的排序码为 { 46, 79, 56, 38, 40, 84 }，采用快速排序（以位于最左位置的对象为基准
而）得到的第一次划分结果为：
A. { 38, 46, 79, 56, 40, 84 } C. { 40, 38, 46, 79, 56, 84 }
15. 如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中（ ）
算法最快。
A. 归并排序 C. 快速排序
B. 希尔排序 D. 基数排序
B. { 38, 79, 56, 46, 40, 84 } D. { 38, 46, 56, 79, 40, 84 }
B. 快速排序 D. 归并排序
B. 希尔排序 D. 快速排序
《数据结构》知识题汇编09第九章排序试题
