《数据结构》课程教学资源（试卷习题）第10章 排序自测卷空题（无答案）

第10章 排序 姓名 学号： 班级 题号一 二三四 五 总分 题分24 18 36 14 100 得分 一、填空题（每空1分，共24分） 1.大多数排序算法都有两个基本的操作： 和 2.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时，当把第7个记录60插 入到有序表时，为寻找插入位置至少需比较 次。 3.在插入和选择排序中，若初始数据基本正序，则选用 ；若初始数据基本反序，则选 用 4.在堆排序和快速排序中，若初始记录接近正序或反序，则选用 若初始记录基本无序 则最好选用 5.对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 。若对其讲行快速排序， 在最坏的情况下所需要的时间是 6.对于个记录的集合进行归并排序，所需要的平均时间是 ,所需要的附加空间是 7.对于个记录的表进行2路归并排序，整个归并排序需进行越（），共计移动 次记录。 8.设要将序列(Q,H,C,Y,P,A,M,S,R,D,E,X)中的关楚码按字母序的升序重新排列，则： 目泡接来一销扫描的结果是 初始步长为4的希尔(h)排序一超的结果是 路归并排 一趙扫描的结果是 快速排序一翅扫描的结果是 堆排序初始建堆的结果是 9.在堆排序、快速排序和归并排序中， 若只从存储空间考虑，则应首先选取 方法，其次选取 方法，最后选取 方法： 若只从排序结果的稳定性考虑，则应选取】 方法： 若只从平均情况下最快考虑，则应选取 方法： 若只从最坏情况下最快并且要节省内存考感，则应选取 方法。 二、单项选择题（每小题1分，共18分） （)1.将5个不同的数据进行排序，至多需要比较次。 A.8 B.9 c.10 D.25 （)2.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较， 将其放入已排序序列的正确位置上的方法，称 A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序

1 第 10 章 排序 姓名： 学号： 班级： 题号 一 二 三 四 五 总分 题分 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.从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一增的方法，称为 A.希尔排序 B.归并排序 C.插入排序 D.选择排序 )4.对个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。 A.从小到大排列好的B.从大到小排列好的C.元素无序D.元素基本有序 ( )5.对个不同的排序码进行目泡排序，在元素无序的情况下比较的次数为 A.n+1 B.n C.n-1 D.n(n-1)2 )6.快速排序在下列哪种情况下最易发挥其长处。 A. 被排序的数据中含有多个相同排序码B.被排序的数据已基本有序 C.被排序的数据完全无序 D.被排序的数据中的最大值和最小值相差悬殊 （)7.对有个记录的表作快速排序，在最坏情况下，算法的时间复杂度是 A.0(m)B.0(2) C.O(nlogzn)D.O(n') （)8.若一组记录的排序码为(4679,56,38,40,84)，则利用快速排序的方法，以第一个记录为基 准得到的一次划分结果为 A.38,40,46,56,7984 B.40,38,46,79,56,84 C.40,38,46,56,79,84 D.40,38.46,8456.79 （)9.在最好情况下，下列排序算法中 排序算法所需比较关健字次数最少。 A.冒泡 B.归并 C.快速 D.直接插入 ()10。置换选择排序的功能是 A.选出最大的元素B.产生初始归并段C.产生有序文件 D.置换某个记录 （)山.将5个不同的数据进行排序，至少需要比较次。 A.4 B.5 C.6 D.7 （)12.下列关键字序列中， 是堆。 A.16,72,31,23.94,53 B.94,23,31,72,16,53 C.16,53,23,94,31,72 D.16.23.53.31.94.72 （)13.堆是一种 排序。 A.插入 B选择 C.交换 D.归并 （)14.堆的形状是一棵 A,二叉排序树 B满二叉树 C.完全二叉树D.平衡二叉树 （)15.若一组记录的排序码为(46,79,56,38,40,84)，则利用堆排序的方法建立的初始堆为 A.79,46.56,3840,8 B.84,79,56,38,40,4 C.84,79,56,46,40,38 D.84,56,79,40,46,38 ()16.下述几种排序方法中，平均查找长度(ASL)最小的是 A.插入排序 B.快速排序 C.归并排序 D.选彝排序 （)17.下述几种排胖方法中，要求内存最大的是 A.插入排序 B.快速排序 C.归并排序 D.选择排序 （)18。目前以比较为基础的内部排序方法中，其比较次数与特排胖的记录的初始排列状态无关的是 A.插入排序B.二分插入排序 C.快速排序 D.冒泡排序

2 （ ）3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为 Ａ. 希尔排序 Ｂ. 归并排序 Ｃ. 插入排序 Ｄ. 选择排序 （ ）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分） 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个值不同的元素存于顺序结构中，试问能否用比23少的比较次数洗出这m 个元素中的最大值和最小值？若能请说明如何实现（不需写算法）。在最坏情况下至少需进行多少次比较。 6.将两个长度为n的有序表归并为一个长度为2n的有序表，最小需要比较n次，最多需要比较2m-1次， 请说明这两种情况发生时，两个被归并的表有何特征？ 7.【严题集10.11②】试问：按钠标赛排序的思想，决出8名运动员之间的名次排列，至少需编排多少 场次的比赛（应考虑最坏的情况）？ 8【严题集10.19④】假设某大旅店共有5000个床位，每天需要根据住宿旅客的文件制造一份花名： 该名册要求按省（市）的次序排列，每一 省（市）按县（区）排列，又同一县（区）的旅客按姓氏排 列。请你为旅店的管理人员设计一个制作这份花名册的方法。 2

3 三、简答题（每小题 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 → 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 个床位，每天需要根据住宿旅客的文件制造一份花名册， 该名册要求按省（市）的次序排列，每一省（市）按县（区）排列，又同一县（区）的旅客按姓氏排 列。请你为旅店的管理人员设计一个制作这份花名册的方法

9.【严题集10.6④】奇偶交换排序如下所述：第一越对所有奇数，将a[]和a[i+刀进行比较；第二越 对所有的偶数，将a[]和a[i1]进行比较，若a[]>a[+1],则两者交换：第三趙对奇数三，第四植对 偶数 .依次类推直至整个序列有序为止 (1)试问这种排序方法的结束条件是什么？是否为稳定排F? (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④】序列的“中值记录”指的是：如果将此序列排序后，它是第[/2]个记录。试写- 个求中值记录的算法。 4

4 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]个记录。试写一 个求中值记录的算法