算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）（第2版） 第12章課后習(xí)題答案

PAGEPAGE4習(xí)題答案選擇題1-5：ABCDC6-10：DCCCC填空題1、（1）比較（2）移動2、（1）減?。?）13、冒泡快速4、希爾排序、簡單選擇排序、快速排序、堆排序等5、外排序判斷題1-5：錯錯錯錯對應(yīng)用題1、設(shè)待排序的關(guān)鍵字序列為{15，21，6，30，23，6′，20，17}，試分別寫出使用以下排序方法每趟排序后的結(jié)果。(1)直接插入排序 (2)希爾排序(增量為5，2，1) (3)冒泡排序 (4)快速排序 (5)直接選擇排序 (6)堆排序(7)二路歸并排序 【解答】(1)直接插入排序初始關(guān)鍵字序列：15，21，6，30，23，6′，20，17第一趟直接插入排序：【15，21】第二趟直接插入排序：【6，15，21】第三趟直接插入排序：【6，15，21，30】第四趟直接插入排序：【6，15，21，23，30】第五趟直接插入排序：【6，6′，15，21，23，30】第六趟直接插入排序：【6，6′，15，20，21，23，30】第七趟直接插入排序：【6，6′，15，17，20，21，23，30】(2)希爾排序(增量為5，2，1)初始關(guān)鍵字序列：15，21，6，30，23，6′，20，17第一趟希爾排序：6′，20，6，30，23，15，21，17第二趟希爾排序：6′，15，6，17，21，20，23，30第三趟希爾排序：6′，6，15，17，20，21，23，30(3)起泡排序初始關(guān)鍵字序列：15，21，6，30，23，6′，20，17第一趟起泡排序：15，6，21，23，6′，20，17，30第二趟起泡排序：6，15，21，6′，20，17，23，30第三趟起泡排序：6，15，6′，20，17，21，23，30第四趟起泡排序：6，6′，15，17，20，21，30，23第五趟起泡排序：6，6′，15，17，20，21，30，23(4)快速排序初始關(guān)鍵字序列：15，21，6，30，23，6′，20，17第一趟快速排序：【6′，6】15【30，23，21，20，17】第二趟快速排序：6′，6，15【17，23，21，20】30第三趟快速排序：6′，6，15，17【23，21，20】30第四趟快速排序：6′，6，15，17，【20，21】23，30第五趟快速排序：6，6′，15，17，20，21，30，23(5)直接選擇排序初始關(guān)鍵字序列：15，21，6，30，23，6′，20，17第一趟直接選擇排序：6，21，15，30，23，6′，20，17第二趟直接選擇排序：6，6′，15，30，23，21，20，17第三趟直接選擇排序：6，6′，15，30，23，21，20，17第四趟直接選擇排序：6，6′，15，17，23，21，20，30第五趟直接選擇排序：6，6′，15，17，20，21，23，30第六趟直接選擇排序：6，6′，15，17，20，21，23，30第七趟直接選擇排序：6，6′，15，17，20，21，23，30(6)堆排序 初始關(guān)鍵字序列：15，21，6，30，23，6′，20，17初始堆：6，17，6’第一次調(diào)堆：6’第二次調(diào)堆：15，17，20，21，23，30，【6’第三次調(diào)堆：17，21，20，30，23，【15，6’，6】第四次調(diào)堆：20，21，23，30，【17，15，6’，6】第五次調(diào)堆：21，30，23，【20，17，15，6’，6】第六次調(diào)堆：23，30，【21，20，17，15，6’，6】第七次調(diào)堆：30，【23，21，20，17，15，6’，6】堆排序結(jié)果調(diào)堆：【30，23，21，20，17，15，6’，6】(7)二路歸并排序初始關(guān)鍵字序列：15，21，6，30，23，6′，20，17二路歸并排序結(jié)果：15，17，20，21，23，30，6’，6final↑↑first2、在各種排序方法中，哪些是穩(wěn)定的？哪些是不穩(wěn)定的？并為每一種不穩(wěn)定的排序方法舉出一個不穩(wěn)定的實(shí)例?！窘獯稹恳娤卤恚号判蚍椒ㄆ骄鶗r間最壞情況輔助空間穩(wěn)定性不穩(wěn)定排序舉例直接插入排序O(n2)O(n2)O(1)穩(wěn)定折半插入排序O(n2)O(n2)O(1)穩(wěn)定二路插入排序O(n2)O(n2)O(n)穩(wěn)定表插入排序O(n2)O(n2)O(1)穩(wěn)定起泡排序O(n2)O(n2)O(1)穩(wěn)定直接選擇排序O(n2)O(n2)O(1)不穩(wěn)定2,2’希爾排序O(n1.3)O(n1.3)O(1)不穩(wěn)定3,2,2’快速排序O(nlog2n)O(n2)O(log2n)不穩(wěn)定2,2’堆排序O(nlog2n)O(nlog2n)O(1)不穩(wěn)定2,1,1’2-路歸并排序O(nlog2n)O(nlog2n)O(n)穩(wěn)定基數(shù)排序O(d*(rd+n))O(d*(rd+n))O(rd)穩(wěn)定3、判斷下面的每個結(jié)點(diǎn)序列是否能表示堆，如果不是堆，請把它調(diào)整成堆。100，90，80，60，85，75，20，25，10，70，65，50100，70，50，20，90，75，60，25，10，85，65，80【解答】(1)是堆(2)不是堆。調(diào)成大堆：100,90,80,25,85,75,60,20,10,70,65,504、奇偶交換排序如下所述：對于初始序列A[1]，A[2]，…，A[n]，第一趟對所有奇數(shù)i(1<=i<n)，將A[i]和A[i+1]進(jìn)行比較，若A[i]>A[i+1]，則將兩者交換；第二趟對所有偶數(shù)i(2<=i<n)，將A[i]和A[i+1]進(jìn)行比較，若A[i]>A[i+1]，則將兩者交換。第三趟對所有奇數(shù)i(1<=i<n)；第四趟對所有偶數(shù)i(2<=i<n)，…，依次類推直至到整個序列有序?yàn)橹埂?1)分析這種排序方法的結(jié)束條件。(2)寫出用這種排序方法對35，70，33，65，24，21，33進(jìn)行排序時，每一趟的結(jié)果?！窘獯稹颗判蚪Y(jié)束條件為，連續(xù)的第奇數(shù)趟排序和第偶數(shù)趟排序都沒有交換。第一趟奇數(shù)：35,70,33,65,21,24,33第二趟偶數(shù)：35,33,70,21,65,24,33第三趟奇數(shù)：33,35,21,70,24,65,33第四趟偶數(shù)：33,21,35,24,70,33,65第五趟奇數(shù)：21,33,24,35,33,70,65第六趟偶數(shù)：21,24,33,33,35,65,70第七趟奇數(shù)：21,24,33,33,35,65,70(無交換)第八趟偶數(shù)：21,24,33,33,35,65,70(無交換)結(jié)束5、①快速排序②冒泡排序③直接插入排序④堆排序算法設(shè)計題1、對給定關(guān)鍵字序號j(1<j<n)，要求在無序記錄A[1..n]中找到關(guān)鍵字從小到大排在第j位上的記錄，寫一個算法利用快速排序的劃分思想實(shí)現(xiàn)上述查找。(要求用最少的時間和最少的空間)。例如：給定無序關(guān)鍵字{7，5，1，6，2，8，9，3}，當(dāng)j=4時，找到的關(guān)鍵字應(yīng)是5。[題目分析]在無序記錄r[n]中，找到第j（1<=j<=n）個記錄，利用快速排序思想，找到第一軸元素的位置i，若i=j則查找結(jié)束。否則，根據(jù)j<i或j>i，在1~i-1或i+1~n之間查找，直到i=j為止。template<classType>voidfindJ(TypeA[],intn,intj){inti=partition(A,1,n);while(i!=j)if(i<j)i=partition(A,i+1,n); //在后半部分繼續(xù)進(jìn)行劃分elsei=partition(A,1,i-1); //在前半部分繼續(xù)進(jìn)行劃分cout<<A[i]<<endl;}2、按由大到小的順序?qū)σ缓衝個元素的數(shù)組A[n]進(jìn)行排序，利用如下改進(jìn)的簡單選擇排序方法：第一次選出最大者存入A[0]，第二次選出最小者存入A[n-1]，第三次選出次大者存入A[1]，第四次選出次小者存入A[n-2]，如此大小交替地選擇，直到排序完畢。voidSimple_Selection(intA[]，intn)∥改進(jìn)的選擇排序，選大和選小交替進(jìn)行，按題意，元素下標(biāo)從0開始{for(i=0;i<n/2;i++){k=i;∥k記最大元素下標(biāo)for(j=i+1;j<=n-1-i;j++)if(A[j]>A[k])k=j;∥選第i+1個最大元素(i從0開始)if(k!=i)A[i]<-->A[k];∥選出第i+1個最大元素ii=k=n-1-i;∥k記最小元素下標(biāo)for(j=n-1-i;j>i;j--)if(A[j]<A[k])k=j;∥選第i+1個最小元素if(k!=ii)A[ii]<-->A[k];∥選出第i+1個最小元素}∥高層for}∥Simple_Selection設(shè)有順序放置的n個桶，每個桶中裝有一粒礫石，每粒礫石的顏色是紅，白，藍(lán)之一。設(shè)計算法重新安排礫石，使得所有紅色礫石在前，所有白色礫石居中，所有藍(lán)色礫石居后，重新安排時對每粒礫石的顏色只能看一次，并且只允許交換操作來調(diào)整礫石的位置。[題目分析]利用快速排序思想解決。由于要求“對每粒礫石的顏色只能看一次”，設(shè)3個指針i，j和k，將r[0..j-1]作為紅色，r[j..k-1]為白色，r[k..n-1]為蘭色。從j=0開始查看，若r[j]為白色，則j=j+1；若r[j]為紅色，則交換r[j]與r[i]，且j=j+1，i=i+1；若r[j]為蘭色，則交換r[j]與r[k];k=k-1。算法進(jìn)行到j(luò)>k為止。為方便處理，將三種礫石的顏色用整數(shù)1、2和3表示。voidQkSort(Typer[]，intn)∥本算法對含有n個元素(礫石)的順序表r排序，使所有紅色礫石在前，白色居中，蘭色在最后{inti=0，j=0，k=n-1，temp;while(j<=k)if(r[j]==1)∥當(dāng)前元素是紅色{temp=r[i];r[i]=r[j];r[j]=temp;i++;j++;}elseif(r[j]==2)j++;∥當(dāng)前元素是白色else∥(r[j]==3當(dāng)前元素是蘭色{temp=r[j];r[j]=r[k];r[k]=temp;k--;}4、請編寫一個算法，在基于單鏈表表示的關(guān)鍵字序列上進(jìn)行簡單選擇排序。voidLinkedListSelectSort(LinkedListhead);∥本算法一趟找出一個關(guān)鍵字最小的結(jié)點(diǎn),其數(shù)據(jù)和當(dāng)前結(jié)點(diǎn)進(jìn)行交換{p=head->next;while(p){q=p->next;r=p;∥設(shè)r是指向關(guān)鍵字最小的結(jié)點(diǎn)的指針while(q!=null){if(q->data<r->data)r=q;q=q->next;}if(r!=p)r->data<-->p->data;p=p->next;∥選下一個最小元素}【算法討論】本算法只交換兩個結(jié)點(diǎn)的數(shù)據(jù)，若要交換結(jié)點(diǎn)，則須記下當(dāng)前結(jié)點(diǎn)和最小結(jié)點(diǎn)的前驅(qū)指針5、已知記錄序列a[1..n]中的關(guān)鍵字各不相同，可按如下所述實(shí)現(xiàn)計數(shù)排序：另設(shè)數(shù)組c[1..n]，對每個記錄a[i]，統(tǒng)計序列中關(guān)鍵字比它小的記錄個數(shù)存于c[i]，則c[i]=0的記錄必為關(guān)鍵字最小的記錄，然后依c[i]值的大小對a中記錄進(jìn)行重新排列，編寫算法實(shí)現(xiàn)上述排序方法。voidCountSort(rectyper[],intn){//對r[1..n]進(jìn)行計數(shù)排序 c[1..n]=0;//c數(shù)組初始化，元素值指其在r中的位置。 for(i=1;i<n;i++)//一趟比較選出大小，給數(shù)組c賦值 for(j=i+1;j<=n;j++) if(r[i].key>r[j].key)c[i]++; elsec[j]++; i=1; c[1..n]=c[1..n]+1;//c數(shù)組元素值指其在r中的位置。 while(i<n) {while(c[i]!=i) {j=c[i];c[i]c[j];r[i]r[j];} i=i+1; }6.引自知乎：2022年408真題數(shù)據(jù)結(jié)構(gòu)篇（修訂版）-知乎()/p/565209806方法一：選擇排序思想（1）遍歷A[1..n]，找到最小值交換到A[1]。遍歷A[2..n]，找到最小值交換到A[2]。遍歷A[3..n]，找到最小值交換到A[3]。……遍歷A[10..n]，找到最小值交換到A[10]。此時A[1..10]保存的就是排序好的最小的10個數(shù)。（2）算法分析：時間復(fù)雜度：O(n)，需要遍歷10次數(shù)組?？臻g復(fù)雜度：O(1)，中間過程額外需要常數(shù)個變量。如果這里將10修改為k，則：時間復(fù)雜度：O(nk)，需要遍歷k次數(shù)組。方法二：堆排序思想（1）先用A[1..10]]原地建立大頂堆（注意：這里不能用小頂堆），然后遍歷剩余元素A[11..n]，每個元素A[i]（11≤i≤n）都要和堆頂元素A如果A[i]小于堆頂元素A[1]，那么就刪除堆頂元素，將A[i]放入堆頂，然后將A[1..10]重新調(diào)整為大頂堆。當(dāng)剩余元素（即A[11..n]）全部掃描完畢，堆中保存的就是最小的10個數(shù)。（2）算法分析：時間復(fù)雜度：O(n)，由于堆大小為常量，所以建堆，維護(hù)堆的代價為O(1)，僅需要遍歷一遍數(shù)組，該算法時間復(fù)雜度為O(n)。空間復(fù)雜度：O(1)，該算法原地建堆，使用了常數(shù)個輔助變量，該算法的空間復(fù)雜度為O(1)。如果這里將10修改為k，則：時間復(fù)雜度：O(nlogk)，所以建堆的代價為O(k)，每次維護(hù)堆的代價為O(logk)，僅需要遍歷一遍數(shù)組，總共n個元素，該算法時間復(fù)雜度為O(nlogk)。方法三：快速排序思想【中科院研究生院2003十二(15分)】【武漢理工大學(xué)2002四.3(35/3分)】曾有過相似題。題目已經(jīng)給出重要提示：“平均情況下的比較次數(shù)盡可能少”，明顯指向隨機(jī)化選擇算法。也是本題的最優(yōu)解。經(jīng)過快速排序算法的一次劃分（partition），凡關(guān)鍵字小于軸的均移動至樞軸之前，凡關(guān)鍵字大于樞軸的均移動至樞軸之后。一趟排序后，樞軸元素保存在了下標(biāo)i處，則i將序列劃分為兩個子序列L和R，