习题9答案

一.选择题1.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是____希尔排序冒泡排序插入排序选择排序2.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用_____排序法。冒泡排序快速排序堆排序基数排序3.在待排序的元素的序列基本有序的前提下，效率最高的排序方法是____插入排序选择排序快速排序归并排序4.下列排序方法中，_____可能会出现这样的情况：初始数据有序时，花费的时间反而最多。插入排序选择排序快速排序归并排序5.下列排序方法中，____可能会出现这样的情况：在最后一趟开始之前，所有元素都不在其最终位置上。堆排序冒泡排序快速排序插入排序6.依次将待排序序列中的元素和有序子序列合并为一个新的有序子序列的是_____插入排序冒泡排序快速排序堆排序7.快速排序在最好的情况下的时间复杂度是____O(n)O(nlog2n）O(n^2)O(log2n）8.下列排序法中，时间复杂度不收数据初始状态影响，总是为O(n2）的是____快速排序直接选择排序冒泡排序堆排序9.下列排序法中，_____每一趟都选出一个元素放在其最终位置上，并且是不稳定的。直接插入排序直接选择排序冒泡排序希尔排序10.下列排序方法中，时间复杂度为O(nlog2n）且占用额外空间最少的是_____堆排序冒泡排序快速排序希尔排序11.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为____79，46，56，38，40，8084，79，56，38，40，4684，79，56，46，40，3840，38，46，84，56，7912.一组记录的排序码为（25，48，16，35，79，82，23，40，36，72）其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为____16，25，35，48，23，40，79，82，36，7216，25，35，48，79，82，23，36，40，7216，25，48，35，79，82，23，36，40，7216，25，35，48，79，23，36，40，72，8213.用某中排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，35，27，47，68，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84则采用的排序方法是_____选择排序希尔排序归并排序快速排序14.有一组序列48，36，68，99，75，24，28，52进行快速排序，要求结果从小到大排序，则进行一次划分之后的结果为____（24，28，36）48（52，68，75，99）（28，36，24）48（75，99，68，52）（36，88，99）48（75，24，28，52）（28，36，24）48（99，75，68，52）15.已知两个有序表，若要将它们组合成一个新的有序表，最好的方法是____希尔排序二分插入排序归并排序冒泡排序16.下述几种排序方法中，平均查找长度最小的是_____插入排序选择排序快速排序归并排序17.下述几种排序方法中，要求内存量最大的是_____插入排序选择排序快速排序归并排序18.排序方法有稳定的和不稳定的之分。下列四个说法中，只有___B__是正确的。A.快速排序是稳定的排序方法B.堆排序是不稳定的排序方法C.希尔排序是稳定的排序方法D.冒泡排序是不稳定的排序方法二、填空题1．在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较3次。2．在利用快速排序方法对一组记录（54，38，96，23，15，72，60，45，83）进行快速排序时，递归调用而使用的栈的所能达到的最大深度为①7??，共需递归调用的次数为11??②，其中第二次递归调用是对23,15,38③???一组记录进行快速排序。3．在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取堆排序①方法，其次选取快速排序②方法，最后选取归并排序③方法；若只从排序结果的稳定性考虑，则应选取归并排序④方法，若只从平均情况下排序最快考虑，则应选取快速排序⑤方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取堆排序⑥方法。4．在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有希尔排序、快速排、堆排序序。5．在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的是基数排序①，需要内存容量最多的是归并排序②。6．在堆排序和快速排序中，若原始记录接近正序或反序，则选用堆排序①，若原始记录无序，则最好选用快速排序②。7．在插入和选择排序中，若初始数据基本正序，则选用插入排序①，若初始数据基本反序，则最好选用选择排序②。8．对n个元素的序列进行冒泡排序时，最少的比较次数是n-1。9．冒泡排序在最好的情况下的元素交换次数为0。10．已知一个待排序的序列已基本有序，则在直接选择排序、堆排序、快速排序和直接插入排序中，最省时间的是直接选择排序。11．在堆排序、希尔排序、快速排序和归并排序中占用辅助空间最多的是归并排序。