《第九章 排序》由会员分享，可在线阅读，更多相关《第九章 排序（6页珍藏版）》请在金锄头文库上搜索。
1、第九章 排序一、选择题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.
2、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. 3B. 4C. 5 D. 610. 对数据元素序列( 49, 72, 68, 13, 38, 50, 97, 27 )排序，前三趟排序结束时的结 果依次为：第一趟：13, 72, 68, 49, 38, 5
3、0, 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，则最多经过趟插入排序可以得到有序序列。A6B7C8D913. 设一组初始记录关键字序列为(Q, H, C, Y, P
4、, A, M, S, R, D, F, X),则按字母升序的第一趟冒泡排序结束后的结果是。A.F,H,C,D,P,A,M,Q,R,S,Y,XB.P,A,C,S,Q,D,F,X,R,H,M,YC.A,D,C,R,F,Q,MS,Y,P,H,XD.H,C,Q,P,A,M,S,R,D,F,X,Y14. 每次从无序表中取出一个元素,把它插入到有序表中的适当位置,此种排序方法叫做 排序。A.插入B.堆C.快速D.归并15. 每次从无序表中挑选出一个最小或最大元素,把它交换到有序表的一端,此种排序方法叫做排序。A.插入B.堆C.快速D.归并16. 下列种排序算法的平均时间复杂度为O (nlog2n)。A.简
5、单选择排序 B.简单插入排序C.冒泡排序 D.归并排序17. 下列种排序算法更适合于外部排序。A.选择排序B.插入排序C.冒泡排序 D.归并排序18. 设一组初始记录关键字序列(5, 2, 6, 3, 8),以第一个记录关键字5为基准进行一趟快速排序的结果为 。A.2,3, 5,8,6B.3, 2, 5,8,6C.3,2, 5,6,8D.2, 3, 6,5,819. 二路归并排序的时间复杂度为。A. O(n)B. O(n2)C. O(nlog2n)D. O(log2n)20. 时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是。A. 堆排序 B.冒泡排序C.希尔排序D.快速排序21.
6、一趟排序结束后不一定能够选出一个元素放在其最终位置上的是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，21B. 10，15，14，18，20，40，36，21C. 10，15，14，20，18，40，36，2lD. 15，10，14，18
7、，20，36，40，2124. 设一组初始记录关键字序列为（345，253，674，924，627），则用基数排序需要进行趟的分配和回收才能使得初始关键字序列变成有序序列。A. 3B. 4C. 5 D. 825. 设一组初始记录关键字序列为（50，40，95，20，15，70，60，45），则以增量d=4的一趟希尔排序结束后前4条记录关键字为。A. 40，50，20，95B. 15，40，60，20C. 15，20，40，45D. 45，40，15，2026. 设一组初始记录关键字序列为（25，50，15，35，80，85，20，40，36，70）， 其中含有5个长度为2的有序子表，则用归并排
8、序的方法对该记录关键字序列进行趟归并后的结果为A.15，25，35，50，20，40，80，85，36，70B.15，25，35，50，80，20，85，40，70，36C.15，25，35，50，80，85，20，36，40，70D.15，25，35，50，80，20，36，40，70，8527. 对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为的结点开始。A. 100B. 12 C. 60D. 1528. 一组记录的排序码为（46，79，56，38，40，84），则堆排序时建立的初始大顶堆为。A79，46，56，38，40，80
9、B38，46, 56，79， 40，84C84，79，56，38，40，46D84，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. 在堆排序的过程中,对任一分支结点进行筛运
10、算的时间复杂度为,整个堆排序过程的时间复杂度为。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. 设一组初
11、始关键字序列为(38, 65, 97, 76, 13, 27, 10),则第3趟冒泡排序结束后的结果为。11. 设一组初始记录关键字为(72, 73, 71, 23, 94, 16, 5),则以记录关键字72为基准的一趟快速排序结果为。12. 当待排序的记录数较大,排序码较随机且对稳定性不作要求时,宜采用排序；当待排序的记录数较大,存储空间允许且要求排序是稳定时,宜采用排序。13. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排 序中，排序是不稳定的有。14. 在快速排序、堆排序、归并排序中，排序是稳定的。三、判断题1. 直接选择排序是一种稳定的排序方法。 ( )2. 冒泡
12、排序在初始关键字序列为逆序的情况下执行的交换次数最多。( )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 ln中找到按关键字自小 到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快 速排序的划分思想编写算法实现上述的查找操作。4.改写快速排序算法，要求采用前、中、后三者取中的方式选择划分的基准记录； 若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对 其排序。
