考研历年排序题目

《考研历年排序题目》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

第10章排序一、选择题1.某内排序方法的稳定性是指（）。【南京理工大学1997—、10（2分】A.该排序算法不允许有相同的关键字记录B.该排序算法允许有相同的关键字记录C.平均时间为0（nlogn）的排序方法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.若需在0（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序B.堆排序C.归并排序D.直接插入排序【中国科技大学1998二、4（2分】【中科院计算所1998二、4（2分）】10.下面的排序算法中，不稳定的是（cf）【北京工业大学1999一、2（2分）】A.起泡排序B.折半插入排序C.简单选择排序D.希尔排序E.基数排序F.堆排序。11.下列内部排序算法中：【北京工业大学2000一、1（10分每问2分）】A.快速排序B.直接插入排序C.二路归并排序D.简单选择排序E.起泡排序F.堆排序

1（1）其比较次数与序列初态无关的算法是（de）（2）不稳定的排序算法是(adf)(3)在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序，k«n)的情况下，排序效率最高的算法是(b)(4)排序的平均时间复杂度为O(n・logn)的算法是(acf)为O(n・n)的算法是(bde)1.排序趟数与序列的原始状态有关的排序方法是(b)排序法。【北京航空航天大学1999一、9(2分】A.插入B.选择C.冒泡D.快速2.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。(a)A.选择排序法B.插入排序法C.快速排序法D.堆积排序法【北京航空航天大学2000一、10(2分】3.对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是(d)oA.直接插入B.二分法插入C.快速排序D.归并排序【南京理工大学2000—、7(1.5分】4.在下列排序算法中，哪一个算法的时间复杂度与初始排序无关(d)。【北京理工大学2001六、4(2)]A.直接插入排序B.气泡排序C,快速排序D.直接选择排序16.比较次数与排序的初始状态无关的排序方法是(d)。【北方交通大学2000二、2(2分)】A.直接插入排序B.起泡排序C.快速排序D.简单选择排序17.数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的()的两趟排序后的结果。A.选择排序B.冒泡排序C.插入排序D.堆排序【合肥工业大学1999一、3(2分】18.数据序列(2,1,4,9,8,10,6,20)只能是下列排序算法中的()的两趟排序后的结果。A.快速排序B.冒泡排序C.选择排序D.插入排序【合肥工业大学2000一、3(2分】19.对一组数据(84,47,25,15,21)排序，数据的排列次序在排序的过程中的变化为(1)8447251521(2)1547258421(3)1521258447(4)1521254784则采用的排序是()。【南京理工大学1997一、2(2分】A.选择B.冒泡C.快速D.插入20.对序列｛15,9,7,8,20,-1,4｝进行排序，进行一趟后数据的排列变为｛4,9,-1,8,20,7,15)；则采用的是()排序。【南京理工大学1998—、8(2分】A.选择B.快速C.希尔D.冒泡21.若上题的数据经一趟排序后的排列为{9,15,7,8,20,-1,4},则采用的是（

2）排序。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,20C.20,15,8,9,7,-1,4,7D.9,4,7,8,7,-1,15,2026.一组记录的关键码为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）o【燕山大学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.在下面的排序方法中，辅助空间为0（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.快速

331.如果只想得到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排序32.在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）A.直接插入排序B.冒泡排序C.简单选择排序【山东工业大学1995二、1（2分】类似本题的另外叙述有:（1）在文件"局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）oA.直接插入排序B.冒泡排序C.简单选择排序D.快速排序【山东大学2001二、2（1分）】（2）在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）o【武汉大学2000二、6]A.插入排序B.选择排序C.快速排序D.归并排序33.下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。【南开大学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]

4A.选择B.冒泡C.插入D.堆36.用直接插入排序方法对下面四个序列进行排序(由小到大)，元素比较次数最少的是()。A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,40【北方交通大学2001一、15(2分】37.直接插入排序在最好情况下的时间复杂度为()【北京邮电大学1999一、5(2分】A.0(1ogn)B.0(n)C.0(n*logn)D.0(n2)40.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行()次比较。A.3B.10C.15D.25【南京理工大学1999一、11(4分】类似本题的另外叙述有:(1)若用冒泡排序对关键字序列{18,16,14,12,10,8},进行从小到大的排序，所需进行的关键字比较总次数是()【北京工商大学2001一、4(3分】A.10B.15C.21D.3441.采用简单选择排序，比较次数与移动次数分别为()。【南京理工大学2000一、18(1.5分】A.0(n),0(logn)B.0(logn),0(n*n)C.0(n*n),0(n)D.0(nlogn),0(n)42.对序列{15,9,7,8,20,-1,4,}用希尔排序方法排序，经一趟后序列变为{15,-1,4,8,20,9,7}则该次采用的增量是()【南京理工大学1999一、15(1分】A.1B.4C.3D.243.对下列关键字序列用快速排序法进行排序时，速度最快的情形是()oA.{21,25,5,17,9,23,30}B.{25,23,30,17,21,5,9}C.{21,9,17,30,25,23,5}D.{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个数据用快速排序算法排序，则时间复杂度是(c),当用递归算法求n!时，算法的时间复杂度是(7),则：(6)-(7)=

5()【南京理工大学1999-(6-7)(4分)】A.0(n)B.O(nlogn)C,0(n*n)D.O(logn)40.快速排序在最坏情况下的时间复杂度是()，比()的性能差。A.O(NlogN)B.0(N2)C.0(N3)D.堆排序E.冒泡排序F.选择排序【山东工业大学1995二、2(4分】41.快速排序方法在()情况下最不利于发挥其长处。【燕山大学2001一、3(2分)】A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本仃序49.在含有n个关键字的小根堆(堆顶元素最小)中，关键字最大的记录有可能存储在()位置上。A.Ln/2jB.Ln/2j-lC.1D.|_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.下列四个序列中，哪一个是堆(分】A.75,65,30,15,25,45,20,10C.75,45,65,30,15,25,20,10)»【北京工商大学2001一、8(3B.75,65,45,10,30,25,20,15D.75,45,65,10,25,30,20,1552.堆排序是(e)类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(g)A.插入B.交换F.0(n2)和0⑴H.0(nlog2n)和0(n)C.归并D.基数E.选择G.0(nlog2n)和0(1)I.0(n2)和0(n)【西北大学2001二、53.在对n个元素的序列进行排序时,A.0(log2n)B.0(1)C,0(n)应用一、10(2分)】54.对n个记录的文件进行堆排序,堆排序所需要的附加存储空间是()oD.0(nlog2n)【西安电子科技大学2001最坏情况下的执行时间是多少？()A.0(log2n)B.0(n)C.0(nlog2n)D.0(n*n)【北方交通大学2001~■、9(2分)】55.有一组数据(15,9,7,8,20,-1,7,4),用堆排序的筛选方法建立的初始堆为()A.-1,4,8,9,20,7,15,7B.-1,7,15,7,4,8,20,9C.-1,4,7,8,20,15,7,9D.A,B,C均不对。【南京理工大学1996二、5(2分】56.归并排序中，归并的趟数是()。【南京理工大学200019(1.5分】A.0(n)B.O(logn)C.0(nlogn)D.0(n*n)类似本题的另外叙述有:(1)归并排序的时间复杂性是()o【中山大学1999一、12]A.0(N*N)B.0(N)C.0(N*LOG(N)>D.0(LOG(N))

655.在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫（）A.插入排序B.枚举排序C.选择排序D.交换排序【北京邮电大学2000二、6（20/8分】56.就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（）A.堆排序〈快速排序〈归并排序B.堆排序〈归并排序〈快速排序C.堆排序〉归并排序〉快速排序D.堆排序>快速排序>归并排序E.以上答案都不对【西安交通大学1996三、1（3分）】57.排序方法有许多种,3法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上;法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换;（b）和（d）是基于这类方法的两种排序方法，而（b）是比（d）效率更高的方法;迎法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。【北方交通大学1999一、3（5分】（1）—（5）:A.选择排序B.快速排序C.插入排序D.起泡排序E.归并排序F.shell排序G.堆排序H.基数排序类似本题的另外叙述有:（1）排序的方法有很多种，（e）法从未排序的序列中依次取出元素与已排序序列中的元素比较，将其放在已排序序列的正确位置上；（b）法从未排序序列中挑选元素，并将其依次放入已排序序列的一端；交换排序法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换。（）和（）是基于这类方法的两种排序方法，而（）是比（）效率更高的方法。供选择的答案：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）（b）是初始步长为4的shell排序一趟扫描的结果；（2）（）是对排序初始建堆的结果；（3）（a）是以第一个元素为分界元素的快速一趟扫描的结果。从下面供选择的答案中选出正确答案填入括号内。【厦门大学2000六、3（16%/3分）】A.f,h,c,d,p,a,m,q,r,s,y,xB.p,a,c,s,q,d,f,x,r,h,m,yC.a,d,c,r,f,q,m,s,y,p,h,xD.h,c,q,p,a,m,s,r,d,f,x,yE.h,q,c,y,a,p,m,s,d,r,f,x类似本题的另外叙述有:(1)在内排序的过程中，通常需要对待排序的关键码进行多编扫描,采用不同重新排序方法，会产生不同的排序中间结果。设要将序列

7趟扫描的结果，(4)是以第一个元素为分界元素的快速排序一趟扫描的结果，(5)是堆排序初始建堆的结果。供选择的答案：【上海海运学院1997二、3(5分】1~5:A.f,h,c,d,p,a,m,q,r,s,y,xB.p,a,c,s,q,d,f,x,r,h,m,yC.a,d,c,r,f,q,m,s,y,p,h,xC.h,c,q,p,a,m,s,r,d,f,x,yE.h,q,c,y,a,p,m,s,d,r,f,x61.对由n个记录所组成的表按关键码排序时,下列各个常用排序算法的平均比较次数分别是:二路归并排序为(B),直接插入排序为(D.)，快速排序为(B)，其中，归并排序和快速排序所需要的辅助存储分别是(C)和(F)o【上海海运学院1998二、4(5分】1-5:A.0(1)B.0(nlog2n)C.0(n)D.0(n2)E.0(n(log2n)2)F.0(log2n)62.将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是()A.NB.2N-1C.2ND.N-1【中科院计算所1998二、7(2分)】【中国科技大学1998二、7(2分】63.基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是()oA.O(nlogn)B.O(logn)C.0(n)D.0(n*n)【南京理工大学1996一、2(2分】64.已知待排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为()oA.0(nlog2n)B.0(nlog2k)C.0(klog2n)D.0(klog2k)【中国科技大学1998二、9(2分】类似本题的另外叙述有:(1)已知待排序的N个元素可分为N/K个组，每个组包含K个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为()A.0(klog2k)B.0(klog2n)C.O(nlog2k)D.0(nlog2n)【中科院计算所1998二、9(2分)】65.采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k()A.有关B.无关【北京工业大学2000一、2(3分)】66.采用败者树进行K路平衡归并时，总的(包括访外)归并效率与K()。A.有关B.无关【北京工业大学2001一、4(2分)】二、判断题：1.当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。(V)【长沙铁道学院1998一、10(1分)】2.内排序要求数据一定要以顺序方式存储。(x)【南京理工大学1997二、2(2分]3.排序算法中的比较次数与初始元素序列的排列无关。(x)【南京航空航天大学1997一、8(1分】4.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。(x)【南京航空航天大学1996六、9(1分】5.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。(v)【上海交通大学1998一、18]6.直接选择排序算法在最好情况下的时间复杂度为0(N)。(x)【合肥工业大学2001二、10(1分】

81.两分法插入排序所需比较次数与待排序记录的初始排列状态相关。(v)[上海交通大学1998一、15]2.在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。(x)【合肥工业大学2000二、9(1分】3.在待排数据基本有序的情况下，快速排序效果最好。(x)【南京理工大学1997二、4(2分)】4.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。(x)【上海交通大学1998—,16]5.快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。(x)【北京邮电大学1998一、7(2分】6.堆肯定是一棵平衡二叉树。(v)【南京航空航天大学1997一、6(1分】7.堆是满二叉树。(x)【南京航空航天大学1996六、6(1分】8.(101,88,46,70,34,39,45,58,66,10)是堆。(v)【北京邮电大学1999二、1(2分】9.在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。(v)【合肥工业大学2000二、10(1分】10.堆排序是稳定的排序方法。(x)【上海交通大学1998一、19]11.归并排序辅助存储为0(l)o(x)【青岛大学2000四、9(1分】12.在分配排序时，最高位优先分配法比最低位优先分配法简单。(x)【上海交通大学1998一、20]13.冒泡排序和快速排序都是基于交换两个逆序元素的排序方法，冒泡排序算法的最坏时间复杂性是0(n*n),而快速排序算法的最坏时间复杂性是O(nlogJ),所以快速排序比冒泡排序算法效率更高。(x)【上海海运学院1997一、9(1分】14.交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是0(n*最，而快速排序算法的最坏时间复杂性是0(nlog?n)；所以快速排序比冒泡排序效率更高。(x)【上海海运学院1998一、10(1分)】【上海海运学院1995一、10(1分】15.快速排序和归并排序在最坏情况下的比较次数都是O(nlogm)。(x)【上海海运学院1996—、9(1分】16.在任何情况下，归并排序都比简单插入排序快。（x）【北京邮电大学2000一、4（1分】17.归并排序在任何情况下都比所有简单排序速度快。（x）【北京邮电大学2002一、9（1分）】18.快速排序总比简单排序快。（x）【东南大学2001—、9（1分）】19.中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（）【中山大学1994一、4（2分】20.外部排序是把外存文件调入内存,可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（）【北京邮电大学1998一、8（2分】21.在外部排序时，利用选择树方法在能容纳m个记录的内存缓冲区中产生的初始归并段的平均长度为2m个记录。（）【上海海运学院1999一、10（1分）】

91.为提高在外排序过程中，对长度为N的初始序列进行“置换一选择”排序时，可以得到的最大初始有序段的长度不超过N/2。（）2.排序速度，进行外排序时，必须选用最快的内排序算法。（）3.在完成外排序过程中，每个记录的I/O次数必定相等。（）【大连海事大学2001一、20（每题1分）］4.影响外排序的时间因素主要是内存与外设交换信息的总次数。（）【东北大学1997二、5（2分）】三、填空题1.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的和记录的O【北京邮电大学2001二、7（4分】2.外排序的基本操作过程是和。【西安电子科技大学1998二、3（3分】类似本题的另外叙述有:（1）外部排序中两个相对独立的阶段是__和_o［西安电子科技大学1999软件一、8（2分）】3.属于不稳定排序的有快速堆shell-【青岛大学2002三、5（2分】4.分别采用堆排序，快速排序，冒泡年序和归并排序，对初态为有序的表，则最省时间的是直接插入算法，最费时间的是快速算法。【福州大学1998二、10（2分）】类似本题的另外叙述有:（1）设表中元素的初始状态是按健值递增的，分别用堆排序，快速排序，冒泡排序和归并排序方法对其进行排序（按递增顺序），—冒泡排序最省时间，_快速排序最费时间。【厦门大学2001—、5（14%/5分）］5.不受待排序初始序列的影响，时间复杂度为O（V）的排序算法是简单选择，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是直接插入。【中国人民大学2001一、3（2分）】6.直接插入排序用监视哨的作用是防止越界。【南京理工大学2001二、8（2分】7.对n个记录的表进行简单选择排序，所需进行的关键字间的比较次数为n2o【华中理工大学2000一、10(1分】8.用链表表示的数据的简单选择排序，结点的域为数据域data,指针域next；链表首指针为head,链表无头结点。selectsort(head)p=head;while(p(1)){q=p；r=(2)while((3)){if((4))q=r;r=(5);)tmp=q->data;q->data=p->data;p->data=tmp;p=⑹;)【南京理工大学2000三、2(6分】

107.下面的c函数实现对链表head进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式：#includetypedefstructnode{chardata;structnode*link;}node;node*select(node*head){node*p,*q,*r,*s;p=(node*)malloc(sizeof(node));p->link=head;head=p;while(p->link!=null){q=p->link;r=p;while((1)){if(q->link->datalink->data)r=q;q=q->link;}if((2)){s=r->link;r->link=s->link;s->link=((3));(UI)-(15).);)p=head;head=head->link;free(p);return(head);)【复旦大学1999六(15分】10.下面的排序算法的思想是：第一趟比较将最小的元素放在r[l]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中,将次大的放在r[n-l]中…,依次下去，直到待排序列为递增序。(注：<->)代表两个变量的数据交换)。voidsort(SqList&r,intn){i二l；while((l)){min=max=l;for(j=i+l;(2)_;++j){if((3))min=j;elseif(r[j].key>r[max],key)max=j;}if((4))r[min]<>r[j];if(max!=n-i+l)｛if((5)_)r[min]<>r[n-i+l];else((6));｝i++；)｝//sort【南京理工大学2001三、2(10分】11.表插入排序的基本思想是在结点中设一指针字段，插入Ri时R1到Ri-1己经用指针按排序码不减次序链结起夹，这时采用顺序比较的方法找到Ri应插入的位置，做链表插入。如此反复，直到把Rn插入为止。(1)(6分)请完成下列表插人的算法;【山东工业大学2000五(16分】【山东大学1998五】①.RF01.LINK-(1)：RN.LINK-(2);②.循环，I以-1而反，从他―到④Z2S行

11(1)P-R[0].LINK;Q*-0(2)循环，当P>0且(5)吐，反复执行Q-P；P-(6)(3)R[Q].LINK*-I;RLI].LINK*-P(2)(2分)表插入排序的最大比较次数是d；(3)(2分)表插入排序的最小比较次数是或—；(4)(2分)记录移动的次数是®(5)(2分)需要附加的存储空间是710)；(6)(2分)该排序算法是否是稳定的(11)。12.设用希尔排序对数组｛98,36,-9,0,47,23,1,8,10,7｝进行排序，给出的步长(也称增量序列)依次是4,2,1则排序需_3趟，写出第一趟结束后，数组中数据的排列次序。【南京理工大学1997三、5(2分】13.从平均时间性能而言，快速—排序最佳。【青岛大学2001六、5(3分】14.对于7个元素的集合｛1,2,3,4,5,6,7｝进行快速排序，具有最小比较和交换次数的初始排列次序为—4261357_。【长沙铁道学院1997二、1(2分)】15.快速排序在的情况下最易发挥其长处。【长沙铁道学院1998二、5(2分)】类似本题的另外叙述有:(1)快速排序法在情况下最不利于发挥其长处，在情况下最易发挥其长处。【山东大学2001三、5(2分)】16.在数据表有序时，快速排序算法的时间复杂度是。【合肥工业大学2001三、10(2分】17.堆排序的算法时间复杂度为：。【合肥工业大学1999三、10(2分】18.PROCsift(VARr：listtype;k,m:integer);｛假设r[k+l..m]中各元素满足堆的性质，本算法调整r[k]使整个序列r[k..m]中各元素满足堆的性质。｝i:=k;j:=(1);x:=r[k].key;finished:=false;t:=r[k];

12WHILE(j<=m)ANDNOTfinishedDO[IF(jheap[j+l].key则⑶否则若⑷—则heapEi]-heap[j];(5);(6)跳出循环步3.［结束］heap［i］一⑺【山东工业大学1996三、2(7分】20.以下程序的功能是利用堆进行排序。请在空白处填上适当语句，使程序完整。PROCEDUREsift(VARr:arr;k,m:integer);VARi,j,x:integer;t:rec;finished:boolean;BEGINi：=k;(1);x:=r[i].key;(2)：t:=r[k];WHILE(j<=m)ANDNOTfinishedDOBEGINIF(j

13④16,31,23,94,53,72⑤94,31,53,23,16,72堆排序是一种(1)类型的排序,它的一个基本问题是如何建堆，常用的建堆算法是1964年Floyd提出的(2),对含有n个元素的序列进行排序时,堆排序的时间复杂度是(3),所需要的附加结点是(4)。【山东工业大学1994一、2(5分】20.堆是一种有用的数据结构.堆排序是一种(用排序,堆实质上是一棵结点的层次序列。对含有N个元素的序列进行排序时，堆排序的时间复杂度是⑶，所需的附加存储结点是(4)。关键码序列05,23,16,68,94,72,71,73是否满足堆的性质(5)。【山东工业大学1996三、1(5分】21.将如下的堆排序算法补写完整。说明如下：TYPEheaptype=ARRAY[l..n]0Finteger；过程heapsort的功能是将数组h中的前n个记录按关键字递减的次序排序。heapsort调用过程sift时的参数h,k,r有如下定义:以h[k+l],h[k+2],…，h[r]为根的子树已经是堆；执行sift后，以h[k],h[k+l],h[k+2],…,h[r]为根的子树都成为堆。PROCsift(VARh：heaptype；k,r：integer)；VARi,j,x：integer；finish：boolean；BEGINi:=k；x:=h[i]；j:=2*j；(0));WHILE(j<=r)ANDNOTfinishDO[IF(jh[j+U)THENj:=j+l;IFx>hLj]THEN[⑵]ELSEfinish:=true;(31]END;PROCheapsort(VARh:heaptype;n:integer);VARk,r,i,j:integer;BEGINFORk:=nDIV2DOWNTO1DOsift((4));FORr:=nDOWNTO2DO[x:=h[l];h[l]:=h[r];h[r]:=x;(⑸)]END;【北京工业大学1997五、2(16分)】22.设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按2路归并排序方法对该序列进行一趟扫描后的结果。【北方交通大学2001二、7]23.阅读下列程序说明和PASCAL程隹，把应填入其中处的字句写在答题纸上。程序说明：本题给出的是将数组a的元素a”a?,…,a0从大到小排序的子程序。子程序采用改进的选择排序方法，该方法基于以下思想：在选择第一大元过程中，ai与aj(j=n,nT,…,2)逐个比较，若发现aQa”则a”与小变换,变换后新的a“有性质a」12at(jl

14则它们都满足这一性质，它们的下标满足n^jl>j2>->jk>lo有了这些下标，在确定第二大元时，可只考虑a2与a,(j=jk,jk-1,-.3)逐个比较。倘若jk=2,则可不经比较就知道它是第二大元。在选择第二大元过程中，将与a2交换过的元素下标也标记下来，可供选择其他大元使用，但在选择第二大元时，应保证与a?交换的那些位置上的新值也都满足上述性质，依次类推，顺序选择第一，第二，…，第n-1大元，实现对a的排序。设程序包含有常量和类型定义：CONSTmaxn=1000;TYPEvector=ARRAY[l..maxn]OFinteger;index=1..maxn;PROCEDUREsort(VARa:vector;n:index)VARp:vector;i,j,k,m,t:integer;BEGINk:=0;i:=1;m:=n;WHILEia[i+l],将二者交换；以后重复上述二趟过程,直至整个数组有序。程序.(a)PROCEDUREoesort(VARa:ARRAY[1..n]OFinteger);VARflag:boolean;i,t:integer;BEGINREPEATflag:=false;FORi:=1TOnstep2DOIF(a[i]>a[i+l])THEN[flag:=(1)：t:=a[i+l];a[i+l]:=a[i];⑵]FORi:=(3)DOIF(a[i]>a[i+l])THEN[flag:=(4);t:=a[i+l];a[i+l]:=a[i];a[i]:=t;]UNTIL(5);END;程序(b)voidoesort(inta[n]){intflag,i,t;do{flag=0;

15for(i=l;ia[i+l]){flag^(l)：t=a[i+l];a[i+l]=a[i];(2)：}for(3).if(a[i]>a[i+U){flag=(4)：t=a[i+l];a[i+l]=a[i];a[i]=t;}}while(5)：}【上海大学2000一、1(10分】20.关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X),要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是;若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是o【北京大学1997一、4(4分】类似本题的另外叙述有:(1)设有字符序列Q、H、C、Y、P、A、M、S、R、D、F、X要求按字符升序排序,采用初始步长为4的希尔(shell)排序，一趟扫描的结果是—;采用以首元素为分界元素的快速排序，一趟扫描的结果是»【北京工业大学1999一、7(8分)】21.外部排序的基本方法是归并排序，但在之前必须先生成【北京邮电大学2001二、6(2分】22.磁盘排序过程主要是先生成,然后对合并，而提高排序速度很重要的是，我们将采用方法来提高排序速度。【山东工业大学1995一、4(4分】23.设输入的关键字满足kl>k2>…>kn,缓冲区大小为m,用置换-选择排序方法可产生一个初始归并段。【武汉大学2000一、9]24.下面是一改进了的快速排序算法，请填空并简要说明支持improveqsort递归所需要的最大栈空间用量。PROCEDUREimproveqsort(VARlist:afile;m,n:integer);{设listEm].key<=list[n+1].key}VARi,j,k:integer;BEGINWHILEm=k;REPEATj:=jTUNTILlist[j].key<-k;IFi=j;interchange(list[m],list[j]);IFn-j>=j-m

16THENBEGINimproveqsort(list,(1));(2)ENDELSEBEGINimproveqsort(list,(3));(4);ENDEND;{OFWHILE}END;【东南大学2001五(10分】四、应用题1.内部排序(名词解释)。【燕山大学1999一、5(2分】2.在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。【大连海事大学1996七、3(4分)】类似本题的另外叙述有:【西安电子科技大学1996三、4(5【燕山大学2001三、3(5分】【北京邮电大学1993二、3(6【东南大学1996一、5(6分】【东南大学1999一、5(5分】(1)举例说明堆排序是否为稳定排序法.分】(2)选择排序算法是否稳定？为什么？(3)举例分析堆排序方法是否稳定。分】(4)堆排序是稳定排序吗？举例说明。(5)试举例分析堆排序法是否稳定。(6)树型选择排序通常采用顺序存储结构，①试指出n个元素的原始序列般如何在该存储结构中存放(起始存储位置，次序)，请说明理由。②讨论树形选择排序的稳定性。若稳定，须说明理由；不稳定，须举反例，并尝试找出使它稳定的方法。【北京工业大学1999七(10分)】3.在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？【燕山大学2001三、4(5分】4.设有5个互不相同的元素a、b、c、d、e,能否通过7次比较就将其排好序？如果能，请列出其比较过程；如果不能，则说明原因。【北方交通大学1996五(10分】5.对一个由n个关键字不同的记录构成的序列，能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录？请说明如何实现？在最坏的情况下至少进行多少次比较？【东南大学2000一、5(8分】6.利用比较的方法进行排序，在最坏的情况下，能达到的最好时间复杂性是什么？请给出详细证明。【上海交通大学2000六(8分】7.以下概念的区别：拓扑排序与冒泡排序。【大连海事大学1996三、2(3)(2分)】8.简述直接插入排序，简单选择排序，2-路归并排序的基本思想以及在时间复杂度和排序稳定性上的差别。【西北工业大学1999二(8分)】9.快速排序，堆排序和希尔排序是时间性能较好的排序方法，也是稳定的排序方法。判断正误并改错。

17【燕山大学1998二、5(2分】1.设LS是一个线性表，LS=(al,a2,…,an),若采用顺序存储结构，则在等概率的前提下,插入一个元素需要平均移动的元素个数是多少？若元素插在ai与aitl之间(0<=i<=n-l)的概率为(n-i)/(n*(n+l)/2),则插入一个元素需要平均移动的元素个数又是多少？【西安电子科技大学2001软件二、3(5分】2.对于堆积排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？若仅考虑排序结果的稳定性，则应该选取其中哪种方法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？【北京航空航天大学1998一、10(4分】3.在堆排序、快速排序和合并排序中：【吉林大学2001—、5(6分)】(1).若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？(2).若只从排序结果的稳定性考虑，则应选取哪种排序方法？(3).若只从平均情况下排序最快考虑，则应选取哪种排序方法？(4).若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？13.快排序、堆排序、合并排序、Shell排序中哪种排序平均比较次数最少，哪种排序占用空间最多，哪几种排序算法是不稳定的？【首都经贸大学1997一、3(4分】14.欲求前k个最大元素，用什么分类方法好？为什么？什么是稳定分类？分别指出下列算法是否是稳定分类算法，或易于改成稳定分类算法？A.插入分类B.快速分类C.合并分类D.堆分类E.基数分类【东南大学1994一、3(8分】15.考虑由三个不同关键词构成的序列：{a,b,c},试画出直接插入排序算法的二叉判定树。【吉林大学2001—、3(4分)】16.请阅读下列算法，回答问题PROCEDUREsort(r,n)BEGINFORi:=2TOnDOBEGINx:=r(i)；r(0):=x；j:=i-l；WHILEx.key

18WHILE(i<=(1))AND(flag=(2))DOBEGINflag:=(3)—;FORj:=lTOmDOIFr[j].key>r[j+l].keyTHENBEGINflag:=(4);t:=r[j];r[j]:=r[j+l];r[j+l]:=tEND;i:=i+lEND;END.(1)请在上面横线上填上适当的语句，完成该算法程序。(2)设计标志flag的作用是什么？(3)该算法结点的最大比较次数和最大移动次数是多少？(4)该分类算法稳定吗？【上海海运学院1996六(12分)1999六(16分]13.仔细阅读下面的过程，并回答有关的问题PROCEDUREunknownname(VARA:array[1..500]OFinteger;n:integer);VARi,j,x:integer;b:boolean;BEGINb:=true;i:=1;WHILE(i

19[exchanged:=false;WHILEi<>pos[d]DO[IF(r[i]-r[i+d])*d>0THEN[r⑴与r[i+d]交换；exchanged:=true;];i:=i+d;]pos[d]:=pos[d]-d;i:=pos[d];d:=-d;]ENDP;【山东科技大学2002五(12分】13.设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最大。【南京航空航天大学1996九、1(4分】14.设与记录R1,R2,…，Rn对应的关键词分别是KI,K2,Kno如果存在Ri和Rj使得j

20（2）用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。（3）直接插入排序算法和直接选择排序算法的稳定性如何？【山东工业大学1997四（15分】26.在执行某个排序算法过程中，出现了排序关键字朝着最终排序序列相反的方向的移动，从而认为该算法是不稳定的。这种说法对么？为什么？【东北大学2001一、1（4分）】类似本题的另外叙述有:（1）（冒泡）排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。快速排序过程中有没有这种现象？【东北大学2000一、5（4分）】27.对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。（125,11,22,34,15,44,76,66,100,8,14,20,2,5,1）。【合肥工业大学1999四、4（5分】28.快速排序的最大递归深度是多少？最小递归深度是多少？【清华大学1999一、1（2分】29.已知某文件的记录关键字集为｛50,10,50,40,45,85,80）,选择一种从平均性能而言是最佳的排序方法进行排序，且说明其稳定性。【西安电子科技大学1996五（10分】30.在内排序算法中，待排序的数据已基本有序时，花费时间反而最多的排序方法是哪种？【西安电子科技大学2000计应用一、1（5分】31.我们知道，对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：【西安电子科技大学2001计应用五（12分）】【中国矿业大学2000六（10分】（1）当n=7时，在最好情况下需进行多少次比较？请说明理由。（2）当n=7时，给出一个最好情况的初始排序的实例。（3）当n=7时，在最坏情况下需进行多少次比较？请说明理由。（4）当n=7时，给出一个最坏情况的初始排序的实例。类似本题的另外叙述有:（1）快速排序（quicksorting）的效率与原始序列有关，现用快速排序算法对关键字分别为1—15的15个元素进行排序①在最好情况下要进行几遍比较，给出一种原始序列实例；②在最坏情况下要进行几遍比较，给出一种原始序列实例。【浙江大学1995七七2分分（2）对N个元素组成的线性表进行快速排序时，所需进行的比较次数依赖于这N个元素的初始排列。对N=7,给出快速排序的一个最好情况的初始排列实例（7个元素可取自集合｛1,2,3,4,5,6,7））o【西北大学2000二、5（5分）】32.有一随机数组(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

21第二趟：13,20,21,25,35,27,46,68,84第三趟：13,20,21,25,27,35,46,68,8426.快速排序是在所有情况下，排序速度最快吗？为什么？在何种情况下使用此排序法最好？【北京邮电大学1993一、1(5分】27.对给定文件(28,07,39,10,65,14,61,17,50,21)选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。【厦门大学1998七、1(8分)】类似本题的另外叙述有:(1)对下列关键字序列进行快速排序(从小至大)(48,38,65,95,73,13,27,50)要求给出快速排序的算法思想,并画出排序过程示意图。【南京航空航天大学1999五(10分】(2)设记录的关键字集合K={23,9,39,5,68,12,62,48,33},给定的增量序列口={4,2,1),请写出对K按“SHELL方法”排序时各趟排序结束时的结果；若每次以表的第一元素为基准(或枢轴)，写出对K按“快速排序方法”排序时，各趟排序结束时的结果。【北京科技大学1999七(10分)2000七(10分】28.下面是一改进了的快速分类算法1.PROCEDUREqsort1(VARlist:afile;m,n:integer);2(设key〈list[n+l].key)3VARi,j,k:integer;4BEGIN5WHILEm=k;10REPEATj:=j-lUNTILlist[j].key<=k;11IFi=j;13interchange(list[m],list[j]);14IFn-j>=j-m15THENBEGINqsort1(1ist,m,j+1);m:=j+l;END16ELSEBEGINqsortl(list,j+1,n);n:=j-l;END17END;(OFWHILE)18END.问：(1)将第9、10行中的>=,V=分别改成>，V行吗？为什么？(5分)(2)该排序算法稳定否？举例说明(5分)

22(3)对输入文件(22,3,30,4,60,11,58,18,40,16),列表表示该文件在每次调用qsortl时的状态及相应m、n值。(5分)(4)若输入文件有n个记录，简要说明支持qsortl递归所需最大栈空间用量(设一层递归用一个单位栈空间)。(5分)【东南大学1998四(20分】26.如果只要找出一个具有n个元素的集合的第k(IWkWn)个最小元素，你所学过的排序方法中哪种最适合？给出实现的思想。【北方交通大学1998六(10分】27.已知快速排序和归并排序的算法分别如下所示：PROCEDUREqksort(VARr:listtype;s,t:integer);BEGINIFs

23类似本题的另外叙述有:(1)判别以下序列是否是堆(大顶堆)，如果不是，则把它调整为堆。(12,70,33,65,24,56,48,92,86,33)【燕山大学2001四、1(8分】(2)判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。①100,90,80,60,85,75,20,25,10,70,65,50②100,70,50,20,90,75,60,25,10,85,65,80【复旦大学1997二(8分】(3)判别下列两个序列是否为堆，若不是，按照对序列建堆的思想把它调整为堆，用图表示建堆的过程。【厦门大学2001二、1(24%/3分)】①(1,5,7,20,18,8,8,40)②(18,9,5,8,4,17,21,6)(4)根据给定的关键字集合(20,15,40,35,45,25,50,30,10)顺序输入①构造一棵完全二叉树；②画出整理好的一棵堆树；③画出一棵输出一个排序记录后的二叉树；④画出重新调整好的堆树。【大连海事大学2001六(5分)】40.全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为什么？【北京邮电大学1996一、3(4分】类似本题的另外叙述有:(1)如果在1000000个记录中找出2个最小的记录，你认为采用什么样的排序方法所需的关键字比较次数最少？共计多少次？【厦门大学1999三、4)41.已知待排序的序列为(503,87,512,61,908,170,897,275,653,462),试完成下列各题。(1)根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。(2)输出最小值后，如何得到次小值。(并画出相应结果图)【同济大学2001二(10分)】类似本题的另外叙述有:(1)对于输入关键字序列48,70,65,33,24,56,12,92进行：①建立堆排序的初始堆(小顶堆)，要求画出主要过程。②建一棵平衡二叉树，画出过程(至少每次调整有一张，标出最小不平衡子树的根)o【北京工业大学2001二、5(6分)】(2)简要叙述堆排序的算法思想。并对如下关键字序列(3,8,85,12,37,50)按堆排序算法进行从小到大排序，要求画出排序全过程的示意图。【南京航空航天大学1997五(10分】(3)设记录关键字集合K={28,17,85,96,75,8,42,65,04)①写出对K进行“二路归并”且按关键字递增次序排序时，各趟排序的结果；②如何将K建成一个完全二叉树形式的最小堆；【北京科技大学1997七(10分】42.设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序歹IJ,其中n»k,最好采用什么排序方法？为什么？如果有这样一个序列{59,11,26,34,17,91,25},得到的部分序列是：{11,17,25},对于该例使用所选择的方法实现时，共执行多少次比较？【东北大学2002一、4(3分)】

24类似本题的另外叙述有:(1)如果只想得到一个序列中第K个最小元素之前的部分排序序列，那么最好应采用哪种排序算法？为什么？如由这样一个序列：57,40,38,11,13,34,48,75,25,6,19,9,7得到其第四个最小元素之前的部分排序序列：6,7,9,11,…用你选用算法实现时，共执行多少次比较？【北方交通大学1994七(16分】40.写出用堆排序算法对文件F=(12,3,15,30,9,28)进行排序时，初始堆及以后每挑好一个元素重新调整后堆的状态，并指出这里的堆和败者树的一个主要区别。【东南大学1998二(8分】41.请回答下列关于堆(Heap)的一些问题：【清华大学2000五(12分】(1)(4分)堆的存储表示是顺序的，还是链接的？(2)(4分)设有一个最小堆，即堆中任意结点的关键码均大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？(3)(4分)对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大0表示法)？42.解答问题(1)(6分)设某文件中待排序记录的排序码为72,73,71,23,94,16,05,68,试画图表示出树形选择排序(增序)过程的前三步。(2)(4分)试说明树形选择排序的基本思想。(3)(2分)树形选择排序与直接选择排序相比较，优缺点是什么？(4)(3分)堆排序是如何改进树形排序方法的？优点是什么？【山东大学1999五(15分】【山东工业大学1999五(15分】43.若有N个元素已构成一个小根堆，那么如果增加一个元素为K„h,请用文字简要说明你如何在log2n的时间内将其重新调整为一个堆？【中科院计算所1999三、2(5分)】44.填空并回答相关问题(1)下面是将任意序列调整为最大堆(MAXHEAP)的算法，请将空白部分填上：将任意序列调整为最大堆通过不断调用adjust函数，即：F0R(i=n/2；i>0；i--)adjust(list,i,n)；舜list为待调整序列所在数组(从下标1璐)，n为序列元素个数，adjust函数为：voidadjust(intlist口，introot,intn)/*将以root为下标的对应元素作为待调整堆的根，待调整元素放在list数组中，最大元素下标为n*/{intchild,rootkey;rootkey=list[root];child=2*root;while(child〈=n){if((child

25else(List[(2)child*=2;]=list[child];list[child/2]=rootkey;)(2).判断下列序列能否构成最大堆:(12,70,33,65,24,56,48,92,86,33)；若不能按上述算法将其调整为堆，调整后的结果为：()o1浙江大学1998七(11分)】48.回答问题：(1)设待排序的结点个数是n。试问堆排序算法在完成一次sift建堆，并且取走找到的最小关键码后，是否还需要对于n-1个关键码从头开始建堆？为什么？(2)假定采用sift建堆算法。试问堆排序算法采用了怎样的节省存储空间的措施？堆排序完成后，heap中保存了关键码值的升序排列还是降序排列？【山东工业大学1996三、3(8分】49.够关键字排序时,LSD和MSD两种方法的特点是什么？【北京邮电大学2001三、3(5分】50.内排序的过程中，通常需要对待排序的关键字集合进行多遍扫描。采用不同排序方法，会产生不同的中间结果。设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键字按字母序的升序重新排列，请分别给出对该序列进行冒泡排序，初始步长为4的希尔排序，二路归并排序及以第一个元素为分界元素的快速排序的第一趟扫描的结果，并给出对该序列作堆排序时初始建堆的结果。【长沙铁道学院1998四、5(6分)】51.给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列；(1)希尔排序(第一趟排序的增量为5)(2)快速排序(选第一个记录为枢轴(分隔))(3)链式基数排序(基数为10)【上海交通大学1999八(9分】52.给出一组关键字：29,18,25,47,58,12,51,10,分别写出按下列各种排序方法进行排序时的变化过程：【南开大学1998八(12分)】(1)归并排序每归并一次书写一个次序。(2)快速排序每划分一次书写一个次序。(3)堆排序先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。类似本题的另外叙述有:(1)对关键字/权值序列{9,4,3,8,10,7,6,5}①设序列是初始归并段的长度，画出最佳归并树，并计算其对应归并排序的I/O次数(假设每次I/O读写一个记录)。②设序列是关键字输入次序，画出得到的二叉排序树。③画出构造初始小根堆的过程。④画出快速排序第一趟的过程。⑤画出步长为2的一趟希尔排序结果。【华南师范大学2000二(20分)】53.(1)判定起泡排序的结束条件是什么？(2)请简单叙述希尔排序的基本思想。

26（3）将下列序列调整成堆（堆顶为最小值）12345678910712fTo^33^65[^4[^6^8^92^80|13（4）在16个关键字中选出最小的关键字至少要多少次比较？再选出次小的关键字至少要多少次比较？请简要说明选择的方法和过程。【燕山大学1999九（14分】54.给出如下关键字序列321,156,57,46,28,7,331,33,34,63试按链式基数排序方法，列出一趟分配和收集的过程。【北京轻工业学院1999九（10分】类似本题的另外叙述有:（1）已知整数数组a的10个元素为326,129,167,588,212,95,980,725,443,601,用以下排序方法进行由小到大排序。【西南交通大学2000二、6]①用基数排序算法时，试写出第一次分配和收集后数组a中的结果。②用堆排序时，试写出将第一个选出的数据放在数组a的最后位置上，将a调整为堆之后的a中的结果。55.请写出应填入下列叙述中（）内的正确答案。【上海大学2002一（8分）】排序有各种方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如下：15,13,20,18,12,60o下面是一组由不同排序方法进行一遍排序后的结果。()排序的结果为：12,13,15,18,20,60()排序的结果为：13,15,18,12,20,60()排序的结果为：13,15,20,18,12,60()排序的结果为：12,13,20,18,15,60no

27yesnoyes注：a是整数数组，存放要排序的数组集合，n是a的长度，p,i,j,k,m,t是临时变量，p为整型数组，为整型变量。本题给出的是将数组a的元素al,a2,…,an从大到小排序的子程序的框图，如上图，填空完善此算法框图。该子程序采用改进的选择排序方法，该方法基于以下思想：在选择第一大元过程中：al与aj(j=n,nT,…,2)逐个比较，若发现ajl〉al,则ajl与al交换，交换后新的ajl有性质ajl>=at(jlai(j2=at(j2=0)个，依次为ajl,aj2,…,ajk,则它们都满足这一性质。它们的下标满足n>=jl>j2>->jk>lo有了这些下标，在确定第二大元时，可只考虑a2与aj(j=jk,jk-b3)逐一比较。倘若jk=2,则可不经比较就知道a2就是第二大元。在选择第二大元的过程中，将与a2交换过的元素下标也记录下来，可供选择其他大元使用。但在选择第二大元时，应保证与a2交换的那些位置上的新值也都满足上述性质。依次类推，顺序选择第一，第二，…，第n-1大元，实现对a的排序。【哈尔滨工业大学1999六(14分)】57.给定一个关键字序列序4,19,32,43,38,6,13,22},请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？【西安电子科技大学1999五(10分】58.奇偶交换排序如下所述：对于初始序列A[l],A[2],…,A[n],第一趟对所有奇数i(l<=i〈n),将A[i]和A[i+1]进行比较，若A[i]>A[i+l],则将两者交换；第二趟对所有偶数i(2<=i

28(2)设有12个初始归并段，其长度分别为8,6,30,44,62,18,85,68,9,60,3,20；试画出表示归并过程的最佳归并树，并计算树的WPLo【厦门大学1998七、2(8分】(3)现有12个初始归并段，其记录数分别为：{30,44,8,6,3,20,60,18,9,62,68,85},现用3路平衡归并，画出最佳归并树。【北京邮电大学2002二、1(5分】(4)设有13个初始归并段，其长度分别为28,16,37,42,5,9,13,14,20,17,30,12,18.试画出4路归并时的最佳归并树，并计算它的带权路径长度WPL。【清华大学1998九(10分】62.已知有31个长度不等的初始归并段，其中8段长度为2；8段长度为3；7段长度为5；5段长度为12：3段长度为20(单位均为物理块)，请为此设计一个最佳5-路归并方案，并计算总的(归并所需的)读/写外存的次数。【清华大学1994四(10分】类似本题的另外叙述有:(1)已知在进行置换-选择排序时得到14个有序段，其长度分别为2,3,4,5,6,7,8,9,11,13,17,20,21,23；现进行4路平衡归并，要求给出所对应的最佳归并树和总的读/写次数。【中科院计算所2000二(10分】(2)已知某文件经过置换-选择排序后，得到长度分别为47,9,31,18,4,12,23,7的8个初始归并段。试为3路平衡归并设计读写外存次数最少的归并方案，并求出读写外存的次数。【东南大学2000一、6(8分】(3)置换选择排序得到初始归并段长(k字节数)为37,34,300,41,70,120,35,43作图表示出这些磁盘文件进行归并所用的4阶最佳归并树，算出归并的总读写字节数，每读写1字节计为1。【北京工业大学1999六(8分)】63.以归并算法为例，比较内排序和外排序的不同，说明外排序如何提高操作效率。【华南师范大学1999四（10分）】64.对输入文件（101,51,19,61,3,71,31,17,19,100,55,20,9,30,50,6,90）；当k=6时，使用置换-选择算法，写出建立的初始败者树及生成的初始归并段。【北方交通大学1999四（12分】类似本题的另外叙述有:（1）给出一组关键字T=（12,2,16,30,8,28,4,10,20,6,18）,设内存工作区可容纳4个记录，写出用置换-选择排序得到的全部初始归并段。【上海交通大学1999十】（2）用置换-选择排序法产生文件F（长度为n）的初始归并段（设内存缓冲区的长度为m）,①平均情况下，初始归并段的长度为多少？为什么？②初始归并段的长度最长与最短时，其长度分别为多少？在何种情况下出现？简单解释一下。【上海交通大学2000九（8分】65.设有N个记录的一个文件，经内部排序后得到650个初始归并段。（1）试问在四台磁带机上分别用平衡归并和多步归并进行外部排序各需要多少趟归并？（2）给出多步归并排序前五趟归并的情况。（10分）【北方交通大学1997六（16分］类似本题的另外叙述有:（1）已知有8个初始归并段，其长度分别为10,20,25,30,45,12,16,2,现用TO,Tl,T2三条磁带进行二路多步归并排序，写出每遍归并后各归并段的分布，并给出初始归并段在磁带上的最佳初始分布。【西北工业大学1998二、1（10分）】66.写出或画出下面两题的结果：【北京邮电大学1997四（10分】（1）归并段长度分别为9,4,7,3,8,6,15,试画出3路平衡最佳归并树。（2）有二叉树中序序列为：ABCEFGHD;后序序列为：ABFHGEDC.请画出此二叉树。类似本题的另外叙述有:（1）设有11个长度（即包含记录的个数）不同的初始归并段，它们所包含的记录个数分别为25,40,16,38,77,64,53,88,9,48,98。试根据它们做4路平衡归并，要求：（1）指出总的归并趟数；（3分）（2）构造最佳归并树；（8分）

29（3）根据最佳归并树计算每一趟及总的读记录数。（5分）【清华大学1997八（16分】62.外排序中为何采用k-路（k>2）合并而不用2-路合并？这种技术用于内排序有意义吗？为什么？【东南大学1995三（8分】63.给定输入文件：101,48,19,65,3,74,33,17,21,20,99,53,21,并设记录缓冲区个数k=4,写出基于败者树的外排序顺串生成算法runs输出的顺串。【东南大学1996一、6（6分】五、算法设计题：1.冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。【吉林大学2001二、3（9分】类似本题的另外叙述有:（1）编写一个双向气泡排序的算法，即相邻两遍向相反方向起泡。【北京邮电大学1992六（10分）】2.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）【北京邮电大学1997七（15分）】I八匕"I二对回II=~~3.请编写直接插入排序算法。TYPErcdtype=RECORDkey:integer;otheritem:anytype：END;1isttype=ARRAY[0..n]OFrcdtype;【北京轻工业学院1998七（10分】4.（此题单考生做）用类PASCAL语言（或PASCAL语言）完成下列各题：设单链表头结点指针为L,结点数据值为整型，试写出对链表L按“插入方法”排序的算法：LINSORT（L）o【北京科技大学1999十、1（10分）2000十、1（10分】5.输入50个学生的记录（每个学生的记录包括学号和成绩），组成记录数组，然后按成绩由高到低的次序输出（每行10个记录）。排序方法采用选择排序。【北京师范大学1999五】6.有一种简单的排序算法，叫做计数排序（countsorting）0这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c,那么，这个记录在新的有序表中的合适的存放位置即为Co（1）（3分）给出适用于计数排序的数据表定义；（2）（7分）使用Pascal或C语言编写实现计数排序的算法；（3）（4分）对于有n个记录的表，关键码比较次数是多少？（4）（3分）与简单选择排序相比较，这种方法是否更好?为什么？【清华大学2000三（17分】类似本题的另外叙述有:结点类型和存储方式如下：（l）TYPEnode=RECORDkey:integer;info:datatype;count:integerEND;VARr:ARRAY[l..n]OFnode;请给出一个排序方法，不移动结点存储位置，只在结点的count字段记录结点在排序中的序号(设排序码最大的结点序号为1)。【国防科技大学1999七)7.快速分类算法中，如何选取一个界值(又称为轴元素)，影响着快速分类的效率，而且界值也并不一定是被分类序列中的一个元素。例如，我们可以用被分类序列中所有元素

30的平均值作为界值。编写算法实现以平均值为界值的快速分类方法。【石油大学1998五(18分)】7.写出一趟快速排序算法。【山东师范大学2000二、4(10分)2001二、5(10分)】类似本题的另外叙述有:(1)某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。请改写快速排序算法，对这个字符串序列进行排序。【西安电子科技大学2000计应用七(11分)】(2)若待排序列用单链表存储，试给出其快速排序算法。【北京邮电大学2000七(15分】8.设有一个数组中存放了一个无序的关键序列KI、K2、…、Kno现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。(注：用程序实现)【南京航空航天大学1997六(12分】9.借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“notfind”信息。请编写出算法并简要说明算法思想。【北京邮电大学1998七(15分】10.已知关键字序列(KI,K2,K3,…，Kn-1)是大根堆。(1)试写出一算法将(KI,K2,K3,…，Kn-1,Kn)调整为大根堆；(2)利用(1)的算法写一个建大根堆的算法。【中科院软件所1999七、2(7分】类似本题的另外叙述有:(1)设文件(RI,R2,…，Rn)是一个堆，Rn+1是任意一个节点，试设计一个算法，该算法把Rn+1添加到堆中，并使添加后形成的文件仍是一个堆，要求算法的时间复杂性为O(logzn)。【吉林大学1999二、2(8分)】11.辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设用K[l],K[2],…，K[N]表示N个结点的值，用…，T[N]表示辅助地址表.初始时T[i]:=i,在排序中，凡需对结点交换就用它的地址来进行。例如当N=3时，对K(31,11,19)则有T(2,3,l)o试编写实现辅助地址表排序(按非递减序)算法的语句序列。【重庆大学2000四、2】12.关于堆排序方法，完成如下工作：(1)简述该方法的基本思想。(2)写出堆排序算法。(3)分析该算法的时间复杂度。【西南财经大学1999五】类似本题的另外叙述有:(DN个元素的序列满足什么条件才能称之为堆？用类PASCAL语言写出堆排序和算法。【南开大学1997七(15分)】13.设待排序的文件用单链表作存储结构，其形式如下：TYPEpointer=tnode;node=RECORDkey:integer;next:pointer;END;写出以head为头指针的选择排序算法。【中山大学1999二(10分】14.非递归的快速排序算法。【中科院软件所1997三(10分)】15.一最小最大堆(minmaxheap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆；

31minlevelmaxlevelminlevelmaxlevel(1)画出在上图中插入关键字为5的结点后的最小最大堆。(2)画出在上图中插入关键字为80的结点后的最小最大堆；(3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。(4)用C或PASCA；实现上述算法。【浙江大学1996八(26分)】7.二路插入排序是将待排关键字序列r[l..n]中关键字分二路分别按序插入到辅助向量d[l..n]前半部和后半部(注：向量d可视为循环表)，其原则为，先将赋给d[l],再从r[2]记录开始分二路插入。编写实现二路插入排序算法。【北京工业大学1998八(10分)】8.叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179,208,93,306,55,859,984,9,271,33)【南京航空航天大学2000一]9.输入N个只含一位数字的整数，试用基数排序的方法，对这N个数排序。【中国人民大学2001三、1(10分)】10.设记录R[i]的关键字为R[i].KEY(K=i<=k),梯点T[i](l<=i<=K-l)指向败者记录，T[0]为全胜记录下标。写一算法产生对应上述R[i](l<=i<=k)的败者树，要求除和T[0..k-1]以外，只用0(1)辅助空间。【东南大学1995九(15分】11.设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红，白，蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。【上海大学1999二2(18分】12.数据结构DEAP的定义如下：DEAP是一棵完全二叉树，它或者是一棵空树，或者满足下列特性：

32(1)树根不包含元素.(2)其左子树是一小堆(MINHEAP),其右子树是一大堆(MAXHEAP).(3)若右子树非空，设i是左子树的任一结点，j是右子树中与i相应的结点.若这样的j结点不存在，则取j为右子树中与i的父结点相应的结点；结点i的关键字总是小于或等于结点j的关键字值。一个DEAP的例子如右图所示，厂、与结点15相对应的结点为20,与结点19对应的结点为25.(1)给出在该DEAP中插入结点4后的结果.哭(2)写出在DEAP中插入新结点的算法.O@@(4015)(19)(9)(30【浙江大学1997(20分】(3)用C或PASCAL语言编写实现上述算法的程序.(20分)