搜索
第10章排序一、选择题1．某内排序方法的稳定性是指(D)。【南京理工大学1997一、10（2分）】A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（nlogn）的排序方法D．以上都不对2．下面给出的四种排序法中(D)排序法是不稳定性排序法。【北京航空航天大学1999一、10（2分）】A.插入B.冒泡C.二路归并D.堆积3．下列排序算法中，其中（D）是稳定的。【福州大学1998一、3(2分)】A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序4．稳定的排序方法是（B）【北方交通大学2000二、3（2分）】A．直接插入排序和快速排序B．折半插入排序和起泡排序C．简单选择排序和四路归并排序D．树形选择排序和shell排序5．下列排序方法中，哪一个是稳定的排序方法？（B）【北方交通大学2001一、8（2分）】A．直接选择排序B．二分法插入排序C．希尔排序D．快速排序6.快速排序方法在（D）情况下最不利于发挥其长处。【燕山大学2001一、3（2分）】A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序7.以下序列不是堆的是(D)。【西安电子科技大学2001应用一、5（2分）】A.(100,85,98,77,80,60,82,40,20,10,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)8．下列四个序列中，哪一个是堆（C）。【北京工商大学2001一、8（3分）】A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,159．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为(A)排序法。【北京航空航天大学1999一、8（2分）】A.插入B.选择C.希尔D.二路归并10．比较次数与排序的初始状态无关的排序方法是(D)。【北方交通大学2000二、2（2分）】A．直接插入排序B．起泡排序C．快速排序D．简单选择排序11．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（B）。A.(2,5,12,16)26(60,32,72)B.(5,16,2,12)28(60,32,72)C.(2,16,12,5)28(60,32,72)D.(5,16,2,12)28(32,60,72)【青岛大学2000三、4（2分）】12．下列排序算法中(B)不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序B.shell排序C.堆排序D.冒泡排序【合肥工业大学2001一、3（2分）】13．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为(A)（按递增序）。【南京理工大学1996一、4（2分）】A．下面的B，C，D都不对。B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7D.9，4，7，8，7，-1，15，2014．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C）。【燕山大学2001一、4（2分）】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)15．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是(C)排序。A．冒泡B.希尔C.快速D.堆【南京理工大学2001一、12（1.5分）】16.对初始状态为递增序列的表按递增顺序排序，最省时间的是（C）算法，最费时间的是（B）算法。A.堆排序B.快速排序C.插入排序D.归并排序【南开大学2000一、5】17.就平均性能而言，目前最好的内排序方法是(D)排序法。【西安电子科技大学1998一、9(2分）】A.冒泡B.希尔插入C.交换D.快速18．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（D）方法最快。A．起泡排序B．快速排列C．Shell排序D．堆排序E．简单选择排序【清华大学1998一、2（2分）】19．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（A）A．直接插入排序B．冒泡排序C．简单选择排序【山东工业大学1995二、1（2分）】20．下列排序算法中，（D）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。【南开大学2000一、4】【西北大学2001二、1】A.堆排序B.冒泡排序C.快速排序D.插入排序三、填空题1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较_和记录的_移动__。【北京邮电大学2001二、7（4分）】2．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_冒泡_算法，最费时间的是_快速_算法。【福州大学1998二、10(2分)】3.不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是简单选择_，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是(2)直接插入排序（最小的元素在最后时）_。【中国人民大学2001一、3（2分）】4．直接插入排序用监视哨的作用是免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。【南京理工大学2001二、8（2分）】5设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需__3___趟，写出第一趟结束后，数组中数据的排列次序(10,7,-9,0,47,23,1,8,98,36)。【南京理工大学1997三、5（2分）】6．堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆___4_____。①16，72，31，23，94，53②94，53，31，72，16，23③16，53，23，94，31，72④16，31，23，94，53，72⑤94，31，53，23，16，727．堆是一种有用的数据结构.堆排序是一种_(1)选择_排序，堆实质上是一棵_(2)完全二叉树_结点的层次序列。【山东工业大学1996三、1（5分）】8．关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_（Q,A,C,S,Q,D,F,X,R,H,M,Y）_；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_(F,H,C,D,Q,A,M,Q,R,S,Y,X)_。【北京大学1997一、4（4分）】四、应用题1.在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。【大连海事大学1996七、3(４分)】排序方法平均时间最坏情况辅助空间稳定性不稳定排序举例直接插入排序O（n2）O（n2）O（1）稳定折半插入排序O（n2）O（n2）O（1）稳定二路插入排序O（n2）O（n2）O（n）稳定起泡排序O（n2）O（n2）O（1）稳定直接选择排序O（n2）O（n2）O（1）不稳定2,2’,1希尔排序O（n1.3）O（n1.3）O（1）不稳定3,2,2’,1(d=2,d=1)快速排序O（nlog2n）O（n2）O（log2n）不稳定2,2’,1堆排序O（nlog2n）O（nlog2n）O（1）不稳定2,1,1’(极大堆)2-路归并排序O（nlog2n）O（nlog2n）O（n）稳定基数排序O(d*(rd+n))O(d*(rd+n))O(rd)稳定2.对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。（125，11，22，34，15，44，76，66，100，8，14，20，2，5，1）。【合肥工业大学1999四、4（5分）】125，11，22，34，15，44，76，66，100，8，14，20，2，5，1设D=71，11，8，14，15，2，5，66，100，22，34，20，44，76，125D=31，11，2，5，15，8，14，34，20，22，66，100，44，76，125D=11，2，5，8，11，14，15，20，22，34，44，66，76，100，1253．有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下,则该排序方法是什么?【武汉交通科技大学1996二、5(6分)】初始:25,84,21,46,13,27,68,35,20第一趟:20,13,21,25,46,27,68,35,84第二趟:13,20,21,25,35,27,46,68,84第三趟:13,20,21,25,27,35,46,68,84该排序方法为快速排序。4．判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。（1）100，85，98，77，80，60，82，40，20，10，66（2）100，98，85，82，80，77，66，60，40，20，10（3）100，85，40，77，80，60，66，98，82，10，20（4）10，20，40，60，66，77，80，82，85，98，100【山东大学1998四(5分)】【山东工业大学2000四（5分）】答案:(1)是大堆；(2)是大堆；（4）是小堆；(3)不是堆，调成大堆100，98，66，85，80，60，40，77，82，10，205．给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列；(1)希尔排序（第一趟排序的增量为5）(2)快速排序（选第一个记录为枢轴（分隔））【上海交通大学1999八（9分）】(1)一趟希尔排序:12,2,10,20,6,18,4,16,30,8,28（D=5）(2)一趟快速排序：6,2,10,4,8,12,28,30,20,16,186.给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：【南开大学1998八(12分)】(1)归并排序每归并一次书写一个次序。(2)快速排序每划分一次书写一个次序。(3)堆排序先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。(1)2路归并第一趟:18,29,25,47,12,58,10,51；第二趟:18,25,29,47,10,12,51,58；第三趟:10,12,18,25,29,47,51,58(2)快速排序第一趟:10,18,25,12,29,58,51,47；第二趟:10,18,25,12,29,47,51,88；第三趟:10,12,18,25,29,47,51,88(3)堆排序建大堆:58,47,51,29,18,12,25,10；①51,47,25,29,18,12,10,58；②47,29,25,10,18,12,51,58；③29,18,25,10,12,47,51,58；④25,18,12,10,29,47,51,58；⑤18,10,12,25,29,47,51,58；⑥12,10,18,25,29,47,51,58；⑦10,12,18,25,29,47,51,58