5.《算法設(shè)計(jì)與分析》試題庫

1、算法分析與設(shè)計(jì)試題庫(一)一、 選擇題1 .應(yīng)用Johnson法則的流水作業(yè)調(diào)度采用的算法是(D)A.貪心算法B.分支限界法C.分治法D.動(dòng)態(tài)規(guī)劃算法塔問題如下圖所示?，F(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)Hanoi 塔if (n > 0)hanoi(n-1,A,C, B);B. void hanoi(int n, int A, int B, int C) if (n >

2、 0)hanoi(n-1, A, C, B);C. void hanoi(int n, int C, int B, int A) if (n > 0)hanoi(n-1, A, C, B);D. void hanoi(int n, int C, int A, int B)if (n > 0)hanoi(n-1, A, C, B);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) 表示(D)A.漸進(jìn)下界B.漸進(jìn)上界C非緊上界

3、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)C. O(f(n)+O(g(n) = O(minf(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)用A.7 .回溯法在問題的解空間樹中，按（D）策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹廣度優(yōu)先B.活

4、結(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 (t>n) output(x);elsefor (int i=t;i<=n;i+) swap(xt, xi);B.void backtrack (int t)if (t>n) output(x);elsefor (int i=0;i<=1;i+) xt=i;C.void backtrack (int t

5、)if (t>n) output(x);elsefor (int i=0;i<=1;i+) xftKD.void backtrack （int t）if （t>n） output（x）; else10 .回溯法的效率不砒nf圖測(cè)n+火素（C ）A.產(chǎn)生xk的時(shí)郵叩僅也，xi）；B.滿足顯約束的xk值的個(gè)數(shù)；C.問題的解空間的形式；D.計(jì)算上界函數(shù)bound的時(shí)間；11.常見的兩種分支限界法為（D）A.廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B.隊(duì)列式（FIFQ分支限界法與堆棧式分支限界法；C.排列樹法與子集樹法；D.隊(duì)列式（FIFQ分支限界法與優(yōu)先隊(duì)列式分支限界法；12. k

6、帶圖靈機(jī)的空間復(fù)雜性S（n雙指（B）A. k帶圖靈機(jī)處理所有長(zhǎng)度為n的輸入時(shí)，在某條帶上所使用過的最大方格數(shù)。B. k帶圖靈機(jī)處理所有長(zhǎng)度為n的輸入時(shí)，在k條帶上所使用過的方格數(shù)的總 和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è)

7、能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái) NDTM所接受的語言; 14.記號(hào)O 的定義正確的是(A)。A. O(g(n) = f(n) |存在正常數(shù)c和n0使得對(duì)所有n n0有：0f(n)cg(n) ；B. O(g(n) = f(n) |存在正常數(shù)c和n0使得對(duì)所有n n0有：0cg(n) f(n) ；C. O(g(n) = f(n) |對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0>0使得對(duì)所有n n0有： 0f(n)<cg(n) ;D. O(g(n) = f(n) |對(duì)于任何正常數(shù)c>0,存在正數(shù)和no >0使得對(duì)所有n n0 有：0 cg(n) < f(n) ；15.記號(hào)的定義正

8、確的是(B)。A. O(g(n) = f(n) |存在正常數(shù)c和n0使得對(duì)所有n n。有：0f(n)cg(n) ；B. O(g(n) = f(n) |存在正常數(shù)c和n0使得對(duì)所有n n0有：0cg(n) f(n) ；C. (g(n) = f(n) |對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0>0使得對(duì)所有n no有： 0f(n)<cg(n) ;D. (g(n) = f(n) |對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0 >0使得對(duì)所有n n。有： 0 cg(n) < f(n) ;二、 填空題1 .下面程序段的所需要的計(jì)算時(shí)間為(O(n2)。int MaxSum(int

9、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+=aj;if(thissum>sum) sum=thissum;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）。i1234567891011Si130535688212fi

10、45678910111213143 .所謂貪心選擇性質(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í)，該

11、問題的解空間結(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<Typew, 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;11 .用回溯法解布線問題時(shí)，求最優(yōu)解的主要程序段如下。如果布

12、線區(qū)域劃分為 b += pi;n m的方格陣列，擴(kuò)展每個(gè)結(jié)點(diǎn)需O(1)的時(shí)間，L為最短布線路徑的長(zhǎng)度，則i+;算法共耗時(shí)(O(mn),構(gòu)造相應(yīng)的最短距離需要(O(L時(shí)間。for (int i = 0; i < NumOfNbrs; i+) =+ offseti.row;=+ offseti.col;if (grid川=0) /該方格未標(biāo)記grid也= grid + 1;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<=

13、n;j+)if(akj= =1)&&(xj= =xk) return false;解答題13 .旅行售貨員問題的解空間樹是(排列樹)1 .機(jī)器調(diào)度問題。問題描述：現(xiàn)在有n 件任務(wù)和無限多臺(tái)的機(jī)器，任務(wù)可以在機(jī)器上得到處理。每件任務(wù)的開始時(shí)間為si ，完成時(shí)間為fi ， si<fi 。 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ù)分配是指在分配中沒有兩件重疊的任務(wù)分配給同一臺(tái)機(jī)器。因此，在可行的分配中每

14、臺(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 .已知非齊次遞歸方程：fbf(n 1) g，其中，b、c是常數(shù)，g(n) f(0) cn是n的某一個(gè)函數(shù)。則f(n)的非遞歸表達(dá)式為：f(n) cbnbn ig。i1現(xiàn)有Hanoi塔問題的遞歸方程為："2h(n 1) 1求卜的非遞歸表 h(1) 1達(dá)式。解：利用給出的關(guān)系式，此時(shí)有： b=2, c=1, g(n)=

15、1, 從 n 遞推到 1，有：n1h(n)cbn 1bn1 ig(i)i1n1 n222n 12n 2 . 22 2 12n 13. 單源最短路徑的求解。問題的描述：給定帶權(quán)有向圖(如下圖所示) G =(V,E)其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V 中的一個(gè)頂點(diǎn)，稱為源。現(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。 這里路的長(zhǎng)度是指路上各邊權(quán)之和。 這個(gè)問題通常稱為單源佚代Sudist2dist3dist4dist5初始110maxint30100一一14. W與出 2即溯法解裝載題日勺世啜。-裝載3題：有一批共n個(gè):集裝箱1煤上21騰重量分別為c1不1 c2的輪月4n1到其它頂點(diǎn)間最短路

16、徑。請(qǐng)將此Wi Cl C2其中集裝箱i的重量為wi,且i 1。裝載問題要求確定是否有一個(gè)合理的裝載方案可將這n個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。解：void backtrack (int i)用分支限界法解裝載問題時(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) (wt)

17、;解答：斜線標(biāo)識(shí)的部分完成的功能為：提前更新bestw值；這樣做可以盡早的進(jìn)行對(duì)右子樹的剪枝。具體為：算法 Maxloading初始 時(shí)將bestw設(shè)置為0,直到搜索到第一個(gè)葉結(jié)點(diǎn)時(shí)才更新 bestwo因此在算法搜 索到第一個(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)公共子序列問題

18、：給定2個(gè)序列X=x1,x2,力m! Y=y1,y2,yn找出X 和Y的最長(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 i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí) Cij=0o其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：0i 0, j 0cijci 1j 1 1 i,j 0;xyjmaxcij 1,ci 1j i, j 0kyj在程序中，bij記錄Cij的值是由哪一個(gè)子問題的解得到的。(1)請(qǐng)?zhí)顚懗绦蛑械目崭?，以使函?shù) LCSLe

19、ngt位成計(jì)算最優(yōu)值的功能。void LCSLengt(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-1i>=cii-1) (2)函數(shù)LC取現(xiàn)由g據(jù)b的內(nèi)容打印出Xi和Yj的最長(zhǎng)公共子序

20、列。請(qǐng)?zhí)?寫程序中的空格，以使函數(shù)LC航成構(gòu)造最長(zhǎng)公共子序列的功能(請(qǐng) 將bij的取值與(1)中您填寫的取值對(duì)應(yīng)，否則視為錯(cuò)誤)。void LCS(int i, int j, char *x, int *b)if (i =0 | j=0) return;if (b皿尸 1) LCS-1, j-1, x, b);cout<<xi;8 .對(duì)下面的遞歸算法，寫出調(diào)用f(4)的執(zhí)行結(jié)果void f(int k) if( k>0 ) printf("%dn ",k);f(k-1);f(k-1);算法分析與設(shè)計(jì)試題庫 （二 ）：1. 算法重要特性是什么2. 算法分析的

21、目的是什么3. 算法的時(shí)間復(fù)雜性與問題的什么因素相關(guān)4. 算法的漸進(jìn)時(shí)間復(fù)雜性的含義5. 最壞情況下的時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性有什么不同6. 簡(jiǎn)述二分檢索（折半查找）算法的基本過程。7. 背包問題的目標(biāo)函數(shù)和貪心算法最優(yōu)化量度相同嗎8. 采用回溯法求解的問題，其解如何表示有什么規(guī)定9. 回溯法的搜索特點(diǎn)是什么10. n 皇后問題回溯算法的判別函數(shù)place 的基本流程是什么11. 為什么用分治法設(shè)計(jì)的算法一般有遞歸調(diào)用12. 為什么要分析最壞情況下的算法時(shí)間復(fù)雜性13. 簡(jiǎn)述漸進(jìn)時(shí)間復(fù)雜性上界的定義。14. 二分檢索算法最多的比較次數(shù)15. 快速排序算法最壞情況下需要多少次比較運(yùn)算16. 貪

22、心算法的基本思想17. 回溯法的解（X1,X2，-xn）的隱約束一般指什么18. 闡述歸并排序的分治思路。19. 快速排序的基本思想是什么。20. 什么是直接遞歸和間接遞歸消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)21. 什么是哈密頓環(huán)問題22. 用回溯法求解哈密頓環(huán)，如何定義判定函數(shù)23. 請(qǐng)寫出 prim 算法的基本思想。參考答案： 1. 確定性、可實(shí)現(xiàn)性、輸入、輸出、有窮性2 . 分析算法占用計(jì)算機(jī)資源的情況，對(duì)算法做出比較和評(píng)價(jià)，設(shè)計(jì)出額更好的算法。3 . 算法的時(shí)間復(fù)雜性與問題的規(guī)模相關(guān)，是問題大小 n 的函數(shù)。4 .當(dāng)問題的規(guī)模n趨向無窮大時(shí)，影響算法效率的重要因素是T(n)的數(shù)量級(jí)， 而其他

23、因素僅是使時(shí)間復(fù)雜度相差常數(shù)倍，因此可以用T(n)的數(shù)量級(jí)(階)評(píng)價(jià) 算法。時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)(階)稱為漸進(jìn)時(shí)間復(fù)雜性。5 . 最壞情況下的時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性考察的是n 固定時(shí)， 不同輸入實(shí)例下的算法所耗時(shí)間。最壞情況下的時(shí)間復(fù)雜性取的輸入實(shí)例中最大的時(shí)間復(fù)雜度：W(n) = max T(q I) , I Dn平均時(shí)間復(fù)雜性是所有輸入實(shí)例的處理時(shí)間與各自概率的乘積和：A(n)應(yīng) P(I)T(q I) IC Dn6 .設(shè)輸入是一個(gè)按非降次序排列的元素表 Ai: j和x,選取A(i+j)與x比 較，如果 A(i+jy2=x,則返回(i+j)/2,如果 A(i+jy2<x,則

24、Ai: (i+j)/2-1找 x, 否則在A (i+j)/2+1: j找x。上述過程被反復(fù)遞歸調(diào)用?；厮莘ǖ乃阉魈攸c(diǎn)是什么7 . 不相同。目標(biāo)函數(shù)：獲得最大利潤(rùn)。最優(yōu)量度：最大利潤(rùn) / 重量比。8 .問題的解可以表示為n元組：(xi,x2j-xn), xiCS, S為有窮集合，xiCS, (xi,x2/-xn)具備完備性，即(xi,x2/-xn)是合理的，則(xi,x2Jfi) (i<n) 一 定合理。9 . 在解空間樹上跳躍式地深度優(yōu)先搜索， 即用判定函數(shù)考察xk 的取值， 如果 xk 是合理的就搜索xk 為根節(jié)點(diǎn)的子樹，如果xk 取完了所有的值，便回溯到 xk-1。10 . 將第 K

25、 行的皇后分別與前k-1 行的皇后比較，看是否與它們相容，如果不相容就返回false,測(cè)試完畢則返回true。11 . 子問題的規(guī)模還很大時(shí)， 必須繼續(xù)使用分治法， 反復(fù)分治， 必然要用到遞歸。12 最壞情況下的時(shí)間復(fù)雜性決定算法的優(yōu)劣， 并且最壞情況下的時(shí)間復(fù)雜性較平均時(shí)間復(fù)雜性游可操作性。13 .T(n足某算法的時(shí)間復(fù)雜性函數(shù)，f(n)是一簡(jiǎn)單函數(shù)，存在正整數(shù)No和C, nNo,有 T(n)<f(n),這種關(guān)系記作 T(n)=O(f(n)>14 .二分檢索算法的最多的比較次數(shù)為log n 。15 .最壞情況下快速排序退化成冒泡排序，需要比較n2 次。16 . 是一種依據(jù)最優(yōu)化量

26、度依次選擇輸入的分級(jí)處理方法。基本思路是：首先根據(jù)題意， 選取一種 量度標(biāo)準(zhǔn)； 然后 按這種量度標(biāo)準(zhǔn)對(duì)這n 個(gè)輸入排序， 依次選擇輸入量加入部分解中。 如果當(dāng)前這個(gè)輸入量的加入， 不滿足約束條件， 則不把此輸入加到這部分解中。17 .回溯法的解(xi,x2,-xn)的隱約束一股指?jìng)€(gè)元素之間應(yīng)滿足的某種關(guān)系。18 . 講數(shù)組一分為二，分別對(duì)每個(gè)集合單獨(dú)排序，然后將已排序的兩個(gè)序列歸并成一個(gè)含 n 個(gè)元素的分好類的序列。 如果分割后子問題還很大， 則繼續(xù)分治，直到一個(gè)元素。19 .快速排序的基本思想是在待排序的 N 個(gè)記錄中任意取一個(gè)記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關(guān)

27、鍵字比該記錄關(guān)鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間， 這個(gè)過程稱作一次快速排序。 之后重復(fù)上述過程， 直到每一部分內(nèi)只有一個(gè)記錄為止。20 .在定義一個(gè)過程或者函數(shù)的時(shí)候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成分，既調(diào)用它自己本身， 這稱為直接遞歸。 如果過程或者函數(shù)P 調(diào)用過程或者函數(shù)Q，Q又調(diào)用P,這個(gè)稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)。21 .哈密頓環(huán)是指一條沿著圖G的N條邊環(huán)行的路徑，它的訪問每個(gè)節(jié)點(diǎn)一 次并且返回它的開始位置。22 .當(dāng)前選擇的節(jié)點(diǎn)Xk是從未到過的節(jié)點(diǎn)，即XkwXi(i=1,2,k-1),且C(Xk-1, Xk戶00,如果

28、k=j,則 c(xk, X1) woo。23 . 思路是：最初生成樹T 為空，依次向內(nèi)加入與樹有最小鄰接邊的 n-1 條邊。 處理過程： 首先加入最小代價(jià)的一條邊到 T， 根據(jù)各節(jié)點(diǎn)到 T 的鄰接邊排序， 選擇最小邊加入， 新邊加入后， 修改由于新邊所改變的鄰接邊排序， 再選擇下一 條邊加入，直至加入 n-1 條邊。、復(fù)雜性分析1、 MERGESORT(lo，whigh)if low<high ；then mid (low, high)/2；MERGESORT(lo，wmid)；MERGESORT(mid+，1 high)；MERGE(low， mid ， high)；endifend

29、MERGESORTT(n) 2(2T(n/4) cn/2) cn14T(n/4) 2cn12kT(1) kcnan cnlogn答: 1、 遞歸方程anT(n) 2T(n/2) cn n設(shè) n=2k解遞歸方程：2、 procedure S1(P， W ， M ， X， n)i1; a 0while i< n doif W(i)>M then return endifaa+iii+1 ;repeatend解：i1 ;曠0時(shí)間為：O(1)while i< n do 循環(huán) n 次循環(huán)體內(nèi)所用時(shí)間為 O(1)所以 總時(shí)間為 :T(n)=O(1)+ nO(1)= O(n)PARTITI

30、ON(m,p)Integer m,p,i;global A(m:p-1)v A(m);imlooploop ii+1 until A(i) >v repeatloop pp-1 until A(p) < v repeatif i<pthen call INTERCHANGE(A(i),A(p)else exitendifrepeatA(m) A(p)；A(p) - vEnd PARTITION解：最多的查找次數(shù)是p-m+1 次F1(n)if n<2 then return(1)else return(F2(2,n,1,1)endifend F1procedure F2(

31、i,n,x,y)if i < nthen call F2(i+1,n,y,x+y)endifreturn(y)end F2解：F2 (2, n,1,1)的時(shí)間復(fù)雜度為：T(n)=O(n-2);因?yàn)閕&n時(shí)要遞歸調(diào)用F2, 一共是n-2次當(dāng)n = 1時(shí)F1的時(shí)間為0(1)當(dāng)n>1時(shí)F1(n)的時(shí)間復(fù)雜度與F2(2,n,1,1)的時(shí)間復(fù)雜度相同即為為0(n)MAX(A,n,j)xmax A(1);j1fo門2 to n doif A(i)>xmax then xmax A(i); ji;endifrepeatend MAX解：xmaxA(1);j1時(shí)間為：0(1)fo門2

32、 to n do循環(huán)最多n-1次所以 總時(shí)間為 :T(n)=0(1)+ (n-1)0(1)= 0(n)BINSRCH(A,n,x,j)integer low,high,mid,j,n;low1;highnwhile low < high domid|_(low+high)/2_|case:x<A(mid):highmid-1:x>A(mid):lowmid+1:else:jmid; returnendcaserepeatj-0end BINSRCH解：log2n+1三、算法理解1、寫出多段圖最短路經(jīng)動(dòng)態(tài)規(guī)劃算法求解下列實(shí)例的過程，并求出最優(yōu)值。各邊的代價(jià)如下:C(4,5)=2

33、, C(4,6)=1C(1,2)=3C(1,3)=5 , C(1,4)=2C(2,6)=8 , C(2,7)=4 , C(3,5)=5 , C(3,6)=4,C(5,8)=4 C(6,8)=5 , C(7,8)=6解： Cost(4,8)=0Cost(3,7)= C(7,8)+0=6， D5=8Cost(3,6)= C(6， 8)+0=5, D6=8Cost(3,5)= C(5， 8)+0=4 D7=8Cost(2,4)= minC(4， 6)+ Cost(3,6), C(4， 5)+ Cost(3,5)= min1+ 5, 2+4=6 D4=6Cost(2,3)= minC(3， 6)+ C

34、ost(3,6) = min4+5=9 D3=5Cost(2,2)= minC(2， 6)+ Cost(3,6), C(2， 7)+ Cost(3,7)= min8+5, 4+6=10 D2=7Cost(1,1)= minC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4)= min3+10, 5+9,2+6= 8D1=44-6-82、寫出 maxmin 算法對(duì)下列實(shí)例中找最大數(shù)和最小數(shù)的過程。數(shù)組 A=(48,12,61,3,5,19,32,7)解：寫出 maxmin 算法對(duì)下列實(shí)例中找最大數(shù)和最小數(shù)的過程。數(shù)組 A=()5,19,3

35、2,75,1932,71932, 571、 48,12,61,3,2、 48,1261,33、 4861, 1234、 61 32355、 6133、快速排序算法對(duì)下列實(shí)例排序，算法執(zhí)行過程中，寫出數(shù)組A第一次被分割的過程。A=(65,70,75,80,85,55,50,2)解：第一個(gè)分割元素為654、歸并排序算法對(duì)下列實(shí)例排序，寫出算法執(zhí)行過程。1)(2)(3)(4)(5)(6)(7)(8)iP6570-75-80-855550杷22865275-80 -85 55f 507037652508085*5575704665250558580757046557075808565502A=(48,

36、12,61,3,5,19,32,7)解:48,12,61,35,19,32,748,1261,35,1932,712,483,615,197,323, 12, 48, 615, 7, 19,323,5, 7,12, 19, 32, 48,615、寫出圖著色問題的回溯算法的判斷Xk是否合理的過程。解:i-0while i<k doif Gk,i=1 and Xk= Xi thenreturn falsei-i+1repeatif i= k then return true6、對(duì)于下圖，寫出圖著色算法得出一種著色方案的過程解：K 1X1 1 ,返回 trueX21,返回 false; X2尸

37、X2+1=2,返回 trueX31，返回 false; X3尸X3+1=2,返回 false;X3X3+1=3,返回 trueX41,返回 false; X4 X4+1=2,返回 false;X4 X4+1=3,返回 true 找到一個(gè)解 (1, 2, 3, 3)7、寫出第7題的狀態(tài)空間樹。解:8、寫出歸并排序算法對(duì)下列實(shí)例排序的過程。(6,2,9,3,5,1,8,7)5,1,8,7分成兩個(gè)子解：調(diào)用第一層次 6,2,9,3問題調(diào)用第二層次6,29,35,18,7 分成四個(gè)子問題調(diào)用第三層次6 29 35 18 7 分成八個(gè)子問題調(diào)用第四層次 只有一個(gè)元素返回上一層第三層歸并2 ,63, 91

38、,57,8 返回上一層第二層歸并2 ,3,6, 91,5,7,8返回上一層第一層歸并1, 2 ,3, 5 ,6, 7, 8,9 排序結(jié)束，返回主函數(shù)9、寫出用背包問題貪心算法解決下列實(shí)例的過程。P=(18,12,4,1)W=(12,10,8,3)M=25解：實(shí)例符合P(i)/W(i)P(i+1)/W(i+1)的順序。CU 25k 0W1< CU: x1 1; CU CU-W1=13;W2< CU: x2 1; CU CU-W2=3;W3>CU:x3CU/ W3=38;實(shí)例的解為： ( 1， 1， 3/8， 0)11、有一個(gè)有序表為 1， 3， 9， 12， 32， 41， 4

39、5， 62， 75， 77， 82， 95， 100，當(dāng)使用二分查找值為82 的結(jié)點(diǎn)時(shí)，經(jīng)過多少次比較后查找成功并給出過程。解：有一個(gè)有序表為 1， 3， 9， 12， 32， 41， 45， 62， 75， 77， 82， 95， 100，當(dāng)使用二分查找值為82 的結(jié)點(diǎn)時(shí)，經(jīng)過多少次比較后查找成功并給出過程。一共要要執(zhí)行四次才能找到值為 82 的數(shù)。12、使用prim 算法構(gòu)造出如下圖 G 的一棵最小生成樹。1dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;dist(1,3)=1;dist(2,3)=5;dist(3,4

40、)=5;dist(3,6)=4;dist(5,3)=6解：使用普里姆算法構(gòu)造出如下圖G的一棵最小生成樹dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=613、有如下函數(shù)說明int f(int x,int y)f=x Mod y +1;已知a=10,b=4,c=5則執(zhí)行k=f(f(a+c,b),f(b,c)后,k的值是多少并寫出詳細(xì)過程。解：有如下函數(shù)說明int f(int x,int y)f=x Mod y

41、+1;已知a=10,b=4,c=5則執(zhí)行k=f(f(a+c,b),f(b,c)后,k的值是多少并寫出詳細(xì)過程。K的值是514、McCathy函數(shù)定義如下:當(dāng) x>100 時(shí) m(x)=x-10;當(dāng) x<=100 時(shí) m(x)=m(m(x+11);編寫一個(gè)遞歸函數(shù)計(jì)算給定x的m(x)值。解： McCathy 函數(shù)定義如下：當(dāng) x>100 時(shí) m(x)=x-10;當(dāng) x<=100 時(shí) m(x)=m(m(x+11);編寫一個(gè)遞歸函數(shù)計(jì)算給定x的m(x)值。int m(int x)int y;if(x>100) return(x-100);elsey=m(x+11);re

42、turn (m(y);15、 設(shè)計(jì)一個(gè)算法在一個(gè)向量A 中找出最大數(shù)和最小數(shù)的元素。解：設(shè)計(jì)一個(gè)算法在一個(gè)向量A 中找出最大數(shù)和最小數(shù)的元素。Void maxmin(A,n)Vector A;int n;int max,min,i;max=A1;min=A1;for(i=2;i<=n;i+)if(Ai>max)max=Ai;else if(Ai<min)min=Ai;printf( max=%d,min=%dn”,max,min);四、設(shè)計(jì)算法1 .設(shè)有n項(xiàng)獨(dú)立的作業(yè)1,2,n,由m臺(tái)相同的機(jī)器加工處理。作業(yè)i所需 要的處理時(shí)間為tio約定：任何一項(xiàng)作業(yè)可在任何一臺(tái)機(jī)器上處理

43、，但未完工前 不準(zhǔn)中斷處理；任何作業(yè)不能拆分更小的子作業(yè)。多機(jī)調(diào)度問題要求給出一種調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間 內(nèi)由m臺(tái)機(jī)器處理完。設(shè)計(jì)算法，并討論是否可獲最優(yōu)解。解：對(duì)于處理機(jī)j,用Sj表示處理機(jī)j已有的作業(yè)數(shù)，用Pj,k表示處理機(jī) j的第k個(gè)作業(yè)的序號(hào)。1)將作業(yè)按照t1 >t2>>tn排序2 ) S1:m清零j0設(shè)有n種面值為：d1>d2>>dn的錢幣，需要找零錢M,如何選擇錢幣dk,的數(shù)目Xk,滿足d1XXi+-dnXXn M ,使得X + Xn最小請(qǐng)選擇貪心策略，并設(shè)計(jì)貪心算法。解：貪心原則：每次選擇最大面值硬幣。CUM;i 1;X

44、0有 n 個(gè)物品，已知 n=7,禾潤(rùn)為 P=(10,5,15,7,6,18,3)重量 W=(2,3,5,7,1,4,1),背包容積M=15，物品只能選擇全部裝入背包或不裝入背 包，設(shè)計(jì)貪心算法，并討論是否可獲最優(yōu)解。解：定義結(jié)構(gòu)體數(shù)組G,將物品編號(hào)、利潤(rùn)、重量作為一個(gè)結(jié)構(gòu)體：例如Gk=1,10,2求最優(yōu)解，按利潤(rùn)/重量的遞減序，有5,6,1,61,10,2,56,18,4,92 3,15,5,3 7,3,1,32,5,3,53 4,7,7,1算法procedure KNAPSACKPW, M, X, n)設(shè)計(jì)只求一個(gè)哈密頓環(huán)的回溯算法。解： Hamiltonian(n)k 1; xk 0;Wh

45、ile k>0 doxk xk+1;while B(k)=false and xk< n doxk xk+1; repeatIf xk < n thenif k=n then print x; return else k k+1; xk0; endifelse Q k-1endifrepeatendprocedure B(k) Gxk-1,xk w 1 then return false;fo門1 to k-1 doif xi=xk then return false;endifrepeatreturn true;5利用對(duì)稱性設(shè)計(jì)算法，求n 為偶數(shù)的皇后問題所有解。解：利用對(duì)

46、稱性設(shè)計(jì)算法，求n 為偶數(shù)的皇后問題所有解。procedure NQUEENS1(n) a -042l f(n) (g(n) f(n) (g(n) f(n) log n ;g(n) log n 5;f(n) 2n;g(n) 100n2; f(n) 2n;g(n) 3n; log n2 (log n 5) 2n (100n2)2n(3n ) R r1, r2,., rn) n r1, r2 ,.,rn RPerm(4 分)cout<<endl;else for(int i=k;i<=m;i+)if(ok(list,k,i)swap(listk,listi);Perm(list,

47、k+1,m);swap(listk,listi);(8 分);其中 ok 用于判別重復(fù)元素。Template<class>int ok(Type list,int k,int i)if(i>k)for(int t=k;t<I;t+)if(listt= =listi) return 0;return 1;(13分).3、試用分治法對(duì)一個(gè)有序表實(shí)現(xiàn)二分搜索算法。( 12 分)解：解答如下：Template<class>int BinarySearch(Type a,const Type& x,int n)( 4 分)if(x= =amiddle) ret

48、urn middle+1;if(x>amiddle) left=middle+1;else right=middle-1;)return -1;(12分).4、試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)0-1閉包問題。(15分)解：解答如下：Template<class>void Knapsack(Type v,int w,int c,int n,Type *m)Int jMax=min(wn-1,c);for(int j=0;j<=jMax;j+) mnj=0;for(int j=wn;j<=c;j+) mnj=vn;(5分)for(int i=n-1;i>1;i-)jMax=

49、min(wi-1,c);for(int j=0;j<=jMax;j+) mij=mi+1j;for(int j=wi;j<=c;j+) mij=max(mi+1j,mi+1j- wi+vi);(-8分);m1c=m2c;if(c>=w1) m1c=max(m1c,m2c- w1+v1);(T0分)Template<class>Void Traceback(Type *m,int w,int c,int n,int x)for(int i=1;i<n;i+)if(mic= =mi+1c) xi=0;(12分)else xi=1,c-=wi;xn=(mnc)1:

50、0;(15分).5、試用貪心算法求解下列問題：將正整數(shù)n分解為若干個(gè)互不相同的自然數(shù)之和，使這些自然數(shù)的乘積最大。(15分)解：解答如下：void dicomp(int n,int a)k=1;if(n<3) a1=0;return;if(n<5) ak=1;a+k=n-1;return;(5 分)a1=2;n-=2;while(n>ak)k+;ak=ak-1+1;n-=ak; (10分).if(n= =ak) ak+;n-;for(int i=0;i<n;i+) ak-i+;(15分).6、試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)最大子矩陣和問題：求m n矩陣A的一個(gè)子矩陣，使其各元素之

51、各為最大。(15分)解：解答如下:int MaxSum2(int m,int n,int *a) (int sum=0;int *b=new intn+1;(5分)for(int i=1;i<=m;i+)for(int k=1;k<=n;k+) bk=0;for(int j=i;j<=m;j+)for(int k=1;k<=n;k+) bk+=ajk;int max=MaxSum(n,b);if(max>sum) sum=max;return sum; 。分)int MaxSum(int n,int *a)int sum=0,b=0;for(int i=1;i&l

52、t;=n;i+)if(b>0) b+=ai;else b=ai;if(b>sum) sum=b;Return sum; (15分)7、試用回溯法解決下列整數(shù)變換問題：關(guān)于整數(shù)i的變換f和g定義如下:f(i) 3i;g(i)i/2。對(duì)于給定的兩個(gè)整數(shù)n和m,要求用最少的變換f和g變換次數(shù)將n變?yōu)閙 o (18分)解：解答如下：void compute()(k=1;while(!search(1,n)k+;if(k>maxdep) break;init();)； (6分).if(found) output();else cout« ” No Solution! ” «endl;)(9分).b