數(shù)據(jù)結(jié)構(gòu)與算法答案

1、第8章排序技術(shù)課后習(xí)題講解1.填空題（1）排序的主要目的是為了以后對(duì)已排序的數(shù)據(jù)元素進(jìn)行（）?！窘獯稹坎檎摇痉治觥繉?duì)已排序的記錄序列進(jìn)行查找通常能提高查找效率。對(duì)n個(gè)元素進(jìn)行起泡排序，在（）情況下比較的次數(shù)最少，其比較次數(shù)為（）。在（）情況下比較次數(shù)最多，其比較次數(shù)為（）?！窘獯稹空?，n-1,反序，n（n-1）/2對(duì)一組記錄（54,38,96,23,15,72,60,45,83）進(jìn)行直接插入排序，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較（）次?！窘獯稹?【分析】當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，該有序表中有2個(gè)記錄大于60o對(duì)一組記錄（54,38,96,23,15,72,60,

2、45,83）進(jìn)行快速排序，在遞歸調(diào)用中使用的棧所能達(dá)到的最大深度為（）?！窘獯稹?對(duì)n個(gè)待排序記錄序列進(jìn)行快速排序，所需要的最好時(shí)間是（），最壞時(shí)間是（）?！窘獯稹縊（nlog2n）,O（n2）利用簡單選擇排序?qū)個(gè)記錄進(jìn)行排序，最壞情況下，記錄交換的次數(shù)為（）?！窘獯稹縩-1如果要將序列（50,16,23,68,94,70,73）建成堆，只需把16與（）交換。【解答】50對(duì)于鍵值序列（12,13,11,18,60,15,7,18,25,100）,用篩選法建堆，必須從鍵值為（）的結(jié)點(diǎn)開始。【解答】60【分析】60是該鍵值序列對(duì)應(yīng)的完全二叉樹中最后一個(gè)分支結(jié)點(diǎn)。2 .選擇題（1）下述排序方法中，

3、比較次數(shù)與待排序記錄的初始狀態(tài)無關(guān)的是（）。A插入排序和快速排序B歸并排序和快速排序C選擇排序和U3并排序D插入排序和歸并排序【解答】C【分析】選擇排序在最好、最壞、平均情況下的時(shí)間性能均為下的時(shí)間性能均為O（nlog2n）。O（n2）,歸并排序在最好、最壞、平均情況下列序列中，（）是執(zhí)行第一趟快速排序的結(jié)果。Ada,ax,eb,de,bbffha,gcBcd,eb,ax,daffha,gc,bbCgc,ax,eb,cd,bbffda,haDax,bb,cd,daffeb,gc,ha【解答】A【分析】此題需要按字典序比較，前半?yún)^(qū)間中的所有元素都應(yīng)小于ff,后半?yún)^(qū)間中的所有元素都應(yīng)大于ff。對(duì)初

4、始狀態(tài)為遞增有序的序列進(jìn)行排序，最省時(shí)間的是（），最費(fèi)時(shí)間的是（）。已知待排序序列中每個(gè)元素距其最終位置不遠(yuǎn)，則采用（）方法最節(jié)省時(shí)間。A堆排序B插入排序C快速排序D直接選擇排序【解答】B,C,B【分析】待排序序列中每個(gè)元素距其最終位置不遠(yuǎn)意味著該序列基本有序。（4）堆的形狀是一棵（）。A二叉排序樹B滿二叉樹C完全二叉樹D判定樹【解答】C【分析】從邏輯結(jié)構(gòu)的角度來看，堆實(shí)際上是一種完全二叉樹的結(jié)構(gòu)。當(dāng)待排序序列基本有序或個(gè)數(shù)較小的情況下，最佳的內(nèi)部排序方法是（），就平均時(shí)間而言，（）最佳。A直接插入排序B起泡排序C簡單選擇排序D快速排序【解答】A,D設(shè)有5000個(gè)元素，希望用最快的速度挑選出前

5、10個(gè)最大的，采用（）方法最好。A快速排序B堆排序C希爾排序D歸并排序【解答】B【分析】堆排序不必將整個(gè)序列排序即可確定前若干個(gè)最大（或最?。┰?。設(shè)要將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關(guān)鍵碼按升序排列，則（）是起泡排序一趟掃描的結(jié)果，（）是增量為4的希爾排序一趟掃描的結(jié)果，（）二路歸并排序一趟掃描的結(jié)果，（）是以第一個(gè)元素為軸值的快速排序一趟掃描的結(jié)果，（）是堆排序初始建堆的結(jié)果。A（F,H,C,D,P,A,M,Q,R,S,Y,X）B（P,A,C,S,Q,D,F,X,R,H,M,Y）C（A,D,C,R,F,Q,M,S,Y,P,H,X）D（H,C,Q,P,A,M,S,

6、R,D,F,X,Y）E（H,Q,C,Y,A,P,M,S,D,R,F,X）【解答】D,B,E,A,C【分析】此題需要按字典序比較，并且需要掌握各種排序方法的執(zhí)行過程。排序的方法有很多種，（）法從未排序序列中依次取出元素，與已排序序列中的元素作比較，將其放入已排序序列的正確位置上。（）法從未排序序列中挑選元素，并將其依次放入已排序序列的一端。交換排序是對(duì)序列中元素進(jìn)行一系列比較，當(dāng)被比較的兩元素為逆序時(shí)，進(jìn)行交換；（）和（）是基于這類方法的兩種排序方法，而（）是比（）效率更高的方法；（）法是基于選擇排序的一種方法，是完全二叉樹結(jié)構(gòu)的一個(gè)重要應(yīng)用。A選擇排序B快速排序C插入排序D起泡排序E歸并排序F

7、堆排序【解答】C,A,D,B,B,D,F快速排序在()情況下最不利于發(fā)揮其長處。A待排序的數(shù)據(jù)量太大B待排序的數(shù)據(jù)中含有多個(gè)相同值C待排序的數(shù)據(jù)已基本有序D待排序的數(shù)據(jù)數(shù)量為奇數(shù)【解答】C【分析】快速排序等改進(jìn)的排序方法均適用于待排序數(shù)據(jù)量較大的情況，各種排序方法對(duì)待排序的數(shù)據(jù)中是否含有多個(gè)相同值，待排序的數(shù)據(jù)數(shù)量為奇數(shù)或偶數(shù)都沒有影響。(10)()方法是從未排序序列中挑選元素，并將其放入已排序序列的一端。A歸并排序B插入排序C快速排序D選擇排序【解答】D3 .判斷題(1)如果某種排序算法是不穩(wěn)定的，則該排序方法沒有實(shí)際應(yīng)用價(jià)值。【解答】錯(cuò)。一種排序算法適合于某種特定的數(shù)據(jù)環(huán)境，有時(shí)對(duì)排序的穩(wěn)

8、定性沒有要求。當(dāng)待排序的元素很大時(shí)，為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜性的主要因素?！窘獯稹繉?duì)。此時(shí)著重考慮元素的移動(dòng)次數(shù)。對(duì)n個(gè)記錄的集合進(jìn)行快速排序，所需要的附加空間是O(n)。【解答】錯(cuò)。最壞情況下是O(n)。堆排序所需的時(shí)間與待排序的記錄個(gè)數(shù)無關(guān)?！窘獯稹垮e(cuò)。堆排序最好、最壞及平均時(shí)間均為O(nlog2n),是待排序的記錄個(gè)數(shù)n的函數(shù)。一般來說，待排序的記錄個(gè)數(shù)越多，排序所消耗的時(shí)間也就越多。設(shè)有鍵值序列(k1,k2,，kr),當(dāng)i>n/2時(shí)，任何一個(gè)子序列(ki,ki+1,，kn一定是堆?！窘獯稹繉?duì)。當(dāng)i>n/2時(shí)，ki,ki+1,，kn均是葉

9、子結(jié)點(diǎn)，所以一定是堆。4 .已知數(shù)據(jù)序列為(12,5,9,20,6,31,24),對(duì)該數(shù)據(jù)序列進(jìn)行排序，寫出插入排序、起泡排序、快速排序、簡單選擇排序、堆排序以及二路歸并排序每趟的結(jié)果。【解答】用上述排序方法的每趟結(jié)果如下：初始謔值序列12592063124第一趟靖果5129083124第二趟緒果5g122063124第三趟結(jié)果59122063124第四趟結(jié)果569U203124第五趟培果56912203124第六趟造果569122U2431插入排序:初始鍵值序列125g2063124第一趟結(jié)果51292083124第二超結(jié)果58920123124第三趟結(jié)果53g20123124第四趟結(jié)果53

10、912203124第五趟結(jié)果53912203124第六趟結(jié)果58912202431簡單選擇排序:快速排序，初始建值序列12592063124第一越結(jié)果659U2031243第二通結(jié)果56912203124第三趟結(jié)果56912202431第四趟結(jié)果56912202431起泡排序，初始碑值序列125P2。631241第一越結(jié)果5912fi202431第二迤結(jié)果59612202431第三趟結(jié)果56912202431第四趟結(jié)果56g12202431堆排序：初始鍵值序列初始建堆結(jié)果第一甚結(jié)果第二趟結(jié)果第三趟結(jié)果第四趟結(jié)果第五趟結(jié)果第六趟造果m24201296cLLLL55121224nu231二路歸并排

11、序：初始誕值序列12592063124第一趟結(jié)果51292063124第二趟結(jié)果59122062431第三趟結(jié)果569122024315 .對(duì)n=7,給出快速排序一個(gè)最好情況和最壞情況的初始排列的實(shí)例?！窘獯稹孔詈们闆r：4,7,5,6,3,1,2最壞情況：7,6,5,4,3,2,16 .判別下列序列是否為堆，如不是，按照堆排序思想把它調(diào)整為堆，用圖表示建堆的過程。(1,5,7,25,21,8,8,42)(2)(3,9,5,8,4,17,21,6)【解答】序列是堆，序列不是堆，調(diào)整為堆(假設(shè)為大根堆)的過程如圖8-5所示。堆調(diào)整的過程7.已知下列各種初始狀態(tài)(長度為n)的元素，試問當(dāng)利用直接插入

12、排序進(jìn)行排序時(shí)，至少需要進(jìn)行多少次比較(要求排序后的記錄由小到大順序排列)？(1)關(guān)鍵碼從小到大有序(key1<key2<<keyn關(guān)鍵碼從大到小有序(key1>key2>>keyn奇數(shù)關(guān)鍵碼順序有序，偶數(shù)關(guān)鍵碼順序有序(按關(guān)鍵碼順序有序，后半部分元素按關(guān)鍵碼順序有序，(key1<key2<<keym,keym+1<keym+2<-）。key1<key3V,key2key4）。br/>前半部分元素即：【解答】依題意，最好情況下的比較次數(shù)即為最少比較次數(shù)。(1)插入第i(2<i<ii)個(gè)元素的比較次數(shù)為1,

13、因此總的比較次數(shù)為:1+1+1=n-1插入第i(2<i<ii)個(gè)元素的比較次數(shù)為i,因此總的比較次數(shù)為:2+3+n=(n-1)(n+2)/2比較次數(shù)最少的情況是所有記錄關(guān)鍵碼按升序排列，總的比較次數(shù)為:n-1在后半部分元素的關(guān)鍵碼均大于前半部分元素的關(guān)鍵碼時(shí)需要的比較次數(shù)最少，總的比較次數(shù)為:n-18.算法設(shè)計(jì)(1)直接插入排序中尋找插入位置的操作可以通過折半查找來實(shí)現(xiàn)。據(jù)此寫一個(gè)改進(jìn)的插入排序的算法?！窘獯稹坎迦肱判虻幕舅枷胧牵好刻藦臒o序區(qū)中取出一個(gè)元素，再按鍵值大小插入到有序區(qū)中。對(duì)于有序區(qū)，當(dāng)然可以采用折半查找來確定插入位置。具體算法如下：mosimage設(shè)待排序的記錄序列

14、用單鏈表作存儲(chǔ)結(jié)構(gòu)，試寫出直接插入排序算法?！窘獯稹勘舅惴ú捎玫拇鎯?chǔ)結(jié)構(gòu)是帶頭結(jié)點(diǎn)的單鏈表。首先找到元素的插入位置，然后把元素從鏈表中原位置刪除，再插入到相應(yīng)的位置處。具體算法如下：插入排序算法Skm圓tSortvoidStraightsort(intr,int口)(fori<=n;i+)1P)-lowl,fhg=l,while(10w<=higha&flag)(mi(i=(low+high)f2tif(r0司曲可)high-mid-1;elseif(r(0lowi=nji(i+1,elseflag=D,for(j=i-1;j>=mid;j一)珀+UF,rmid-r0

15、;)設(shè)待排序的記錄序列用單鏈表作存儲(chǔ)結(jié)構(gòu)，試寫出簡單選擇排序算法。【解答】參見8,2.2o對(duì)給定的序號(hào)j(1<j<n),要求在無序記錄A1An中找到按關(guān)鍵碼從小到大排在第j位上的記錄,試?yán)每焖倥判虻膭澐炙枷朐O(shè)計(jì)算法實(shí)現(xiàn)上述查找?！窘獯稹勘舅惴ú灰髮⒄麄€(gè)記錄進(jìn)行排序，而只進(jìn)行查找第j個(gè)記錄。插入排序算法StiaightSortvoidSti3ightSort(NodE*first)附口函請(qǐng)參見第二童單鏈表的結(jié)點(diǎn)結(jié)構(gòu)(pre=first;p=firsl->nerl;q=p*>neKt,while(p)(while(q!邛)(while(p->data<q&g

16、t;data)P51,p-p_next,).if(pF=q)(u-=q>next.Rpre'>ncst=q7q->nezt=p;qfelseq=q->next;)pre=first;pMirst->next;)寫出快速排序的非遞歸調(diào)用算法?！窘獯稹肯日{(diào)用劃分函數(shù)Quickpass（劃分函數(shù)同教材），以確定中間位置，然后再借助棧分別對(duì)中間元素的左、右兩邊的區(qū)域進(jìn)行快速排序。查找第j小算法£組曲intSearch(mtr,mtn,intj)(s-i；ifgDevci年s11);while(k!弓)if(k<j)k=Oevo(t;k+ltt);e

17、lsekDevo(r,kH);returnrj;)mtDevo(mtrpmtlow,inthigh)(i=low,jhigh；器叩口刷；while(i<j)(whileCrj>=xj;可磅通Mfl；卦+淳while(ri&&i<j)i+;ifg)口比廣；)屯Fretumi;一個(gè)線性表中的元素為正整數(shù)或負(fù)整數(shù)。設(shè)計(jì)算法將正整數(shù)和負(fù)整數(shù)分開，使線性表的前一半為負(fù)整數(shù),后一半為正整數(shù)。不要求對(duì)這些元素排序，但要求盡量減少比較次數(shù)?！窘獯稹勘绢}的基本思想是：先設(shè)置好上、下界和軸值，然后分別從線性表兩端查找正數(shù)和負(fù)數(shù)，找到后進(jìn)行交換，直到上下界相遇。算法如下：快速排序非

18、強(qiáng)歸算法QuicksortvoidQuicksort(intr,intn)top1,“采用順序楨并假定不會(huì)發(fā)生溢出low&hhigh3n;while(low<high11top!=-l)(whale(low<high)(Quickpass(r,low,high),S+top=i;high=+I;if(topl-l)S-lop;10W=!+l；已知（k1,k2,，k。是堆，試寫一算法將（k1,k2,，kn,kn+1）調(diào)整為堆【解答】增加一個(gè)元素應(yīng)從葉子向根方向調(diào)整，假設(shè)調(diào)整為小根堆。正負(fù)整數(shù)分開算法Devut|voidDevol(intr,intn)(i-1Jn;while(

19、i<»(whileCrj>0&&i<j)j一；while(ri<0-ii+,if(i<j)(，度城元素i+；L,)給定n個(gè)記錄的有序序列An和m個(gè)記錄的有序序列Bm,將它們歸并為一個(gè)有序序列，存放在Cm+n中，試寫出這一算法?！窘獯稹坎捎枚窔w并排序中一次歸并的思想，設(shè)三個(gè)參數(shù)i、j和k分別指向兩個(gè)待歸并的有序序列和最終有序序列的當(dāng)前記錄，初始時(shí)i、j分別指向兩個(gè)有序序列的第一個(gè)記錄，即i=1,j=1,k指向存放歸并結(jié)果的位置，即k=1。然后，比較i和j所指記錄的關(guān)鍵碼，取出較小者作為歸并結(jié)果存入k所指位置，直至兩個(gè)有序序列之一的所有記錄

20、都取完，再將另一個(gè)有序序列的剩余記錄順序送到歸并后的有序序列中。插入法建堆算法nsertHeapvoidInsertHeap(intr,intk)傷O明為堆，將姓1*唯+1調(diào)整為堆(i=k+l,while(i/2>0&&ri/2>x)(aHR；i旬老中曰；學(xué)習(xí)自測及答案1 .評(píng)價(jià)基于比較的排序算法的時(shí)間性能，主要標(biāo)準(zhǔn)是（【解答】關(guān)鍵碼的比較次數(shù)，記錄的移動(dòng)次數(shù)2 .對(duì)n個(gè)記錄組成的任意序列進(jìn)行簡單選擇排序，所需進(jìn)行的關(guān)鍵碼間的比較次數(shù)總共為（【解答】比較次數(shù)=（n-1）+（n-2）+2+1=nX（n-1）/23 .對(duì)于一個(gè)堆，按二叉樹的層序遍歷可以得到一個(gè)有序序列，

21、這種說法是否正確？【解答】錯(cuò)誤。堆的定義只規(guī)定了結(jié)點(diǎn)與其左右孩子結(jié)點(diǎn)之間的大小關(guān)系，而同一層上的結(jié)點(diǎn)之間并無明確的大小關(guān)系。4 .一組記錄的關(guān)鍵碼為46,79,56,38,40,84),則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為()。A40,38,46,56,79,84)B40,38,46,79,56,84)C40,38,46,84,56,79)D84,79,56,46,40,38)【解答】A5 .排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是()。A直接插入排序B簡單選擇排序C快速排序D歸并排序【解答】C6 .用直接插入排序?qū)ο旅嫠膫€(gè)序列進(jìn)行由小到大排序，元素比較次數(shù)最少的是()

22、。A94,32,40,90,80,46,21,69B21,32,46,40,80,69,90,94C32,40,21,46,69,94,90,80D90,69,80,46,21,32,94,40【解答】B7 .對(duì)數(shù)列(25,84,21,47,15,27,68,35,20)進(jìn)行排序，元素序列的變化情況如下：(1) 25,84,21,47,15,27,68,35,20(2)20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84則采用的排序方法是()。A希爾排序B簡單選擇排序C快速排序D歸并排序【解

23、答】C8 .如果只想得到一個(gè)序列中第k個(gè)最小元素之前的部分排序序列，最好采用什么排序方法？為什么？對(duì)于序列57,40,38,11,13,34,48,75,25,6,19,9,7)，得到其第4個(gè)最小元素之前的部分序列6,7,9,11),使用所選擇的排序算法時(shí)，要執(zhí)行多少次比較？【解答】采用堆排序最合適，依題意可知只需取得第k個(gè)最小元素之前的排序序列時(shí)，堆排序的時(shí)間復(fù)雜度O(n+klog2n),若k<nlog2n,則得到的時(shí)間復(fù)雜性是0(n)。對(duì)于上述序列得到其前4個(gè)最小元素，使用堆排序?qū)崿F(xiàn)時(shí)，執(zhí)行的比較次數(shù)如下：初始建堆：比較20次，得到6;第一次調(diào)整：比較5次，得到7;第二次調(diào)整：比較4次，得到9;第三次調(diào)整：比較5次，得到11o9 .荷蘭國旗問題。要求重新排列一個(gè)由字符R,W,B(R代表紅色，W代表白色，B代表蘭色，這都是荷蘭國旗的顏色)構(gòu)成的數(shù)組，使得所有的R都排在最前面，W排在其次，B排在最后。為荷蘭國旗問題設(shè)計(jì)一個(gè)算法，其時(shí)間性能是O(n)o【解答】設(shè)立三個(gè)參數(shù)i、j、k,其中i以前的元素全部為紅色；j表示當(dāng)前元素；k以后的元素全部為藍(lán)色。這樣，就可以根據(jù)j的顏色，把其交換到序列的前部或后部。具體算法如下:一次歸并算法必記口voidUnion(n