发布时间 : 星期五 文章数据结构 第9章自测题更新完毕开始阅读f07877649b6648d7c1c746ad
第九章 排序 自测卷 姓名 班级
题号 题分 得分 一 24 二 18 三 36
四 8 五 14 总分 100 一、填空题（每空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个不同的数据进行排序，至多需要比较 次。
Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25
（ ）2． 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，
将其放入已排序序列的正确位置上的方法，称为 Ａ. 希尔排序 Ｂ. 冒泡排序 Ｃ. 插入排序 Ｄ. 选择排序
（ ）3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为
Ａ. 希尔排序 Ｂ. 归并排序 Ｃ. 插入排序 Ｄ. 选择排序
1
（ ）4．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。
Ａ. 从小到大排列好的 Ｂ. 从大到小排列好的 Ｃ. 元素无序 Ｄ. 元素基本有序 （ ）5．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为
Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n(n-1)/2 （ ）6．快速排序在下列哪种情况下最易发挥其长处。
Ａ. 被排序的数据中含有多个相同排序码 Ｂ. 被排序的数据已基本有序
Ｃ. 被排序的数据完全无序 Ｄ. 被排序的数据中的最大值和最小值相差悬殊
（ ）7． 对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是
A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)
（ ）8．若一组记录的排序码为（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
（ ）9． 在最好情况下，下列排序算法中 排序算法所需比较关键字次数最少。
A．冒泡 B．归并 C．快速 D．直接插入
（ ）10． 置换选择排序的功能是 。
A．选出最大的元素 B．产生初始归并段 C．产生有序文件 D．置换某个记录 （ ）11．将5个不同的数据进行排序，至少需要比较 次。
Ａ. 4 Ｂ. 5 Ｃ. 6 Ｄ. 7
（ ）12．下列关键字序列中， 是堆。
Ａ. 16, 72, 31, 23, 94, 53 Ｂ. 94, 23, 31, 72, 16, 53 Ｃ. 16, 53, 23, 94，31, 72 Ｄ. 16, 23, 53, 31, 94, 72 （ ）13．堆是一种 排序。
Ａ. 插入 Ｂ.选择 Ｃ. 交换 Ｄ. 归并
（ ）14．堆的形状是一棵
Ａ. 二叉排序树 Ｂ.满二叉树 Ｃ. 完全二叉树 Ｄ. 平衡二叉树 （ ）15．若一组记录的排序码为（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
（ ）16． 下述几种排序方法中，平均查找长度（ASL）最小的是
Ａ. 插入排序 Ｂ.快速排序 Ｃ. 归并排序 Ｄ. 选择排序 （ ）17． 下述几种排序方法中，要求内存最大的是
Ａ. 插入排序 Ｂ.快速排序 Ｃ. 归并排序 Ｄ. 选择排序
（ ）18．目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态无关的是
Ａ. 插入排序 Ｂ. 二分插入排序 Ｃ. 快速排序 Ｄ. 冒泡排序
三、简答题（每小题4分，共36分）
2
1. 已知序列基本有序，问对此序列最快的排序方法是多少，此时平均复杂度是多少？
2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好采用哪种排序方法？
3. 用某种排序方法对线性表（25, 84，21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下： 25, 84，21,47,15,27,68,35,20 → 20, 15, 21, 25，47, 27,68,35, 84 → 15, 20, 21, 25，35, 27, 47, 68, 84→ 15, 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个床位，每天需要根据住宿旅客的文件制造一份花名册，
该名册要求按省（市）的次序排列，每一省（市）按县（区）排列，又同一县（区）的旅客按姓氏排列。请你为旅店的管理人员设计一个制作这份花名册的方法。
3
9.【严题集10.6④】奇偶交换排序如下所述：第一趟对所有奇数i，将a[i]和a[i+1]进行比较；第二趟对所有的偶数i,将a[i]和a[i+1]进行比较，若a[i]>a[i+1]，则两者交换；第三趟对奇数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） 若待排记录数≤3,则不再进行分割，而是直接进行比较排序。
3. 【严题集10.41④】假设有1000个关键字为小于10000的整数的记录序列，请设计一种排序方法，要
求以尽可能少的比较次数和移动次数实现排序，并按你的设计编出算法。
4. 【严题集10.42④】序列的“中值记录”指的是：如果将此序列排序后，它是第[n/2]个记录。试写一
个求中值记录的算法。
4