一、填空题
1. 大多数排序算法都有两个基本的操作： 比较 和 移动 。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插
入到有序表时，为寻找插入位置至少需比较 3 次。 3. 在插入和选择排序中，若初始数据基本正序，则选用 插入 ；若初始数据基本反序，则选用
选择 。 正序时两种方法移动次数均为0，但比较次数量级不同，插入法：n-1即O(n)，选择法：O(n2) 反序时两种方法比较次数量级相同，均为O(n2)，但移动次数不同，插入法：O(n2)，选择法：3(n-1)即O(n) 4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 ；若初始记录基本无
序，则最好选用 快速排序 。 5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 O(n2) 。若对其进行快速
排序，在最坏的情况下所需要的时间是 O(n2) 。
6. 对于n个记录的集合进行归并排序，所需要的平均时间是 O(nlog2n) ，所需要的附加空间
是 O(n) 。 7． 对于n个记录的表进行2路归并排序，整个归并排序需进行 ┌log2n┐ 趟（遍）。 8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ； 二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X ； 堆排序初始建堆的结果是 Y S X R P C M H Q D F A 。（大根堆）
9. 在堆排序、快速排序和归并排序中，
若只从存储空间考虑，则应首先选取 堆排序 方法，其次选取 快速排序方法，最后选取归并排序方法； 若只从排序结果的稳定性考虑，则应 选取归并排序方法； 若只从平均情况下最快考虑，则应选取快速排序方法；
若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。
二、单项选择题
（ C ）1． 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比
较，将其放入已排序序列的正确位置上的方法，称为
Ａ. 归并排序 Ｂ. 冒泡排序 Ｃ. 插入排序 Ｄ. 选择排序
（ D ）2．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为
Ａ. 冒泡排序 Ｂ. 归并排序 Ｃ. 插入排序 Ｄ. 选择排序 （ B ）3．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。
Ａ. 从小到大排列好的 Ｂ. 从大到小排列好的 Ｃ. 元素无序 Ｄ. 元素基本有序 （ D ）4．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为
Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n(n-1)/2
（ C ）5．快速排序在下列哪种情况下最易发挥其长处。
Ａ. 被排序的数据中含有多个相同排序码 Ｂ. 被排序的数据已基本有序
Ｃ. 被排序的数据完全无序 Ｄ. 被排序的数据中的最大值和最小值相差悬殊 （ B ）6． 对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是
A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)
（ C ）7．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基
准得到的一次划分结果为
Ａ. 38, 40, 46, 56, 79, 84 Ｂ. 40, 38, 46 , 79, 56, 84 Ｃ. 40, 38，46, 56, 79, 84 Ｄ. 40, 38, 46, 84, 56, 79 （ D ）8．下列关键字序列中， 是堆。
Ａ. 16, 72, 31, 23, 94, 53 Ｂ. 94, 23, 31, 72, 16, 53 Ｃ. 16, 53, 23, 94，31, 72 Ｄ. 16, 23, 53, 31, 94, 72 （ B ）9．堆是一种 排序。
Ａ. 插入 Ｂ.选择 Ｃ. 交换 Ｄ. 归并
（ C ）10．堆的形状是一棵
Ａ. 二叉排序树 Ｂ.满二叉树 Ｃ. 完全二叉树 Ｄ. 平衡二叉树 （ B ）11．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为
Ａ. 79, 46, 56, 38, 40, 84 Ｂ. 84, 79, 56, 38, 40, 46 Ｃ. 84, 79, 56, 46, 40, 38 Ｄ. 84, 56, 79, 40, 46, 38 （ C ）12． 下述几种排序方法中，要求内存最大的是
Ａ. 插入排序 Ｂ.快速排序 Ｃ. 归并排序 Ｄ. 选择排序
三、简答题
设待排序的关键码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。 (1) 直接插入排序 (2)起泡排序 (3) 直接选择排序 (4) 快速排序 (5) 二路归并排序(6)堆排序
（1）直接插入排序
[12] 2 16 30 28 10 16* 20 6 18 [2 12] 16 30 28 10 16* 20 6 18 [2 12 16] 30 28 10 16* 20 6 18 [2 12 16 30] 28 10 16* 20 6 18 [2 12 16 28 30] 10 16* 20 6 18 [2 10 12 16 28 30] 16* 20 6 18 [2 10 12 16 16* 28 30] 20 6 18 [2 10 12 16 16* 20 28 30] 6 18 [2 6 10 12 16 16* 20 28 30] 18 [2 6 10 12 16 16* 18 20 28 30]
（2）起泡排序
2 12 16 28 10 16* 20 6 18 [30] 2 12 16 10 16* 20 6 18 [28 30]
2
2 12 10 16 16* 6 18 [20 28 30] 2 10 12 16 6 16* [18 20 28 30] 2 10 12 6 16 [16* 18 20 28 30] 2 10 6 12 [16 16* 18 20 28 30] 2 6 10 [12 16 16* 18 20 28 30]
2 6 10 12 16 16* 18 20 28 30]
（3）直接选择排序
2 [12 16 30 28 10 16* 20 6 18] 2 6 [16 30 28 10 16* 20 12 18] 2 6 10 [30 28 16 16* 20 12 18] 2 6 10 12 [28 16 16* 20 30 18] 2 6 10 12 16 [28 16* 20 30 18] 2 6 10 12 16 16* [28 20 30 28] 2 6 10 12 16 16* 18 [20 30 28] 2 6 10 12 16 16* 18 20 [28 30] 2 6 10 12 16 16* 18 20 28 [30]
（4）快速排序
12 [12 2 16 30 28 10 16* 20 6 18] 6 [6 2 10] 12 [28 30 16* 20 16 18] 28 [2] 6 [10] 12 [28 30 16* 20 16 18 ] 18 2 6 10 12 [18 16 16* 20 ] 28 [30 ] 16* 2 6 10 12 [16* 16] 18 [20] 28 30 2 6 10 12 16* [16] 18 20 28 30 左子序列递归深度为1，右子序列递归深度为3。
（5）二路归并排序
12 2 16 30 28 10 16* 20 6 18 2 12 16 30 10 28 16 * 20 6 18 2 12 16 30 10 16 * 20 28 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 18 20 28 30
（6）堆排序
第一步,形成初始大根堆（详细过程略），第二步做堆排序。
3
12 2 16 30 28 10 16* 20 6 18 初始排序 不是大根堆 12 28 16 20 18 10 16* 2 6 30 交换1与10对象 6 20 16 12 18 10 16* 2 28 30 交换1与9对象 2 18 16 12 6 10 16* 20 28 30 交换1与8对象 4
30 28 16 20 18 10 16* 2 6 12
形成初始大根堆
28 20 16 12 18 10 16* 2 6 30
从1到9重新形成堆
20 18 16 12 6 10 16* 2 28 30
从1到8重新形成堆
18 12 16 2 12 10 16* 20 28 30
从1到7重新形成堆
16* 12 16 2 6 10 18 20 28 30 交换1与7对象 10 12 16 2 6 16* 18 20 28 30 交换1与6对象 6 12 10 2 16 16* 18 20 28 30 交换1与5对象 12 6 10 12 16 16* 18 20 28 30 交换1与4对象 5
16* 12 16 2 6 10 18 20 28 30
从1到6重新形成堆
16 12 10 2 6 16* 18 20 28 30
从1到5重新形成堆
12 6 10 2 16 16* 18 20 28 30
从1到4重新形成堆
10 6 2 12 16 16* 18 20 28 30
从1到3重新形成堆
2 6 12 16 16* 10 18 12 2 16 6 10 16* 18 20 28 30 20 交换1与3对象
2 6 10 12 16 16* 18 20 28 30 交换1与2对象
6
28 30
从1到2重新形成堆 2 6 10 12 16 16* 18 20 28 30 得到结果
因篇幅问题不能全部显示，请点此查看更多更全内容