《【2017年整理】第5章排序测试卷》由会员分享，可在线阅读，更多相关《【2017年整理】第5章排序测试卷（12页珍藏版）》请在金锄头文库上搜索。
1、1理工大学指挥自动化学院试卷中国人民 解放军考 试 科 目 ： 第 5 章 排 序 队 别 专 业 ： 学 号 ： 姓 名 ： 考 试 日 期 ： 年 月 日题 号 1 2 3 总 分得 分阅 卷 人1.单项选择题（每题 1 分，共 24 分）【1】对任意的 7 个关键字进行排序，至少要进行 次关键字之间的两两比较。A13 B14 C15 D16【2】排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 。A希尔排序 B冒泡排序 C插入排序 D选择排序【3】在文件“局部有序”或文件长度较小的情况下，最佳内排序方法是 。A直
2、接插入排序 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 2050 8 30 40 20 90 26 38 80 70 26 8 30 40 20 80 50 38 90 708 20 26
3、30 38 40 50 70 80 90其使用的排序方法是 。A快速排序 B基数排序 C希尔排序 D归并排序【7】对给出的一组关键字14，5，19，20，11，19。若按关键字非递减排序，第 1 趟排2序结果为14，5，19，20，11，19，问采用的排序算法是 。A简单选择排序 B快速排序 C希尔排序 D二路归并排序【8】在对 n 个元素进行冒泡排序的过程中，最好情况下的时间复杂度为 。AO(1) B(log 2n) CO(n 2) DO(n)【9】一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为划分元素得到的一次划分结果为 。A38，40，46
4、，56，79，84 B40，38，46，79，56，84C40，38，46，56，79，84 D40，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】快速排序方法在 情况下最不利于发挥其长处
5、。A要排序的数据量太大 B要排序的数据中含有多个相同值C要排序的数据已基本有序 D要排序的数据个数为奇数【12】快速排序在最坏情况下时间复杂度是 O(n2)，比 的性能差。A堆排序 B冒泡排序 C直接选择排序 D直接插入排序【13】采用直接选择排序，比较的次数与移动次数分别是 。AO(n)，O(log 2n) BO(log 2n)，O(n 2)CO(n 2)，O(n) DO(nlog 2n)，O(n)【14】如果对 n 个元素进行直接选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂度为 。AO(1) BO(log 2n) CO(n 2) DO(n)【15】在所有排序方法中，
6、关键字比较的次数与记录的初始排列次序无关的是 。A希尔排序 B冒泡排序 C直接插入排序 D直接选择排序【16】排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端的方法，称为 。A希尔排序 B归并排序 C直接插入排序 D直接选择排序【17】在对 n 个元素的序列进行排序时，堆排序所需要的附加存储空间是 。AO(log 2n) BO(1) CO(n) DO(nlog 2n)3【18】一组记录的排序码为46，79，56，38，40，84，则利用堆排序(建立大根堆)的方法建立的初始堆为 。A79，46，56，38，40，80 B84，79，56，38，40，46C84，7
7、9，56，46，40，38 D84，56，79，40，46，38【19】设有 1000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，最好选用 排序法。A冒泡排序 B快速排序 C堆排序 D基数排序【20】以下序列不是堆的是 。A100，85，98，77，80，60，82，40，20，l0，66 B100，98，85，82，80，77，66，60，40，20，10)C10，20，40，60，66，77，80，82，85，98，100D100，85，40，77，80，60，66，98，82，10，20)【21】一组记录的排序码为25，48，16，35，79，82，23，40，36
8、，72，其中含有 5 个长度为 2 的有序表，按归并排序的方法对该序列进行一趟归并后的结果为 。A16 25 35 48 23 40 79 82 36 72 B16 25 35 48 79 82 23 36 40 72C16 25 48 35 79 82 23 36 40 72 D16 25 35 48 79 23 36 40 72 82【22】将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是 。An B2n-1 C2n Dn-1【23】就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 。A堆排序归并排序快速排序 D堆排序快速排序归并排序【24】下述几种排序方
9、法中，要求内存量最大的是 。A直接插入排序 B选择排序 C快速排序 D归并排序2.填空题（每题 1 分，共 24 分）【1】在对一组记录54，38，96，23，15，72，60，45，83进行直接插入排序时，当把第 7 个记录 60 插入到有序表时，为寻找插入位置需比较 次。【2】每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做 排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 排序。 【3】每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交 换它们的位置，此种排序方法叫做 排序；每次使两个相邻的有序表合并成一个有
10、序表的排序方法叫4做 排序。 【4】 排序方法采用的是二分法的思想， 排序方法其数据的组织采用完全二叉树结构。 【5】对 n 个记录的表 r1 n进行直接选择排序，所需进行的关键字间的比较次数为 。【6】在堆排序和快速排序中，若原始记录接近正序或反序，则选用 ，若原始记录无序，则最好选用 。 【7】在插入和选择排序中，若初始数据基本正序，则选用 ；若初始数据基本反序，则选用 。 【8】设有关键码序列Q，H，C，Y，Q,A，M，S，R，D，F，X，要按照关键码值递增的次序进行排序，若采用初始步长为 4 的希尔排序法，则一趟扫描的结果是 ：若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果
11、是 。 【9】对 n 个元素的序列进行冒泡排序时，最少的比较次数是 。【10】在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取 方法，其次选取 方法，最后选取 方法；若只从排序结果的稳定性考虑，则应选取 方法；若只从平均情况下排序最快考虑，则应选取 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 方法。 【11】在直接插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有 。【12】在直接插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是 ，需要内存容量最多的是 。 【13】 排序不需要进行记录关键字问的比较。3.简答题（每题 3 分，共 42 分）5【1】已知序列17，18，60，40，7，32，73，65，85，请给出
