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

第9章排序習(xí)題參考答案 一、單選題ABCDABCDn-1n+1n/2.nn/2ABCABCD排序的總趟數(shù)元素的移動(dòng)次數(shù)使用輔助空間的數(shù)量元素之間的比較次數(shù)ABCABCD冒泡排序直接插入排序希爾排序二路歸并排序?qū)φ麛?shù)序列（8，9，10，4，5，6，20，1，2）進(jìn)行遞增排序，采用每趟冒出一個(gè)最小元素的冒泡排序算法，需要進(jìn)行的趟數(shù)是 。AABCD468.對(duì)一組數(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對(duì)關(guān)鍵字序列（，，，，，，，ABCD.，，，)602).，，，)8，，)C.，，，)8，，).，，，)8，，)ABCABCD快速排序在所有排序方法中為最快，而且所需輔助空間也最少在快速排序中，不可以用隊(duì)列替代?？焖倥判虻目臻g復(fù)雜度為On)快速排序在待排序的數(shù)據(jù)隨機(jī)分布時(shí)效率最高.n（n為大于10000的整數(shù)）個(gè)無序元素，希望用最快速度從中選擇前k（1≤k≤n）個(gè)關(guān)鍵字最小的元素，在以下排序方法中應(yīng)選擇 。AABCD快速排序希爾排序二路歸并排序直接插入排序ABCABCD直接插入排序冒泡排序簡單選擇排序都一樣ABCABCDn2n2n-1n-1ABCDABCD.（，，，，，，，，，，）.（，，，，，，，，，，）C.（，，，，，，，，，，）.（，，，，，，，，，，）ABCD有一個(gè)整數(shù)序列為（，，，，，，，ABCD.（，，，，，，，）.（，，，，，，，）C.（，，，，，，，）.ABCABCDngngn+1n2ABCABCD快速排序二路歸并排序基數(shù)排序堆排序ABCABCD10000個(gè)實(shí)數(shù)1000個(gè)由字母、數(shù)字和其他字符組成的字符串個(gè)n類型的整數(shù)10000個(gè)100以內(nèi)的正整數(shù)對(duì)給定的關(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)行排序，所以外排序所花時(shí)間完全由采用的內(nèi)排序決定外排序分為產(chǎn)生初始?xì)w并段和多路歸并兩個(gè)階段外排序并不涉及文件的讀寫操作外排序完全可以由內(nèi)排序來替代將一個(gè)由置換-選擇排序方法得到的輸出文件F1作為輸入文件再次進(jìn)行置換-選擇排序，得到輸出文件F2，問F1和F2的差異是 。AABCDF2中歸并段的最大長度增大F2和F1無差異歸并段個(gè)數(shù)及各歸并段長度均不變，但F2中可能存在與F1不同的歸并段AB采用敗者樹進(jìn)行k路平衡歸并的外排序算法，其總的歸并效率與k 。AB有關(guān)無關(guān)ABCABCD1/k/kgkmAB設(shè)有100初始?xì)w并段，如采用k路平衡歸并3趟完成排序，則k值是 。AB56CDCD8ABm個(gè)初始?xì)w并段采用k路平衡歸并時(shí)，構(gòu)建的敗者樹中共有 個(gè)結(jié)點(diǎn)（不計(jì)冠軍結(jié)點(diǎn)）。AB2k-1.2kCDC.CD.1ABCABCD0123ABCABCD該排序算法不允許有相同的關(guān)鍵字記錄該排序算法允許有相同的關(guān)鍵字記錄平均時(shí)間為Ongn的排序方法以上都不對(duì)ABCABCD經(jīng)過排序后，能使關(guān)鍵字相同的元素保持原順序中的相對(duì)位置不變經(jīng)過排序后，能使關(guān)鍵字相同的元素保持原順序中的絕對(duì)位置不變排序算法的性能與被排序元素的數(shù)量關(guān)系不大排序算法的性能與被排序元素的數(shù)量關(guān)系密切ABCABCD這兩個(gè)元素的前后位置不發(fā)生變化這兩個(gè)元素的前后位置一定發(fā)生變化這兩個(gè)元素的位置不發(fā)生變化這兩個(gè)元素的前后位置可能發(fā)生變化ABCABCD穩(wěn)定的排序方法優(yōu)于不穩(wěn)定的排序方法，因?yàn)榉€(wěn)定的排序方法效率較高對(duì)同一個(gè)順序表使用不同的排序方法進(jìn)行排序，得到的排序結(jié)果可能不同排序方法都是在順序表上實(shí)現(xiàn)的，在鏈表上無法實(shí)現(xiàn)排序方法在順序表上實(shí)現(xiàn)的排序方法在鏈表上也可以實(shí)現(xiàn)ABCABCD二路歸并排序拓?fù)渑判蚨雅判蛑苯硬迦肱判駻BCABCD簡單選擇排序冒泡排序歸并排序堆排序ABCABCD希爾選擇快速排序歸并排序堆排序ABCD下列排序方法中，輔助空間為OnABCD希爾選擇冒泡排序堆排序歸并排序A下列四種排序中（）的空間復(fù)雜度最大。 A直接插入排序BBCD堆排序二路歸并排序ABCABCDABCABCD快速排序歸并排序基數(shù)排序堆排序ABCABCD快速排序堆排序希爾排序基數(shù)排序ABCABCD10n52ABCABCD10n52ABCABCD10000個(gè)實(shí)數(shù)1000個(gè)由字母、數(shù)字和其他字符組成的字符串個(gè)n類型的整數(shù)10000個(gè)100以內(nèi)的正整數(shù)ABCABCD直接插入排序和快速排序直接插入排序和冒泡排序簡單選擇排序和歸并排序歸并排序和冒泡排序ABCABCD快速排序冒泡排序堆排序希爾排序ABCABCD0nn-13n(n-1)/2ABCABCD01n3n(n-1)/2二、編程題OJ—N排序問題時(shí)間限制：，空間限制：。問題描述：：一個(gè)序列中的未排序的度量是相對(duì)于彼此順序不一致的條目對(duì)的數(shù)量，例如，在字母序列EC中，該度量為，因?yàn)镈大于右邊是個(gè)字母，E大于其右邊的個(gè)字母。該度量稱為該序列的逆序數(shù)。序列CE只有一個(gè)逆序?qū)Γ‥和），它幾乎被排序好了，而序列Q有個(gè)逆序?qū)?，它是未排序的，恰好是反序。你需要?duì)若干個(gè)N序列（僅包含個(gè)字母、C、和的字符串）分類，注意是分類而不是按字母順序排序，而是按照“最多排序”到“最小排序”的順序排列，所有DNA序列的長度都相同。輸入格式：第一行包含兩個(gè)整數(shù)，n（0<n≤50）表示字符串長度，m（0<m≤100）表示字符串個(gè)數(shù)。后面是m行，每行包含一個(gè)長度為n的字符串。輸出格式：按“最多排序”到“最小排序”的順序輸出所有字符串。若兩個(gè)字符串的逆序?qū)€(gè)數(shù)相同，按原始順序輸出它們。答：prtvu*;csEeype{ntv; //存放r的逆序數(shù)nt; //存放字符串的下標(biāo)i}pubccsn{cntN=;cnt=;cntn; //相鄰整數(shù)的最小交換數(shù)量cn]=newnN; //存放整數(shù)序cvdergechrntntdnthgh)//兩個(gè)相鄰有序段歸并{nt=;ntntk=;chrb=newchrhgh+; //開辟臨時(shí)空間hei<=d&j<=hgh) //二路歸并：d、d+hgh=>b{>){bk++=++;n+=d+; /計(jì)逆序數(shù)}eebk++=++;}hei<=d)bk++=++;hej<=hgh)bk++=++;rntk=;k1<k;k++) //bk=>hgh]+k=bk;}cvdergeSrchrntnt)//二路歸并排序{>=)reurn; //的長度為或者時(shí)返回nt=+/; //取中間位置mergeSr; //對(duì)前子表排序ergeSr+; //對(duì)后子表排序erge; //將兩個(gè)有序子表合并成一個(gè)有序表}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相同時(shí)按reurn;ee //v不相同時(shí)按vreurnvv;}});rnt=;i<;++) //輸出結(jié)果Syeuprn"%\n"rb;}}.OJ—求中位數(shù)問題時(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中每行包含一個(gè)整數(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í)間限制：，空間限制：。問題描述：：對(duì)于這個(gè)問題，你需要編寫一個(gè)程序讀取一系列整數(shù)，在讀取每個(gè)奇數(shù)序號(hào)的整數(shù)后輸出到目前為止接收的整數(shù)的中值（中位數(shù)）。輸入格式：第一行輸入包含一個(gè)整數(shù)t（1≤t≤1000）表示數(shù)據(jù)集個(gè)數(shù)。每個(gè)數(shù)據(jù)集的第一行包含數(shù)據(jù)集編號(hào)，后跟一個(gè)空格，后跟一個(gè)奇數(shù)十進(jìn)制整數(shù)（≤≤），表示要處理的有符號(hào)整數(shù)的個(gè)數(shù)，數(shù)據(jù)集中的其余行由每行個(gè)整數(shù)組成，由單個(gè)空格分隔。數(shù)據(jù)集中的最后一行可能包含少于10個(gè)整數(shù)。輸出格式：對(duì)于每個(gè)數(shù)據(jù)集，第一行輸出包含數(shù)據(jù)集編號(hào)，單個(gè)空格和中位數(shù)個(gè)數(shù)（應(yīng)該是輸入整數(shù)個(gè)數(shù)的一半加一），將在以下行中輸出中位數(shù)，每行10個(gè)由單個(gè)空格分隔。最后一行可能少于10個(gè)元素，但至少有1個(gè)元素。輸出中沒有空行。答：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) //若小根堆元素個(gè)數(shù)較少erbgp; //取出bg的堆頂元素插入到中e>bge+) //若比bg至少多個(gè)元素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ù)序號(hào)的整數(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)該被忽略掉，除非這個(gè)整數(shù)就是由若干個(gè)組成的，這時(shí)這個(gè)整數(shù)就是）。你的任務(wù)是對(duì)這些分割得到的整數(shù)，依從小到大的順序排序輸出。輸入格式：輸入包含多組測試用例，每組輸入數(shù)據(jù)只有一行數(shù)字（數(shù)字之間沒有空格），這行數(shù)字的長度不大于1000。輸入數(shù)據(jù)保證分割得到的非負(fù)整數(shù)不會(huì)大于，輸入數(shù)據(jù)不可能全由組成。輸出格式：對(duì)于每個(gè)測試用例，輸出分割得到的整數(shù)排序的結(jié)果，相鄰的兩個(gè)整數(shù)之間用一個(gè)空格分開，每組輸出占一行。答：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; //對(duì)benr=rue;rnt=;i<cn;++) //輸出結(jié)果{if(first){Syeuprn;r=e;}eeSyeuprn""+;}Syeuprnn;}}}HDU1862—EXCEL10000ms，空間限制：32768K。問題描述：：Exce可以對(duì)一組紀(jì)錄按任意指定列排序?，F(xiàn)請(qǐng)你編寫程序?qū)崿F(xiàn)類似功能。答：prtvuScnner;prtvu*;csSud //學(xué)生元素類{ntn; //學(xué)號(hào)Srngne; //姓ntgrde; //成績pubcSudntnSrngnentgrde) //構(gòu)造方法{hn=n;hne=ne;hgrde=grde;}pubcvddp //輸出一個(gè)學(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é)號(hào)遞增排序{reurnnn;}});eefc==)rryrnnewCprr<Sud>){pubcntcpreSudSud){fnecprene==)//姓名相同reurnnn; //按按學(xué)號(hào)遞增排序ee //否則按姓名非遞減排序reurnnecprene;}});ee //c==的情況rryrnnewCprr<Sud>{pubcntcpreSudSud)//按成績的非遞減排序{fgrde==grde) //成績相同reurnnn; //按按學(xué)號(hào)遞增排序ee //否則按成績的非遞減排序reurngrdegrde;}});Syeuprnn"Ce"+c+":"; //rnt=;i<n;++)dp;c++;}}}H—按絕對(duì)值排序問題時(shí)間限制：，空間限制：。問題描述：：輸入n（n≤100）個(gè)整數(shù)，按照絕對(duì)值從大到小排序后輸出。題目保證對(duì)于每一個(gè)測試實(shí)例，所有的數(shù)的絕對(duì)值都不相等。輸入格式：輸入數(shù)據(jù)有多組，每組占一行，每行的第一個(gè)數(shù)字為n，接著是n個(gè)整數(shù)，n=0表示輸入數(shù)據(jù)的結(jié)束，不做處理。輸出格式：對(duì)于每個(gè)測試實(shí)例，輸出排序后的結(jié)果，兩個(gè)數(shù)之間用一個(gè)空格隔開。每個(gè)測試實(shí)例占一行。答：prtvuScnner;prtvu*;pubccsn{cnlntN=;cn]=newnN;cntrnntnt)//按表首元素為基準(zhǔn)進(jìn)行劃分{nt==;ntbe=; //以表首元素為基準(zhǔn)he=) //從表兩端交替向中間遍歷直至=為止{he>i&hb)<=hbbe); //從后向前遍歷找一個(gè)小于基準(zhǔn)的]f>){=; //前移覆蓋]++;}hei=hbbe)++; //從前向后遍歷找一個(gè)大于基準(zhǔn)的]if(i{=; //后移覆蓋]j--;}}=be; //基準(zhǔn)歸位returni; //返回歸位的位置}cvdQuckSrntnt)//對(duì)的元素進(jìn)行快速排序(s{nt=rn;QuckSr; //對(duì)左子表遞歸排序QuckSr+; //對(duì)右子表遞歸排序}}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); //從后向前遍歷找一個(gè)小于基準(zhǔn)的]f>){=; //前移覆蓋]++;}hei=hbbe)++; //從前向后遍歷找一個(gè)大于基準(zhǔn)的]if(i{=; //后移覆蓋]j--;}}=be; //基準(zhǔn)歸位returni; //返回歸位的位置}cvdQuckSrntnt)//對(duì)的元素進(jìn)行快速排序(s{nt=rn;QuckSr; //對(duì)左子表遞歸排序QuckSr+; //對(duì)右子表遞歸排序}}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)參賽者完成演講時(shí)評(píng)委將對(duì)他的表演進(jìn)行評(píng)分。工作人員刪除最高分和最低分，并計(jì)算其余的平均分作為參賽者的最終成績。這是一個(gè)容易出問題的問題，因?yàn)橥ǔＶ挥袔酌u(píng)委?？紤]上面問題的一般形式，給定n個(gè)正整數(shù)，刪除最大的n1個(gè)和最小的n2個(gè)，并計(jì)算其余的平均值。答：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)); } }三、簡答題簡述何時(shí)使用穩(wěn)定的排序算法。 答：如果排序數(shù)據(jù)存在相同關(guān)鍵字的元素，而且要求排序后不改變這些相同關(guān)鍵字記錄的相對(duì)位置，此時(shí)需要使用穩(wěn)定的排序算法。如張三的成績是82，李四成績也是82，而張三的記錄在李四的記錄的前面，要求按成績遞減排序，排好序后，張三的記錄仍在李四的記錄的前面，這就需要使用穩(wěn)定的排序算法。另一個(gè)用途是多關(guān)鍵字排序，如學(xué)生記錄有姓名、數(shù)學(xué)、語文成績和總分，要求這樣排名次，先按總分，總分相同再按數(shù)學(xué)成績。可以這樣排序，先采用任一種排序方法按數(shù)學(xué)成績遞減排序，再選擇一種穩(wěn)定的排序方法按總分排序，后者一定用穩(wěn)定的排序方法，否則會(huì)出現(xiàn)總分相同，數(shù)學(xué)成績低的排到前面了。排序方法的穩(wěn)定性受什么因素影響？ 答：在排序過程中，需要以一個(gè)較大的間隔互換元素，或把元素隔空搬運(yùn)一段較大距離時(shí)，排序方法一定不穩(wěn)定，它可能會(huì)把原先排在前面的元素搬到具有相同關(guān)鍵字值的另一個(gè)元素的后面，改變了相對(duì)位置。證明：對(duì)于一個(gè)長度為n的線性表基于比較方法進(jìn)行排序，至少需要進(jìn)行ngn次比較。 答：證明：對(duì)于一個(gè)長度為n的線性表基于比較方法進(jìn)行排序，元素兩兩比較構(gòu)成的判定樹可以近似看成是一棵滿二叉樹，其中葉子結(jié)點(diǎn)是某種排序結(jié)果，由于n個(gè)元素總共有n!種不同的排列，所以葉子結(jié)點(diǎn)個(gè)數(shù)為n!，一次排序恰好經(jīng)過從根結(jié)點(diǎn)到某個(gè)葉子結(jié)點(diǎn)的路徑，比較次數(shù)為樹的高度，而h=gn≈ngn，所以至少需要進(jìn)行ngn次比較。給出關(guān)鍵字序列采用直接插入排序時(shí)各趟的結(jié)果。答：直接插入排序算法在含有n個(gè)元素的初始數(shù)據(jù)正序、反序和數(shù)據(jù)全部相等時(shí)，時(shí)間復(fù)雜度各是多少？ 答：含有n個(gè)元素的初始數(shù)據(jù)正序時(shí)，直接插入排序算法的時(shí)間復(fù)雜度為On。含有n個(gè)元素的初始數(shù)據(jù)反序時(shí)，直接插入排序算法的時(shí)間復(fù)雜度為On含有n個(gè)元素的初始數(shù)據(jù)全部相等時(shí)，直接插入排序算法的時(shí)間復(fù)雜度為On。已知序列，采用二路歸并排序法對(duì)該序列作升序排序時(shí)的每一趟的結(jié)果。 答：.兩個(gè)各含有n個(gè)元素的有序序列歸并成一個(gè)有序序列時(shí)，關(guān)鍵字比較次數(shù)為n～2n-1，也就是說關(guān)鍵字比較次數(shù)與初始序列有關(guān)。為什么通常說二路歸并排序與初始序列無關(guān)呢？答：二路歸并排序中使用了輔助空間，需要先將所有歸并數(shù)據(jù)移到中，然后再復(fù)制到中，所以每一趟移動(dòng)元素的次數(shù)n，共需gn趟排序，總的移動(dòng)次數(shù)總是Ongn并排序與初始序列無關(guān)。二路歸并排序中每一趟排序都要開辟On的輔助空間，共需gn趟排序，為什么總的輔助空間仍為On？ 答：二路歸并排序中每一趟排序都要開辟On的輔助空間，但在一趟排序結(jié)束后，這些輔助空間都被釋放了，所以總的輔助空間仍為On.在堆排序、快速排序和歸并排序中：（1）若只從存儲(chǔ)空間考慮，則應(yīng)首先選取哪種排序方法，其次選取哪種排序方法，最后選取哪種排序方法？（2）若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取哪種排序方法？（3）若只從最壞情況下的排序時(shí)間考慮，則不應(yīng)選取哪種排序方法？答：若只從存儲(chǔ)空間考慮，則應(yīng)首先選取堆排序（空間復(fù)雜度為O），其次選取快速排序（空間復(fù)雜度為Ogn），最后選取歸并排序（空間復(fù)雜度為On）。若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取歸并排序。因?yàn)闅w并排序是穩(wěn)定的，其他兩種排序方法是不穩(wěn)定的。若只從最壞情況下的排序時(shí)間考慮，則不應(yīng)選取快速排序方法。因?yàn)榭焖倥判蚍椒ㄗ顗那闆r下的時(shí)間復(fù)雜度為On，其他兩種排序方法在最壞情況下的時(shí)間復(fù)雜度為O(nlog2n)。以歸并算法為例，比較內(nèi)排序和外排序的不同，說明外排序如何提高操作效率。 答：內(nèi)排序中的歸并排序是在內(nèi)存中進(jìn)行的歸并排序，輔助空間為O(n)。外部歸并排序是將外存中的多個(gè)有序子文件合并成一個(gè)有序子文件，將每個(gè)子文件中記錄讀入內(nèi)存后的排序方法可采用多種內(nèi)排序方法。外部排序的效率主要取決于讀寫外存的次數(shù)，即歸并的趟數(shù)。因?yàn)闅w并的趟數(shù)s=logkm，其中，m是歸并段個(gè)數(shù)，k是歸并路數(shù)。增大k和減少m都可減少歸并趟數(shù)。實(shí)際應(yīng)用中通過敗者樹進(jìn)行k（k≥3）路平衡歸并和置換-選擇排序減少m，來提高外部排序的效率。給出關(guān)鍵字序列按低位到高位進(jìn)行基數(shù)排序時(shí)每一趟的結(jié)果。 答：給出關(guān)鍵字序列按高位到低位進(jìn)行基數(shù)排序時(shí)每一趟的結(jié)果。 答：排序結(jié)果如圖所示，從中看到，最終的排序結(jié)果是錯(cuò)誤的，所以對(duì)于數(shù)值數(shù)據(jù)排序時(shí)只能是按低位到高位進(jìn)行基數(shù)排序。.有n個(gè)不同的英文單詞（均為小寫字母），它們的長度相等，均為m。若n=50，m<5，試問采用什么排序方法時(shí)其時(shí)間復(fù)雜度最??？為什么？答：采用基數(shù)排序方法最好，這里r=，其時(shí)間復(fù)雜度為On+，其他排序方法的時(shí)間復(fù)雜度最小為Ongn，當(dāng)n=，<5時(shí)，n+<ngn，所以基數(shù)排序方法最好。問在一般情況下，直接插入排序、簡單選擇排序和冒泡排序的過程中，所需元素交換次數(shù)最少的是哪種排序方法？ 答：對(duì)于直接插入排序，有序區(qū)分別有、、…、n個(gè)元素，平均交換一半的元素，所以平均元素交換次數(shù)rd/ebeddng/eObecbn>++…n≈n/。對(duì)于簡單選擇排序，最多只進(jìn)行n-1次元素交換對(duì)于冒泡排序，平均每趟交換一半的元素，平均排序n/趟，所以平均元素交換次數(shù)=<Obec:rd/ebeddng/eObecbn>n-+n+…n/+≈n/。所以元素交換次數(shù)最少的是簡單選擇排序。.在下列情況下，選擇哪種內(nèi)排序算法比較合適？說明理由。（1）需要對(duì)1000個(gè)大型記錄進(jìn)行排序，記錄本身存儲(chǔ)在外存中，在內(nèi)存中只保研了所有記錄的關(guān)鍵字。關(guān)鍵字之間的比較非?？?，但移動(dòng)代價(jià)很大，因?yàn)橐坏┮苿?dòng)一個(gè)關(guān)鍵字，相應(yīng)的外存中的記錄也要移動(dòng)，這將涉及很多磁盤塊的移動(dòng)。（2）已知一個(gè)包含了5000個(gè)單詞的列表已按字母順序排好序，需要再進(jìn)行一次檢查，確保所有的單詞已經(jīng)排好序。（3）需要將500張隨機(jī)排列的圖書卡片按照字母順序排序。答：選擇簡單選擇排序，該排序方法可以達(dá)到盡量少地移動(dòng)記錄，雖然比較次數(shù)達(dá)到On，但是相對(duì)外存的處理時(shí)間來說，不是關(guān)鍵因素。因?yàn)檎麄€(gè)表已經(jīng)基本有序，所以應(yīng)該采用直接插入排序。因?yàn)槭请S機(jī)排列的卡片，所以選擇快速排序比較合適。四、填空題如果一組數(shù)據(jù)采用某種排序方法進(jìn)行排序，排序后相同關(guān)鍵字的元素的相對(duì)位置不發(fā)生改變，稱該排序方法是。 答：穩(wěn)定的若不考慮基數(shù)排序，在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的。和記錄的。 答：比較;移動(dòng)每次從無序子表中取出一個(gè)元素，通過依次比較把它插入到有序子表的適當(dāng)位置，此種排序方法稱為。 答：直接插入排序?qū)衝個(gè)元素的數(shù)據(jù)序列進(jìn)行直接插入排序（采用《教程》中的算法），在最好情況下移動(dòng)元素的個(gè)數(shù)是，關(guān)鍵字比較的次數(shù)是。答：2(n-1);n-1對(duì)含有n個(gè)元素的數(shù)據(jù)序列進(jìn)行直接插入排序（采用《教程》中的算法），在最壞情況下移動(dòng)元素的個(gè)數(shù)是，關(guān)鍵字比較的次數(shù)是。答：nn+/;nn/2數(shù)據(jù)序列采用二路歸并排序方法進(jìn)行遞增排序，經(jīng)過兩趟排序后的結(jié)果是。答：}數(shù)據(jù)序列采用二路歸并排序方法進(jìn)行遞增排序，所需要關(guān)鍵字比較次數(shù)是。答：12.數(shù)據(jù)序列中有 個(gè)元素，采用二路歸并排序方法進(jìn)行遞增排序，最好情況下所需要關(guān)鍵字比較次數(shù)是。答：在快速排序、堆排序、歸并排序中，排序是穩(wěn)定的。答：歸并排序二路歸并排序算法的空間復(fù)雜度是。答：On)題：基數(shù)排序主要適用于排序的情況。答：多關(guān)鍵字題：基數(shù)排序與其他幾種排序方法的區(qū)別是。答：基數(shù)排序采用分配和收集實(shí)現(xiàn)，不需要進(jìn)行關(guān)鍵字的比較，而其他幾種排序方法都是通過關(guān)鍵字的比較實(shí)現(xiàn)的題：對(duì)數(shù)據(jù)序列采用最低位優(yōu)先的基數(shù)排序，第一趟排序后的結(jié)果是。答：}題：對(duì)數(shù)據(jù)序列采用最低位優(yōu)先的基數(shù)排序，第趟排序后的結(jié)果是。答：}題：基數(shù)排序的空間復(fù)雜度是。答：Or（r為排序的基數(shù)）五、判斷題一組數(shù)據(jù)序列為………，與的關(guān)鍵字相同，采用某種排序方法排序后變?yōu)椤?，則該排序算法是穩(wěn)定的。答：錯(cuò)誤2.當(dāng)待排序的元素很大時(shí)，為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響算法時(shí)間復(fù)雜度的主要因素。 答：錯(cuò)誤內(nèi)排序方法要求數(shù)據(jù)一定以順序表方式存儲(chǔ)。 答：錯(cuò)誤所有內(nèi)排序算法中的比較次數(shù)與初始元素序列的排列無關(guān)。 答：錯(cuò)誤排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。 答：錯(cuò)誤二路歸并排序算法是穩(wěn)定的。 答：正確對(duì)于不同的初始數(shù)據(jù)序列，二路歸并排序算法中關(guān)鍵字比較次數(shù)有所不同。 答：正確二路歸并排序算法的時(shí)間復(fù)雜度與初始數(shù)據(jù)序列的順序無關(guān)。 答：正確二路歸并排序算法的最好時(shí)間復(fù)雜度為On。 答：錯(cuò)誤n個(gè)元素采用二路歸并排序算法，總的趟數(shù)為n。 答：錯(cuò)誤基數(shù)排序只適用于以數(shù)字為關(guān)鍵字的情況，不適用以字符串為關(guān)鍵字的情況。 答：錯(cuò)誤基數(shù)排序與初始數(shù)據(jù)的次序無關(guān)。 答：正確基數(shù)排序與初始數(shù)據(jù)中關(guān)鍵字的大小無關(guān)。 答：錯(cuò)誤快速排序、簡單選擇排序和堆排序都與初始序列次序無關(guān)。 答：錯(cuò)誤直接插入排序、冒泡排序和簡單選擇排序在最好情況下的時(shí)間復(fù)雜度均為On。 答：錯(cuò)誤第9章排序習(xí)題參考答案 一、單選題.對(duì)一組數(shù)據(jù)進(jìn)行排序，若前三趟的結(jié)果如下：第一趟：8第二趟：8第三趟：8則采用的排序方法可能是(。AABCD希爾排序歸并排序基數(shù)排序

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