(完整word版)《算法設(shè)計(jì)與分析》考試題目及答案

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

2、A)if (n 0)void hanoi (intn, intC, intA, intB)if (n 0)3。動(dòng)態(tài)規(guī)劃算法的基本要素為(C)最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)重疊子問(wèn)題性質(zhì)與貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問(wèn)題性質(zhì)預(yù)排序與遞歸調(diào)用記號(hào)0表示(D)。4。算法分析中，記號(hào)O表示(B),記號(hào)Q表示(A),A。漸進(jìn)下界B。漸進(jìn)上界C。非緊上界D。緊漸進(jìn)界E。非緊下界5。以下關(guān)于漸進(jìn)記號(hào)的性質(zhì)是正確的有：(A)A。f (n)二 0(g(n),g(n)二 0(h(n) n f (n)二 0(h(n)B。f(n)二 O(g(n),g(n)二 O(h(n) n h(n)二 O(f(n)Co O(f

3、 ( n) +O(g(n ) = O(minf(n) ,g(n )D。 f (n)二 O(g(n) o g(n)二 O(f (n)6o能采用貪心算法求最優(yōu)解的問(wèn)題，一般具有的重要性質(zhì)為：(A)最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)重疊子問(wèn)題性質(zhì)與貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問(wèn)題性質(zhì)預(yù)排序與遞歸調(diào)用回溯法在問(wèn)題的解空間樹(shù)中，按（D）策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù).廣度優(yōu)先B?；罱Y(jié)點(diǎn)優(yōu)先C.擴(kuò)展結(jié)點(diǎn)優(yōu)先D.深度優(yōu)先8 分支限界法在問(wèn)題的解空間樹(shù)中，按（A）策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。A 廣度優(yōu)先B.活結(jié)點(diǎn)優(yōu)先C.擴(kuò)展結(jié)點(diǎn)優(yōu)先D。深度優(yōu)先A.B。程序塊（A ）是回溯法中遍歷排列樹(shù)的算法框架程序.vo

4、id back track ( int t)if (tn) output (x);elsefor (int i=t;i二n;i+) void backtrack (int t)if (tn) output(x );elsefor (int i=0;i = 1 ; i+) C。void backtrack (int t)D.void back track (int t )if (tn) output(x);elsefor (int i=t ; i二n;i + + ) 回溯法的效率不依賴(lài)于以下哪一個(gè)因素？ ( C )產(chǎn)生x k的時(shí)間；滿足顯約束的刈k值的個(gè)數(shù)；c.問(wèn)題的解空間的形式；計(jì)算上界函數(shù)b

5、ound的時(shí)間；滿足約束函數(shù)和上界函數(shù)約束的所有xk 的個(gè)數(shù)。計(jì)算約束函數(shù)constraint的時(shí)間；常見(jiàn)的兩種分支限界法為( D )A。廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B。隊(duì)列式(FIFO )分支限界法與堆棧式分支限界法；C。排列樹(shù)法與子集樹(shù)法；D。隊(duì)列式( FIFO )分支限界法與優(yōu)先隊(duì)列式分支限界法；12。k帶圖靈機(jī)的空間復(fù)雜性S(n)是指(B)A. k帶圖靈機(jī)處理所有長(zhǎng)度為n的輸入時(shí)，在某條帶上所使用過(guò)的最大方格數(shù)。b. k帶圖靈機(jī)處理所有長(zhǎng)度為n的輸入時(shí)，在k條帶上所使用過(guò)的方格數(shù)的總和。k帶圖靈機(jī)處理所有長(zhǎng)度為n的輸入時(shí)，在k條帶上所使用過(guò)的平均方格數(shù)。d. k帶圖靈機(jī)處理

6、所有長(zhǎng)度為n的輸入時(shí)，在某條帶上所使用過(guò)的最小方格數(shù)。NP類(lèi)語(yǔ)言在圖靈機(jī)下的定義為(D)NP=L|L是一個(gè)能在非多項(xiàng)式時(shí)間內(nèi)被一臺(tái)NDTM所接受的語(yǔ)言;NP=L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)NDTM所接受的語(yǔ)言;NP=L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)DTM所接受的語(yǔ)言;NP=L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)NDTM所接受的語(yǔ)言；記號(hào)O的定義正確的是(A )O(g(n) = f(n) | 存在正常數(shù) c 和 nO 使得對(duì)所有 n n。有：0 f(n) n。有：。 cg(n) 0,存在正數(shù)和n00使得對(duì)所有n n0有：0 0,存在正數(shù)和n 使得對(duì)所有nn有： 0 cg(n) n。有：。 f(

7、n) n。有：0 cg(n) 0,存在正數(shù)和n 0使得對(duì)所有n n有：0 f (n)0,存在正數(shù)和n0使得對(duì)所有n n有： 0 cg(n) f(n) ;二、 填空題下面程序段的所需要的計(jì)算時(shí)間為(O(n2).int MaxSum(int n, int 火a, int &besti, int&bestj)int sum=0；for (int i=l;i 二n;i+)int thissum=0；for(int j二i； j二n;j+)thissum+=a j;有 11 個(gè)待安排的活動(dòng)，它們具有下表所示的開(kāi)始時(shí)間與結(jié)束時(shí)間,如果以貪心算法求解這 些活動(dòng)的最優(yōu)安排（即為活動(dòng)安排問(wèn)題：在所給的活動(dòng)集合中

8、選出最大的相容活動(dòng)子集 合）,得到的最大相容活動(dòng)子集合為活動(dòng)（1,4, & 11 ）。i1234567891011Si130535688212fi4567891011121314所謂貪心選擇性質(zhì)是指（所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪 心選擇來(lái)達(dá)到）。所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指（問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解）?；厮莘ㄊ侵福ň哂邢藿绾瘮?shù)的深度優(yōu)先生成法）。用回溯法解題的一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間。在任何時(shí)刻 ,算法 只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹(shù) 中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路 徑的長(zhǎng)度為 h （ n ） ,則回溯法所需的計(jì)算空間通常為（

9、O（h（n ） ） ）。回溯法的算法框架按照問(wèn)題的解空間一般分為（子集樹(shù)）算法框架與（排列樹(shù)）算法框架.用回溯法解 0/1 背包問(wèn)題時(shí),該問(wèn)題的解空間結(jié)構(gòu)為（子集樹(shù)）結(jié)構(gòu).用回溯法解批處理作業(yè)調(diào)度問(wèn)題時(shí),該問(wèn)題的解空間結(jié)構(gòu)為（排列樹(shù)）結(jié)構(gòu)。用回溯法解0/1 背包問(wèn)題時(shí),計(jì)算結(jié)點(diǎn)的上界的函數(shù)如下所示,請(qǐng)?jiān)诳崭裰刑钊牒线m的 內(nèi)容：Typep KnapTypew, Typep： Bound(int i)/計(jì)算上界Typew cleft = c 一 cw; / 剩余容量Typep b = cp；/結(jié)點(diǎn)的上界/以物品單位重量?jī)r(jià)值遞減序裝入物品 while (i 二 n & w i二 cleft) cle

10、ft = w i;11用回溯法解布線問(wèn)題時(shí)，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為n m的方格陣 列，擴(kuò)展每個(gè)結(jié)點(diǎn)需O (1)的時(shí)間丄為最短布線路徑的長(zhǎng)度，則算法共耗時(shí)(O(mn)， 構(gòu)造相應(yīng)的最短距離需要(O(L)時(shí)間。for (int i 二 0; i NumOfNbrs； i+)nbr.row = here.row + offset i。row;nbr。 col = here。 col + offset i。 col;if (grid nbr。 row nbr。 col = 0)/該方格未標(biāo)記gridnbr.row nbr。 col=gridhere.row here。 col +

11、 1;if ( (nbr。row = finish.row) &(nbr.col = finish。col) break; / 完成布線Q.Add (nbr) ； 12。用回溯法解圖的m著色問(wèn)題時(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 1merge將k個(gè)子問(wèn)題的解合并為原問(wèn)題的解需用f (n)個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為|P|二n的問(wèn)題所需的計(jì)算時(shí)間,則有：t(n)=通過(guò)迭代法求得T(n )的顯式表達(dá)式為:T (n) =nlogmk +

12、乞 kjf (n / mj)j=0試證明T (n)的顯式表達(dá)式的正確性。2。舉反例證明0/1背包問(wèn)題若使用的算法是按照Pj/Wj的非遞減次序考慮選擇的物品,即只要 正在被考慮的物品裝得進(jìn)就裝入背包，則此方法不一定能得到最優(yōu)解(此題說(shuō)明 0/1 背包問(wèn)題 與背包問(wèn)題的不同)。證明：舉例如:p= 7,4,4 ,w=3 , 2 , 2,c=4時(shí)，由于7/3最大，若按題目要求的方法,只能取 第一個(gè),收益是7。而此實(shí)例的最大的收益應(yīng)該是8，取第2，3 個(gè)。求證:O(f(n) )+O(g(n ) = O ( max f(n),g ( n)。證明：對(duì)于任意f1(n) e O(f(n)，存在正常數(shù)c1和自然數(shù)

13、n1,使得對(duì)所有n n1,有f1(n) n2, 有 g1(n) n3 ,有fl ( 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) .求證最優(yōu)裝載問(wèn)題具有貪心選擇性質(zhì).(最優(yōu)裝載問(wèn)題：有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi. 最優(yōu)裝載問(wèn)題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。 設(shè)集 裝箱已依其重量從小到大排序，(X, x2,., xn )是最優(yōu)裝載問(wèn)題的一個(gè)最優(yōu)解。又設(shè) k = m

14、ini I x = 1。 如果給定的最優(yōu)裝載問(wèn)題有解，則有1 k n。)1in證明:四、 解答題機(jī)器調(diào)度問(wèn)題。問(wèn)題描述：現(xiàn)在有 n 件任務(wù)和無(wú)限多臺(tái)的機(jī)器，任務(wù)可以在機(jī)器上得到處理.每件任務(wù) 的開(kāi)始時(shí)間為si，完成時(shí)間為fi, sifj .si,fi為處理任務(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ù)分配是指在分配中沒(méi)有兩件重疊的 任務(wù)分配給同一臺(tái)機(jī)器.因此,在可行的分配中每臺(tái)機(jī)器在任何時(shí)刻最多只處理一個(gè)任務(wù)。最 優(yōu)分配是指使用的機(jī)器最少的可行分配方案。(完整word版

15、)算法設(shè)計(jì)與分析考試題目及答案問(wèn)題實(shí)例：若任務(wù)占用的時(shí)間范圍是 1,4,2,5,4,5, 2,6, 4,7,則按時(shí)完成所有任務(wù)最少需要幾臺(tái)機(jī)器？(提示：使用貪心算法) 畫(huà)出工作在對(duì)應(yīng)的機(jī)器上的分配情況。已知非齊次遞歸方程：Jf(n)= bf(n-1)+如)，其中，b、c是常數(shù),g (n)是n的某一個(gè) I f(0)= c函數(shù)。則f(n)的非遞歸表達(dá)式為：f(n) = cbn+ bn-ig(i).i=1現(xiàn)有Hanoi塔問(wèn)題的遞歸方程為：p(n)= 2h(n -D+1，求h(n)的非遞歸表達(dá)式.h(1)=1解利用給出的關(guān)系式，此時(shí)有：b=2, c=1 , g(n) = 1 ,從n遞推到1,有：h(n

16、) = cbn-1 + 駅 bn-1-i g(i)i=1=2n-1 + 2n -2 + + 22 + 2 +1=2n 1單源最短路徑的求解。問(wèn)題的描述：給定帶權(quán)有向圖(如下圖所示)G =(V , E),其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另 外，還給定V中的一個(gè)頂點(diǎn)，稱(chēng)為源?，F(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里 路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱(chēng)為單源最短路徑問(wèn)題。解法：現(xiàn)采用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑。請(qǐng)將此過(guò)程填入下表 中.迭代Sudist2dist3dist4dist5初始110maxint301001234請(qǐng)寫(xiě)出用回溯法解裝載問(wèn)題的函數(shù).裝載問(wèn)題：

17、有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的n乙 w n) / 到達(dá)葉結(jié)點(diǎn)更新最優(yōu)解 bestx，bestw;return;r -= wi；if (cw + wi = c) / 搜索左子樹(shù) xi = 1;cw += wi;backtrack(i + 1);cw -= wi ;if (cw + r bestw) xi = 0；/ 搜索右子樹(shù)backtrack(i + 1);r += wi;5。用分支限界法解裝載問(wèn)題時(shí)，對(duì)算法進(jìn)行了一些改進(jìn)，下面的程序段給出了改進(jìn)部分；試 說(shuō)明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法在執(zhí)行上有什么不 同。/檢查左兒

18、子結(jié)點(diǎn)Type wt二Ew + wi；/左兒子結(jié)點(diǎn)的重量if (wt二c) /可行結(jié)點(diǎn)if (wtbestw) bestw = wt；/加入活結(jié)點(diǎn)隊(duì)列if (i 0故Ew+rbestw總是成立。也就是說(shuō),此時(shí)右子樹(shù)測(cè)試不起作用。為了使上述右子樹(shù)測(cè)試盡早生效，應(yīng)提早更新bestw。又知算法最終找到的最優(yōu)值是所求 問(wèn)題的子集樹(shù)中所有可行結(jié)點(diǎn)相應(yīng)重量的最大值.而結(jié)點(diǎn)所相應(yīng)得重量?jī)H在搜索進(jìn)入左子樹(shù)是增 加，因此，可以在算法每一次進(jìn)入左子樹(shù)時(shí)更新bestw的值。7。最長(zhǎng)公共子序列問(wèn)題：給定2個(gè)序列X= x1,x2,.,xm和Y= y1,y2，yn,找出X和Y 的最長(zhǎng)公共子序列。(完整word版)算法設(shè)計(jì)

19、與分析考試題目及答案由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(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的最長(zhǎng)公共子序列。故此時(shí)Cij =0其它情況下，由最優(yōu)子結(jié) 0i = 0, j = 0構(gòu)性質(zhì)可建立遞歸關(guān)系如下：ci j = 0; x = yijmaxcij 1,ci-lj i, j 0;x 豐 yij在程序中,bij 記錄Ci j的值是由哪一個(gè)子問(wèn)題的解得到的。(1)請(qǐng)?zhí)顚?xiě)程序中的空格，以使函數(shù)LCSLength完成計(jì)算最優(yōu)值的功能。void LCSLen

20、g th(i nt m, intn, char *x, char *y, int 火*c, int 火 *b)int i,j；for(i = 1;i 二m; i+)ci0=for(i = 1;i = n;i+) c0i = 0;for(i = 1；i = m；i+)for (j = 1； j = n; j+)if (xi=y j)(2)函數(shù)LCS實(shí)現(xiàn)根據(jù)b的內(nèi)容打印出Xi和Yj的最長(zhǎng)公共子序列請(qǐng)?zhí)顚?xiě)程序中的空格， 以使函數(shù)LCS完成構(gòu)造最長(zhǎng)公共子序列的功能(請(qǐng)將bi j啲取值與(1 )中您填寫(xiě) 的取值對(duì)應(yīng),否則視為錯(cuò)誤)。void LCS(int i, int j, char 火x, int

21、*b)if (i =0 II j=0) return；if (b i j= 1)LCS (i-1, j1,x, b)；&對(duì)下面的遞歸算法，寫(xiě)出調(diào)用f(4 )的執(zhí)行結(jié)果.void f(int k) if ( k0 ) printf (” %dn “，k)f (k-1)f(k一1)；1。一個(gè)算法就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特殊類(lèi)型問(wèn)題的一系列運(yùn)算, TOC o 1-5 h z 此外，算法還應(yīng)具有以下五個(gè)重要特性:,，,。2 。 算 法 的 復(fù) 雜 性 有 和 之 分 ， 衡 量 一 個(gè) 算 法 好 壞 的 標(biāo) 準(zhǔn) 是3。某一問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征是.4若序列 X二B

22、,C,A,D,B,C,D,Y二A,C,B,A,B,D,C,D,請(qǐng)給出序列 X 和 Y的一個(gè)最長(zhǎng)公共子序列。用回溯法解問(wèn)題時(shí)，應(yīng)明確定義問(wèn)題的解空間，問(wèn)題的解空間至少應(yīng)包含。6。動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干，先求解，然后從這些的解得到原問(wèn)題的解。7。以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為.8。0-1 背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為，用動(dòng)態(tài)規(guī)劃算法所需的計(jì)算時(shí)間為。動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是和。二分搜索算法是利用實(shí)現(xiàn)的算法。二、綜合題（50分）1。寫(xiě)出設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟.2。流水作業(yè)調(diào)度問(wèn)題的johnson算法的思想。若n=4，在機(jī)器M1和M2上加工作業(yè)i所需的時(shí)間

23、分別為a：和b.,且 宀宀，a4）=（ 4,5， 12,10 ）（b1, b2, b3,b4 ） = （8, 2,15 , 9）求4個(gè)作業(yè)的最優(yōu)調(diào)度方案，并計(jì)算最優(yōu)值。使用回溯法解0/1背包問(wèn)題：n = 3 , C=9,V= 6,10, 3 , W=3,4,4,其解空間有長(zhǎng)度為3的0-1向量組成，要求用一棵完全二叉樹(shù)表示其解空間（從根出發(fā)，左1右0 ） ，并畫(huà)出其解 空間樹(shù),計(jì)算其最優(yōu)值及最優(yōu)解。5。設(shè)S=X1 , X2八Xn是嚴(yán)格遞增的有序集，利用二叉樹(shù)的結(jié)點(diǎn)來(lái)存儲(chǔ)S中的元素,在表示S 的二叉搜索樹(shù)中搜索一個(gè)元素X,返回的結(jié)果有兩種情形,（1 ）在二叉搜索樹(shù)的內(nèi)結(jié)點(diǎn)中找到 X=X.,其概率為

24、b.（2）在二叉搜索樹(shù)的葉結(jié)點(diǎn)中確定Xe（ Xi,Xi+1）/其概率為a.。在表示S的 二叉搜索樹(shù)T中，設(shè)存儲(chǔ)元素X.的結(jié)點(diǎn)深度為C.;葉結(jié)點(diǎn)（X., Xi+1）的結(jié)點(diǎn)深度為d.，則二叉 搜索樹(shù)T的平均路長(zhǎng)p為多少？假設(shè)二叉搜索樹(shù)Tij= X., Xi+1 ,必最優(yōu)值為mij, Wij = ai1+bi+bj+aj/則 m i j（1 = i=j二n）遞歸關(guān)系表達(dá)式為什么？描述0-1背包問(wèn)題.簡(jiǎn)答題（30分）流水作業(yè)調(diào)度中，已知有n個(gè)作業(yè)，機(jī)器M1和M2上加工作業(yè)i所需的時(shí)間分別為a.和b., 請(qǐng)寫(xiě)出流水作業(yè)調(diào)度問(wèn)題的johnson法則中對(duì)a.和b.的排序算法。（函數(shù)名可寫(xiě)為sort （ s,

25、n）最優(yōu)二叉搜索樹(shù)問(wèn)題的動(dòng)態(tài)規(guī)劃算法（設(shè)函數(shù)名 binarysearchtree）答案：一、填空1確定性 有窮性 可行性 0個(gè)或多個(gè)輸入 一個(gè)或多個(gè)輸出2。時(shí)間復(fù)雜性 空間復(fù)雜性 時(shí)間復(fù)雜度高低該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)4。BABCD 或 CABCD或 CADCD 5。一個(gè)（最優(yōu)）解子問(wèn)題 子問(wèn)題 子問(wèn)題回溯法o（n*2n） o（minnc，2n）最優(yōu)子結(jié)構(gòu) 重疊子問(wèn)題動(dòng)態(tài)規(guī)劃法二、綜合題1。問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；構(gòu)造最優(yōu)值的遞歸關(guān)系表達(dá)式；最優(yōu)值的算法描述；構(gòu) 造最優(yōu)解；2。令N=i | a. = b.;將叫中作業(yè)按a.的非減序排序得到NJ，將N2 中作業(yè)按b.的非增序排序得到N2:NJ中作

26、業(yè)接N2中作業(yè)就構(gòu)成了滿足Johnson法則的 最優(yōu)調(diào)度。步驟為：N1二1, 3,N2=2,4;N1=1,3， N2=4，2；最優(yōu)值為：38解空間為（0，0,0），（0，1,0）,（0，0,1）,（1，0，0）,（0,1，1），（1，0,1）, （1，1，0），（1，1，1）。解空間樹(shù)為：該問(wèn)題的最優(yōu)值為：16最優(yōu)解為：(1，1，0)5。二叉樹(shù)T的平均路長(zhǎng)P= bi*(l + Ci) + Yaj*djj=0 m ij二Wij +min mik + m k+1ji=1(1=i=jj) 6。已知一個(gè)背包的容量為C，有n件物品，物品i的重量為W.，價(jià)值為V.,求應(yīng)如何選擇裝入背包中的物品，使得裝入背

27、包中物品的總價(jià)值最大。三、簡(jiǎn)答題1.void sort(flowjope s，int n)int i，k，j，l;for(i=1;in ) break;/沒(méi)有 ai,跳出elsefor(j=k+1 ；j=n；j+)if(sjtag =O)if(s kL asj.a) k=j ;swap(si。index , s k.index );swap(si.tag，sk.tag);l = i；/記下當(dāng)前第一個(gè)Q的下標(biāo)for(i=l;i=n-1;i+)k=i；for ( j = k+1 ； j = n;j+ )if(sk.bsj.b) k=j;swap(si。index,sk。index) ; /只移動(dòng)

28、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；i1）4!U 0 !M+f| i+| uj+ l| !山二1 （+耳匸|化+ !二|）6t 打!sI fl ! m+ 0 i + iuj+ l!uj = fi uj gq+ f e+ifiM= f! m-l+!=f（+ + 口一心!）0異胡I-（+ + lfu 二 |【o 二 | ）0 I 0=l!JUJI l-!e= l-i ! m鬱紅目鯽皋出B曲辭當(dāng)翊

29、P0M 辭）一、填空題(本題15分，每小題1分) TOC o 1-5 h z 1、算法就是一組有窮的，它們規(guī)定了解決某一特定類(lèi)型問(wèn)題的。2、在進(jìn)行問(wèn)題的計(jì)算復(fù)雜性分析之前，首先必須建立求解問(wèn)題所用的計(jì)算模型。3個(gè)基本計(jì)算模型是 、。3、算法的復(fù)雜性是的度量，是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。4、計(jì)算機(jī)的資源最重要的是和資源。因而，算法的復(fù)雜性有和之分.5、f(n) = 6x2n+n2,f ( n)的漸進(jìn)性態(tài) f( n)= O ()6、貪心算法總是做出在當(dāng)前看來(lái)的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上礦。7、許多可以用貪心算法求解的問(wèn)題一般具有2個(gè)重要的性質(zhì)：性質(zhì)和 性

30、質(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、NP、NPC問(wèn)題三、算法填空(本題20分，每小題5分)1、n后問(wèn)題回溯算法用二維數(shù)組AN N存儲(chǔ)皇后位置，若第i行第j列放有皇后，則Aij為非0值， 否則值為0.分別用一維數(shù)組M N、L2*N1、R2*N-1 表示豎列、左斜線、右斜線是否放有 棋子，有則值為1,否則值為0。for(j=0;jN；j+)if( 1) /*安全檢查*/ Aij=i+1；/放皇后/2；if(i=N1) 輸出結(jié)果；else 3；; /*試探下一行*

31、/*去皇后*/2、數(shù)塔問(wèn)題。有形如下圖所示的數(shù)塔從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一起走到底層,要求找出一條路徑，使路徑上的值最大.for(r=n2;r=0;r-) 自底向上遞歸計(jì)算 TOC o 1-5 h z for( c=0 ；1；c+)if( tr+1ctr+1c+1) else 3;3、HanoiHanoi(n , a,b,c)if (n = = 1)1else 2；3;Hanoi(n-1,b , a, c);4、Dijkstra算法求單源最短路徑du :s到u的距離pu:記錄前一節(jié)點(diǎn)信息Init-singl source ( G,s)for each vertex ve

32、VGdo d v=8；1d s=0Relax ( u,v,w )if dvdu +w(u , v)then dv=du +w u,v;dijkstra(G,w, s)Init-singl source(G,s )s=e3。Q=VG4。while Qdo u = min （ Q ）S=SU u for each vertex do 4Vi法，求下圖中從 徑，請(qǐng)畫(huà)出求得 被舍棄的結(jié)點(diǎn)用 單圓圈?？蚱穑?、算法理解題（本題10分） 根據(jù)優(yōu)先隊(duì)列式分支限界 v1點(diǎn)到v9點(diǎn)的單源最短路 最優(yōu)解的解空間樹(shù).要求中間 X標(biāo)記，獲得中間解的結(jié)點(diǎn)用最優(yōu)解用雙圓圈框起.五、算法理解題（本題5分）設(shè)有n=2k個(gè)運(yùn)動(dòng)

33、員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表:每個(gè)選手必須與其他n1名選手比賽各一次；每個(gè)選手一天至多只能賽一次；循環(huán)賽要在最短時(shí)間內(nèi)完成。（1）如果n=2k,循環(huán)賽最少需要進(jìn)行幾天；（2）當(dāng)n=23=8時(shí)，請(qǐng)畫(huà)出循環(huán)賽日程表。六、算法設(shè)計(jì)題（本題15分）分別用貪心算法、動(dòng)態(tài)規(guī)劃法、回溯法設(shè)計(jì)01背包問(wèn)題。要求：說(shuō)明所使用的算法策略;寫(xiě)出算法實(shí)現(xiàn)的主要步驟；分析算法的時(shí)間。七、算法設(shè)計(jì)題（本題10分）通過(guò)鍵盤(pán)輸入一個(gè)高精度的正整數(shù)n（n的有效位數(shù)240 ）去掉其中任意s個(gè)數(shù)字后,剩下的 數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的n和s,尋找一種方案，使得剩下的 數(shù)字組成的新數(shù)最小?！緲永斎搿?78543S=4【樣例輸出】13一、填空題（本題15分，每小題1分）1規(guī)則 一系列運(yùn)算隨機(jī)存取機(jī) RAM（Random Access Machine ）；隨機(jī)存取存儲(chǔ)程序機(jī) RASP（RandomAccess Stored Program Machine ）;圖靈機(jī)（Turing Machine）算法效率時(shí)間 、空間、時(shí)間復(fù)雜度、 空間復(fù)雜度52n6 最好 局部最優(yōu)選擇貪心選擇 最優(yōu)子結(jié)構(gòu)二、簡(jiǎn)答題（本題25分，每小題5分）6、分治法的基本