算法分析期末試題集答案(6套)

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

2、;0)hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);C. voidhanoi(intn,intC,intB,intA)if(n>0)hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);D. voidhanoi(intn,intC,intA,intB)if(n>0)hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);3.動態(tài)規(guī)劃算法的基本要素為(C)A.最優(yōu)子結構性質與貪心選擇性質B.重疊子問題性質與貪心選擇性質C.最優(yōu)子結構性質與重疊子問題性質D.預排序與遞

3、歸調(diào)用4 .算法分析中，記號。表示(B),記號表示(A),記號表示(D)A.漸進下界B.漸進上界C.非緊上界D.緊漸進界E.非緊下界5 .以下關于漸進記號的性質是正確的有：(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)解的問題，一般具有的重要性質為：(A)A.最優(yōu)子結構性質與貪心選擇性質B.重疊子問題性質與貪心選擇性質C.最優(yōu)子結構性質與重疊子問題性質D.預排序與遞歸調(diào)用7

4、 .回溯法在問題的解空間樹中，按（D）策略，從根結點出發(fā)搜索解空間樹。A.廣度優(yōu)先B.活結點優(yōu)先C.擴展結點優(yōu)先D.深度優(yōu)先8 .分支限界法在問題的解空間樹中，按（A）策略，從根結點出發(fā)搜索解空間樹A.廣度優(yōu)先B.活結點優(yōu)先C.擴展結點優(yōu)先D.深度優(yōu)先9.程序塊（A是回溯法中遍歷排列樹的算法框架程序。A.voidbacktrack(intt)if(t>n)output(x);elsefor(inti=t;i<=n;i+)swap(xt,xi);if(legal(t)backtrack(t+1);swap(xt,xi);B.voidbacktrack(intt)if(t>n)o

5、utput(x);elsefor(inti=0;i<=1;i+)xt=i;if(legal(t)backtrack(t+1);C.voidbacktrack(intt)if(t>n)output(x);elsefor(inti=0;i<=1;i+)xt=i;if(legal(t)backtrack(t-1);D.voidbacktrack(intt)if(t>n)output(x);elsefor(inti=t;i<=n;i+)swap(xt,xi);if(legal(t)backtrack(t+1);10 .回溯法的效率不依賴于以下哪一個因素（C）A. 產(chǎn)生xk

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

7、的總和。C. k帶圖靈機處理所有長度為n的輸入時，在k條帶上所使用過的平均方格數(shù)。D. k帶圖靈機處理所有長度為n的輸入時，在某條帶上所使用過的最小方格數(shù)。13. NP類語言在圖靈機下的定義為(D)A. NP=L|L是一個能在非多項式時間內(nèi)被一臺NDTMf接受的語言;B. NP=L|L是一個能在多項式時間內(nèi)被一臺NDTMf接受的語言;C. NP=L|L是一個能在多項式時間內(nèi)被一臺DTMT接受的語言;D. NP=L|L是一個能在多項式時間內(nèi)被一臺NDTMf接受的語言;14. 記號。的定義正確的是(A)。A. O(g(n)=f(n)|存在正常數(shù)c和n0使得對所有nn0有：0f(n)cg(n)；B.

8、 O(g(n)=f(n)|存在正常數(shù)c和n0使得對所有nn。有：0cg(n)f(n)；C. O(g(n)=f(n)|對于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對所有nn0有：0f(n)<cg(n)；D. O(g(n)=f(n)|對于任何正常數(shù)c>0,存在正數(shù)和n0>0使得對所有nn0有：0cg(n)<f(n);15. 記號的定義正確的是(B)。A. O(g(n)=f(n)|存在正常數(shù)c和n0使得對所有nn0有：0f(n)cg(n)；B. O(g(n)=f(n)|存在正常數(shù)c和n0使得對所有nn0有：0cg(n)f(n)；C. (g(n)=f(n)|對于任何

9、正常數(shù)c>0,存在正數(shù)和n0>0使得對所有nn0有：0f(n)<cg(n)；D. (g(n)=f(n)|對于任何正常數(shù)c>0,存在正數(shù)和n0>0使得對所有nn0有：0cg(n)<f(n)；填空題1 .下面程序段的所需要的計算時間為(O(n2)。intMaxSum(intn,int*a,int&besti,int&bestj)intsum=0;for(inti=1;i<=n;i+)intthissum=0;for(intj=i;j<=n;j+)thissum+=aj;if(thissum>sum)sum=thissum;bes

10、ti=i;bestj=j;returnsum;2 .有11個待安排的活動，它們具有下表所示的開始時間與結束時間，如果以貪心算法求解這些活動的最優(yōu)安排(即為活動安排問題：在所給的活動集合中選出最大的相容活動子集合)，得到的最大相容活動子集合為活動(1,4,8,11)。i1234567891011Si130535688212fi45678910111213143 .所謂貪心選擇性質是指（所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到）。4 .所謂最優(yōu)子結構性質是指（問題的最優(yōu)解包含了其子問題的最優(yōu)解）。5 .回溯法是指（具有限界函數(shù)的深度優(yōu)先生成法）。6 .用回溯法解題的一個顯

11、著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h（n）,則回溯法所需的計算空間通常為（O（h（n）。7 .回溯法的算法框架按照問題的解空間一般分為（子集樹）算法框架與（排歹I樹）算法框架。8 .用回溯法解0/1背包問題時，該問題的解空間結構為（子集樹）結構。9 .用回溯法解批處理作業(yè)調(diào)度問題時，該問題的解空間結構為（排列樹）結構。10 .用回溯法解0/1背包問題時，計算結點的上界的函數(shù)如下所示，請在空格中填入合適的內(nèi)容：TypepKnap<Typew,Typep>:Bound（inti）

12、/計算上界Typewcleft=c-cw;/剩余容量Typepb=cp;/結點的上界/以物品單位重量價值遞減序裝入物品while（i<=n&&wi<=cleft）cleft-=wi;b+=pi;i+;/裝滿背包if（i<=n）（b+=pi/wi*cleft）;returnb;11 .用回溯法解布線問題時，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為nm的方格陣列，擴展每個結點需0(1)的時間，L為最短布線路徑的長度，則算法共耗時(0(mn),構造相應的最短距離需要(0(L)時間for(inti=0;i<NumOfNbrs;i+)=+offseti.row

13、;=+offseti.col;if(grid叩=0)/該方格未標記grid叩=grid叩+1；if(=&&=)break;完成布線(nbr);12 .用回溯法解圖的m著色問題時，使用下面的函數(shù)OK檢查當前擴展結點的每一個兒子所相應的顏色的可用性，則需耗時(漸進時間上限)(O(m。)。BoolColor:OK(intk)/for(intj=1;j<=n;j+)if(akj=1)&&(xj=xk)returnfalse;returntrue;13 .旅行售貨員問題的解空間樹是(排列樹)解答題1.機器調(diào)度問題。問題描述：現(xiàn)在有n件任務和無限多臺的機器，任務可以在

14、機器上得到處理。每件任務的開始時間為Si,完成時間為fi,Si<fi。Si,fi為處理任務i的時間范圍。兩個任務i，j重疊指兩個任務的時間范圍區(qū)間有重疊，而并非指i，j的起點或終點重合。例如：區(qū)間1，4與區(qū)間2，4重疊，而與4，7不重疊。一個可行的任務分配是指在分配中沒有兩件重疊的任務分配給同一臺機器。因此，在可行的分配中每臺機器在任何時刻最多只處理一個任務。最優(yōu)分配是指使用的機器最少的可行分配方案。問題實例：若任務占用的時間范圍是1，4，2，5，4，5，2，6，4，7，則按時完成所有任務最少需要幾臺機器(提示：使用貪心算法)畫出工作在對應的機器上的分配情況。2.已知非齊次遞歸方程：f(

15、n)bf(n1)g(n)，其中，b、c是常數(shù)，f(0)cng(n)是n的某一個函數(shù)。則f(n)的非遞歸表達式為：f(n)cbnbnig(i)i1現(xiàn)有Hanoi塔問題的遞歸方程為：h(n)2h(n1)1，求h(n)的非遞歸表h(1)1達式。解：利用給出的關系式，此時有：b=2,c=1,g(n)=1,從n遞推到1，有：n1h(n)cbn1bn1ig(i)i1n1n222n12n2.2221n2n13.單源最短路徑的求解。問題的描述：給定帶權有向圖(如下圖所示)G=(V,E),其中每條邊的權是非負實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路

16、上各邊權之和。這個問題通常稱為單源最短路徑問題。解法：現(xiàn)采用Dijkstra算法計算從源頂點1到其它頂點間最短路徑。請將此過程填入下表中。迭代Sudist2dist3dist4dist5初始1-10maxint3010012344.請寫出用回溯法解裝載問題的函數(shù)。裝載問題：有一批共n個集裝箱要裝上2艘載重量分別為cl和c2的輪船,nWigC2其中集裝箱i的重量為wi,且i1。裝載問題要求確定是否有一個合理的裝載方案可將這n個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。解：voidbacktrack(inti)用分支限界法解裝載問題時，對算法進行了一些改進，下面的程序段給出了改進部分；試說明

17、斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法在執(zhí)行上有什么不同。/檢查左兒子結點Typewt=Ew+wi;/左兒子結點的重量if(wt<=c)/可行結點if(wt>bestw)bestw=wt;/加入活結點隊列if(i<n)(wt);/檢查右兒子結點if(Ew+r>bestw&&i<n)(Ew);/可能含最優(yōu)解(Ew);/取下一擴展結點解答：斜線標識的部分完成的功能為：提前更新bestw值；這樣做可以盡早的進行對右子樹的剪枝。具體為：算法Maxloading初始時將bestw設置為0,直到搜索到第一個葉結點時才更新bestw。因此

18、在算法搜索到第一個葉子結點之前，總有bestw=0,r>0故Ew+r>bestw總是成立。也就是說，此時右子樹測試不起作用。為了使上述右子樹測試盡早生效，應提早更新bestwo又知算法最終找到的最優(yōu)值是所求問題的子集樹中所有可行結點相應重量的最大值。而結點所相應得重量僅在搜索進入左子樹是增加，因此，可以在算法每一次進入左子樹時更新bestw的值。7 .最長公共子序列問題：給定2個序列X=x1,x2,xmDY=y1,y2,yn,找出X和Y的最長公共子序列。由最長公共子序列問題的最優(yōu)子結構性質建立子問題最優(yōu)值的遞歸關系。用cij記錄序列Xi和Yj的最長公共子序列的長度。其中,Xi=x1

19、,x2，,xi ； Yj=y1,y2,yj的最長公共子序列。故此時Cij=0當i=0或j=0時，空序列是Xi和Yj 其它情況下，由最優(yōu)子結構性質可建立0ci 1j1 1maxcij 1,ci 1ji 0,j 0i, j0;xiyji, j0;xiyj在程序中，bij記錄Cij的值是由哪一個子問題的解得到的。(1)請?zhí)顚懗绦蛑械目崭?，以使函?shù)LCSLength完成計算最優(yōu)值的功能。voidLCSLength(intm,intn,char*x,char*y,int*c,int*b)inti,j;for(i=1;i<=m;i+)ci0=0;for(i=1;i<=n;i+)c0i=0;fo

20、r(i=1;i<=m;i+)for(j=1;j<=n;j+)if(xi=yj)cij=ci-1j-1+1;bij=1;elseif(ci-1j>=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bi用=3;(2)函數(shù)LC對現(xiàn)由g據(jù)b的內(nèi)容打印出Xi和Yj的最長公共子序列。請?zhí)顚懗绦蛑械目崭瘢允购瘮?shù)LCS完成構造最長公共子序列的功能(請將bij的取值與(1)中您填寫的取值對應，否則視為錯誤)。voidLCS(inti,intj,char*x,int*b)if(i=0|j=0)return;if(bij=1)LCS(i-1,j-1,x,b);cout&l

21、t;<xi;elseif(bij=2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);8 .對下面的遞歸算法，寫出調(diào)用f(4)的執(zhí)行結果voidf(intk)if(k>0)printf("%dn",k);f(k-1);f(k-1);算法分析與設計期末復習題（二）：1. 算法重要特性是什么2. 算法分析的目的是什么3. 算法的時間復雜性與問題的什么因素相關4. 算法的漸進時間復雜性的含義5. 最壞情況下的時間復雜性和平均時間復雜性有什么不同6. 簡述二分檢索（折半查找）算法的基本過程。7. 背包問題的目標函數(shù)和貪心算法最優(yōu)化量度相同嗎8. 采用

22、回溯法求解的問題，其解如何表示有什么規(guī)定9. 回溯法的搜索特點是什么10. n皇后問題回溯算法的判別函數(shù)place的基本流程是什么11. 為什么用分治法設計的算法一般有遞歸調(diào)用12. 為什么要分析最壞情況下的算法時間復雜性13. 簡述漸進時間復雜性上界的定義。14. 二分檢索算法最多的比較次數(shù)15. 快速排序算法最壞情況下需要多少次比較運算16. 貪心算法的基本思想17. 回溯法的解(Xl,X2,Xn)的隱約束一般指什么18. 闡述歸并排序的分治思路。19. 快速排序的基本思想是什么。20. 什么是直接遞歸和間接遞歸消除遞歸一般要用到什么數(shù)據(jù)結構21. 什么是哈密頓環(huán)問題22. 用回溯法求解哈

23、密頓環(huán)，如何定義判定函數(shù)23. 請寫出prim算法的基本思想。參考答案：1.確定性、可實現(xiàn)性、輸入、輸出、有窮性2. 分析算法占用計算機資源的情況，對算法做出比較和評價，設計出額更好的算法。3. 算法的時間復雜性與問題的規(guī)模相關，是問題大小n的函數(shù)。4當問題的規(guī)模n趨向無窮大時，影響算法效率的重要因素是T(n)的數(shù)量級，而其他因素僅是使時間復雜度相差常數(shù)倍，因此可以用T(n)的數(shù)量級(階)評價算法。時間復雜度T(n)的數(shù)量級(階)稱為漸進時間復雜性。5 .最壞情況下的時間復雜性和平均時間復雜性考察的是n固定時，不同輸入實例下的算法所耗時間。最壞情況下的時間復雜性取的輸入實例中最大的時間復雜度：

24、W(n)=maxT(n,I),ICDn平均時間復雜性是所有輸入實例的處理時間與各自概率的乘積和：A(n)=12P(I)T(n,I)ICDn6 .設輸入是一個按非降次序排列的元素表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。上述過程被反復遞歸調(diào)用?；厮莘ǖ乃阉魈攸c是什么7 .不相同。目標函數(shù)：獲得最大利潤。最優(yōu)量度：最大利潤/重量比。8 .問題的解可以表示為n元組：(xi,x2,xn),xiCSi,Si為有窮集合，xies,(xi,x2,xn)具備完

25、備性，即(xi,x2,xn)是合理的，則(xi,x2,xi)(i<n)一定合理。9 .在解空間樹上跳躍式地深度優(yōu)先搜索，即用判定函數(shù)考察xk的取值，如果xk是合理的就搜索xk為根節(jié)點的子樹，如果xk取完了所有的值，便回溯到xk-i。10 .將第K行的皇后分別與前k-i行的皇后比較，看是否與它們相容，如果不相容就返回false，測試完畢則返回true。11 .子問題的規(guī)模還很大時，必須繼續(xù)使用分治法，反復分治，必然要用到遞歸。12 最壞情況下的時間復雜性決定算法的優(yōu)劣，并且最壞情況下的時間復雜性較平均時間復雜性游可操作性。13 .T(n)是某算法的時間復雜性函數(shù)，f(n)是一簡單函數(shù)，存在

26、正整數(shù)No和C,nNo,有T(n)<f(n)，這種關系記作T(n)=O(f(n)。14 .二分檢索算法的最多的比較次數(shù)為logn。1.1. 最壞情況下快速排序退化成冒泡排序，需要比較n2次。16. 是一種依據(jù)最優(yōu)化量度依次選擇輸入的分級處理方法。基本思路是：首先根據(jù)題意，選取一種量度標準；然后按這種量度標準對這n個輸入排序，依次選擇輸入量加入部分解中。如果當前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。17. 回溯法的解(xi,x2,xn)的隱約束一般指個元素之間應滿足的某種關系。18. 講數(shù)組一分為二，分別對每個集合單獨排序，然后將已排序的兩個序列歸并成一個含n個元素

27、的分好類的序列。如果分割后子問題還很大，則繼續(xù)分治，直到一個元素。19. 快速排序的基本思想是在待排序的N個記錄中任意取一個記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關鍵字比該記錄關鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復上述過程，直到每一部分內(nèi)只有一個記錄為止。20. 在定義一個過程或者函數(shù)的時候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成分，既調(diào)用它自己本身，這稱為直接遞歸。如果過程或者函數(shù)P調(diào)用過程或者函數(shù)Q,Q又調(diào)用P,這個稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結構。21. 哈密頓環(huán)是指一條沿著圖G的N

28、條邊環(huán)行的路徑，它的訪問每個節(jié)點一次并且返回它的開始位置。22. 當前選擇的節(jié)點Xk是從未到過的節(jié)點，即XkwXi(i=1,2,k-1)，且C(Xk-1,Xk)woo,如果k=i,則c(xk,X1)woo。23. 思路是：最初生成樹T為空，依次向內(nèi)加入與樹有最小鄰接邊的n-1條邊。處理過程：首先加入最小代價的一條邊到T,根據(jù)各節(jié)點到T的鄰接邊排序，選擇最小邊加入，新邊加入后，修改由于新邊所改變的鄰接邊排序，再選擇下一條邊加入，直至加入n-1條邊。、復雜性分析1、 MERGESORT(lo，whigh)iflow<high；thenmid(low,high)/2;MERGESORT(low

29、，mid)；MERGESORT(mid+1，high)；MERGE(low，mid，high)；endifT(n) 2(2T(n/4) cn/2) cn 4T(n/4) 2cn2kT(1) kcnan cnlognendMERGESORT答:1、遞歸方程T(n)設 n=2k解遞歸方程：2、 procedurean12T(n/2)cnn1S1(P，W，M，X，n)1 1;a-0whilei<ndoifW(i)>Mthenreturnendifaa+i1 -i+1;repeatend解：i1;s0時間為：O(1)whilei<ndo循環(huán)n次循環(huán)體內(nèi)所用時間為O(1)所以總時間為:

30、T(n)=O(1)+nO(1)=O(n)PARTITION(m,p)Integerm,p,i;globalA(m:p-1)vA(m);imlooploopii+1untilA(i)>vrepeatlooppp-1untilA(p)<vrepeatifi<pthencallINTERCHANGE(A(i),A(p)elseexitendifrepeatA(m)-A(p);A(p)-vEndPARTITION解：最多的查找次數(shù)是p-m+1次F1(n)ifn<2thenreturn(1)elsereturn(F2(2,n,1,1)endifendF1procedureF2(i

31、,n,x,y)ifi<nthencallF2(i+1,n,y,x+y)endifreturn(y)endF2解：F2(2，n,1,1)的時間復雜度為：0(n)T(n)=O(n-2);因為iWn時要遞歸調(diào)用F2,一共是n-2次當n=1時Fi(n)的時間為0(1)當n>1時F1(n)的時間復雜度與F2(2,n,1,1)的時間復雜度相同即為為MAX(A,n,j)xmaxfor iA(1)；j -1-2 to n doif A(i)>xmax then xmax repeatend MAX解：xmax A(1);j -1for i 2 to n do所以 總時間為:T(n)=0(1)

32、+ (n-1)0(1)= 0(n)-A(i)； ji;endif時間為：0(1)循環(huán)最多n-1 次BINSRCH(A,n,x,j)integer low,high,mid,j,n;low -1;high nwhile low< high domid |_(low+high)/2 _|case:x<A(mid):highmid-1:x>A(mid):low -mid+1 :else:j mid; return endcase repeat j 0end BINSRCH解：log n+1 三、算法理解1、寫出多段圖最短路經(jīng)動態(tài)規(guī)劃算法求解下列實例的過程，并求出最優(yōu)值。C(1,2)

33、=3 , C(1,3)=5, C(1,4)=2C(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=4D7=8,5)+ Cost(3,5)，7)+ Cost(3,7)Cost(2,4)=minC(4,6)+Cost(3,6),C(4=min1+5,2+4=6D4=6Cost(2,3)=minC(3,6)+Cost(3,6)=min

34、4+5=9D3=5Cost(2,2)=minC(2,6)+Cost(3,6),C(2=min8+5,4+6=10D2=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=42、寫出maxmin算法對下列實例中找最大數(shù)和最小數(shù)的過程。數(shù)組A=(48,12,61,3,5,19,32,7)解：寫出maxmin算法對下列實例中找最大數(shù)和最小數(shù)的過程。數(shù)組A=()1、48,12,61,3,5,19,32,72、48,1261,35,1932,73、4861,1231932,574、613

35、2355、6133、快速排序算法對下列實例排序，算法執(zhí)行過程中，寫出數(shù)組A第一次被分割的過程。A=(65,70,75,80,85,55,50,2)解：第一個分割元素為65(1)(2)(3)(4)(5)(6)(8)ip65707580855550228V65275808555507037<65250808555757046<A652505585807570465570758085655024、 歸并排序算法對下列實例排序，寫出算法執(zhí)行過程。A=(48,12,61,3,5,19,32,7)解：48,12,61,35,19,32,748,1261,35,1932,712,483,615,

36、197,323, 12,48,615,7,19,323.5, 7,12,19,32,48,615、寫出圖著色問題的回溯算法的判斷Xk是否合理的過程。解：i0whilei<kdoifGk,i=1andXk=Xithenreturnfalsei-i+1repeatifi=kthenreturntrue6、對于下圖，寫出圖著色算法得出一種著色方案的過程。1X1-1,返回trueX2-1,返回false;X2-X2+1=2,返回trueX3-1,返回false;X3-X3+1=2,返回false;X3-X3+1=3,返回trueX4-1,返回false;X4-X4+1=2,返回false;X4-

37、X4+1=3,返回true找到一個解(1,2,3,3)7、寫出第7題的狀態(tài)空間樹。解：分成兩個子問題分成四個子問題分成八個子問題返回上一層返回上一層排序結束，返回主函數(shù)8、寫出歸并排序算法對下列實例排序的過程。(6,2,9,3,5,1,8,7)解：調(diào)用第一層次6,2,9,35,1,8,7調(diào)用第二層次6,29,35,18,7調(diào)用第三層次62935187調(diào)用第四層次只有一個元素返回上一層第三層歸并2,63,91,57,8第二層歸并2,3,6,91,5,7,8第一層歸并1,2,3,5,6,7,8,99、寫出用背包問題貪心算法解決下列實例的過程。P=(18,12,4,1)W=(12,10,8,3)M=

38、25解：實例符合P(i)/W(i)>P(i+1)/W(i+1)的順序。CU25,X0W1<CU:x1-1;CUCU-W1=13;W2<CU:x2-1;CUCU-W2=3;W3>CU:x3CU/W3=3/8;實例的解為：(1,1,3/8,0)11、有一個有序表為1,3,9,12,32,41,45,62,75,77,82,95,100,當使用二分查找值為82的結點時，經(jīng)過多少次比較后查找成功并給出過程。解：有一個有序表為1,3,9,12,32,41,45,62,75,77,82,95,100,當使用二分查找值為82的結點時，經(jīng)過多少次比較后查找成功并給出過程。一共要要執(zhí)行四

39、次才能找到值為82的數(shù)。12、使用prim算法構造出如下圖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)=6解：使用普里姆算法構造出如下圖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)

40、=613、有如下函數(shù)說明intf(intx,inty)f=xMody+1;后，k的值是多少并寫出詳細過程。后，k的值是多少并寫出詳細過程。已知a=10,b=4,c=5則執(zhí)行k=f(f(a+c,b),f(b,c)解：有如下函數(shù)說明intf(intx,inty)f=xMody+1;已知a=10,b=4,c=5則執(zhí)行k=f(f(a+c,b),f(b,c)K的值是514、McCathy函數(shù)定義如下：當x>100時m(x)=x-10;當x<=100時m(x)=m(m(x+11);編寫一個遞歸函數(shù)計算給定x的m(x)值。解：McCathy函數(shù)定義如下：當x>100時m(x)=x-10;當

41、x<=100時m(x)=m(m(x+11);編寫一個遞歸函數(shù)計算給定x的m(x)值。intm(intx)inty;if(x>100)return(x-100);elsey=m(x+11);return(m(y);15、設計一個算法在一個向量A中找出最大數(shù)和最小數(shù)的元素。解：設計一個算法在一個向量A中找出最大數(shù)和最小數(shù)的元素。Voidmaxmin(A,n)VectorA;intn;intmax,min,i;max=A1;min=A1;for(i=2;i<=n;i+)if(Ai>max)max=Ai;elseif(Ai<min)min=Ai;printf("

42、max=%d,min=%dn'，max,min);四、設計算法1 .設有n項獨立的作業(yè)1,2,，n,由m臺相同的機器加工處理。作業(yè)i所需要的處理時間為ti。約定：任何一項作業(yè)可在任何一臺機器上處理，但未完工前不準中斷處理；任何作業(yè)不能拆分更小的子作業(yè)。多機調(diào)度問題要求給出一種調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器處理完。設計算法，并討論是否可獲最優(yōu)解。解：對于處理機j,用Sj表示處理機j已有的作業(yè)數(shù)，用Pj,k表示處理機j的第k個作業(yè)的序號。1)將作業(yè)按照t1>t2>>tn排序2 )S1:m清零j-0設有n種面值為：d1>d2>>dn

43、的錢幣，需要找零錢M,如何選擇錢幣dk,的數(shù)目X,滿足d1XX+dnXXM,使得X+X最小請選擇貪心策略，并設計貪心算法。解：貪心原則：每次選擇最大面值硬幣。CU-M;i-1;X-0有n個物品，已知n=7,禾U潤為P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1),背包容積M=15，物品只能選擇全部裝入背包或不裝入背包，設計貪心算法，并討論是否可獲最優(yōu)解。解：定義結構體數(shù)組G,將物品編號、利潤、重量彳為一個結構體：例如Gk尸1,10,2求最優(yōu)解，按利潤/重量的遞減序，有5,6,1,61,10,2,56,18,4,9/23,15,5,37,3,1,32,5,3,5/

44、34,7,7,1算法procedureKNAPSACK(P,WM,X,n)設計只求一個哈密頓環(huán)的回溯算法。解：Hamiltonian(n)k1;xk-0;Whilek>0doxk-xk+1;whileB(k尸falseandxk<ndoxk-xk+1;repeatIfxk<nthenifk=nthenprintx;returnelsekk+1;xk-0;endifelsekk-1endifrepeatendprocedureB(k)Gxk-1,xk豐1thenreturnfalse;fori-1tok-1doifxi=xkthenreturnfalse;endifrepeat

45、returntrue;a05.利用對稱性設計算法，求n為偶數(shù)的皇后問題所有解。解：利用對稱性設計算法，求n為偶數(shù)的皇后問題所有解。procedureNQUEENS1(n)2f(n)(g(n)f(n)(g(n)f(n)logn;g(n)logn5;f(n)2n;g(n)100n2;f(n)2n;g(n)3n;logn2(logn5)2n(100n2)2n(3n)R1,2,，rn)n1,2,，rnRPerm(4分)cout<<endl;elsefor(inti=k;i<=m;i+)if(ok(list,k,i)swap(listk,listi);Perm(list,k+1,m);

46、swap(listk,listi);.(8分);其中ok用于判別重復元素。Template<class>intok(Typelist,intk,inti)(if(i>k)for(intt=k;t<I;t+)if(listt=listi)return0;return1;.(13分)3、試用分治法對一個有序表實現(xiàn)二分搜索算法。(12分)解：解答如下：Template<class>intBinarySearch(Typea,constType&x,intn)(4分)if(x=amiddle)returnmiddle+1;if(x>amiddle)le

47、ft=middle+1;.(8分)elseright=middle-1;return-1;.(12分)4、試用動態(tài)規(guī)劃算法實現(xiàn)0-1閉包問題。(15分)解：解答如下：Template<class>voidKnapsack(Typev,intw,intc,intn,Type*m)IntjMax=min(wn-1,c);for(intj=0;j<=jMax;j+)mnj=0;for(intj=wn;j<=c;j+)mnj=vn;.(5分)for(inti=n-1;i>1;i-)jMax=min(wi-1,c);for(intj=0;j<=jMax;j+)mij=

48、mi+1j;for(intj=wi;j<=c;j+)mij=max(mi+1j,mi+1j-wi+vi);(8分);m1c=m2c;if(c>=w1)m1c=max(m1c,m2c-w1+v1);(10分)Template<class>VoidTraceback(Type*m,intw,intc,intn,intx)for(inti=1;i<n;i+)if(mic=mi+1c)xi=0;(12分)elsexi=1,c-=wi;xn=(mnc)1:0;.(15分)5、試用貪心算法求解下列問題：將正整數(shù)n分解為若干個互不相同的自然數(shù)之和，使這些自然數(shù)的乘積最大。(15

49、分)解：解答如下：voiddicomp(intn,inta)(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(inti=0;i<n;i+)ak-i+;.(15分)6、試用動態(tài)規(guī)劃算法實現(xiàn)最大子矩陣和問題：求mn矩陣A的一個子矩陣，使其各元素之各為最大。(15分)解：解答如下：intMaxSum2(intm,intn,int*a)intsum=0;int*b=newintn+1;fo

50、r(inti=1;i<=m;i+)for(intk=1;k<=n;k+)bk=0;.(5分)for(intj=i;j<=m;j+)for(intk=1;k<=n;k+)bk+=ajk;intmax=MaxSum(n,b);if(max>sum)sum=max;returnsum;.(10分)intMaxSum(intn,int*a)intsum=0,b=0;for(inti=1;i<=n;i+)if(b>0)b+=ai;elseb=ai;if(b>sum)sum=b;)Returnsum;.(15分)7、試用回溯法解決下列整數(shù)變換問題：關于整數(shù)i

51、的變換f和g定義如下：f(i)3i;g(i)i/2。對于給定的兩個整數(shù)n和m,要求用最少的變換f和g變換次數(shù)將n變?yōu)閙。(18分)解：解答如下：voidcompute()k=1;while(!search(1,n)k+;if(k>maxdep)break;init();.(6分)if(found)output();elsecout<<"NoSolution!"<<endl;.(9分)boolsearch(intdep,intn)If(dep>k)returnfalse;for(inti=0;i<2;i+)intn1=f(n,i);tdep=i;.(12分)if(n1=m|search(dep+1,n1)Found=true;Out();returntrue;returnfalse;.(18分)算法設計與分析考試試卷(20 分)排序和查找是經(jīng)常遇到的問題。按照要求完成以下各題:(1) 對數(shù)組A=15,29,135,18,32,1,27,25,5,用快速排序方法將其排成遞減