第3章排序答案.doc
《第3章排序答案.doc》由會(huì)員分享,可在線閱讀,更多相關(guān)《第3章排序答案.doc(10頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
第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. 在堆排序和快速排序中,若初始記錄接近正序或反序,則選用 堆排序 ;若初始記錄基本無(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)鍵碼按字母序的升序重新排列,則:冒泡排序一趟掃描的結(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)首先選取 堆排序 方法,其次選取 快速排序 方法,最后選取 歸并排序 方法;若只從排序結(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 排序方法中,從未排序序列中挑選元素,并將其依次插入已排序序列(初始時(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 )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快速 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ù) .滿二叉樹(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目前以比較為基礎(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. 用某種排序方法對(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ù)各是多少?答:冒泡排序的比較和交換次數(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輪則能全部確定,(因?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)(不需寫算法)。在最壞情況下至少需進(jìn)行多少次比較。(或問(wèn):對(duì)含有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)(2n-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個(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+2k-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)于冒泡排序的一趟;所以結(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)為例,分別寫出執(zhí)行以下算法的各趟排序結(jié)束時(shí),關(guān)鍵字序列的狀態(tài),并說(shuō)明這些排序方法中,哪些易于在鏈表(包括各種單、雙、循環(huán)鏈表)上實(shí)現(xiàn)? 直接插入排序 希爾排序 冒泡排序 快速排序直接選擇排序 堆排序 歸并排序 基數(shù)排序 (8分)解:先回答第2問(wèn): 皆易于在鏈表上實(shí)現(xiàn)。 直接插入排序的中間過(guò)程如下: 希爾排序的中間過(guò)程如下: 冒泡排序的中間過(guò)程如下: 快速排序的中間過(guò)程如下: 直接選擇排序的中間過(guò)程如下: 堆排序(大根堆)的中間過(guò)程如下: 歸并排序排序的中間過(guò)程如下: 基數(shù)排序的中間過(guò)程如下:五、算法設(shè)計(jì)題(4選2, 每題7分,共14分)1. 【嚴(yán)題集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+) /逐個(gè)插入 p=0;x=L.ri.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】按下述原則編寫快排的非遞歸算法:(1) 一趟排序之后,先對(duì)長(zhǎng)度較短的子序列進(jìn)行排序,且將另一子序列的上、下界入棧保存;(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,pivot+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 int Partition(SQList &L,int low,int high)/一趟劃分的算法,與書上相同 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ù)的記錄序列,請(qǐng)?jiān)O(shè)計(jì)一種排序方法,要求以盡可能少的比較次數(shù)和移動(dòng)次數(shù)實(shí)現(xiàn)排序,并按你的設(shè)計(jì)編出算法。解:可以用基數(shù)排序來(lái)實(shí)現(xiàn),關(guān)鍵字位數(shù)d=4,數(shù)基radix=10(從09)則基數(shù)排序的算法如下;void Hash_Sort(int a )/對(duì)1000個(gè)關(guān)鍵字為四位整數(shù)的記錄進(jìn)行排序 int b10000; for(i=0;i1000;i+) /直接按關(guān)鍵字散列 (即分配) for(j=ai;bj;j=(j+1)%10000); bj=ai; for(i=0,j=0;i1000;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. 【嚴(yán)題集10.42】序列的“中值記錄”指的是:如果將此序列排序后,它是第n/2個(gè)記錄。試寫一個(gè)求中值記錄的算法。10.42 typedef struct int gt; /大于該記錄的個(gè)數(shù) int lt; /小于該記錄的個(gè)數(shù) place; /整個(gè)序列中比某個(gè)關(guān)鍵字大或小的記錄個(gè)數(shù) int Get_Mid(int a ,int n) /求一個(gè)序列的中值記錄的位置 place bMAXSIZE; for(i=0;in;i+) /對(duì)每一個(gè)元素統(tǒng)計(jì)比它大和比它小的元素個(gè)數(shù)gt和lt for(j=0;jai) bi.gt+; else if(ajai) bi.lt+; mid=0; min_dif=abs(b0.gt-b0.lt); for(i=0;in;i+) /找出gt值與lt值最接近的元素,即為中值記錄 if(abs(bi.gt-bi.lt)min_dif) mid=i; return mid; /Get_Mid 10- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
5 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 排序 答案
鏈接地址:http://www.szxfmmzy.com/p-12786901.html