《数据结构》-数据结构试卷第十章

数据结构期末复习题及参考答案第10章排序一、选择题1、N个记录进行直接插入排序时，记录最小的比较次数是AN1B0CN3N2/2DN2/22、对N个记录进行希尔排序，所需要的辅助存储空间为（）。AO（1OG2N）BO（N）CO（1）DO（N2）3、就平均性能而言，目前最好的内排序方法是排序法。A冒泡B希尔插入C交换D快速4、直接插入排序在最好情况下的时间复杂度为（）AOLOGNBONCONLOGNDON25、以下算法思路分别出自什么排序算法取当前最小的数，插入到已经排好序的数据末尾（）；取当前要排序的数，插入到已经排好序的数据中适当位置（）；相邻两个数比较，如果大小顺序颠倒就把两者交换过来（）。A插入排序、选择排序、起泡排序B选择排序、插入排序、起泡排序C插入排序、选择排序、快速排序D选择排序、插入排序、快速排序6、设一组初始关键字记录关键字为20，15，14，18，21，36，40，10，则以20为基准记录的一趟快速排序结束后的结果为。A10，15，14，18，20，36，40，21B10，15，14，18，20，40，36，21C10，15，14，20，18，40，36，2LD15，10，14，18，20，36，40，217、下列四种排序算法中，哪一个需要采用递归调用的方式实现A、直接插入排序B、快速排序C、冒泡排序D、折半插入排序8、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为排序法。A插入B选择C希尔D快速9、快速排序方法在（）情况下最不利于发挥其长处。A要排序的数据量太大B要排序的数据中含有多个相同值C要排序的数据个数为奇数D要排序的数据已基本有序10、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是。A选择B冒泡C快速D插入11、在希尔排序算法中，需要借助（）实现A、直接插入排序B、快速排序C、冒泡排序D、折半插入排序12、若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进行（）次比较。A3B10C15D2513、在下列排序算法中，哪一个算法的时间复杂度与初始排序无关（）。A直接插入排序B起泡排序C快速排序D选择排序14、对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是。A直接插入B起泡排序C快速排序D二分法插入15、若采用希尔排序法对序列12,36,21,7,2,19,6,31,49,13,27,38,5进行排序，增量分别为5、3、1。那么当增量为3时，排序结束后的序列是哪一个A5,2,19,6,27,21,7,31,38,12,36,49,13B12,6,5,7,2,19,36,21,49,13,27,38,31C7,2,5,12,6,19,13,21,38,31,27,49,36D2,6,5,7,12,13,27,21,31,19,36,38,49二、填空题1、直接插入排序、折半插入排序、起泡排序都属于稳定排序。希尔排序、快速排序、选择排序都属于不稳定排序。2、直接插入排序用监视哨的作用是免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。3、对有限个记录进行起泡排序，第N趟起泡排序的排序结束位置应为上一趟排序中最后一次发生记录交换的位置。4、对N个记录的表R1N进行简单选择排序，所需进行的关键字间的比较次数为NN1/2,若进行起泡排序，则最多需要NN1/2次的比较。5、假设存放在计算机内存中的含N个记录的序列为R1,R2,，RN，其相应的关键字序列为K1,K2,，KN，这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系KS1KS2KSN，按此固有关系将N个记录序列重新排列为RS1,RS2,，RSN。若整个排序过程都在内存中完成，不需要访问外存，则称此类排序问题为内部排序。6、对于排序算法，其基本思想是不断扩大有序序列区，同时不断缩小无序序列区。7、判定起泡排序的结束条件是当至多进行N1趟起泡排序，或一趟起泡排序中未发生交换（即已有序）时，结束排序。三、简答题1、1请简单叙述希尔排序的基本思想。2写出初始数列49，38，65，97，76，13，27，49，55，4在希尔排序下的状态变化过程（假设增量D5、3、1）。1希尔排序是对直接插入排序算法的改进，它从“记录个数少”和“基本有序”出发，将待排序的记录划分成几组（缩小增量分组），从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。22、1请简述直接插入排序和选择排序的基本思想以及在时间复杂度和排序稳定性上的差别。2设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。分别写出用直接插入排序和选择排序下序列的状态变化过程。要求以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。1直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。即将记录RI21LASTEXCHANGEINDEX1FORJ1JRJ1KEYTMPRJRJRJ1RJ1TEMPLASTEXCHANGEINDEXJ/记下进行交换的记录位置ILASTEXCHANGEINDEX/本趟进行过交换的最后一个记录的位置3、阅读下面的一趟快速排序算法的代码，并完成填空。INTPARTITIONREDTYPER,INTLOW,INTHIGHR0RLOWPIVOTKEYRLO