第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】每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做 ① 排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此 …… 此处隐藏：2371字，全部文档内容请下载后查看。喜欢就下载吧 ……