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

算法分析與設(shè)計(jì)試題庫(一)一、 選擇題 1.應(yīng)用Johnson法則的流水作業(yè)調(diào)度采用的算法是（D）A. 貪心算法 B. 分支限界法 C.分治法 D. 動(dòng)態(tài)規(guī)劃算法2.Hanoi塔問題如下圖所示?，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) 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(minf(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(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); A.void backtrack (int t) if (t>n) output(x); else for (int i=0;i<=1;i+) xt=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+) xt=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(xt, xi); if (legal(t) backtrack(t+1); 10. 回溯法的效率不依賴于以下哪一個(gè)因素？（C ）A. 產(chǎn)生xk的時(shí)間；B. 滿足顯約束的xk值的個(gè)數(shù)；C. 問題的解空間的形式； D. 計(jì)算上界函數(shù)bound的時(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ī)處理所有長度為n的輸入時(shí)，在某條帶上所使用過的最大方格數(shù)。B. k帶圖靈機(jī)處理所有長度為n的輸入時(shí)，在k條帶上所使用過的方格數(shù)的總和。C. k帶圖靈機(jī)處理所有長度為n的輸入時(shí)，在k條帶上所使用過的平均方格數(shù)。D. k帶圖靈機(jī)處理所有長度為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)<cg(n) ；D. O(g(n) = f(n) | 對(duì)于任何正常數(shù)c>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)<cg(n) ；D. (g(n) = f(n) | 對(duì)于任何正常數(shù)c>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+=aj;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 ）。1413121110987654fi122886535031Si1110987654321i3. 所謂貪心選擇性質(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)的最長路徑的長度為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<Typew, Typep>:Bound(int i)/ 計(jì)算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 結(jié)點(diǎn)的上界 / 以物品單位重量價(jià)值遞減序裝入物品 while (i <= n && wi <= cleft) cleft -= wi; b += pi; i+; / 裝滿背包 if (i <= n) （b += pi/wi * cleft）; return b;11. 用回溯法解布線問題時(shí)，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為的方格陣列，擴(kuò)展每個(gè)結(jié)點(diǎn)需O(1)的時(shí)間，L為最短布線路徑的長度，則算法共耗時(shí) ( O(mn) )，構(gòu)造相應(yīng)的最短距離需要（O(L)）時(shí)間。for (int i = 0; i < NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col; if (gridnbr.rownbr.col = 0) / 該方格未標(biāo)記 gridnbr.rownbr.col = gridhere.rowhere.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(akj= =1)&&(xj= =xk) return false;return true;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ī)器。因此，在可行的分配中每臺(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. 已知非齊次遞歸方程： ，其中，b、c是常數(shù)，g(n)是n的某一個(gè)函數(shù)。則f(n)的非遞歸表達(dá)式為：?，F(xiàn)有Hanoi塔問題的遞歸方程為： ，求h(n)的非遞歸表達(dá)式。解：利用給出的關(guān)系式，此時(shí)有：b=2, c=1, g(n)=1, 從n遞推到1，有：3. 單源最短路徑的求解。問題的描述：給定帶權(quán)有向圖（如下圖所示）G =(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。解法：現(xiàn)采用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑。請(qǐng)將此過程填入下表中。432110030maxint10-1初始dist5dist4dist3dist2uS迭代4. 請(qǐng)寫出用回溯法解裝載問題的函數(shù)。裝載問題：有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱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 + 1); r += wi; 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) 解答：斜線標(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ìn)入左子樹是增加，因此，可以在算法每一次進(jìn)入左子樹時(shí)更新bestw的值。7. 最長公共子序列問題：給定2個(gè)序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。 由最長公共子序列問題的最優(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時(shí)，空序列是Xi和Yj的最長公共子序列。故此時(shí)Cij=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：在程序中，bij記錄Cij的值是由哪一個(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+) 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-1j>=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; （2） 函數(shù)LCS實(shí)現(xiàn)根據(jù)b的內(nèi)容打印出Xi和Yj的最長公共子序列。請(qǐng)?zhí)顚懗绦蛑械目崭瘢允购瘮?shù)LCS完成構(gòu)造最長公共子序列的功能（請(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 (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，x，b);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ì)試題庫(二)一、簡(jiǎn)要回答下列問題 ：1. 算法重要特性是什么？ 2. 算法分析的目的是什么？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. 貪心算法的基本思想？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í)，而其他因素僅是使時(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(n，I) , IDn平均時(shí)間復(fù)雜性是所有輸入實(shí)例的處理時(shí)間與各自概率的乘積和：A(n) =P(I)T(n，I) IDn6. 設(shè)輸入是一個(gè)按非降次序排列的元素表Ai：j 和x，選取A(i+j)/2與x比較，如果A(i+j)/2=x，則返回(i+j)/2，如果A(i+j)/2<x，則Ai：(i+j)/2-1找x，否則在A (i+j)/2+1：j 找x。上述過程被反復(fù)遞歸調(diào)用?；厮莘ǖ乃阉魈攸c(diǎn)是什么7. 不相同。目標(biāo)函數(shù)：獲得最大利潤。最優(yōu)量度：最大利潤/重量比。8. 問題的解可以表示為n元組：（x1,x2,xn），xiSi, Si為有窮集合，xiSi, （x1,x2,xn）具備完備性，即（x1,x2,xn）是合理的，則（x1,x2,xi）(i<n)一定合理。9. 在解空間樹上跳躍式地深度優(yōu)先搜索，即用判定函數(shù)考察xk的取值，如果xk是合理的就搜索xk為根節(jié)點(diǎn)的子樹，如果xk取完了所有的值，便回溯到xk-1。10. 將第K行的皇后分別與前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)化量度依次選擇輸入的分級(jí)處理方法?；舅悸肥牵菏紫雀鶕?jù)題意，選取一種量度標(biāo)準(zhǔn)；然后按這種量度標(biāo)準(zhǔn)對(duì)這n個(gè)輸入排序，依次選擇輸入量加入部分解中。如果當(dāng)前這個(gè)輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。17回溯法的解（x1,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)鍵字比該記錄關(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),即XkXi(i=1,2,k-1)，且C(Xk-1, Xk)，如果k=-1，則C(Xk, X1) 。23. 思路是：最初生成樹T為空，依次向內(nèi)加入與樹有最小鄰接邊的n-1條邊。處理過程：首先加入最小代價(jià)的一條邊到T，根據(jù)各節(jié)點(diǎn)到T的鄰接邊排序，選擇最小邊加入，新邊加入后，修改由于新邊所改變的鄰接邊排序，再選擇下一條邊加入，直至加入n-1條邊。二、復(fù)雜性分析1、 MERGESORT(low，high) if low<high； then mid(low，high)/2； MERGESORT(low，mid)； MERGESORT(mid+1，high)； MERGE(low，mid，high)； endif end MERGESORT答: 1、 遞歸方程 設(shè)n=2k解遞歸方程：2、 procedure S1(P，W，M，X，n) i1; a0 while i n do if W(i)>M then return endif aa+i ii+1 ; repeat end 解： i1 ;s0 時(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)3.procedure PARTITION(m,p) Integer m,p,i;global A(m:p-1) vA(m);im looploop ii+1 until A(i) v repeatloop pp-1 until A(p) v repeat if i<p then call INTERCHANGE(A(i),A(p) else exit endif repeat A(m) A(p);A(p) v End PARTITION解：最多的查找次數(shù)是p-m+1次 4.procedure F1(n) if n<2 then return(1) else return(F2(2,n,1,1) endif end F1 procedure F2(i,n,x,y) if in then call F2(i+1,n,y,x+y) endif return(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)n1時(shí)F1(n)的時(shí)間為 O(1)當(dāng)n>1時(shí)F1(n)的時(shí)間復(fù)雜度與F2(2,n,1,1)的時(shí)間復(fù)雜度相同即為為 O(n) 5.procedure MAX(A,n,j) xmaxA(1);j1 for i2 to n do if A(i)>xmax then xmaxA(i); ji;endif repeatend MAX 解：xmaxA(1);j1 時(shí)間為：O(1) for i2 to n do 循環(huán)最多n-1次 所以 總時(shí)間為:T(n)=O(1)+ (n-1)O(1)= O(n)6.procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low1;highn while lowhigh do mid|_(low+high)/2_| case :x<A(mid):highmid-1:x>A(mid):lowmid+1:else:jmid; return endcase repeat j0 end BINSRCH解：log2n+1三、算法理解1、寫出多段圖最短路經(jīng)動(dòng)態(tài)規(guī)劃算法求解下列實(shí)例的過程，并求出最優(yōu)值。52863174各邊的代價(jià)如下：C(1,2)=3， C(1,3)=5 ，C(1,4)=2 C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4， C(4,5)=2，C(4,6)=1C(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)+ Cost(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=414682、 寫出maxmin算法對(duì)下列實(shí)例中找最大數(shù)和最小數(shù)的過程。數(shù)組 A=(48,12,61,3,5,19,32,7) 解：寫出maxmin算法對(duì)下列實(shí)例中找最大數(shù)和最小數(shù)的過程。數(shù)組 A=() 1、 48,12,61,3, 5,19,32,72、48,12 61,3 5,19 32,73、 4861, 123 1932，574、 6132 355、 61 33、 快速排序算法對(duì)下列實(shí)例排序，算法執(zhí)行過程中，寫出數(shù)組A第一次被分割的過程。 A=(65,70,75,80,85,55,50,2)解：第一個(gè)分割元素為65(1) (2) (3) (4) (5) (6) (7) (8) i p65 70 75 80 85 55 50 2 2 865 2 75 80 85 55 50 70 3 765 2 50 80 85 55 75 70 4 665 2 50 55 85 80 75 70 4 655 70 75 80 85 65 50 24、 歸并排序算法對(duì)下列實(shí)例排序，寫出算法執(zhí)行過程。 A=(48,12,61,3,5,19,32,7) 解： 48,12,61,3 5,19,32,748,12 61,3 5,19 32,712,48 3,61 5,19 7,32 3, 12, 48, 61 5, 7, 19，323,5, 7,12，19，32，48,61 5、 寫出圖著色問題的回溯算法的判斷Xk是否合理的過程。解：i0while i<k do if Gk,i=1 and Xk= Xi then return false ii+1repeat if i= k then return true6、 對(duì)于下圖，寫出圖著色算法得出一種著色方案的過程。2314解：K1X1 1 , 返回 trueX21,返回false; X2X2+1=2, 返回 trueX31 ,返回false; X3X3+1=2, 返回false;X3X3+1=3, 返回 true X41, 返回false; X4X4+1=2, 返回false;X4X4+1=3, 返回 true找到一個(gè)解 （1，2，3，3）7、 寫出第7題的狀態(tài)空間樹。解：X1=1X2=2X3=33X4=338、寫出歸并排序算法對(duì)下列實(shí)例排序的過程。(6,2,9,3,5,1,8,7)解：調(diào)用第一層次 6,2,9,3 5,1,8,7 分成兩個(gè)子問題 調(diào)用第二層次 6,2 9,3 5,1 8,7 分成四個(gè)子問題 調(diào)用第三層次 6 2 9 3 5 1 8 7 分成八個(gè)子問題 調(diào)用第四層次 只有一個(gè)元素返回上一層第三層歸并 2 ,6 3, 9 1,5 7,8 返回上一層第二層歸并 2 ,3,6, 9 1,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)的順序。 CU25,X0 W1< CU: x11; CUCU-W1=13; W2< CU: x21; CUCU-W2=3;W3>CU: x3CU/ W3=3/8;實(shí)例的解為：（1，1，3/8，0）11、有一個(gè)有序表為1，3，9，12，32，41，45，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的一棵最小生成樹。124356dist(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)=6解：使用普里姆算法構(gòu)造出如下圖G的一棵最小生成樹。124356dist(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)=61316136412645126343313、有如下函數(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 +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);else y=m(x+11); return (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í)間為ti。約定：任何一項(xiàng)作業(yè)可在任何一臺(tái)機(jī)器上處理，但未完工前不準(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è)按照t1t2tn排序2）S1:m清零 j0 /從第一個(gè)處理機(jī)開始安排3) for i1 to n do /安排n個(gè)作業(yè) jj mod m +1 /選下一個(gè)處理機(jī)SjSj+1; Pj,Sji ； Repeat2. 設(shè)有n種面值為:d1d2dn的錢幣，需要找零錢M，如何選擇錢幣dk，的數(shù)目Xk，滿足 d1XidnXn=M ，使得XiXn 最小 請(qǐng)選擇貪心策略，并設(shè)計(jì)貪心算法。解：貪心原則：每次選擇最大面值硬幣。CUM;i1;X0 / X為解向量While CU0 do XiCU div di / Xi為第i中硬幣數(shù)CUCU-di*Xiii+1;repeat3. 有n個(gè)物品，已知n=7, 利潤為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)、利潤、重量作為一個(gè)結(jié)構(gòu)體：例如Gk=1,10,2求最優(yōu)解，按利潤/重量的遞減序，有 5,6,1,6 1,10,2,56,18,4,9/2 3,15,5,3 7,3,1,32,5,3,5/3 4,7,7,1 算法 procedure KNAPSACK(P，W，M，X，n) /P(1：n)和W(1；n)分別含有按 P(i)/W(i)P(i+1)/W(i+1)排序的n件物品的效益值 和重量。M是背包的容量大小，而x(1：n)是解向量/ real P(1：n)，W(1：n)，X(1：n)，M，cu； integer i，n； X0 /將解向量初始化為零/ cuM /cu是背包剩余容量/ for i1 to n do if W(i)>cu then exit endif X(i) 1 cucu-W(i) repeat end GREEDY-KNAPSACK 根據(jù)算法得出的解： X=（1,1,1,1,1,0,0）獲利潤52， 而解（1,1,1,1, 0, 1,0）可獲利潤54 因此貪心法不一定獲得最優(yōu)解。4. 設(shè)計(jì)只求一個(gè)哈密頓環(huán)的回溯算法。解：Hamiltonian(n)k1; xk 0; While k>0 do xk xk+1; while B(k)=false and xkn do xk xk+1; repeat If xkn then if k=n then print x; return else k k+1; xk0; endif else k k-1 endifrepeatendprocedure B(k) Gxk-1,xk 1 then return false; for i1 to k-1 do if xi=xk then return false;endif repeat return true; 5利用對(duì)稱性設(shè)計(jì)算法，求n為偶數(shù)的皇后問題所有解。解：利用對(duì)稱性設(shè)計(jì)算法，求n為偶數(shù)的皇后問題所有解。procedure NQUEENS1(n)a0 /計(jì)數(shù)器清零X(1)0；k1 /k是當(dāng)前行；X(k)是當(dāng)前列/ While k>0 do /對(duì)所有的行執(zhí)行以下語句/1) X(k)X(k)+1 /移到下一列/While X(k)n and not PLACE(k) do 2) X(k)X(k)十l if X(k)n then if k=n / then print(X)，aa+1 /找到一個(gè)解計(jì)數(shù)器a加1/ if a=n/2 then return / 找到n/2個(gè)解算法結(jié)束 3) else kk+1；X(k)0； 4) else kk1 /回溯/ end NQUEENS 算法分析與設(shè)計(jì)試題庫(三)1、對(duì)于下列各組函數(shù)f(n)和g(n)，確定f(n)=O(g(n)或或，并簡(jiǎn)述理由。（12分）(1) (2) (3) 解：簡(jiǎn)答如下： （1），（2），（3）2、試用分治法實(shí)現(xiàn)有重復(fù)元素的排列問題：設(shè)是要進(jìn)行排列的個(gè)元素，其中元素可能相同，試計(jì)算的所有不同排列。（13分）解：解答如下： Template<class Type>void Perm(Type list,int k,int m) if(k= =m