算法分析期末試題集答案6套

1、 ?算法分析與設(shè)計?期末復(fù)習(xí)題一 一、 選擇題 1.應(yīng)用Johnson法那么的流水作業(yè)調(diào)度采用的算法是D A. 貪心算法 B.分支限界法 C.分治法 D.動態(tài)規(guī)劃算法 2. Hanoi塔問題如以下圖所示。現(xiàn)要求將塔座 A上的的所有圓盤移到塔座 B上，并 仍按同樣順序疊置。移動圓盤時遵守 Hanoi塔問題的移動規(guī)那么。由此設(shè)計出解 B. void 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

2、 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,a,b); 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

3、); 2 1： 1 11 Hanoi 塔 hanoi(n-1, C, B, A); 3. 動態(tài)規(guī)劃算法的根本要素為(C) A. 最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì) B. 重疊子問題性質(zhì)與貪心選擇性質(zhì) C. 最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì) D. 預(yù)排序與遞歸調(diào)用 4. 算法分析中，記號O表示(B),記號Q表示(A),記號O表示(D) A. 漸進下界 B. 漸進上界 C. 非緊上界 D. 緊漸進界 E. 非緊下界 5. 以下關(guān)丁漸進記號的性質(zhì)是正確的有：(A) A. f(n)-(g(n),g(n)-(h(n) = f(n)-(h(n) B. f(n) =O(g(n),g(n) = O(h(n) = h(

4、n) =O(f(n) C. O(f(n)+O(g(n) = O(minf(n),g(n) D. f(n) =O(g(n) g(n) =O(f(n) 6. 能采用貪心算法求最優(yōu)解的問題，一般具有的重要性質(zhì)為： (A) A. 最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì) B. 重疊子問題性質(zhì)與貪心選擇性質(zhì) 8. 9. 分支限界法在問題的解空間樹中，按A策略，從根結(jié)點出發(fā)搜索解空間樹 A.廣度優(yōu)先B.活結(jié)點優(yōu)先 C.擴展結(jié)點優(yōu)先 D.深度優(yōu)先 程序塊A是回溯法中遍歷排列樹的算法框架程序。 void backtrack (int t) ( if (tn) output(x); else for (int i=t;in

5、) output(x); else for (int i=0;in) output(x); else for (int i=0;in) output(x); else for (int i=t;i=n;i+) ( swap(xt, xi); if (legal(t) backtrack(t+1); 10. 回溯法的效率不依賴丁以下哪一個因素？ C A. 產(chǎn)生xk的時間； B. 滿足顯約束的xk值的個數(shù)； C. 問題的解空間的形式； D. 計算上界函數(shù)bound的時間； E. 滿足約束函數(shù)和上界函數(shù)約束的所有 xk的個數(shù)。 F. 計算約束函數(shù)constraint的時間； 11. 常見的兩種分支限

6、界法為D A. 廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法； B. 隊列式FIFO分支限界法與堆棧式分支限界法； C. 排歹U樹法與子集樹法； D. 隊列式FIFO分支限界法與優(yōu)先隊列式分支限界法； 12. k帶圖靈機的空間復(fù)雜性Sn是指B A. k帶圖靈機處理所有長度為n的輸入時，在某條帶上所使用過的最大方格數(shù)。 B. k帶圖靈機處理所有長度為n的輸入時，在k條帶上所使用過的方格數(shù)的總 和。 C. k帶圖靈機處理所有長度為n的輸入時，在k條帶上所使用過的平均方格數(shù)。 D. k帶圖靈機處理所有長度為n的輸入時，在某條帶上所使用過的最小方格數(shù)。 13. NP類語言在圖靈機下的定義為(D) A. NP

7、=L|L是一個能在非多項式時間內(nèi)被一臺 NDT晰接受的語言; B. NP=L|L是一個能在多項式時間內(nèi)被一臺 NDT晰接受的語言; C. NP=L|L是一個能在多項式時間內(nèi)被一臺 DT通接受的語言; D. NP=L|L是一個能在多項式時間內(nèi)被一臺 NDT晰接受的語言; 14. 記號。的定義正確的選項是(A)。 A. O(g(n) = f(n) | 存在正常數(shù)c和n0使得對所有n芝n0有：0苴f(n) cg(n) ; B. O(g(n) = f(n) |存在正常數(shù)c和n0使得對所有n芝n有：0M cg(n) 0,存在正數(shù)和 防0使得對所有n芝m 有：0 f(n)0,存在正數(shù)和n0 0使得對所有

8、n芝m有 :0 cg(n) f(n) ; 15. 記號Q的定義正確的選項是(B)。 A. O(g(n) = f(n) | 存在正常數(shù)c和n0使得對所有 nm有：0 f(n) cg(n) ； B. O(g(n) = f(n) |存在正常數(shù)c和n0使得對所有 n芝n。有：0 cg(n) 0,存在正數(shù)和 n。0使得對所有n芝m 有：0 f(n)0,存在正數(shù)和 n00使得對所有n芝n 有：0 -cg(n) f(n) ； 填空題 1.下面程序段的所需要的計算時間為( O ( n ) )。 int MaxSum(int n, int *a, int &besti, int &bestj)

9、( int sum=0; for(int i=1;i=n;i+) int thissum=0; for(int j=i;jsum) sum=thissum; besti=i; bestj=j; return sum; 2. 有11個待安排的活動，它們具有下表所示的開始時間與結(jié)束時間，如果 以貪心算法求解這些活動的最優(yōu)安排即為活動安排問題：在所給的活 動集合中選出最大的相容活動子集合，得到的最大相容活動子集合為活 動(1 , 4, 8, 11) i 1 2 3 4 5 6 7 8 9 10 11 Si 1 3 0 5 3 5 6 8 8 2 12 fi 4 5 6 7 8 9 10 11 12

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

11、9. 用回溯法解批處理作業(yè)調(diào)度問題時，該問題的解空間結(jié)構(gòu)為排列樹結(jié) 構(gòu)。 10. 用回溯法解0/1背包問題時，計算結(jié)點的上界的函數(shù)如下所示，請在空格 中填入適宜的內(nèi)容： Typep Knap: Boundint i /計算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 結(jié)點的上界 / 以物品單位重量價值遞減序裝入物品 while i = n & wi = cleft cleft -= wi; b += pi； i+； / 裝滿背包 if i = n b += pi/wi * cleft ; return b; 11. 用回溯法解布線問題時

12、，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為 nm的方格陣列，擴展每個結(jié)點需 0(1)的時間，L為最短布線路徑的長度，那么 算法共耗時(0(mn)，構(gòu)造相應(yīng)的最短距離需要(0(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.rowhere.col + 1; if (nbr.row = fin

13、ish.row) & (nbr.col = finish.col) break; / 完成布線 Q.Add(nbr); 12. 用回溯法解圖的m著色問題時，使用下面的函數(shù) OK檢查當前擴展結(jié)點的 每一個兒子所相應(yīng)的顏色的可用性，那么需耗時漸進時間上限 O mn。 Bool Color:OK(int k) (/ for(int j=1;j=n;j+) if(akj= =1)&(xj= =xk) return false; return true; 13. 旅行售貨員問題的解空間樹是排列樹 三、 解答題 1. 機器調(diào)度問題。 問題描述：現(xiàn)在有n件任務(wù)和無限多臺的機器，任務(wù)可以在機器

14、上得到 處理。每件任務(wù)的開始時間為Si,完成時間為fi , Si n) / 到達葉結(jié)點 更新最優(yōu)角牟 bestx,bestw;return; r -= wi; if (cw + wi bestw) ( xi = 0; / 搜索右子樹 backtrack (i + 1); r += wi; 5. 用分支限界法解裝載問題時，對算法進行了一些改良，下面的程序段給出了 改良局部；試說明斜線局部完成什么功能，以及這樣做的原因，即采用這樣的方 式， 算法在執(zhí)行上有什么不同。 /檢查左兒子結(jié)點 Type wt = Ew + wi; / 左兒子結(jié)點的重量 if (wt bestw) bestw = wt; /

15、 參加活結(jié)點隊列 if (i bestw & i 0故Ew+rbestw總是成立。也就 是說，此時右子樹測試不起作用。 為了使上述右子樹測試盡早生效，應(yīng)提早更新 bestw。乂知算法最終找到的 最優(yōu)值是所求問題的子集樹中所有可行結(jié)點相應(yīng)重量的最大值。 而結(jié)點所相應(yīng)得 重量僅在搜索進入左子樹是增加，因此，可以在算法每一次進入左子樹時更新 bestw的值。 7. 最長公共子序歹U問題：給定2個序歹U X=x1,x2, -,xm和Y=y1,y2, -,yn , 找出X和Y的最長公共子序列。 由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。 用cij 記錄序列Xi和Yj的最長公

16、共子序列的長度。其中， Xi=x1,x2, -,xi ; Yj=y1,y2, -,yj。當 i=0 或 j=0 時，空序歹U是 Xi 和 Yj 的最長公共子序列。故此時Cij=0 。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立 0 i =0, j = 0 遞歸關(guān)系如下：cij = ci 1 j 1+1 i,j?0;xi=yj maxcij 1,ci 1j i,j 0;xyj J 在程序中，bij 記錄Cij 的值是由哪一個子問題的解得到的。 (1) 請?zhí)顚懗绦蛑械目崭?，以使函?shù) LCSLength完成計算最優(yōu)值的功能。 void LCSLength(int m , int n , char *x , c

17、har *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 =cij-1 ) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 2函數(shù)LCS現(xiàn)根據(jù)b的內(nèi)容打印出Xi和Yj的最長公共子序列。請?zhí)?寫程序中的空格，以使函數(shù)LCS完成構(gòu)造最長公共子序列的功能請 將bij 的取值與1中您填寫的取值對應(yīng)，否那么視為錯誤。 void LCS(int i , in

18、t j , char *x , int *b) ( if (i =0 | j=0) return; if ( bij= 1 ) ( LCS( i-1 , j-1 , x, b); cout0 ) ( printf(%dn ,k); f(k-1); f(k-1); 算法分析與設(shè)計?期末復(fù)習(xí)題(二) 一、簡要答復(fù)以下問題 ： 1. 算法重要特性是什么？ 2. 算法分析的目的是什么？ 3. 算法的時間復(fù)雜性與問題的什么因素相關(guān)？ 4. 算法的漸進時間復(fù)雜性的含義？ 5. 最壞情況下的時間復(fù)雜性和平均時間復(fù)雜性有什么不同？ 6. 簡述二分檢索(折半查找)算法的根本過程。 7. 背包問題的目標函數(shù)和貪心

19、算法最優(yōu)化量度相同嗎？ 8. 采用回溯法求解的問題，其解如何表示？有什么規(guī)定？ 9. 回溯法的搜索特點是什么？ 10. n 皇后問題回溯算法的判別函數(shù) place的根本流程是什么？ 11. 為什么用分治法設(shè)計的算法一般有遞歸調(diào)用？ 12. 為什么要分析最壞情況下的算法時間復(fù)雜性？ 13. 簡述漸進時間復(fù)雜性上界的定義。 14. 二分檢索算法最多的比擬次數(shù)？ 15. 快速排序算法最壞情況下需要多少次比擬運算？ 16. 貪心算法的根本思想？ 17. 回溯法的解(X1,X2,xn)的隱約束一般指什么？ 18. 闡述歸并排序的分治思路。 19. 快速排序的根本思想是什么。 20. 什么是直接遞歸和間接

20、遞歸？消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？ 21. 什么是哈密頓環(huán)問題？ 22. 用回溯法求解哈密頓環(huán)，如何定義判定函數(shù)？ 23. 請寫出 prim算法的根本思想。 參考答案：1.確定性、可實現(xiàn)性、輸入、輸出、有窮性 2. 分析算法占用計算機資源的情況，對算法做出比擬和評價，設(shè)計出額更好的算法。 3. 算法的時間復(fù)雜性與問題的規(guī)模相關(guān)，是問題大小 n 的函數(shù)。 4. 當問題的規(guī)模 n 趨向無窮大時，影響算法效率的重要因素是 T(n)的數(shù)量級，而其他 因素僅是使時間復(fù)雜度相差常數(shù)倍， 因此可以用 T(n)的數(shù)量級(階)評價算法。時間復(fù)雜 度 T(n)的數(shù)量級(階)稱為漸進時間復(fù)雜性。 5. 最壞情況

21、下的時間復(fù)雜性和平均時間復(fù)雜性考察的是 n 固定時，不同輸入實例下的 算法所耗時間。最壞情況下的時間復(fù)雜性取的輸入實例中最大的時間復(fù)雜度： W(n) = max T(n , I) , I Dn 平均時間復(fù)雜性是所有輸入實例的處理時間與各自概率的乘積和： A(n) = E P(I)T(n , I) I Dn 6. 設(shè)輸入是一個按非降次序排列的元素表 Ai : j和 x,選取 A(i+j)/2 與 x比擬， 如果 A(i+j)/2=x ，那么返回(i+j)/2 ，如果 A(i+j)/2x ，貝 U Ai : (i+j)/2-1 找 x, 否那么在A (i+j)/2+1 : j找 x。上述過程被反復(fù)

22、遞歸調(diào)用。 回溯法的搜索特點是什么 7. 不相同。目標函數(shù)：獲得最大利潤。最優(yōu)量度：最大利潤 /重量比。 8. 問題的解可以表示為 . n 元組：(XI,X2, xn), xi Si, Si為有窮集合，xi 8, (XI ,x 2, . xn)具備完備性，即(XI,X 2, . xn)是合理的，那么(乂1飛2, . xi ) (i No, 有 T(n)f(n)，這種關(guān)系記作 T(n)=O(f(n)。 14 .二分檢索算法的最多的比擬次數(shù)為 log n 。 15.最壞情況下快速排序退化成冒泡排序，需要比擬 n2次。 16. 是一種依據(jù)最優(yōu)化量度依次選擇輸入的分級處理方法。 根本思路是：首先根據(jù)題

23、意， 選取一種 量度標準；然后按這種量度標準對這 n 個輸入排序，依次選擇輸入量參加局部解中。 如果當前這個輸入量的參加，不滿足約束條件，那么不把此輸入加到這局部解中。 17. 回溯法的解(XI,X 2,xn)的隱約束一般指個元素之間應(yīng)滿足的某種關(guān)系。 18. 講數(shù)組一分為二，分別對每個集合單獨排序， 然后將已排序的兩個序列歸并成一個 含 n 個元素的分好類的序列。如果分割后子問題還很大，那么繼續(xù)分治，直到一個元素。 19. 快速排序的根本思想是在待排序的 N 個記錄中任意取一個記錄，把該記錄放在最終 位置后，數(shù)據(jù)序列被此記錄分成兩局部。 所有關(guān)鍵字比該記錄關(guān)鍵字小的放在前一局部， 所 有比它

24、大的放置在后一局部， 并把該記錄排在這兩局部的中間， 這個過程稱作一次快速排序。 之后重復(fù)上述過程，直到每一局部內(nèi)只有一個記錄為止。 20. 在定義一個過程或者函數(shù)的時候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成分，既調(diào)用它自 己本身，這稱為直接遞歸。如果過程或者函數(shù) P調(diào)用過程或者函數(shù) Q, Q 又調(diào)用 P,這個稱 為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)。 21. 哈密頓環(huán)是指一條沿著圖 G的 N 條邊環(huán)行的路徑，它的訪問每個節(jié)點一次并且返回 它的開始位置。 22. 當前選擇的節(jié)點 Xk是從未到過的節(jié)點 ，即 Xk豐Xi(i=1,2, -,k-1)，且 C(Xk-1, Xk) 乒 8,如果 k=-

25、1，貝 U C(Xk, X1) 乒 8。 23. 思路是：最初生成樹 T為空，依次向內(nèi)參加與樹有最小鄰接邊的 n-1 條邊。處理過 程：首先參加最小代價的一條邊到 T,根據(jù)各節(jié)點到 T的鄰接邊排序，選擇最小邊參加，新 邊參加后，修改由于新邊所改變的鄰接邊排序，再選擇下一條邊參加，直至參加 n-1 條邊。 、復(fù)雜性分析 1、MERGESORT(lowhigh) if lowhigh ; then mid (low , high)/2 ; MERGESORT(low , mid); MERGESORT(mid+1 , high); MERGE(low , mid, high); endif end

26、 MERGESORT 答：1、遞歸方程 T(n)= a 2T(n/2) cn T(n) =2(2T(n/4) cn/2) cn = 4T(n/4) 2cn = 2kT(1) kcn =an cnlog n 設(shè) n=2k 解遞歸方程： 2、 procedure S1(P , W M X, n) i 。1; a。0 while i M then return endif a j a+i i 。i+1 ; repeat end 解：i。1 ;s。0 時間為：O(1) while i v repeat loop p。p-1 until A(p) v repeat if ip then call INT

27、ERCHANGE(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 n2 then return(1) else return(F2(2,n,1,1) endif end F1 procedure F2(i,n,x,y) if i n then call F2(i+1,n,y,x+y) endif return(y) end F2 解：F2 (2, n,1,1 )的時間復(fù)雜度為： T(n)=O(n-2); 因為 i 1 時 F1(n

28、)的時間復(fù)雜度與 F2(2,n,1,1)的時間復(fù)雜度相同即為為 0(n) 5. procedure MAX(A,n,j) xmax A(1);j 1 for i 2 to n do if A(i)xmax then xmax repeat end MAX 解：xma 曰 A(1);j 1 for i 2 to n do 所以總時間為： T(n)=O(1)+ (n-1)O(1)= O(n) 6. procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low 1;high n while low high do mid |_(low+high)/

29、2 _| case :xA(mid):low mid+1 :else:j mid; return endcase repeat j 0 end BINSRCH 解：log 2n+1 三、算法理解 1、寫出多段圖最短路經(jīng)動態(tài)規(guī)劃算法求解以下實例的過程，并求出最優(yōu)值。 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)=1 C(5,8)=4 , C(6,8)=5 , C(7,8)=6 A(i); j i;endif 時間為：O(1) 循環(huán)最多 n-1 次 解：Cos

30、t(4,8)=0 Cost(3,7)= C(7,8)+0=6 , D5=8 Cost(3,6)= C(6 , 8)+0=5, D6=8 Cost(3,5)= C(5 , 8)+0=4 D7=8 Cost(2,4)= min(C(4 , 6)+ Cost(3,6), C(4 , 5)+ Cost(3,5) =min(1+ 5, 2+4=6 D4=6 Cost(2,3)= min(C(3 , 6)+ Cost(3,6) =min(4+5=9 D3=5 Cost(2,2)= min(C(2 , 6)+ Cost(3,6), C(2 , 7)+ Cost(3,7) =min(8+5, 4+6=10 D

31、2=7 Cost(1,1)= min(C(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4) =min(3+10, 5+9,2+6= 8 D1=4 1 r 4 6 8 2、 寫出 maxmin 算法對以下實例中找最大數(shù)和最小數(shù)的過程。 數(shù)組 A=(48,12,61,3,5,19,32,7) 解：寫出 maxmin算法對以下實例中找最大數(shù)和最小數(shù)的過程。 數(shù)組 A=() 1、 48,12,61,3, 5,19,32,7 2、 48,12 61,3 5,19 32,7 3、 48 61, 12 3 19 32, 5 7 4、 61 32 3

32、5 5、 61 3 3、 快速排序算法對以下實例排序， 算法執(zhí)行過程中，寫出數(shù)組 A 第一次被分割的過程。 A=(65,70,75,80,85,55,50,2) 解：第一個分割元素為 65 (1) (2) (3) (4) (5) (6)(8) i p 65 70 75 80 85 55 50 2 2 8 65 2 75 80_ 85 55 50 70 3 7 65 2 50 80 85 55 75 70 4 6 65 2 50 55 85 80 75 70 4 6 55 70 75 80 85 65 50 2 4、 歸并排序算法對以下實例排序，寫出算法執(zhí)行過程。 A=(48,12,61,3,5

33、,19,32,7) 解：48,12,61,3 5,19,32,7 48,12 61,3 5,19 32,7 12,48 3,61 5,19 7,32 3, 12, 48, 61 5, 7, 19 , 32 3,5, 7,12 , 19, 32, 48,61 5、 寫出圖著色問題的回溯算法的判斷 Xk是否合理的過程。 解：i 0 while i P(i+1)/W(i+1)的順序。 CU 25,X 0 W1 CU: x1 1; CU CU-W1=13; W2CU: x3 CU/ W3=3/8; 實例的解為：(1 , 1, 3/8 , 0) 11、有一個有序表為1, 3, 9, 12, 32, 41

34、, 45, 62, 75, 77, 82, 95, 100,當使用 二分查找值為 82 的結(jié)點時，經(jīng)過多少次比擬后查找成功并給出過程。 解：有一個有序表為1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100,當使用二分 查找值為 82 的結(jié)點時，經(jīng)過多少次比擬后查找成功并給出過程。 一共要要執(zhí)行四次才能找到值為 82 的數(shù)。 12、使用 prim算法構(gòu)造出如以下圖 G的一棵最小生成樹。 dist(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)

35、=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6 解：使用普里姆算法構(gòu)造出如以下圖 G的一棵最小生成樹。分成兩個子問題 分成四個子問題 分成八個子問題 返回上一層 返回上一層 排序結(jié)束，返回主函數(shù) 13、有如下函數(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) 解：有如下函數(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) dist(1,2)=6;dist(2,5

36、)=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 后，k 的值是多少并寫出詳細過程。 后，k 的值是多少并寫出詳細過程。 K的值是 5 14、McCathy函數(shù)定義如下： 當 x100 時 m(x)=x-10; 當 x100 時 m(x)=x-10; 當 x100) return(x-100); else y=m(x+11); return (m(y); 15、設(shè)計一個算法在一個向量 A 中找出最大數(shù)和最小數(shù)的元素。 解：設(shè)計一個算法在一個向量

37、 A 中找出最大數(shù)和最小數(shù)的元素。 Void maxmin(A,n) Vector A; int n; int max,min,i; max=A1;min=A1; for(i=2;imax)max=Ai; else if(Ai t2 tn排序 Sj - Sj+1; Pj,Sj J i Repeat 2. 設(shè)有 n 種面值為： d1d2 . dn 的錢幣，需要找零錢 M,如何選擇錢幣 dk,的數(shù)目 X,滿足 d1X X +dnX X=M ,使得 X +X 最小 請選擇貪心策略，并設(shè)計貪心算法。 解：貪心原那么：每次選擇最大面值硬幣。 Cl M;i 1;X 0 / X 為解向量 While CU

38、豐 0 do Xi CU div di / Xi 為第 i 中硬幣數(shù) Cl CU-di*Xi i i+1; repeat 3. 有 n 個物品， n=7,利潤為 P=(10,5,15,7,6,18,3) ，重量 W=(2,3,5,7,1,4,1) , 背包容積 M=15,物品只能選擇全部裝入背包或不裝入背包，設(shè)計貪心算法，并討論是否可獲 最優(yōu)解。 解：定義結(jié)構(gòu)體數(shù)組 G,將物品編號、利潤、重量作為一個結(jié)構(gòu)體：例如 Gk=1,10,2 求最優(yōu)解，按利潤/重量的遞減序，有 5,6,1, 6 1,10,2, 56,18,4, 9/2 3,15,5, 3 7,3,1, 32,5,3 ,5/3 4,7,

39、7, 1 算法 procedure KNAPSACK(P , W M X n) /P(1 : n)和 W(1; n)分別含有按 P(i)/W(i) P(i+1)/W(i+1) 排序的 n 件物品的效益值 和重量。M 是背包的容量大小，而 x(1 : n)是解向量/ real P(1 : n) , W(1： n), X(1 : n), M cu; integer i , n ； X - 0 /將解向量初始化為零/ cu M /cu 是背包剩余容量/ for i 1 to n do if W(i)cu then exit endif X(i) 1 cu cu-W(i) repeat 2) S1:m

40、清零 j 0 3) for i 1 to n do j j mod m +1 / / / 從第一個處理機開始安排 安排 n 個作業(yè) 選下一個處理機 end GREEDY-KNAPSACK 根據(jù)算法得出的解： X= (1,1,1,1,1,0,0 )獲利潤 52,而解 (1,1,1,1,0, 1,0 )可獲利潤 54 因此貪心法不一定獲得最優(yōu)解。 4. 設(shè)計只求一個哈密頓環(huán)的回溯算法。 解：Hamiltonian(n) (k。1; xk 。0; While k0 do xk 。xk+1; while B(k)=false and xk n do xk 。xk+1; repeat If xk 0 d

41、o /對所有的行執(zhí)行以下語句 / 1) ( X(k) j X(k)+1 / 移到下一列 / While X(k) n and not PLACE(k) do 2) X(k) 。X(k)十 l if X(k) n then if k=n / then (print (X) , a。a+1 /找到一個解計數(shù)器 a 加 1/ if a=n/2 then return / 找到 n/2個解算法結(jié)束 3) else ( k。k+1; X(k)。0; 4) else kJ k-1 / 回溯 / end NQUEENS 武漢工業(yè)學(xué)院工商學(xué)院 2021 T2021學(xué)年第1學(xué)期 算法分析考試試卷(A卷) 課程名

42、稱 算法分析 編號03080121 題號 一 一 三 四 五 六 七 八 總分 得分 評閱人 注：1、考生必須填寫班級、姓名、學(xué)號； 2、試題紙共 J 頁。 1、對 丁下歹 0 各組函數(shù) f(n)和 g(n),確定 f(n)=O(g(n)或 f (n) = “(g(n)或 f (n) =8(g(n),并簡述理由。(12分) (1) f(n) =log n2; g(n) =logn 5; (2) f(n) =2n;g(n) =100n2; f (n) =2n; g(n) =3n; 解：簡答如下： (1) log n2 =(log n+5), 2n =Q(100n2), (3) 2n =o(3n)

43、 2、試用分治法實現(xiàn)有重復(fù)元素的排列問題： 設(shè)R=r1,2,.,rn)是要進行排列的n 個元素，其中元素r1,r2,.,rn可能相同，試計算R的所有不同排列。(13分) 解：解答如下： Template void Perm(Type list,int k,int m) if(k= =m) for(int i=0;i=m;i+) coutlisti; . .(4 分) coutendl; else for(int i=k;i=m;i+) if(ok(list,k,i) swap(listk,listi); Perm(list,k+1,m); swap(listk,listi); . .(8 分)

44、 ; 其中 ok 用于判別重復(fù)元素。 Template int ok(Type list,int k,int i) if(ik) for(int t=k;tI;t+) if(listt= =listi) return 0; return 1; . .(13 分) 3、 試用分治法對一個有序表實現(xiàn)二分搜索算法。 (12分) 解：解答如下： Template int BinarySearch(Type a,const Type& x,int n) /假定藪組a已按非遞減有序排列，本算法找到 x后返回其在數(shù)組a口中 的位置，否那么返回-1 int left=0,right=n-1; while(leftamiddle) left=middle+1; . .(8 分) else right=middle-1; return -1; . .(12 分) 4、 試用動態(tài)規(guī)劃算法實現(xiàn)0-1閉包問題。(15分) 解：解答如下： Template void Knapsack(Type v,int w,int c,int n,Type *m) Int jMax=min(wn-1,c); for(int j=0;j=jMax;j+) mnj=0; for