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

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

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

3、結(jié)點。2. 選擇題A插入排序和快速排序 B歸并排序和快速排序C選擇排序和歸并排序 D插入排序和歸并排序【解答】C【分析】選擇排序在最好、最壞、平均情況下的時間性能均為0（n2），歸并排序在最好、最壞、平均情況下的時間性能均為O（nlog2n）。下列序列中，（）是執(zhí)行第一趟快速排序的結(jié)果。A da， ax，eb，de，bb ff ha ， gc B cd ， eb，ax， da ff ha ，gc，bbC gc，ax，eb，cd， bb ff da ，ha D ax ， bb，cd，da ff eb ， gc， ha【解答】A【分析】此題需要按字典序比較，前半?yún)^(qū)間中的所有元素都應(yīng)小于ff,后半?yún)^(qū)

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

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

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

7、排序B快速排序C插入排序D起泡排序E歸并排序F堆排序【解答】C，A，D，B，B，D，F(xiàn)快速排序在（）情況下最不利于發(fā)揮其長處。A待排序的數(shù)據(jù)量太大B待排序的數(shù)據(jù)中含有多個相同值C待排序的數(shù)據(jù)已基本有序D待排序的數(shù)據(jù)數(shù)量為奇數(shù)【解答】C【分析】快速排序等改進的排序方法均適用于待排序數(shù)據(jù)量較大的情況，各種排序方法對待排序的數(shù)據(jù)中 是否含有多個相同值，待排序的數(shù)據(jù)數(shù)量為奇數(shù)或偶數(shù)都沒有影響。（）方法是從未排序序列中挑選兀素，并將其放入已排序序列的一端。A歸并排序B插入排序C快速排序D選擇排序【解答】D3. 判斷題如果某種排序算法是不穩(wěn)定的，則該排序方法沒有實際應(yīng)用價值?！窘獯稹垮e。一種排序算法適合于

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

9、>n/2時，ki, ki+1,kn均是葉子結(jié)點，所以一定是堆。4 已知數(shù)據(jù)序列為（12，5，9, 20，6，31，24），對該數(shù)據(jù)序列進行排序，寫出插入排序、起泡排序、快 速排序、簡單選擇排序、堆排序以及二路歸并排序每趟的結(jié)果。【解答】用上述排序方法的每趟結(jié)果如下：:插入曲E序：|初始鍵值序列口叮59 20 S 31| 第一趟結(jié)果512920831| 第二趟結(jié)果591220631|第三趟結(jié)果5912206317第四趟鰭果1569122031|第五趟結(jié)果569122031第六趟結(jié)果13聽9越202424；初始鍵值序列125g2063124 :第一趟結(jié)果512920E3124 ；第二趟結(jié)果5

10、8920123134 ；第三趟結(jié)果53920123134 第四這結(jié)果53g12203124 ;第五趙結(jié)果53g122031312 !第六趟結(jié)果589122024簡單選擇排序:24；24；24；24 丁24：243：31 :i快速排序：i iI初始鍵值序列1259 20 6 3124：;| 第一趟結(jié)果659 12203124:;| 第二趟結(jié)果569 122031241| 第三逍結(jié)果569 1220L2431：;第四趟結(jié)果56912202431j初始龍值序列応5P2063124第一逍結(jié)果59126202431第二趟結(jié)果5gC12202431第三趟結(jié)果5912202431第四趟結(jié)果56g122024

11、31起泡排序:I堆排序2i初始鍵值序列 I初始建堆結(jié)果 第一趟結(jié)果 :第二趟結(jié)果 策三遇結(jié)果 :第四趟結(jié)果 策五趟結(jié)果 ；第六趟結(jié)果|二=二-二亠一二 i3242012g 6 E L L L L520631iI2456912；56931 :5a2431刃202431 :122024si in202431 112202431 !24246 _JM3 g 9;二路歸并J®序：!初始鍵值序列12592063124 ：| 第一趟結(jié)果占12 920 631 E24:| 第二趟結(jié)果5P 1220 624 31;第三趟結(jié)果56912 20 24 31；'I5對n=7，給出快速排序一個最好情

12、況和最壞情況的初始排列的實例?！窘獯稹孔詈们闆r：4， 7，5，6，3，1，2最壞情況：7，6，5，4，3，2，16判別下列序列是否為堆，如不是，按照堆排序思想把它調(diào)整為堆，用圖表示建堆的過程。（1）（ 1，5，7，25，21，8，8，42）3（ 3，9，5，8，4，17，21，6）【解答】序列是堆，序列不是堆，調(diào)整為堆（假設(shè)為大根堆）的過程如圖8-5所示。堆調(diào)整的過程7 已知下列各種初始狀態(tài)(長度為n)的元素，試問當(dāng)利用直接插入排序進行排序時，至少需要進行多少次比較(要求排序后的記錄由小到大順序排列)？ 關(guān)鍵碼從小到大有序(keylv k ey2<< keyn )。 關(guān)鍵碼從大到小

13、有序(key1> key2>> keyn )。 奇數(shù)關(guān)鍵碼順序有序，偶數(shù)關(guān)鍵碼順序有序(key1< key3<，key2 key4)。br /> 前半部分元素按關(guān)鍵碼順序有序，后半部分兀素按關(guān)鍵碼順序有序，即：(key1< key2< < keym ， keym+1< keym+2< 【解答】依題意，最好情況下的比較次數(shù)即為最少比較次數(shù)。 插入第i (2<i <n個元素的比較次數(shù)為1，因此總的比較次數(shù)為：1+1+ +1=n-1 插入第i (2<i <n個元素的比較次數(shù)為i，因此總的比較次數(shù)為：2+3+ +

14、n=(n-1)(n+2)/2 比較次數(shù)最少的情況是所有記錄關(guān)鍵碼按升序排列，總的比較次數(shù)為：n-1在后半部分元素的關(guān)鍵碼均大于前半部分元素的關(guān)鍵碼時需要的比較次數(shù)最少，總的比較次數(shù)為:n-18 算法設(shè)計直接插入排序中尋找插入位置的操作可以通過折半查找來實現(xiàn)。據(jù)此寫一個改進的插入排序的算法?！窘獯稹坎迦肱判虻幕舅枷胧牵好刻藦臒o序區(qū)中取岀一個元素，再按鍵值大小插入到有序區(qū)中。對于有 序區(qū)，當(dāng)然可以采用折半查找來確定插入位置。具體算法如下：mosimage 設(shè)待排序的記錄序列用單鏈表作存儲結(jié)構(gòu)，試寫岀直接插入排序算法。【解答】本算法采用的存儲結(jié)構(gòu)是帶頭結(jié)點的單鏈表。首先找到元素的插入位置，然后把元

15、素從鏈表中原 位置刪除，再插入到相應(yīng)的位置處。具體算法如下： 設(shè)待排序的記錄序列用單鏈表作存儲結(jié)構(gòu)，試寫岀簡單選擇排序算法?！窘獯稹繀⒁?22。 對給定的序號j (1 v jv n),要求在無序記錄 A1An中找到按關(guān)鍵碼從小到大排在第j位上的記錄,試?yán)每焖倥判虻膭澐炙枷朐O(shè)計算法實現(xiàn)上述查找。【解答】本算法不要求將整個記錄進行排序，而只進行查找第j個記錄。插入排序算Sightsortvoid StraightSort (Node * first) 如口血請參見第二童單鏈表的結(jié)點結(jié)構(gòu) (pre=first; pMirst->nesfL; q=p->next,while (p)(wh

16、ile (q!=p)(while (p->data<q->data)pr&=p, p-p'ext, if (pF=q) u-=q->ncKtP pre>next=q,q->neirt=p; qp赳q=q->next;preMir st; pMkst->nart;) 寫岀快速排序的非遞歸調(diào)用算法?！窘獯稹肯日{(diào)用劃分函數(shù) Quickpass （劃分函數(shù)同教材），以確定中間位置，然后再借助棧分別對中間元 素的左、右兩邊的區(qū)域進行快速排序。査找第j小算法Search、 I I、 、 t t 卜=" iniSearch (mt r

17、 p int int j)(s=l; tpADevci (r, s, t);while (k!=j)if (k<j) k=4?evo(t; k+lt t); else kDevo (匚翼 k 1); return rj;int Dcvo (mt r p nit low, int high)Mow, jhigh; xrlow|；;while (i<j)whileCr£i&& i<j)廠亠;ifg爼Ml； i+Jwhile(ri <x && Kj)ipifCKO«=!比廠 J)電If return 耳一個線性表中的元素為正

18、整數(shù)或負(fù)整數(shù)。設(shè)計算法將正整數(shù)和負(fù)整數(shù)分開，使線性表的前一半為負(fù)整數(shù), 后一半為正整數(shù)。不要求對這些元素排序，但要求盡量減少比較次數(shù)。【解答】本題的基本思想是：先設(shè)置好上、下界和軸值，然后分別從線性表兩端查找正數(shù)和負(fù)數(shù)，找到后 進行交換，直到上下界相遇。算法如下：快速排序非還歸算法Quicks ort void Quicksort(int r ,int n) (top1,"采用順序橫并假定不會發(fā)生溢出 lowl;high=n;while (low<higji 11 top!=-l)(while (low<high)( i=Qui 亡 kp 包站(rT low, high)

19、, S+top=i; high=i-l;if (tciplhl) Ffp. lowM+1; 已知（k1, k2,，kn是堆，試寫一算法將（k1, k2,，kn, kn+1 ）調(diào)整為堆【解答】增加一個元素應(yīng)從葉子向根方向調(diào)整，假設(shè)調(diào)整為小根堆。正理整數(shù)分開舜址Devutvoid Devot (int r , int n) while (i<j)(while (rj >0 && i<j) j; while (ri <0 && i<j) i+; if (i<j) 4；給定n個記錄的有序序列 An和m個記錄的有序序列 Bm，將它們歸并

20、為一個有序序列，存放在 Cm+n中，試寫出這一算法?！窘獯稹坎捎枚窔w并排序中一次歸并的思想，設(shè)三個參數(shù)i、j和k分別指向兩個待歸并的有序序列和最終有序序列的當(dāng)前記錄，初始時i、j分別指向兩個有序序列的第一個記錄，即i=1，j=1，k指向存放歸并結(jié)果的位置，即k=1。然后，比較i和j所指記錄的關(guān)鍵碼，取岀較小者作為歸并結(jié)果存入k所指位置，直至兩個有序序列之一的所有記錄都取完，再將另一個有序序列的剩余記錄順序送到歸并后的有序序列中。插入法逮堆算法InsertHeapvoid InsertHeap(int r , int k) "rl卜開為堆將 rlrk+l調(diào)整為堆 (Kr=rk+1;i

21、=k+l,while (i/2>0 && ri/2>s)皿；學(xué)習(xí)自測及答案1 評價基于比較的排序算法的時間性能，主要標(biāo)準(zhǔn)是（）和（）?！窘獯稹筷P(guān)鍵碼的比較次數(shù)，記錄的移動次數(shù)2. 對n個記錄組成的任意序列進行簡單選擇排序，所需進行的關(guān)鍵碼間的比較次數(shù)總共為（）【解答】比較次數(shù)=（n-1）+（n- 2）+2+1=nX（n -1）/23. 對于一個堆，按二叉樹的層序遍歷可以得到一個有序序列，這種說法是否正確？【解答】錯誤。堆的定義只規(guī)定了結(jié)點與其左右孩子結(jié)點之間的大小關(guān)系，而同一層上的結(jié)點之間并無明 確的大小關(guān)系。4 一組記錄的關(guān)鍵碼為46, 79, 56, 38, 4

22、0, 84，則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一 次劃分結(jié)果為（）。A 40, 38, 46, 56, 79, 84 B 40, 38, 46, 79, 56, 84C 40, 38, 46, 84, 56, 79 D 84, 79, 56, 46, 40, 38【解答】A5 排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是（）。A直接插入排序 B簡單選擇排序 C快速排序D歸并排序【解答】C6. 用直接插入排序?qū)ο旅嫠膫€序列進行由小到大排序，元素比較次數(shù)最少的是（）。A 94, 32, 40, 90, 80, 46, 21,69 B 21,32, 46, 40, 80, 69, 90, 9

23、4C 32, 40, 21,46, 69, 94, 90, 80 D 90, 69, 80, 46, 21,32, 94, 40【解答】B7. 對數(shù)列（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, 84 15, 20, 21,25, 27, 35, 47, 68, 84則采用的排序方法是（）。A希爾排序B簡單選擇排序C快速排序D歸并排序【解答

24、】C8. 如果只想得到一個序列中第k個最小元素之前的部分排序序列，最好采用什么排序方法？為什么？對于序列57, 40, 38, 11, 13, 34, 48, 75, 25, 6, 19, 9, 7，得到其第4個最小元素之前的部分序列 6,7,9,11，使用所選擇的排序算法時，要執(zhí)行多少次比較？【解答】采用堆排序最合適，依題意可知只需取得第k個最小元素之前的排序序列時，堆排序的時間復(fù)雜度O（n+klog2n），若kwnlog2n，則得到的時間復(fù)雜性是O（n）。對于上述序列得到其前4個最小元素，使用堆排序?qū)崿F(xiàn)時，執(zhí)行的比較次數(shù)如下：初始建堆：比較20次，得到6;第一次調(diào)整：比較5次，得到7;第二

25、次調(diào)整：比較4次，得到9;第三次調(diào)整：比較 5次，得到11 o9 .荷蘭國旗問題。要求重新排列一個由字符R, W, B （ R代表紅色，W代表白色，B代表蘭色，這都是荷蘭國旗的顏色）構(gòu)成的數(shù)組，使得所有的R都排在最前面，W排在其次，B排在最后。為荷蘭國旗問題設(shè)計一個算法，其時間性能是 O（n）?！窘獯稹吭O(shè)立三個參數(shù)i、j、k，其中i以前的元素全部為紅色；j表示當(dāng)前元素；k以后的元素全部為藍(lán)色。 這樣，就可以根據(jù)j的顏色，把其交換到序列的前部或后部。具體算法如下:_次歸并算jUhion Ivoid Union(inl A , int n, int B ,ini n, int C)i=l;j=UU

26、while (i<=n &生 j<=m)(if(Ai<-Bj) Ck+-Ai+;dseCk+=Bj+>)while(K=n) Ck+=Ai+-b;while (j<=m) Ck+=&+,10.已知記錄序列 A1An中的關(guān)鍵碼各不相同，可按如下方法實現(xiàn)計數(shù)排序：另設(shè)一個數(shù)組C1Cn，對每個記錄 Ai，統(tǒng)計序列中關(guān)鍵碼比它小的記錄個數(shù) Ci，則Ci=0的記錄必為關(guān)鍵碼最小的記 錄，Ci=1的記錄必為關(guān)鍵碼次小的記錄，依此類推，即按Ci值的大小對A中記錄進行重新排列。試編寫算法實現(xiàn)上述計數(shù)排序?！窘獯稹烤唧w算法如下：荷蘭國旗算法FlagAdjust _e

27、num C olor Red, White, Blu e);void FlagAdpst (Color a , int n)(i=0;j=O?k-n-l;whileswitch ajcase Red: aR+ aj+t 膠換元素 treak,case White: j+七break,case Blue: aj+ breali;11.對于記錄序列A1An可按如下如下方法實現(xiàn)奇偶交換排序：第一趟對所有的奇數(shù)i,將Ai和Ai+1進行比較，第二趟對所有的偶數(shù)i,將Ai和Ai+1進行比較，每次比較時若 Ai>Ai+1，則將二者交換，然后重復(fù)上述排序過程，直至整個數(shù)組有序。編寫算法實現(xiàn)上述奇偶交換排

28、序?！窘獯稹烤唧w算法如下:計數(shù)排厚算法Count初rt void CountSort(int A int B int n) 僦t數(shù)狙 A攤序，結(jié)果存于數(shù)組 B 中 far (A 1; Ki, i+)川計數(shù)數(shù)組C初始化Ci=0;far (i=l?i<=n,i)(far(J=l,j<-nj+)if (Aj<Ai) Ci+-F;膽充計每于記錄按關(guān)犍碣犬4啲次序)fur (i=l, i<=n; i+)BCi+l=Ai; 懂排記錄)Whe n you are old and grey and full of sleep,And no ddi ng by the fire, take dow n this book,And slowly read, and dream of the soft lookYour eyes had once, and of their shadows deep;How many loved your mome nts of