上傳第10章排序習題

1、答案】B9.1選擇題1從末排序的序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在排序序列的合適位置，該排序方法稱為（）排序法。A）插入B）選擇C）希爾D）二路歸并【答案】A下面各種排序方法中，最好情況下時間復雜度為0（n）的是（）A）快速排序B）直接插入排序C）堆排序D）歸并排序【答案】B下面給出的四種排序法中，（）排序是不穩(wěn)定排序法。A）插入B）冒泡C）二路歸并D）堆【答案】D快速排序方法在（）情況下最不利于發(fā)揮其長處。A）要排序的數(shù)據(jù)量太大B）要排序的數(shù)據(jù)中含有多個相同值C）要排序的數(shù)據(jù)已基本有序D）要排序的數(shù)據(jù)個數(shù)為奇數(shù)【答案】C7.對記錄的關(guān)鍵碼50，26，38，8

2、0，70，90，8，30，40，20進行排序，各趟排序結(jié)束時的結(jié)果為：50,26,38,80,70,90,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是（）A）快速排序B）基數(shù)排序C）希爾排序D）歸并排序【答案】C8在文件“局部有序”或文件長度較小的情況下，最佳內(nèi)部排序方法是（）A）直接插入排序B）冒泡排序C）簡單選擇排序D）歸并排序【答案】A【解析】當待排序列基本有序時，對冒泡排序來說，若最大關(guān)鍵字位于序列首部，則每趟排序僅能使其“下

3、沉”一個位置，要使其下沉到底部仍需n-1趟排序，也即時間復雜度仍為。（）。而對簡單選擇排序來說，其比較次數(shù)與待排序列的初始狀態(tài)無關(guān)；歸并排序要求待排序列已經(jīng)部分有序，而部分有序的含義是待排序列由若干有序的子序列組成，即每個子序列必須有序，并且其時間復雜度為O（nlogn）；直接插入排序在待排序列基本有序時，每趟的比較次數(shù)大為降低，也即2n-1趟比較的時間復雜度由O（n2）降至O（n）。9在下列算法中，（）算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。A）堆排序B）冒泡排序C）插入排序D）快速排序【答案】C【解析】在插入排序中，如果待排序列中的最后一個元素其關(guān)鍵字值為

4、最小，則在最后一趟開始之前，前n-1個排好序的元素都不在其最終位置上，與排好序后的位置相差一個位置。因此，選C。10設(shè)有5000個無序的元素，希望用最快速度挑選出其中前10個最大的元素，在以下的排序方法中，采用（）方法最好A）快速排序B）堆排序C）基數(shù)排序【解析】用堆排序最好，因為堆排序不需要等整個排序結(jié)束就可挑出前10個最大元素，而快速排序和基數(shù)排序都需等待整個排序結(jié)束才能知道前10個最大元素。11對給出的一組關(guān)鍵字14，5，19，20，11，19。若按關(guān)鍵字非遞減排序，第一趟排序結(jié)果為14，5，19，20，11，19，問采用的排序算法是（）A）簡單選擇排序B）快速排序C）希爾排序D）二路歸

5、并排序【答案】C12以下序列不是堆的是（）A）100,85,98,77,80,60,82,40,20,10,66B）100,98,85,82,80,77,66,60,40,20,10C）10,20,40,60,66,77,80,82,85,98,100D）100,85,40,77,80,60,66,98,82,10,20【答案】D【解析】根據(jù)堆采用完全二叉樹的順序存儲形式及堆的特點，因第一個結(jié)點即根結(jié)點關(guān)鍵字值最大，則應建立一個大根堆，但依據(jù)此數(shù)據(jù)序列建立起堆后關(guān)鍵字值為40的左右孩子結(jié)點分別為60、66，不符合大根堆特點。13下面排序方法中，關(guān)鍵字比較次數(shù)與記錄的初始排列無關(guān)的是（）A）希爾

6、排序B）冒泡排序C）直接插入排序D）直接選擇排序【答案】D【解析】如果初始排列基本有序，則對希爾排序來說，前幾趟的插入工作大為減少。冒泡排序和直接插入排序都與初始排序序列有關(guān)，只有直接選擇排序與初始序列無關(guān)故選D。14一組記錄的關(guān)鍵字為45，80，55，40，42，85，則利用堆排序的方法建立的初始堆為（）答案】答案】答案】B80,45,50,40,42,8585,80,55,40,42,4585,80,55,45,42,4085,55,80,42,45,40【答案】B16n個元素進行冒泡排序的過程中，最好情況下的時間復雜度為()O(1)B)O(log2n)C)O(n2)D)O(n)【答案】D

7、【解析】最好情況下至少需要一趟排序，即比較n-1次，故選D。17n個元素進行快速排序的過程中，第一次劃分最多需要移動()次元素(包括開始將基準元素移到臨時變量的那一次)。A)n2B)n-1C)nD)n+l【答案】D【解析】移動次數(shù)最多的情況是對n-1個元素比較時都需移動，加上開始將基準元素移到臨時變量以及由臨時變量移至正確位置的二次即共需n+1次故選D18下述幾種排序方法中，要求內(nèi)存量最大的是()A)插入排序B)選擇排序C)快速排序D)歸并排序【答案】D【解析】插入排序和選擇排序需要的輔助空間為0(1),快速排序需要的輔助空間為O(log2n)，歸并排序需要的輔助空間為0(n),因此選D。19

8、下面排序方法中，時間復雜度不是0(n2)的是()A)直接插入排序B)二路歸并排序C)冒泡排序D)直接選擇排序【解析】直接插入排序、冒泡排序和直接選擇排序的時間復雜度為0（n2）,而二路歸并排序的時間復雜度為0（nlog2n）,故選B。20對下列4個序列用快速排序方法進行排序,以序列的第1個元素為基準進行劃分。在第1趟劃分過程中,元素移動次數(shù)最多的是序列（）A）70,75,82,90,23,16,10,68B）70,75,68,23,10,16,90,82C）82,75,70,16,10,90,68,23D）23,10,16,70,82,75,68,90【答案】A【解析】快速排序第一趟劃分的方法

9、是：將第1個元素放入最終排好序序列中的正確位置上,則在這個位置右邊小于該元素值的元素都將移到其左邊,在這個位置左邊大于該元素值的元素都將其移到其右邊。由此得到A需移動的元素最多,故選A。9.2填空題2在堆排序、快速排序和歸并排序中,若從節(jié)省存儲空間考慮,則應首先選取方法，其次選取方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應先方法；若只從平均情況下排序的速度來考慮，則選擇方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應選取方法?！敬鸢浮浚?）堆排序（2）快速排序（3）歸并排序（4）快速（5）堆對n個元素的序列進行冒泡排序，最少的比較次數(shù)是，此時元素的排列情況為，在情況下比較次數(shù)最多，其比較次數(shù)為

10、（4）。（1）n-1（2）從小到大排序（3）元素從大到小排列（4）n（n-1）/2【解析】初始元素正序時，第一趟比較n-1次，并無數(shù)據(jù)交換，則不再比較，故只比較n-1次。若反序，則比較（n-1）+（n-2）+（n-3）+.+2+l共n（n-1）/2次。4希爾排序是把記錄按下標的一定增量分組，對每組記錄進行直接插入排序，隨著增量，所分成的組包含的記錄越來越多，當增量的值為時，整個數(shù)組合為一組。TOC o 1-5 h z【答案】（1）減少（2）15.直接插入排序需借助的存儲單元個數(shù)（空間復雜度）為，最好情況下直接插入排序的算法時間復雜度為，最壞情況下該算法的時間復雜度為。【答案】（1）1（2）O（

11、n）（3）O（n2）6對n個數(shù)據(jù)進行簡單選擇排序，所需進行的關(guān)鍵字間的比較次數(shù)為，時間復雜度為?！敬鸢浮浚?）n（n-1）/2（2）O（n2）7對于關(guān)鍵字序列（12，13，11，18，60，15，7，20，25，100），用篩選法建堆，必須從鍵值為的關(guān)鍵字開始。【答案】60【解析】建堆必須從n/2結(jié)點開始，而10/2=5位置的結(jié)點值為60,故填60。8對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到已排序的有序表時，為尋找其插入位置需比較次。【答案】3【解析】當把第7個記錄60插入到有序表時，則前6個記錄已經(jīng)有序，此時記錄60由后向

12、前與有序表中的元素進行比較，直到遇到值小于60的記錄為止，也即在有序表（15，23，38，54，72，96）中共需比較3次，因此填3。9.若對順序存儲在AlA9的記錄（76,38,62,53,80,74,83,65,85）進行堆排序，已知除第一個元素76外，以其余元素為根的結(jié)點都已是堆，則對第一個元素進行篩運算時,它將最終被篩到A數(shù)組下標為的位置上?！敬鸢浮?【解析】從樹結(jié)構(gòu)關(guān)鍵字值看,除根外是小根堆。對第一元素進行篩運算時,得到的數(shù)據(jù)序列為：38,53,62,65,80,74,83,76,85。11在時間復雜度為O（log2n）的排序方法中，排序方法是穩(wěn)定的；在時間復雜度為0（n）的排序方法

13、中，排序方法是不穩(wěn)定的。【答案】（1）歸并（2）直接選擇設(shè)表中元素的初態(tài)是按鍵值遞增的,若分別用堆排序、快速排序、冒泡排序和歸并排序方法對其仍按遞增順序進行排序，則最省時間，最費時間?！敬鸢浮浚?）冒泡排序（2）快速排序【解析】若初始序列已經(jīng)有序,則冒泡排序僅需一趟（比較n-1次）；而快速排序則需n-1趟，其時間復雜度升至0（n2）。因此填：冒泡排序，快速排序。從一個無序序列建立一個堆的方法是：首先將要排序的n個鍵值分放到一棵的各個結(jié)點中，然后從i=的結(jié)點K.開始，逐步把以K,、Ki-2、K1為根的子樹排成堆，直到以Kl為根的樹排成堆，就完成了建堆的過程。【答案】（1）完全二叉樹（2）n2下取

14、整。9.4應用題2.冒泡排序算法是否穩(wěn)定？為什么？【答案】冒泡排序算法是穩(wěn)定的。因為依據(jù)該排序算法的基本思想，排序過程只比較相鄰兩個記錄的關(guān)鍵字，若交換記錄也只在相鄰二個記錄之間進行，從而可知在交換過程中不會出現(xiàn)跨越多個記錄的情形。即使是相鄰兩個記錄關(guān)鍵字相同時，經(jīng)過比較也不會產(chǎn)生相鄰記錄的交換。所以冒泡排序法不會改變相同關(guān)鍵字記錄的相對次序，故是穩(wěn)定的。3在起泡排序過程中，什么情況下排序碼會朝向與排序相反的方向移動，試舉例說明。在快速排序過程中有這種現(xiàn)象嗎？【答案】如果在待排序序列的后面的若干排序碼比前面的排序碼小，則在起泡排序的過程中，排序碼可能向與最終它應移向的位置相反的方向移動。例如：

15、初始關(guān)鍵字：59451090第一趟排序：45105990第二趟排序：10455990其中45在第一趟排序中移向了與最終位置相反的方向。但在快速排序中不會出現(xiàn)這種情況，因為在每趟排序中，比基準元素大的都交換到右邊，而比基準元素小的都交換到左邊。4設(shè)待排序的排序碼序列為12,2,16,30,28,10,16*,20,6,18,試分別寫出使用以下排序方法每趟排序后的結(jié)果。并說明做了多少次排序碼比較。（1）直接插入排序（2）希爾排序（增量為5,2,1）（3）起泡排序（4）快速排序（5）基數(shù)排序（6）堆排序答案】1）直接插入排序辛觸1列0123dJ67S9排序碼磁熾i-112J2163Q2810托206

16、L81i-2I412価3023m206比Ii-3I21216旳23ID2Q6IS1i4【2121630231016b206W2i5(212162S、301016J206IE5i-6I3ID7、23J6206IE3f21012J6、2S、30206LS3i-I210L2Id20、28*306183i92、LG、12、訪v_*ld、20、23F183I2召12i6JG7対、302）希爾排序（增量為5,2,1）初綜徉列d=5d-10123456789216302&10潔2D61310216詣1216203028103164W12詣如卻蕭610L2歷嬉132023303）起泡排序冊始徘與I03dl=t

17、212首6303濟12ID16i=32S10口i*4361012【U5s=52JO1216i-6261012626101216WIS30期20!W予J(5+B20302S202530擇序碼比較汶數(shù)l+1+i+l+J-5(1+1+2+1)+(1+1+1+IJ-P+1+3+1+3+1+1+E+2=14排年碼比較次數(shù)4）快速排序PimtfVtpos0123456?g9排序瑪比較次數(shù)口1122fposfpCH:uID)-鈾百186叮162fPO5tfOSIH12281616*203C18228m$noj12J2SMtpw?pns16-fptH20tpsIM51E4Jj6161

18、012114E6tptpos16fpw2B【30】3164361012Ili”4pcs16JIS【2D】283012id13直1【持120305）基數(shù)排序按最低位分配巴璽1030*1030fI4J明r7jr岡18161r+1r+麗誕收集按最高位分配收集6）堆排序第一步，形成初始的最大堆（略），第二步，做堆排序。初始排列，不是最大堆交換0#與9#對象形成初始最大202Sl2030.01812IE30.283010)(16r2S)(30從0#到8#重新形成堆交換0#與8#對從0#到7#重新形成堆lc1613ia3020J：(220)(281(30交換0#與7#對象從0#到6#重新形成堆交換0#與6

19、#對象161016101612101&70302020)(231(30167,(1從0#到1GEG13161$203&20306HE從0#到5#重新形成堆交換0#與5#對象4#重新形成堆從0#到3#重新形成堆交換0#與4#對象交換0#與3#對象l1QId歷16ISII203C23Jgm(i書從0#到2#重新形成堆交換0#與2#對象從0#到1#重新形成堆21010121612：162030.旳US2S)t30間113交換0#與1#對象從0#到1#重新形成堆，得到結(jié)果6對一個具有7個記錄的文件進行快速排序，請問：（1）在最好情況下需進行多少次比較？并給出一個最好情況初始排列的實例。（2）在最壞情況

20、下需進行多少次比較？為什么？并給出此時的實例?！敬鸢浮浚?）在最好情況下，由于快速排序是一個劃分子區(qū)間的排序，每次劃分最好能得到兩個長度相等的子表，設(shè)表的長度為n=2k-l,顯然有，第一遍劃分得到兩個長度均為n/2的子表。第二遍劃分得到4個長度均為n/4的子表，以此類推，總共進行k=log（n+l）遍劃分，各子表的長度均為1時，此時排序結(jié)束。2由于n=7,k=3，在最好情況下，第一遍經(jīng)過6次，可找到一個其基準是正中間的元素，第二遍分別對兩個子表（此時長度為3）進行排序，各需要2次，這樣就可將整個數(shù)據(jù)序列排序完畢，從而知7個數(shù)據(jù)的最好情況下需進行10次比較。如：4，7，5，6，3，1，2。（2）

21、在最壞情況下，若每次劃分時用的基準，它的關(guān)鍵字值是當前記錄中最大（或最小值），那么每次劃分只能得到左子表（或右子表），子表長度只比原表減少了一個。因此，若初始排列的記錄是按關(guān)鍵字遞增或遞減的，而所得的結(jié)果須為遞減或遞增排列的，此時快速排序就退化為與冒泡排序相似，而且時間復雜度為O（n2），此時反而不快了。對于n=7的數(shù)據(jù)序列，顯然最壞情況下的比較次數(shù)為21。例如：7，6，5，4，3，2，1。9.5算法設(shè)計題1試設(shè)計一個算法，使得在0（n）的時間內(nèi)重排數(shù)組，將所有取負值的排序碼排在所有取正值（非負值）的排序碼之前。【算法分析】此題算法較簡單，即開始時設(shè)頭、尾兩個下標指針分別指向第一和最后一個元素

22、，頭指針逐一向后移動直到遇到非負數(shù)為止，尾指針逐一向前移動直到遇到負數(shù)為止，此時交換頭、尾指針所指的數(shù)，即：負數(shù)交換到前面而非負數(shù)交換到了后面。然后頭、尾指針繼續(xù)按剛才的規(guī)律移動并交換數(shù)據(jù)直到頭、尾指針相遇為止。算法源代碼】voidreArrange(intL,intn)inti=0,j=n-1,temp;while(i!=j)while(Li=0)j-;temp=Li;Li=Lj;Lj=temp;i+;j-;2.奇偶交換排序是另一種交換排序。它的第一趟對序列中的所有奇數(shù)項i掃描，第二趟對序列中的所有偶數(shù)項i掃描。若AiAi+1，則交換它們。第三趟有對所有的奇數(shù)項，第四趟對所有的偶數(shù)項，如此反

23、復，直到整個序列全部排好序為止?！舅惴ǚ治觥扛鶕?jù)題目要求，可設(shè)一個布爾變量exchange,判斷在每一次做過一趟奇數(shù)項掃描和一趟偶數(shù)項掃描后是否有過交換。若exchange為1，表示剛才有過交換，還需繼續(xù)做下一趟奇數(shù)項掃描和一趟偶數(shù)項掃描；若exchange為0，表示剛才沒有交換，可以結(jié)束排序。【算法源代碼】OddEvenSort(intVector,intn)inti,exchange,temp;doexchange=0;for(i=1;iVectori+1)/*相鄰兩項比較,發(fā)生逆序*/exchange=1;/*作交換標記*/temp=Vectori;Vectori=Vectori+1;V

24、ectori+1=temp;/*交換*/for(i=0;iVectori+1)/*相鄰兩項比較,發(fā)生逆序*/exchange=1;/*作交換標記*/temp=Vectori;Vectori=Vectori+1;Vectori+1=temp;/*交換*/while(exchange!=0);3設(shè)計一個算法，實現(xiàn)雙向冒泡排序?！舅惴ǚ治觥棵芭菖判驈淖钕旅娴挠涗涢_始，對每兩個相鄰的關(guān)鍵字進行比較，且使關(guān)鍵字較小的記錄換至關(guān)鍵字較大的記錄之上，使得經(jīng)過一趟冒泡排序后，關(guān)鍵字最小的記錄到達最上端，接著，再在剩下的記錄中找關(guān)鍵字最小的記錄，并把它換到第二位置上。依次類推，一直到所有記錄都有序為止。雙向冒泡

25、排序則是每一趟通過每兩個相鄰的關(guān)鍵字進行比較，產(chǎn)生最小和最大的元素。【算法源代碼】voiddbSort(intr,intn)inti=1,j,t,b=1;while(b)b=0;for(j=n-i;j=i;j-)/*找最小元素*/if(rjrj-1)b=1;t=rj;rj=rj-1;rj-1=t;for(j=i;jrj+1)b=1;t=rj;rj=rj+1;rj+1=t;i+;4寫出快速排序的非遞歸算法?！舅惴ǚ治觥吭O(shè)對記錄空間R仁n進行快速排序，要求用非遞歸算法，可以利用一個棧s來進行，其類型類型為SqStack，每個棧元素含兩個域：一個是top域，即棧頂指針；另一個為data域，用于存放元

26、素，其中data數(shù)組元素含兩個域，一個為low,個為high，分別指示某個子文件的首、尾記錄的首、尾地址,設(shè)棧空間最大容量為MAXSIZE，而且假定在整個排序過程中不會發(fā)生溢出?！舅惴ㄔ创a】QuikSort(intR,intn)inti,j,lw,hg,temp;SqStack*s;s-top=1;s-datas-top.low=1;s-datas-top.high=n;while(s-top!=0)/*棧非空，則取出一個子文件進行劃分*/lw=s-datas-top.low;hg=s-datas-top.high;s-top-;i=lw;j=hg;temp=Ri;dowhile(itemp)j-;if(ij)Ri=Rj;