《《算法設(shè)計(jì)與分析》考試題目及答案.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法設(shè)計(jì)與分析》考試題目及答案.doc（69頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

《算法分析與設(shè)計(jì)》期末復(fù)習(xí)題 一、 選擇題 1.應(yīng)用Johnson法則的流水作業(yè)調(diào)度采用的算法是（D） A. 貪心算法 B. 分支限界法 C.分治法 D. 動(dòng)態(tài)規(guī)劃算法 2.Hanoi塔問題如下圖所示。現(xiàn)要求將塔座A上的的所有圓盤移到塔座B上，并仍按同樣順序疊置。移動(dòng)圓盤時(shí)遵守Hanoi塔問題的移動(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, A); } } Hanoi塔 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 hanoi(int n, int C, int B, int A) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } } D. void hanoi(int n, int C, int A, int B) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(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)用 4. 算法分析中，記號(hào)O表示（B）， 記號(hào)表示（A）， 記號(hào)表示（D）。 A.漸進(jìn)下界 B.漸進(jìn)上界 C.非緊上界 D.緊漸進(jìn)界 E.非緊下界 5. 以下關(guān)于漸進(jìn)記號(hào)的性質(zhì)是正確的有：（A） A. B. C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. 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 backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); swap(x[t], x[i]); } } A. void backtrack (int t) { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t+1); } } B. void backtrack (int t) { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t-1); } } C. D.void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); } } 10. 回溯法的效率不依賴于以下哪一個(gè)因素？（C ） A. 產(chǎn)生x[k]的時(shí)間； B. 滿足顯約束的x[k]值的個(gè)數(shù)； C. 問題的解空間的形式； D. 計(jì)算上界函數(shù)bound的時(shí)間； E. 滿足約束函數(shù)和上界函數(shù)約束的所有x[k]的個(gè)數(shù)。 F. 計(jì)算約束函數(shù)constraint的時(shí)間； 11. 常見的兩種分支限界法為（D） A. 廣度優(yōu)先分支限界法與深度優(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. 。 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)NDTM所接受的語言}； B. NP={L|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)O的定義正確的是（A）。 A. O(g(n)) = { f(n) | 存在正常數(shù)c和n0使得對(duì)所有nn0有：0 f(n) cg(n) }； B. O(g(n)) = { f(n) | 存在正常數(shù)c和n0使得對(duì)所有nn0有：0 cg(n) f(n) }； C. O(g(n)) = { f(n) | 對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0 >0使得對(duì)所有nn0有：0 f(n)0，存在正數(shù)和n0 >0使得對(duì)所有nn0有：0 cg(n) < f(n) }； 15. 記號(hào)的定義正確的是（B）。 A. O(g(n)) = { f(n) | 存在正常數(shù)c和n0使得對(duì)所有nn0有：0 f(n) cg(n) }； B. O(g(n)) = { f(n) | 存在正常數(shù)c和n0使得對(duì)所有nn0有：0 cg(n) f(n) }； C. (g(n)) = { f(n) | 對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0 >0使得對(duì)所有nn0有：0 f(n)0，存在正數(shù)和n0 >0使得對(duì)所有nn0有：0 cg(n) < f(n) }； 二、 填空題 1. 下面程序段的所需要的計(jì)算時(shí)間為（ ）。 int MaxSum(int n, int *a, int &besti, int &bestj) { int sum=0; for(int i=1;i<=n;i++){ int thissum=0; for(int j=i;j<=n;j++){ thissum+=a[j]; if(thissum>sum) { sum=thissum; besti=i; bestj=j; } } } return 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} ）。 14 13 12 11 10 9 8 7 6 5 4 f[i] 12 2 8 8 6 5 3 5 0 3 1 S[i] 11 10 9 8 7 6 5 4 3 2 1 i 3. 所謂貪心選擇性質(zhì)是指（所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到）。 4. 所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指（問題的最優(yōu)解包含了其子問題的最優(yōu)解）。 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)诳崭裰刑钊牒线m的內(nèi)容： Typep Knap::Bound(int i) {// 計(jì)算上界 Typew cleft = c - cw; // 剩余容量 Typep b = cp; // 結(jié)點(diǎn)的上界 // 以物品單位重量?jī)r(jià)值遞減序裝入物品 while (i <= n && w[i] <= cleft) { cleft -= w[i]; b += p[i]; i++; } // 裝滿背包 if (i <= n) （b += p[i]/w[i] * cleft）; return b; } 11. 用回溯法解布線問題時(shí)，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為的方格陣列，擴(kuò)展每個(gè)結(jié)點(diǎn)需O(1)的時(shí)間，L為最短布線路徑的長(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)記 grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1; if ((nbr.row == finish.row) && (nbr.col == finish.col)) break; // 完成布線 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((a[k][j]= =1)&&(x[j]= =x[k])) return false; return true; } 13. 旅行售貨員問題的解空間樹是（排列樹）。 6. 7. 三、 證明題 1. 一個(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）的顯式表達(dá)式為： 試證明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))+O(g(n)) = O(max{f(n),g(n)}) 。 證明：對(duì)于任意f1(n) O(f(n)) ，存在正常數(shù)c1和自然數(shù)n1，使得對(duì)所有nn1，有f1(n) c1f(n) 。 類似地，對(duì)于任意g1(n) O(g(n)) ，存在正常數(shù)c2和自然數(shù)n2，使得對(duì)所有nn2，有g(shù)1(n) c2g(n) 。 令c3=max{c1, c2}， n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。 則對(duì)所有的 n n3，有 f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n) = c3(f(n) + g(n)) c32 max{f(n),g(n)} = 2c3h(n) = O(max{f(n),g(n)}) . 4. 求證最優(yōu)裝載問題具有貪心選擇性質(zhì)。 （最優(yōu)裝載問題：有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。 設(shè)集裝箱已依其重量從小到大排序，(x1,x2,…,xn)是最優(yōu)裝載問題的一個(gè)最優(yōu)解。又設(shè) 。如果給定的最優(yōu)裝載問題有解，則有。） 證明： 四、 解答題 1. 機(jī)器調(diào)度問題。 問題描述：現(xiàn)在有n件任務(wù)和無限多臺(tái)的機(jī)器，任務(wù)可以在機(jī)器上得到處理。每件任務(wù)的開始時(shí)間為si，完成時(shí)間為fi，si n) // 到達(dá)葉結(jié)點(diǎn) 更新最優(yōu)解bestx,bestw;return; r -= w[i]; if (cw + w[i] <= c) {// 搜索左子樹 x[i] = 1; cw += w[i]; backtrack(i + 1); cw -= w[i]; } if (cw + r > bestw) { x[i] = 0; // 搜索右子樹 backtrack(i + 1); } r += w[i]; } 5. 用分支限界法解裝載問題時(shí)，對(duì)算法進(jìn)行了一些改進(jìn)，下面的程序段給出了改進(jìn)部分；試說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法在執(zhí)行上有什么不同。 // 檢查左兒子結(jié)點(diǎn) Type wt = Ew + w[i]; // 左兒子結(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) 解答：斜線標(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)公共子序列問題：給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長(zhǎng)公共子序列。 由最長(zhǎng)公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列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í)C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下： 在程序中，b[i][j]記錄C[i][j]的值是由哪一個(gè)子問題的解得到的。 （1） 請(qǐng)?zhí)顚懗绦蛑械目崭?，以使函?shù)LCSLength完成計(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++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2;} else { c[i][j]=c[i][j-1]; b[i][j]=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)將b[i][j]的取值與（1）中您填寫的取值對(duì)應(yīng)，否則視為錯(cuò)誤）。 void LCS(int i，int j，char *x，int **b) { if (i ==0 || j==0) return; if (b[i][j]== 1) { LCS(i-1，j-1，x，b); cout<0 ) { printf("%d\n ",k); f(k-1); f(k-1); } } 一、填空題（20分） 1.一個(gè)算法就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特殊類型問題的一系列運(yùn)算，此外，算法還應(yīng)具有以下五個(gè)重要特性:_________,________,________,__________,__________。 2.算法的復(fù)雜性有_____________和___________之分，衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是______________________。 3.某一問題可用動(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和Y的一個(gè)最長(zhǎng)公共子序列_____________________________。 5.用回溯法解問題時(shí)，應(yīng)明確定義問題的解空間，問題的解空間至少應(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è)基本要素是___________和___________。 10.二分搜索算法是利用_______________實(shí)現(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í)間分別為ai和bi，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(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=｛X1，X2，，Xn｝是嚴(yán)格遞增的有序集，利用二叉樹的結(jié)點(diǎn)來存儲(chǔ)S中的元素，在表示S的二叉搜索樹中搜索一個(gè)元素X，返回的結(jié)果有兩種情形，（1）在二叉搜索樹的內(nèi)結(jié)點(diǎn)中找到X=Xi，其概率為bi。（2）在二叉搜索樹的葉結(jié)點(diǎn)中確定X∈（Xi，Xi+1），其概率為ai。在表示S的二叉搜索樹T中，設(shè)存儲(chǔ)元素Xi的結(jié)點(diǎn)深度為Ci；葉結(jié)點(diǎn)（Xi，Xi+1）的結(jié)點(diǎn)深度為di，則二叉搜索樹T的平均路長(zhǎng)p為多少？假設(shè)二叉搜索樹T[i][j]=｛Xi，Xi+1，，Xj｝最優(yōu)值為m[i][j]，W[i][j]= ai-1+bi++bj+aj，則m[i][j](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ì)ai和bi的排序算法。（函數(shù)名可寫為sort(s,n)） 2.最優(yōu)二叉搜索樹問題的動(dòng)態(tài)規(guī)劃算法（設(shè)函數(shù)名binarysearchtree)） 答案： 一、填空 1．確定性 有窮性 可行性 0個(gè)或多個(gè)輸入 一個(gè)或多個(gè)輸出 2.時(shí)間復(fù)雜性 空間復(fù)雜性 時(shí)間復(fù)雜度高低 3. 該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 4.{BABCD}或{CABCD}或{CADCD｝ 5.一個(gè)（最優(yōu)）解 6.子問題 子問題 子問題 7.回溯法 8. o(n*2n) o(min{nc,2n}) 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. ①令N1={i|ai=bi}；②將N1中作業(yè)按ai的非減序排序得到N1’，將N2中作業(yè)按bi的非增序排序得到N2’；③N1’中作業(yè)接N2’中作業(yè)就構(gòu)成了滿足Johnson法則的最優(yōu)調(diào)度。 3.步驟為：N1={1，3}，N2={2，4}； N1’={1，3}， N2’={4，2}； 最優(yōu)值為：38 4.解空間為{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空間樹為： A B C F E D G K J I H O N M L 1 1 1 0 0 0 0 1 0 1 1 0 1 0 該問題的最優(yōu)值為：16 最優(yōu)解為：（1，1，0） 5.二叉樹T的平均路長(zhǎng)P=+ m[i][j]=W[i][j]+min{m[i][k]+m[k+1][j]} (1<=i<=j<=n,m[i][i-1]=0) m[i][j]=0 (i>j) 6.已知一個(gè)背包的容量為C，有n件物品，物品i的重量為Wi，價(jià)值為Vi，求應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大。 三、簡(jiǎn)答題 1. void sort(flowjope s[],int n) { int i,k,j,l; for(i=1;i<=n-1;i++)//-----選擇排序 { k=i; while(k<=n&&s[k].tag!=0) k++; if(k>n) break;//-----沒有ai，跳出 else { for(j=k+1;j<=n;j++) if(s[j].tag==0) if(s[k].a>s[j].a) k=j; swap(s[i].index,s[k].index); swap(s[i].tag,s[k].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(s[k].b=0;r--) //自底向上遞歸計(jì)算 for(c=0; 1 ;c++) if( t[r+1][c]>t[r+1][c+1]) 2 ； else 3 ； 3、Hanoi算法 Hanoi(n,a,b,c) if （n==1） 1 ； else { 2 ； 3 ； Hanoi(n-1,b, a, c); } 4、Dijkstra算法求單源最短路徑 d[u]:s到u的距離 p[u]:記錄前一節(jié)點(diǎn)信息 Init-single-source(G,s) for each vertex v∈V[G] do { d[v]=∞; 1 } d[s]=0 Relax(u,v,w) if d[v]>d[u]+w(u,v) then { d[v]=d[u]+w[u,v]; 2 } dijkstra(G,w,s) 1. Init-single-source(G,s) 2. S=Φ 3. Q=V[G] 4.while Q<> Φ do u=min(Q) S=S∪{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)用標(biāo)記，獲得中間解的結(jié)點(diǎn)用單圓圈○框起，最優(yōu)解用雙圓圈◎框起。 五、算法理解題（本題5分） 設(shè)有n=2k個(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=2k，循環(huán)賽最少需要進(jìn)行幾天； （2）當(dāng)n=23=8時(shí)，請(qǐng)畫出循環(huán)賽日程表。 六、算法設(shè)計(jì)題（本題15分） 分別用貪心算法、動(dòng)態(tài)規(guī)劃法、回溯法設(shè)計(jì)0-1背包問題。要求：說明所使用的算法策略；寫出算法實(shí)現(xiàn)的主要步驟；分析算法的時(shí)間。 七、算法設(shè)計(jì)題（本題10分） 通過鍵盤輸入一個(gè)高精度的正整數(shù)n(n的有效位數(shù)≤240)，去掉其中任意s個(gè)數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的n 和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小。 【樣例輸入】 178543 S=4 【樣例輸出】 13 一、填空題（本題15分，每小題1分） 1．規(guī)則 一系列運(yùn)算 2. 隨機(jī)存取機(jī)RAM(Random Access Machine)；隨機(jī)存取存儲(chǔ)程序機(jī)RASP(Random Access Stored Program Machine)；圖靈機(jī)(Turing Machine) 3. 算法效率 4. 時(shí)間、空間、時(shí)間復(fù)雜度、空間復(fù)雜度 5．2n 6．最好 局部最優(yōu)選擇 7. 貪心選擇 最優(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é)化的語言來描述：假設(shè)為了解決某一優(yōu)化問題，需要依次作出n個(gè)決策D1，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)先搜索過程。在回溯法中，并不是先構(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) !M[j]&&!L[i+j]&&!R[i-j+N] (2) M[j]=L[i+j]=R[i-j+N]=1; (3) try(i+1,M,L,R,A) (4) A[i][j]=0 (5) M[j]=L[i+j]=R[i-j+N]=0 2、數(shù)塔問題。 （1）c<=r (2)t[r][c]+=t[r+1][c] （3）t[r][c]+=t[r+1][c+1] 3、Hanoi算法 （1）move(a,c) （2）Hanoi(n-1, a, c , b) （3）Move(a,c) 4、（1）p[v]=NIL （2）p[v]=u (3) v∈adj[u] （4）Relax(u,v,w) 四、算法理解題（本題10分） 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 五、（1）8天（2分）； （2）當(dāng)n=23=8時(shí)，循環(huán)賽日程表（3分）。 六、算法設(shè)計(jì)題（本題15分） （1）貪心算法 O（nlog（n）） 首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。 具體算法可描述如下： void Knapsack(int n,float M,float v[],float w[],float x[]) {Sort(n,v,w); int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) {if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; } （2）動(dòng)態(tài)規(guī)劃法 O(nc) m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式如下。 void KnapSack(int v[],int w[],int c,int n,int m[][11]) {int jMax=min(w[n]-1,c); for (j=0;j<=jMax;j++) /*m(n,j)=0 0==w[n]*/ m[n][j]=v[n]; for (i=n-1;i>1;i--) { int jMax=min(w[i]-1,c); for (j=0;j<=jMax;j++) /*m(i,j)=m(i+1,j) 0==w[n]*/ m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } （3）回溯法 O(2n) cw:當(dāng)前重量 cp:當(dāng)前價(jià)值 bestp：當(dāng)前最優(yōu)值 voidbacktrack(inti) //回溯法 i初值1 {if(i>n) //到達(dá)葉結(jié)點(diǎn) { bestp=cp; return; } if(cw+w[i]<=c) //搜索左子樹 {cw+=w[i]; cp+=p[i]; backtrack(i+1); cw-=w[i]; cp-=p[i]; } if(Bound(i+1)>bestp) //搜索右子樹 backtrack(i+1); } 七、算法設(shè)計(jì)題（本題10分） 為了盡可能地逼近目標(biāo)，我們選取的貪心策略為：每一步總是選擇一個(gè)使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個(gè)數(shù)字，否則刪除第一個(gè)遞減區(qū)間的首字符。然后回到串首，按上述規(guī)則再刪除下一個(gè)數(shù)字。重復(fù)以上過程s次，剩下的數(shù)字串便是問題的解了。 具體算法如下： 輸入s, n; while（ s > 0 ） { i=1; //從串首開始找 while (i < length(n)) && (n[i]1)&& (n[1]=‘0’) delete(n,1,1); //刪去串首可能產(chǎn)生的無用零 輸出n; 歡迎你們?cè)诎倜χ猩W臨我校指導(dǎo)工作，借此機(jī)會(huì)我代表全體師生向各位領(lǐng)導(dǎo)的到來表示熱烈的歡迎和衷心的感謝！我們學(xué)校環(huán)境幽雅，占地面積9810平方米，校舍建筑面積9639平方米?，F(xiàn)有31個(gè)教學(xué)班，1763名學(xué)生，91名教師。多年來，我校以“潤(rùn)育潛質(zhì)培養(yǎng)習(xí)慣 發(fā)展個(gè)性 奠基未來”為辦學(xué)宗旨，致力于實(shí)現(xiàn)“綠色校園 人文課堂 涵養(yǎng)教師 儒雅學(xué)生”的辦學(xué)目標(biāo)，以“人文 和諧 文明 向上”為學(xué)校精神。把“關(guān)愛 合作和諧 平安”作為學(xué)校德育工作的主旋律，把“課程改革，主動(dòng)構(gòu)建”作為素質(zhì)教育的主攻方向，把“創(chuàng)建學(xué)習(xí)型校園，引領(lǐng)教師專業(yè)成長(zhǎng)”作為興校強(qiáng)師之道，有效地促進(jìn)了教育資源的優(yōu)化，激發(fā)了團(tuán)結(jié)拼搏的團(tuán)隊(duì)精神，提升了整體辦學(xué)水平，取得了豐碩的教育教學(xué)成果。 　　德育工作是學(xué)校教育的靈魂，是學(xué)生健康成長(zhǎng)和學(xué)校工作保障。因此，學(xué)校把德育工作擺在重要位置，時(shí)刻樹立教書育人、管理育人、服務(wù)育人的思想，確保學(xué)校德育工作的順利實(shí)施。近幾年，我校順應(yīng)時(shí)代的發(fā)展，努力更新教育理念，全面貫徹黨的教育方針，以德育工作為靈魂，堅(jiān)持以“綠色校園、優(yōu)質(zhì)教育、全面發(fā)展、快樂成長(zhǎng)”的基本思路；從“小事”抓起、據(jù)“實(shí)際”而行、作“有效”之為。堅(jiān)持以“為每一個(gè)孩子的幸福人生奠基”的育人理念，并遵循學(xué)生身心發(fā)展規(guī)律進(jìn)行了一系列的管理和教育活動(dòng)。 　　我們學(xué)校以“環(huán)境教育”為辦學(xué)特色，堅(jiān)持以綠色觀念教育師生，在全校范圍內(nèi)滲透可持續(xù)發(fā)展意識(shí)、環(huán)境價(jià)值觀、道德觀、以及環(huán)境教育創(chuàng)新意識(shí)，打造“綠色人文”校園的特色品牌。從1992年成立環(huán)境教育實(shí)驗(yàn)小組、1996年成為南昌市第一所環(huán)境教育試點(diǎn)學(xué)校、1999年被省環(huán)保局授予“環(huán)境教育示范學(xué)?！?、2001年被評(píng)為“全國(guó)綠色學(xué)校”、2011年被國(guó)家環(huán)保局授予 “國(guó)際生態(tài)學(xué)?！保?012年被國(guó)家環(huán)保局授予“全國(guó)環(huán)境教育示范?！薄Ｖ两?，經(jīng)歷了一個(gè)從點(diǎn)到面，讓環(huán)境教育滾動(dòng)式普及、從低到高，讓環(huán)境教育多層次開展、從單一到綜合，讓環(huán)境教育多學(xué)科滲透、從課堂到社會(huì)，把環(huán)境教育全方位推進(jìn)的成長(zhǎng)歷程。 　　良好的校園環(huán)境是對(duì)學(xué)生進(jìn)行環(huán)境教育的主要陣地，因此，我們注重加強(qiáng)校園文化建設(shè)，明確提出“校園無處不育人，校園無時(shí)不育人”的口號(hào)。校園內(nèi)有許多環(huán)保宣傳標(biāo)語，特色班級(jí)文化，特色班牌設(shè)計(jì)，樓道的警示語，環(huán)境教育資源隨處可見。走進(jìn)校園綠樹成陰，足跡生態(tài)園、七彩長(zhǎng)廊、翠屏小徑、生命在于運(yùn)動(dòng)文化墻、動(dòng)感地帶、等人文景觀與主體綠化相映成趣，愉悅的環(huán)境陶冶著師生的情操，同學(xué)們賞花護(hù)綠，人與自然是那么和諧。 　　學(xué)校在“發(fā)展個(gè)性、奠基未來”的辦學(xué)理念指導(dǎo)下，以藝術(shù)教育為突破口，全面推進(jìn)藝術(shù)教育健康持續(xù)發(fā)展，走出了一條跨越發(fā)展之路。為使學(xué)生的各項(xiàng)特長(zhǎng)得到規(guī)范、專業(yè)的指導(dǎo)，在每周二、周三的下午，開設(shè)足球班、舞蹈班、合唱班、美術(shù)班等興趣班，使學(xué)校文藝活動(dòng)如百花齊放。俗話說：“一份耕耘、一份汗水、一份收獲?！闭?yàn)閷W(xué)