1、第3章 排序 自測(cè)卷 答案 姓名 班級(jí) 題號(hào)一二三四五總分題分241836814100得分一、填空題（每空1分，共24分）1. 大多數(shù)排序算法都有兩個(gè)基本的操作： 比較（兩個(gè)關(guān)鍵字的大?。?和 移動(dòng)（記錄或改變指向記錄的指針） 。2. 在對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置至少需比較 3 次。(可約定為，從后向前比較)3. 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用 插入排序（到尾部） ；若初始數(shù)據(jù)基本反序，則選用 選擇排序 。4. 在堆排序和快速排序中，若初始記錄接近正序或反序，則選用 堆排

2、序 ；若初始記錄基本無(wú)序，則最好選用 快速排序 。5. 對(duì)于n個(gè)記錄的集合進(jìn)行冒泡排序，在最壞的情況下所需要的時(shí)間是 O(n2) 。若對(duì)其進(jìn)行快速排序，在最壞的情況下所需要的時(shí)間是 O(n2) 。6. 對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需要的平均時(shí)間是 O(nlog2n) ，所需要的附加空間是 O(n) 。7【計(jì)研題2000】對(duì)于n個(gè)記錄的表進(jìn)行2路歸并排序，整個(gè)歸并排序需進(jìn)行 log2n 趟（遍），共計(jì)移動(dòng) n log2n 次記錄。(即移動(dòng)到新表中的總次數(shù)！共log2n趟，每趟都要移動(dòng)n個(gè)元素)8.設(shè)要將序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的關(guān)鍵碼按

3、字母序的升序重新排列，則：冒泡排序一趟掃描的結(jié)果是 H, C, Q, P, A, M, S, R, D, F, X ,Y ；初始步長(zhǎng)為4的希爾（shell）排序一趟的結(jié)果是 P, A, C, S, Q, D, F, X , R, H,M, Y ；二路歸并排序一趟掃描的結(jié)果是 H, Q, C, Y，A, P, M, S, D, R, F, X ；快速排序一趟掃描的結(jié)果是 F, H, C, D, P, A, M, Q, R, S, Y，X ；堆排序初始建堆的結(jié)果是 A, D, C, R, F, Q, M, S, Y，P, H, X 。9. 在堆排序、快速排序和歸并排序中，若只從存儲(chǔ)空間考慮，則應(yīng)首

4、先選取 堆排序 方法，其次選取 快速排序 方法，最后選取 歸并排序 方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng) 選取歸并排序方法；若只從平均情況下最快考慮，則應(yīng)選取快速排序方法；若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取堆排序方法。二、單項(xiàng)選擇題（每小題1分，共18分）（ C ）1將5個(gè)不同的數(shù)據(jù)進(jìn)行排序，至多需要比較 次。. 8 . 9 . 10 . 25（ C ）2 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為. 希爾排序 . 冒泡排序 . 插入排序 . 選擇排序（ D ）3 排序方法中，從未排序序列中挑選元

5、素，并將其依次插入已排序序列（初始時(shí)為空）的一端的方法，稱為. 希爾排序 . 歸并排序 . 插入排序 . 選擇排序（ C ）4對(duì)個(gè)不同的排序碼進(jìn)行冒泡排序，在下列哪種情況下比較的次數(shù)最多。. 從小到大排列好的 . 從大到小排列好的 . 元素?zé)o序 . 元素基本有序（ D ）5對(duì)個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為. n+1 . n . n-1 . n(n-1)/2(前3個(gè)答案都太小了)（ C ）6快速排序在下列哪種情況下最易發(fā)揮其長(zhǎng)處。. 被排序的數(shù)據(jù)中含有多個(gè)相同排序碼 . 被排序的數(shù)據(jù)已基本有序. 被排序的數(shù)據(jù)完全無(wú)序 . 被排序的數(shù)據(jù)中的最大值和最小值相差懸殊（ B

6、）7 【計(jì)研題2001】對(duì)有n個(gè)記錄的表作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是AO(n) BO(n2) CO(nlog2n) DO(n3)（ C ）8若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為. 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【計(jì)研題2001】在最好情況下，下列排序算法中 排序算法所需比較關(guān)鍵字次數(shù)最少。A冒泡 B歸并 C快速

7、D直接插入(僅n1次！)（ C ）10 【計(jì)研題2001】置換選擇排序的功能是 。 （置換選擇排序簡(jiǎn)單選擇排序？）A選出最大的元素 B產(chǎn)生初始?xì)w并段 C產(chǎn)生有序文件 D置換某個(gè)記錄（ A ）11將5個(gè)不同的數(shù)據(jù)進(jìn)行排序，至少需要比較 次。. 4 . 5 . 6 . 7（ D ）12下列關(guān)鍵字序列中， 是堆。. 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堆的形狀是一棵 . 二叉排序樹(shù)

8、.滿二叉樹(shù) . 完全二叉樹(shù) . 平衡二叉樹(shù)（ 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 下述幾種排序方法中，平均查找長(zhǎng)度（ASL）最小的是. 插入排序 .快速排序 . 歸并排序 . 選擇排序（ C ）17 下述幾種排序方法中，要求內(nèi)存最大的是. 插入排序 .快速排序 . 歸并排序 . 選擇排序（ B ）18目前以

9、比較為基礎(chǔ)的內(nèi)部排序方法中，其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無(wú)關(guān)的是. 插入排序 . 二分插入排序 . 快速排序 . 冒泡排序三、簡(jiǎn)答題（每小題4分，共36分）1. 【全國(guó)專升本題】已知序列基本有序，問(wèn)對(duì)此序列最快的排序方法是多少，此時(shí)平均復(fù)雜度是多少？答：插入排序和冒泡應(yīng)該是最快的。因?yàn)橹挥斜容^動(dòng)作，無(wú)需移動(dòng)元素。此時(shí)平均時(shí)間復(fù)雜度為O(n)2. 設(shè)有1000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好采用哪種排序方法？答：用堆排序或錦標(biāo)賽排序最合適，因?yàn)椴槐氐热吭嘏磐昃湍艿玫剿杞Y(jié)果，時(shí)間效率為O(nlog2n)；若用冒泡排序則需時(shí)n!/(n-10)!3. 用

10、某種排序方法對(duì)線性表（25, 84，21,47,15,27,68,35,20）進(jìn)行排序時(shí)，元素序列的變化情況如下：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， 問(wèn)采用的是什么排序方法？答：用的是快速排序方法。注意每一趟要振蕩完全部元素才算一個(gè)中間結(jié)果。4. 對(duì)于整數(shù)序列100，99，98，3，2，1，如果將它完全倒過(guò)來(lái)，分別用冒泡排序和快速排序法，它們的比較次數(shù)和交換次數(shù)各是多少？答：冒

11、泡排序的比較和交換次數(shù)將最大，都是1+2+n-1=n(n-1)/25099=4545次快速排序則看按什么數(shù)據(jù)來(lái)分子表。如果按100來(lái)分，則很慘，也會(huì)是n(n-1)/2！若按中間數(shù)據(jù)50或51來(lái)分表，則：第1輪能確定1個(gè)元素，即在1個(gè)子表中比較和交換了n1個(gè)元素；n（21-1）第2輪能再確定2個(gè)元素，即在2個(gè)子表中比較和交換了n3個(gè)元素；n（22-1）第3輪能再確定4個(gè)元素，即在4個(gè)子表中比較和交換了n7個(gè)元素；n（23-1）第4輪能再確定8個(gè)元素，即在8個(gè)子表中比較和交換了n15個(gè)元素；n（24-1）第6輪能再確定32個(gè)元素，即在32個(gè)子表中比較和交換了n65個(gè)元素；n（26-1）第7輪則能全

12、部確定，（因?yàn)?7=128）， 在100個(gè)子表中比較和交換了n（1001）個(gè)元素； 比較和交換總次數(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.【全國(guó)專升本試題】【嚴(yán)題集10.15】設(shè)有n個(gè)值不同的元素存于順序結(jié)構(gòu)中，試問(wèn)能否用比2n-3少的比較次數(shù)選出這n個(gè)元素中的最大值和最小值？若能請(qǐng)說(shuō)明如何實(shí)現(xiàn)（不需寫(xiě)算法）。在最壞情況下至少需進(jìn)行多少次比較。（或問(wèn)：對(duì)含有

13、n個(gè)互不相同元素的集合，同時(shí)找最大元和最小元至少需進(jìn)行多少次比較?）答：若用冒泡排序法，求最大值需n-1次比較；第二趟改為從n-1開(kāi)始求最小值，需n-2次比較，合計(jì)2n-3次。顯然本題意圖是放棄冒泡排序，尋找其他方法。法1 ：一個(gè)簡(jiǎn)單的辦法是，在一趟比較時(shí)，將頭兩個(gè)元素分別作為最大和最小值的暫存內(nèi)容，將其余n-2個(gè)元素與其相比，具體可設(shè)計(jì)為：第1步：a1a2? YES則直接替換a2，NO則再比較a1， 12次；第3步：a4a2? YES則直接替換a2，NO則再比較a1， 12次；第n-1步：ana2? YES則直接替換a2，NO則再比較a1， 12次；合計(jì)：（n-2）（12）1=(n-1)(2

14、n-3 )2n-3 最好情況至少需要n-1次比較，最壞情況需2n-3次。法2 ：借用快速排序第一趟思想：以a1為支點(diǎn)，將序列分成兩個(gè)子表。這一趟需要n-1次比較；然后，在左邊的子表中求最小值，冒泡一趟需要y-1次；在右邊的子表中求最大值，冒泡一趟需要z-1次；合計(jì)需要(n-1)+( y-1)+( z-1)=n+y+z-3 因?yàn)閥+z+1=n, 所以總次數(shù)2n42n3!但最壞情況下仍為為2n-3次，即一趟完畢后仍為單子表的情況。怎么辦？有無(wú)更好的辦法？法3 ：能否用錦標(biāo)賽排序思路？求最大值等于求冠軍，需要n1次比較；但接著求最小值，等于在n/2個(gè)葉子中比較即可。編程也不復(fù)雜：可設(shè)計(jì)為，第一趟：n

15、個(gè)數(shù)據(jù)兩兩比較（共n/2次），小者放偶數(shù)位，大者放奇數(shù)位；第二趟：對(duì)奇數(shù)位元素繼續(xù)兩兩比較（n/4次）；對(duì)偶數(shù)位元素也兩兩比較（n/4次）；合計(jì)n/2次；第三趟：對(duì)奇數(shù)位元素繼續(xù)兩兩比較（n/23次）；對(duì)偶數(shù)位元素也兩兩比較（n/23次）；合計(jì)n/22次；第四趟：對(duì)奇數(shù)位元素繼續(xù)兩兩比較（n/24次）；對(duì)偶數(shù)位元素也兩兩比較（n/24次）；合計(jì)n/23次；第log2n趟：對(duì)奇數(shù)位元素繼續(xù)兩兩比較（n/2log2n次1）；對(duì)偶數(shù)位元素也兩兩比較（1次）；合計(jì)2次；全部比較次數(shù)為：2+4+8+n/2次2n-3 （n1） 用二進(jìn)制性質(zhì)即可證明？ 因?yàn)?20+21+2k-2+2k-12k ，即21+2

16、k-2+2k-12k 1 2k 1 +2k 2(n=2k, 當(dāng)k1，即n=2時(shí)為極端情況，11; n=3時(shí)，1.53k=2時(shí)，即n=4時(shí)，2ai+1，則兩者交換；第三趟對(duì)奇數(shù)i,第四趟對(duì)偶數(shù)i；依次類推直至整個(gè)序列有序?yàn)橹埂＃?）試問(wèn)這種排序方法的結(jié)束條件是什么？是否為穩(wěn)定排序？（2）分析當(dāng)初始序列為正序或逆序兩種情況下，奇偶交換排序過(guò)程中所需進(jìn)行的關(guān)鍵字比較的次數(shù)。 （3）分析此種排序方法的平均復(fù)雜度及最壞復(fù)雜度。答：（1） 這種算法其實(shí)是兩兩比較，第一趟很像錦標(biāo)賽的“初賽”，將勝者（大數(shù)）置于偶數(shù)單元；第二趟對(duì)偶數(shù)單元操作，即第一組大者與第二組小者戰(zhàn)，大者后移。結(jié)果相當(dāng)于冒泡排序的一趟；所

17、以結(jié)束條件應(yīng)為偶數(shù)趟無(wú)交換。結(jié)束條件是：若n為偶數(shù)時(shí)，奇數(shù)循環(huán)時(shí)in-1 ，偶數(shù)循環(huán)時(shí)in ，若n為奇數(shù)時(shí)，奇數(shù)循環(huán)時(shí)in 偶數(shù)循環(huán)時(shí)in+1似乎不穩(wěn)定？因?yàn)榻粨Q沒(méi)有依次進(jìn)行。四、【全國(guó)專升本類似題】【類嚴(yán)題集10.1】以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，分別寫(xiě)出執(zhí)行以下算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)，并說(shuō)明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實(shí)現(xiàn)？ 直接插入排序 希爾排序 冒泡排序 快速排序直接選擇排序 堆排序 歸并排序 基數(shù)排序 （8分）解：先回答第2問(wèn)： 皆易于在鏈表上實(shí)現(xiàn)。 直接插入排序的中

18、間過(guò)程如下： 希爾排序的中間過(guò)程如下： 冒泡排序的中間過(guò)程如下： 快速排序的中間過(guò)程如下： 直接選擇排序的中間過(guò)程如下： 堆排序（大根堆）的中間過(guò)程如下： 歸并排序排序的中間過(guò)程如下： 基數(shù)排序的中間過(guò)程如下：五、算法設(shè)計(jì)題（4選2， 每題7分，共14分）1. 【嚴(yán)題集10.25】試編寫(xiě)教科書(shū)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+) /逐個(gè)插入 p=0;x=L.ri

19、.key; while(L.rL.rp.next.keyx&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;iL.length;i+) /重排記錄的位置 while(pi) p=L.rp.next; q=L.rp.next; if(p!=i) L.rpL.ri; L.ri.next=p; p=q; /for /SLInsert_Sort 2. 【嚴(yán)題集10.30】按下述原則編寫(xiě)快排的非遞歸算法：（1） 一趟排序之后，先對(duì)長(zhǎng)度較短的子序列進(jìn)行排序，且將另一子序列的上、

20、下界入棧保存；（2） 若待排記錄數(shù)3,則不再進(jìn)行分割，而是直接進(jìn)行比較排序。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(low2) /如果當(dāng)前子序列長(zhǎng)度大于3且尚未排好序 pivot=Partition(L,low,high); /進(jìn)行一趟劃分 if(high-pivotpivot-low) Push(S,p

21、ivot+1,high); /把長(zhǎng)的子序列邊界入棧 high=pivot-1; /短的子序列留待下次排序 else Push(S,low,pivot-1); low=pivot+1; /if else if(lowhigh&high-low3)/如果當(dāng)前子序列長(zhǎng)度小于3且尚未排好序 Easy_Sort(L,low,high); /直接進(jìn)行比較排序 low=high; /當(dāng)前子序列標(biāo)志為已排好序 else /如果當(dāng)前子序列已排好序但棧中還有未排序的子序列 Pop(S,a); /從棧中取出一個(gè)子序列 low=a.low; high=a.high; /while /QSort_NotRecurve

22、int Partition(SQList &L,int low,int high)/一趟劃分的算法,與書(shū)上相同 L.r0=L.rlow; pivotkey=L.rlow.key; while(lowhigh) while(low=pivotkey) high-; L.rlow=L.rhigh; while(lowhigh&L.rlow.keyL.rhigh.key) L.rlowL.rhigh; else /子序列含有三個(gè)元素 if(L.rlow.keyL.rlow+1.key) L.rlowL.rlow+1; if(L.rlow+1.keyL.rhigh.key) L.rlow+1L.rhigh; if(L.rlow.keyL.rlow+1.key) L.rlowL.rlow+1; /Easy_Sort 3. 【嚴(yán)題集10.41】假設(shè)有1000個(gè)關(guān)鍵字為小于10000的整數(shù)的記