(第5章排序测试卷.docVIP

理工大学指挥自动化学院试卷 考试科目： 第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趟排序结果为{14，5，19，20，11，19}，问采用的排序算法是 。 A．简单选择排序 B．快速排序 C．希尔排序 D．二路归并排序 【8】在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为 。 A．O(1) B．(log2n) C．O(n2) 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．要排序的数据个数为奇数 【12】快速排序在最坏情况下时间复杂度是O(n2)，比 的性能差。 A．堆排序