




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 張掖中考試題及答案
- 物業(yè)完整試題及答案
- 淘寶客服溝通培訓(xùn)
- 路基施工(路基排水施工)
- 經(jīng)驗(yàn)交流活動(dòng)策劃與實(shí)施
- 溫控設(shè)備管理員工培訓(xùn)
- 2025年中國(guó)母嬰用品行業(yè)市場(chǎng)全景分析及前景機(jī)遇研判報(bào)告
- 2025生物課標(biāo)培訓(xùn)
- 針灸出科門診病例分析專題報(bào)告
- 籃球教學(xué)工作總結(jié)
- 目標(biāo)探測(cè)與識(shí)別知到智慧樹章節(jié)測(cè)試課后答案2024年秋北京航空航天大學(xué)
- 安全附件管理培訓(xùn)
- 寫字樓保安培訓(xùn)資料
- 市政道路施工方案投標(biāo)文件(技術(shù)方案)
- 08SS523建筑小區(qū)塑料排水檢查井
- 瑞得RTS-820系列全站儀說明書(適用RTS-822.822A.822L.822R.822R .822R3)
- 學(xué)生干部培訓(xùn)2024年學(xué)生干部培訓(xùn)方案
- 天津市西青區(qū)2023-2024學(xué)年八年級(jí)下學(xué)期期末歷史試卷(解析版)
- -投標(biāo)技術(shù)標(biāo)書范文模板-人員配備與團(tuán)隊(duì)構(gòu)建
- (正式版)YS∕T 5040-2024 有色金屬礦山工程項(xiàng)目可行性研究報(bào)告編制標(biāo)準(zhǔn)
- 貸款合同模板銀行版
評(píng)論
0/150
提交評(píng)論