第5章排序测试卷

中国人民

解放军理工大学指挥自动化学院试卷

考试科目： 第5章 排序 队别专业： 学 号： 姓 名： 考试日期： 年 月 日

题 号 得 分 阅 卷 人 1 2 3 总 分 1.单项选择题（每题1分，共24分）

【1】对任意的7个关键字进行排序，至少要进行 次关键字之间的两两比较。 A．13 B．14 C．15 D．16

【2】排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 。

A．希尔排序 B．冒泡排序 C．插入排序 D．选择排序

【3】在文件“局部有序”或文件长度较小的情况下，最佳内排序方法是 。 A．直接插入排序 B．冒泡排序 C．直接选择排序 D．归并排序

【4】在待排序的元素序列基本有序的前提下，效率最高的排序方法是 。 A．插入排序 B．选择排序 C．快速排序 D．归并排序

【5】在下列算法中， 算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。

A．堆排序 B．冒泡排序 C．插入排序 D．快速排序

【6】对记录的关键字为{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：

50 26 38 80 70 90 8 30 40 20

50 8 30 40 20 90 26 38 80 70 ． 26 8 30 40 20 80 50 38 90 70 8 20 26 30 38 40 50 70 80 90 其使用的排序方法是 。

A．快速排序 B．基数排序 C．希尔排序 D．归并排序

【7】对给出的一组关键字{14，5，19，20，11，19}。若按关键字非递减排序，第1趟排序

1

结果为{14，5，19，20，11，19}，问采用的排序算法是 。

A．简单选择排序 B．快速排序 C．希尔排序 D．二路归并排序

【8】在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为 。

2

A．O(1) B．(log2n) C．O(n) D．O(n)

【9】一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为划分元素得到的一次划分结果为 。

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

【10】用某种排序方法对线性表{25，84，21，47，15，27，68，35，20}进行排序时，元素序列的变化情况如下：

(1)25，84，21，47，l5，27，68，35，20 (2)20，15，21，25，47，27，68，35，84 (3)15，20，21，25，35，27，47，68，84 (4)15，20，21，25，27，35，47，68，84 则采用的排序方法是 。

A．直接选择排序 B．希尔排序 C．归并排序 D．快速排序

【11】快速排序方法在 情况下最不利于发挥其长处。

A．要排序的数据量太大 B．要排序的数据中含有多个相同值 C．要排序的数据已基本有序 D．要排序的数据个数为奇数

2

【12】快速排序在最坏情况下时间复杂度是O(n)，比 的性能差。

A．堆排序 B．冒泡排序 C．直接选择排序 D．直接插入排序

【13】采用直接选择排序，比较的次数与移动次数分别是 。

2

A．O(n)，O(log2n) B．O(log2n)，O(n)

2

C．O(n)，O(n) D．O(nlog2n)，O(n)

【14】如果对n个元素进行直接选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂度为 。

2

A．O(1) B．O(log2n) C．O(n) D．O(n)

【15】在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 。 A．希尔排序 B．冒泡排序 C．直接插入排序 D．直接选择排序

【16】排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端的方法，称为 。

A．希尔排序 B．归并排序 C．直接插入排序 D．直接选择排序

【17】在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 。 A．O(log2n) B．O(1) C．O(n) D．O(nlog2n)

2

【18】一组记录的排序码为{46，79，56，38，40，84}，则利用堆排序(建立大根堆)的方法建立的初始堆为 。

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

【19】设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用 排序法。

A．冒泡排序 B．快速排序 C．堆排序 D．基数排序

【20】以下序列不是堆的是 。

A．{100，85，98，77，80，60，82，40，20，l0，66} B．{100，98，85，82，80，77，66，60，40，20，10) C．{10，20，40，60，66，77，80，82，85，98，100} D．{100，85，40，77，80，60，66，98，82，10，20)

【21】一组记录的排序码为{25，48，16，35，79，82，23，40，36，72}，其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为 。 A．16 25 35 48 23 40 79 82 36 72 B．16 25 35 48 79 82 23 36 40 72 C．16 25 48 35 79 82 23 36 40 72 D．16 25 35 48 79 23 36 40 72 82

【22】将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 。 A．n B．2n-1 C．2n D．n-1

【23】就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 。 A．堆排序<快速排序<归并排序 B．堆排序<归并排序<快速排序 C．堆排序>归并排序>快速排序 D．堆排序>快速排序>归并排序

【24】下述几种排序方法中，要求内存量最大的是 。

A．直接插入排序 B．选择排序 C．快速排序 D．归并排序

2.填空题（每题1分，共24分）

【1】在对一组记录{54，38，96，23，15，72，60，45，83}进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 次。

【2】每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做 ① 排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 ② 排序。

① ② 【3】每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交 换它们的位置，此种排序方法叫做 ① 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 ② 排序。

3

① ②

【4】 ① 排序方法采用的是二分法的思想， ② 排序方法其数据的组织采用完全二叉树结构。

① ② 【5】对n个记录的表r[1．．n]进行直接选择排序，所需进行的关键字间的比较次数为 。

【6】在堆排序和快速排序中，若原始记录接近正序或反序，则选用 ① ，若原始记录无序，则最好选用 ② 。

① ②

【7】在插入和选择排序中，若初始数据基本正序，则选用 ① ；若初始数据基本反序，则选用 ② 。

① ②

【8】设有关键码序列{Q，H，C，Y，Q,A，M，S，R，D，F，X}，要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是 ① ：若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是 ② 。 ① ②

【9】对n个元素的序列进行冒泡排序时，最少的比较次数是 。

【10】在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取 ① 方法，其次选取 ② 方法，最后选取 ③ 方法；若只从排序结果的稳定性考虑，则应选取 ④ 方法；若只从平均情况下排序最快考虑，则应选取 ⑤ 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 ⑥ 方法。

① ② ③ ④ ⑤ ⑥

【11】在直接插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有 。

【12】在直接插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是 ① ，需要内存容量最多的是 ② 。 ① ②

【13】 排序不需要进行记录关键字问的比较。

3.简答题（每题3分，共42分）

【1】已知序列{17，18，60，40，7，32，73，65，85}，请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。

4

【2】已知序列{503，87，512，61，908，170，897，275，653，462}，请给出采用快速排序法对该序列作升序排序时的每一趟的结果。

5

【3】已知序列{503，87，512，61，908，170，897，275，653，462}，请给出采用堆序法对该序列作降序排序时的每一趟的结果。

6

【4】已知序列{503，87，512，61，908，170，897，275，653，462}，请给出采用基数排序法对该序列作升序排序时的每一趟的结果。

【5】已知序列{503，17，512，908，170，897，275，653，426，154，509，612，677，765，703，94}，请给出采用希尔排序法(d1=8)对该序列作升序排序时的每一趟的结果。

7

【6】已知序列{70，83，100，65，10，32，7，9}，请给出采用直接插入排序法对该序列作升序排序时的每一趟的结果。

【7】已知序列{10，18，4，3，6，12，1，9，18，8}，请给出采用2路归并排序法对该序列作升序排序时的每一趟的结果。

【8】在冒泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动。试举例说明之。快速排序过程中有没有这种现象?

8

【9】假设我们把n个元素的序列{a1，a2，?，an}中满足条件ak?max?at?的元素ak称为

1?t?k逆序元素。若在一个无序序列中有一对元素ai>aj(i

【10】请回答下列关于堆的一些问题：

（1）堆的存储表示是顺序的，还是链式的? （2）设有一个最小堆(小根堆)，即堆中任意结点的关键字均小于它的左孩子和右孩子的关键字。其具有最大关键字的元素可能在什么地方?

【11】 有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序方法时间复杂度最佳?为什么?

9

【12】针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数)： (1)输入的n个数据全部有序； (2)输入的n个数据全部逆向有序； (3)随机地输入n个数据。

【13】如果只想得到一个序列中第k个最小元素之前的部分排序序列，最好采用什么排序方法?为什么?如由这样的一个序列：{57，40，38，11，13，34，48，75，25，6，19，9，7}得到其第4个最小元素之前的部分序列{6，7，9，11}，使用所选择的算法实现时，要执行多少次比较?

【14】已知下列各种初始状态(长度为n)的元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)? (1)关键字自小至大有序(key1key2>?>keyn)

(3)奇数关键字顺序有序，偶数关键字顺序有序(key1

(4)前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key1

10

4.算法设计题（每题5分，共10分）

【1】设计一个算法，修改冒泡排序过程以实现双向冒泡排序。

11

【2】编写一个算法，采用非递归方式实现快速排序。

12

本文来源：https://www.bwwdw.com/article/j1wx.html