《《算法設(shè)計(jì)與分析》考試題目及答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法設(shè)計(jì)與分析》考試題目及答案（25頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 《算法分析與設(shè)計(jì)》期末復(fù)習(xí)題 一、 選擇題 1.應(yīng)用Johnson法則的流水作業(yè)調(diào)度采用的算法是（D） A. 貪心算法 B. 分支限界法 C.分治法 D. 動(dòng)態(tài)規(guī)劃算法 2.Hanoi塔問題如下圖所示?，F(xiàn)要求將塔座A上的的所有圓盤移到塔座B上，并仍按同樣順序疊置。移動(dòng)圓盤時(shí)遵守Hanoi塔問題的移動(dòng)規(guī)則。由此設(shè)計(jì)出解Hanoi塔問題的遞歸算法正確的為：（B） A. void hanoi(int n, int A, int C, int B) { if (n > 0) { hanoi(n-1,A

2、,C, B); move(n,a,b); hanoi(n-1, C, B, A); } } Hanoi塔 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.

3、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);

4、 move(n,a,b); hanoi(n-1, C, B, A); } } 3. 動(dòng)態(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）， 記號表示（A）， 記號表示（D）。 A.漸進(jìn)下界 B.漸進(jìn)上界 C.非緊上界 D.緊漸進(jìn)界 E.非緊下界 5. 以下關(guān)于漸進(jìn)記號的性質(zhì)是正確的有：（A） A. B. C.

5、 O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. 6. 能采用貪心算法求最優(yōu)解的問題，一般具有的重要性質(zhì)為：（A） A. 最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì) B．重疊子問題性質(zhì)與貪心選擇性質(zhì) C．最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì) D. 預(yù)排序與遞歸調(diào)用 7. 回溯法在問題的解空間樹中，按（D）策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。 A． 廣度優(yōu)先 B. 活結(jié)點(diǎn)優(yōu)先 C.擴(kuò)展結(jié)點(diǎn)優(yōu)先 D. 深度優(yōu)先 8. 分支限界法在問題的解空間樹中，按（A）策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。 A． 廣度優(yōu)先 B. 活結(jié)點(diǎn)

6、優(yōu)先 C.擴(kuò)展結(jié)點(diǎn)優(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(x[t], x[i]); if (legal(t)) backtrack(t+1); swap(x[t], x[i]); } } A. void backtrack (int t)

7、 { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=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++) { x[t]=i; if (legal(t)) backtrack

8、(t-1); } } C. D.void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); } } 10. 回溯法的效率不依賴于以下哪一個(gè)因素？（C ） A. 產(chǎn)生x[k]的時(shí)間； B. 滿足顯約束的x[k]值的個(gè)數(shù)； C. 問題的解空間的

9、形式； D. 計(jì)算上界函數(shù)bound的時(shí)間； E. 滿足約束函數(shù)和上界函數(shù)約束的所有x[k]的個(gè)數(shù)。 F. 計(jì)算約束函數(shù)constraint的時(shí)間； 11. 常見的兩種分支限界法為（D） A. 廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法； B. 隊(duì)列式（FIFO）分支限界法與堆棧式分支限界法； C. 排列樹法與子集樹法； D. 隊(duì)列式（FIFO）分支限界法與優(yōu)先隊(duì)列式分支限界法； 12. k帶圖靈機(jī)的空間復(fù)雜性S(n)是指（B） A. k帶圖靈機(jī)處理所有長度為n的輸入時(shí)，在某條帶上所使用過的最大方格數(shù)。 B. k帶圖靈機(jī)處理所有長度為n的輸入時(shí)，在k條帶上所使用

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

11、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)0，存在正數(shù)和n0 >0使得對所有nn0有：0 cg(n) < f(n) }； 15. 記號的定義正確的是（B）。 A. O(g(n)) = {

12、 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. (g(n)) = { f(n) | 對于任何正常數(shù)c>0，存在正數(shù)和n0 >0使得對所有nn0有：0 f(n)0，存在正數(shù)和n0 >0使得對所有nn0有：0 cg(n) < f(n) }； 二、 填空題 1. 下面程序段的所需要的計(jì)算時(shí)間為（ ）。 int MaxSum(

13、int n, int *a, int &besti, int &bestj) { int sum=0; for(int i=1;i<=n;i++){ int thissum=0; for(int j=i;j<=n;j++){ thissum+=a[j]; if(thissum>sum) { sum=thissum; besti=i; bestj=j; } } } return sum; } 2. 有11個(gè)待安排的活動(dòng)，它們具

14、有下表所示的開始時(shí)間與結(jié)束時(shí)間，如果以貪心算法求解這些活動(dòng)的最優(yōu)安排（即為活動(dòng)安排問題：在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合），得到的最大相容活動(dòng)子集合為活動(dòng)（ {1，4，8，11} ）。 14 13 12 11 10 9 8 7 6 5 4 f[i] 12 2 8 8 6 5 3 5 0 3 1 S[i] 11 10 9 8 7 6 5 4 3 2 1 i 3. 所謂貪心選擇性質(zhì)是指（所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到）。 4. 所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指（問題的最優(yōu)解

15、包含了其子問題的最優(yōu)解）。 5. 回溯法是指（具有限界函數(shù)的深度優(yōu)先生成法）。 6. 用回溯法解題的一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。 如果解空間樹 中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長路徑的長度為h(n)，則回溯法所需的計(jì)算空間通常為（O(h(n)) ）。 7. 回溯法的算法框架按照問題的解空間一般分為（子集樹）算法框架與（排列樹）算法框架。 8. 用回溯法解0/1背包問題時(shí)，該問題的解空間結(jié)構(gòu)為（子集樹）結(jié)構(gòu)。 9.用回溯法解批處理作業(yè)調(diào)度問題時(shí)，該問題的解空間結(jié)構(gòu)為（排列樹）結(jié)構(gòu)。 10.用回溯法解0/1背包問題時(shí)

16、，計(jì)算結(jié)點(diǎn)的上界的函數(shù)如下所示，請?jiān)诳崭裰刑钊牒线m的內(nèi)容： Typep Knap::Bound(int i) {// 計(jì)算上界 Typew cleft = c - cw; // 剩余容量 Typep b = cp; // 結(jié)點(diǎn)的上界 // 以物品單位重量價(jià)值遞減序裝入物品 while (i <= n && w[i] <= cleft) { cleft -= w[i]; b += p[i]; i++; } // 裝滿背包 if (i <= n

17、) （b += p[i]/w[i] * cleft）; return b; } 11. 用回溯法解布線問題時(shí)，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為的方格陣列，擴(kuò)展每個(gè)結(jié)點(diǎn)需O(1)的時(shí)間，L為最短布線路徑的長度，則算法共耗時(shí) ( O(mn) )，構(gòu)造相應(yīng)的最短距離需要（O(L)）時(shí)間。 for (int i = 0; i < NumOfNbrs; i++) { nbr.row = here.row + offset[i].row; nbr.col = here.col + of

18、fset[i].col; if (grid[nbr.row][nbr.col] == 0) { // 該方格未標(biāo)記 grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1; if ((nbr.row == finish.row) && (nbr.col == finish.col)) break; // 完成布線 Q.Add(nbr);}

19、 } 12. 用回溯法解圖的m著色問題時(shí)，使用下面的函數(shù)OK檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色的可用性，則需耗時(shí)（漸進(jìn)時(shí)間上限）（O（mn））。 Bool Color::OK(int k) {// for(int j=1;j<=n;j++) if((a[k][j]= =1)&&(x[j]= =x[k])) return false; return true; } 13. 旅行售貨員問題的解空間樹是（排列樹）。 6. 7. 三、 證明題 1. 一個(gè)分治法將規(guī)模為n的問題分

20、成k個(gè)規(guī)模為n／m的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問題分解為k個(gè)子問題以及用merge將k個(gè)子問題的解合并為原問題的解需用f(n)個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計(jì)算時(shí)間，則有： 通過迭代法求得T（n）的顯式表達(dá)式為： 試證明T（n）的顯式表達(dá)式的正確性。 2. 舉反例證明0/1背包問題若使用的算法是按照pi/wi的非遞減次序考慮選擇的物品，即只要正在被考慮的物品裝得進(jìn)就裝入背包，則此方法不一定能得到最優(yōu)解（此題說明0/1背包問題與背包問題的不同）。 證明：舉例如：p={7,4,4},w

21、={3,2,2},c=4時(shí)，由于7/3最大，若按題目要求的方法，只能取第一個(gè)，收益是7。而此實(shí)例的最大的收益應(yīng)該是8，取第2，3 個(gè)。 3. 求證：O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 。 證明：對于任意f1(n) O(f(n)) ，存在正常數(shù)c1和自然數(shù)n1，使得對所有nn1，有f1(n) c1f(n) 。 類似地，對于任意g1(n) O(g(n)) ，存在正常數(shù)c2和自然數(shù)n2，使得對所有nn2，有g(shù)1(n) c2g(n) 。 令c3=max{c1, c2}， n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。 則

22、對所有的 n n3，有 f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n) = c3(f(n) + g(n)) c32 max{f(n),g(n)} = 2c3h(n) = O(max{f(n),g(n)}) . 4. 求證最優(yōu)裝載問題具有貪心選擇性質(zhì)。 （最優(yōu)裝載問題：有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。 設(shè)集裝箱已依其重量從小到大排序，(x1,x2,…,xn)是

23、最優(yōu)裝載問題的一個(gè)最優(yōu)解。又設(shè) 。如果給定的最優(yōu)裝載問題有解，則有。） 證明： 四、 解答題 1. 機(jī)器調(diào)度問題。 問題描述：現(xiàn)在有n件任務(wù)和無限多臺的機(jī)器，任務(wù)可以在機(jī)器上得到處理。每件任務(wù)的開始時(shí)間為si，完成時(shí)間為fi，si

24、可行分配方案。 問題實(shí)例：若任務(wù)占用的時(shí)間范圍是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，則按時(shí)完成所有任務(wù)最少需要幾臺機(jī)器？（提示：使用貪心算法） 畫出工作在對應(yīng)的機(jī)器上的分配情況。 2. 已知非齊次遞歸方程： ，其中，b、c是常數(shù)，g(n)是n的某一個(gè)函數(shù)。則f(n)的非遞歸表達(dá)式為：。 現(xiàn)有Hanoi塔問題的遞歸方程為： ，求h(n)的非遞歸表達(dá)式。 解：利用給出的關(guān)系式，此時(shí)有：b=2, c=1, g(n)=1, 從n遞推到1，有： 3. 單源最短路徑的求解。 問題的描述：給定帶權(quán)有向圖（如下圖所示）G =(V,E)，其中每條邊的權(quán)是非負(fù)

25、實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源。現(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。 解法：現(xiàn)采用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑。請將此過程填入下表中。 4 3 2 1 100 30 maxint 10 - {1} 初始 dist[5] dist[4] dist[3] dist[2] u S 迭代 4. 請寫出用回溯法解裝載問

26、題的函數(shù)。 裝載問題：有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且。裝載問題要求確定是否有一個(gè)合理的裝載方案可將這n個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。 解：void backtrack (int i) {// 搜索第i層結(jié)點(diǎn) if (i > n) // 到達(dá)葉結(jié)點(diǎn) 更新最優(yōu)解bestx,bestw;return; r -= w[i]; if (cw + w[i] <= c) {// 搜索左子樹 x[i] = 1; cw += w

27、[i]; backtrack(i + 1); cw -= w[i]; } if (cw + r > bestw) { x[i] = 0; // 搜索右子樹 backtrack(i + 1); } r += w[i]; } 5. 用分支限界法解裝載問題時(shí)，對算法進(jìn)行了一些改進(jìn)，下面的程序段給出了改進(jìn)部分；試說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法在執(zhí)行上有什么不同。 // 檢查左兒子結(jié)點(diǎn) Type wt =

28、 Ew + w[i]; // 左兒子結(jié)點(diǎn)的重量 if (wt <= c) { // 可行結(jié)點(diǎn) if (wt > bestw) bestw = wt; // 加入活結(jié)點(diǎn)隊(duì)列 if (i < n) Q.Add(wt); } // 檢查右兒子結(jié)點(diǎn) if (Ew + r > bestw && i < n) Q.Add(Ew); // 可能含最優(yōu)解 Q.Delete(Ew); // 取下一擴(kuò)展結(jié)點(diǎn)

29、 解答：斜線標(biāo)識的部分完成的功能為：提前更新bestw值； 這樣做可以盡早的進(jìn)行對右子樹的剪枝。具體為：算法Maxloading初始時(shí)將bestw設(shè)置為0，直到搜索到第一個(gè)葉結(jié)點(diǎn)時(shí)才更新bestw。因此在算法搜索到第一個(gè)葉子結(jié)點(diǎn)之前，總有bestw=0，r>0 故Ew+r>bestw總是成立。也就是說，此時(shí)右子樹測試不起作用。 為了使上述右子樹測試盡早生效，應(yīng)提早更新bestw。又知算法最終找到的最優(yōu)值是所求問題的子集樹中所有可行結(jié)點(diǎn)相應(yīng)重量的最大值。而結(jié)點(diǎn)所相應(yīng)得重量僅在搜索進(jìn)入左子樹是增加，因此，可以在算法每一次進(jìn)入左子樹時(shí)更新bestw的值。 7. 最長公共子序列問題

30、：給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。 由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列Xi和Yj的最長公共子序列的長度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長公共子序列。故此時(shí)C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下： 在程序中，b[i][j]記錄C[i][j]的值是由哪一個(gè)子問題的解得到的。 （1） 請?zhí)顚懗绦蛑械目崭?，以使函?shù)LCSLength完成計(jì)算最優(yōu)值的功能。 voi

31、d LCSLength(int m，int n，char *x，char *y，int **c，int **b) { int i，j; for (i = 1; i <= m; i++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (x[i]==y[j]) { c[i][j

32、]=c[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2;} else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } （2） 函數(shù)LCS實(shí)現(xiàn)根據(jù)b的內(nèi)容打印出Xi和Yj的最長公共子序列。請?zhí)顚懗绦蛑械目崭?，以使函?shù)LCS完成構(gòu)造最長公共子序列的功能（請將b[i][j]的取值與（1）

33、中您填寫的取值對應(yīng)，否則視為錯(cuò)誤）。 void LCS(int i，int j，char *x，int **b) { if (i ==0 || j==0) return; if (b[i][j]== 1) { LCS(i-1，j-1，x，b); cout<

34、遞歸算法，寫出調(diào)用f(4)的執(zhí)行結(jié)果。 void f(int k) { if( k>0 ) { printf("%d\n ",k); f(k-1); f(k-1); } } 一、填空題（20分） 1.一個(gè)算法就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特殊類型問題的一系列運(yùn)算，此外，算法還應(yīng)具有以下五個(gè)重要特性:_________,________,________,__________,__________。 2.算法的復(fù)雜性有_____________和________

35、___之分，衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是______________________。 3.某一問題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征是____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，請給出序列X和Y的一個(gè)最長公共子序列_____________________________。 5.用回溯法解問題時(shí)，應(yīng)明確定義問題的解空間，問題的解空間至少應(yīng)包含___________。 6.動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干____________，先求解___________，然

36、后從這些____________的解得到原問題的解。 7.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為_____________。 8.0-1背包問題的回溯算法所需的計(jì)算時(shí)間為_____________,用動(dòng)態(tài)規(guī)劃算法所需的計(jì)算時(shí)間為____________。 9.動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是___________和___________。 10.二分搜索算法是利用_______________實(shí)現(xiàn)的算法。 二、綜合題（50分） 1.寫出設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟。 2.流水作業(yè)調(diào)度問題的johnson算法的思想。 3.若n=4，在機(jī)器M1和M2上加工作業(yè)i所需的時(shí)間分別為ai和bi

37、，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4個(gè)作業(yè)的最優(yōu)調(diào)度方案，并計(jì)算最優(yōu)值。 4.使用回溯法解0/1背包問題：n=3，C=9，V={6,10,3}，W={3,4,4},其解空間有長度為3的0-1向量組成，要求用一棵完全二叉樹表示其解空間（從根出發(fā)，左1右0），并畫出其解空間樹，計(jì)算其最優(yōu)值及最優(yōu)解。 5.設(shè)S=｛X1，X2，，Xn｝是嚴(yán)格遞增的有序集，利用二叉樹的結(jié)點(diǎn)來存儲S中的元素，在表示S的二叉搜索樹中搜索一個(gè)元素X，返回的結(jié)果有兩種情形，（1）在二叉搜索樹的內(nèi)結(jié)點(diǎn)中找到X=Xi，其概率為bi。（2）在二叉搜索樹的葉結(jié)

38、點(diǎn)中確定X∈（Xi，Xi+1），其概率為ai。在表示S的二叉搜索樹T中，設(shè)存儲元素Xi的結(jié)點(diǎn)深度為Ci；葉結(jié)點(diǎn)（Xi，Xi+1）的結(jié)點(diǎn)深度為di，則二叉搜索樹T的平均路長p為多少？假設(shè)二叉搜索樹T[i][j]=｛Xi，Xi+1，，Xj｝最優(yōu)值為m[i][j]，W[i][j]= ai-1+bi++bj+aj，則m[i][j](1<=i<=j<=n)遞歸關(guān)系表達(dá)式為什么？ 6.描述0-1背包問題。 三、簡答題（30分） 1.流水作業(yè)調(diào)度中，已知有n個(gè)作業(yè)，機(jī)器M1和M2上加工作業(yè)i所需的時(shí)間分別為ai和bi，請寫出流水作業(yè)調(diào)度問題的johnson法則中對ai和bi的排序算法。（函數(shù)名可寫為

39、sort(s,n)） 2.最優(yōu)二叉搜索樹問題的動(dòng)態(tài)規(guī)劃算法（設(shè)函數(shù)名binarysearchtree)） 答案： 一、填空 1．確定性 有窮性 可行性 0個(gè)或多個(gè)輸入 一個(gè)或多個(gè)輸出 2.時(shí)間復(fù)雜性 空間復(fù)雜性 時(shí)間復(fù)雜度高低 3. 該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 4.{BABCD}或{CABCD}或{CADCD｝ 5.一個(gè)（最優(yōu)）解 6.子問題 子問題 子問題 7.回溯法 8. o(n*2n) o(min{nc,2n}) 9.最優(yōu)子結(jié)構(gòu) 重疊子問題 10.動(dòng)態(tài)規(guī)劃法 二、綜合題 1.①問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；②構(gòu)造最優(yōu)值的遞歸

40、關(guān)系表達(dá)式； ③最優(yōu)值的算法描述；④構(gòu)造最優(yōu)解； 2. ①令N1={i|ai=bi}；②將N1中作業(yè)按ai的非減序排序得到N1’，將N2中作業(yè)按bi的非增序排序得到N2’；③N1’中作業(yè)接N2’中作業(yè)就構(gòu)成了滿足Johnson法則的最優(yōu)調(diào)度。 3.步驟為：N1={1，3}，N2={2，4}； N1’={1，3}， N2’={4，2}； 最優(yōu)值為：38 4.解空間為{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空間樹為： A B C F E D G

41、 K J I H O N M L 1 1 1 0 0 0 0 1 0 1 1 0 1 0 該問題的最優(yōu)值為：16 最優(yōu)解為：（1，1，0） 5.二叉樹T的平均路長P=+ m[i][j]=W[i][j]+min{m[i][k]+m[k+1][j]} (1<=i<=j<=n,m[i][i-1]=0) m[i][j]=0 (i>j) 6.已知一個(gè)背包的容量為C，有n件物品，物品i的重量為Wi，價(jià)值為Vi，求應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大。 三、簡答題 1. void sort(flowjope

42、s[],int n) { int i,k,j,l; for(i=1;i<=n-1;i++)//-----選擇排序 { k=i; while(k<=n&&s[k].tag!=0) k++; if(k>n) break;//-----沒有ai，跳出 else { for(j=k+1;j<=n;j++) if(s[j].tag==0) if(s[k].a>s[j].a) k=j; swap(s[i].index,s[k].index); swap(s[i].tag,s[k].tag); }

43、 } l=i;//-----記下當(dāng)前第一個(gè)bi的下標(biāo) for(i=l;i<=n-1;i++) { k=i; for(j=k+1;j<=n;j++) if(s[k].b

44、**m,int **s,int **w) { int i,j,k,t,l; for(i=1;i<=n+1;i++) { w[i][i-1]=a[i-1]; m[i][i-1]=0; } for(l=0;l<=n-1;l++)//----l是下標(biāo)j-i的差 for(i=1;i<=n-l;i++) { j=i+l; w[i][j]=w[i][j-1]+a[j]+b[j]; m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j]; s[i][j]=i; for(k=i+1;k<=j;k++) { t=m[i][

45、k-1]+m[k+1][j]+w[i][j]; if(t

46、 資源。因而，算法的復(fù)雜性有 和 之分。 5、 f(n)= 62n+n2，f(n)的漸進(jìn)性態(tài)f(n)= O( ) 6、 貪心算法總是做出在當(dāng)前看來 的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的 。 7、 許多可以用貪心算法求解的問題一般具有2個(gè)重要的性質(zhì)： 性質(zhì)和 性質(zhì)。 二、簡答題（本題25分，每小題5分） 1、 簡單描述分治法的基本思想。 2、 簡述動(dòng)態(tài)規(guī)劃方法所運(yùn)用的最優(yōu)化原理。 3、 何謂最優(yōu)子結(jié)構(gòu)性質(zhì)？ 4、 簡單描述回溯法基本思想。 5、 何謂P、NP、

47、NPC問題 三、算法填空（本題20分，每小題5分） 1、n后問題回溯算法 (1)用二維數(shù)組A[N][N]存儲皇后位置,若第i行第j列放有皇后,則A[i][j]為非0值,否則值為0。 (2)分別用一維數(shù)組M[N]、L[2*N-1]、R[2*N-1]表示豎列、左斜線、右斜線是否放有棋子，有則值為1,否則值為0。 for(j=0;j

48、探下一行*/ 4 ； /*去皇后*/ 5 ；; } 2、數(shù)塔問題。有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一起走到底層，要求找出一條路徑，使路徑上的值最大。 for(r=n-2;r>=0;r--) //自底向上遞歸計(jì)算 for(c=0; 1 ;c++) if( t[r+1][c]>t[r+1][c+1]) 2 ； else 3 ； 3、Hanoi算法 Hanoi(n,a,b,c) if （n==1）

49、 1 ； else { 2 ； 3 ； Hanoi(n-1,b, a, c); } 4、Dijkstra算法求單源最短路徑 d[u]:s到u的距離 p[u]:記錄前一節(jié)點(diǎn)信息 Init-single-source(G,s) for each vertex v∈V[G] do { d[v]=∞; 1 } d[s]=0 Relax(u,v,w) if d[v]>d[u]+w(u,v) then { d[v]=d[u]+w[u,v]; 2

50、 } dijkstra(G,w,s) 1. Init-single-source(G,s) 2. S=Φ 3. Q=V[G] 4.while Q<> Φ do u=min(Q) S=S∪{u} for each vertex 3 do 4 四、算法理解題（本題10分） 根據(jù)優(yōu)先隊(duì)列式分支限界法，求下圖中從v1點(diǎn)到v9點(diǎn)的單源最短路徑，請畫出求得最優(yōu)解的解空間樹。要求中間被舍棄的結(jié)點(diǎn)用標(biāo)記，獲得中間解的結(jié)點(diǎn)用單圓圈○框起，最優(yōu)解用雙圓圈

51、◎框起。 五、算法理解題（本題5分） 設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： ①每個(gè)選手必須與其他n-1名選手比賽各一次； ②每個(gè)選手一天至多只能賽一次； ③循環(huán)賽要在最短時(shí)間內(nèi)完成。 （1）如果n=2k，循環(huán)賽最少需要進(jìn)行幾天； （2）當(dāng)n=23=8時(shí)，請畫出循環(huán)賽日程表。 六、算法設(shè)計(jì)題（本題15分） 分別用貪心算法、動(dòng)態(tài)規(guī)劃法、回溯法設(shè)計(jì)0-1背包問題。要求：說明所使用的算法策略；寫出算法實(shí)現(xiàn)的主要步驟；分析算法的時(shí)間。 七、算法設(shè)計(jì)題（本題10分） 通過鍵盤輸入一個(gè)高精度的正整數(shù)n(n的有效位數(shù)≤240)，去掉其中任意s個(gè)數(shù)字后，剩

52、下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對給定的n 和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小。 【樣例輸入】 178543 S=4 【樣例輸出】 13 一、填空題（本題15分，每小題1分） 1．規(guī)則 一系列運(yùn)算 2. 隨機(jī)存取機(jī)RAM(Random Access Machine)；隨機(jī)存取存儲程序機(jī)RASP(Random Access Stored Program Machine)；圖靈機(jī)(Turing Machine) 3. 算法效率 4. 時(shí)間、空間、時(shí)間復(fù)雜度、空間復(fù)雜度 5．2n 6．最好 局部最優(yōu)選擇 7. 貪心

53、選擇 最優(yōu)子結(jié)構(gòu) 二、簡答題（本題25分，每小題5分） 6、 分治法的基本思想是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同；對這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止；將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。 7、 “最優(yōu)化原理”用數(shù)學(xué)化的語言來描述：假設(shè)為了解決某一優(yōu)化問題，需要依次作出n個(gè)決策D1，D2，…，Dn，如若這個(gè)決策序列是最優(yōu)的，對于任何一個(gè)整數(shù)k，1 < k < n，不論前面k個(gè)決策是怎樣的，以后的

54、最優(yōu)決策只取決于由前面決策所確定的當(dāng)前狀態(tài)，即以后的決策Dk+1，Dk+2，…，Dn也是最優(yōu)的。 8、 某個(gè)問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。 9、 回溯法的基本思想是在一棵含有問題全部可能解的狀態(tài)空間樹上進(jìn)行深度優(yōu)先搜索，解為葉子結(jié)點(diǎn)。搜索過程中，每到達(dá)一個(gè)結(jié)點(diǎn)時(shí)，則判斷該結(jié)點(diǎn)為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的解，則放棄對該子樹的搜索，退回到上層父結(jié)點(diǎn)，繼續(xù)下一步深度優(yōu)先搜索過程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài)空間樹，再進(jìn)行搜索，而是在搜索過程，逐步構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造。 10、 P(Polynomial問題)：

55、也即是多項(xiàng)式復(fù)雜程度的問題。 NP就是Non-deterministicPolynomial的問題，也即是多項(xiàng)式復(fù)雜程度的非確定性問題。 NPC(NP Complete)問題，這種問題只有把解域里面的所有可能都窮舉了之后才能得出答案，這樣的問題是NP里面最難的問題，這種問題就是NPC問題。 三、算法填空（本題20分，每小題5分） 1、n后問題回溯算法 (1) !M[j]&&!L[i+j]&&!R[i-j+N] (2) M[j]=L[i+j]=R[i-j+N]=1; (3) try(i+1,M,L,R,A) (4) A[i][j]=0 (5) M[j]=L[i+j]=R

56、[i-j+N]=0 2、數(shù)塔問題。 （1）c<=r (2)t[r][c]+=t[r+1][c] （3）t[r][c]+=t[r+1][c+1] 3、Hanoi算法 （1）move(a,c) （2）Hanoi(n-1, a, c , b) （3）Move(a,c) 4、（1）p[v]=NIL （2）p[v]=u (3) v∈adj[u] （4）Relax(u,v,w) 四、算法理解題（本題10分） 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7

57、 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 五、（1）8天（2分）； （2）當(dāng)n=23=8時(shí)，循環(huán)賽日程表（3分）。 六、算法設(shè)計(jì)題（本題15分） （1）貪心算法 O（nlog（n）） 首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。 具體算法可

58、描述如下： void Knapsack(int n,float M,float v[],float w[],float x[]) {Sort(n,v,w); int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) {if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; } （2）動(dòng)態(tài)規(guī)劃法 O(nc) m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建

59、立計(jì)算m(i，j)的遞歸式如下。 void KnapSack(int v[],int w[],int c,int n,int m[][11]) {int jMax=min(w[n]-1,c); for (j=0;j<=jMax;j++) /*m(n,j)=0 0==w[n]*/ m[n][j]=v[n]; for (i=n-1;i>1;i--) { int jMax=min(w[i]-1,c); for (j=0;j<=jMax;j++)

60、 /*m(i,j)=m(i+1,j) 0==w[n]*/ m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } （3）回溯法 O(2n) cw:當(dāng)前重量 cp:當(dāng)前價(jià)值 bestp：當(dāng)前最優(yōu)值 voidbacktrack

61、(inti) //回溯法 i初值1 {if(i>n) //到達(dá)葉結(jié)點(diǎn) { bestp=cp; return; } if(cw+w[i]<=c) //搜索左子樹 {cw+=w[i]; cp+=p[i]; backtrack(i+1); cw-=w[i]; cp-=p[i]; } if(Bound(i+1)>bestp) //搜索右子樹 backtrack(i+1); } 七、算法設(shè)計(jì)題（本題10分） 為了盡可能地逼近目標(biāo)，我們選取的貪心策略為：每一步總是

62、選擇一個(gè)使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個(gè)數(shù)字，否則刪除第一個(gè)遞減區(qū)間的首字符。然后回到串首，按上述規(guī)則再刪除下一個(gè)數(shù)字。重復(fù)以上過程s次，剩下的數(shù)字串便是問題的解了。 具體算法如下： 輸入s, n; while（ s > 0 ） { i=1; //從串首開始找 while (i < length(n)) && (n[i]1)&& (n[1]=‘0’) delete(n,1,1); //刪去串首可能產(chǎn)生的無用零 輸出n;