数据结构|《数据结构》-第八章排序(习题) 算法|数据结构

第八章排序排序作为各类数据结构的相应的运算的一种，在很多领域中都有广泛的应用。主要的排序方法有插入排序、交换排序、选择排序、二路归并排序、基数排序、外部排序等各类排序方法。堆排序、快速排序和归并排序是本章的重难点，应深入掌握各种排序算法的思想、排序过程(能动手模拟)和特征(初态的影响、复杂度、稳定性、适用性等)。
本章同样作为考察重点章节，通常以选择题的形式考查不同算法之间的对比。此外，对于一些常用排序算法的关键代码，要达到熟练编写的程度:看到某特定序列，读者应具有选择最优排序算法的能力。
一、选择题

1. 从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端的方法，称为（）。
A．归并排序B．冒泡排序C．插入排序D．选择排序
【答案】D。
2. 快速排序在下列（）情况下最易发挥其长处。
A．被排序的数据中含有多个相同排序码B．被排序的数据已基本有序
C．被排序的数据完全无序D．被排序的数据中的最大值和最小值相差悬殊
【答案】C 。B 选项是快速排序的最坏情况。
3. 堆是一种（）排序。
A．插入B．选择C．交换D．归并
【答案】B。
4. 下述几种排序方法中，要求内存最大的是（）。
A．希尔排序B．快速排序C．归并排序D．堆排序
【答案】C 。堆排序、希尔排序的空间复杂度为 O(1) ，快速排序的空间复杂度为 O(log 2n)，归并排序的空间复杂度为 O(n) 。
5. 数据表中有 10000 个元素，如果仅要求求出其中最大的 10 个元素，则采用 ( )算法最节省时间。
A．冒泡排序B．快速排序C．简单选择排序D．堆排序
【答案】D。
6. 下列排序算法中，（）不能保证每趟排序至少能将一个元素放到其最终的位置上。
A．希尔排序B．快速排序C．冒泡排序D．堆排序
【答案】A。快速排序的每趟排序能将作为枢轴的元素放到最终位置；冒泡排序的每趟排序能将最大或最小的元素放到最终位置；堆排序的每趟排序能将最大或最小的元素放到最终位置。
7. 对任意7个关键字进行基于比较的排序，至少要进行()次关键字之间的两两比较。
A.13B. 14C.15D. 6
【答案】A。对于任意序列进行基于比较的排序，求最少的比较次数应考虑最坏情况。对任意n个关键字排序的比较次数至少为「log2(n!)]。将n=7代入公式，答案为13。

8. 在下列算法中，( ) 算法可能出现下列情况:在最后一趟开始之前，所有元素都不在最终位置上。
A.堆排序B.冒泡排序C.直接插入排序D. 快速排序
【答案】C。在直接插入排序中，若待排序列中的最后一个元素应插入表中的第一个位置，则前面的有序子序列中的所有元素都不在最终位置上。

9.用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9, 1,4,13, 7,8, 20,23, 15，则该趟排序采用的增量(间隔)可能是( )。
A.2B.3C.4D. 5
【答案】B。首先，第二个元素为1,是整个序列中的最小元素，因此可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为2,则第1 +2个元素4明显比第1个元素9要小，A排除; 若增量为3，则第,i+3,i+6 (i=1, 2, 3)个元素都为有序序列，符合希尔排序的定义:若增量为4,则第1个元素9比第1+4个元素7要大，C排除:若增量为S,则第1个元素9比第1+5个元素8要大，D排除，选B.

10. 折半插入排序算法的时间复杂度为()。
A. O (n)B. O(nlog2n)C. O (n2)D. O(n3)
【答案】C。虽然折半插入排序是对直接插入排序的改进，但它改进的只是比较的次数，而移动次数未发生变化，时间复杂度仍为O(n2)。

11. 用某种排序方法对线性表{25, 84, 21, 47, 15, 27, 68, 35, 20}进行排序时，元素序列的变化情况如下:1) 25, 84,21, 47, 15, 27, 68, 35, 20
2) 20, 15, 21,25, 47,27, 68,35, 84
3) 15, 20,21,25, 35, 27, 47, 68, 84
4) 15, 20,21, 25, 27,35, 47, 68, 84，则所采用的排序方法是( )。
A.选择排序B.插入排序C.2路归并排序D.快速排序
【答案】D。选择排序在每趟结束后可以确定一个元素的最终位置，不对。插入排序，第i趟后前i+ 1个元素应该是有序的，不对。第2趟{20, 15}和{21, 25}是反序的，因此不是归并排序。快速排序每趟都将基准元素放在其最终位置，然后以它为基准将序列划分为两个子序列。观察题中的排序过程，可知是快速排序。
12. 快速排序算法在()情况下最不利于发挥其长处。
A.要排序的数据量太大B.要排序的数据中含有多个相同值
C.要排序的数据个数为奇数D.要排序的数据已基本有序
【答案】D。当待排序数据为基本有序时，每次选取第n个元素为基准，会导致划分区间分配不均匀，不利于发挥快速排序算法的优势。相反，当待排序数据分布较为随机时，基准元素能将序列划分为两个长度大致相等的序列，这时才能发挥快速排序的优势。
13. 数据序列F= {2,1,4,9, 8, 10, 6, 20}只能是下列排序算法中的( ) 两趟排序后的结果。
A.快速排序B.冒泡排序C.选择排序D.插入排序.
【答案】A。若为插入排序，则前三个元素应该是有序的，显然不对。而冒泡排序和选择排序经过两趟排序后应该有两个元素处于最终位置(最左/右端)，无论是按从小到大还是从大到小排序，数据序列中都没有两个满足这样的条件的元素，因此只可能选A。
14. 对下列关键字序列用快排进行排序时，速度最快的情形是( ), 速度最慢的情形是( ).
A. {21, 25,5, 17, 9, 23, 30}B. {25, 23, 30, 17,21,5,9}
C. {21,9, 17, 30, 25, 23, 5}D. {5,9, 17,21, 23, 25, 30}
【答案】A、D。由考点精析可知，当每次的枢轴都把表等分为长度相近的两个子表时，速度是最快的；当表本身已经有序或逆序时，速度最慢。选项D中的序列已按关键字排好序，因此它是最慢的，而A中第一趟枢轴值21将表划分为两个子表{9, 17, 5}和{25, 23, 30},而后对两个子表划分时，枢轴值再次将它们等分，所以该序列是快速排序最优的情况，速度最快。其他选项可以类似分析。
15. 下列序列中，( )可能是执行第一趟快速排序后所得到的序列。
I. {68, 11,18, 69, 23, 93, 73}II. {68, 11, 69, 23, 18, 93, 73}
II，{93, 73, 68, 11, 69, 23, 18}IV. {68, 11, 69, 23, 18, 73, 93}
A.I、IVB.Il、IIIC.III、IVD.只有IV
【答案】C。显然，若按从小到大排序，则最终有序的序列是{11, 18, 23, 68, 69, 73, 93}; 若按从大到小排序，则最终有序的序列是{93, 73, 69, 68, 23, 18, 11}。对比可知1、I中没有处于最终位置的元素,故I、II都不可能。III 中73和93处于从大到小排序后的最终位置，而且73将序列分割成大于73和小于73的两部分，故m是有可能的。IV中73和93处于从小到大排列后的最终位置，73也将序列分割成大于73和小于73的两部分。
16.下列选项中，不可能是快速排序第2趟排序结果的是()。
A.2,3,5,4,6,7,9B. 2,7,5,6,4,3,9
C. 3,2,5,4, 7,6,9D.4,2,3,5, 7, 6,9
【答案】C。快排的阶段性排序结果的特点是，第i趟完成时，会有i个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要找不存在两个这样的数的选项。A选项中2,3, 6, 7, 9均符合，所以A排除; B选项中，2,9 均符合，所以B排除; D选项中5, 9均符合，所以D排除; 最后看C选项，只有9一个数符合，所以C不可能是快速排序第二趟的结果。
17. 对n个关键字进行快速排序，最大递归深度为( )，最小递归深度为( )。
A. 1B. nC. log2nD. nlog2n
【答案】B、C。快速排序过程构成一个递归树，递归深度即递归树的高度。枢轴值每次都将子表等分时，递归树的高为log2n; 枢轴值每次都是子表的最大值或最小值时，递归树退化为单链表,树高为n。
18. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是( )。
A.5,2, 16, 12, 28, 60, 32, 72B.2, 16.5, 28, 12, 60, 32, 72
C.2, 12, 16, 5, 28,32, 72, 60D.5,2, 12, 28, 16, 32, 72, 60
【答案】D。要理解清楚排序过程中一“趟”的含义，题干也进行了解释_--对尚未确定最终位置的所有元素都处理一遍才是一趟，所以此时要对前后两块子表各做一次快速排序才是一 “趟”快速排序，如果只对一块子表进行了排序，而未处理另-块子表，就不能算是完整的一趟。选项A，第一趟匹配72,只余一块无序序列，第二趟匹配28，A可能。选项B，第一趟匹配2,第二趟匹配72, B可能。选项C，第一趟匹配2,第二趟匹配28或32, C可能。选项D,无论是先匹配12还是先匹配32,都会将序列分成两块，那么第二趟必须有两个元素匹配，所以D不可能，故选D.
19. 简单选择排序算法的比较次数和移动次数分别为( )。
A. O (n), O(log2n)B. O(log2n), O (n2)
C. O (n2), O(n)D. O(nlog2n), O(n)
【答案】C。
20.设线性表中每个元素有两个数据项k和k2，现对线性表按以下规则进行排序:先看数据项k, k值小的元素在前，大的元素在后; 在k值相同的情况下，再看k，kz值小的在前，大的元案在后，满足这种要求的排序方法是()。
A.先按k1进行直接插入排序，再按k2进行简单选择排序
B.先按k2进行直接插入排序，再按k1进行简单选择排序
C.先按k1进行简单选择排序，再按k2进行直接插入排序
D.先按k2进行简单选择排序，再按k1进行直接插入排序
【答案】D。首先应确定k1、k2的排序顺序，若先排k1再排k2,则排序结果不符合题意，排除选项A、C。再考虑算法的稳定性，当k2排好序后，再对k1排序，若对k1排序采用的算法是不稳定的，则对于k1相同而k2不同的元素可能会改变相对次序，从而不一定能满足题干中的条件“在k1值相同的情况下，k2值小的元素在前，大的元素在后”。直接插入排序算法是稳定的，而简单选择排序算法是不稳定的，故只能选D。
21. 向具有n个结点的堆中插入一个新元素的时间复杂度为( ), 删除一个元素的时间复杂度为( )。
A. O (1)B. O(n)C. O (log2n)D. O(nlog2n)
【答案】C、C。在向有n个元案的堆中插入一个新元素时，需要调用一个向上调整的算法，比较次数最多等于树的高度减1,由于树的高度为Llog2nJ+ 1,所以堆的向.上调整算法的比较次数最多等于Llog2nJ。此处需要注意，调整堆和建初始堆的时间复杂度是不一样的。
22. 构建n个记录的初始堆，其时间复杂度为( ); 对n个记录进行堆排序，最坏情况下其时间复杂度为( )。
A. O(n)B. O (n2)C. O(log2n)D. O(nlog2n)
【答案】A、D。建堆过程中，向下调整的时间与树高h有关，为O(h).每次向下调整时，大部分结点的高度都较小。因此，可以证明在元素个数为n的序列上建堆，其时间复杂度为0(n)。无论是在最好情况下还是在最坏情况下，堆排序的时间复杂度均为o(nlog2n)o。
23.巳知小根堆为8, 15, 10, 21,34, 16, 12,删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是( )。
A.1B.2C.3D.4
【答案】C。删除8后，将12移动到堆项，第一次是15和10比较，第二次是10和12比较并交换，第三次还需比较12和16，故比较次数为3。
24. 以下排序算法中，( )不需要进行关键字的比较。
A.快速排序B.归并排序C.基数排序D.堆排序
【答案】C。基数排序是基于关键字各位的大小进行排序的，而不是基于关键字的比较进行的。
25. 在下列排序算法中，平均情况下空间复杂度为O(n)的是(); 最坏情况下空间复杂度为O(n)的是()。
I.希尔排序I.堆排序II.冒泡排序IV.归并排序V.快速排序VI.基数排序
A. I、IV、VIB. II、VC. IV、VD. IV
【答案】D、C。归并排序算法在平均情况下和最坏情况下的空间复杂度都会达到O(n),快速排序只在最坏情况下才会达到O(n),平均情况下为O(log2n)。所以归并排序算法可视为本章所有算法中占用辅助空间最多的排序算法。
26. 2路归并排序中，归并趟数的数量级是( ).
A. O(n)B. O (log2n)C. O(nlogzn)D. O (n2)
【答案】B。对N个元素进行k路归并排序时，排序的趟数m满足k"=N,所以m = ? logN ?,本题中即为? log2n ?.

27. 将两个各有N个元素的有序表合并成一个有序表，最少的比较次数是()，最多的比较次数是()。
A. NB.2N-1C.2ND.N-1
【答案】A、B。注意到当一个表中的最小元素比另一个表中的最大元素还大时，比较的次数是最少的，仅比较N次; 而当两个表中的元素依次间隔地比较时，即a1 A.05, 46, 13, 55, 94, 17, 42B.05, 13, 17, 42, 46, 55, 94
C.42, 13, 94, 05, 55, 46, 17D. 05, 13, 46, 55, 17, 42, 94
【答案】C。比较各数的个位数，按各数的个位数进行排序，可知选C。
29. 排序趟数与序列的原始状态无关的排序方法是( )。
I. 直接插入排序II.简单选择排序II.冒泡排序IV.基数排序
A.I、IIIB. I、II、IVC. I、II、IIID. I、IV
【答案】B。交换类的排序，其趟数和原始序列状态有关，故冒泡排序与初始序列有关。直接插入排序:每趟排序都插入一个元素，所以排序趟数固定为n-1; 简单选择排序:每趟排序都选出一个最小(或最大)的元素，所以排序趟数固定为n-1; 基数排序:每趟排序都要进行“分配”和“收集”，排序趟数固定为d。
30. 置换-选择排序的作用是( )。
A.用于生成外部排序的初始归并段
B.完成将一个磁盘文件排序成有序文件的有效的外部排序算法
C.生成的初始归并段的长度是内存工作区的2倍
D.对外部排序中输入/归并/输出的并行处理
【答案】A。置换选择排序是外部排序中生成初始归并段的方法,用此方法得到的初始归并段的长度是不; 等长的，其长度平均是传统等长初始归并段的2倍，从而使得初始归并段数减少到原来的近二分之一。但是，置换选择排序不是一-种完整的生成有序文件的外部排序算法。
31. 在下列关于外部排序过程输入/输出缓冲区作用的叙述中，不正确的是( )。
A.暂存输入/输出记录B.内部归并的工作区
C.产生初始归并段的工作区D.传送用户界面的消息
【答案】D。在外部排序过程中输入/输出缓冲区就是排序的内存工作区，例如做m路平衡归并需要m个输入缓冲区和1个输出缓冲区，用以存放参加归并的和归并完成的记录。在产生初始归并段时也可用作内部排序的工作区。它没有传送用户界面的消息的任务。
32. 在做m路平衡归并排序的过程中，为实现输入内部归并/输出的并行处理，需要设置( ① )个输入缓冲区和( ② )个输出缓冲区。
①A.2B. mC. 2m- 1D.2m
②A.2B. mC.2m- 1D.2m
【答案】D、A。在做m路平衡归并排序的过程中，为实现输入/内部归并/输出的并行处理，需要设置2m个输入缓冲区和2个输出缓冲区，以便在执行内部归并时，能同时进行输入/输出操作。若仅设置m个输入缓冲区，则仅能进行串行操作，无法并行处理。

二、填空题

1. 设 T 为一棵平衡树，在其中插入一个结点 n，然后立即删除该结点后得到 T1，则 T 与 T1 必定相同。（）
【答案】×。平衡树在插入结点后，如果平衡被破坏，则需进行调整，在进行删除结点后，T与T1则不相同。
2. 在9阶B-树中，除叶子以外的任意结点的分指数介于5和9之间。（）
【答案】×。未指出根至少有两个结点。
3. B-树的插入算法中，通过结点的向上“分裂”，代替了专门的平衡调整。（）
【答案】√。多路平衡树就是这样。
4. 堆肯定是一棵平衡二叉树。（）
【答案】×。堆是二叉树。而平衡二叉树要求左右子树遵循左小右大的规律，而堆不能保证该规律。
5. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）
【答案】×。相同关键字的位置。

三、综合应用题

1. 设待排序的关键字序列为 {12 ， 2， 16 ， 30 ， 28， 10， 16* ， 20 ， 6， 18} ，试分别写
出使用以下排序方法，每趟排序结束后关键字序列的状态。
① 直接插入排序② 折半插入排序③ 希尔排序（增量选取 5， 3， 1）
④ 冒泡排序⑤ 快速排序⑥ 简单选择排序
⑦ 二路归并排序
【答案】①直接插入排序，过程如下：
[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]
② 折半插入排序排序过程同①；
③ 希尔排序（增量选取 5， 3， 1），过程如下：
10 2 16 6 18 12 16* 20 30 28 （增量选取 5）
6 2 12 10 18 16 16* 20 30 28 （增量选取 3）
2 6 10 12 16 16* 18 20 28 30 （增量选取 1）
④ 冒泡排序，过程如下：
2 12 16 28 10 16* 20 6 18 [30]
2 12 16 10 16* 20 6 18 [28 30]
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]
⑤ 快速排序，过程如下：
12 [6 2 10] 12 [28 30 16* 20 16 18]
6 [2] 6 [10] 12 [28 30 16* 20 16 18 ]
28 2 6 10 12 [18 16 16* 20 ] 28 [30 ]
18 2 6 10 12 [16* 16] 18 [20] 28 30
16* 2 6 10 12 16* [16] 18 20 28 30
左子序列递归深度为 1，右子序列递归深度为 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 18]
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]
⑦二路归并排序，过程如下：
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

2. 给出如下关键字序列｛ 321 ， 156 ， 57 ， 46 ， 28 ， 7， 331 ， 33， 34 ， 63｝，试按链式基数排序方法，列出每一趟分配和收集的过程。
【答案】
按最低位优先法 → 321 → 156 → 57 → 46→ 28 → 7→ 331→ 33 → 34→ 63
分配 [0][1][2][3][4][5][6][7][8][9]
32133341565728
33163467
收集 → 321→ 331 → 33 → 63→ 34→ 156→ 46 → 57→ 7→ 28

3. 对输入文件（ 101 ， 51 ， 19， 61 ， 3， 71 ， 31， 17， 19 ， 100， 55 ， 20，9， 30 ， 50 ，6， 90 ）；当 k=6 时，使用置换 - 选择算法，写出建立的初始败者树及生成的初始归并段。
【答案】初始败者树，如图所示：
数据结构|《数据结构》-第八章排序(习题)

文章图片

初始归并段： R1:3,19,31,51,61,71,100,101
R2:9,17,19,20,30,50,55,90
R3 :6

4. 给出关键字序列{50, 26, 38, 80, 70, 90, 8, 30, 40, 20}的希尔排序过程(取增量序列为d= {5,3, 1}，排序结果为从小到大排列)。
【答案】原始序列:50, 26, 38, 80, 70, 90, 8, 30, 40, 20
第一趟(增量5): 50, 8, 30, 40, 20, 90, 26, 38, 80, 70
第二趟(增量3): 26, 8, 30, 40, 20, 80, 50, 38, 90, 70
第三趟(增量1): 8, 20, 26, 30, 38, 40, 50, 70, 80, 90

四、算法题

1. 试以单链表为存储结构，实现简单选择排序算法。

2. 有 n 个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。

3. 编写算法，对 n 个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：
① 采用顺序存储结构，至多使用一个记录的辅助存储空间；
② 算法的时间复杂度为 O(n) 。

【注】所有题目的代码不唯一，如需参考答案可私信。