《算法設(shè)計與分析》考試題目及答案

算法分析與設(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è)計出解Hanoi 塔問題的遞歸算法正確的為： （ B）A. void hanoi(int n, int A, int C, int B)if (n > 0)Hanoi 塔hanoi(n-1,A,C, B);move(n,a,b);hanoi(n-1, C, B, A);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 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(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）， 記號 表示（ A）， 記號 表示（ 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(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ì)C最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D. 預(yù)排序與遞歸調(diào)用7. 回溯法在問題的解空間樹中，按（ D）策略，從根結(jié)點出發(fā)搜索解空間樹。A 廣度優(yōu)先B. 活結(jié)點優(yōu)先C.擴展結(jié)點優(yōu)先D. 深度優(yōu)先8. 分支限界法在問題的解空間樹中， 按（ A）策略，從根結(jié)點出發(fā)搜索解空間樹。A 廣度優(yōu)先B. 活結(jié)點優(yōu)先C.擴展結(jié)點優(yōu)先D. 深度優(yōu)先9. 程序塊（ A ）是回溯法中遍歷排列樹的算法框架程序。A.voidbacktrack(int t)B.if (t>n) output(x);elsefor (int i=t;i<=n;i+) swap(xt, xi);if (legal(t) backtrack(t+1);swap(xt, xi);void backtrack (int t)if (t>n) output(x);elsefor (int i=0;i<=1;i+) xt=i;if (legal(t) backtrack(t+1);C. void backtrack (int t)if (t>n) output(x); elsefor (int i=0;i<=1;i+) xt=i;if (legal(t) backtrack(t-1);D.voidbacktrack(int t)if (t>n) output(x);elsefor (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. 常見的兩種分支限界法為（ D）A. 廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B. 隊列式（ FIFO）分支限界法與堆棧式分支限界法；C. 排列樹法與子集樹法；D. 隊列式（ FIFO）分支限界法與優(yōu)先隊列式分支限界法；12. k 帶圖靈機的空間復(fù)雜性 S(n) 是指（ B）A. k 帶圖靈機處理所有長度為 n 的輸入時，在某條帶上所使用過的最大方格數(shù)。B. k 帶圖靈機處理所有長度為 n 的輸入時，在 k 條帶上所使用過的方格數(shù)的總和。C. k 帶圖靈機處理所有長度為 n 的輸入時，在 k 條帶上所使用過的平均方格數(shù)。D. k 帶圖靈機處理所有長度為 n 的輸入時，在某條帶上所使用過的最小方格數(shù)。13. NP 類語言在圖靈機下的定義為（ D）A.NP=L|L 是一個能在非多項式時間內(nèi)被一臺NDTM所接受的語言 ；B.NP=L|L 是一個能在多項式時間內(nèi)被一臺NDTM所接受的語言 ；C.NP=L|L 是一個能在多項式時間內(nèi)被一臺DTM所接受的語言 ；D.NP=L|L 是一個能在多項式時間內(nèi)被一臺NDTM所接受的語言 ；14. 記號 O 的定義正確的是（ A ）。A. O(g(n) = f(n) |存在正常數(shù) c 和 n0 使得對所有 nn0 有： 0f(n)cg(n) ；B.O(g(n)= f(n)|存在正常數(shù) c 和 n0 使得對所有 nn0 有： 0cg(n)f(n) ；C.O(g(n)= f(n)|對于任何正常數(shù) c>0，存在正數(shù)和 n0 >0 使得對所有 n n0有： 0f(n)<cg(n) ；D. O(g(n) = f(n) |對于任何正常數(shù) c>0，存在正數(shù)和 n0 >0 使得對所有nn0 有： 0cg(n) < f(n) ；15. 記號 的定義正確的是（ B）。A. O(g(n) = f(n) |存在正常數(shù) c 和 n0 使得對所有 nn0 有： 0f(n)cg(n) ；B.O(g(n)= f(n)| 存在正常數(shù) c 和 n0 使得對所有 nn0 有： 0cg(n)f(n) ；C.(g(n)= f(n)|對于任何正常數(shù) c>0，存在正數(shù)和 n0 >0 使得對所有 nn0有： 0f(n)<cg(n) ；D.(g(n)= f(n)|對于任何正常數(shù)，存在正數(shù)和n>0 使得對所有 nnc>000有： 0cg(n) < f(n) ；二、填空題1.下面程序段的所需要的計算時間為（O(n 2 )）。intMaxSum(int n, int*a,intint 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;&besti,int &bestj)return sum;2. 有 11 個待安排的活動，它們具有下表所示的開始時間與結(jié)束時間，如果以貪心算法求解這些活動的最優(yōu)安排（即為活動安排問題：在所給的活動集合中選出最大的相容活動子集合） ，得到的最大相容活動子集合為活動（ 1 ，4，8，11）。i1234567891011Si130535688212fi45678910111213143. 所謂貪心選擇性質(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é)點到當(dāng)前擴展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為 h(n) ，則回溯法所需的計算空間通常為（ O(h(n) ）。7. 回溯法的算法框架按照問題的解空間一般分為 （子集樹）算法框架與（排列樹）算法框架。8. 用回溯法解 0/1 背包問題時，該問題的解空間結(jié)構(gòu)為（ 子集樹）結(jié)構(gòu)。9. 用回溯法解批處理作業(yè)調(diào)度問題時，該問題的解空間結(jié)構(gòu)為（排列樹）結(jié)構(gòu)。10. 用回溯法解 0/1 背包問題時，計算結(jié)點的上界的函數(shù)如下所示， 請在空格中填入合適的內(nèi)容：Typep Knap<Typew, Typep>:Bound(int i)/計算上界Typew cleft = c - cw; /Typep b = cp;/剩余容量結(jié)點的上界/ 以物品單位重量價值遞減序裝入物品while (i <= n && wi <= cleft) cleft -= wi;b += pi;i+;/ 裝滿背包if (i <= n)return b;（b += pi/wi * cleft） ;11. 用回溯法解布線問題時， 求最優(yōu)解的主要程序段如下。 如果布線區(qū)域劃分為n m 的方格陣列，擴展每個結(jié)點需 O(1) 的時間， L 為最短布線路徑的長度，則算法共耗時 ( O(mn) ) ，構(gòu)造相應(yīng)的最短距離需要（ 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.rowhere.col + 1;if (nbr.row = finish.row) &&(nbr.col = finish.col) break; / 完成布線 Q.Add(nbr);12. 用回溯法解圖的 m 著色問題時，使用下面的函數(shù) OK 檢查當(dāng)前擴展結(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. 一個分治法將規(guī)模為 n 的問題分成 k 個規(guī)模為 n m的子問題去解。設(shè)分解閥值 n0=1，且 adhoc 解規(guī)模為 1 的問題耗費 1 個單位時間。再設(shè)將原問題分解為 k 個子問題以及用 merge將 k 個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n) 表示該分治法解規(guī)模為 |P|=n 的問題所需的計算時間，O(1)n1則有： T (n)f (n) n1kT( n / m)loglog m n1通過迭代法求得 T（n）的顯式表達式為：mkk j f ( n / m j )T (n) nj 0試證明 T（ n）的顯式表達式的正確性。2. 舉反例證明0/1背包問題若使用的算法是按照pi/w i 的非遞減次序考慮選擇的物品，即只要正在被考慮的物品裝得進就裝入背包， 則此方法不一定能得到最優(yōu)解（此題說明 0/1 背包問題與背包問題的不同） 。證明：舉例如： p=7,4,4,w=3,2,2,c=4 時，由于 7/3 最大，若按題目要求的方法，只能取第一個，收益是 7。而此實例的最大的收益應(yīng)該是 8，取第 2，3 個。3. 求證： O(f(n)+O(g(n) = O(maxf(n),g(n)。證明：對于任意f1(n)O(f(n)，存在正常數(shù)c1 和自然數(shù)n1，使得對所有 nn1，有f1(n)c1f(n)。所有類似地，對于任意nn2，有 g1(n)g1(n)c2g(n)。O(g(n)，存在正常數(shù)c2 和自然數(shù)n2，使得對令 c3=maxc1, c2 ，n3 =maxn1, n2 ，h(n)= maxf(n),g(n)。則對所有的nn3，有f1(n) +g1(n)c1f(n) + c2g(n)c3f(n) + c3g(n)= c3(f(n) + g(n)c32 maxf(n),g(n)= 2c3h(n) = O(maxf(n),g(n) .4. 求 最 裝 具有 心 性 。（最 裝 ： 有一批集裝箱要裝上一艘 重量 c 的 船。其中集裝箱i 的重量 Wi。最 裝 要求確定在裝 體 不受限制的情況下，將盡可能多的集裝箱裝上 船。 集裝箱已依其重量從小到大排序，(x 1,x 2, ,x n) 是最 裝 的一個最 解。 又 kmin i | xi1。如果 定的最 裝 有解，1 in 有 1kn 。） 明：四、解答 1. 機器 度 。 描述： 在有n 件任 和無限多臺的機器，任 可以在機器上得到 理。每件任 的開始 si ，完成 fi ，si <fi 。si，f i 理任 i 的 范 。兩個任 i ，j 重疊指兩個任 的 范 區(qū) 有重疊，而并非指 i ，j 的起點或 點重合。例如：區(qū) 1，4與區(qū) 2， 4重疊，而與 4， 7 不重疊。一個可行的任 分配是指在分配中沒有兩件重疊的任 分配 同一臺機器。因此，在可行的分配中每臺機器在任何 刻最多只 理一個任 。最 分配是指使用的機器最少的可行分配方案。 例：若任 占用的 范 是1 ，4， 2，5，4 ，5，2， 6，4，7 ， 按 完成所有任 最少需要幾臺機器？（提示：使用 心算法）畫出工作在 的機器上的分配情況。f (n)bf (n1)g(n)2. 已知非 次 方程：，其中，b、c是常數(shù)，f (0)cng(n)是 n 的某一個函數(shù)。 f(n)的非 表達式 ：f (n)cbnbn ig(i)。i 1現(xiàn)有 Hanoi 塔問題的遞歸方程為：h(n) 2h(n1) 1h(1)，求 h(n)的非遞歸表1達式。解：利用給出的關(guān)系式，此時有：b=2, c=1, g(n)=1, 從 n 遞推到 1，有：n1h(n)cb n 1bn 1i g(i)i12n 12n 2. 222 12n13. 單源最短路徑的求解。問題的描述：給定帶權(quán)有向圖（如下圖所示）G =(V,E) ，其中每條邊的權(quán)是非負實數(shù)。另外，還給定V 中的一個頂點，稱為源。現(xiàn)在要計算從源到所有其它各頂點的最短路長度。 這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。解法：現(xiàn)采用 Dijkstra算法計算從源頂點1 到其它頂點間最短路徑。請將此過程填入下表中。迭代Sudist2dist3dist4dist5初始1-10maxint3010012344. 請寫出用回溯法解裝載問題的函數(shù)。裝載問題：有一批共n 個集裝箱要裝上2 艘載重量分別為 c1 和 c2 的輪船，nwic1c2其中集裝箱 i 的重量為 wi ，且 i 1。裝載問題要求確定是否有一個合理的裝載方案可將這n 個集裝箱裝上這2 艘輪船。如果有，找出一種裝載方案。解： voidbacktrack(int i)/搜索第i層結(jié)點if(i > n) /到達葉結(jié)點更新最優(yōu)解bestx,bestw;return;r -= wi;if(cw + wi <= c) /搜索左子樹xi = 1;cw += wi;backtrack (i + 1);cw -= wi;if(cw + r > bestw) xi = 0; /搜索右子樹backtrack (i + 1);r += wi;5. 用分支限界法解裝載問題時，對算法進行了一些改進，下面的程序段給出了改進部分；試說明斜線部分完成什么功能， 以及這樣做的原因， 即采用這樣的方式，算法在執(zhí)行上有什么不同。/檢查左兒子結(jié)點Type wt = Ew + wi;if (wt <= c) /左兒子結(jié)點的重量可行結(jié)點if (wt > bestw) bestw = wt;/ 加入活結(jié)點隊列if (i < n) Q.Add(wt);/ 檢查右兒子結(jié)點if (Ew + r > bestw && i < n)Q.Add(Ew);/Q.Delete(Ew);/可能含最優(yōu)解取下一擴展結(jié)點解答：斜 的部分完成的功能 ：提前更新bestw ； 做可以盡早的 行 右子 的剪枝。具體 ：算法Maxloading 初始 將 bestw 置 0，直到搜索到第一個葉 點 才更新bestw 。因此在算法搜索到第一個葉子 點之前， 有bestw=0，r>0 故 Ew+r>bestw 是成立。也就是 ，此 右子 不起作用。 了使上述右子 盡早生效， 提早更新bestw 。又知算法最 找到的最 是所求 的子集 中所有可行 點相 重量的最大 。而 點所相 得重量 在搜索 入左子 是增加，因此，可以在算法每一次 入左子 更新bestw 的 。7. 最 公共子序列 ： 定 2 個序列 X=x1,x2, ,xm 和 Y=y1,y2, ,yn ，找出 X 和 Y 的最 公共子序列。由最 公共子序列 的最 子 構(gòu)性 建立子 最 的 關(guān)系。用 cij 序列 Xi 和 Yj 的最 公共子序列的 度。其中，Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng) i=0 或 j=0 ，空序列是 Xi 和 Yj的最 公共子序列。故此 Cij=0。其它情況下，由最 子 構(gòu)性 可建立 關(guān)系如下：c i j 0c i1 j1max c i j1,ci11 j ii , ji , j0, j0; xi0; xi0yjy j在程序中，bij記錄Cij的 是由哪一個子 的解得到的。（1） 填寫程序中的空格，以使函數(shù)LCSLength完成 算最 的功能。voidLCSLength(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;else if (ci-1j>=cij-1cij=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)，否則視為錯誤） 。voidLCS(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-1else LCS(i ，j-1 ，x，b);，j，x，b);8. 對下面的遞歸算法，寫出調(diào)用 f(4) 的執(zhí)行結(jié)果。void f(int k) if( k>0 ) printf("%dn ",k); f(k-1);f(k-1);一、填空題 （20 分）1. 一個算法就是一個有窮規(guī)則的集合， 其中之規(guī)則規(guī)定了解決某一特殊類型問題的 一 系 列 運 算 ， 此 外 ， 算 法 還 應(yīng) 具 有 以 下 五 個 重 要 特性:_,_,_,_,_ 。2. 算法的復(fù)雜性有 _和 _之分，衡量一個算法好壞的標準是 _。3. 某 一 問 題 可 用 動 態(tài) 規(guī) 劃 算 法 求 解 的 顯 著 特 征 是。4. 若序列 X=B,C,A,D,B,C,D ，Y=A,C,B,A,B,D,C,D，請給出序列X 和個最長公共子序列。Y 的一5. 用回溯法解問題時，應(yīng)明確定義問題的解空間，問題的解空間至少應(yīng)包含_。6. 動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干_，先求解_，然后從這些 _的解得到原問題的解。7. 以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為 _。8.0-1背包問題的回溯算法所需的計算時間為_,用動態(tài)規(guī)劃算法所需的計算時間為 _。9. 動態(tài)規(guī)劃算法的兩個基本要素是 _和 _。10. 二分搜索算法是利用 _實現(xiàn)的算法。二、綜合題 （50 分）1. 寫出設(shè)計動態(tài)規(guī)劃算法的主要步驟。2. 流水作業(yè)調(diào)度問題的 johnson 算法的思想。3. 若 n=4，在機器 M1 和 M2 上加工作業(yè) i 所需的時間分別為 ai 和 bi ，且 (a 1,a 2 ,a 3,a 4)=(4,5,12,10) ， (b 1,b 2,b 3,b 4)=(8,2,15,9) 求 4 個作業(yè)的最優(yōu)調(diào)度方案，并計算最優(yōu)值。4. 使用回溯法解 0/1 背包問題： n=3，C=9，V=6,10,3 ，W=3,4,4, 其解空間有長度為 3 的 0-1 向量組成，要求用一棵完全二叉樹表示其解空間 （從根出發(fā)， 左1 右 0），并畫出其解空間樹，計算其最優(yōu)值及最優(yōu)解。5. 設(shè) S=X1，X2，Xn是嚴格遞增的有序集，利用二叉樹的結(jié)點來存儲 S 中的元素，在表示 S 的二叉搜索樹中搜索一個元素 X，返回的結(jié)果有兩種情形，（1）在二叉搜索樹的內(nèi)結(jié)點中找到 X=Xi，其概率為 bi 。（2）在二叉搜索樹的葉結(jié)點中確定 X（ Xi ，Xi+1 ），其概率為 ai 。在表示 S 的二叉搜索樹 T 中，設(shè)存儲元素 Xi的結(jié)點深度為 Ci ；葉結(jié)點（ Xi ，Xi+1 ）的結(jié)點深度為 di ，則二叉搜索樹 T 的平均路長 p 為多少？假設(shè)二叉搜索樹 Tij= Xi ， Xi+1 ，Xj 最優(yōu)值為 mij ， ai-1 +bi + +bj +aj ，則 mij(1<=i<=j<=n) 遞歸關(guān)系表達式為什么？ Wij=6. 描述 0-1 背包問題。三、簡答題 （30 分）1. 流水作業(yè)調(diào)度中， 已知有 n 個作業(yè)，機器 M1和 M2上加工作業(yè) i 所需的時間分別為 ai 和 bi ，請寫出流水作業(yè)調(diào)度問題的johnson 法則中對 ai 和 bi 的排序算法。（函數(shù)名可寫為sort(s,n)）2. 最優(yōu)二叉搜索樹問題的動態(tài)規(guī)劃算法（設(shè)函數(shù)名binarysearchtree)）答案：一、填空1確定性有窮性可行性0 個或多個輸入一個或多個輸出2. 時間復(fù)雜性 空間復(fù)雜性 時間復(fù)雜度高低3. 該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)4.BABCD或 CABCD或CADCD5. 一個（最優(yōu)）解6. 子問題子問題子問題7. 回溯法8. o(n*2 n) o(minnc,2 n )9. 最優(yōu)子結(jié)構(gòu) 重疊子問題10. 動態(tài)規(guī)劃法二、綜合題1. 問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)； 構(gòu)造最優(yōu)值的遞歸關(guān)系表達式； 最優(yōu)值的算法描述；構(gòu)造最優(yōu)解；2. 令 N1=i|a i <bi ，N2=i|a i >=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 ， N 2=4 ， 2 ；最優(yōu)值為： 384. 解空間為 (0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)。解空間樹為：1A0BC1010DEFG11011000HIJKLMNO該問題的最優(yōu)值為：16最優(yōu)解為：（1，1，0）nn5. 二叉樹T 的平均路長P=bi * (1Ci)+aj * dji1j0mij=Wij+minmik+mk+1j (1<=i<=j<=n,mii-1=0)mij=0(i>j)6. 已知一個背包的容量為 C，有 n 件物品，物品 i 的重量為 Wi，價值為 Vi ，求應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大。三、簡答題1.void sort(flowjope s,int n)int i,k,j,l;for(i=1;i<=n-1;i+)/-選擇排序k=i;while(k<=n&&sk.tag!=0) k+;if(k>n) break;/-沒有 ai ，跳出elsefor(j=k+1;j<=n;j+)if(sj.tag=0)if(sk.a>sj.a)k=j;swap(si.index,sk.index);swap(si.tag,sk.tag);l=i;/-記下當(dāng)前第一個 bi 的下標for(i=l;i<=n-1;i+)k=i;for(j=k+1;j<=n;j+)if(sk.b<sj.b) k=j;swap(si.index,sk.index); /-swap(si.tag,sk.tag);只移動 index和 tag2.void binarysearchtree(int a,int b,int n,int *m,int *s,int *w)int i,j,k,t,l;for(i=1;i<=n+1;i+)wii-1=ai-1;mii-1=0;for(l=0;l<=n-1;l+)/-l是下標j-i的差for(i=1;i<=n-l;i+)j=i+l;wij=wij-1+aj+bj;mij=mii-1+mi+1j+wij;sij=i;for(k=i+1;k<=j;k+)t=mik-1+mk+1j+wij;if(t<mij)mij=t;sij=k;一、填空題（本題 15 分，每小題 1 分）1、算 法就 是一組有窮的，它們規(guī) 定了 解決某一特定類型 問題的。2、在進行問題的計算復(fù)雜性分析之前，首先必須建立求解問題所用的計算模型。 3 個基本計算模型是、。3、算法的復(fù)雜性是的度量，是評價算法優(yōu)劣的重要依據(jù)。4、計算機的資源最重要的是和資源。因而，算法的復(fù)雜性有和之分。n2，f(n) 的漸進性態(tài) f(n)= O()5、f(n)= 6 2 +n6、貪心算法總是做出在當(dāng)前看來的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的。7、許多可以用貪心算法求解的問題一般具有2 個重要的性質(zhì)：性質(zhì)和性質(zhì)。二、簡答題（本題 25 分，每小題 5 分）1、簡單描述分治法的基本思想。2、簡述動態(tài)規(guī)劃方法所運用的最優(yōu)化原理。3、何謂最優(yōu)子結(jié)構(gòu)性質(zhì)？4、簡單描述回溯法基本思想。5、何謂 P、 NP、NPC問題三、算法填空（本題20 分，每小題 5 分）1、n 后問題回溯算法(1) 用二維數(shù)組 ANN非 0 值, 否則值為 0。存儲皇后位置, 若第i行第j列放有皇后, 則Aij為(2) 分別用一維數(shù)組 MN、L2*N-1 、R2*N-1 表示豎列、左斜線、右斜線是否放有棋子，有則值為1, 否則值為 0。for(j=0;j<N;j+)if( 1) /*安全檢查*/ Aij=i+1;/*放皇后 */2；if(i=N-1)else345；;輸出結(jié)果；; /*試探下一行/*去皇后 */*/2、數(shù)塔問題。有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點可以選擇向左走或是向右走，一起走到底層，要求找出一條路徑，使路徑上的值最大。for(r=n-2;r>=0;r-) /自底向上遞歸計算for(c=0;1;c+)if( tr+1c>tr+1c+1)2；else3；3、Hanoi 算法Hanoi(n,a,b,c)if（ n=1）else231；Hanoi(n-1,b, a, c);4、Dijkstra算法求單源最短路徑du:s到 u 的距離pu:記錄前一節(jié)點信息Init-single-source(G,s)for each vertex v VGdo dv=;1ds=0Relax(u,v,w)if dv>du+w(u,v)then dv=du+wu,v;2dijkstra(G,w,s)1. Init-single-source(G,s)2. S= 3. Q=VG4.while Q<>do u=min(Q)S=Sufor each vertex3do4四、算法理解題（本題10 分）根據(jù)優(yōu)先隊列式分支限界法， 求下圖中從 v1 點到 v9 點的單源最短路徑，請畫出求得最優(yōu)解的解空間樹。要求中間被舍棄的結(jié)點用標記，獲得中間解的結(jié)點用單圓圈框起，最優(yōu)解用雙圓圈框起。五、算法理解題（本題5 分）k設(shè)有 n=2 個運動員要進行循環(huán)賽，現(xiàn)設(shè)計一個滿足以下要求的比賽日程表：每個選手必須與其他n-1 名選手比賽各一次；每個選手一天至多只能賽一次；（ 1）如果 n=2k ，循環(huán)賽最少需要進行幾天；（ 2）當(dāng) n=23 =8 時，請畫出循環(huán)賽日程表。六、算法設(shè)計題（本題15 分）分別用貪心算法、動態(tài)規(guī)劃法、回溯法設(shè)計 0-1 背包問題。要求：說明所使用的算法策略；寫出算法實現(xiàn)的主要步驟；分析算法的時間。七、算法設(shè)計題（本題10 分）通過鍵盤輸入一個高精度的正整數(shù) n(n 的有效位數(shù) 240) ，去掉其中任意 s 個數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。 編程對給定的 n 和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小?！緲永斎搿?78543S=4【樣例輸出】13一、填空題（本題15 分，每小題 1 分）1規(guī)則一系列運算2. 隨 機 存 取 機 RAM(RandomAccess Machine) ； 隨 機 存 取 存 儲 程 序 機 RASP(Random Access Stored Program Machine) ；圖靈機 (Turing Machine)3. 算法效率4. 時間 、空間、時間復(fù)雜度、空間復(fù)雜度52n6最好局部最優(yōu)選擇7. 心 最 子 構(gòu)二、 答 （本 25 分，每小 5 分）6、分治法的基本思想 是將一個 模 n 的 分解 k 個 模 小的子 ， 些子 互相獨立且與原 相同； k 個子 分 求解。如果子 的 模仍然不 小， 再劃分 k 個子 ，如此 的 行下去，直到 模足 小，很容易求出其解 止；將求出的小 模的 的解合并 一個更大 模的 的解，自底向上逐步求出原來 的解。7、“ 最 化原理 ”用數(shù)學(xué)化的 言來描述：假 了解決某一 化 ，需要依次作出 n 個決策 D1，D2， Dn，如若 個決策序列是最 的， 于任何一個整數(shù) k，1 < k < n，不 前面 k 個決策是怎 的，以后的最 決策只取決于由前面決策所確定的當(dāng)前狀 ，即以后的決策 Dk+1，Dk+2，Dn 也是最 的。8、某個 的最 解包含著其子 的最 解。 種性 稱 最 子 構(gòu)性質(zhì)。9、回溯法的基本思想 是在一棵含有 全部可能解的狀 空 上 行深度 先搜索，解 葉子 點。搜索 程中，每到達一個 點 ， 判斷 點 根的子 是否含有 的解，如果可以確定 子 中不含有 的解， 放棄 子 的搜索，退回到上 父 點， 下一步深度 先搜索 程。在回溯法中，并不是先構(gòu)造出整棵狀 空 ，再 行搜索，而是在搜索 程，逐步構(gòu)造出狀 空 ，即 搜索， 構(gòu)造。10、 P(Polynomial 問題 ) ：也即是多 式復(fù) 程度的 。NP就是 Non-deterministicPolynomial的 ，也即是多 式復(fù) 程度的非確定性 。NPC(NP Complete) ， 種 只有把解域里面的所有可能都 了之后才能得出答案， 的 是 NP里面最 的 ， 種 就是 NPC問 。三、算法填空（本 20 分，每小 5