第10章排序一、选择题1．某内排序方法的稳定性是指( B )。

【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 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．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。

B 【北京邮电大学 2001 一、5（2分）】7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

（ C E ）就是不稳定的排序方法。

【清华大学 1998 一、3 (2分）】A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序8．下面的排序算法中，不稳定的是（C E F ）【北京工业大学 1999 一、2 (2分)】A.起泡排序B.折半插入排序C.简单选择排序D.希尔排序E.基数排序F.堆排序。

9．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( BD )。

A．直接插入 B. 二分法插入 C. 快速排序 D. 归并排序【南京理工大学 2000 一、7 （1.5分）】10．比较次数与排序的初始状态无关的排序方法是( D )。

【北方交通大学 2000 二、2（2分）】A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序11．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84则采用的排序是 ( A )。

【南京理工大学 1997 一、2 （2分）】A. 选择B. 冒泡C. 快速D. 插入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，7 D. 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分）】类似本题的另外叙述有：(1)在文件"局部有序"或文件长度较小的情况下，最佳内部排序的方法是（ A ）。

A. 直接插入排序B. 冒泡排序C. 简单选择排序D. 快速排序【山东大学 2001 二、 2 (1分)】(2)在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ A ）。

【武汉大学 2000 二、6】A.插入排序B. 选择排序C. 快速排序D. 归并排序20．下列排序算法中，（ D ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。

【南开大学 2000 一、4】【西北大学 2001 二、1】A. 堆排序B. 冒泡排序C. 快速排序D. 插入排序21．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。

【北京航空航天大学 1999 一、8（2分）】A. 插入B. 选择C. 希尔D. 二路归并22. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（A ）。

【中山大学 1999 一、11】A. 选择B. 冒泡C. 插入D. 堆23．直接插入排序在最好情况下的时间复杂度为（ B ）【北京邮电大学 1999 一、5 （2分）】A． O(logn) B． O(n) C． O(n*logn) D． O(n2)24．对关键码序列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分）】25. 快速排序方法在（ D ）情况下最不利于发挥其长处。

【燕山大学 2001 一、3 （2分）】A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据个数为奇数D. 要排序的数据已基本有序26. 以下序列不是堆的是( 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)27．下列四个序列中，哪一个是堆（ 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,15三、填空题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 (４分)】2. 对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。

（125，11，22，34，15，44，76，66，100，8，14，20，2，5，1）。

【合肥工业大学 1999 四、4 （5分）】125，11，设D=7D=31，11，2，5，15，8，14，34，20，22，66，100，44，76，125D=1 1，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该排序方法为快速排序。