第3章 排序 自測卷 答案 姓名 班級 題號一二三四五總分題分241836814100得分一、填空題（每空1分，共24分）1. 大多數(shù)排序算法都有兩個基本的操作： 比較（兩個關鍵字的大?。?和 移動（記錄或改變指向記錄的指針） 。2. 在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置至少需比較 3 次。(可約定為，從后向前比較)3. 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用 插入排序（到尾部） ；若初始數(shù)據(jù)基本反序，則選用 選擇排序 。4. 在堆排序和快速排序中，若初始記錄接近正序或反序，則選用 堆排序 ；若初始記錄基本無序，則最好選用 快速排序 。5. 對于n個記錄的集合進行冒泡排序，在最壞的情況下所需要的時間是 O(n2) 。若對其進行快速排序，在最壞的情況下所需要的時間是 O(n2) 。6. 對于n個記錄的集合進行歸并排序，所需要的平均時間是 O(nlog2n) ，所需要的附加空間是 O(n) 。7【計研題2000】對于n個記錄的表進行2路歸并排序，整個歸并排序需進行 log2n 趟（遍），共計移動 n log2n 次記錄。(即移動到新表中的總次數(shù)！共log2n趟，每趟都要移動n個元素)8.設要將序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的關鍵碼按字母序的升序重新排列，則：冒泡排序一趟掃描的結果是 H, C, Q, P, A, M, S, R, D, F, X ,Y ；初始步長為4的希爾（shell）排序一趟的結果是 P, A, C, S, Q, D, F, X , R, H,M, Y ；二路歸并排序一趟掃描的結果是 H, Q, C, Y，A, P, M, S, D, R, F, X ；快速排序一趟掃描的結果是 F, H, C, D, P, A, M, Q, R, S, Y，X ；堆排序初始建堆的結果是 A, D, C, R, F, Q, M, S, Y，P, H, X 。9. 在堆排序、快速排序和歸并排序中，若只從存儲空間考慮，則應首先選取 堆排序 方法，其次選取 快速排序 方法，最后選取 歸并排序 方法；若只從排序結果的穩(wěn)定性考慮，則應 選取歸并排序方法；若只從平均情況下最快考慮，則應選取快速排序方法；若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮，則應選取堆排序方法。二、單項選擇題（每小題1分，共18分）（ C ）1將5個不同的數(shù)據(jù)進行排序，至多需要比較 次。. 8 . 9 . 10 . 25（ C ）2 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為. 希爾排序 . 冒泡排序 . 插入排序 . 選擇排序（ D ）3 排序方法中，從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方法，稱為. 希爾排序 . 歸并排序 . 插入排序 . 選擇排序（ C ）4對個不同的排序碼進行冒泡排序，在下列哪種情況下比較的次數(shù)最多。. 從小到大排列好的 . 從大到小排列好的 . 元素無序 . 元素基本有序（ D ）5對個不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數(shù)為. n+1 . n . n-1 . n(n-1)/2(前3個答案都太小了)（ C ）6快速排序在下列哪種情況下最易發(fā)揮其長處。. 被排序的數(shù)據(jù)中含有多個相同排序碼 . 被排序的數(shù)據(jù)已基本有序. 被排序的數(shù)據(jù)完全無序 . 被排序的數(shù)據(jù)中的最大值和最小值相差懸殊（ B ）7 【計研題2001】對有n個記錄的表作快速排序，在最壞情況下，算法的時間復雜度是AO(n) BO(n2) CO(nlog2n) DO(n3)（ C ）8若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為. 38, 40, 46, 56, 79, 84 . 40,38, 46 , 79, 56, 84 . 40, 38，46, 56, 79, 84 . 40, 38,46, 84, 56, 79（ A&D ）9【計研題2001】在最好情況下，下列排序算法中 排序算法所需比較關鍵字次數(shù)最少。A冒泡 B歸并 C快速 D直接插入(僅n1次！)（ C ）10 【計研題2001】置換選擇排序的功能是 。 （置換選擇排序簡單選擇排序？）A選出最大的元素 B產(chǎn)生初始歸并段 C產(chǎn)生有序文件 D置換某個記錄（ A ）11將5個不同的數(shù)據(jù)進行排序，至少需要比較 次。. 4 . 5 . 6 . 7（ D ）12下列關鍵字序列中， 是堆。. 16,72,31,23,94,53 . 94,23, 31, 72, 16, 53 . 16, 53, 23,94,31, 72 . 16, 23, 53,31, 94, 72（ B ）13堆是一種 排序。. 插入 .選擇 . 交換 . 歸并（ C ）14堆的形狀是一棵 . 二叉排序樹 .滿二叉樹 . 完全二叉樹 . 平衡二叉樹（ B ）15若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用堆排序的方法建立的初始堆為. 79, 46, 56, 38, 40, 84 . 84, 79, 56, 38, 40, 46 . 84, 79, 56, 46, 40, 38 . 84, 56, 79, 40, 46, 38 （ B ）16 下述幾種排序方法中，平均查找長度（ASL）最小的是. 插入排序 .快速排序 . 歸并排序 . 選擇排序（ C ）17 下述幾種排序方法中，要求內(nèi)存最大的是. 插入排序 .快速排序 . 歸并排序 . 選擇排序（ B ）18目前以比較為基礎的內(nèi)部排序方法中，其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無關的是. 插入排序 . 二分插入排序 . 快速排序 . 冒泡排序三、簡答題（每小題4分，共36分）1. 【全國專升本題】已知序列基本有序，問對此序列最快的排序方法是多少，此時平均復雜度是多少？答：插入排序和冒泡應該是最快的。因為只有比較動作，無需移動元素。此時平均時間復雜度為O(n)2. 設有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好采用哪種排序方法？答：用堆排序或錦標賽排序最合適，因為不必等全部元素排完就能得到所需結果，時間效率為O(nlog2n)；若用冒泡排序則需時n!/(n-10)!3. 用某種排序方法對線性表（25, 84，21,47,15,27,68,35,20）進行排序時，元素序列的變化情況如下：25, 84，21,47,15,27,68,35,20 20, 15, 21, 25，47, 27,68,35, 84 15, 20, 21, 25，35, 27, 47, 68, 8415, 20, 21, 25，27, 35, 47, 68, 84， 問采用的是什么排序方法？答：用的是快速排序方法。注意每一趟要振蕩完全部元素才算一個中間結果。4. 對于整數(shù)序列100，99，98，3，2，1，如果將它完全倒過來，分別用冒泡排序和快速排序法，它們的比較次數(shù)和交換次數(shù)各是多少？答：冒泡排序的比較和交換次數(shù)將最大，都是1+2+n-1=n(n-1)/25099=4545次快速排序則看按什么數(shù)據(jù)來分子表。如果按100來分，則很慘，也會是n(n-1)/2！若按中間數(shù)據(jù)50或51來分表，則：第1輪能確定1個元素，即在1個子表中比較和交換了n1個元素；n（21-1）第2輪能再確定2個元素，即在2個子表中比較和交換了n3個元素；n（22-1）第3輪能再確定4個元素，即在4個子表中比較和交換了n7個元素；n（23-1）第4輪能再確定8個元素，即在8個子表中比較和交換了n15個元素；n（24-1）第6輪能再確定32個元素，即在32個子表中比較和交換了n65個元素；n（26-1）第7輪則能全部確定，（因為27=128）， 在100個子表中比較和交換了n（1001）個元素； 比較和交換總次數(shù)為：7n(2112212312611001) 7n+7(12464+100)=7n(8+16+32+164)=700-220=480次若從中間選擇初始元素，則ASL=（n+1）log2n(212223+2m)= nlog2n+log2n(212223+n)O（nlog2n）5.【全國專升本試題】【嚴題集10.15】設有n個值不同的元素存于順序結構中，試問能否用比2n-3少的比較次數(shù)選出這n個元素中的最大值和最小值？若能請說明如何實現(xiàn)（不需寫算法）。在最壞情況下至少需進行多少次比較。（或問：對含有n個互不相同元素的集合，同時找最大元和最小元至少需進行多少次比較?）答：若用冒泡排序法，求最大值需n-1次比較；第二趟改為從n-1開始求最小值，需n-2次比較，合計2n-3次。顯然本題意圖是放棄冒泡排序，尋找其他方法。法1 ：一個簡單的辦法是，在一趟比較時，將頭兩個元素分別作為最大和最小值的暫存內(nèi)容，將其余n-2個元素與其相比，具體可設計為：第1步：a1<a2? 用來設立max和min標志;無論Y/N都只比較1次； 1次；第2步：a3>a2? YES則直接替換a2，NO則再比較a1， 12次；第3步：a4>a2? YES則直接替換a2，NO則再比較a1， 12次；第n-1步：an>a2? YES則直接替換a2，NO則再比較a1， 12次；合計：（n-2）（12）1=(n-1)(2n-3 )2n-3 最好情況至少需要n-1次比較，最壞情況需2n-3次。法2 ：借用快速排序第一趟思想：以a1為支點，將序列分成兩個子表。這一趟需要n-1次比較；然后，在左邊的子表中求最小值，冒泡一趟需要y-1次；在右邊的子表中求最大值，冒泡一趟需要z-1次；合計需要(n-1)+( y-1)+( z-1)=n+y+z-3 因為y+z+1=n, 所以總次數(shù)2n42n3!但最壞情況下仍為為2n-3次，即一趟完畢后仍為單子表的情況。怎么辦？有無更好的辦法？法3 ：能否用錦標賽排序思路？求最大值等于求冠軍，需要n1次比較；但接著求最小值，等于在n/2個葉子中比較即可。編程也不復雜：可設計為，第一趟：n個數(shù)據(jù)兩兩比較（共n/2次），小者放偶數(shù)位，大者放奇數(shù)位；第二趟：對奇數(shù)位元素繼續(xù)兩兩比較（n/4次）；對偶數(shù)位元素也兩兩比較（n/4次）；合計n/2次；第三趟：對奇數(shù)位元素繼續(xù)兩兩比較（n/23次）；對偶數(shù)位元素也兩兩比較（n/23次）；合計n/22次；第四趟：對奇數(shù)位元素繼續(xù)兩兩比較（n/24次）；對偶數(shù)位元素也兩兩比較（n/24次）；合計n/23次；第log2n趟：對奇數(shù)位元素繼續(xù)兩兩比較（n/2log2n次1）；對偶數(shù)位元素也兩兩比較（1次）；合計2次；全部比較次數(shù)為：2+4+8+n/2次2n-3 （n>1） 用二進制性質(zhì)即可證明？ 因為 20+21+2k-2+2k-1<2k ，即21+2k-2+2k-1<2k 1 < 2k 1 +2k 2(n=2k, 當k1，即n=2時為極端情況，11; n=3時，1.5<3k=2時，即n=4時，2<5 6. 【成教考題】將兩個長度為n的有序表歸并為一個長度為2n的有序表，最小需要比較n次，最多需要比較2n-1次，請說明這兩種情況發(fā)生時，兩個被歸并的表有何特征?答：最少的比較次數(shù)是這樣一種情況：若A表所有元素都小于（或大于）B表元素，則A1比較完B1Bn之后，直接拼接即可。最多比較次數(shù)的情況應該是A、B兩表互相交錯，此時需要穿插重排。則A表的每個元素都要與B表元素相比，A1與B1相比，能確定其中一個元素的位置；剩下一個還要與另一表中下一元素再比較一次，即：在表A或表B的n個元素中，除了最后一個元素外，每個元素都要比較2次！最壞情況總共為2n1次。7. 【嚴題集10.11】試問：按錦標賽排序的思想，決出8名運動員之間的名次排列，至少需編排多少場次的比賽（應考慮最壞的情況）？劉答：不能簡單地用(n-1)+(n-2)log2n來計算比賽場次。要特別注意，隨著n/2的葉子結點被調(diào)整完畢之后，樹的深度會逐層減少！分別n=8和n=7的情況推導并歸納，得到如下計算公式：比賽場次（n-1）+n/2(k-1)+ (n/22)(k-2)+ n/2(k-1) ，其中k=log2n當n8時，k=3, 比賽場次78/2(2)8/4= 17場(這是最壞情況，即每次都先從葉子調(diào)整起)8. 【嚴題集10.19】假設某大旅店共有5000個床位，每天需要根據(jù)住宿旅客的文件制造一份花名冊，該名冊要求按?。ㄊ校┑拇涡蚺帕?，每一省（市）按縣（區(qū)）排列，又同一縣（區(qū)）的旅客按姓氏排列。請你為旅店的管理人員設計一個制作這份花名冊的方法。（提示）這是一個多關鍵字的排序問題。請思考對這個文件進行排序用哪一種方法更合適，是MSD法還是LSD法？答：采用哪種排序方法，關鍵要看記錄的結構是如何定義的，如果旅客填表如下：?。ㄊ校┛h（區(qū)）姓名床位號則按題意要求，應當采用MSD法，否則無法滿足。但若“姓名”項在前，則必須用LSD才符合題意要求。9. 【全國專升本題】【嚴題集10.6】奇偶交換排序如下所述：第一趟對所有奇數(shù)i，將ai和ai+1進行比較；第二趟對所有的偶數(shù)i,將ai和ai+1進行比較，若ai>ai+1，則兩者交換；第三趟對奇數(shù)i,第四趟對偶數(shù)i；依次類推直至整個序列有序為止。（1）試問這種排序方法的結束條件是什么？是否為穩(wěn)定排序？（2）分析當初始序列為正序或逆序兩種情況下，奇偶交換排序過程中所需進行的關鍵字比較的次數(shù)。 （3）分析此種排序方法的平均復雜度及最壞復雜度。答：（1） 這種算法其實是兩兩比較，第一趟很像錦標賽的“初賽”，將勝者（大數(shù)）置于偶數(shù)單元；第二趟對偶數(shù)單元操作，即第一組大者與第二組小者戰(zhàn)，大者后移。結果相當于冒泡排序的一趟；所以結束條件應為偶數(shù)趟無交換。結束條件是：若n為偶數(shù)時，奇數(shù)循環(huán)時i>n-1 ，偶數(shù)循環(huán)時i>n ，若n為奇數(shù)時，奇數(shù)循環(huán)時i>n 偶數(shù)循環(huán)時i>n+1似乎不穩(wěn)定？因為交換沒有依次進行。四、【全國專升本類似題】【類嚴題集10.1】以關鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，分別寫出執(zhí)行以下算法的各趟排序結束時，關鍵字序列的狀態(tài)，并說明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實現(xiàn)？ 直接插入排序 希爾排序 冒泡排序 快速排序直接選擇排序 堆排序 歸并排序 基數(shù)排序 （8分）解：先回答第2問： 皆易于在鏈表上實現(xiàn)。 直接插入排序的中間過程如下： 希爾排序的中間過程如下： 冒泡排序的中間過程如下： 快速排序的中間過程如下： 直接選擇排序的中間過程如下： 堆排序（大根堆）的中間過程如下： 歸并排序排序的中間過程如下： 基數(shù)排序的中間過程如下：五、算法設計題（4選2， 每題7分，共14分）1. 【嚴題集10.25】試編寫教科書10.2.2節(jié)中所述鏈表插入排序的算法。10.25 void SLInsert_Sort(SLList &L)/靜態(tài)鏈表的插入排序算法 L.r0.key=0;L.r0.next=1; L.r1.next=0; /建初始循環(huán)鏈表 for(i=2;i<=L.length;i+) /逐個插入 p=0;x=L.ri.key; while(L.rL.rp.next.key<x&&L.rp.next) p=L.rp.next; q=L.rp.next; L.rp.next=i; L.ri.next=q; /for p=L.r0.next; for(i=1;i<L.length;i+) /重排記錄的位置 while(p<i) p=L.rp.next; q=L.rp.next; if(p!=i) L.rp<->L.ri; L.ri.next=p; p=q; /for /SLInsert_Sort 2. 【嚴題集10.30】按下述原則編寫快排的非遞歸算法：（1） 一趟排序之后，先對長度較短的子序列進行排序，且將另一子序列的上、下界入棧保存；（2） 若待排記錄數(shù)3,則不再進行分割，而是直接進行比較排序。10.30 typedef struct int low; int high; boundary; /子序列的上下界類型 void QSort_NotRecurve(int SQList &L)/快速排序的非遞歸算法 low=1;high=L.length; InitStack(S); /S的元素為boundary類型 while(low<high&&!StackEmpty(S) /注意排序結束的條件 if(high-low>2) /如果當前子序列長度大于3且尚未排好序 pivot=Partition(L,low,high); /進行一趟劃分 if(high-pivot>pivot-low) Push(S,pivot+1,high); /把長的子序列邊界入棧 high=pivot-1; /短的子序列留待下次排序 else Push(S,low,pivot-1); low=pivot+1; /if else if(low<high&&high-low<3)/如果當前子序列長度小于3且尚未排好序 Easy_Sort(L,low,high); /直接進行比較排序 low=high; /當前子序列標志為已排好序 else /如果當前子序列已排好序但棧中還有未排序的子序列 Pop(S,a); /從棧中取出一個子序列 low=a.low; high=a.high; /while /QSort_NotRecurve int Partition(SQList &L,int low,int high)/一趟劃分的算法,與書上相同 L.r0=L.rlow; pivotkey=L.rlow.key; while(low<high) while(low<high&&L.rhigh.key>=pivotkey) high-; L.rlow=L.rhigh; while(low<high&&L.rlow.key<=pivotkey) low+; L.rhigh=L.rlow; /while L.rlow=L.r0; return low; /Partition void Easy_Sort(SQList &L,int low,int high)/對長度小于3的子序列進行比較排序 if(high-low=1) /子序列只含兩個元素 if(L.rlow.key>L.rhigh.key) L.rlow<->L.rhigh; else /子序列含有三個元素 if(L.rlow.key>L.rlow+1.key) L.rlow<->L.rlow+1; if(L.rlow+1.key>L.rhigh.key) L.rlow+1<->L.rhigh; if(L.rlow.key>L.rlow+1.key) L.rlow<->L.rlow+1; /Easy_Sort 3. 【嚴題集10.41】假設有1000個關鍵字為小于10000的整數(shù)的記錄序列，請設計一種排序方法，要求以盡可能少的比較次數(shù)和移動次數(shù)實現(xiàn)排序，并按你的設計編出算法。解：可以用基數(shù)排序來實現(xiàn)，關鍵字位數(shù)d=4，數(shù)基radix=10（從09）則基數(shù)排序的算法如下；void Hash_Sort(int a )/對1000個關鍵字為四位整數(shù)的記錄進行排序 int b10000; for(i=0;i<1000;i+) /直接按關鍵字散列 （即分配） for(j=ai;bj;j=(j+1)%10000); bj=ai; for(i=0,j=0;i<1000;j+) /將散列收回a中 if(bj) for(x=bj,k=j;bk;k=(k+1)%10000) if(bk=x) ai+=x; bk=0; /if /Hash_Sort 4. 【嚴題集10.42】序列的“中值記錄”指的是：如果將此序列排序后，它是第n/2個記錄。試寫一個求中值記錄的算法。10.42 typedef struct int gt; /大于該記錄的個數(shù) int lt; /小于該記錄的個數(shù) place; /整個序列中比某個關鍵字大或小的記錄個數(shù) int Get_Mid(int a ,int n) /求一個序列的中值記錄的位置 place bMAXSIZE; for(i=0;i<n;i+) /對每一個元素統(tǒng)計比它大和比它小的元素個數(shù)gt和lt for(j=0;j<n;j+) if(aj>ai) bi.gt+; else if(aj<ai) bi.lt+; mid=0; min_dif=abs(b0.gt-b0.lt); for(i=0;i<n;i+) /找出gt值與lt值最接近的元素,即為中值記錄 if(abs(bi.gt-bi.lt)<min_dif) mid=i; return mid; /Get_Mid 10