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

1、學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供學(xué)習(xí)和參考，如有侵權(quán)，請聯(lián)系網(wǎng)站刪除學(xué)習(xí)資料算法分析與設(shè)計期末復(fù)習(xí)題一、 選擇題1應(yīng)用Johnson法則的流水作業(yè)調(diào)度采用的算法是（D）D.動態(tài)規(guī)劃算法A.貪心算法B.分支限界法 C.分治法2 .Hanoi塔問題如下圖所示?，F(xiàn)要求將塔座 A上的的所有圓盤移到塔座 B上，并仍按同樣順序疊置。移動圓盤時遵守Hanoi塔問題的移動規(guī)則。由此設(shè)計出解Hanoi 塔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);hano

2、i(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,

3、 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 .算法分析中，記號。表示(B),記號C表示(A),記號。表示(D)A.漸進(jìn)下界B.漸進(jìn)上界C.非緊上界D.緊漸進(jìn)界E.非緊下界5 .以下關(guān)于漸進(jìn)記號的性質(zhì)是正確的有：(A)A. f(n) -O(g(n),g(n) - 9(h(n) = f (n) - 9(h(n)B. f(n) =O(g(n),g(n) = O(h(n) = h(n) =O(f(n)C. O(f(n)

4、+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.擴(kuò)展結(jié)點優(yōu)先 D.深度優(yōu)先8.分支限界法在問題的解空間樹中,按（A）策略，從根結(jié)點出發(fā)搜索解空間樹A.廣度優(yōu)先B.活結(jié)點優(yōu)先C.擴(kuò)展結(jié)點優(yōu)先D.深度優(yōu)先9.程序塊（A）是回溯法中遍歷排列樹的算法框架程序。A.v

5、oid backtrack (intt)if (t>n) output(x);elsefor (int i=t;i<=n;i+) swap(xt, xi);if (legal(t) backtrack(t+1); swap(xt, xi);B.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&l

6、t;=1;i+) xt=i;if (legal(t) backtrack(t-1);D.void backtrack (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.常見的兩種分支限界法

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

8、個能在非多項式時間內(nèi)被一臺 NDTMf接受的語言;B. NP=L|L是一個能在多項式時間內(nèi)被一臺 NDTMf接受的語言;C. NP=L|L是一個能在多項式時間內(nèi)被一臺 DTMf接受的語言;D. NP=L|L是一個能在多項式時間內(nèi)被一臺 NDTMf接受的語言;14 .記號。的定義正確的是(A)。A. O(g(n) = f(n) |存在正常數(shù)c和n0使得對所有n之n0有：0M f(n) <cg(n) ；B. O(g(n) = f(n) |存在正常數(shù)c和n0使得對所有n至no有：0M cg(n) < f(n) ;C. O(g(n) = f(n) |對于任何正常數(shù)c>0,存在正數(shù)和n

9、0>0使得對所有n之n0 有：0 4f(n)<cg(n)；D. O(g(n) = f(n) |對于任何正常數(shù)c>0,存在正數(shù)和n0 >0使得對所有n 至1有：0 <cg(n) < f(n) ；15 .記號C的定義正確的是(B)。A. O(g(n) = f(n) | 存在正常數(shù)c和n0使得對所有n2n0有：0W f(n) < cg(n) ;B. O(g(n) = f(n) |存在正常數(shù)c和n0使得對所有n之n0有：0M cg(n) < f(n) ;C. (g(n) = f(n) |對于任何正常數(shù)c>0,存在正數(shù)和n0>0使得對所有n2n

10、。 有：0 4f(n)<cg(n);D. (g(n) = f(n) |對于任何正常數(shù)c>0,存在正數(shù)和n0>0使得對所有n'n° 有：0 Mcg(n) < f(n) ；填空題1 .下面程序段的所需要的計算時間為( o(n)。int MaxSum(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+=aj; if(thissum>sum) sum=th

11、issum;besti=i; bestj=j;return sum;2 .有11個待安排的活動，它們具有下表所示的開始時間與結(jié)束時間，如果 以貪心算法求解這些活動的最優(yōu)安排（即為活動安排問題：在所給的活學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供學(xué)習(xí)和參考，如有侵權(quán)，請聯(lián)系網(wǎng)站刪除動集合中選出最大的相容活動子集合），得到的最大相容活動子集合為活 動（1 , 4, 8, 11）。i1234567891011Si130535688212fi45678910111213143 .所謂貪心選擇性質(zhì)是指（所求問題的整體最優(yōu)解可以通過一系列局部最 優(yōu)的選擇，即貪心選擇來達(dá)到）。4 .所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指（問題的最優(yōu)解包含了

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

13、空格 中填入合適的內(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）（b += pi/wi * cleft）;return b;11 .用回溯法解布線問題時，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為n Mm的方格陣列，擴(kuò)展每個結(jié)點需0(

14、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) /該方格未標(biāo)記gridnbr.rownbr.col=gridhere.rowhere.col + 1;if (nbr.row = finish.row) &&(nbr.col = finish.col) break; 完

15、成布線Q.Add(nbr);12 .用回溯法解圖的m著色問題時，使用下面的函數(shù) OK檢查當(dāng)前擴(kuò)展結(jié)點的每一個兒子所相應(yīng)的顏色的可用性，則需耗時（漸進(jìn)時間上限）（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個子問題以及用me

16、rge將k個子問題的解合并為原問題的解需用f(n) 個單位時間。用T(n)表示該分治法解規(guī)模為|P|二n的問題所需的計算時間，則有:kT(n/m) f(n) n 1通過迭代法求得T (n)的顯式表達(dá)式為：T(n)=nlogmk+ £ kj f (n/mj)試證明T (n)的顯式表達(dá)式的正確性。2 .舉反例證明0/1背包問題若使用的算法是按照 pi/wi的非遞減次序考慮選擇的 物品，即只要正在被考慮的物品裝得進(jìn)就裝入背包， 則此方法不一定能得到最優(yōu) 解(此題說明0/1背包問題與背包問題的不同)。證明：舉例如：p=7,4,4,w=3,2,2,c=4時，由于7/3最大，若按題目要求的方 法

17、，只能取第一個，收益是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,使得對所有n>n1, 有 f1(n)W c1f(n)。類似地，對于任意g1(n) w O(g(n),存在正常數(shù)c2和自然數(shù)n2,使得對 所有 n>n2,有 g1(n) <c2g(n) 0令 c3=maxc1, c2, n3 =maxn1, n2 , h(n)= maxf(n),g(n)。則對所有的n - n3,有f1(n) +g1(n) 一 c1f(n) + c2

18、g(n)m c3f(n) + c3g(n) =c3(f(n) + g(n)三 c32 maxf(n),g(n)=2c3h(n) = O(maxf(n),g(n).4 .求證最優(yōu)裝載問題具有貪心選擇性質(zhì)。(最優(yōu)裝載問題：有一批集裝箱要裝上一艘載重量為 c的輪船。其中集裝箱i的重量為Wio最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下， 將盡可能 多的集裝箱裝上輪船。 設(shè)集裝箱已依其重量從小到大排序，(Xl,X2，,x n)是最優(yōu) 裝載問題的一個最優(yōu)解。又設(shè)k = mini | X =1。如果給定的最優(yōu)裝載問題有解，i 口則有 1 <k <n o)證明：四、 解答題1 .機(jī)器調(diào)度問題。

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

20、少需要幾臺機(jī)器？(提示：使用貪心算法)畫出工作在對應(yīng)的機(jī)器上的分配情況。2 .已知非“方程：dn),其中，常數(shù),ng(n)是n的某一個函數(shù)。則f(n)的非遞歸表達(dá)式為：f(n)=cbn+£ bngi 1h(n) =2h(n-1) 1 小斗 »現(xiàn)有Hanoi塔問題的遞歸方程為:i，求h(n)的非遞歸表h(1)=1達(dá)式。解：利用給出的關(guān)系式，此時有：b=2, c=1, g(n)=1,從n遞推到1,有:n 1h(n)=cbn一二：bnJ_Lg(i)i 1= 2n，2T 22 2 1=2n -13 .單源最短路徑的求解。問題的描述：給定帶權(quán)有向圖(如下圖所示)G =(V,E),其中

21、每條邊的權(quán)是非負(fù)實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。解法：現(xiàn)采用算法計算從源頂點1到其它頂點間最短路徑。請將Dijkstra迭代Sudist2dist3dist4dist5初始1-10maxint3010012344 .請寫出用回溯法解裝載問題的函數(shù)。裝載問題：有一批共n個集裝箱要裝上2艘載重量分別為cl和c2的輪船,n v ' wi - C| C2其中集裝箱i的重量為wi,且w。裝載問題要求確定是否有一個合理的裝載方案可將這n個集裝箱裝上這2艘輪船。如果有，找出一種裝載

22、方案。解：void backtrack (int i)/ 搜索第i層結(jié)點if (i > n) /到達(dá)葉結(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.用分支限界法解裝載問題時，對算法進(jìn)行了一些改進(jìn)，下面的程序段給出了 改進(jìn)部分；試說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方 式，算法在

23、執(zhí)行上有什么不同。/檢查左兒子結(jié)點Type wt = Ew + wi; /左兒子結(jié)點的重量if (wt <= c) /可行結(jié)點if (wt > bestw) bestw = wt;/加入活結(jié)點隊列if (i < n) Q.Add(wt);/檢查右兒子結(jié)點if (Ew + r > bestw && i < n)Q.Add(Ew); /可能含最優(yōu)解Q.Delete(Ew); /取下一擴(kuò)展結(jié)點學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供學(xué)習(xí)和參考，如有侵權(quán)，請聯(lián)系網(wǎng)站刪除解答：斜線標(biāo)識的部分完成的功能為：提前更新bestw值；這樣做可以盡早的進(jìn)行對右子樹的剪枝。具體

24、為：算法 Maxloading初始 時將bestw設(shè)置為0,直到搜索到第一個葉結(jié)點時才更新 bestw。因此在算法搜 索到第一個葉子結(jié)點之前，總有 bestw=0, r>0故Ew+r>bestw總是成立。也就 是說，此時右子樹測試不起作用。為了使上述右子樹測試盡早生效，應(yīng)提早更新bestw。又知算法最終找到的最優(yōu)值是所求問題的子集樹中所有可行結(jié)點相應(yīng)重量的最大值。而結(jié)點所相應(yīng)得重量僅在搜索進(jìn)入左子樹是增加，因此，可以在算法每一次進(jìn)入左子樹時更新 bestw的值。7.最長公共子序列問題：給定2個序列X=x1,x2,xmD Y=y1,y2,yn,找出X和Y的最長公共子序列由最長公共子序

25、列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系用cij 記錄序列Xi和Yj的最長公共子序列的長度。其中,Xi=x1,x2,xi ; Yj=y1,y2,yj。當(dāng) i=0 或 j=0 時，空序列是 Xi 和 Yj的最長公共子序列。故此時Cij=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立0i =0, j = 0遞歸關(guān)系如下：cij= ci -1 j -1 1 i, j0;xi - yjmaxci j -1,ci -1j i, j0;xi = yj在程序中，bij 記錄Cij的值是由哪一個子問題的解得到的。(1)請?zhí)顚懗绦蛑械目崭瘢允购瘮?shù) LCSLength完成計算最優(yōu)值的功能。void LCSLen

26、gth(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-1) cij=ci-1j; bij=2;else cij=cij-1; bij=3;學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅

27、供學(xué)習(xí)和參考,如有侵權(quán)，請聯(lián)系網(wǎng)站刪除學(xué)習(xí)資料(2)函數(shù)LC對現(xiàn)由g據(jù)b的內(nèi)容打印出Xi和Yj的最長公共子序列。請?zhí)?寫程序中的空格，以使函數(shù)LCS完成構(gòu)造最長公共子序列的功能(請 將bij 的取值與(1)中您填寫的取值對應(yīng)，否則視為錯誤)。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);else LCS(i , j-1 , x, b);

28、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ù)雜性有 ?口之分，衡量一個算法好壞的標(biāo)準(zhǔn)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)明確定義問

29、題的解空間，問題的解空間至少應(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,在機(jī)器 M1和M2上加工作業(yè)i所需的時間分別為 a和bi,且 (a1,a2,a3,a4)=(4,5,12,10) ， (b1,b2,

30、b3,b4)=(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= Xi, X2, ，Xn是嚴(yán)格遞增的有序集，利用二叉樹的結(jié)點來存儲S中的元素， 在表示 S 的二叉搜索樹中搜索一個元素X， 返回的結(jié)果有兩種情形，( 1)在二叉搜索樹的內(nèi)結(jié)點中找到X=Xi， 其概率為bi。 ( 2) 在二叉搜索樹的葉結(jié)點中確定XC (X, X+i),其概

31、率為a。在表示S的二叉搜索樹T中，設(shè)存儲元素X 的結(jié)點深度為C;葉結(jié)點(X, X+i)的結(jié)點深度為di,則二叉搜索樹T的平均路 長p為多少？假設(shè)二叉搜索樹Tij=X, X+i, 一，X最優(yōu)值為mij,Wij=ai-i +b+ - +b+a ,貝 mij(1<=iv=jv=n) 遞歸關(guān)系表達(dá)式為什么？6 . 描述 0-i 背包問題。三、簡答題( 30 分)1 .流水作業(yè)調(diào)度中，已知有n個作業(yè)，機(jī)器M1和M2上加工作業(yè)i所需的時間分 別為ai和bi,請寫出流水作業(yè)調(diào)度問題的johnson法則中對a和bi的排序算法。 (函數(shù)名可寫為sort(s,n) )2 . 最優(yōu)二叉搜索樹問題的動態(tài)規(guī)劃算法

32、(設(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,2n)9. 最優(yōu)子結(jié)構(gòu)重疊子問題10. 動態(tài)規(guī)劃法二、綜合題1 .問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；構(gòu)造最優(yōu)值的遞歸關(guān)系表達(dá)式；最優(yōu)值的算法描述；構(gòu)造最優(yōu)解；2 .令N=i|a i<b,也i|a i>=b;將N中作業(yè)按a的非減序排序得到N', 將年中作業(yè)按bi

33、的非增序排序得到N/;N'中作業(yè)接N/中作業(yè)就構(gòu)成了 滿足Johnson法則的最優(yōu)調(diào)度。3 .步驟為：N1=1, 3, N2=2, 4;N' =1, 3, N2' =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)。解空間樹為：該問題的最優(yōu)值為：16 最優(yōu)解為：(1,1, 0)nn5.二叉樹 T 的平均路長 P=Z bi * (1 +Ci) +Z aj* dji 1j =0mij=Wij+minmik+mk+1j (1<=i<=j<=n

34、,mii-1=0)mij=0 (i>j)6.已知一個背包的容量為C,有n件物品，物品i的重量為W,價值為V,求應(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.inde

35、x,sk.index);swap(si.tag,sk.tag);l=i;/ 記下當(dāng)前第一個bi 的下標(biāo)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); / 只移動 index 和 tagswap(si.tag,sk.tag);2.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

36、(l=0;l<=n-1;l+)/l是下標(biāo) 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、在進(jìn)行問題的計算復(fù)雜性分析之前，首先必須建立求解問題所用的計算模型。3個基本計算模型是 、。3、算法的復(fù)雜性是 的度量，是評價算法優(yōu)劣的重要依據(jù)。4、計算機(jī)的資源最重

37、要的是 和 資源。因而，算法的復(fù)雜性有 和之分05、f(n尸 6 X2n+n2, f(n)的漸進(jìn)性態(tài) f(n尸 0( )6、貪心算法總是做出在當(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、 何i胃P、NP NPC問題三、算法填空(本題20分，每小題5分)1、n后問題回溯算法學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供學(xué)習(xí)和參考，

38、如有侵權(quán)，請聯(lián)系網(wǎng)站刪除(1)用二維數(shù)組ANN存儲皇后位置，若第i行第j列放有皇后,則Aij 為 非0值，否則值為00(2)分別用一維數(shù)組 MN、L2*N-1、R2*N-1表示豎列、左斜線、右斜線是 否放有棋子，有則值為1,否則值為00for(j=0;j<N;j+)if( 1) /* Aij=i+1；2 if(i=N-1)else 345安全檢查*/*放皇后*/輸出結(jié)果；; ; /*試探下一行*/;/* 去皇后*/學(xué)習(xí)資料2、數(shù)塔問題。有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點可以選擇向 左走或是向右走，一起走到底層，要求找出一條路徑，使路徑上的值最大。for(r=n-2;r>=

39、0;r-) /自底向上遞歸計算for(c=0; 1;c+)if( tr+1c>tr+1c+1)2else_33、Hanoi 算法Hanoi(n,a,b,c) if (n=1)1elseHanoi(n-1,b, a, c);4、Dijkstra算法求單源最短路徑du:s到u的距離pu:記錄前一節(jié)點信息Init-single-source(G,s)for each vertex v VGdo dv=8 ； 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

40、)2. S=3. Q=VG4. while Q<> do u=min(Q)S=S U ufor each vertex 3do 4四、算法理解題（本題10分） 根據(jù)優(yōu)先隊列式分支限界法，求 下圖中從v1點到v9點的單源最 短路徑，請畫出求得最優(yōu)解的解 空間樹。要求中間被舍棄的結(jié)點 用x標(biāo)記，獲得中間解的結(jié)點用 單圓圈?？蚱穑顑?yōu)解用雙圓圈 框起。五、算法理解題（本題5分）設(shè)有n=2k個運動員要進(jìn)行循環(huán)賽,每個選手必須與其他n-1名選手比賽各一次;每個選手一天至多只能賽一次；循環(huán)賽要在最短時間內(nèi)完成。（1）如果n=2循環(huán)賽最少需要進(jìn)行幾天;（2）當(dāng)n=23=8時，請畫出循環(huán)賽日程表。

41、六、算法設(shè)計題（本題15分）分別用貪心算法、動態(tài)規(guī)劃法、回溯法設(shè)計 0-1背包問題。要求：說明所使 用的算法策略；寫出算法實現(xiàn)的主要步驟；分析算法的時間。七、算法設(shè)計題（本題10分）通過鍵盤輸入一個高精度的正整數(shù) n（n的有效位數(shù)0 240）,去掉其中任意s 個數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。編程對給定的n和 s,尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小?！緲永斎搿?78543S=4【樣例輸出】13一、填空題（本題15分，每小題1分）1. 規(guī)則一系列運算2. 隨機(jī)存取機(jī) RAM（RandomAccess Machine）；隨機(jī)存取存儲程序機(jī) RASP（Random Ac

42、cess Stored Program Machine）；圖靈機(jī)（Turing Machine）3. 算法效率4. 時間、空間、時間復(fù)雜度、 空間復(fù)雜度5. 2n6. 最好局部最優(yōu)選擇學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供學(xué)習(xí)和參考，如有侵權(quán)，請聯(lián)系網(wǎng)站刪除7. 貪心選擇最優(yōu)子結(jié)構(gòu)二、簡答題(本題25 分，每小題5 分)6、 分治法的基本思想是將一個規(guī)模為n 的問題分解為k 個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同；對這k 個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k 個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止；將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的

43、問題的解，自底向上逐步求出原來問題的解。7、“最優(yōu)化原理 ”用數(shù)學(xué)化的語言來描述：假設(shè)為了解決某一優(yōu)化問題，需要依次作出n個決策D1, D2,Dn,如若這個決策序列是最優(yōu)的，對于任何一個整數(shù)k， 1 < k < n ，不論前面k 個決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前狀態(tài)，即以后的決策Dk+1, Dk+2,Dn也是最優(yōu)的。8、某個問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。9、 回溯法的基本思想是在一棵含有問題全部可能解的狀態(tài)空間樹上進(jìn)行深度優(yōu)先搜索，解為葉子結(jié)點。搜索過程中，每到達(dá)一個結(jié)點時，則判斷該結(jié)點為根的子樹是否含有問題的解，如果可

44、以確定該子樹中不含有問題的解，則放棄對該子樹的搜索，退回到上層父結(jié)點，繼續(xù)下一步深度優(yōu)先搜索過程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài)空間樹，再進(jìn)行搜索，而是在搜索過程，逐步構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造。10、 P(Polynomial 問題 )：也即是多項式復(fù)雜程度的問題。NP就是Non-deterministicPolynomial的問題，也即是多項式復(fù)雜程度的非確定性問題。NPC(NP Complete)問題，這種問題只有把解域里面的所有可能都窮舉了之 后才能得出答案，這樣的問題是 NP里面最難的問題，這種問題就是 NPC'可 題。三、算法填空(本題20 分，每小題5 分)1

45、、 n 后問題回溯算法(1) !Mj&&!Li+j&&!Ri-j+N(2) Mj=Li+j=Ri-j+N=1;(3) try(i+1,M,L,R,A)(4) Aij=0(5) Mj=Li+j=Ri-j+N=02、數(shù)塔問題。( 1) c<=r(2)trc+=tr+1c( 3) trc+=tr+1c+13、 Hanoi 算法(1) 1) move(a,c)(2) Hanoi(n-1, a, c , b)(3) Move(a,c)4、(1) pv=NIL(2) pv=u(3) v C adju(4) Relax(u,v,w)1 2 3 42 1 4 33 4 1 24 3 2 15 6 7 86 5 8 77 8 5 68 7 6 55 6 7 86 5 8 77 8 5 68 7 6 51 2 3 42 1 4 33 4 1 24 3 2 1四、算法理解題(本題10分)五、(1) 8天(2分)；(2)當(dāng)n=23=8時，循環(huán)賽日程表(3分)六、算法設(shè)計題(本題15分)(1)貪心算法 O (nlog (n)首先計算每種物品單