第9章排序自测卷空题

第9章 排序 自测卷姓名 班级题号一一二三四五总分题分241836814100得分一、填空题（每空 1 分，共 24 分）1. 大多数排序算法都有两个基本的操作：和。2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第 7个记录 60插入到有序表时，为寻找插入位置至少需比较次。3. 在插入和选择排序中，若初始数据基本正序，则选用 ;若初始数据基本反序，则选用。4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用;若初始记录基本无序，则最好选用。5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间 。若对其进行快速排序，在最坏的情况下所需要的时间 。6. 对于n个记录的集合进行归并排序，所需要的平均时间是，所需要的附加空间是。7. 对于n个记录的表进行2路归并排序，整个归并排序需进行（遍）共计移动 次记录。8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是;初始步长为4的希尔（shell）排序一趟的结果是;二路归并排序一趟扫描的结果;快速排序一趟扫描的结果是;堆排序初始建堆的结果是。9. 在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取方法，其次选取方法，最后选取方法；若只从排序结果的稳定性考虑，则应选取方法；若只从平均情况下最快考虑，则应选取方法；若只从最坏情况下最快并且要节省内存考虑，则应选取方法。二、单项选择题（每小题 1分，共18分）（）1.将5个不同的数据进行排序，至多需要比较次。A. 8B. 9C. 10D. 25（）2. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为A希尔排序B.冒泡排序C.插入排序D选择排序（）3.从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为A . 希尔排序B . 归并排序C . 插入排序D . 选择排序()4.对n个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。A.从小到大排列好的B.从大到小排列好的C.元素无序D.元素基本有序()5.对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为A. n+1B. nC. n-1D. n(n-1)/2)6.快速排序在下列哪种情况下最易发挥其长处。A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C . 被排序的数据完全无序D . 被排序的数据中的最大值和最小值相差悬殊()7.对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是A. O(n)B. O(n2)C. O(nlog2n)D. O(n3)8.若一组记录的排序码为(46, 79, 56, 38, 40, 84)，则利用快速排序的方法，以第一个记录为基 准得到的一次划分结果为A .38,40,46, 56, 79, 84B . 40, 38, 46 , 79, 56, 84C .40,38，46, 56, 79, 84D . 40, 38, 46,84, 56, 79()9.在最好情况下，下列排序算法中排序算法所需比较关键字次数最少。A.冒泡B.归并C.快速D.直接插入()10.置换选择排序的功能是。A.选出最大的元素B.产生初始归并段C.产生有序文件D.置换某个记录()11.将5个不同的数据进行排序，至少需要比 次。A. 4B. 5C. 6D. 7()12.下列关键字序列中，是堆。A. 16, 72, 31, 23, 94, 53C. 16, 53, 23, 94， 31, 72()13.堆是一种排序。A.插入B.选择14.堆的形状是一棵A . 二叉排序树B .满二叉树B. 94, 23, 31, 72, 16, 53D. 16, 23, 53, 31, 94, 72C.交换D.归并C完全二叉树D.平衡二叉树15.若一组记录的排序码为(46, 79, 56, 38, 40, 84 ，则利用堆排序的方法建立的初始堆为A . 79, 46, 56, 38, 40, 84B . 84, 79, 56, 38, 40, 46C . 84, 79, 56, 46, 40, 38D . 84, 56, 79, 40, 46, 38()16.下述几种排序方法中，平均査找长度(ASL )最小的是A . 插入排序B .快速排序C . 归并排序D . 选择排序17. 下述几种排序方法中，要求内存最大的是A . 插入排序B .快速排序C . 归并排序D . 选择排序18.目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态无关的是A . 插入排序B . 二分插入排序 C . 快速排序D . 冒泡排序三、简答题(每小题 4分，共36分1. 已知序列基本有序，问对此序列最快的排序方法是多少，此时平均复杂度是多少？2. 设有 1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好采用哪种排序方法？3. 用某种排序方法对线性表(25, 84，21,47,15,27,68,35,20)进行排序时，元素序列的变化情况如下25, 84, 21,47,15,27,68,35,20 f 20, 15, 21, 25, 47, 27,68,35, 84 f 15, 20, 21, 25, 35,27, 47, 68, 8415, 20, 21, 25， 27, 35, 47, 68, 84， 问采用的是什么排序方法？4. 对于整数序列 100, 99, 98,3, 2, 1,如果将它完全倒过来,分别用冒泡排序和快速排序法,它们 的比较次数和交换次数各是多少？5. 【严题集10.15】设有n个值不同的元素存于顺序结构中，试问能否用比2n-3少的比较次数选出这n个元素中的最大值和最小值？若能请说明如何实现（不需写算法）。在最坏情况下至少需进行多少次比较。6. 将两个长度为n的有序表归并为一个长度为2n的有序表，最小需要比较n 次,最多需要比较2n-1 次, 请说明这两种情况发生时,两个被归并的表有何特征?7. 【严题集10.11】试问：按锦标赛排序的思想，决出8名运动员之间的名次排列，至少需编排多少 场次的比赛（应考虑最坏的情况）？8. 【严题集10.19】假设某大旅店共有5000个床位，每天需要根据住宿旅客的文件制造一份花名册， 该名册要求按省（市）的次序排列,每一省（市）按县（区）排列,又同一县（区）的旅客按姓氏排 列。请你为旅店的管理人员设计一个制作这份花名册的方法。9. 【严题集10.6】奇偶交换排序如下所述：第一趟对所有奇数i,将ai和ai+l进行比较；第二趟 对所有的偶数i,将ai和ai+1进行比较，若aiai+l,则两者交换；第三趟对奇数i,第四趟对 偶数i；依次类推直至整个序列有序为止。（1）试问这种排序方法的结束条件是什么？是否为稳定排序？（2）分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关键字比较的次数。（3）分析此种排序方法的平均复杂度及最坏复杂度。四、以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写 出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这些排序方法中，哪些 易于在链表（包括各种单、双、循环链表）上实现？ 直接插入排序 希尔排序 冒泡排序 快速排序 直接选择排序 堆排序 归并排序 基数排序（8 分）五、算法设计题（4 选 2， 每题7分，共14 分）1.【严题集10.25】试编写教科书10.2.2节中所述链表插入排序的算法。2. 【严题集10.30】按下述原则编写快排的非递归算法：（1） 一趟排序之后，先对长度较短的子序列进行排序，且将另一子序列的上、下界入栈保存（2）若待排记录数W3,则不再进行分割，而是直接进行比较排序。3. 【严题集10.41】假设有1000个关键字为小于10000的整数的记录序列，请设计一种排序方法，要 求以尽可能少的比较次数和移动次数实现排序，并按你的设计编出算法。4. 【严题集10.42】序列的“中值记录”指的是：如果将此序列排序后，它是第n/2 个记录。试写一 个求中值记录的算法。