第九章 排序

第九章 排序

一、选择题

1.下述排序算法中，稳定的是________。

A．直接选择排序 B．直接插入排序 C．快速排序 D．堆排序 2.下列排序算法中，________需要的辅助存储空间最大。

A．快速排序 B．插入排序 C．希尔排序 D．归并排序 3.下列排序算法中，________是稳定的。

A．插入、希尔 B．冒泡、快速 C．选择、堆排序 D．基数、归并 4.下列各种排序算法中平均时间复杂度为O(n2)的是________。

A．快速排序 B．堆排序 C．归并排序 D．冒泡排序 5. 在待排序的元素基本有序的前提下，效率最高的排序方法是________。 A．简单插入排序 B．简单选择排序 C．快速排序 D．归并排序 6. 利用直接插入排序法的思想建立一个有序线性表的时间复杂度为_______。 A．O(n) B．O(nlog2n) C．O(n2) D．O(log2n) 7. 对n个记录进行堆排序，所需要的辅助存储空间为________。 A．O(1og2n) B．O(n) C．O(1) D．O(n2) 8. 快速排序在最坏情况下的时间复杂度为________。

A．O(log2n) B．O(nlog2n) C．O(n) D．O(n2)

9. 设有序列12、42、37、19，当使用直接插入排序从小到大排序时，其比较次数为________。

A．3 B．4 C．5 D．6

10. 对数据元素序列( 49, 72, 68, 13, 38, 50, 97, 27 )排序，前三趟排序结束时的结果依次为：

第一趟：13, 72, 68, 49, 38, 50, 97, 27； 第二趟：13, 27, 68, 49, 38, 50, 97, 72； 第三趟：13, 27, 38, 49, 68, 50, 97, 72； 该排序采用的方法是_________。

A. 直接插入排序 B. 直接选择排序 C. 冒泡排序 D. 堆排序 11. 如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置

发生颠倒，则称该排序算法是不稳定的。________就是不稳定的排序方法。 A．起泡排序 B．归并排序 C．直接插入排序 D．简单选择排序 12. 设一组初始记录关键字的长度为8，则最多经过________趟插入排序可以得到有序序列。

A．6 B．7 C．8 D．9

13. 设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是________。 A． F，H，C，D，P，A，M，Q，R，S，Y，X B． P，A，C，S，Q，D，F，X，R，H，M，Y C． A，D，C，R，F，Q，M，S，Y，P，H，X D． H，C，Q，P，A，M，S，R，D，F，X，Y

14. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做________ 排序。

A．插入 B．堆 C．快速 D．归并

15.每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做________排序。

A．插入 B．堆 C．快速 D．归并 16.下列________种排序算法的平均时间复杂度为O(nlog2n)。

A．简单选择排序 B．简单插入排序 C．冒泡排序 D．归并排序 17. 下列________种排序算法更适合于外部排序。

A．选择排序 B．插入排序 C．冒泡排序 D．归并排序 18. 设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为________ 。

A．2，3，5，8，6 B．3，2，5，8，6 C．3，2，5，6，8 D．2，3，6，5，8 19. 二路归并排序的时间复杂度为________。

A． O(n) B．O(n2) C．O(nlog2n) D．O(log2n) 20. 时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是________。 A． 堆排序 B．冒泡排序 C．希尔排序 D．快速排序

21.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是________。 A．堆排序 B．冒泡排序 C．快速排序 D．希尔排序 22.设有5000 个待排序的记录关键字，如果需要用最快的方法选出其中最小的10 个记录关键字，则用下列________方法可以达到此目的。

A．快速排序 B．堆排序 C．归并排序 D．插入排序 23. 设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20 为基准记录的一趟快速排序结束后的结果为________。 A．10，15，14，18，20，36，40，21 B．10，15，14，18，20，40，36，21 C．10，15，14，20，18，40，36，2l D．15，10，14，18，20，36，40，21

24. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行________趟的分配和回收才能使得初始关键字序列变成有序序列。 A． 3 B． 4 C．5 D．8

25．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4 条记录关键字为________。 A．40，50，20，95 B．15，40，60，20 C．15，20，40，45 D．45，40，15，20

26. 设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为________。

A． 15，25，35，50，20，40，80，85，36，70 B． 15，25，35，50，80，20，85，40，70，36 C． 15，25，35，50，80，85，20，36，40，70 D． 15，25，35，50，80，20，36，40，70，85

27.对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为__________的结点开始。 A． 100 B． 12 C． 60 D．15

28.一组记录的排序码为（46，79，56，38，40，84），则堆排序时建立的初始

大顶堆为________。

A．79，46，56，38，40，80 B．38，46, 56，79， 40，84 C．84，79，56，38，40，46 D．84，56，79，40，46，38

二、填空题

1. 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4 为增量的一趟希尔排序结束后的结果为_______。

2. 对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为______，在整个排序过程中最多需要进行______趟排序才可以完成。

3. 设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为________。

4. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_______，整个堆排序过程的时间复杂度为________。

5. 对n个元素的序列进行起泡排序时，最少的比较次数是_______。

6. 在插入和选择排序中，若初始数据基本正序，则选用_______；若初始数据基本反序，则选用_______。

7. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较_______。 8. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果是________。

9. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果是_______。

10. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的结果为_______。

11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为_________。

12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用____ 排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用

_______排序。

13. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有_______。

14. 在快速排序、堆排序、归并排序中，_______排序是稳定的。

三、判断题

1. 直接选择排序是一种稳定的排序方法。 （ ） 2. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ） 3. 希尔排序算法的时间复杂度为O(n2)。 （ ） 4. 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（ ） 5. 一组关键码已完全有序时，最快的排序方法是快速排序。 （ ） 6. 快速排序是排序算法中平均性能最好的一种排序。 （ ） 7. 堆是完全二叉树，完全二叉树不一定是堆。 （ ） 8. 层次遍历初始堆可以得到一个有序的序列。 （ ） 9. 从平均性能而言，快速排序最佳，其所需时间最省。 （ ）

四、算法设计题

1.设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。

2.写一组英文单词按字典序排列的基数排序算法。设单词均由大写字母构成，最长的单词有d个字母。提示：所有长度不足d个字母的单词都在尾处补足空格，排序时设置27个箱子，分别与空格，A，B...Z对应。

3.对给定的j（1<=j<=n），要求在无序的记录区R［1…n］中找到按关键字自小到大排在第j个位置上的记录（即在无序集合中找到第j个最小元），试利用快速排序的划分思想编写算法实现上述的查找操作。

4.改写快速排序算法，要求采用前、中、后三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。