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

1、算法分析與設(shè)計期末復(fù)習(xí)題一、 選擇題1。應(yīng)用Johnson法則的流水作業(yè)調(diào)度采用的算法是（D）貪心算法B.分支限界法C.分治法D.動態(tài)規(guī)劃算法Hanoi塔問題如下圖所示。現(xiàn)要求將塔座A上的的所有圓盤移到塔座B上，并仍按同樣順序疊置。移動圓盤時遵守Hanoi塔問題的移動規(guī)則.由此設(shè)計出解Hanoi塔問題的遞歸算法正確的 為：（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。動態(tài)規(guī)劃算法的基本要素為(C)最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)重疊子問題性質(zhì)與貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)預(yù)排序與遞歸調(diào)用記號0表示(D)。4。算法分析中，記號O表示(B),記號Q表示(A),A。漸進下界B。漸進上界C。非緊上界D。緊漸進界E。非緊下界5。以下關(guān)于漸進記號的性質(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)解的問題，一般具有的重要性質(zhì)為：(A)最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)重疊子問題性質(zhì)與貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)預(yù)排序與遞歸調(diào)用回溯法在問題的解空間樹中，按（D）策略，從根結(jié)點出發(fā)搜索解空間樹.廣度優(yōu)先B?；罱Y(jié)點優(yōu)先C.擴展結(jié)點優(yōu)先D.深度優(yōu)先8 分支限界法在問題的解空間樹中，按（A）策略，從根結(jié)點出發(fā)搜索解空間樹。A 廣度優(yōu)先B.活結(jié)點優(yōu)先C.擴展結(jié)點優(yōu)先D。深度優(yōu)先A.B。程序塊（A ）是回溯法中遍歷排列樹的算法框架程序.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 + + ) 回溯法的效率不依賴于以下哪一個因素？ ( C )產(chǎn)生x k的時間；滿足顯約束的刈k值的個數(shù)；c.問題的解空間的形式；計算上界函數(shù)b

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

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

7、n) n。有：0 cg(n) 0,存在正數(shù)和n 0使得對所有n n有：0 f (n)0,存在正數(shù)和n0使得對所有n n有： 0 cg(n) f(n) ;二、 填空題下面程序段的所需要的計算時間為(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 個待安排的活動，它們具有下表所示的開始時間與結(jié)束時間,如果以貪心算法求解這 些活動的最優(yōu)安排（即為活動安排問題：在所給的活動集合中

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

9、O（h（n ） ） ）?；厮莘ǖ乃惴蚣馨凑諉栴}的解空間一般分為（子集樹）算法框架與（排列樹）算法框架.用回溯法解 0/1 背包問題時,該問題的解空間結(jié)構(gòu)為（子集樹）結(jié)構(gòu).用回溯法解批處理作業(yè)調(diào)度問題時,該問題的解空間結(jié)構(gòu)為（排列樹）結(jié)構(gòu)。用回溯法解0/1 背包問題時,計算結(jié)點的上界的函數(shù)如下所示,請在空格中填入合適的 內(nèi)容：Typep KnapTypew, Typep： Bound(int i)/計算上界Typew cleft = c 一 cw; / 剩余容量Typep b = cp；/結(jié)點的上界/以物品單位重量價值遞減序裝入物品 while (i 二 n & w i二 cleft) cle

10、ft = w i;11用回溯法解布線問題時，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為n m的方格陣 列，擴展每個結(jié)點需O (1)的時間丄為最短布線路徑的長度，則算法共耗時(O(mn)， 構(gòu)造相應(yīng)的最短距離需要(O(L)時間。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著色問題時，使用下面的函數(shù)OK檢查當(dāng)前擴展結(jié)點的每一個兒子所相 應(yīng)的顏色的可用性，則需耗時(漸進時間上限)(O(mn)Bool Color： OK (int k)/for (int j=1;j 1merge將k個子問題的解合并為原問題的解需用f (n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|二n的問題所需的計算時間,則有：t(n)=通過迭代法求得T(n )的顯式表達式為:T (n) =nlogmk +

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

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

14、ini I x = 1。 如果給定的最優(yōu)裝載問題有解，則有1 k n。)1in證明:四、 解答題機器調(diào)度問題。問題描述：現(xiàn)在有 n 件任務(wù)和無限多臺的機器，任務(wù)可以在機器上得到處理.每件任務(wù) 的開始時間為si，完成時間為fi, sifj .si,fi為處理任務(wù)i的時間范圍。兩個任務(wù)i ,j 重疊指兩個任務(wù)的時間范圍區(qū)間有重疊，而并非指i,j的起點或終點重合.例如：區(qū)間1,4 與區(qū)間2，4重疊，而與4，7不重疊.一個可行的任務(wù)分配是指在分配中沒有兩件重疊的 任務(wù)分配給同一臺機器.因此,在可行的分配中每臺機器在任何時刻最多只處理一個任務(wù)。最 優(yōu)分配是指使用的機器最少的可行分配方案。(完整word版

15、)算法設(shè)計與分析考試題目及答案問題實例：若任務(wù)占用的時間范圍是 1,4,2,5,4,5, 2,6, 4,7,則按時完成所有任務(wù)最少需要幾臺機器？(提示：使用貪心算法) 畫出工作在對應(yīng)的機器上的分配情況。已知非齊次遞歸方程：Jf(n)= bf(n-1)+如)，其中，b、c是常數(shù),g (n)是n的某一個 I f(0)= c函數(shù)。則f(n)的非遞歸表達式為：f(n) = cbn+ bn-ig(i).i=1現(xiàn)有Hanoi塔問題的遞歸方程為：p(n)= 2h(n -D+1，求h(n)的非遞歸表達式.h(1)=1解利用給出的關(guān)系式，此時有：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單源最短路徑的求解。問題的描述：給定帶權(quán)有向圖(如下圖所示)G =(V , E),其中每條邊的權(quán)是非負(fù)實數(shù)。另 外，還給定V中的一個頂點，稱為源。現(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里 路的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。解法：現(xiàn)采用Dijkstra算法計算從源頂點1到其它頂點間最短路徑。請將此過程填入下表 中.迭代Sudist2dist3dist4dist5初始110maxint301001234請寫出用回溯法解裝載問題的函數(shù).裝載問題：

17、有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的n乙 w n) / 到達葉結(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。用分支限界法解裝載問題時，對算法進行了一些改進，下面的程序段給出了改進部分；試 說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法在執(zhí)行上有什么不 同。/檢查左兒

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

19、與分析考試題目及答案由最長公共子序列問題的最優(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é) 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的值是由哪一個子問題的解得到的。(1)請?zhí)顚懗绦蛑械目崭?，以使函?shù)LCSLength完成計算最優(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實現(xiàn)根據(jù)b的內(nèi)容打印出Xi和Yj的最長公共子序列請?zhí)顚懗绦蛑械目崭瘢?以使函數(shù)LCS完成構(gòu)造最長公共子序列的功能(請將bi j啲取值與(1 )中您填寫 的取值對應(yīng),否則視為錯誤)。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)；&對下面的遞歸算法，寫出調(diào)用f(4 )的執(zhí)行結(jié)果.void f(int k) if ( k0 ) printf (” %dn “，k)f (k-1)f(k一1)；1。一個算法就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特殊類型問題的一系列運算, TOC o 1-5 h z 此外，算法還應(yīng)具有以下五個重要特性:,，,。2 。 算 法 的 復(fù) 雜 性 有 和 之 分 ， 衡 量 一 個 算 法 好 壞 的 標(biāo) 準(zhǔn) 是3。某一問題可用動態(tài)規(guī)劃算法求解的顯著特征是.4若序列 X二B

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

23、分別為a：和b.,且 宀宀，a4）=（ 4,5， 12,10 ）（b1, b2, b3,b4 ） = （8, 2,15 , 9）求4個作業(yè)的最優(yōu)調(diào)度方案，并計算最優(yōu)值。使用回溯法解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=X1 , X2八Xn是嚴(yán)格遞增的有序集，利用二叉樹的結(jié)點來存儲S中的元素,在表示S 的二叉搜索樹中搜索一個元素X,返回的結(jié)果有兩種情形,（1 ）在二叉搜索樹的內(nèi)結(jié)點中找到 X=X.,其概率為

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

25、n）最優(yōu)二叉搜索樹問題的動態(tài)規(guī)劃算法（設(shè)函數(shù)名 binarysearchtree）答案：一、填空1確定性 有窮性 可行性 0個或多個輸入 一個或多個輸出2。時間復(fù)雜性 空間復(fù)雜性 時間復(fù)雜度高低該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)4。BABCD 或 CABCD或 CADCD 5。一個（最優(yōu)）解子問題 子問題 子問題回溯法o（n*2n） o（minnc，2n）最優(yōu)子結(jié)構(gòu) 重疊子問題動態(tài)規(guī)劃法二、綜合題1。問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；構(gòu)造最優(yōu)值的遞歸關(guān)系表達式；最優(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）。解空間樹為：該問題的最優(yōu)值為：16最優(yōu)解為：(1，1，0)5。二叉樹T的平均路長P= bi*(l + Ci) + Yaj*djj=0 m ij二Wij +min mik + m k+1ji=1(1=i=jj) 6。已知一個背包的容量為C，有n件物品，物品i的重量為W.，價值為V.,求應(yīng)如何選擇裝入背包中的物品，使得裝入背

27、包中物品的總價值最大。三、簡答題1.void sort(flowjope s，int n)int i，k，j，l;for(i=1;in ) break;/沒有 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)前第一個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) ; /只移動

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ī)定了解決某一特定類型問題的。2、在進行問題的計算復(fù)雜性分析之前，首先必須建立求解問題所用的計算模型。3個基本計算模型是 、。3、算法的復(fù)雜性是的度量，是評價算法優(yōu)劣的重要依據(jù)。4、計算機的資源最重要的是和資源。因而，算法的復(fù)雜性有和之分.5、f(n) = 6x2n+n2,f ( n)的漸進性態(tài) f( n)= O ()6、貪心算法總是做出在當(dāng)前看來的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上礦。7、許多可以用貪心算法求解的問題一般具有2個重要的性質(zhì)：性質(zhì)和 性

30、質(zhì)。二、簡答題(本題25分，每小題5分)1、簡單描述分治法的基本思想。2、簡述動態(tài)規(guī)劃方法所運用的最優(yōu)化原理。3、何謂最優(yōu)子結(jié)構(gòu)性質(zhì)？4、簡單描述回溯法基本思想。5、何謂P、NP、NPC問題三、算法填空(本題20分，每小題5分)1、n后問題回溯算法用二維數(shù)組AN N存儲皇后位置，若第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ù)塔問題。有形如下圖所示的數(shù)塔從頂部出發(fā)，在每一結(jié)點可以選擇向左走或是向右走，一起走到底層,要求找出一條路徑，使路徑上的值最大.for(r=n2;r=0;r-) 自底向上遞歸計算 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é)點信息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法，求下圖中從 徑，請畫出求得 被舍棄的結(jié)點用 單圓圈?？蚱穑?、算法理解題（本題10分） 根據(jù)優(yōu)先隊列式分支限界 v1點到v9點的單源最短路 最優(yōu)解的解空間樹.要求中間 X標(biāo)記，獲得中間解的結(jié)點用最優(yōu)解用雙圓圈框起.五、算法理解題（本題5分）設(shè)有n=2k個運動

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