数据结构-考研复习题第10章排序

10 )。【理工大学1997一、10（2分 C．平均时间为0（nlogn）的排序方 )排序法是不稳定性排序法【航空航天大学一、10（2A.插 B.冒 C.二路归 D.堆 ）是稳定的。【福州大学1998一、3(2分) B.快速排序，堆排C.直接选择排序，归并排 D.归并排序，冒泡排 【北方交通大学2000二、3（2分】 D．树形选择排序和s排序 ）【北方交通大学2001一、8（2 6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序B．归并排序C．冒泡排序【邮电大学2001一、5（2分则称该排序算法是不稳定的（）就是不稳定的排序方法【1998一、3(2起泡排序B．归并排序C．S排序D．直接插入排序E．简单选若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）直接插入B．直接选择C．堆D．快速E．基数【计算所2000一若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（A.B.堆排序C.归并排序D.【中国科技大学1998二、4（2分】【计算所1998二、4（2分 ）【工业大学1999一、2(2分)A.起泡排序B.折半插入排序 E.基数排序F.堆下列内部排序算法中：【工业大学2000一、1(10分每问2分)快速排 B.直接插入排序C.二路归并排 D.简单选择排序E.起泡排F. 在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<<n）的情况下 )排序法【航空航天大学插 B.选 C.冒 D.快 B.插入排序法 C.快速排序法 D.堆积排序法【航空航天大学2000一、10（2分 B.二分法插入 C.快速排序 D.归并排序【理工大学2000一、7（1.5分在下列排序算法中,哪一个算法的时间复杂度与初始排序无关 【理工大（2 气泡排 C.快速排 D.直接选择排 )【北方交通大学2000二、（2 A．选择排 19993（2 A.快速排 B.冒泡排 C.选择排 D.插入排20003（2（1）84472515（2）15472584（3）1521258447（4）152147) 【理工大1997一、2（2A.B.C.快 D.插对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，- ）排序【理工大学1998一、8（2分A.选 B.快 C.希 D.冒 选 B. C.直接插 D.冒泡【理工大学1998一、（2 A.快速排序B.s排序C.堆排 D.冒泡排序【合肥工业大学2001一 A.选 B.冒 C.归 D.【理工大学2001一、7（1.5分【哈尔滨工业大学2001二、4（2分 ）是执行第一趟快速排序后所得的序列。【福州大学1998一 (2 B. C. D. 据的排序为( )（按递增序。【理工大学1996一、4（2分】A．下面的B，C，D都不对。 D.9，4，7，8，7，-（46，79，56，38，40，84， 。【燕山大学2001一、4（2分】 B. D. )【理工大学1999一、（1 B.堆排 C.选择排 D.归并排 B.希尔C.快速D. 【理工大学2001一、12（1.5分 A.直接插入排 B.快速排 A.堆排 B.快速排 C.插入排 D.归并排序【大学一、5 )排序法【西安电子科技大学一、9(2A.冒 希尔插 交换D.快如果只想得到1000个元素组成的序列中第5个最小元前的部分排序的序列， 起泡排 B．快速排列C．S排 【1998一、2（2分 )最好?为什么?【山东工业大学1995二、4（3分】A．快速排序B．堆排序C．归并排序D．基数排序E．S排数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( A.堆排序B.希尔排序C.快速排序D.直接选择排序【理工大学2000一、（2排序方法中采用哪一种最好？( 【东学1999一、5 (3分)】A.快速排 B.归并排 C.堆排 E.s排 B．冒泡排序C．简单选择排序【山东工业大学19951（2 A.直接插入排序B.冒泡排序C.简单选择排序D.快速排序【山东大学20012(1 。【大20006 B.选择排 C.快速排 D.归并排（ 都不在其最终的位置上【大学2000 一、4】【西学2001二、1】A.堆排 B.冒泡排 C.快速排 D.插入排 )【厦门大学2002五2（8分A.归并排 B.快速排 C.希尔排 D.堆排 )排序法【航空航天大学1999一、（2A.插 B.选 C.希 D.二路归 【中山大学1999一、11】A.选 B.冒 C.插 D.用直接插入排序方法对下面四个序列进行排序（由小到大，元素比较次数最少的是 B．C． D．【北方交通大学200115（2 【邮电大学1999一、5（2 B． C． D．若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ A. B. C. D. 【理工大学1999一、分 ）【工商大学2001一、4（3分】A. B. C. D. )【理工大学2000一、（1.5A.（n,O(logn) B. C. D.对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是( )【理工大学1999一、15（1分】A. B. C. D. C．{21,9,17,30,25,23,5}{5,9,17,21,23,25,302001（2 (2,5,12,16)26(60,32,72)B.C.(2,16,12,5)28(60,32,72)D.(5,16,2,12)28(32,60,72)【青岛大学2000三、（2对n（每次分区后，先处理较短的部分B．5（2nn6)，当用递归算法求n!时，算法的时间复杂度是(7)，则：(6)-(7)=（【理工大学1999（6-7（4】A.O(n)B.O(nlogn)C.O(n*n)D.快速排序在情况下的时间复杂度是(),比()的性能差。A．O(NlogN)B．O(N2)C．O(N3)DE．F．选择排序19952（4 ）情况下最不利于发挥其长处。【燕山大学2001一、3（2 B.要排序的数据中含有多个相同C.要排序的数据个数为奇 D.要排序的数据已基本有在含有n个关键字的小根（堆顶元素最小中关键字最大的记录有可能（ n/2B．n/2-1C．1 【计算所一、（2 )【西安电子科技大学2001应用一、5（2分 。【工商大学2001一、8（3分 B.C. D. A.插 B.交 C.归 D.基 E.选F.O（n2）和 G.O（nlog2n）和H.O（nlog2n）和 I.O（n2）和 【西学2001二、2在对n个元素的序列进行排序时，堆排序所需要的附加空间是 A.O(log2n)B.O(1)C. DO(nlog2n)2001对n个记录的文件进行堆排序，情况下的执行时间是多少 174 B．-C．-1，4，7，8，20，15，7，9D．A，B，C均不对。【理工大学1996二 )【理工大学2000一、19（1.5分 。【中山大学 B. C.O（N*LOG（N） D.O（LOG（N 插入排序B．枚举排序C．选择排序D．交换排【邮电大学2000二6就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（ A．堆排序〈快速排序〈归并排序 B．堆排序〈归并排序〈快速排序C．堆排序〉归并排序〉快速排序 D．堆排序>快速排序>归并排序 【西安交通大学1996三、1(3分)（1）（2）素，并将其依次放入已排序序列（初始时为空）（3）（5）是完全二叉树结构的一个重要应用。【北方交通大学1999一、3（5】（1）--（5）:A．选择排序B．快速排序C．插入排序D．起泡排序E．归并排序F．s排序G．堆排序H．基数排序（1）排序的方法有很多种（）法从未排序的序列中依次取出元素与已排序序列中的（）法从未排序序列中挑选元素，并将两元素逆序时，进行交换（）和（）是基于这类方法的两种排序方法，而()是比()效率更高的方法。供选择的答案：A.B.C.D．冒泡排序E．直接1998三、2(52000三、2（7设要将序列（q,h,c,y,p,a,m,s,r,d,f,x）（1）（）是初始步长为4的s排序一趟扫描的结果；（2）（）是对排序初（3）（）20003（16%/3f,h,c,d,p,a,m,q,r,s,y,xp,a,c,s,q,d,f,x,r,h,mC.a,d,c,r,f,q,m,s,y,p,h,xh,c,q,p,a,m,s,r,d,f,xh,q,c,y,a,p,m,s,d,r,f母序的升序排列，则(1)是冒泡排序一趟扫描的结果,(24(S)排序一趟扫描的结果,(3)是合并排序一趟扫描的结果,(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.D.h,c,q,p,a,m,s,r,d,f,x,yE.n是:二路归并排序为(1),直接插入排序为(2),快速排序为(3),其中,归并排序和快速排序所需要的辅助分别是(4)和(5)。【海运学院1998二4（51-5:A.O(1)B.O（nlog2n）C.O（n）D.O（n2）E.O（n(log2n)2）F. A．NB．2N- C．2ND．N-【计算所1998二、7（2分】【中国科技大学1998二、7（2分基于比较方法的n个数据的内部排序。情况下的时间复杂度能达到的最好下界（A.O(nlogn)B.O(logn)C.O(n)D.O(n*n)【理工大学1996一、2（2时间下界应为（A.O(nlog2n)B.O(nlog2k)C.O(klog2n)D.O(klog2k)19989（2间下界应为()A.O(klog2k)B.O(klog2n)C.O(nlog2k)D.O(nlog2n)【计算所1998二、（2kk（有关B．无关【工业大学2000一、2(3分)K（包括访外）K（ B．无关【工业大学2001一、4(2分)】 ）【长沙铁道学院1998一、10(1分)】内排序要求数据一定要以顺序方式。 8（1 【航空航天大学1996六、9（1分 ）【交通大学1998一、18】（N两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（）【交通大199815在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。 20009（1 【理工大学1997二 【交通大学1998一、16 【邮电大学1998一、7（2分 ）【航空航天大学1997一、6（1分 ）【航空航天大学1996六、6（1分14（1018846703439455866101（2 200010（1 ）【交通大学1998一、19O（1 ）【青岛大学2000四、9（1分在分配排序时，最优先分配法比最低位优先分配法简单。 ）【交通大199820冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的时间复杂性是O(n*n),而快速排序算法的时间复杂性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。（）【海运学院1997一、9（1分，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的时间复杂性（nlog2n序效率更高。（）【海运学院1998一、10（1分【海运学院1995一、10（1分快速排序和归并排序在情况下的比较次数都是O(nlog2n)。 【海运学院1996一、9（1分 ）【邮电大学2000一、（1 ）【邮电大学2002一 ）【东南大学2001一、9（1分 1994一、4（2取决于内部排序的时间。 )【邮电大学1998一、8（2分在外部排序时，利用选择树方法在能容纳m个记录的内存缓冲区中产生的初始归并段的平均长度为2m个记录。( )【海运学院1999一、10（1分】为提高在外排序过程中，对长度为N的初始序列进行“置换—选择”排序时，可以得到的最大初始有序段的长度不超过N/2。( I/O2001201 【东学1997二5(2 【邮电大学2001二、7（4分 。【西安电子科技大学1999软件一、（2 【青岛大学2002三、5（2分 算法【福州大学1998二、10(2分)】排序方法对其进行排序（按递增顺序20015（14%/5）

排序最省时间，O(N2)的排序算法是，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是【大学2001一、3（2）】 【理工大学2001二、8（2分 【华中理工大学200010（1datanext；链表首head，链表无头结点。while {q=p; {if((4) }tmp=q->data;q->data=p->data;p->data=tmp;p= }【理工大学2000三、2（6分chead从小到大。请在空框处填上适当内容,每个空框只填一个语句或一个表达式#includetypedefstructnode{chardata;structnode*link;}node;node*select(node*head){nodep=(node*)malloc(sizeof(node));p->link=head;head=p;{q=p->link;r=p;while {if(q->link->data<r->link->data)r=q;}if((2) ){s=r->link;r->link=s->link;s->link=((3) );((4) );}p=head;head=head->link;(p);1999（15r[1]voidsort(SqList&r,intn){while((1)) for )min=j;else max=j; )r[min] if(max!=n-i+1){if((5) )r[min]<---->r[n-i+1];else((6));}}}//sort【理工大学2001三、2（10分RiRlRi-1Rn（1）(62000五（161998 ; ②，I1(3)到(4)（1）P←R[0].LINK;Q←P>0(5)Q←P； （2）(2(7)（3（2（4（2（5（2（6（2 称增量序列）依次是4，2，1则排序需 【理工大学1997三、5（2分 排序最佳【青岛大学2001六、5（3分的初始排列次序 【长沙铁道学院1997二、 (2分) 的情况下最易发挥其长处【长沙铁道学院1998二、 (2分) 情况下最易发挥其长处2001三、5(2 【合肥工业大学2001三、10（2 【合肥工业大学1999三、10（2分PROCsift(VARi:=k;j:=(1);x:=r[k].key;finished:=false;WHILE(j<=m)ANDNOTfinishedDO[IF(j<m)AND((2))THENj:=j+1;IFx<=r[j].keyTHENELSE[r[i]:= i:=j;j:= ENDP;{sift}19982（15设n，datatypeTYPEnode=RECORDkey：integer；info：datatypeEND； heap：ARRAY[1..n]OFnodel，r，i，j：0..n i←l;j←(1);步2．[过筛]循环：当 ⑴．若j<r且heap[j].key>heap[j+1].key则 ⑵．若(4)则heap[i]←heap[j];(5) ;(6) 步3.[结束]heap[i] 【山东工业大学19962（7PROCEDUREsift(VARr:arr;k,m:integer);VARi,j,x:integer;t:rec;finished:boolean;i:=k;(1) ;x:=r[i].key;(2) WHILE(j<=m)ANDNOTfinishedBEGINIF(j<m)AND THENIFx<=r[j].keyTHENELSE ; ; PROCEDUREheapsort(VARr:arr);VARi:integer;x:rec;BEGINFORi:=nDIV2DOWNTO1 DO(8) FORi:=nDOWNTO2DOBEGINx:=r[1]; ;r[i]:=x; 2000（20 堆排序是一种_(1)_1964年Floyd_(2)_，对含有n个元素的序列进行排序时,堆排序的时间复杂度19942（5堆是一种有用的数据结构.堆排序是一种_(1)_排序，堆实质上是一棵_(2)_结点的层次序列。对含有N个元素的序列进行排序时，堆排序的时间复杂度是_(3)_，所需的附加【山东工业大学1996三、1（5】TYPEheaptype=ARRAY[1..n]OFinteger；sifth，k，rh[k+1]，h[k+2]，…,h[r]为根的子树已sifth[k]，h[k+1],h[k+2],…,h[r]为根的子树都成为堆。h：heaptype；k，r：integer (j<=r) NOTfinish[IF(j<r)AND(h[j]>h[j+1])THENIFx>h[j]THEN ELSE ]PROCheapsort(VARh:heaptype;n:integer);VARk,r,i,j:integer; k:=nDIV sift((4))FOR [x:=h[1];h[1]:=h[r];h[r]:=x;((5))END;【工业大学1997五、2(16分)设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按2路归并排序方法对该序列进行 。【北方交通大学2001二、7】阅读下列程序说明和PASCAL程序，把应填入其中 a1与aj(j=n,n-1,…,2)aj1>a1aj1与a1变aj2aj2≥at(j2<t≤na1k(k≥0)a2与aj(j=jk,jk-1,…,3)jk=2，a2交换过的元素下标也n-1a vector=ARRAY[1..maxn]OFinteger;index=1..maxn;PROCEDUREsort(VARa:vector;n:index)VARp:vector;i,j,k,m,t:integer;k:=0;i:=1;m:=n;WHILEi<nDOFORj:=mDOWNTOi+1DOIFa[i]<a[j]THENBEGINt:=a[i];a[i]:=a[j];a[j]:=t;k:=k+1;（(1) ELSEBEGINm:=p[k];k:=k-1;END;UNTIL(i<m)OR(i=n);IF BEGINt:=a[i];（(6)）;（(7)END;【海运学院1997七（14分i,a[ia[i+1a[i]>a[i+1],将二者程序PROCEDUREoesort(VARa:ARRAY[1..n]OFinteger);VARflag:boolean; FORi:=1TOnstep2DOIF(a[i]>a[i+1])[flag:= ;t:=a[i+1];a[i+1]:=a[i]; FORi:= (a[i]>a[i+1])[flag:=(4)UNTIL(5) 程序voidoesort(int{intflag,i,t;do{flag=0;

;t:=a[i+1];a[i+1]:=a[i];{flag=(1);t=a[i+1];a[i+1]=a[i];(2) for(3) if ;t=a[i+1];a[i+1]=a[i];}while 【大学2000一、1（10分QHCYQAMSRDFX行排序，若采用初始步长为4的S排序法，则一趟扫描的结果是；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果 。【1997一4（4步长为４的希尔（s）排序，一趟扫描的结果是;采用以首元素为分界元素的快速排序，一趟扫描的结果是。【工业大学1999一、7(8分)外部排序的基本方法是归并排序，但在之前必须先生成【邮电大学2001二，磁盘排序过程主要是先生成，然后对合并，而提高排序速度很重要的是采用方法来提高排序速度。【山东工业大学1995一4（4分】， 【大 PROCEDUREimproveqsort(VARVARi,j,k:integer;WHILEm<nDOi:=m;j:=n+1;k:=list[m].key;IFi<j UNTILi>=j; improveqsort(list,(1) improveqsort(list,(3) {OF 2001五（10内部排序（ 【燕山大学1999一、5（2分出一个不稳定的实例【大连海事大学1996七、3 举例说明堆排序是否为稳定排序法.19964（5 【燕山大学2001三、3（5分 【邮电大学1993二、3（6分 【东南大学1996一、5（6分 【东南大学1999一、5（5分 结构，① n个元素的原始序列一般如何在 ， 为该排序算法是不稳定的，这种说法对吗？为什么？【燕山大学2001三、4（5】请列出其比较过程；如果不能，则说明原因。【北方交通大学1996五（10】n2n-3键字取最大值和关键字取最小值的记录？请说明如何实现？在的情况下至少进行多少20005（8利用比较的方法进行排序，在的情况下，能达到的最好时间复杂性是什么？请给出【交通大学2000六（8分1996三、2（3）(2【西北工业大学1999 1998二、5（2设LS是一个线性表，LS=(a1,a2,…,an),若采用顺序结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是多少？若元素插在ai与ai+1之间(0<=i<=n-1)的子科技大学2001软件 二、3（5分】对于堆积排序法，快速排序法和归并排序法，若仅从节省空间考虑，则应该首先种方法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？【航空航天大学1998一、10（4】20015(6若只从空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选(4)．若只从情况下排序最快并且要节省内存考虑，则应选取哪种排序方法空间最多，哪几种排序算法是不稳定的？【首都经贸大学1997一、3（4】欲求前k个最大元素，用什么分类方法好？为什么？什么是稳定分类？分别下列A．插入分类B．快速分类C．合并分类D．堆分类E．基数分类【东南大学1994一、3（8】｛a,b,c2001一、3(4PROCEDUREsort（r，n）FORi:=2TOnDO r(j+1):=r(j);j:=j-1该算法将会有什么变化，是否还能正确工作？【海运学院1998六（10分 bubblesort(r,n)i:=1;m:=n-1;WHILE(i<=(1))AND(flag=(2) )DOflag:=(3);FORj:=1TOmDOIF BEGINflag:=(4);t:=r[j];r[j]:=r[j+1];r[j+1]:=t该分类算法稳定吗？【海运学院1996六（12分 unknownname(VARA:array[1..500]OFinteger;n:integer);VARi,j,x:integer; WHILE(i<n)ANDbDOFORj:=1TO(1)DO THENx:=A[j];A[j]:=A[j+1]; A[j+1]:=x;(3) 2001（14 r: n: pos[-1]:=1; exchanged:= [exchanged:=false;WHILE (r[i]- [r[i]与r[i+d]交换;

]pos[d]:=pos[d]-d;i:=pos[d];d:=-]ENDP;【山东科技大学2002（12【航空航天大学1996九、1（4分1996四、3】交通大学1997四（8】分析下面排序算法中各带标号语句的频度及此算法的时间复杂度，并该算法是属于哪一种排序方法。【邮电大学1996一、2（7分】PROCEDUREsort(VARa:ARRAY[1..n] n-1 IF THEN t:=a[i];a[i]:=a[j];]使前七个记录有序，中间结果如下:【山东工业大学1996七（10】 在一些特殊情况下，二分法插入排序比直接插入排序要执行的比较。这句话对直接插入排序算法和直接选择排序算法的稳定性如何？【山东工业大学1997四从而认为该算法是不稳定的。这种说法对么？为什么？【东学2001一、1(4分)】 【东学2000一、5 (4分)】对下面数据表，写出采用S排序算法排序的每一趟的结果，并标出数据移动情况341544766610081420251四、4（5快速排序的最大递归深度是多少？最小递归深度是多少？【1999一、1（21996五（10【西安电子科技大学2000计应 一、1（5分nn2001（12大学2000六（10】当n=7时，在情况下需进行多少次比较？请说明理由当n=7时，给出一个情况的初始排序的实例快速排序（quicksorting）1—1515①② 情况下要进行几遍比较给出一种原始序列实例【浙江大学1995七(12分)N=7，给出快速排序的一个最好情况的初始排列实例(7【西学2000二、5(5分)(25,84,21,46,13,2,68,35,20)排序结果如下,则该序方法是什么?【交通科技大学1996、5(6)】初始:25,84,21,46,13,27,68,35,20 第二趟 【邮电大学1993一、1（5分分，写出其快速排序第一遍的排序过程。【厦门大学1998七、1（8）】(48,38,65,9573,13,27,50)要求给出快速排序的算法思想,并画出排序过程示意图。【航空航天大学1999五（102，1}，请写出对K按“S方法”排序时各趟排序结束时的结果；若每次以表的第一元素为基准（或枢轴K【科技大学1999七（10分）2000七（10分 PROCEDUREqsort1(VARVARWHILEm<n i:=m;j:=n+1;REPEAT UNTILREPEATj:=j- UNTILIFi<jTHENinterchangeUNTILinterchange(IFn-j>=j-THENBEGINELSEBEGINqsort1(list,j+1,n);n:=j-END;(OF9、10（5该排序算法稳定否？举例说明（5（22，3，30，4，60，11，58，18，4016qsort1m、n（5）层递归用一个单位栈空间（5分） 【东南大学1998四（20分】1998六（10】PROCEDUREqksort(VARr:listtype;s,t:integer);IF IFs=t MERGESORT(r,r2,s,(s+t)DIV2);MERGESORT(r,r2,(S+t)DIV2+1,t);MERGE(r2,s,(s+t)DIV2,t,rl)（98，36，77，42，23，65，84，10，59，37，61，18。【1996六】1998二、7（10】 （1）8770266145123 26 3 （7）3122645617087（4）10，20，40，60，66，77，80，【山东大学1998 (5分)】【山东工业大学2000四（5分70，33，65，24，56，48，92，86，33【复旦大学表示建堆的过程。【厦门大学2001二、1（24%/3）】①（1，5，7，20，18，8，8，40）④画出重新调整好的堆树。2001(5【邮电大学1996一、3（4分 个记录中找出2个最小的记录，你认为采用什么样的排序方法所需 【厦门大学1999三、4】（503，8，512，61908，170，897，275，653，462，输出最小值后，如何得到次小值（并画出相应结果图【同济大学2001 ①建立堆排序的初始堆（小顶堆②（【工业大学2001二、 序算法进行从小到大排序，要求画出排序全过程的示意图。【航空航天大学1997五①写出对K②如何将K建成一个完全二叉树形式的最小堆； 科技大学1997七（10分nk次比较？【东学2002一、4(3分)】(1)如果只想得到一个序列中第K个最小元前的部分排序序列，那么最好应采用哪种排序算法？为什么？如由这样一个序列：57,40,38,11,13,34,48,75,25,6,9,7得到其第四个最小元前的部分排序序列：6,7,9,11,…用你选用算法实现时，1994（16F=（12，3，15，30，9，28）进行排序时，初始堆及以后每挑好一个元素重新调整后堆的状态，并这里的堆和败者树的一个主要区别【东南大学1998二（8】请回答下列关于堆(Heap)的一些问题【2000五（12分(1)(4分)堆的表示是顺序的，还是的(2)（4）(3)（2）(4)（3）1999（15】1999（15若有NKn+1,请用文字简要说明你如何在log2n的时间内将其重新调整为一个堆?【计算所1999三、2（5分】下面是将任意序列调整为最大堆（MAXHEAP）adjust：FOR（i=n/2；i0；i），n个数，adjustvoidadjust（intlist[]，introot，intn*/{intchild,rootkey; }}}（12703365245648928633不能按上述算法将其调整为堆，调整后的结果为 【浙江大学1998七回答问题：(1)nsiftn-1假定采用sift建堆算法。试问堆排序算法采用了怎样的节省空间的措施？堆排序完成后，heap19963（8在多关键字排序时，LSD和MSD两种方法的特点是什么？【邮电大学2001三、（5会产生不同的中间结果。设要将序列（Q,H,C,Y,P,A,M,S,RD,F,X）中的关键字按字母序的4998四、5(6T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序希尔排序（第一趟排序的增量为5） (2)快速排序（选第一个记录为枢轴（分）(3)链式基数排序（基数为 【交通大学1999八（9分行排序时的变化过程【大学1998八(12分) 堆排 (1)①②③④⑤22000(20（1） 16少要多少次比较？请简要说明选择的方法和过程。【燕山大学1999九（14】i<m或者方法，列出一趟分配和收集的过程 【轻工业学院1999九（10分用以下排序方法进行由小到大排序。【西南交通大学2000二、6】 a55．请写出应填入下列叙述中（）内的正确答案。【大学2002一（8分（）排序的结果为（）排序的结果为（）排序的结果为注：anap,i,j,k,m,tp整型数组，i,j,k,m,taa1,a2，…,an该方法基于以下思想：在选择第一大元过程中：a1ajj=n,n-1,…,2)逐个比较，若发现aj1>a1,则aj1与a1交换，交换后新的aj1有性质aj1>=at(j1<t<n)。若再有aj2>ai(j2<j1),aj2a1aj2aj2>=at(j2<t<=na1k(k>=0)aj1,aj2,…,ajk，则它们都满足这a2aj(j=jk,jk-1,…,3)jk=2,a2a2a2n-1a1999（14果；堆排序时所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那法使用的辅助空间最少？在情况下那种方法的时间复杂度？【西安电子科技大学1999（10】奇偶交换排序如下所述：对于初始序列A[1]，A[2],…,A[n],第一趟对所有奇数（2<=i<n（1<=i<n2001（1019993（5】19965（5并树，并计算出wpl=?【东学1996一、2(5分)】30；4wpl。2001二、3（24%/320；试画出表示归并过程的最佳归并树，并计算树的WPL。 【厦门大学1998七、2（81268，85}，现用3路平衡归并，画出最佳归并树【邮电大学2002二、1（5分出4路归并时的最佳归并树，并计算它的带权路径长度WPL。【1998九（10计算总的（归并所需的）读/写外存的次数。【1