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

2、nt n, int A, int B, int C) (if(n >0)(hanoi(n-l, A, C, B);move (n,a,b);hanoi(n-l, C, B, A);)C void hanoi(int n, int C, int B, int A) (if(n >0)(hanoi(n-l, A, C, B);move (n,a,b);hanoi(n-l, C, B, A);)D- void hanoi(int n, int C, int A, int B)if(n >0)(hanoi(n-l, A, C, B);move(n,a,b);hanoi(n-l, C,

3、 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 .算法分析中，記號(hào)。表示(B),記號(hào)球示(A),記號(hào)O表示(D) oA.漸進(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) =0(h(n) = f (n) =O(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.

4、f(n) =O(g(n) 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 ）是回溯法中遍歷排列樹的算法框架程序。A.void backtrack (int t)(if (

5、t>n) output(x);elsefor (int i=t;i<=n;i+) swap(xt, xi);if (legal(t) backtrack(t+l);swap(xt, xi);) void backtrack (int t)(if (t>n) output(x);elsefor (int i=0;i<=l ;i+) xt=i;if (legal(t) backtrack(t+l);)C.)void backtrack (int t)(if (t>n) output(x);elsefor (int i=0;i<=l ;i+) xt=i;if (l

6、egal(t) backtrack(t-l);)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-f-l);)10 .回溯法的效率不依賴于以下哪一個(gè)因素？ （ C ）A.產(chǎn)生xk的時(shí)間；B.滿足顯約束的xk值的個(gè)數(shù)；C.問題的解空間的形式；D.計(jì)算上界函數(shù)bound的時(shí)間；E.滿足約束函數(shù)和上界函數(shù)約束的所有xk的個(gè)數(shù)。F.計(jì)算約束函數(shù)constraint的時(shí)間;11 .常見的兩種分支限界法為（D）A.廣度優(yōu)先分支限界

7、法與深度優(yōu)先分支限界法；B.隊(duì)列式（FIFO）分支限界法與堆棧式分支限界法；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類語(yǔ)言在圖靈機(jī)下的定義為(D)NDTM所接受的語(yǔ)A. NP = UL是一個(gè)能在非多項(xiàng)式時(shí)

8、間內(nèi)被一臺(tái)言)；NDTM所接受的語(yǔ)言)；DTM所接受的語(yǔ)言；NDTM所接受的語(yǔ)言)；B. NP = LIL是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)C. NP = LIL是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)D. NP = LIL是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)14 .記號(hào)O的定義正確的是(A )。A. O(g(n) = f(n)l 存在正常數(shù)c和nO使得對(duì)所有n之n有：標(biāo)f(n)工 0cg(n) ;> < <B. O(g(n) = f(n) I存在正常數(shù)c和nO使得對(duì)所有n no有：0 cg(n)f(n) ;>C. O(g(n) = f(n) I對(duì)于任何正常數(shù)c>0,存在正數(shù)和no >

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

10、0,存在正數(shù)和n0>0使得對(duì)所有n no有：0 f(n)<cg(n) ；D. (g(n) = f(n)|對(duì)于任何正常數(shù)“，存在正數(shù)和n>。使得對(duì)所有nn00<有：0 cg(n) < f(n) ；二、填空題1 .下面程序段的所需要的計(jì)算時(shí)間為( O(n ) oint MaxSum(int n, int *a, int &besti, int &bestj) | int sum=O;for(int i=l ；i<=n;i+) int thissum=O;for(intj=i;j<=n;j+) thissum+=aj;if(thissum&g

11、t;sum) sum=thissum; besti=i; bestj=j; ) ) re turn sum;2 .有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） o11234567891011Si130535688212fi45678910111213143 .所謂貪心選擇性質(zhì)是指（所求問題的整體最優(yōu)解可以通過一系列局部最 優(yōu)的選擇，即貪心選擇來達(dá)到）。4 .所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指（問題的最優(yōu)解包含了其子問題的最優(yōu)解

12、）。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)的最長(zhǎng)路徑的長(zhǎng)度為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í)，計(jì)算結(jié)點(diǎn)的上界的函數(shù)如下所示，請(qǐng)?jiān)诳崭裰?填入合適的

13、內(nèi)容：Typep KnapvTypew, Typep>: Bound(int 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+；)/裝滿背包if (i <= n)(b += pi/wi * cleft);re turn b;11 .用回溯法解布線問題時(shí)，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為n'm的方格陣列，擴(kuò)展每個(gè)結(jié)點(diǎn)需0(1)的時(shí)間，L為最短

14、布線路徑的長(zhǎng)度，則算 法共耗時(shí)(O(mn),構(gòu)造相應(yīng)的最短距離需要(O(L)時(shí)間。for (int i = 0; i < NumOtNbrs; i+) nbr.row = he re.row + offs eti.row;nbr.col = here.col + offseti.col;if (gridnbr.rownbr.col = 0) /該方格未標(biāo)記gridnbr.rownbr.col=grid here.rowhere .col + 1;if (nbr.row = finish.row) &&(nbr.col = finish.col) break; / 完成布線

15、 Q.Add(nbr);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(akj= =l)&&(xj= =xk) return false; re tu rn tru e;)13 .旅行售貨員問題的解空間樹是（排列樹）。三、 證明題1. 一個(gè)分治法將規(guī)模為n的問題分成k個(gè)規(guī)模為n/ m的子問題去解。設(shè)分 解閥值nO=l,且adhoc解規(guī)模為1的問題耗費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問題 分解為

16、k個(gè)子問題以及用merge將k個(gè)子問題的解合并為原問題的解需用f(n) 個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為IPI=n的問題所需的計(jì)算時(shí)間，f 0(1) n = 1則有：T(n)J<T( n / m)+ f (n) n > 1log m n_ 1 log k通過迭代法求得T (n)的顯式表達(dá)式為：T(n)=n m + kjf(n/mj)手。試證明T ( n)的顯式表達(dá)式的正確性。i i的非遞減次序考慮選擇的2 .舉反例證明0/1背包問題若使用的算法是按照 p /w物品，即只要正在被考慮的物品裝得進(jìn)就裝入背包，則此方法不一定能得到最優(yōu) 解(此題說明0/1背包問題與背包問題的不同

17、)。證明：舉例如：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)+O(g(n) = O(maxf(n),g(n) o證明：對(duì)于任意口5)亡O(f(n),存在正常數(shù)cl和自然數(shù)nl,使得對(duì)所有n>nl, 有 fl(n) < clf(n)。類似地，對(duì)于任意gl(n) e O(g(n),存在正常數(shù)c2和自然數(shù)n2,使得對(duì) 所有 n*n2,有 gl(n) <c2g(n) o令 c3=maxcl, c2 ,n3 =maxnl, n2 , h(n)= maxf

18、(n),g(n) 。則對(duì)所有的nn3,有fl(n) +gl(n) < clf(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)裝載問題具有貪心選擇性質(zhì)。最優(yōu)裝載問題：有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi0最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。設(shè)集裝箱已依其重量從小到大排序， (X 2,X n)是最優(yōu)裝載問題的一個(gè)最優(yōu)解。又設(shè)k =mjnilxi = l o如果給定的最優(yōu)裝載問

19、題有解，則有1 " kWn。)證明：四、 解答題1 .機(jī)器調(diào)度問題。問題描述：現(xiàn)在有n件任務(wù)和無限多臺(tái)的機(jī)器，任務(wù)可以在機(jī)器上得到處理。每件任務(wù)的開始時(shí)間為Si ,完成時(shí)間為fi , SiVfi。為處理任務(wù)i的 時(shí)間范圍。兩個(gè)任務(wù)i ,j重疊指兩個(gè)任務(wù)的時(shí)間范圍區(qū)間有重疊，而并非指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 ,

20、2 , 5 , 4 , 5 , 2 , 6, 4 , 7,則按時(shí)完成所有任務(wù)最少需要幾臺(tái)機(jī)器？(提示：使用貪心算法)畫出工作在對(duì)應(yīng)的機(jī)器上的分配情況。f(n) =bf(n -l) + g(n)2 .已知非齊次遞歸方程：、=，其中，b、c是常數(shù),1f(0) - cng(n)是n的某一個(gè)函數(shù)。貝U f(n)的非遞歸表達(dá)式為：f(n)=cbiJZ bn(i) 0百現(xiàn)有Hanoi塔問題的遞歸方程為:，求h(n)的非遞歸表h(l)= 1達(dá)式。解：利用給出的關(guān)系式，此時(shí)有：b=2, c=l,g(n)=l,從n遞推至1,有:n_lh(n) = ct/i+Z b-1 g(i) t=l= 2n7+ 2>+

21、 -22+ 2+l= 2n- 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ì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑。請(qǐng)將此過程填入下表中。迭代SUdist2dist3dist4dist5初始110maxint3010012_344 .請(qǐng)寫出用回溯法解裝載問題的函數(shù)。裝載問題：有一批共n個(gè)集裝箱要裝上2艘載重量分別為cl和c2的輪船，nWi Cl C2

22、Z «+其中集裝箱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 -= wi;if (cw + wi <= c) / 搜索左子樹xi = 1 ； cw + = wi; backtrack (i + 1);cw -= wi;if (cw + r > bestw) xi = 0; /搜索右子樹backtrack (i 4- 1);r += w

23、i;5 .用分支限界法解裝載問題時(shí)，對(duì)算法進(jìn)行了一些改進(jìn)，下面的程序段給出了改進(jìn)部分；試說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方 式，算法在執(zhí)行上有什么不同。/檢查左兒子結(jié)點(diǎn)Type wt = Ew + wi; /左兒子結(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)解答：斜線

24、標(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 o又知算法最終找到的 最優(yōu)值是所求問題的子集樹中所有可行結(jié)點(diǎn)相應(yīng)重量的最大值。而結(jié)點(diǎn)所相應(yīng)得重量?jī)H在搜索進(jìn)入左子樹是增加，因此，可以在算法每一次進(jìn)入左子樹時(shí)更新 bestw的值。7.最長(zhǎng)公共子序列問題：

25、給定2個(gè)序列X=xl,x2, '",xm）和Y=yl,y2,yn , 找出X和Y的最長(zhǎng)公共子序列。由最長(zhǎng)公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。 用ciQ記錄序列Xi和與的最長(zhǎng)公共子序列的長(zhǎng)度。其中，Xi=xl,x2,xi ； Yj=yl,y2,yj。當(dāng) i=0 或 j=0 時(shí)，空序列是 Xi 和 Yj 的最長(zhǎng)公共子序列。故此時(shí)Cij=O o其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立 0i=0,j=0遞歸關(guān)系如下：cj = ' ci-ij -1+1i,j >0;xi = yjLmaxcij -1, ci -lj i, j >0; Xi yj在程序

26、中，bij 記錄的值是由哪一個(gè)子問題的解得到的。LCSLe曄th完成計(jì)算最優(yōu)值的功能。void LCSLength(int m , int n , char *x , char *y , int *c, int *%)(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) ciUJ=ci-lj-l+l;biU=l;else if( ci-lU>=cij-l) c

27、i0=ci-lj;bij=2;else cij=cig-l;biU=3;（2）函數(shù)LCS實(shí)現(xiàn)根據(jù)b的內(nèi)容打印出Xi和Yj的最長(zhǎng)公共子序列。請(qǐng)?zhí)顚?程序中的空格，以使函數(shù)LCS完成構(gòu)造最長(zhǎng)公共子序列的功能（請(qǐng)將 的取值與（1）中您填寫的取值對(duì)應(yīng)，否則視為錯(cuò)誤）。void LCS(int i , int j , char *x , int *十) (if (i =0 II j=0) re turn;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

28、 , x, b);8.對(duì)下面的遞歸算法，寫出調(diào)用f（4）的執(zhí)行結(jié)果。void Rint k) if( k>0 )printf(n%dn ；k);一、填空題)(20 分)1 . 一個(gè)算法就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特殊類型問題的 一系列運(yùn)算，此外，算法還應(yīng)具有以下五個(gè)重要特性:,O2 .算法的復(fù)雜性有 和 之分，衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是 O3 .某一問題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征是4 .若序列 X=B,C,AD,B,C,D , Y=A,C,B,A,B,D,C,D,請(qǐng)給出序列 X 和 Y 的一個(gè)最長(zhǎng)公共子序列j5 .用回溯法解問題時(shí)，應(yīng)明確定義問題的解空間，問題的解空

29、間至少應(yīng)包含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è)基本要素是 和 o10 .二分搜索算法是利用 實(shí)現(xiàn)的算法。二、綜合題(50分)1 .寫出設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟。2 .流水作業(yè)調(diào)度問題的johnson算法的思想。3 .若n=4,在機(jī)器Ml和M2上加工作業(yè)i所需的時(shí)間分別為at和bi ,且(a i,a 2 ,a3,a 4)=(4,5,12,10) , (b i,b 2,b 3,b 4

30、)=(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,其解空間有長(zhǎng) 度為3的0-1向量組成，要求用一棵完全二叉樹表示其解空間(從根出發(fā)，左 1右0),并畫出其解空間樹，計(jì)算其最優(yōu)值及最優(yōu)解。5 .設(shè)S=X, X2, , XJ是嚴(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+i),其概率為ai。在表示S的二叉搜

31、索樹T中，設(shè)存儲(chǔ)元素X的 結(jié)點(diǎn)深度為Ci；葉結(jié)點(diǎn)(X, X+i )的結(jié)點(diǎn)深度為4,則二叉搜索樹T的平均路長(zhǎng)p 為多少？假設(shè)二叉搜索樹X, X+一 ，、最優(yōu)值為可口用，an +b.+ +bj +aj ,則mi皿(lv=i<=j<=n)遞歸關(guān)系表達(dá)式為什么? Wij=6 .描述0-1背包問題。三、簡(jiǎn)答題(30分)1 .流水作業(yè)調(diào)度中，已知有n個(gè)作業(yè)，機(jī)器Ml和M2上加工作業(yè)i所需的時(shí)間分 別為1和bi,請(qǐng)寫出流水作業(yè)調(diào)度問題的johnson法則中對(duì)ai和b的排序算法。(函數(shù)名可寫為sort(s,n)2 .最優(yōu)二叉搜索樹問題的動(dòng)態(tài)規(guī)劃算法(設(shè)函數(shù)名binarysearchtree)答案：

32、一、填空1 .確定性 有窮性 可行性0個(gè)或多個(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=ila i <bi , N2=ila i>=bi ；將Ni中作業(yè)按ai的非減序排序得到NJ , 將N?中作業(yè)按b的非增序排序得到NJ ；NJ中作業(yè)

33、接NJ中作業(yè)就構(gòu)成了 滿足Johnson法則的最優(yōu)調(diào)度。3 .步驟為：N1 = 1, 3 , N2=2, 4；NJ =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 的平均路長(zhǎng) P= £ bi*(lti)+ Z aj*djiUj=0m ij=Wij+min m ik+m k+1 j (1 <=i<=j<=n,m ii-1 =0)m

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

35、k.index);swap(si.tag,sk.tag);li；/-記下當(dāng)前第一個(gè)b的卜標(biāo)ifor(i=l;i<=n-l ;i+)(k=i;for(j=k+l ;j<=n;j+)if(sk.b<s Q.b) k=j;swap(si.index,sk.index); / 只移動(dòng) index 和 tagswap(s i.tag,sk.tag);) ) 2.void binarysearchtree(int a,int b,int n,int *n,int *s,int *v) intfor(i= 1 ;i<=n+1 ;i+) (wii-l=ai-l;mii-l=0;)for

36、(l=0;l<=n-l;14-+)/-l是下標(biāo) j-i 的差for(i=l ;i<=n-l;i+)( j=i+l; wij=wij-l+a|j+b|j;m ij=m ii-1 +m i+1 g+wij；s ij=i； for(k=i+l ;k<=j;k+)(t=mik-l+mk+ljH-wiU；一、 填空題(本題15分，每小題1分)1、算法就是一組有窮的 ，它們規(guī)定了解決某一特定類型問題的 O2、在進(jìn)行問題的計(jì)算復(fù)雜性分析之前，首先必須建立求解問題所用的計(jì)算模 型。3個(gè)基本計(jì)算模型是 o3、算法的復(fù)雜性是 的度量，是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。4、計(jì)算機(jī)的資源最重要的是 和 資源

37、。因而，算法的復(fù)雜性有和之分。n25、f(n)= 6 X2+n , f(n)的漸進(jìn)性態(tài) f(n)= 0( )6、貪心算法總是做出在當(dāng)前看來 的選擇。也就是說貪心算法并不從整 體最優(yōu)考慮，它所做出的選擇只是在某種意義上的 o7、許多可以用貪心算法求解的問題一般具有2個(gè)重要的性質(zhì)：性質(zhì)和性質(zhì)o二、簡(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、NP、NPC問題三、算法填空(本題20分，每小題5分)1、n后問題回溯算法(1)用二維數(shù)組ANN存儲(chǔ)皇后位置，若第i行第j列放有皇

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

39、;tr4-lc+l)2 else 3 ；3、Hanoi 算法Hanoi(n,a,b,c)if ( n=l)1；else 2;3；Hanoi(n-l,b, a, c);)4、Dijkstra 算法求單源最短路徑du:s到u的距離pu: 記錄前一節(jié)點(diǎn)信息In it-s ingle-source(G,s) for each vertex v e VGJdo dv=0° 1ds=0Relax(u,v,w) if d v>d u +w(u,v) then dv=du+wu,v;2) dijks tra(G,w,s)1. Init-single-source(G,s)2. S=3. Q=V

40、G4. while Q<> do u=min（Q）S=S Uufor each vertex 3do 4現(xiàn)設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表:四、算法理解題（本題1。分） 根據(jù)優(yōu)先隊(duì)列式分支限界法，求 下圖中從vl點(diǎn)到v9點(diǎn)的單源最 短路徑，請(qǐng)畫出求得最優(yōu)解的解 空間樹。要求中間被舍棄的結(jié)點(diǎn) 用義標(biāo)記，獲得中間解的結(jié)點(diǎn)用 單圓圈O框起，最優(yōu)解用雙圓圈 框起。五、算法理解題（本題5分） 設(shè)有n=2、個(gè)運(yùn)動(dòng)員要進(jìn)行循環(huán)賽,每個(gè)選手必須與其他n-1名選手比賽各一次;每個(gè)選手一天至多只能賽一次；（1）如果n=2j循環(huán)賽最少需要進(jìn)行幾天；（2）當(dāng)n=23=8時(shí)，請(qǐng)畫出循環(huán)賽日程表。六、算法設(shè)計(jì)

41、題（本題15分）分別用貪心算法、動(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（RandomAccess Machine）； 隨機(jī)存取存儲(chǔ)程序 機(jī) RASP（Random Access S

42、tored Program Machine）；圖靈機(jī)（Turing Machine）3. 算法效率4. 時(shí)間、空間、時(shí)間復(fù)雜度、空間復(fù)雜度5. 2n7.貪心選擇 最優(yōu)子結(jié)構(gòu) 二、簡(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é)化的語(yǔ)言來描述：假設(shè)為了解決某一優(yōu)化

43、問題，需 要依次作出n個(gè)決策DI , D2 ,Dn ,如若這個(gè)決策序列是最優(yōu)的，對(duì)于 任何一個(gè)整數(shù)k , 1 <k<n ,不論前面k個(gè)決策是怎樣的，以后的最優(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)為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的解，則放棄對(duì)該子樹的搜索，退回到上層父結(jié)點(diǎn)，繼續(xù)下一步深度優(yōu)先

44、搜索過 程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài)空間樹，再進(jìn)行搜索，而是在 搜索過程，逐步構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造。10、P（Polynomial問題）：也即是多項(xiàng)式復(fù)雜程度的問題。NP就是Non-deteiTninistic Polynomial的問題，也即是多項(xiàng)式復(fù)雜程度 的非確定性問題。NPC（NP Complete）問題，這種問題只有把解域里面的所有可能都窮舉了之后才能得出答案，這樣的問題是NP里面最難的問題，這種問題就是NPC問題。三、算法填空（本題20分，每小題5分） 1、n后問題回溯算法(1) !Mj&&!Li4-j&&!R i-j+N(2

45、) MU=Li+j=Ri-j+N=l;(3) try(i+l,M,L,R,A)(4) Aij=O(5) Mj=Li+j=Ri-j+N=O2、數(shù)塔問題。(1 ) c<=r(2)trc+=tr+lc(3 ) trc+=tr+lc+l3、Hanoi 算法(1 ) move(a,c)(2 ) Hanoi(n-1, a, c , b)(3 ) Move (a,c)4、(1) pv=NDL(2 ) pv=u(3) v e adju(4) Relax(u,v,w)123,214：341：4325678658778568765567；658'785(876：；12342143)34124321四、算法理解題(本題1。分)五、(1) 8天(2分)；(2)當(dāng)n=23 =8時(shí)，循環(huán)賽日程表(3分)。六、算法設(shè)計(jì)題(本題15分)(1 )貪心算法 O ( nlog ( n)首先計(jì)算每種物品單位重量