算法設(shè)計(jì)與分析考試題目及答案教學(xué)內(nèi)容

1、算法設(shè)計(jì)與分析考試題目及答案精品資料算法分析與設(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上,Hanoi 塔并仍按同樣順序疊置。移動(dòng)圓盤時(shí)遵守 Ha noi塔問題的移動(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,C, B); move( n, a,b);hanoi(n-1, C, B

2、, 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 han oi(i nt n, i nt C, i nt B, i nt A) if (n > 0)hanoi(n-1, A, C, B); move( n, a,b);D. void hanoi(int n, int C, int A, int B) if (n > 0)hanoi(n-1, A, C, B);move( n, a,b);ha

3、noi(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)用表示（D）。4. 算法分析中，記號(hào)0表示（B），記號(hào) 表示（A）,記號(hào)A. 漸進(jìn)下界B. 漸進(jìn)上界C. 非緊上界D. 緊漸進(jìn)界E. 非緊下界5.以下關(guān)于漸進(jìn)記號(hào)的性質(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)僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除 謝謝7C. O(f(n )+0(g( n

4、) = O(mi nf(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é)點(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)優(yōu)先C.擴(kuò)展結(jié)點(diǎn)優(yōu)先D.深度優(yōu)先9. 程序塊(A)是回溯法中遍歷排列樹的算法框架程序。void

5、 backtrack (int t)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)如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)put鍬)；謝謝4elsefor (int i=0;i<=1;i+) xt=i;C.void backtrack (int t) if (t>n) output(x); elsefor (int i=0;i<=1;i+) xt=i;if (legal(t) backt

6、rack(t-1);D.(int t)if (t>n) output(x); elsefor (int i=t;i<=n ;i+) swap(xt, xi);if (legal(t) backtrack(t+1); 10. 回溯法的效率不依賴于以下哪一個(gè)因素？ （ C ）A. 產(chǎn)生xk的時(shí)間；B. 滿足顯約束的xk值的個(gè)數(shù)；C. 問題的解空間的形式；D. 計(jì)算上界函數(shù)bound的時(shí)間；xk的個(gè)數(shù)E. 滿足約束函數(shù)和上界函數(shù)約束的所有精品資料F.計(jì)算約束函數(shù)constraint的時(shí)間；11. 常見的兩種分支限界法為（D）A. 廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B. 隊(duì)列式（FI

7、FO）分支限界法與堆棧式分支限界法；C. 排列樹法與子集樹法；D. 隊(duì)列式（FIFO）分支限界法與優(yōu)先隊(duì)列式分支限界法；12. k帶圖靈機(jī)的空間復(fù)雜性S（n）是指（B）A. k帶圖靈機(jī)處理所有長(zhǎng)度為n的輸入時(shí)，在某條帶上所使用過的最大方格 數(shù)。B. k帶圖靈機(jī)處理所有長(zhǎng)度為n的輸入時(shí)，在k條帶上所使用過的方格數(shù)的 總和。C. k帶圖靈機(jī)處理所有長(zhǎng)度為n的輸入時(shí)，在k條帶上所使用過的平均方格 數(shù)。D. k帶圖靈機(jī)處理所有長(zhǎng)度為n的輸入時(shí)，在某條帶上所使用過的最小方格 數(shù)。13. NP類語言在圖靈機(jī)下的定義為（D）A. NP=L|L是一個(gè)能在非多項(xiàng)式時(shí)間內(nèi)被一臺(tái)NDT晰接受的語言；B. NP=L|

8、L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái) NDTM所接受的語言；C. NP=L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái) DTM所接受的語言；D. NP=L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái) NDTM所接受的語言;14. 記號(hào)0的定義正確的是(A)A.0(g( n) = f(n) |存在正常數(shù)c和n0使得對(duì)所有n no有：0 f(n)cg(n) ；B. 0(g( n) = f(n) |存在正常數(shù)c和nO使得對(duì)所有n no有：0 cg(n)f(n) C. 0(g( n) = f(n) |對(duì)于任何正常數(shù)c>0,存在正數(shù)和n° >0使得對(duì)所有僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝9n n0有：0

9、f(n)<cg(n) ；D. O(g( n) = f(n) |對(duì)于任何正常數(shù)c>0,存在正數(shù)和n° >0使得對(duì)所有n n0有：0 cg(n) < f(n) 15.記號(hào)的定義正確的是(B)A. O(g( n) = f(n) |cg(n) ；B. O(g( n) = f(n) |f(n) ；存在正常數(shù)c和n0使得對(duì)所有n n0有：0 f(n)存在正常數(shù)c和n0使得對(duì)所有n n0有：0 cg(n)C.(g( n) = f(n) |對(duì)于任何正常數(shù)c>0,存在正數(shù)和n°>0使得對(duì)所有n n0有：0f(n)<cg(n) ；D. (g(n) =

10、f(n) |對(duì)于任何正常數(shù)c>0,存在正數(shù)和n° >0使得對(duì)所有n n0有：0 cg(n) < f(n) ；精品資料填空題1. 下面程序段的所需要的計(jì)算時(shí)間為(0(n2)int MaxSum(i nt n, int *a, int &besti, int& bestj) int sum=0;for(int i=1;i<=n;i+)int thissum=0;for(i nt j=i;j<=n ;j+)thissum+=aj;if(thissum>sum) sum=thissum;besti=i;bestj=j;return sum;

11、僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除 謝謝132. 有11個(gè)待安排的活動(dòng)，它們具有下表所示的開始時(shí)間與結(jié)束時(shí)間，如果以貪心算法求解這些活動(dòng)的最優(yōu)安排（即為活動(dòng)安排問題：在所給的 活動(dòng)集合中選出最大的相容活動(dòng)子集合），得到的最大相容活動(dòng)子集合 為活動(dòng)（1，4，8，11）。i1234567891011Si130535688212fi45678910111213143. 所謂貪心選擇性質(zhì)是指（所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到）。4. 所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指（問題的最優(yōu)解包含了其子問題的最優(yōu)解）。5. 回溯法是指（具有限界函數(shù)的深度優(yōu)先生成法）。6. 用回溯法解題的

12、一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h（n），貝U回溯法所需的計(jì)算空間通常為（0（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í)，計(jì)算結(jié)點(diǎn)的上界的函數(shù)如下所示，請(qǐng)?jiān)诳崭裰刑钊牒线m的內(nèi)容：Typep KnapvTypew, Typep>: Bound(in

13、t i)/計(jì)算上界Typew cleft = c - cw; /剩余容量Typep b = cp; /結(jié)點(diǎn)的上界/以物品單位重量?jī)r(jià)值遞減序裝入物品while (i <= n && wi <= cleft) cleft -= wi;b += pi;i+;11. 用回溯法解布線問題時(shí)，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為n m的方格陣列，擴(kuò)展每個(gè)結(jié)點(diǎn)需 0（1）的時(shí)間，L為最短布線路徑的長(zhǎng)度,則算法共耗時(shí)（O（mn），構(gòu)造相應(yīng)的最短距離需要（O（L）時(shí)間for (int i = 0; i < NumOfNbrs; i+) n br.row = here.r

14、ow + offseti.row;n br.col = here.col + offseti.col;if (grid nbr.row nbr.col = 0) /該方格未標(biāo)記grid nbr.row nbr.col=gridhere.rowhere.col + 1;if (nbr.row = fini sh.row) &&(n br.col = fin ish.col) break; /完成12. 用回溯法解圖的m著色問題時(shí)，使用下面的函數(shù) 0K檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色的可用性，則需耗時(shí)（漸進(jìn)時(shí)間上限）（O(mn)。精品資料Bool Color:OK(i nt

15、 k)/for(i nt j=1;j<=n ;j+)if(akj= =1)&&(xj= =xk) return false; return true;13. 旅行售貨員問題的解空間樹是(排列樹)證明題僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除 謝謝171. 一個(gè)分治法將規(guī)模為n的問題分成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)O(1) n 1k

16、T(n/m) f (n) n 1logmn 1通過迭代法求得T (n)的顯式表達(dá)式為：T(n) n碗m*kJ f (n/mj)j 0試證明T (n)的顯式表達(dá)式的正確性。2. 舉反例證明0/1背包問題若使用的算法是按照pi/wi的非遞減次序考慮選擇的 物品，即只要正在被考慮的物品裝得進(jìn)就裝入背包，則此方法不一定能得到最 優(yōu)解(此題說明0/1背包問題與背包問題的不同)。證明：舉例如：p=7,4,4,w=3,2,2,c=4時(shí)，由于7/3最大，若按題目要求的方法，只能取第一個(gè)，收益是7。而此實(shí)例的最大的收益應(yīng)該是 8,取第2, 3 個(gè)。3.求證：O(f(n)+0(g(n) = O(maxf(n),g

17、(n)。證明：對(duì)于任意f1(n) O(f(n)，存在正常數(shù)cl和自然數(shù)n1,使得對(duì)所有n n1，有 f1(n) c1f(n)。類似地，對(duì)于任意g1(n)O(g(n)，存在正常數(shù)c2和自然數(shù)n2,使得對(duì)所有 n n2，有 g1(n) c2g(n)。令 c3=maxc1, c2， n3 =maxn1, n2， h(n)= maxf(n),g(n)。則對(duì)所有的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. 求證最優(yōu)裝

18、載問題具有貪心選擇性質(zhì)。(最優(yōu)裝載問題：有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡 可能多的集裝箱裝上輪船。設(shè)集裝箱已依其重量從小到大排序，(x 1,x 2,x n)是最優(yōu)裝載問題的一個(gè)最優(yōu)解。又設(shè) k mini |xi 1。如果給定1 i n的最優(yōu)裝載問題有解，則有1 k n。)證明：四、解答題1. 機(jī)器調(diào)度問題。問題描述：現(xiàn)在有n件任務(wù)和無限多臺(tái)的機(jī)器，任務(wù)可以在機(jī)器上得 到處理。每件任務(wù)的開始時(shí)間為 Si，完成時(shí)間為fi，SiVfi。Si，fi為處理任 務(wù)i的時(shí)間范圍。兩個(gè)任務(wù)i, j重疊指兩個(gè)任務(wù)的時(shí)間范圍區(qū)間

19、有重疊，而 并非指i，j的起點(diǎn)或終點(diǎn)重合。例如：區(qū)間1，4與區(qū)間2，4重疊，而與 4，7不重疊。一個(gè)可行的任務(wù)分配是指在分配中沒有兩件重疊的任務(wù)分配 給同一臺(tái)機(jī)器。因此，在可行的分配中每臺(tái)機(jī)器在任何時(shí)刻最多只處理一 個(gè)任務(wù)。最優(yōu)分配是指使用的機(jī)器最少的可行分配方案。問題實(shí)例：若任務(wù)占用的時(shí)間范圍是1，4，2，5，4，5，2，6，4，7，則按時(shí)完成所有任務(wù)最少需要幾臺(tái)機(jī)器？(提示：使用貪心 算法)畫出工作在對(duì)應(yīng)的機(jī)器上的分配情況。2.已知非齊次遞歸方程：f(n) fn ?g(n)，其中，b、c 是常數(shù),ng(n)是n的某一個(gè)函數(shù)。貝U f(n)的非遞歸表達(dá)式為：f (n) cbnbn '

20、g(i)i 1現(xiàn)有Hanoi塔問題的遞歸方程為：h(n) 2h(n 1) 1，求h(n)的非遞歸表 h(1) 1達(dá)式。解：禾U用給出的關(guān)系式，此時(shí)有：b=2, c=1, g(n)=1,從n遞推到1,有:n 1h(n) cbn 1 bn1 ig(i)i 12n1 2n 2 . 22 2 12n 13. 單源最短路徑的求解。問題的描述：給定帶權(quán)有向圖(如下圖所示)G =(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定 V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到所有 其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問題通常 稱為單源最短路徑問題解法：現(xiàn)采用Dijkstra 算法計(jì)算從源頂

21、點(diǎn)1到其它頂點(diǎn)間最短路徑。請(qǐng)將 此過程填入下表中。迭代Sudist2dist3dist4dist51-10max int30100初始12344. 請(qǐng)寫出用回溯法解裝載問題的函數(shù)。精品資料裝載問題：有一批共n個(gè)集裝箱要裝上2艘載重量分別為cl和c2的輪船,nWig C2其中集裝箱i的重量為wi，且i 1。裝載問題要求確定是否有一個(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 -= wi;if (cw +

22、wi <= c) /搜索左子樹xi = 1;cw += wi;backtrack (i + 1);cw -= wi;if (cw + r > bestw) xi = 0; /搜索右子樹backtrack (i + 1);r += wi;5. 用分支限界法解裝載問題時(shí)，對(duì)算法進(jìn)行了一些改進(jìn)，下面的程序段給出了 改進(jìn)部分；試說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的 方式，算法在執(zhí)行上有什么不同。/檢查左兒子結(jié)點(diǎn)if (wt <= c) /可行結(jié)點(diǎn)僅供學(xué)習(xí)與交流Typ有侵權(quán)請(qǐng)E網(wǎng)站刪除i謝謝15左兒子結(jié)點(diǎn)的重量if (wt > bestw) bestw = w

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

24、：給定2個(gè)序列X=x1,x2,xm和Y=y1,y2,yn ，找出X和丫的最長(zhǎng)公共子序列。由最長(zhǎng)公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中，Xi=x1,x2,xi ; Yj=y1,y2,yj。當(dāng) i=0 或 j=0 時(shí)，空序列是 Xi 和 Yj僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除 謝謝21精品資料的最長(zhǎng)公共子序列。故此時(shí)Cij=O。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建0i 0, j 0立遞歸關(guān)系如下：ci jci 1j 1 1i, jO;xiyjmaxcij 1,ci 1j i, j 0; Xiyj在程序中，bij 記錄Cij的

25、值是由哪一個(gè)子問題的解得到的。(1)請(qǐng)?zhí)顚懗绦蛑械目崭?，以使函?shù) LCSLe ngth完成計(jì)算最優(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;else if (ci-1j>=ci

26、j-1) cij=ci-1j; bij=2;else cij=cij-1; bij=3;(2)函數(shù)LCS實(shí)現(xiàn)根據(jù)b的內(nèi)容打印出Xi和Yj的最長(zhǎng)公共子序列。請(qǐng) 填寫程序中的空格，以使函數(shù) LCS完成構(gòu)造最長(zhǎng)公共子序列的功能 (請(qǐng)將bij的取值與(1)中您填寫的取值對(duì)應(yīng)，否則視為錯(cuò)誤)。void LCSint i，int j ，char *x，int *b)if (i =0 | j=0) retur n;if (bij= 1) 僅供學(xué)習(xí)與交流，如有CS青聯(lián)系網(wǎng)站刪除 謝謝17x，b);cout<<xi;精品資料僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除 謝謝278. 對(duì)下面的遞歸算法，寫出

27、調(diào)用f(4)的執(zhí)行結(jié)果void f(int k) if( k>0 ) prin tf("%dn ",k);f(k-1);f(k-1);一、填空題Ao分)1. 一個(gè)算法就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特殊類型問題的一系列運(yùn)算，此外，算法還應(yīng)具有以下五個(gè)重要特性:,。2. 算法的復(fù)雜性有 和 分，衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是03. 某一問題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征是4. 若序列 X=B,C,A,D,B,C,D，Y=A,C,B,A,B,D,C,D，請(qǐng)給出序列 X和 丫的一個(gè)最長(zhǎng)公共子序列o5. 用回溯法解問題時(shí)，應(yīng)明確定義問題的解空間，問題的解空間至少應(yīng)包

28、含6. 動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干 ，先求解然后從這些勺解得到原問題的解。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. 二分搜索算法是利用 現(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í)間分別為a和b，且1月2月詬4)=(4,5,12,10)，(b1,b 2,b3,b4)=(8,2,15,9) 求 4 個(gè)作業(yè)的最優(yōu)調(diào)度方案，并

29、計(jì)算最優(yōu)值。4. 使用回溯法解0/1背包問題：n=3, C=9, V=6,10,3 , W=3,4,4,其解空間 有長(zhǎng)度為3的0-1向量組成，要求用一棵完全二叉樹表示其解空間(從根出發(fā)，左1右0)，并畫出其解空間樹，計(jì)算其最優(yōu)值及最優(yōu)解。5. 設(shè)S= X, %, X是嚴(yán)格遞增的有序集，利用二叉樹的結(jié)點(diǎn)來存儲(chǔ) S中的元素，在表示S的二叉搜索樹中搜索一個(gè)元素 X,返回的結(jié)果有兩種情 形，(1)在二叉搜索樹的內(nèi)結(jié)點(diǎn)中找到 X=X，其概率為bi。( 2)在二叉搜索 樹的葉結(jié)點(diǎn)中確定X(X , X+1)，其概率為ai。在表示S的二叉搜索樹T中，設(shè)存儲(chǔ)元素X的結(jié)點(diǎn)深度為C ;葉結(jié)點(diǎn)(X , X+1)的結(jié)點(diǎn)

30、深度為di，則二 叉搜索樹T的平均路長(zhǎng)p為多少？假設(shè)二叉搜索樹Tij=X ,X+1, , X 最優(yōu)值為 mij, Wij= a “+&+ +b+a，貝Umij(1<=i<=j<=n)遞歸關(guān)系表達(dá)式為什么？6. 描述0-1背包問題。三、簡(jiǎn)答題(30分)1. 流水作業(yè)調(diào)度中，已知有n個(gè)作業(yè)，機(jī)器M1和M2上加工作業(yè)i所需的時(shí)間 分別為ai和bi，請(qǐng)寫出流水作業(yè)調(diào)度問題的johnson法則中對(duì)a和b的排序算 法。(函數(shù)名可寫為sort(s,n)2. 最優(yōu)二叉搜索樹問題的動(dòng)態(tài)規(guī)劃算法(設(shè)函數(shù)名 binarysearchtree) 答案：一、填空1 .確定性有窮性可行性0個(gè)或多

31、個(gè)輸入一個(gè)或多個(gè)輸出2. 時(shí)間復(fù)雜性空間復(fù)雜性時(shí)間復(fù)雜度高低3該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)4. BABCD或CABCD或CADCD5. 一個(gè)(最優(yōu))解6. 子問題 子問題 子問題7. 回溯法8. o(n*2 n) o(minnc,2 n)9. 最優(yōu)子結(jié)構(gòu)重疊子問題10. 動(dòng)態(tài)規(guī)劃法二、綜合題1. 問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；構(gòu)造最優(yōu)值的遞歸關(guān)系表達(dá)式；最優(yōu)值的算法描述；構(gòu)造最優(yōu)解；2. 令Ni=i|a i<b , N=i|a i>=b；將N中作業(yè)按a的非減序排序得到 N',將2中作業(yè)按bi的非增序排序得到MNi'中作業(yè)接N/中作業(yè) 就構(gòu)成了滿足Johnson法則的最優(yōu)調(diào)度。

32、3. 步驟為：N1= 1, 3 , N2=2, 4；Z' =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) 。解空間樹為：精品資料A10CB1010GDEF11100100OHJKLMN該問題的最優(yōu)值為：16最優(yōu)解為：(1, 1, 0)nn5. 二叉樹T的平均路長(zhǎng)P= bi * (1 Ci) + aj*dji 1j 0mij=Wij+mi nmik+mk+1j (1<=i<=j<=n, mii-1=0)mij=0 (i>

33、j)6. 已知一個(gè)背包的容量為C,有n件物品，物品i的重量為W,價(jià)值為V，求 應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大。三、簡(jiǎn)答題1.void sort(flowjope s,i nt n)int i,k,j,l;for(i=1;i<=n-1;i+) 選擇排序k=i;while(k<=n&&sk.tag!=O) k+;if(k>n) break;/-沒有 a，跳出elsefor(j=k+1;j<=n ;j+)if(sj.tag=0)if(sk.a>sj.a) k=j;swap(si.i ndex,sk.i ndex);swap(s

34、i.tag,sk.tag);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(sk.b<sj.b) k=j;swap(si.index,sk.index); /只移動(dòng) index 和 tagswap(si.tag,sk.tag);2.void bin arysearchtree(i nt a,i nt b,i nt n ,i nt *m,i nt *s,i nt *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-

35、1;l+)-1是下標(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)行問題的計(jì)算復(fù)雜性分析之前，首先必須建立求解問題所用的計(jì)算模型。3個(gè)基本計(jì)算模型是 、。3、 算法的復(fù)雜性是 的度量，是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。4、 計(jì)算機(jī)的資源最重要的是 和資源。因而，算法的復(fù)

36、雜性有和之分。5、f(n)= 6 x 2n+n2，f(n)的漸進(jìn)性態(tài) f(n)= 0( )&貪心算法總是做出在當(dāng)前看來的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的 07、許多可以用貪心算法求解的問題一般具有2個(gè)重要的性質(zhì)： 性質(zhì)和性質(zhì)。二、簡(jiǎn)答題(本題25分，每小題5分)1、簡(jiǎn)單描述分治法的基本思想。2、簡(jiǎn)述動(dòng)態(tài)規(guī)劃方法所運(yùn)用的最優(yōu)化原理。3、何謂最優(yōu)子結(jié)構(gòu)性質(zhì)？4、簡(jiǎn)單描述回溯法基本思想。5、何謂P、NR NPC'可題三、算法填空(本題20分，每小題5分)1、n后問題回溯算法(1)用二維數(shù)組ANN存儲(chǔ)皇后位置,若第i行第j列放有皇后,則Aij

37、為非0值,否則值為00分別用一維數(shù)組MN、L2*N-1、R2*N-1表示豎列、左斜線、右斜線是 否放有棋子，有則值為1,否則值為0ofor(j=0;j<N;j+)if( 1) /*安全檢查*/ Aij=i+1;/*放皇后 */2 ；if(i=N-1)輸出結(jié)果；else 3； ; /* 試探下一行 */4;/* 去皇后*/2、數(shù)塔問題。有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向 左走或是向右走，一起走到底層，要求找出一條路徑，使路徑上的值最大。for(r= n-2;r>=0;r-) /自底向上遞歸計(jì)算for(c=0; 1;c+)if( t葉 1c>t 葉 1c+1)

38、2else ；3、Hanoi 算法Han oi( n,a,b,c)if ( n=1)_J ；else _J ；Hanoi(n-1,b, a, c); 4、Dijkstra算法求單源最短路徑du:s到u的距離pu:記錄前一節(jié)點(diǎn)信息In it-s in gle-source(G,s)for each vertex v VG do dv= s; 1ds=0Relax(u,v,w)if dv>du+w(u,v)the n dv=du+wu,v;2dijkstra(G,w,s)1. In it-s in gle-source(G,s)2. S=3. Q=VG4. while Q<>do

39、 u=min(Q)S=S U u for each vertex 3 do 4四、算法理解題(本題10分) 根據(jù)優(yōu)先隊(duì)列式分支限界法， 求下圖中從v1點(diǎn)到v9點(diǎn)的單 源最短路徑，請(qǐng)畫出求得最優(yōu) 解的解空間樹。要求中間被舍 棄的結(jié)點(diǎn)用x標(biāo)記，獲得中間 解的結(jié)點(diǎn)用單圓圈?？蚱?，最 優(yōu)解用雙圓圈框起。五、算法理解題（本題5分）設(shè)有門=藝個(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=2，循環(huán)賽最少需要進(jìn)行幾天；（2）當(dāng)n=23=8時(shí)，請(qǐng)畫出循環(huán)賽日程表。六、算法設(shè)計(jì)題（本題1

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

41、Program Machine）;圖靈機(jī)（Turing Machine）3. 算法效率4.時(shí)間、空間、時(shí)間復(fù)雜度、空間復(fù)雜度5.2n6.最好局部最優(yōu)選擇7.貪心選擇最優(yōu)子結(jié)構(gòu)1、簡(jiǎn)答題（本題25分，每小題5分）6分治法的基本思想 是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問 題，這些子問題互相獨(dú)立且與原問題相同；對(duì)這 k個(gè)子問題分別求解。如 果子問題的規(guī)模仍然不夠小，則再劃分為 k個(gè)子問題，如此遞歸的進(jìn)行下 去，直到問題規(guī)模足夠小，很容易求出其解為止；將求出的小規(guī)模的問題 的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。7、“最優(yōu)化原理”用數(shù)學(xué)化的語言來描述：假設(shè)為了解決某一

42、優(yōu)化問題，需 要依次作出n個(gè)決策D1，D2,，Dn,如若這個(gè)決策序列是最優(yōu)的，對(duì)于 任何一個(gè)整數(shù)k，1 < k < n ，不論前面k個(gè)決策是怎樣的，以后的最優(yōu)決僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝31精品資料策只取決于由前面決策所確定的當(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í)，貝U判斷該結(jié) 點(diǎn)為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的解，貝U放棄對(duì)

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

44、Li+j&&!Ri-j+N Mj=Li+j=Ri-j+N=1;(3) try(i+1,M,L,R,A) Aij=0(5) Mj=Li+j=Ri-j+N=02、數(shù)塔問題。(1) c<=r trc+=tr+1c(3) trc+=tr+1c+13、Hanoi 算法(1) move(a,c)(2) Hanoi(n-1, a, c , b)(3) Move(a,c)4、( 1) pv=NIL(2) pv=u(3) v adju(4) Relax(u,v,w)五、(1) 8天(2分)；(2)當(dāng)n=23=8時(shí)，循環(huán)賽日程表(3分)六、算法設(shè)計(jì)題(本題15分)(1)貪心算法 O (nlog (n)?首先計(jì)算每種物品單位重量的價(jià)值1 2 3 45 6 7 82 1 4 36 5 8 73 4 1 27 8 5 64 3 2 18 7 6 55 6 7 81 2 3 46 5 8 72 1 4 37 8 5 63 4 1 28 7 6