数据结构第10章例题与答案
第10章 排序
一、选择题
1．某内排序方法的稳定性是指( )。 【南京理工大学 1997 一、10（2分）】
a．该排序算法不允许有相同的关键字记录 b．该排序算法允许有相同的关键字记录
c．平均时间为0（n log n）的排序方法 d．以上都不对
2．下面给出的四种排序法中( )排序法是不稳定性排序法。【北京航空航天大学 1999 一、10 （2分）】
a. 插入 b. 冒泡 c. 二路归并 d. 堆积
3．下列排序算法中，其中（ ）是稳定的。 【福州大学 1998 一、3 (2分)】
a. 堆排序，冒泡排序 b. 快速排序，堆排序
c. 直接选择排序，归并排序 d. 归并排序，冒泡排序
4．稳定的排序方法是（ ） 【北方交通大学 2000 二、3（2分）】
a．直接插入排序和快速排序 b．折半插入排序和起泡排序
c．简单选择排序和四路归并排序 d．树形选择排序和shell排序
5．下列排序方法中，哪一个是稳定的排序方法？（ ） 【北方交通大学 2001 一、8（2分）】
a．直接选择排序 b．二分法插入排序 c．希尔排序 d．快速排序
6．若要求尽可能快地对序列进行稳定的排序，则应选（a．快速排序 b．归并排序 c．冒泡排序）。
【北京邮电大学 2001 一、5（2分）】
7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ ）就是不稳定的排序方法。【清华大学 1998 一、3 (2分）】
a．起泡排序 b．归并排序 c．shell排序 d．直接插入排序 e．简单选择排序
8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
a．直接插入 b．直接选择 c．堆 d．快速 e．基数 【中科院计算所 2000 一、5（2分）】
9．若需在o(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
a. 快速排序 b. 堆排序 c. 归并排序 d. 直接插入排序
【中国科技大学 1998 二、4（2分）】 【中科院计算所 1998 二、4（2分）】
10．下面的排序算法中，不稳定的是（ ） 【北京工业大学 1999 一、2 (2分)】
a.起泡排序 b.折半插入排序 c.简单选择排序 d.希尔排序 e.基数排序 f.堆排序。
11．下列内部排序算法中： 【北京工业大学 2000 一、1 (10分 每问2分)】
a．快速排序 b.直接插入排序 c. 二路归并排序 d. 简单选择排序 e. 起泡排序 f. 堆排序
（1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ）
（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<（4）排序的平均时间复杂度为o(n•logn)的算法是（ ）为o(n•n)的算法是（ ）
12．排序趟数与序列的原始状态有关的排序方法是( )排序法。【北京航空航天大学 1999 一、9（2分）】
a．插入 b. 选择 c. 冒泡 d. 快速
13．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( )
a．选择排序法 b. 插入排序法 c. 快速排序法 d. 堆积排序法
【北京航空航天大学 2000 一、10（2分）】
14．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。
a．直接插入 b. 二分法插入 c. 快速排序 d. 归并排序
【南京理工大学 2000 一、7 （1.5分）】
15．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ ）。【北京理工大学 2001 六、4 （2）】
a． 直接插入排序 b. 气泡排序 c. 快速排序 d. 直接选择排序
16．比较次数与排序的初始状态无关的排序方法是( )。【北方交通大学 2000 二、2（2分）】
a．直接插入排序 b．起泡排序 c．快速排序 d．简单选择排序
33．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）
a．直接插入排序 b．冒泡排序 c．简单选择排序 【山东工业大学 1995 二、1 （2分）】
类似本题的另外叙述有：
(1)在文件"局部有序"或文件长度较小的情况下，最佳内部排序的方法是（ ）。
a. 直接插入排序 b. 冒泡排序 c. 简单选择排序 d. 快速排序 【山东大学 2001 二、 2 (1分)】
(2)在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）。 【武汉大学 2000 二、6】
a.插入排序 b. 选择排序 c. 快速排序 d. 归并排序
34．下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。【南开大学 2000 一、4】 【西北大学 2001 二、1】
a. 堆排序 b. 冒泡排序 c. 快速排序 d. 插入排序
35. 下列排序算法中，占用辅助空间最多的是：( ) 【厦门大学 2002 五、2 （8分）】
a. 归并排序 b. 快速排序 c. 希尔排序 d. 堆排序
36．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。【北京航空航天大学 1999 一、8（2分）】
a. 插入 b. 选择 c. 希尔 d. 二路归并
37. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ ）。【中山大学 1999 一、11】
a. 选择 b. 冒泡 c. 插入 d. 堆
38．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ ）。
a． 94,32,40,90,80,46,21,69 b． 32,40,21,46,69,94,90,80
c． 21,32,46,40,80,69,90,94 d． 90,69,80,46,21,32,94,40
【北方交通大学 2001 一、15 （2分）】
39．直接插入排序在最好情况下的时间复杂度为（ ）【北京邮电大学 1999 一、5 （2分）】
a． o(logn) b． o(n) c． o(n*logn) d． o(n2)
40. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行 （ ）次比较。
a. 3 b. 10 c. 15 d. 25 【南京理工大学 1999 一、11（4分）】
类似本题的另外叙述有：
(1)若用冒泡排序对关键字序列{18,16,14,12,10,8},进行从小到大的排序，所需进行的关键字比较总次数是（ ） 【北京工商大学 2001 一、4（3分）】
a. 10 b. 15 c. 21 d. 34
41. 采用简单选择排序，比较次数与移动次数分别为( )。【南京理工大学 2000 一、18（1.5分）】
a. o（n）,o(logn) b. o(logn),0(n*n) c. 0(n*n),0(n) d. 0(nlogn),0(n)
42. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( ) 【南京理工大学 1999 一、15（1分）】
a. l b. 4 c. 3 d. 2
43．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ ）。
a． {21,25,5,17,9,23,30} b．{25,23,30,17,21,5,9}
c． {21,9,17,30,25,23,5} ｄ． {5,9,17,21,23,25,30}【北方交通大学 2001 一、18 （2分）】
44．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。
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分）】
45．对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）
a．每次分区后，先处理较短的部分 b．每次分区后，先处理较长的部分
c．与算法每次分区后的处理顺序无关 d．以上三者都不对 【北方交通大学 2000 二、5 （2分）】
46．当n个整型数据是有序时，对这n个数据用快速排序算法排序，则时间复杂度是 ( 6 )，当用递归算法求n!时，算法的时间复杂度是 ( 7 )，则：(6)-(7)=（ ）【南京理工大学1999 一、（6-7）（4分）】
a. o(n) b. o(nlogn) c. o(n*n) d. o(logn)
47．快速排序在最坏情况下的时间复杂度是( ),比( )的性能差。
a．o(nlogn) b．o(n2) c．o(n3) d．堆排序e．冒泡排序f．选择排序
【山东工业大学 1995 二、2 （4分）】
48. 快速排序方法在（ ）情况下最不利于发挥其长处。 【燕山大学 2001 一、3 （2分）】
a. 要排序的数据量太大 b. 要排序的数据中含有多个相同值
c. 要排序的数据个数为奇数 d. 要排序的数据已基本有序
49．在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。
a．ën/2û b．ën/2û -1 c．1 d．ën/2û +2 【中科院计算所2000 一、4（2分）】
50. 以下序列不是堆的是( )。【西安电子科技大学 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)
51．下列四个序列中，哪一个是堆（ ）。 【北京工商大学 2001 一、8 （3分）】
a. 75,65,30,15,25,45,20,10 b. 75,65,45,10,30,25,20,15
c. 75,45,65,30,15,25,20,10 d. 75,45,65,10,25,30,20,15
52. 堆排序是（ ）类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是（）
a. 插入 b. 交换 c. 归并 d. 基数 e. 选择
f. o（n2）和o（1） g. o（nlog2n）和o（1）
h. o（nlog2n）和o（n） i. o（n2）和o（n） 【西北大学 2001 二、2】
53．在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
a. o(log2n) b. o(1) c. o(n) d. o(nlog2n) 【西安电子科技大学2001应用一、10（2分）】
54． 对n 个记录的文件进行堆排序，最坏情况下的执行时间是多少？（ ）
a．o（log2n）b．o（n） c．o（nlog2n） d．o（n*n） 【北方交通大学 2001 一、9（2分）】
55. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ ）
a．-1，4，8，9，20，7，15，7 b．-1，7，15，7，4，8，20，9
c．-1，4，7，8，20，15，7，9 d．a，b，c均不对。 【南京理工大学 1996 二、5（2分）】
56. 归并排序中，归并的趟数是( )。【南京理工大学 2000 一、19（1.5分）】
a．o（n） b．o(logn) c．o(nlogn) d．o(n*n)
类似本题的另外叙述有：
(1)归并排序的时间复杂性是（ ）。 【中山大学 1999 一、12】
a.o（n*n） b. o（n） c. o（n*log（n）） d. o（log（n））
57． 在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫( )
a．插入排序 b．枚举排序 c．选择排序 d．交换排序【北京邮电大学 2000 二、6 （20/8分）】
58．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是 （ ）
a．堆排序〈 快速排序〈归并排序 b．堆排序〈 归并排序〈 快速排序
c．堆排序〉 归并排序 〉快速排序 d．堆排序 > 快速排序 > 归并排序
e．以上答案都不对 【西安交通大学 1996 三、1 (3分)】
59．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法， 而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 【北方交通大学 1999 一、3 （5分）】
（1）--（5）: a．选择排序 b．快速排序 c．插入排序 d．起泡排序
e．归并排序 f．shell排序 g．堆排序 h．基数排序
类似本题的另外叙述有：
（1）排序的方法有很多种，（ ）法从未排序的序列中依次取出元素与已排序序列中的元素比较，将其放在已排序序列的正确位置上；（ ）法从未排序序列中挑选元素，并将其依次放入已排序序列的一端；交换排序法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换。（ ）和（ ）是基于这类方法的两种排序方法，而 ( )是比( )效率更高的方法。供选择的答案：
a. 快速排序 b. 选择排序 c. 归并排序 d．冒泡排序 e．直接插入排序
【山东大学 1998 三、2 (5分)】 【山东工业大学 2000 三、2 （7分）】
60．设要将序列（q,h,c,y,p,a,m,s,r,d,f,x） 中的关键码按字母升序重新排序，
（1）（ ）是初始步长为4的shell排序一趟扫描的结果； （2）（ ）是对排序初始建堆的结果；
（3）（ ）是以第一个元素为分界元素的快速一趟扫描的结果。
从下面供选择的答案中选出正确答案填入括号内。 【厦门大学 2000 六、3 （16%/3分）】
a. f ,h ,c ,d ,p ,a ,m ,q ,r ,s ,y ,x b. p ,a ,c ,s ,q ,d ,f ,x ,r ,h ,m ,y
c. a ,d ,c ,r ,f ,q ,m ,s ,y ,p ,h ,x d. h ,c ,q ,p ,a ,m ,s ,r ,d ,f ,x ,y
e. h ,q ,c ,y ,a ,p ,m ,s ,d ,r ,f ,x
类似本题的另外叙述有：
（1）在内排序的过程中,通常需要对待排序的关键码进行多编扫描,采用不同重新排序方法,会产生不同的排序中间结果。设要将序列中的关键码按字母序的升序排列，则( 1 )是冒泡排序一趟扫描的结果,( 2 )是初始步长为4的希尔(shell)排序一趟扫描的结果,( 3 ) 是合并排序一趟扫描的结果,( 4 )是以第一个元素为分界元素的快速排序一趟扫描的结果,( 5 )是堆排序初始建堆的结果。供选择的答案: 【上海海运学院 1997 二、3 （5分）】
1-5:a. f,h,c,d,p,a,m,q,r,s,y,x b. p,a,c,s,q,d,f,x,r,h,m,y c. a,d,c,r,f,q,m,s,y,p,h,x
d. h,c,q,p,a,m,s,r,d,f,x,y e. h,q,c,y,a,p,m,s,d,r,f,x
61．对由n个记录所组成的表按关键码排序时,下列各个常用排序算法的平均比较次数分别是:二路归并排序为( 1 ),直接插入排序为( 2 ),快速排序为( 3 ),其中,归并排序和快速排序所需要的辅助存储分别是( 4 )和( 5 )。 【上海海运学院 1998 二、4 （5分）】
1-5:a. o(1) b. o（nlog2n） c. o（n） d. o（n2） e. o（n(log2n)2） f. o（log2n）
62．将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是( )
a．n b．2n-1 c．2n d．n-1
【中科院计算所 1998 二、7 （2分）】 【中国科技大学 1998 二、7 （2分）】
63. 基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（ ）。
a. o(nlogn) b. o(logn) c. o(n) d. o(n*n) 【南京理工大学 1996 一、2 （2分）】
64．已知待排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。
a. o(nlog2n) b. o(nlog2k) c. o(klog2n) d. o(klog2k) 【中国科技大学 1998 二、9 （2分）】
类似本题的另外叙述有：
(1)已知待排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( )
a. o(klog2k) b. o(klog2n) c. o(nlog2k) d. o(nlog2n) 【中科院计算所 1998 二、9 （2分）】
65．采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k （ ）
a． 有关 b．无关 【北京工业大学 2000 一 、2 (3分)】
66．采用败者树进行k路平衡归并时，总的（包括访外）归并效率与k（ ）。
a．有关 b．无关 【北京工业大学 2001 一、4 (2分)】
类似本题的另外叙述有：
(1)n个元素的序列满足什么条件才能称之为堆？用类pascal语言写出堆排序和算法。
【南开大学 1997 七 (15分)】
14．设待排序的文件用单链表作存储结构，其形式如下：
type pointer=↑node;
node=record
key:integer;
next:pointer;
end;
写出以head为头指针的选择排序算法。 【中山大学 1999 二 （10分）】
15．非递归的快速排序算法。【中科院软件所 1997 三 (10分)】
16．一最小最大堆（min max heap）是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小（或最大）。如图所示为一最小最大堆；
(1) 画出在上图中插入关键字为5的结点后的最小最大堆。
(2) 画出在上图中插入关键字为80 的结点后的最小最大堆；
(3) 编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。
(4) 用c或pasca；实现上述算法。 【浙江大学 1996 八 (26分 )】
17. 二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注:向量d可视为循环表），其原则为，先将r[l]赋给d[1]，再从r[2] 记录开始分二路插入。编写实现二路插入排序算法。 【北京工业大学 1998 八 (10分)】
18． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。（179,208,93,306,55,859,984,9,271,33） 【南京航空航天大学 2000 一 】
19．输入n个只含一位数字的整数，试用基数排序的方法，对这n个数排序。
【中国人民大学 2001 三、1（10分）】
20．设记录r[i]的关键字为r[i].key（1<=i<=k），树结点t[i]（1<=i<=k-1）指向败者记录，t[0]为全胜记录下标。写一算法产生对应上述r[i]（1<=i<= k）的败者树，要求除r[1..k]和t[0..k-1]以外，只用o(1)辅助空间。 【东南大学 1995 九 （15分）】
21．设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红,白,蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。【上海大学 1999 二 2（18分）】
22. 数据结构deap的定义如下：deap是一棵完全二叉树，它或者是一棵空树，或者满足下列特性：
（1）树根不包含元素．（2）其左子树是一小堆（minheap），其右子树是一大堆（maxheap）．
（3）若右子树非空，设ｉ是左子树的任一结点，ｊ是右子树中与ｉ相应的结点．若这样的ｊ结点不存在，则取ｊ为右子树中与ｉ的父结点相应的结点；结点ｉ的关键字总是小于或等于结点ｊ的关键字值。
一个deap的例子如右图所示，
与结点15相对应的结点为20，与结点19对应的结点为25．
（1） 给出在该deap中插入结点4后的结果．
（2） 写出在deap中插入新结点的算法．
（3） 用c或pascal语言编写实现上述算法的程序．（20分）
【浙江大学 1997 7 （20分）】
一、选择题
1．某内排序方法的稳定性是指( )。 【南京理工大学 1997 一、10（2分）】
a．该排序算法不允许有相同的关键字记录 b．该排序算法允许有相同的关键字记录
c．平均时间为0（n log n）的排序方法 d．以上都不对
2．下面给出的四种排序法中( )排序法是不稳定性排序法。【北京航空航天大学 1999 一、10 （2分）】
a. 插入 b. 冒泡 c. 二路归并 d. 堆积
3．下列排序算法中，其中（ ）是稳定的。 【福州大学 1998 一、3 (2分)】
a. 堆排序，冒泡排序 b. 快速排序，堆排序
c. 直接选择排序，归并排序 d. 归并排序，冒泡排序
4．稳定的排序方法是（ ） 【北方交通大学 2000 二、3（2分）】
a．直接插入排序和快速排序 b．折半插入排序和起泡排序
c．简单选择排序和四路归并排序 d．树形选择排序和shell排序
5．下列排序方法中，哪一个是稳定的排序方法？（ ） 【北方交通大学 2001 一、8（2分）】
a．直接选择排序 b．二分法插入排序 c．希尔排序 d．快速排序
6．若要求尽可能快地对序列进行稳定的排序，则应选（a．快速排序 b．归并排序 c．冒泡排序）。
【北京邮电大学 2001 一、5（2分）】
7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ ）就是不稳定的排序方法。【清华大学 1998 一、3 (2分）】
a．起泡排序 b．归并排序 c．shell排序 d．直接插入排序 e．简单选择排序
8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
a．直接插入 b．直接选择 c．堆 d．快速 e．基数 【中科院计算所 2000 一、5（2分）】
9．若需在o(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
a. 快速排序 b. 堆排序 c. 归并排序 d. 直接插入排序
【中国科技大学 1998 二、4（2分）】 【中科院计算所 1998 二、4（2分）】
10．下面的排序算法中，不稳定的是（ ） 【北京工业大学 1999 一、2 (2分)】
a.起泡排序 b.折半插入排序 c.简单选择排序 d.希尔排序 e.基数排序 f.堆排序。
11．下列内部排序算法中： 【北京工业大学 2000 一、1 (10分 每问2分)】
a．快速排序 b.直接插入排序 c. 二路归并排序 d. 简单选择排序 e. 起泡排序 f. 堆排序
（1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ）
（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<
12．排序趟数与序列的原始状态有关的排序方法是( )排序法。【北京航空航天大学 1999 一、9（2分）】
a．插入 b. 选择 c. 冒泡 d. 快速
13．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( )
a．选择排序法 b. 插入排序法 c. 快速排序法 d. 堆积排序法
【北京航空航天大学 2000 一、10（2分）】
14．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。
a．直接插入 b. 二分法插入 c. 快速排序 d. 归并排序
【南京理工大学 2000 一、7 （1.5分）】
15．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ ）。【北京理工大学 2001 六、4 （2）】
a． 直接插入排序 b. 气泡排序 c. 快速排序 d. 直接选择排序
16．比较次数与排序的初始状态无关的排序方法是( )。【北方交通大学 2000 二、2（2分）】
a．直接插入排序 b．起泡排序 c．快速排序 d．简单选择排序
21．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（ ）排序。
a．选择 b. 堆 c. 直接插入 d. 冒泡 【南京理工大学 1998 一、9（2分）】
22．下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。
a.快速排序 b. shell排序 c. 堆排序 d.冒泡排序 【合肥工业大学 2001 一、3（2分）】
23．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
a. 选择 b. 冒泡 c. 归并 d. 堆
【南京理工大学 2001 一、7（1.5分）】【哈尔滨工业大学 2001 二、4（2分）】
24．下列序列中，（ ）是执行第一趟快速排序后所得的序列。 【福州大学 1998 一、9 (2分)】
a. [68，11，18，69] [23，93，73] b. [68，11，69，23] [18，93，73]
c. [93，73] [68，11，69，23，18] d. [68，11，69，23，18] [93，73]
25．有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为 ( )（按递增序）。 【南京理工大学 1996 一、4 （2分）】
a．下面的b，c，d都不对。 b．9，7，8，4，-1，7，15，20
c．20，15，8，9，7，-1，4，7 d. 9，4，7，8，7，-1，15，20
26．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。 【燕山大学 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)
27. 在下面的排序方法中，辅助空间为o（n）的是( ) 。【南京理工大学 1999 一、17（1分）】
a．希尔排序 b. 堆排序 c. 选择排序 d. 归并排序
28．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。
a． 冒泡 b. 希尔 c. 快速 d. 堆 【南京理工大学 2001 一、12 （1.5分）】
29.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ ）。
a. 直接插入排序 b. 快速排序 c. 直接选择排序 d. 堆排序
30. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（ ）算法，最费时间的是（ ）算法。
a. 堆排序 b. 快速排序 c. 插入排序 d. 归并排序 【南开大学 2000 一、5】
31. 就平均性能而言，目前最好的内排序方法是( )排序法。【西安电子科技大学 1998 一、9 (2分）】
a. 冒泡 b. 希尔插入 c. 交换 d. 快速
32．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。
a．起泡排序 b．快速排列 c．shell排序 d．堆排序 e．简单选择排序
【清华大学 1998 一、2 （2分）】
类似本题的另外叙述有：
(1)设有5000个无序的元素,希望用最快的速度挑选出其中前十个最大的元素,在以下的排序方法中( )最好?为什么? 【山东工业大学 1995 二、4 （3分）】
a．快速排序 b．堆排序 c．归并排序 d．基数排序 e．shell排序
(2)数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )算法最节省时间。
a. 堆排序 b. 希尔排序 c. 快速排序 d. 直接选择排序 【北京理工大学 2000 一、5 （2分）】
(3)设有1000个无序的元素，希望用最快的速度挑选出其中前十个最大的元素，在以下的排序方法中采用哪一种最好？ ( ) 【东北大学 1999 一、5 (3分)】
a. 快速排序 b. 归并排序 c. 堆排序 d.基数排序 e.shell排序
33．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）
a．直接插入排序 b．冒泡排序 c．简单选择排序 【山东工业大学 1995 二、1 （2分）】
类似本题的另外叙述有：
(1)在文件"局部有序"或文件长度较小的情况下，最佳内部排序的方法是（ ）。
a. 直接插入排序 b. 冒泡排序 c. 简单选择排序 d. 快速排序 【山东大学 2001 二、 2 (1分)】
(2)在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）。 【武汉大学 2000 二、6】
a.插入排序 b. 选择排序 c. 快速排序 d. 归并排序
34．下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。【南开大学 2000 一、4】 【西北大学 2001 二、1】
a. 堆排序 b. 冒泡排序 c. 快速排序 d. 插入排序
35. 下列排序算法中，占用辅助空间最多的是：( ) 【厦门大学 2002 五、2 （8分）】
a. 归并排序 b. 快速排序 c. 希尔排序 d. 堆排序
36．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。【北京航空航天大学 1999 一、8（2分）】
a. 插入 b. 选择 c. 希尔 d. 二路归并
37. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ ）。【中山大学 1999 一、11】
a. 选择 b. 冒泡 c. 插入 d. 堆
38．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ ）。
a． 94,32,40,90,80,46,21,69 b． 32,40,21,46,69,94,90,80
c． 21,32,46,40,80,69,90,94 d． 90,69,80,46,21,32,94,40
【北方交通大学 2001 一、15 （2分）】
39．直接插入排序在最好情况下的时间复杂度为（ ）【北京邮电大学 1999 一、5 （2分）】
a． o(logn) b． o(n) c． o(n*logn) d． o(n2)
40. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行 （ ）次比较。
a. 3 b. 10 c. 15 d. 25 【南京理工大学 1999 一、11（4分）】
类似本题的另外叙述有：
(1)若用冒泡排序对关键字序列{18,16,14,12,10,8},进行从小到大的排序，所需进行的关键字比较总次数是（ ） 【北京工商大学 2001 一、4（3分）】
a. 10 b. 15 c. 21 d. 34
41. 采用简单选择排序，比较次数与移动次数分别为( )。【南京理工大学 2000 一、18（1.5分）】
a. o（n）,o(logn) b. o(logn),0(n*n) c. 0(n*n),0(n) d. 0(nlogn),0(n)
42. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( ) 【南京理工大学 1999 一、15（1分）】
a. l b. 4 c. 3 d. 2
43．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ ）。
a． {21,25,5,17,9,23,30} b．{25,23,30,17,21,5,9}
c． {21,9,17,30,25,23,5} ｄ． {5,9,17,21,23,25,30}【北方交通大学 2001 一、18 （2分）】
44．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。
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分）】
45．对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）
a．每次分区后，先处理较短的部分 b．每次分区后，先处理较长的部分
c．与算法每次分区后的处理顺序无关 d．以上三者都不对 【北方交通大学 2000 二、5 （2分）】
46．当n个整型数据是有序时，对这n个数据用快速排序算法排序，则时间复杂度是 ( 6 )，当用递归算法求n!时，算法的时间复杂度是 ( 7 )，则：(6)-(7)=（ ）【南京理工大学1999 一、（6-7）（4分）】
a. o(n) b. o(nlogn) c. o(n*n) d. o(logn)
47．快速排序在最坏情况下的时间复杂度是( ),比( )的性能差。
a．o(nlogn) b．o(n2) c．o(n3) d．堆排序e．冒泡排序f．选择排序
【山东工业大学 1995 二、2 （4分）】
48. 快速排序方法在（ ）情况下最不利于发挥其长处。 【燕山大学 2001 一、3 （2分）】
a. 要排序的数据量太大 b. 要排序的数据中含有多个相同值
c. 要排序的数据个数为奇数 d. 要排序的数据已基本有序
49．在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。
a．ën/2û b．ën/2û -1 c．1 d．ën/2û +2 【中科院计算所2000 一、4（2分）】
50. 以下序列不是堆的是( )。【西安电子科技大学 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)
51．下列四个序列中，哪一个是堆（ ）。 【北京工商大学 2001 一、8 （3分）】
a. 75,65,30,15,25,45,20,10 b. 75,65,45,10,30,25,20,15
c. 75,45,65,30,15,25,20,10 d. 75,45,65,10,25,30,20,15
52. 堆排序是（ ）类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是（）
a. 插入 b. 交换 c. 归并 d. 基数 e. 选择
f. o（n2）和o（1） g. o（nlog2n）和o（1）
h. o（nlog2n）和o（n） i. o（n2）和o（n） 【西北大学 2001 二、2】
53．在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
a. o(log2n) b. o(1) c. o(n) d. o(nlog2n) 【西安电子科技大学2001应用一、10（2分）】
54． 对n 个记录的文件进行堆排序，最坏情况下的执行时间是多少？（ ）
a．o（log2n）b．o（n） c．o（nlog2n） d．o（n*n） 【北方交通大学 2001 一、9（2分）】
55. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ ）
a．-1，4，8，9，20，7，15，7 b．-1，7，15，7，4，8，20，9
c．-1，4，7，8，20，15，7，9 d．a，b，c均不对。 【南京理工大学 1996 二、5（2分）】
56. 归并排序中，归并的趟数是( )。【南京理工大学 2000 一、19（1.5分）】
a．o（n） b．o(logn) c．o(nlogn) d．o(n*n)
类似本题的另外叙述有：
(1)归并排序的时间复杂性是（ ）。 【中山大学 1999 一、12】
a.o（n*n） b. o（n） c. o（n*log（n）） d. o（log（n））
57． 在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫( )
a．插入排序 b．枚举排序 c．选择排序 d．交换排序【北京邮电大学 2000 二、6 （20/8分）】
58．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是 （ ）
a．堆排序〈 快速排序〈归并排序 b．堆排序〈 归并排序〈 快速排序
c．堆排序〉 归并排序 〉快速排序 d．堆排序 > 快速排序 > 归并排序
e．以上答案都不对 【西安交通大学 1996 三、1 (3分)】
59．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法， 而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 【北方交通大学 1999 一、3 （5分）】
（1）--（5）: a．选择排序 b．快速排序 c．插入排序 d．起泡排序
e．归并排序 f．shell排序 g．堆排序 h．基数排序
类似本题的另外叙述有：
（1）排序的方法有很多种，（ ）法从未排序的序列中依次取出元素与已排序序列中的元素比较，将其放在已排序序列的正确位置上；（ ）法从未排序序列中挑选元素，并将其依次放入已排序序列的一端；交换排序法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换。（ ）和（ ）是基于这类方法的两种排序方法，而 ( )是比( )效率更高的方法。供选择的答案：
a. 快速排序 b. 选择排序 c. 归并排序 d．冒泡排序 e．直接插入排序
【山东大学 1998 三、2 (5分)】 【山东工业大学 2000 三、2 （7分）】
60．设要将序列（q,h,c,y,p,a,m,s,r,d,f,x） 中的关键码按字母升序重新排序，
（1）（ ）是初始步长为4的shell排序一趟扫描的结果； （2）（ ）是对排序初始建堆的结果；
（3）（ ）是以第一个元素为分界元素的快速一趟扫描的结果。
从下面供选择的答案中选出正确答案填入括号内。 【厦门大学 2000 六、3 （16%/3分）】
a. f ,h ,c ,d ,p ,a ,m ,q ,r ,s ,y ,x b. p ,a ,c ,s ,q ,d ,f ,x ,r ,h ,m ,y
c. a ,d ,c ,r ,f ,q ,m ,s ,y ,p ,h ,x d. h ,c ,q ,p ,a ,m ,s ,r ,d ,f ,x ,y
e. h ,q ,c ,y ,a ,p ,m ,s ,d ,r ,f ,x
类似本题的另外叙述有：
（1）在内排序的过程中,通常需要对待排序的关键码进行多编扫描,采用不同重新排序方法,会产生不同的排序中间结果。设要将序列
1-5:a. f,h,c,d,p,a,m,q,r,s,y,x b. p,a,c,s,q,d,f,x,r,h,m,y c. a,d,c,r,f,q,m,s,y,p,h,x
d. h,c,q,p,a,m,s,r,d,f,x,y e. h,q,c,y,a,p,m,s,d,r,f,x
61．对由n个记录所组成的表按关键码排序时,下列各个常用排序算法的平均比较次数分别是:二路归并排序为( 1 ),直接插入排序为( 2 ),快速排序为( 3 ),其中,归并排序和快速排序所需要的辅助存储分别是( 4 )和( 5 )。 【上海海运学院 1998 二、4 （5分）】
1-5:a. o(1) b. o（nlog2n） c. o（n） d. o（n2） e. o（n(log2n)2） f. o（log2n）
62．将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是( )
a．n b．2n-1 c．2n d．n-1
【中科院计算所 1998 二、7 （2分）】 【中国科技大学 1998 二、7 （2分）】
63. 基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（ ）。
a. o(nlogn) b. o(logn) c. o(n) d. o(n*n) 【南京理工大学 1996 一、2 （2分）】
64．已知待排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。
a. o(nlog2n) b. o(nlog2k) c. o(klog2n) d. o(klog2k) 【中国科技大学 1998 二、9 （2分）】
类似本题的另外叙述有：
(1)已知待排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( )
a. o(klog2k) b. o(klog2n) c. o(nlog2k) d. o(nlog2n) 【中科院计算所 1998 二、9 （2分）】
65．采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k （ ）
a． 有关 b．无关 【北京工业大学 2000 一 、2 (3分)】
66．采用败者树进行k路平衡归并时，总的（包括访外）归并效率与k（ ）。
a．有关 b．无关 【北京工业大学 2001 一、4 (2分)】
类似本题的另外叙述有：
(1)n个元素的序列满足什么条件才能称之为堆？用类pascal语言写出堆排序和算法。
【南开大学 1997 七 (15分)】
14．设待排序的文件用单链表作存储结构，其形式如下：
type pointer=↑node;
node=record
key:integer;
next:pointer;
end;
写出以head为头指针的选择排序算法。 【中山大学 1999 二 （10分）】
15．非递归的快速排序算法。【中科院软件所 1997 三 (10分)】
16．一最小最大堆（min max heap）是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小（或最大）。如图所示为一最小最大堆；
(1) 画出在上图中插入关键字为5的结点后的最小最大堆。
(2) 画出在上图中插入关键字为80 的结点后的最小最大堆；
(3) 编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。
(4) 用c或pasca；实现上述算法。 【浙江大学 1996 八 (26分 )】
17. 二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注:向量d可视为循环表），其原则为，先将r[l]赋给d[1]，再从r[2] 记录开始分二路插入。编写实现二路插入排序算法。 【北京工业大学 1998 八 (10分)】
18． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。（179,208,93,306,55,859,984,9,271,33） 【南京航空航天大学 2000 一 】
19．输入n个只含一位数字的整数，试用基数排序的方法，对这n个数排序。
【中国人民大学 2001 三、1（10分）】
20．设记录r[i]的关键字为r[i].key（1<=i<=k），树结点t[i]（1<=i<=k-1）指向败者记录，t[0]为全胜记录下标。写一算法产生对应上述r[i]（1<=i<= k）的败者树，要求除r[1..k]和t[0..k-1]以外，只用o(1)辅助空间。 【东南大学 1995 九 （15分）】
21．设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红,白,蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。【上海大学 1999 二 2（18分）】
22. 数据结构deap的定义如下：deap是一棵完全二叉树，它或者是一棵空树，或者满足下列特性：
（1）树根不包含元素．（2）其左子树是一小堆（minheap），其右子树是一大堆（maxheap）．
（3）若右子树非空，设ｉ是左子树的任一结点，ｊ是右子树中与ｉ相应的结点．若这样的ｊ结点不存在，则取ｊ为右子树中与ｉ的父结点相应的结点；结点ｉ的关键字总是小于或等于结点ｊ的关键字值。
一个deap的例子如右图所示，
与结点15相对应的结点为20，与结点19对应的结点为25．
（1） 给出在该deap中插入结点4后的结果．
（2） 写出在deap中插入新结点的算法．
（3） 用c或pascal语言编写实现上述算法的程序．（20分）
【浙江大学 1997 7 （20分）】