第十章 排序作业（共 50 分） 一、选择题（每题 2 分，共 22 分）。 1．若表 R 在排序前已按键值递增顺序排列，则（ A ）算法的比较次数最少。 A．直接插入排序 C．归并排序 B．快速排序 D．选择排序 2．对各种内部排序方法来说，（ B ）。 A．快速排序时间性能最佳 B．归并排序是稳定的排序方法 C．快速排序是一种选择排序 D．堆排序所用的辅助空间比较大 3. 排序算法的稳定性是指（ A ）。 A．经过排序之后，能使值相同的数据保持原顺序中的相对位置不变。 B．经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变。 C．排序算法的性能与被排序元素的数量关系不大 D．排序算法的性能与被排序元素的数量关系密切 4. 如下序列中，（ B ）序列是大顶堆。 A. C. {4,5,3,2,1} {1,2,3,4,5} {5,3,4,1,2} {1,2,3,5,4} B. D. 5. 若将{3,2,5,4,1}排为升序，则实施快速排序一趟后的结果是（ A ）（其中， 枢轴记录取首记录）。 A. C. {1,2,3,4,5} {1,3,5,4,2} {1,2,4,5,3} {2,5,4,1,3} B. D. 6. 若将{1,2,3,4,5,6,7,9,8}排为升序，则（ C ）排序方法的“比较记录”次数最 少。 A. 快速排序 C. 直接插入排序 B. 简单选择排序 D. 冒泡排序 7. 若将{5,4,3,2,1}排为升序，则（ B ）排序方法的“移动记录”次数最多。 A. 快速排序 C. 直接插入排序 B. 冒泡排序 D. 简单选择排序 8. 用简单选择排序将顺序表{2,3,1 ,3′,2′}排为升序，实施排序 1 趟后结果是 {1 ,3,2 ,3′,2′}，则排序 3 趟后的结果是 （ D ）。 A. C. {1 ,2 ,2′,3 ,3′} {1 ,2 ,2′,3′,3 } {1 ,2,3 ,3′,2′} {1 ,2′,2 ,3 ,3′} B. D. 9．下列排序算法中，（ C ）排序在某趟结束后不一定选出一个元素放到其最 

终的位置上。 A．选择 B．冒泡 C．归并 D．堆 10．下列排序算法中，稳定的排序算法是：（ B ）。 A．堆排序 C．快速排序 B．直接插入排序 D．希尔排序 11．堆排序的时间复杂度是（ B ）。 A．O(n*n) C．O(n) B．O(n*log n) D．O(log n) 二、填空题（每空 4 分，共 4 分）。 1．对 n 个元素进行归并排序，空间复杂度为 O（n）。 三、综合题（共 24 分）。 1. （共 12 分）有一组待排序的关键字如下： (54，38，96，23，15，72，60，45，83) 分别写出希尔排序(d=5)、快速排序、堆排序、归并排序第一趟升序排序后的结 果（其中堆排序的第一趟指序列完成初始建堆、将堆顶元素置为最末位子后其余 元素调整为堆的结果）（每个 3 分）。 希尔排序：(54，38，45，23，15，72，60，96，83) 快速排序：(44，38，15，23，54，72，60，96，83) 堆排序：(83，45，72，38，15，54，60，23，96) 归并排序：(38，54，23，96，15，72，45，60，83) 2. （共 12 分）已知数据序列为(12，5，9，20，6，31，24)，对该项数据序列进 行排序，分别写出直接插入排序、简单选择排序、快速排序、堆排序、二路归并 排序及基数排序第一趟升序排序结果（其中堆排序的第一趟指序列完成初始建 堆、将堆顶元素置为最末位子后其余元素调整为堆的结果）（每个 2 分）。 直接插入排序：(5，12，9，20，6，31，24) 简单选择排序：(5，12，9，20，6，31，24) 快速排序：(6，5，9，12，20，31，24) 堆排序：(24，20，12，5，6，9，31) 二路归并排序：(5，12，9，20，6，31，24) 基数排序：(20，31，12，24，5，6，9)