5.《算法設計與分析》試題庫

1、.算法分析與設計>試題庫(一)一、 選擇題 1.應用Johnson法則的流水作業(yè)調度采用的算法是D）A. 貪心算法 B. 分支限界法 C.分治法 D. 動態(tài)規(guī)劃算法2.Hanoi塔問題如下圖所示。現(xiàn)要求將塔座A上的的所有圓盤移到塔座B上，并仍按同樣順序疊置。移動圓盤時遵守Hanoi塔問題的移動規(guī)則。由此設計出解Hanoi塔問題的遞歸算法正確的為：（B）A. void hanoi(int n, int A, int C, int B) if (n > 0) hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); Hanoi塔B. vo

2、id hanoi(int n, int A, int B, int C) if (n > 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); C. void hanoi(int n, int C, int B, int A) if (n > 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); D. void hanoi(int n, int C, int A, int B) if (n > 0) hanoi(n-1, A, C, B); move(n

3、,a,b); hanoi(n-1, C, B, A); 3. 動態(tài)規(guī)劃算法的基本要素為C）A. 最優(yōu)子結構性質與貪心選擇性質B重疊子問題性質與貪心選擇性質C最優(yōu)子結構性質與重疊子問題性質D. 預排序與遞歸調用4. 算法分析中，記號O表示B）， 記號表示A）， 記號表示D）。A.漸進下界B.漸進上界C.非緊上界D.緊漸進界E.非緊下界 5. 以下關于漸進記號的性質是正確的有：（A）A.B. C. O(f(n)+O(g(n) = O(minf(n),g(n) D. 6. 能采用貪心算法求最優(yōu)解的問題，一般具有的重要性質為：（A）A. 最優(yōu)子結構性質與貪心選擇性質B重疊子問題性質與貪心選擇性質C最優(yōu)

4、子結構性質與重疊子問題性質D. 預排序與遞歸調用7. 回溯法在問題的解空間樹中，按D戰(zhàn)略，從根結點出發(fā)搜索解空間樹。A.廣度優(yōu)先 B. 活結點優(yōu)先 C.擴展結點優(yōu)先 D. 深度優(yōu)先8. 分支限界法在問題的解空間樹中，按A戰(zhàn)略，從根結點出發(fā)搜索解空間樹。A 廣度優(yōu)先 B. 活結點優(yōu)先 C.擴展結點優(yōu)先 D. 深度優(yōu)先9. 程序塊A是回溯法中遍歷排列樹的算法框架程序。void backtrack (int t) if (t>n) output(x); else for (int i=t;i<=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1)

5、; swap(xt, xi); A.void backtrack (int t) if (t>n) output(x); else for (int i=0;i<=1;i+) xt=i; if (legal(t) backtrack(t+1); B. void backtrack (int t) if (t>n) output(x); else for (int i=0;i<=1;i+) xt=i; if (legal(t) backtrack(t-1); C.D.void backtrack (int t) if (t>n) output(x); else fo

6、r (int i=t;i<=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); 10. 回溯法的效率不依賴于以下哪一個因素？（C ）A. 產生xk的時間；B. 滿足顯約束的xk值的個數(shù)；C. 問題的解空間的形式； D. 計算上界函數(shù)bound的時間；11. 常見的兩種分支限界法為D）A. 廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B. 隊列式FIFO分支限界法與堆棧式分支限界法；C. 排列樹法與子集樹法；D. 隊列式FIFO分支限界法與優(yōu)先隊列式分支限界法；12. k帶圖靈機的空間復雜性S(n)是指B）A. k帶圖靈機處理所有長度為n的輸入時，

7、在某條帶上所使用過的最大方格數(shù)。B. k帶圖靈機處理所有長度為n的輸入時，在k條帶上所使用過的方格數(shù)的總和。C. k帶圖靈機處理所有長度為n的輸入時，在k條帶上所使用過的平均方格數(shù)。D. k帶圖靈機處理所有長度為n的輸入時，在某條帶上所使用過的最小方格數(shù)。13. NP類語言在圖靈機下的定義為D）A. NP=L|L是一個能在非多項式時間內被一臺NDTM所接受的語言；B. NP=L|L是一個能在多項式時間內被一臺NDTM所接受的語言；C. NP=L|L是一個能在多項式時間內被一臺DTM所接受的語言；D. NP=L|L是一個能在多項式時間內被一臺NDTM所接受的語言；14. 記號O的定義正確的是A）

8、。A. O(g(n) = f(n) | 存在正常數(shù)c和n0使得對所有nn0有：0 f(n) cg(n) ；B. O(g(n) = f(n) | 存在正常數(shù)c和n0使得對所有nn0有：0 cg(n) f(n) ；C. O(g(n) = f(n) | 對于任何正常數(shù)c>0，存在正數(shù)和n0 >0使得對所有nn0有：0 f(n)<cg(n) ；D. O(g(n) = f(n) | 對于任何正常數(shù)c>0，存在正數(shù)和n0 >0使得對所有nn0有：0 cg(n) < f(n) ；15. 記號的定義正確的是B）。A. O(g(n) = f(n) | 存在正常數(shù)c和n0使得對

9、所有nn0有：0 f(n) cg(n) ；B. O(g(n) = f(n) | 存在正常數(shù)c和n0使得對所有nn0有：0 cg(n) f(n) ；C. (g(n) = f(n) | 對于任何正常數(shù)c>0，存在正數(shù)和n0 >0使得對所有nn0有：0 f(n)<cg(n) ；D. (g(n) = f(n) | 對于任何正常數(shù)c>0，存在正數(shù)和n0 >0使得對所有nn0有：0 cg(n) < f(n) ；二、 填空題1. 下面程序段的所需要的計算時間為（ ）。int MaxSum(int n, int *a, int &besti, int &be

10、stj)int sum=0;for(int i=1;i<=n;i+) int thissum=0;for(int j=i;j<=n;j+) thissum+=aj;if(thissum>sum)sum=thissum;besti=i;bestj=j;return sum;2. 有11個待安排的活動，它們具有下表所示的開始時間與結束時間，如果以貪心算法求解這些活動的最優(yōu)安排即為活動安排問題：在所給的活動集合中選出最大的相容活動子集合），得到的最大相容活動子集合為活動（ 1，4，8，11 ）。1413121110987654fi122886535031Si111098765432

11、1i3. 所謂貪心選擇性質是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到）。4. 所謂最優(yōu)子結構性質是指問題的最優(yōu)解包含了其子問題的最優(yōu)解）。5. 回溯法是回溯法是指具有限界函數(shù)的深度優(yōu)先生成法）。6. 用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹 中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n)）。7. 回溯法的算法框架按照問題的解空間一般分為子集樹算法框架與排列樹算法框架。8. 用回溯法解0/1背包問題時，該問題的解空間結構為子集樹構造。9.用回溯

12、法解批處理作業(yè)調度問題時，該問題的解空間結構為排列樹構造。10.用回溯法解0/1背包問題時，計算結點的上界的函數(shù)如下所示，請在空格中填入合適的內容：Typep Knap<Typew, Typep>:Bound(int i)/ 計算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 結點的上界 / 以物品單位重量價值遞減序裝入物品 while (i <= n && wi <= cleft) cleft -= wi; b += pi; i+; / 裝滿背包 if (i <= n) （b += pi/wi *

13、cleft）; return b;11. 用回溯法解布線問題時，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為的方格陣列，擴展每個結點需O(1)的時間，L為最短布線路徑的長度，則算法共耗時 ( O(mn) )，構造相應的最短距離需要O(L)）時間。for (int i = 0; i < NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col; if (gridnbr.rownbr.col = 0) / 該方格未標記 gridnbr.rownbr.col = gridhere.rowh

14、ere.col + 1; if (nbr.row = finish.row) && (nbr.col = finish.col) break; / 完成布線 Q.Add(nbr); 12. 用回溯法解圖的m著色問題時，使用下面的函數(shù)OK檢查當前擴展結點的每一個兒子所相應的顏色的可用性，則需耗時漸進時間上限）（Omn）。Bool Color:OK(int k)/ for(int j=1;j<=n;j+)if(akj= =1)&&(xj= =xk) return false;return true;13. 旅行售貨員問題的解空間樹是排列樹）。三、 解答題1.

15、機器調度問題。問題描述：現(xiàn)在有n件任務和無限多臺的機器，任務可以在機器上得到處理。每件任務的開始時間為si，完成時間為fi，si<fi 。si，fi為處理任務i的時間范圍。兩個任務i，j重疊指兩個任務的時間范圍區(qū)間有重疊，而并非指i，j的起點或終點重合。例如：區(qū)間1，4與區(qū)間2，4重疊，而與4，7不重疊。一個可行的任務分配是指在分配中沒有兩件重疊的任務分配給同一臺機器。因而，在可行的分配中每臺機器在任何時刻最多只處理一個任務。最優(yōu)分配是指使用的機器最少的可行分配方案。問題實例：若任務占用的時間范圍是1，4，2，5，4，5，2，6，4，7，則按時完成所有任務最少需要幾臺機器？（提示：使用貪

16、心算法）畫出工作在對應的機器上的分配情況。2. 已知非齊次遞歸方程： ，其中，b、c是常數(shù)，g(n)是n的某一個函數(shù)。則f(n)的非遞歸表達式為：?，F(xiàn)有Hanoi塔問題的遞歸方程為： ，求h(n)的非遞歸表達式。解：利用給出的關系式，此時有：b=2, c=1, g(n)=1, 從n遞推到1，有：3. 單源最短路徑的求解。問題的描述：給定帶權有向圖如下圖所示G =(V,E)，其中每條邊的權是非負實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。解法：現(xiàn)采用Dijkstra算法計算從源頂點1到其它

17、頂點間最短路徑。請將此過程填入下表中。432110030maxint10-1初始dist5dist4dist3dist2uS迭代4. 請寫出用回溯法解裝載問題的函數(shù)。裝載問題：有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且。裝載問題要求確定是否有一個合理的裝載方案可將這n個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。解：void backtrack (int i) / 搜索第i層結點 if (i > n) / 到達葉結點 更新最優(yōu)解bestx,bestw;return; r -= wi; if (cw + wi <= c) / 搜索左子樹

18、 xi = 1; cw += wi; backtrack(i + 1); cw -= wi; if (cw + r > bestw) xi = 0; / 搜索右子樹 backtrack(i + 1); r += wi; 5. 用分支限界法解裝載問題時，對算法進行了一些改進，下面的程序段給出了改進部分；試說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法在執(zhí)行上有什么不同。/ 檢查左兒子結點 Type wt = Ew + wi; / 左兒子結點的重量 if (wt <= c) / 可行結點 if (wt > bestw) bestw = wt; / 加入活結點隊

19、列 if (i < n) Q.Add(wt);/ 檢查右兒子結點 if (Ew + r > bestw && i < n) Q.Add(Ew); / 可能含最優(yōu)解 Q.Delete(Ew); / 取下一擴展結點 解答：斜線標識的部分完成的功能為：提前更新bestw值；這樣做可以盡早的進行對右子樹的剪枝。具體為：算法Maxloading初始時將bestw設置為0，直到搜索到第一個葉結點時才更新bestw。因此在算法搜索到第一個葉子結點之前，總有bestw=0，r>0 故Ew+r>bestw總是成立。也就是說，此時右子樹測試不起作用。為了使上述右子樹測

20、試盡早生效，應提早更新bestw。又知算法最終找到的最優(yōu)值是所求問題的子集樹中所有可行結點相應重量的最大值。而結點所相應得重量僅在搜索進入左子樹是增加，因而，可以在算法每一次進入左子樹時更新bestw的值。7. 最長公共子序列問題：給定2個序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。 由最長公共子序列問題的最優(yōu)子結構性質建立子問題最優(yōu)值的遞歸關系。用cij記錄序列Xi和Yj的最長公共子序列的長度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時Cij=0。其它情況下，由最優(yōu)子結構性質可建立遞歸

21、關系如下：在程序中，bij記錄Cij的值是由哪一個子問題的解得到的。（1） 請?zhí)顚懗绦蛑械目崭?，以使函?shù)LCSLength完成計算最優(yōu)值的功能。void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i <= m; i+) ci0 = 0; for (i = 1; i <= n; i+) c0i = 0; for (i = 1; i <= m; i+) for (j = 1; j <= n; j+) if (xi=yj) cij=ci-1j-1+1; bij=1;els

22、e if (ci-1j>=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; （2） 函數(shù)LCS實現(xiàn)根據(jù)b的內容打印出Xi和Yj的最長公共子序列。請?zhí)顚懗绦蛑械目崭?，以使函?shù)LCS完成構造最長公共子序列的功能請將bij的取值與1中您填寫的取值對應，否則視為錯誤）。void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); cout<<xi; else if (bij= 2) LCS(i-1，j，x，b); els

23、e LCS(i，j-1，x，b);8.對下面的遞歸算法，寫出調用f(4)的執(zhí)行結果。void f(int k) if( k>0 ) printf("%dn ",k); f(k-1); f(k-1); 算法分析與設計>試題庫(二)一、簡要回答下列問題 ：1. 算法重要特性是什么？ 2. 算法分析的目的是什么？3. 算法的時間復雜性與問題的什么因素相關？4. 算法的漸進時間復雜性的含義？5. 最壞情況下的時間復雜性和平均時間復雜性有什么不同？6. 簡述二分檢索折半查找算法的基本過程。7. 背包問題的目標函數(shù)和貪心算法最優(yōu)化量度相同嗎？8. 采用回溯法求解的問題，其解

24、如何表示？有什么規(guī)定？9. 回溯法的搜索特點是什么？ 10. n皇后問題回溯算法的判別函數(shù)place的基本流程是什么？11. 為什么用分治法設計的算法一般有遞歸調用？12. 為什么要分析最壞情況下的算法時間復雜性？ 13. 簡述漸進時間復雜性上界的定義。14. 二分檢索算法最多的比較次數(shù)？15. 快速排序算法最壞情況下需要多少次比較運算？16. 貪心算法的基本思想？17. 回溯法的解x1,x2,xn的隱約束一般指什么？18. 闡述歸并排序的分治思路。19. 快速排序的基本思想是什么。 20. 什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數(shù)據(jù)結構？21. 什么是哈密頓環(huán)問題？22. 用回溯法

25、求解哈密頓環(huán)，如何定義判定函數(shù)？23. 請寫出prim算法的基本思想。參考答案：1. 確定性、可實現(xiàn)性、輸入、輸出、有窮性2. 分析算法占用計算機資源的情況，對算法做出比較和評價，設計出額更好的算法。3. 算法的時間復雜性與問題的規(guī)模相關，是問題大小n的函數(shù)。4當問題的規(guī)模n趨向無窮大時，影響算法效率的重要因素是T(n)的數(shù)量級，而其他因素僅是使時間復雜度相差常數(shù)倍，因此可以用T(n)的數(shù)量級(階)評價算法。時間復雜度T(n)的數(shù)量級(階)稱為漸進時間復雜性。5. 最壞情況下的時間復雜性和平均時間復雜性考察的是n固定時，不同輸入實例下的算法所耗時間。最壞情況下的時間復雜性取的輸入實例中最大的時

26、間復雜度：W(n) = max T(n，I) , IDn平均時間復雜性是所有輸入實例的處理時間與各自概率的乘積和：A(n) =P(I)T(n，I) IDn6. 設輸入是一個按非降次序排列的元素表Ai：j 和x，選取A(i+j)/2與x比較，如果A(i+j)/2=x，則返回(i+j)/2，如果A(i+j)/2<x，則Ai：(i+j)/2-1找x，否則在A (i+j)/2+1：j 找x。上述過程被反復遞歸調用?；厮莘ǖ乃阉魈攸c是什么7. 不相同。目標函數(shù)：獲得最大利潤。最優(yōu)量度：最大利潤/重量比。8. 問題的解可以表示為n元組：（x1,x2,xn），xiSi, Si為有窮集合，xiSi, （

27、x1,x2,xn具備完備性，即x1,x2,xn是合理的，那么x1,x2,xi）(i<n)一定合理。9. 在解空間樹上跳躍式地深度優(yōu)先搜索，即用判定函數(shù)考察xk的取值，如果xk是合理的就搜索xk為根節(jié)點的子樹，如果xk取完了所有的值，便回溯到xk-1。10. 將第K行的皇后分別與前k-1行的皇后比較，看是否與它們相容，如果不相容就返回false，測試完畢則返回true。11 . 子問題的規(guī)模還很大時，必須繼續(xù)使用分治法，反復分治，必然要用到遞歸。12 最壞情況下的時間復雜性決定算法的優(yōu)劣，并且最壞情況下的時間復雜性較平均時間復雜性游可操作性。 13 .T(n)是某算法的時間復雜性函數(shù)，f(

28、n)是一簡單函數(shù)，存在正整數(shù)No和C，nNo，有T(n)<f(n)，這種關系記作T(n)=O(f(n)。14 .二分檢索算法的最多的比較次數(shù)為 log n 。15.最壞情況下快速排序退化成冒泡排序，需要比較n2次。16. 是一種依據(jù)最優(yōu)化量度依次選擇輸入的分級處理方法?；舅悸肥牵菏紫雀鶕?jù)題意，選取一種量度標準；然后按這種量度標準對這n個輸入排序，依次選擇輸入量加入部分解中。如果當前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。17回溯法的解x1,x2,xn的隱約束一般指個元素之間應滿足的某種關系。 18. 講數(shù)組一分為二，分別對每個集合單獨排序，然后將已排序的兩個序列歸

29、并成一個含n個元素的分好類的序列。如果分割后子問題還很大，則繼續(xù)分治，直到一個元素。19.快速排序的基本思想是在待排序的N個記錄中任意取一個記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關鍵字比該記錄關鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復上述過程，直到每一部分內只有一個記錄為止。20.在定義一個過程或者函數(shù)的時候又出現(xiàn)了調用本過程或者函數(shù)的成分，既調用它自己本身，這稱為直接遞歸。如果過程或者函數(shù)P調用過程或者函數(shù)Q，Q又調用P，這個稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結構。21.哈密頓環(huán)是指一條

30、沿著圖G的N條邊環(huán)行的路徑，它的訪問每個節(jié)點一次并且返回它的開始位置。22.當前選擇的節(jié)點Xk是從未到過的節(jié)點,即XkXi(i=1,2,k-1)，且C(Xk-1, Xk)，如果k=-1，則C(Xk, X1) 。23. 思路是：最初生成樹T為空，依次向內加入與樹有最小鄰接邊的n-1條邊。處理過程：首先加入最小代價的一條邊到T，根據(jù)各節(jié)點到T的鄰接邊排序，選擇最小邊加入，新邊加入后，修改由于新邊所改變的鄰接邊排序，再選擇下一條邊加入，直至加入n-1條邊。二、復雜性分析1、 MERGESORT(low，high) if low<high； then mid(low，high)/2； MERGE

31、SORT(low，mid)； MERGESORT(mid+1，high)； MERGE(low，mid，high)； endif end MERGESORT答: 1、 遞歸方程 設n=2k解遞歸方程：2、 procedure S1(P，W，M，X，n) i1; a0 while i n do if W(i)>M then return endif aa+i ii+1 ; repeat end 解： i1 ;s0 時間為：O(1) while i n do 循環(huán)n次 循環(huán)體內所用時間為 O(1) 所以 總時間為:T(n)=O(1)+ nO(1)= O(n)3.procedure PARTI

32、TION(m,p) Integer m,p,i;global A(m:p-1) vA(m);im looploop ii+1 until A(i) v repeatloop pp-1 until A(p) v repeat if i<p then call INTERCHANGE(A(i),A(p) else exit endif repeat A(m) A(p);A(p) v End PARTITION解：最多的查找次數(shù)是p-m+1次 4.procedure F1(n) if n<2 then return(1) else return(F2(2,n,1,1) endif end

33、 F1 procedure F2(i,n,x,y) if in then call F2(i+1,n,y,x+y) endif return(y) end F2解：F22，n,1,1的時間復雜度為： T(n)=O(n-2); 因為in時要遞歸調用F2，一共是n-2次 當n1時F1(n)的時間為 O(1)當n>1時F1(n)的時間復雜度與F2(2,n,1,1)的時間復雜度相同即為為 O(n) 5.procedure MAX(A,n,j) xmaxA(1);j1 for i2 to n do if A(i)>xmax then xmaxA(i); ji;endif repeatend

34、MAX 解：xmaxA(1);j1 時間為：O(1) for i2 to n do 循環(huán)最多n-1次 所以 總時間為:T(n)=O(1)+ (n-1)O(1)= O(n)6.procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low1;highn while lowhigh do mid|_(low+high)/2_| case :x<A(mid):highmid-1:x>A(mid):lowmid+1:else:jmid; return endcase repeat j0 end BINSRCH解：log2n+1三、算法理解1

35、、寫出多段圖最短路經動態(tài)規(guī)劃算法求解下列實例的過程，并求出最優(yōu)值。52863174各邊的代價如下：C(1,2)=3， C(1,3)=5 ，C(1,4)=2 C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4， C(4,5)=2，C(4,6)=1C(5,8)=4， C(6,8)=5 ，C(7,8)=6解：Cost(4,8)=0Cost(3,7)= C(7,8)+0=6 ，D5=8Cost(3,6)= C(6，8)+0=5, D6=8Cost(3,5)= C(5，8)+0=4 D7=8Cost(2,4)= minC(4，6)+ Cost(3,6), C(4，5)+ Cos

36、t(3,5) = min1+ 5, 2+4=6 D4=6Cost(2,3)= minC(3，6)+ Cost(3,6) = min4+5=9 D3=5Cost(2,2)= minC(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7) = min8+5, 4+6=10 D2=7Cost(1,1)= minC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4) = min3+10, 5+9,2+6= 8D1=414682、 寫出maxmin算法對下列實例中找最大數(shù)和最小數(shù)的過程。數(shù)組 A=(48,12,61,3,5,19,3

37、2,7) 解：寫出maxmin算法對下列實例中找最大數(shù)和最小數(shù)的過程。數(shù)組 A=() 1、 48,12,61,3, 5,19,32,72、48,12 61,3 5,19 32,73、 4861, 123 1932，574、 6132 355、 61 33、 快速排序算法對下列實例排序，算法執(zhí)行過程中，寫出數(shù)組A第一次被分割的過程。 A=(65,70,75,80,85,55,50,2)解：第一個分割元素為65(1) (2) (3) (4) (5) (6) (7) (8) i p65 70 75 80 85 55 50 2 2 865 2 75 80 85 55 50 70 3 765 2 50

38、80 85 55 75 70 4 665 2 50 55 85 80 75 70 4 655 70 75 80 85 65 50 24、 歸并排序算法對下列實例排序，寫出算法執(zhí)行過程。 A=(48,12,61,3,5,19,32,7) 解： 48,12,61,3 5,19,32,748,12 61,3 5,19 32,712,48 3,61 5,19 7,32 3, 12, 48, 61 5, 7, 19，323,5, 7,12，19，32，48,61 5、 寫出圖著色問題的回溯算法的判斷Xk是否合理的過程。解：i0while i<k do if Gk,i=1 and Xk= Xi th

39、en return false ii+1repeat if i= k then return true6、 對于下圖，寫出圖著色算法得出一種著色方案的過程。2314解：K1X1 1 , 返回 trueX21,返回false; X2X2+1=2, 返回 trueX31 ,返回false; X3X3+1=2, 返回false;X3X3+1=3, 返回 true X41, 返回false; X4X4+1=2, 返回false;X4X4+1=3, 返回 true找到一個解 （1，2，3，3）7、 寫出第7題的狀態(tài)空間樹。解：X1=1X2=2X3=33X4=338、寫出歸并排序算法對下列實例排序的過程。

40、(6,2,9,3,5,1,8,7)解：調用第一層次 6,2,9,3 5,1,8,7 分成兩個子問題 調用第二層次 6,2 9,3 5,1 8,7 分成四個子問題 調用第三層次 6 2 9 3 5 1 8 7 分成八個子問題 調用第四層次 只有一個元素返回上一層第三層歸并 2 ,6 3, 9 1,5 7,8 返回上一層第二層歸并 2 ,3,6, 9 1,5,7,8 返回上一層第一層歸并 1, 2 ,3, 5 ,6, 7, 8,9 排序結束，返回主函數(shù)9、寫出用背包問題貪心算法解決下列實例的過程。 P=(18,12,4,1) W=(12,10,8,3) M=25解: 實例符合P(i)/W(i)P(

41、i+1)/W(i+1)的順序。 CU25,X0 W1< CU: x11; CUCU-W1=13; W2< CU: x21; CUCU-W2=3;W3>CU: x3CU/ W3=3/8;實例的解為：（1，1，3/8，0）11、有一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當使用二分查找值為82的結點時，經過多少次比較后查找成功并給出過程。解：有一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當使用二分查找值為82的結點時，經過多少次比較后查找成功并給出過程。一共要要執(zhí)行四次才能找到值為82的數(shù)。12

42、、使用prim算法構造出如下圖G的一棵最小生成樹。124356dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6解：使用普里姆算法構造出如下圖G的一棵最小生成樹。124356dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)

43、=61316136412645126343313、有如下函數(shù)說明int f(int x,int y) f=x Mod y +1;已知a=10,b=4,c=5 則執(zhí)行k=f(f(a+c,b),f(b,c)后，k的值是多少并寫出詳細過程。解：有如下函數(shù)說明int f(int x,int y) f=x Mod y +1;已知a=10,b=4,c=5 則執(zhí)行k=f(f(a+c,b),f(b,c)后，k的值是多少并寫出詳細過程。 K的值是514、McCathy函數(shù)定義如下：當x>100時 m(x)=x-10;當x<=100時 m(x)=m(m(x+11);編寫一個遞歸函數(shù)計算給定x的m(x)

44、值。解：McCathy函數(shù)定義如下：當x>100時 m(x)=x-10;當x<=100時 m(x)=m(m(x+11);編寫一個遞歸函數(shù)計算給定x的m(x)值。int m(int x)int y; if(x>100) return(x-100);else y=m(x+11); return (m(y); 15、 設計一個算法在一個向量A中找出最大數(shù)和最小數(shù)的元素。解：設計一個算法在一個向量A中找出最大數(shù)和最小數(shù)的元素。Void maxmin(A,n)Vector A;int n;int max,min,i; max=A1;min=A1;for(i=2;i<=n;i+)i

45、f(Ai>max)max=Ai;else if(Ai<min)min=Ai;printf(“max=%d,min=%dn”,max,min); 四、設計算法 1. 設有n項獨立的作業(yè)1,2, n,由m臺相同的機器加工處理。作業(yè)i所需要的處理時間為ti。約定：任何一項作業(yè)可在任何一臺機器上處理，但未完工前不準中斷處理；任何作業(yè)不能拆分更小的子作業(yè)。多機調度問題要求給出一種調度方案，使所給的n個作業(yè)在盡可能短的時間內由m臺機器處理完。設計算法，并討論是否可獲最優(yōu)解。解：對于處理機j，用Sj 表示處理機j已有的作業(yè)數(shù)，用Pj,k表示處理機j的第k個作業(yè)的序號 。1將作業(yè)按照t1t2tn排序2S1:m清零 j0 /從第一個處理機開始安排3) for i1 to n do /安排n個作業(yè) jj mod m +1 /選下一個處理機SjSj+1; Pj,Sji ； Repeat2. 設有n種面值為:d1d2dn的錢幣，需要找零錢M，如何選擇錢幣dk，的數(shù)目Xk，滿足 d1×Xidn×Xn=M ，使得XiXn 最小 請選擇貪心策略，并設計貪心算法。解：貪心原則：每次選擇最大面值硬幣。CUM;i1;X0