數(shù)據(jù)結(jié)構(gòu)（Java語言版）-習(xí)題及答案 第9章排序習(xí)題答案

第9章排序習(xí)題參考答案 一、單選題ABCDABCDn-1n+1n/2.nn/2ABCABCD排序的總趟數(shù)元素的移動次數(shù)使用輔助空間的數(shù)量元素之間的比較次數(shù)ABCABCD冒泡排序直接插入排序希爾排序二路歸并排序?qū)φ麛?shù)序列（8，9，10，4，5，6，20，1，2）進(jìn)行遞增排序，采用每趟冒出一個最小元素的冒泡排序算法，需要進(jìn)行的趟數(shù)是 。AABCD468.對一組數(shù)據(jù)（2，12，16，88，5，10）進(jìn)行排序，若前三趟的結(jié)果如下：第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88則采用的排序方法可能是 。AABCD希爾排序二路歸并排序基數(shù)排序

ABCABCD781213ABCD對關(guān)鍵字序列（，，，，，，，ABCD.，，，)602).，，，)8，，)C.，，，)8，，).，，，)8，，)ABCABCD快速排序在所有排序方法中為最快，而且所需輔助空間也最少在快速排序中，不可以用隊列替代?？焖倥判虻目臻g復(fù)雜度為On)快速排序在待排序的數(shù)據(jù)隨機分布時效率最高.n（n為大于10000的整數(shù)）個無序元素，希望用最快速度從中選擇前k（1≤k≤n）個關(guān)鍵字最小的元素，在以下排序方法中應(yīng)選擇 。AABCD快速排序希爾排序二路歸并排序直接插入排序ABCABCD直接插入排序冒泡排序簡單選擇排序都一樣ABCABCDn2n2n-1n-1ABCDABCD.（，，，，，，，，，，）.（，，，，，，，，，，）C.（，，，，，，，，，，）.（，，，，，，，，，，）ABCD有一個整數(shù)序列為（，，，，，，，ABCD.（，，，，，，，）.（，，，，，，，）C.（，，，，，，，）.ABCABCDngngn+1n2ABCABCD快速排序二路歸并排序基數(shù)排序堆排序ABCABCD10000個實數(shù)1000個由字母、數(shù)字和其他字符組成的字符串個n類型的整數(shù)10000個100以內(nèi)的正整數(shù)對給定的關(guān)鍵字序列（110，119，007，911，114，120，122）進(jìn)行基數(shù)排序，則第2趟分配收集后得到的關(guān)鍵字序列是 。A.，，，，，，2ABCD.，，，，，BCDC.，，，，，，2.，，，，，，9ABCABCD冒泡排序直接插入排序快速排序堆排序ABCD數(shù)據(jù)序列（，，，，，，，，ABCD簡單選擇排序冒泡排序直接插入排序堆排序ABCABCD簡單選擇排序希爾排序堆排序冒泡排序ABCABCD簡單選擇排序冒泡排序二路歸并排序堆排序ABCABCD快速排序冒泡排序堆排序簡單選擇排序ABCD整數(shù)序列（，，，，，，，，ABCD冒泡排序二路歸并排序堆排序簡單選擇排序ABCABCD外排序把外存文件調(diào)入內(nèi)存，再利用內(nèi)排序進(jìn)行排序，所以外排序所花時間完全由采用的內(nèi)排序決定外排序分為產(chǎn)生初始?xì)w并段和多路歸并兩個階段外排序并不涉及文件的讀寫操作外排序完全可以由內(nèi)排序來替代將一個由置換-選擇排序方法得到的輸出文件F1作為輸入文件再次進(jìn)行置換-選擇排序，得到輸出文件F2，問F1和F2的差異是 。AABCDF2中歸并段的最大長度增大F2和F1無差異歸并段個數(shù)及各歸并段長度均不變，但F2中可能存在與F1不同的歸并段AB采用敗者樹進(jìn)行k路平衡歸并的外排序算法，其總的歸并效率與k 。AB有關(guān)無關(guān)ABCABCD1/k/kgkmAB設(shè)有100初始?xì)w并段，如采用k路平衡歸并3趟完成排序，則k值是 。AB56CDCD8ABm個初始?xì)w并段采用k路平衡歸并時，構(gòu)建的敗者樹中共有 個結(jié)點（不計冠軍結(jié)點）。AB2k-1.2kCDC.CD.1ABCABCD0123ABCABCD該排序算法不允許有相同的關(guān)鍵字記錄該排序算法允許有相同的關(guān)鍵字記錄平均時間為Ongn的排序方法以上都不對ABCABCD經(jīng)過排序后，能使關(guān)鍵字相同的元素保持原順序中的相對位置不變經(jīng)過排序后，能使關(guān)鍵字相同的元素保持原順序中的絕對位置不變排序算法的性能與被排序元素的數(shù)量關(guān)系不大排序算法的性能與被排序元素的數(shù)量關(guān)系密切ABCABCD這兩個元素的前后位置不發(fā)生變化這兩個元素的前后位置一定發(fā)生變化這兩個元素的位置不發(fā)生變化這兩個元素的前后位置可能發(fā)生變化ABCABCD穩(wěn)定的排序方法優(yōu)于不穩(wěn)定的排序方法，因為穩(wěn)定的排序方法效率較高對同一個順序表使用不同的排序方法進(jìn)行排序，得到的排序結(jié)果可能不同排序方法都是在順序表上實現(xiàn)的，在鏈表上無法實現(xiàn)排序方法在順序表上實現(xiàn)的排序方法在鏈表上也可以實現(xiàn)ABCABCD二路歸并排序拓?fù)渑判蚨雅判蛑苯硬迦肱判駻BCABCD簡單選擇排序冒泡排序歸并排序堆排序ABCABCD希爾選擇快速排序歸并排序堆排序ABCD下列排序方法中，輔助空間為OnABCD希爾選擇冒泡排序堆排序歸并排序A下列四種排序中（）的空間復(fù)雜度最大。 A直接插入排序BBCD堆排序二路歸并排序ABCABCDABCABCD快速排序歸并排序基數(shù)排序堆排序ABCABCD快速排序堆排序希爾排序基數(shù)排序ABCABCD10n52ABCABCD10n52ABCABCD10000個實數(shù)1000個由字母、數(shù)字和其他字符組成的字符串個n類型的整數(shù)10000個100以內(nèi)的正整數(shù)ABCABCD直接插入排序和快速排序直接插入排序和冒泡排序簡單選擇排序和歸并排序歸并排序和冒泡排序ABCABCD快速排序冒泡排序堆排序希爾排序ABCABCD0nn-13n(n-1)/2ABCABCD01n3n(n-1)/2二、編程題OJ—N排序問題時間限制：，空間限制：。問題描述：：一個序列中的未排序的度量是相對于彼此順序不一致的條目對的數(shù)量，例如，在字母序列EC中，該度量為，因為D大于右邊是個字母，E大于其右邊的個字母。該度量稱為該序列的逆序數(shù)。序列CE只有一個逆序?qū)Γ‥和），它幾乎被排序好了，而序列Q有個逆序?qū)Γ俏磁判虻模『檬欠葱?。你需要對若干個N序列（僅包含個字母、C、和的字符串）分類，注意是分類而不是按字母順序排序，而是按照“最多排序”到“最小排序”的順序排列，所有DNA序列的長度都相同。輸入格式：第一行包含兩個整數(shù)，n（0<n≤50）表示字符串長度，m（0<m≤100）表示字符串個數(shù)。后面是m行，每行包含一個長度為n的字符串。輸出格式：按“最多排序”到“最小排序”的順序輸出所有字符串。若兩個字符串的逆序?qū)€數(shù)相同，按原始順序輸出它們。答：prtvu*;csEeype{ntv; //存放r的逆序數(shù)nt; //存放字符串的下標(biāo)i}pubccsn{cntN=;cnt=;cntn; //相鄰整數(shù)的最小交換數(shù)量cn]=newnN; //存放整數(shù)序cvdergechrntntdnthgh)//兩個相鄰有序段歸并{nt=;ntntk=;chrb=newchrhgh+; //開辟臨時空間hei<=d&j<=hgh) //二路歸并：d、d+hgh=>b{>){bk++=++;n+=d+; /計逆序數(shù)}eebk++=++;}hei<=d)bk++=++;hej<=hgh)bk++=++;rntk=;k1<k;k++) //bk=>hgh]+k=bk;}cvdergeSrchrntnt)//二路歸并排序{>=)reurn; //的長度為或者時返回nt=+/; //取中間位置mergeSr; //對前子表排序ergeSr+; //對后子表排序erge; //將兩個有序子表合并成一個有序表}cntInvernchrntn) //二路歸并法求字符串的逆序數(shù){n=;ergeSrn;returnans;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;Srng]r=newSrng;Eeype]b=newEeype;chr]p=newchrN;n=nnexIn;=nnexIn; //輸入n和mrnt=;i<;++) //輸入r=nnex;rnt=;i<;++) //求所有字符串的逆序數(shù){rnt=;j<rengh;++)//將r復(fù)制的字符數(shù)組p中p=rchr;b=newEeype;bv=Invernpn; //求p的逆序b=; //記錄原來的下標(biāo)}rryrbnewCprr<Eeype>){pubcntcpreEeypeEeype){fvv==) //v相同時按reurn;ee //v不相同時按vreurnvv;}});rnt=;i<;++) //輸出結(jié)果Syeuprn"%\n"rb;}}.OJ—求中位數(shù)問題時間限制：，空間限制：。問題描述：：FJ正在調(diào)查他的牛群以尋找最普通的牛群，他想知道產(chǎn)奶量的中位數(shù)：一半奶牛的產(chǎn)奶量與中位數(shù)一樣多或更多，：一半奶牛的產(chǎn)奶量與中位數(shù)一樣多或更少。輸入格式：給定n（n為奇數(shù)，≤n<）頭牛的牛奶產(chǎn)量（到），找到這些奶牛中產(chǎn)奶量的中位數(shù)。輸入的第1行為整數(shù)n，第2行到第n+1中每行包含一個整數(shù)，表示一頭牛奶的產(chǎn)奶量。輸出格式：輸出一行表示產(chǎn)奶量的中位數(shù)。答：prtvuScnner;prtvu*;pubccsn{pubccvdnSrng]rg){nlntN=;n]=newnN;Scnnern=newScnnerSyen;henhNex){ntn=nnexIn;rnt=;i<n;++)=nnexIn;rryrn;Syeuprnnn/;}}}OJ—求中位數(shù)時間限制：，空間限制：。問題描述：：對于這個問題，你需要編寫一個程序讀取一系列整數(shù)，在讀取每個奇數(shù)序號的整數(shù)后輸出到目前為止接收的整數(shù)的中值（中位數(shù)）。輸入格式：第一行輸入包含一個整數(shù)t（1≤t≤1000）表示數(shù)據(jù)集個數(shù)。每個數(shù)據(jù)集的第一行包含數(shù)據(jù)集編號，后跟一個空格，后跟一個奇數(shù)十進(jìn)制整數(shù)（≤≤），表示要處理的有符號整數(shù)的個數(shù)，數(shù)據(jù)集中的其余行由每行個整數(shù)組成，由單個空格分隔。數(shù)據(jù)集中的最后一行可能包含少于10個整數(shù)。輸出格式：對于每個數(shù)據(jù)集，第一行輸出包含數(shù)據(jù)集編號，單個空格和中位數(shù)個數(shù)（應(yīng)該是輸入整數(shù)個數(shù)的一半加一），將在以下行中輸出中位數(shù)，每行10個由單個空格分隔。最后一行可能少于10個元素，但至少有1個元素。輸出中沒有空行。答：prtvuScnner;prtvu*;pubccsn{crryQueue<neger>=newrryQueue<neger>;//小根堆crryQueue<neger>bg=newrryQueue<neger>newCprr<neger>){@OverrdepubcntcpreInegerIneger) //大根堆{reurnn;}});crry<neger>n=newrry;//存放中位數(shù)序列cvdddntx) //增加整數(shù)x{Epy //若小根堆空{(diào)erx; //將x插入到return;}x>peek) //若x大于小根堆堆頂元erx; //將x插入到中eebgerx; //否則將x插入到大根堆bg中e<bge) //若小根堆元素個數(shù)較少erbgp; //取出bg的堆頂元素插入到中e>bge+) //若比bg至少多個元素bgerp; //取出的堆頂元素插入到bg中}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntcx;=nnexIn;he>){heEpyp;//初始化hebgEpybgp;ncer;c=nnexIn;=nnexIn;rnt=;i<=;++){x=nnexIn;add(x); //增加整數(shù)x%==) //x為奇數(shù)序號的整數(shù)nddpeek;//將求出的中位數(shù)添加到n中}Syeuprn"%d%d\n"c+/;rnt=;<ne;++)//輸出中位數(shù)序列{f>0&%==)Syeuprnn;Syeuprnnge+"";}Syeuprnn;}}}HDU11062000ms，空間限制：65536K。問題描述：：輸入一行數(shù)字，如果我們把這行數(shù)字中的都看成空格，那么就得到一行用空格分割的若干非負(fù)整數(shù)（可能有些整數(shù)以這些頭部的應(yīng)該被忽略掉，除非這個整數(shù)就是由若干個組成的，這時這個整數(shù)就是）。你的任務(wù)是對這些分割得到的整數(shù)，依從小到大的順序排序輸出。輸入格式：輸入包含多組測試用例，每組輸入數(shù)據(jù)只有一行數(shù)字（數(shù)字之間沒有空格），這行數(shù)字的長度不大于1000。輸入數(shù)據(jù)保證分割得到的非負(fù)整數(shù)不會大于，輸入數(shù)據(jù)不可能全由組成。輸出格式：對于每個測試用例，輸出分割得到的整數(shù)排序的結(jié)果，相鄰的兩個整數(shù)之間用一個空格分開，每組輸出占一行。答：prtvuScnner;prtvu*;pubccsn{cnlntN=;cn]=newnN;pubccvdnSrng]rg){Scnnern=newScnnerSyen;Srngr;henhNex){r=nnexne;Srngp=rp"";//分拆數(shù)字字符串rntcn=;rnt=;i<pengh;++){fpequ""){ntx=InegerpreInp;cn++=x; //將非空串轉(zhuǎn)換為整數(shù)添加到}}rryrcn; //對benr=rue;rnt=;i<cn;++) //輸出結(jié)果{if(first){Syeuprn;r=e;}eeSyeuprn""+;}Syeuprnn;}}}HDU1862—EXCEL10000ms，空間限制：32768K。問題描述：：Exce可以對一組紀(jì)錄按任意指定列排序?，F(xiàn)請你編寫程序?qū)崿F(xiàn)類似功能。答：prtvuScnner;prtvu*;csSud //學(xué)生元素類{ntn; //學(xué)號Srngne; //姓ntgrde; //成績pubcSudntnSrngnentgrde) //構(gòu)造方法{hn=n;hne=ne;hgrde=grde;}pubcvddp //輸出一個學(xué)生元素{nt=InegerSrngnengh;rnt=;>;)Syeuprn;Syeuprnnn+""+ne+""+grde;}}pubccsn{cnlntN=;cSud];pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntncc=;henhNex){n=nnexIn;fn==)brek;Stud[]a=newStud[n];c=nnexIn;rnt=;i<n;++){ntn=nnexIn;Srngne=nnex;ntgrde=nnexIn;=newSudnnegrde;}fc==)rryrnnewCprr<Sud>){pubcntcpreSudSud)//按學(xué)號遞增排序{reurnnn;}});eefc==)rryrnnewCprr<Sud>){pubcntcpreSudSud){fnecprene==)//姓名相同reurnnn; //按按學(xué)號遞增排序ee //否則按姓名非遞減排序reurnnecprene;}});ee //c==的情況rryrnnewCprr<Sud>{pubcntcpreSudSud)//按成績的非遞減排序{fgrde==grde) //成績相同reurnnn; //按按學(xué)號遞增排序ee //否則按成績的非遞減排序reurngrdegrde;}});Syeuprnn"Ce"+c+":"; //rnt=;i<n;++)dp;c++;}}}H—按絕對值排序問題時間限制：，空間限制：。問題描述：：輸入n（n≤100）個整數(shù)，按照絕對值從大到小排序后輸出。題目保證對于每一個測試實例，所有的數(shù)的絕對值都不相等。輸入格式：輸入數(shù)據(jù)有多組，每組占一行，每行的第一個數(shù)字為n，接著是n個整數(shù)，n=0表示輸入數(shù)據(jù)的結(jié)束，不做處理。輸出格式：對于每個測試實例，輸出排序后的結(jié)果，兩個數(shù)之間用一個空格隔開。每個測試實例占一行。答：prtvuScnner;prtvu*;pubccsn{cnlntN=;cn]=newnN;cntrnntnt)//按表首元素為基準(zhǔn)進(jìn)行劃分{nt==;ntbe=; //以表首元素為基準(zhǔn)he=) //從表兩端交替向中間遍歷直至=為止{he>i&hb)<=hbbe); //從后向前遍歷找一個小于基準(zhǔn)的]f>){=; //前移覆蓋]++;}hei=hbbe)++; //從前向后遍歷找一個大于基準(zhǔn)的]if(i{=; //后移覆蓋]j--;}}=be; //基準(zhǔn)歸位returni; //返回歸位的位置}cvdQuckSrntnt)//對的元素進(jìn)行快速排序(s{nt=rn;QuckSr; //對左子表遞歸排序QuckSr+; //對右子表遞歸排序}}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;henhNex){n=nnexIn;fn==)brek;rnt=;i=nnexIn;QuckSrn;benr=rue;rnt=;i{if(first){Syeuprn;r=e;}eeSyeuprn""+;}Syeuprnn;}}}prtvuScnner;prtvu*;pubccsn{cnlntN=;cn]=newnN;cntrnntnt)//按表首元素為基準(zhǔn)進(jìn)行劃分{nt==;ntbe=; //以表首元素為基準(zhǔn)he=) //從表兩端交替向中間遍歷直至=為止{he>i&hb)<=hbbe); //從后向前遍歷找一個小于基準(zhǔn)的]f>){=; //前移覆蓋]++;}hei=hbbe)++; //從前向后遍歷找一個大于基準(zhǔn)的]if(i{=; //后移覆蓋]j--;}}=be; //基準(zhǔn)歸位returni; //返回歸位的位置}cvdQuckSrntnt)//對的元素進(jìn)行快速排序(s{nt=rn;QuckSr; //對左子表遞歸排序QuckSr+; //對右子表遞歸排序}}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;henhNex){n=nnexIn;fn==)brek;rnt=;i=nnexIn;QuckSrn;benr=rue;rnt=;i{if(first){Syeuprn;r=e;}eeSyeuprn""+;}Syeuprnn;}}}7.求平均數(shù)問題。在演講比賽中，當(dāng)參賽者完成演講時評委將對他的表演進(jìn)行評分。工作人員刪除最高分和最低分，并計算其余的平均分作為參賽者的最終成績。這是一個容易出問題的問題，因為通常只有幾名評委?？紤]上面問題的一般形式，給定n個正整數(shù)，刪除最大的n1個和最小的n2個，并計算其余的平均值。答：publicvoidaverageNumber(){ Scannerfin=newScanner(System.in); intn1,n2,n; while(fin.hasNext()){ n1=fin.nextInt(); n2=fin.nextInt(); n=fin.nextInt(); if(n1==0&&n2==0&&n==0)break; PriorityQueue<Long>small=newPriorityQueue<Long>();//小根堆 PriorityQueue<Long>big=newPriorityQueue<Long>(11,newComparator<Long>(){ @Override publicintcompare(Longo1,Longo2){ //大根堆 return(int)(o2-o1); } }); longsum=0,a; intsmallcnt=0,bigcnt=0; for(inti=1;i<=n;i++){ a=fin.nextLong(); sum+=a; if(smallcnt<n1){ smallcnt++; small.offer(a); } elseif(a>small.peek()){ small.poll(); small.offer(a); } if(bigcnt<n2){ bigcnt++; big.offer(a); } elseif(a<big.peek()){ big.poll(); big.offer(a); } } while(!big.isEmpty()){ longx=big.poll(); sum-=x; } while(!small.isEmpty()){ longx=small.poll(); sum-=x; } System.out.printf("%.6f\n",(sum*1.0)/(n-n1-n2)); } }三、簡答題簡述何時使用穩(wěn)定的排序算法。 答：如果排序數(shù)據(jù)存在相同關(guān)鍵字的元素，而且要求排序后不改變這些相同關(guān)鍵字記錄的相對位置，此時需要使用穩(wěn)定的排序算法。如張三的成績是82，李四成績也是82，而張三的記錄在李四的記錄的前面，要求按成績遞減排序，排好序后，張三的記錄仍在李四的記錄的前面，這就需要使用穩(wěn)定的排序算法。另一個用途是多關(guān)鍵字排序，如學(xué)生記錄有姓名、數(shù)學(xué)、語文成績和總分，要求這樣排名次，先按總分，總分相同再按數(shù)學(xué)成績?？梢赃@樣排序，先采用任一種排序方法按數(shù)學(xué)成績遞減排序，再選擇一種穩(wěn)定的排序方法按總分排序，后者一定用穩(wěn)定的排序方法，否則會出現(xiàn)總分相同，數(shù)學(xué)成績低的排到前面了。排序方法的穩(wěn)定性受什么因素影響？ 答：在排序過程中，需要以一個較大的間隔互換元素，或把元素隔空搬運一段較大距離時，排序方法一定不穩(wěn)定，它可能會把原先排在前面的元素搬到具有相同關(guān)鍵字值的另一個元素的后面，改變了相對位置。證明：對于一個長度為n的線性表基于比較方法進(jìn)行排序，至少需要進(jìn)行ngn次比較。 答：證明：對于一個長度為n的線性表基于比較方法進(jìn)行排序，元素兩兩比較構(gòu)成的判定樹可以近似看成是一棵滿二叉樹，其中葉子結(jié)點是某種排序結(jié)果，由于n個元素總共有n!種不同的排列，所以葉子結(jié)點個數(shù)為n!，一次排序恰好經(jīng)過從根結(jié)點到某個葉子結(jié)點的路徑，比較次數(shù)為樹的高度，而h=gn≈ngn，所以至少需要進(jìn)行ngn次比較。給出關(guān)鍵字序列采用直接插入排序時各趟的結(jié)果。答：直接插入排序算法在含有n個元素的初始數(shù)據(jù)正序、反序和數(shù)據(jù)全部相等時，時間復(fù)雜度各是多少？ 答：含有n個元素的初始數(shù)據(jù)正序時，直接插入排序算法的時間復(fù)雜度為On。含有n個元素的初始數(shù)據(jù)反序時，直接插入排序算法的時間復(fù)雜度為On含有n個元素的初始數(shù)據(jù)全部相等時，直接插入排序算法的時間復(fù)雜度為On。已知序列，采用二路歸并排序法對該序列作升序排序時的每一趟的結(jié)果。 答：.兩個各含有n個元素的有序序列歸并成一個有序序列時，關(guān)鍵字比較次數(shù)為n～2n-1，也就是說關(guān)鍵字比較次數(shù)與初始序列有關(guān)。為什么通常說二路歸并排序與初始序列無關(guān)呢？答：二路歸并排序中使用了輔助空間，需要先將所有歸并數(shù)據(jù)移到中，然后再復(fù)制到中，所以每一趟移動元素的次數(shù)n，共需gn趟排序，總的移動次數(shù)總是Ongn并排序與初始序列無關(guān)。二路歸并排序中每一趟排序都要開辟On的輔助空間，共需gn趟排序，為什么總的輔助空間仍為On？ 答：二路歸并排序中每一趟排序都要開辟On的輔助空間，但在一趟排序結(jié)束后，這些輔助空間都被釋放了，所以總的輔助空間仍為On.在堆排序、快速排序和歸并排序中：（1）若只從存儲空間考慮，則應(yīng)首先選取哪種排序方法，其次選取哪種排序方法，最后選取哪種排序方法？（2）若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取哪種排序方法？（3）若只從最壞情況下的排序時間考慮，則不應(yīng)選取哪種排序方法？答：若只從存儲空間考慮，則應(yīng)首先選取堆排序（空間復(fù)雜度為O），其次選取快速排序（空間復(fù)雜度為Ogn），最后選取歸并排序（空間復(fù)雜度為On）。若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取歸并排序。因為歸并排序是穩(wěn)定的，其他兩種排序方法是不穩(wěn)定的。若只從最壞情況下的排序時間考慮，則不應(yīng)選取快速排序方法。因為快速排序方法最壞情況下的時間復(fù)雜度為On，其他兩種排序方法在最壞情況下的時間復(fù)雜度為O(nlog2n)。以歸并算法為例，比較內(nèi)排序和外排序的不同，說明外排序如何提高操作效率。 答：內(nèi)排序中的歸并排序是在內(nèi)存中進(jìn)行的歸并排序，輔助空間為O(n)。外部歸并排序是將外存中的多個有序子文件合并成一個有序子文件，將每個子文件中記錄讀入內(nèi)存后的排序方法可采用多種內(nèi)排序方法。外部排序的效率主要取決于讀寫外存的次數(shù)，即歸并的趟數(shù)。因為歸并的趟數(shù)s=logkm，其中，m是歸并段個數(shù)，k是歸并路數(shù)。增大k和減少m都可減少歸并趟數(shù)。實際應(yīng)用中通過敗者樹進(jìn)行k（k≥3）路平衡歸并和置換-選擇排序減少m，來提高外部排序的效率。給出關(guān)鍵字序列按低位到高位進(jìn)行基數(shù)排序時每一趟的結(jié)果。 答：給出關(guān)鍵字序列按高位到低位進(jìn)行基數(shù)排序時每一趟的結(jié)果。 答：排序結(jié)果如圖所示，從中看到，最終的排序結(jié)果是錯誤的，所以對于數(shù)值數(shù)據(jù)排序時只能是按低位到高位進(jìn)行基數(shù)排序。.有n個不同的英文單詞（均為小寫字母），它們的長度相等，均為m。若n=50，m<5，試問采用什么排序方法時其時間復(fù)雜度最??？為什么？答：采用基數(shù)排序方法最好，這里r=，其時間復(fù)雜度為On+，其他排序方法的時間復(fù)雜度最小為Ongn，當(dāng)n=，<5時，n+<ngn，所以基數(shù)排序方法最好。問在一般情況下，直接插入排序、簡單選擇排序和冒泡排序的過程中，所需元素交換次數(shù)最少的是哪種排序方法？ 答：對于直接插入排序，有序區(qū)分別有、、…、n個元素，平均交換一半的元素，所以平均元素交換次數(shù)rd/ebeddng/eObecbn>++…n≈n/。對于簡單選擇排序，最多只進(jìn)行n-1次元素交換對于冒泡排序，平均每趟交換一半的元素，平均排序n/趟，所以平均元素交換次數(shù)=<Obec:rd/ebeddng/eObecbn>n-+n+…n/+≈n/。所以元素交換次數(shù)最少的是簡單選擇排序。.在下列情況下，選擇哪種內(nèi)排序算法比較合適？說明理由。（1）需要對1000個大型記錄進(jìn)行排序，記錄本身存儲在外存中，在內(nèi)存中只保研了所有記錄的關(guān)鍵字。關(guān)鍵字之間的比較非?？?，但移動代價很大，因為一旦移動一個關(guān)鍵字，相應(yīng)的外存中的記錄也要移動，這將涉及很多磁盤塊的移動。（2）已知一個包含了5000個單詞的列表已按字母順序排好序，需要再進(jìn)行一次檢查，確保所有的單詞已經(jīng)排好序。（3）需要將500張隨機排列的圖書卡片按照字母順序排序。答：選擇簡單選擇排序，該排序方法可以達(dá)到盡量少地移動記錄，雖然比較次數(shù)達(dá)到On，但是相對外存的處理時間來說，不是關(guān)鍵因素。因為整個表已經(jīng)基本有序，所以應(yīng)該采用直接插入排序。因為是隨機排列的卡片，所以選擇快速排序比較合適。四、填空題如果一組數(shù)據(jù)采用某種排序方法進(jìn)行排序，排序后相同關(guān)鍵字的元素的相對位置不發(fā)生改變，稱該排序方法是。 答：穩(wěn)定的若不考慮基數(shù)排序，在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的。和記錄的。 答：比較;移動每次從無序子表中取出一個元素，通過依次比較把它插入到有序子表的適當(dāng)位置，此種排序方法稱為。 答：直接插入排序?qū)衝個元素的數(shù)據(jù)序列進(jìn)行直接插入排序（采用《教程》中的算法），在最好情況下移動元素的個數(shù)是，關(guān)鍵字比較的次數(shù)是。答：2(n-1);n-1對含有n個元素的數(shù)據(jù)序列進(jìn)行直接插入排序（采用《教程》中的算法），在最壞情況下移動元素的個數(shù)是，關(guān)鍵字比較的次數(shù)是。答：nn+/;nn/2數(shù)據(jù)序列采用二路歸并排序方法進(jìn)行遞增排序，經(jīng)過兩趟排序后的結(jié)果是。答：}數(shù)據(jù)序列采用二路歸并排序方法進(jìn)行遞增排序，所需要關(guān)鍵字比較次數(shù)是。答：12.數(shù)據(jù)序列中有 個元素，采用二路歸并排序方法進(jìn)行遞增排序，最好情況下所需要關(guān)鍵字比較次數(shù)是。答：在快速排序、堆排序、歸并排序中，排序是穩(wěn)定的。答：歸并排序二路歸并排序算法的空間復(fù)雜度是。答：On)題：基數(shù)排序主要適用于排序的情況。答：多關(guān)鍵字題：基數(shù)排序與其他幾種排序方法的區(qū)別是。答：基數(shù)排序采用分配和收集實現(xiàn)，不需要進(jìn)行關(guān)鍵字的比較，而其他幾種排序方法都是通過關(guān)鍵字的比較實現(xiàn)的題：對數(shù)據(jù)序列采用最低位優(yōu)先的基數(shù)排序，第一趟排序后的結(jié)果是。答：}題：對數(shù)據(jù)序列采用最低位優(yōu)先的基數(shù)排序，第趟排序后的結(jié)果是。答：}題：基數(shù)排序的空間復(fù)雜度是。答：Or（r為排序的基數(shù)）五、判斷題一組數(shù)據(jù)序列為………，與的關(guān)鍵字相同，采用某種排序方法排序后變?yōu)椤?，則該排序算法是穩(wěn)定的。答：錯誤2.當(dāng)待排序的元素很大時，為了交換元素的位置，移動元素要占用較多的時間，這是影響算法時間復(fù)雜度的主要因素。 答：錯誤內(nèi)排序方法要求數(shù)據(jù)一定以順序表方式存儲。 答：錯誤所有內(nèi)排序算法中的比較次數(shù)與初始元素序列的排列無關(guān)。 答：錯誤排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。 答：錯誤二路歸并排序算法是穩(wěn)定的。 答：正確對于不同的初始數(shù)據(jù)序列，二路歸并排序算法中關(guān)鍵字比較次數(shù)有所不同。 答：正確二路歸并排序算法的時間復(fù)雜度與初始數(shù)據(jù)序列的順序無關(guān)。 答：正確二路歸并排序算法的最好時間復(fù)雜度為On。 答：錯誤n個元素采用二路歸并排序算法，總的趟數(shù)為n。 答：錯誤基數(shù)排序只適用于以數(shù)字為關(guān)鍵字的情況，不適用以字符串為關(guān)鍵字的情況。 答：錯誤基數(shù)排序與初始數(shù)據(jù)的次序無關(guān)。 答：正確基數(shù)排序與初始數(shù)據(jù)中關(guān)鍵字的大小無關(guān)。 答：錯誤快速排序、簡單選擇排序和堆排序都與初始序列次序無關(guān)。 答：錯誤直接插入排序、冒泡排序和簡單選擇排序在最好情況下的時間復(fù)雜度均為On。 答：錯誤第9章排序習(xí)題參考答案 一、單選題.對一組數(shù)據(jù)進(jìn)行排序，若前三趟的結(jié)果如下：第一趟：8第二趟：8第三趟：8則采用的排序方法可能是(。AABCD希爾排序歸并排序基數(shù)排序

ABABCD簡單選擇排序冒泡排序堆排序直接插入排序.對數(shù)據(jù)排序，數(shù)據(jù)的排列次序在排序過程中的變化如圖所示，則采用的排序方法是（）。AABCD簡單選擇排序快速排序冒泡排序直接插入排序.假設(shè)排序過程中順序表的變化情況如下：21，25，49，25，16，8（初始狀態(tài)）8，25，49，25，16，218，16，49，25，25，218，16，21，25，25，498，16，21，25，25，498，16，21，25，25，49（最終狀態(tài)）可以斷定，所采用的排序方法是（）排序。AABCD冒泡二路歸并簡單選擇ABCABCD直接插入和快速冒泡和快速簡單選擇和直接插入簡單選擇和冒泡ABCABCD直接插入排序冒泡排序簡單選擇排序都一樣ABCABCD內(nèi)排序速度快，而外排序速度慢內(nèi)排序不涉及內(nèi)、外存數(shù)據(jù)交換，而外排序涉及內(nèi)、外存數(shù)據(jù)交換內(nèi)排序所需內(nèi)存小，而外排序所需內(nèi)存大內(nèi)排序的數(shù)據(jù)量小，而外排序的數(shù)據(jù)量大ABCABCD外排序把外存文件調(diào)入內(nèi)存，再利用內(nèi)排序方法進(jìn)行排序，所以外排序所花時間完全由采用的內(nèi)排序確定外排序所花時間=內(nèi)排序時間+外存信息讀寫時間+內(nèi)部歸并所花時間外排序并不涉及文件的讀寫操作外排序完全可以由內(nèi)排序來替代ABCABCD減少初始?xì)w前段的段數(shù)便于實現(xiàn)敗者樹減少歸并趟數(shù)以上都對ABCABCDgkmgk+1gk+)gkABCABCD3456ABCDk個結(jié)點的敗者樹中選取最小的關(guān)鍵字，則所需時間為ABCDOgk)O)Ok)以上都不對ABm個初始?xì)w并段采用k路平衡歸并時，構(gòu)建的敗者樹中共有 （）個結(jié)點（不含冠軍結(jié)點）。AB2k-1.2kCDC.CD.1ABCDABCDgk1gkgk+1gkm題9：m個初始?xì)w并段中總共有u個記錄，采用k路平衡歸并，在k個記錄中選取最小關(guān)鍵字的記錄時采用逐個比較的方式進(jìn)行，則總的關(guān)鍵字比較次數(shù)是（）。AABCD.guk)guk/gkgu)gk)始?xì)w并段中總共有u個記錄，采用k路平衡歸并，在k個記錄中選取最小關(guān)鍵字的記錄時采用敗者樹進(jìn)行，則總的關(guān)鍵字比較次數(shù)是 （）（用時間復(fù)雜度表示）。AABCD.guk)guk/gkgu)gk)ABCABCD成正比成反比無關(guān)以上都不對題12：如將一個由置換-選擇排序得到的輸出文件F1（含所有初始?xì)w并段）作為輸入文件再次進(jìn)行置換-選擇排序，得到輸出文件F2（含所有初始?xì)w并段），問F1和F2的差異是（）。AABCDF2歸并段個數(shù)減少F2中歸并段的最大長度增大F2和F1無差異歸并段個數(shù)及各歸并段長度均不變，但F2中可能存在與F1不同的歸并段ABCD題13：n個記錄采用置換ABCDm與n成正比m與n成反比=gn以上都不對ABCD題：當(dāng)內(nèi)存工作區(qū)可容納的記錄個數(shù)=時，記錄序列采用置換ABCD1235題：當(dāng)內(nèi)存工作區(qū)可容納的記錄個數(shù)=時，記錄序列采用置換選擇算法產(chǎn)生（）有序段。 AABCD235ABCABCD.，，}.，，}C.，，}.，，}ABCD題：對于個初始?xì)w并段，構(gòu)建k路最佳歸并樹時，設(shè)u=)%k，當(dāng)u≠ABCDuk-uk-1-uu-1ABCABCDk階平衡樹平衡二叉樹k階哈夫曼樹以上都不對ABCABCD./k./kC./k).ABCABCDk/k.k/k)C.k/k).AB題21：對于磁帶文件的k路平衡歸并最好使用（）臺磁帶機。ABCD1.CDC.k.k1AB題22：對于磁帶文件的k路多階段歸并需要使用（）臺磁帶機。ABCD1.CDC.k.k1二、填空題對含有n個元素的數(shù)據(jù)序列進(jìn)行冒泡排序，其中關(guān)鍵字比較最多的次數(shù)是。 答：n(n-1)/2對含有n個元素的數(shù)據(jù)序列進(jìn)行冒泡排序，其中關(guān)鍵字比較最少的次數(shù)是。 答：n-1冒泡排序算法在最好情況下的時間復(fù)雜度是。 答：On)冒泡排序算法的平均時間復(fù)雜度是。 答：.對數(shù)據(jù)序列采用冒泡排序方法進(jìn)行遞增排序，每趟通過交換歸位關(guān)鍵字最小的元素，經(jīng)過一趟后的排序結(jié)果是。答：}簡單選擇排序的最好、最壞和平均時間復(fù)雜度分別為 、、。 答：On;On;On)在直接插入排序、冒泡排序和簡單選擇排序這三種簡單排序方法中，是不穩(wěn)定的。 答：簡單選擇排序數(shù)據(jù)序列采用簡單選擇排序進(jìn)行遞增排序，每趟挑選最小元素，經(jīng)過趟排序后結(jié)果是。 答：}對含有n個元素的數(shù)據(jù)序列進(jìn)行簡單選擇排序，總的關(guān)鍵字比較次數(shù)是。 答：n(n-1)/2對含有n個元素的數(shù)據(jù)序列進(jìn)行簡單選擇排序，最好情況下元素移動的次數(shù)是。 答：0磁盤是一種設(shè)備，磁帶是一種設(shè)備， 答：直接存取;順序存取外排序有兩個基本階段，第一階段是，第二階段是。 答：生成初始?xì)w并段;對這些歸并段采用某種歸并方法，進(jìn)行多遍歸并外排序的基本方法是歸并排序，但在之前必須先生成。 答：初始?xì)w并段外排序有兩個基本階段，置換-選擇排序算法用于。 答：外排序的第一個階段置換-選擇排序算法的作用是。 答：由一個無序文件產(chǎn)生若干個有序子文件n個記錄采用置換-選擇排序，假設(shè)內(nèi)存工作區(qū)可容納的記錄個數(shù)為w（n遠(yuǎn)大于w），則除最后一個初始?xì)w并段外，其他每個初始?xì)w并段的長度至少是。答：wn個記錄采用置換-選擇排序，假設(shè)內(nèi)存工作區(qū)可容納的記錄個數(shù)為w（n遠(yuǎn)大于w），產(chǎn)生的初始?xì)w并段的最大長度是。 答：n一組關(guān)鍵字=，設(shè)內(nèi)存工作區(qū)可容納個記錄，記采用置換選擇排序，則產(chǎn)生個初始?xì)w并段。答：2一組關(guān)鍵字=，設(shè)內(nèi)存工作區(qū)可容納個記錄，記采用置換選擇排序，則產(chǎn)生的初始?xì)w并段為。答：，}m個初始?xì)w并段采用k路平衡歸并，歸并的趟數(shù)是。 答：在敗者樹中，“敗者”是指。 答：在一次比較中，沒有上升進(jìn)入雙親結(jié)點的結(jié)點采用k路歸并構(gòu)建的敗者樹中，不計冠軍結(jié)點，敗者樹的結(jié)點總數(shù)是。 答：2k-1對于n個記錄采用逐個比較方式選取最小記錄，總的比較次數(shù)是。對于含有n個結(jié)點（不含冠軍結(jié)點）敗者樹，從中選取最小記錄，最多的比較次數(shù)是。答：n;gn)有8個長度為2、5、3、10、4、7、9、18的初始?xì)w并段，采用3路歸并，在其最佳歸并樹中需增加個虛段。 答：1有8個長度為2、5、3、10、4、7、9、18的初始?xì)w并段，采用3路歸并，在其最佳歸并樹中WPL=。 答：103三、判斷題冒泡排序在最好情況下的時間復(fù)雜度也是On。 答：錯誤采用冒泡排序進(jìn)行遞增排序時，關(guān)鍵字較小的元素總是向前移動，關(guān)鍵字較大的元素總是向后移動。 答：錯誤對n個元素進(jìn)行冒泡排序，只有在初始元素反序時，冒泡排序移動元素的次數(shù)才會達(dá)到最大值。 答：正確冒泡排序在最好情況下元素移動的次數(shù)為。 答：正確冒泡排序中，關(guān)鍵字比較的次數(shù)與初始數(shù)據(jù)序列有關(guān)，而元素移動的次數(shù)與初始數(shù)據(jù)序列無關(guān)。 答：錯誤簡單選擇排序在初始數(shù)據(jù)正序時，其時間復(fù)雜度為On。 答：錯誤簡單選擇排序中，每趟產(chǎn)生的有序區(qū)中所有元素在以后的排序中不再改變位置。 答：正確簡單選擇排序是一種不穩(wěn)定的排序方法。 答：正確n個元素采用簡單選擇排序進(jìn)行排序，關(guān)鍵字比較的次數(shù)總是nn/。 答：正確從時間性能看，堆排序總是優(yōu)于簡單選擇排序。 答：正確外排序與外部設(shè)備的特性無關(guān)。 答：錯誤內(nèi)排序過程在數(shù)據(jù)量很大時就變成了外排序過程。 答：錯誤影響外排序的時間因素主要是內(nèi)存與外存交換信息的次數(shù)。 答：正確外排序是把外存文件調(diào)入內(nèi)存，可利用內(nèi)排序方法進(jìn)行排序，因此排序所花時間取決于內(nèi)排序的時間。 答：錯誤外排序中沒有關(guān)鍵字比較。 答：錯誤在外排序過程中所有記錄的I/O次數(shù)必定相等。答：錯誤在外排序過程中，一個記錄的讀入內(nèi)存的次數(shù)和寫到外存的次數(shù)必定相等。 答：正確為了提高外排序的速度，在外排序中必須選用最快的內(nèi)排序算法。 答：錯誤通常外排序采用多路歸并排序方法，實際上也可以用其他內(nèi)排序方法代替歸并排序方法。 答：錯誤.設(shè)有5個初始?xì)w并段，每個歸并段有20個記錄，采用5路平衡歸并，若不采用敗者樹，使用逐個比較的方法選取最小記錄，則總共需要396次關(guān)鍵字比較。答：正確設(shè)有個初始?xì)w并段，每個歸并段有個記錄，采用路平衡歸并，若采用敗者樹選取最小記錄，則總共需要次關(guān)鍵字比較。答：錯誤減少初始?xì)w并段的個數(shù)，可以使外排序的時間縮短。 答：正確外排序的k路平衡歸并中，采用敗者樹時，歸并效率與k無關(guān)。 答：錯誤采用多路平衡歸并方法可以減少初始?xì)w并段的個數(shù)。 答：錯誤.磁盤上存放375000個記錄，做5路平衡歸并排序，內(nèi)存工作區(qū)能容納600個記錄，內(nèi)排序采用直接插入排序。為把所有記錄排好序，需做6趟歸并排序。答：錯誤k路平衡歸并中，敗者樹的主要作用是減少歸并的趟數(shù)。 答：錯誤k路平衡歸并建立的敗者樹中沒有度為的結(jié)點。 答：正確k路平衡歸并建立的敗者樹的結(jié)點個數(shù)正好為k（不含冠軍結(jié)點）。 答：錯誤置換選擇排序算法的作用是由一個無序文件生成一個全部有序的文件。 答：錯誤置換選擇排序算法的作用是由一個無序文件生成若干個有序的子文件。 答：正確n個記錄采用置換選擇排序算法，什么情況下產(chǎn)生的初始?xì)w并段的個數(shù)不可能為n。 答：錯誤k路最佳歸并樹在外排序中的作用是完成k路歸并排序。 答：錯誤k路最佳歸并樹在外排序中的作用是設(shè)計k路歸并排序的優(yōu)化方案。 答：正確34.k路最佳歸并樹一定是一棵k路平衡樹。 答：錯誤四、簡答題已知序列，給出采用冒泡排序方法對該序列做升序排序時的過程。 答：冒泡排序在什么情況下需要進(jìn)行的關(guān)鍵字比較次數(shù)最多，最多關(guān)鍵字比較次數(shù)是多少？ 答：冒泡排序在初始數(shù)據(jù)反序時需要進(jìn)行的關(guān)鍵字比較次數(shù)最多，此時關(guān)鍵字比較次數(shù)=n+n+…+=nn/。冒泡排序在什么情況下需要進(jìn)行的元素移動次數(shù)最少，最少元素移動次數(shù)是多少？ 答：冒泡排序在初始數(shù)據(jù)正序時需要移動的元素次數(shù)最小，此時移動的元素次數(shù)為0。在冒泡排序過程中，有的關(guān)鍵字在某趟排序中可能朝著與最終排序相反的方向移動，請舉例說明之。快速排序過程中有沒有這種現(xiàn)象出現(xiàn)？答：在冒泡排序，有的關(guān)鍵字在某趟排序中可能朝著與最終排序相反的方向移動，例如，以下冒泡排序過程中關(guān)鍵字38便是如此：49，38，13，27，97（初始關(guān)鍵字）38，13，27，49，97（第1趟排序）13，27，38，49，97（第2趟排序）但在快速排序中不會出現(xiàn)這種情況。因為在每趟排序中，比基準(zhǔn)元素大的都交換到其右邊，而基準(zhǔn)元素小的則交換到其左邊。已知序列，給出采用快速排序方法對該序列做升序排序時的過程。 答：給出數(shù)據(jù)序列采用簡單選擇排序進(jìn)行遞增排序時各趟的結(jié)果。并指出簡單選擇排序的缺陷。 答：排序過程如下：=：，，，，，，，，9=：，，，，，，，，9=：，，，，，，，，9=：，，，，，，，，9=：，，，，，，，，9=：，，，，，，，，9=：，，，，，，，，9=：，，，，，，，，9從中看出，當(dāng)=這一趟排序結(jié)束后，數(shù)據(jù)已有序，但簡單選擇排序仍要完成余下的各趟排序，也就是說簡單選擇排序沒有中途退出機制。簡述簡單選擇排序的時間性能。答：簡單選擇排序的主要時間花在關(guān)鍵字比較上，無論初始數(shù)據(jù)序列如何排列，所需關(guān)鍵字比較次數(shù)均為n(n-1)/2，所以簡單選擇排序算法的時間復(fù)雜度總是On，與初始數(shù)據(jù)序列如何排列無關(guān)。.一個有n個整數(shù)的數(shù)組n說明理由。答：該數(shù)組一定構(gòu)成一個堆，遞增有序數(shù)組構(gòu)成一個小根堆，遞減有序數(shù)組構(gòu)成一個大根堆。以遞增有序數(shù)組為例，假設(shè)數(shù)組元素為k、k、…、kn是遞增有序的，從中看出下標(biāo)越大的元素值也越大，對于任一元素k，有k<k，k<k+（<n/），這正好滿足小根堆的特性，所以構(gòu)成一個小根堆。已知關(guān)鍵字序列為，采用堆排序法對該序列進(jìn)行遞增排序，給出整個排序過程。 答：該序列對應(yīng)的完全二叉樹如圖（）所示，調(diào)整成初始堆如圖（b）所示，用堆排序方法排序的各趟過程如圖（c）～（）所示，排序結(jié)果為。.請回答下列關(guān)于堆排序中堆的一些問題：（1）堆的存儲表示是順序還是鏈?zhǔn)降模浚?）設(shè)有一個小根堆，即堆中任意結(jié)點的關(guān)鍵字均小于它的左孩子和右孩子的關(guān)鍵字。其中具有最大關(guān)鍵字的結(jié)點可能在什么地方？答：通常堆的存儲表示是順序的。因為堆排序?qū)⒋判蛐蛄锌闯墒且豢猛耆鏄洌缓髮⑵湔{(diào)整成一個堆。而完全二叉樹特別適合于采用順序存儲結(jié)構(gòu)，所以堆的存儲表示采用順序方式最合適。小根堆中具有最大關(guān)鍵字的結(jié)點只可能出現(xiàn)在葉子結(jié)點中。因為最小堆的最小關(guān)鍵字的結(jié)點必是根結(jié)點，而最大關(guān)鍵字的結(jié)點由偏序關(guān)系可知，只有葉子結(jié)點可能是最大關(guān)鍵字的結(jié)點。簡述外排序的過程。 答：外排序過程主要分為兩個階段：生成初始?xì)w并段和對初始?xì)w并段進(jìn)行歸并。生成初始?xì)w并段可以采用某種內(nèi)排序?qū)崿F(xiàn)。假設(shè)內(nèi)存大小為（內(nèi)存中每次最多可放入個記錄），要進(jìn)行外排序的文件為nd序文件out.dat的過程如下：①可以每次從外存文件nd中讀入個記錄，采用某種內(nèi)排序方法（如置換選擇算法）進(jìn)行排序來產(chǎn)生初始?xì)w并段，即產(chǎn)生ud、…、und有序文件，如圖（）所示。②采用多路歸并方法將所有初始?xì)w并段（ud、…、und文件）進(jìn)行歸并產(chǎn)生一個有序文件ud，如圖（b）所示。什么是多路平衡歸并，多路平衡歸并的目的是什么？ 答：歸并過程可以用一棵歸并樹來表示。多路平衡歸并對應(yīng)的歸并樹中，每個結(jié)點都是平衡的，即每個結(jié)點的所有子樹的高度相差不超過1。k路平衡歸并的過程是：第一趟歸并將個初始?xì)w并段歸并為/k個歸并段，以后每一趟歸并將個初始?xì)w并段歸并為/k成一個大的歸并段為止。個歸并段采用k路平衡歸并，其歸并趟數(shù)=gk，其趟數(shù)是所有歸并方案中最少的，所以多路平衡歸并的目的是減少歸并趟數(shù)。外排序中何采用k（k>）路歸并而不用二路歸并？這種技術(shù)用于內(nèi)排序有意義嗎？為什么？答：外排序中采用k（k>2）路歸并，是因為k越小，歸并趟數(shù)越多，讀寫外存次數(shù)越多，時間效率越低，所以一般應(yīng)大于最少的二路歸并。若將k路歸并的敗者樹思想用于內(nèi)排序，因其由勝者樹改進(jìn)而來，且需要輔助空間大，完全可由堆排序取代，故將其用于內(nèi)排序效率并不高第9章排序習(xí)題參考答案 一、簡答題什么是敗者樹？其主要作用是什么？用于k路歸并的敗者樹中共有多少個結(jié)點（不含冠軍結(jié)點）？ 答：敗者樹是一棵有k個葉子結(jié)點的完全二叉樹，從葉子結(jié)點開始，兩個結(jié)點進(jìn)行比較，將它們中的敗者（較大者）上升到雙親結(jié)點，勝者（較小者）參加更高一層的比較。敗者樹的主要作用是從k個記錄中選取關(guān)鍵字最小的記錄。敗者樹中有k個葉子結(jié)點，且沒有度為的結(jié)點，即n=k，n=，n=n=k，所以n=n+n+n=k。使用敗者樹后，多路平衡歸并的關(guān)鍵字比較次數(shù)與路數(shù)k無關(guān)了，因此只要內(nèi)存空間允許，k越大越好，這個敘述正確嗎？ 答：雖然增大k會有效地減少歸并樹的高度，從而減少I/O的次數(shù)，提高外排序的速度。但并不是k越大越好，因為k沖區(qū)個數(shù)。如果可供使用的內(nèi)存空間不變，這樣會減少每個輸入緩沖區(qū)的容量，使得內(nèi)、外存數(shù)據(jù)交換的次數(shù)增大，所以說當(dāng)k值過大時，雖然歸并趟數(shù)會減少，但讀寫外存的次數(shù)仍會增加。以歸并排序為例，說明內(nèi)排序和外排序的不同，說明外排序如何提高操作效率？ 答：內(nèi)排序中的歸并排序是在內(nèi)存中進(jìn)行的歸并排序，所有數(shù)據(jù)都要調(diào)入內(nèi)存，所需輔助空間為On文件合并成一個有序子文件，將每個子文件中記錄讀入內(nèi)存后的排序方法可采用多種內(nèi)排序方法。外排序的效率主要取決于讀寫外存的次數(shù)，個初始子文件采用k路平衡歸并時，其歸并趟數(shù)=gk，越大讀寫外存的次數(shù)也越大，增大和減少m都可以減少s，從而提高外排序的效率。.w（w>1），若輸入的n（n>w）個關(guān)鍵字為遞減次序，則算法的輸出是什么？答：若輸入的關(guān)鍵字為遞減次序，算法輸出為：最后一個初始?xì)w并段的長度小于或等于m，其他各初始?xì)w并段的長度為m，全部歸并段的個數(shù)為n/。.w（w>1），若輸入的n（n>w）個關(guān)鍵字為遞增次序，則算法的輸出是什么？答：若輸入的關(guān)鍵字為遞增次序，算法輸出為：只有一個初始?xì)w并段，其長度恰好為n。采用置換-選擇算法產(chǎn)生初始?xì)w并段時，如果內(nèi)存緩沖區(qū)的長度為w（w>1），則產(chǎn)生的初始?xì)w并段的最大長度和最短長度分別是多少？答：當(dāng)輸入文件遞增有序時，僅產(chǎn)生一個初始?xì)w并段，其長度為n。除了最后產(chǎn)生僅含一個記錄的初始?xì)w并段外，其他情況最短為w。給出一組關(guān)鍵字=，設(shè)內(nèi)存工作區(qū)可容納個記錄，寫出用置換選擇方法得到的全部初始?xì)w并段。答：置換選擇方法得到的結(jié)果如下：歸并段：。歸并段：。.在一個無序文件中存放有若干個記錄，其中所有記錄構(gòu)成的關(guān)鍵字序列為。設(shè)緩沖區(qū)能有容納個記錄的容量。按置換選擇方法求初始?xì)w并段。請寫出各初始?xì)w并段中選出的關(guān)鍵字。答：置換選擇方法得到的結(jié)果如下：歸并段：，關(guān)鍵字為。歸并段：，關(guān)鍵字為。歸并段，，關(guān)鍵字為。.給出一組關(guān)鍵字=，采用置換選擇方法得到的全部初始?xì)w并段?；卮鹨韵聠栴}：（）若內(nèi)存工作區(qū)容量=，給出相應(yīng)的結(jié)果。（2）若內(nèi)存工作區(qū)容量w=2，給出相應(yīng)的結(jié)果。（3）若內(nèi)存工作區(qū)容量w=5，給出相應(yīng)的結(jié)果。（4）若內(nèi)存工作區(qū)容量w=8，給出相應(yīng)的結(jié)果。答：（1）w=1時共產(chǎn)生10個初始?xì)w并段，即為{10}、{9}、{8}、{7}、{6}、{5}、{4}、{3}、{2}、{1}。（）=時共產(chǎn)生個初始?xì)w并段，即為、、、、。（）=時共產(chǎn)生個初始?xì)w并段，即為、。（）=時共產(chǎn)生個初始?xì)w并段，即為、。外排序中的敗者樹和堆有什么區(qū)別？若用敗者樹求k個數(shù)中的最小值，在某次比較中得到>b，那么誰是敗者？ 答：外排序中的“敗者樹”和堆的區(qū)別如下：敗者樹是在雙親結(jié)點中記下剛進(jìn)行比較的敗者（較大者），讓勝者（較小者）去參加更高一層的比較。而堆可看作是一種“勝者樹”，即雙親結(jié)點表示其左、右孩子中的勝者。敗者樹中參加比較