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

1、算法分析與設(shè)計期末復(fù)習題（一）一、選擇題1應(yīng)用Johnson法則的流水作業(yè)調(diào)度采用的算法是（D）D.動態(tài)規(guī)劃算法A.貪心算法B.分支限界法C.分治法2 .Hanoi塔問題如下圖所示。現(xiàn)要求將塔座A上的的所有圓盤移到塔座B上，并仍按同樣順序疊置。移動圓盤時遵守Hanoi塔問題的移動規(guī)則。由此設(shè)計出解Hanoi塔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)

2、(if(n>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)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B.重疊子問題性質(zhì)與貪心選擇性質(zhì)C.最優(yōu)子結(jié)構(gòu)性質(zhì)與

3、重疊子問題性質(zhì)D.預(yù)排序與遞歸調(diào)用4 .算法分析中，記號O表示(B),記號C表示(A),記號。表示(D)A.漸進下界B.漸進上界C.非緊上界D.緊漸進界E.非緊下界5 .以下關(guān)于漸進記號的性質(zhì)是正確的有：(A)A. f(n)-O(g(n),g(n)-9(h(n)=f(n)-9(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ì)與貪心選擇

4、性質(zhì)C.最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D.預(yù)排序與遞歸調(diào)用7.回溯法在問題的解空間樹中，按（D）策略，從根結(jié)點出發(fā)搜索解空間樹。A.廣度優(yōu)先B.活結(jié)點優(yōu)先C.擴展結(jié)點優(yōu)先D.深度優(yōu)先分支限界法在問題的解空間樹中，按（A）策略，從根結(jié)點出發(fā)搜索解空間樹A.廣度優(yōu)先B.活結(jié)點優(yōu)先C.擴展結(jié)點優(yōu)先D.深度優(yōu)先程序塊（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.C.void

5、backtrack(intt)if(t>n)output(x);elsefor(inti=0;i<=1;i+)xt=i;if(legal(t)backtrack(t+1);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.回溯法

6、的效率不依賴于以下哪一個因素？（C）A.產(chǎn)生xk的時間；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帶圖靈機的空間復(fù)雜性S（n）是指（B）A. k帶圖靈機處理所有長度為n的輸入時，在某條帶上所使用過的最大方格數(shù)。B. k帶圖靈機處理所有長度為n

7、的輸入時，在k條帶上所使用過的方格數(shù)的總和。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)被一臺DTMf接受的語言;D. NP=L|L是一個能在多項式時間內(nèi)被一臺NDTMf接受的語言;14 .記號O的定義正確的是(A)。A. O(g(n)=f(n)|存在正常數(shù)c和n0使得對所有

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

9、常數(shù)c和n0使得對所有n之死有：0Mcg(n)<f(n);C. (g(n)=f(n)|對于任何正常數(shù)c>0,存在正數(shù)和防>0使得對所有n至1有：04f(n)<cg(n)；D. (g(n)=f(n)|對于任何正常數(shù)c>0,存在正數(shù)和n0>0使得對所有n'n°有：0Mcg(n)<f(n);填空題1 .下面程序段的所需要的計算時間為（o（n）。intMaxSum（intn,int*a,int&besti,int&bestj）（intsum=0;for(inti=1;i<=n;i+)intthissum=0;for(in

10、tj=i;j<=n;j+)thissum+=aj;if(thissum>sum)sum=thissum;besti=i;bestj=j;returnsum;2 .有11個待安排的活動，它們具有下表所示的開始時間與結(jié)束時間，如果以貪心算法求解這些活動的最優(yōu)安排（即為活動安排問題：在所給的活動集合中選出最大的相容活動子集合），得到的最大相容活動子集合為活動（1,4,8,11）。i1234567891011Si130535688212fi45678910111213143 .所謂貪心選擇性質(zhì)是指（所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到）。4 .所謂最優(yōu)子結(jié)構(gòu)性

11、質(zhì)是指（問題的最優(yōu)解包含了其子問題的最優(yōu)解）。5 .回溯法是指（具有限界函數(shù)的深度優(yōu)先生成法）。6 .用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點到當前擴展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為h（n）,則回溯法所需的計算空間通常為（O（h（n）。7 .回溯法的算法框架按照問題的解空間一般分為（子集樹）算法框架與（排歹I樹）算法框架。8 .用回溯法解0/1背包問題時，該問題的解空間結(jié)構(gòu)為（子集樹）結(jié)構(gòu)。9 .用回溯法解批處理作業(yè)調(diào)度問題時，該問題的解空間結(jié)構(gòu)為（排列樹）結(jié)構(gòu)。10 .用回溯法解0/1背包問題時，計算結(jié)點的上界

12、的函數(shù)如下所示，請在空格中填入合適的內(nèi)容：TypepKnap<Typew,Typep>:Bound（inti）/計算上界Typewcleft=c-cw;/剩余容量Typepb=cp;/結(jié)點的上界/以物品單位重量價值遞減序裝入物品while（i<=n&&wi<=cleft）cleft-=wi;b+=pi;i+;/裝滿背包if（i<=n）（b+=pi/wi*cleft）;returnb;11 .用回溯法解布線問題時，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為nMm的方格陣列，擴展每個結(jié)點需0(1)的時間，L為最短布線路徑的長度，則算法共耗時(0(mn

13、),構(gòu)造相應(yīng)的最短距離需要(0(L)時間。for(inti=0;i<NumOfNbrs;i+)nbr.row=here.row+offseti.row;nbr.col=here.col+offseti.col;if(gridnbr.rownbr.col=0)/該方格未標記gridnbr.rownbr.col=gridhere.rowhere.col+1;if(nbr.row=finish.row)&&(nbr.col=finish.col)break;/完成布線Q.Add(nbr);12 .用回溯法解圖的m著色問題時，使用下面的函數(shù)OK檢查當前擴展結(jié)點的每一個兒子所相應(yīng)的

14、顏色的可用性，則需耗時（漸進時間上限）（O（mn）。BoolColor:OK(intk)/for(intj=1;j<=n;j+)if(akj=1)&&(xj=xk)returnfalse;returntrue;)13 .旅行售貨員問題的解空間樹是（排列樹）三、解答題1 .機器調(diào)度問題。問題描述：現(xiàn)在有n件任務(wù)和無限多臺的機器，任務(wù)可以在機器上得到處理。每件任務(wù)的開始時間為Si,完成時間為fi,Si<fi。Si,fi為處理任務(wù)i的時間范圍。兩個任務(wù)i,j重疊指兩個任務(wù)的時間范圍區(qū)間有重疊，而并非指i,j的起點或終點重合。例如：區(qū)間1,4與區(qū)間2,4重疊，而與4,7不重

15、疊。一個可行的任務(wù)分配是指在分配中沒有兩件重疊的任務(wù)分配給同一臺機器。因此，在可行的分配中每臺機器在任何時刻最多只處理一個任務(wù)。最優(yōu)分配是指使用的機器最少的可行分配方案。問題實例：若任務(wù)占用的時間范圍是1,4,2,5,4,5,2,6,4,7,則按時完成所有任務(wù)最少需要幾臺機器？(提示：使用貪心算法)畫出工作在對應(yīng)的機器上的分配情況。2 .已知非齊次遞歸方程：-=bf("1Hg，其中，b、c是常數(shù)，f(0)=cng(n)是n的某一個函數(shù)。則f(n)的非遞歸表達式為：f(n)=cbn+£bn_lg(i)。iW現(xiàn)有Hanoi塔問題的遞歸方程為：0=2h(nD+1求h(n)的非遞歸

16、表h(1)=1達式。解：利用給出的關(guān)系式，此時有：b=2,c=1,g(n)=1,從n遞推到1,有：n4h(n)=cbn'一二bn4"g=2n，2T.2221n/=2-13 .單源最短路徑的求解。問題的描述：給定帶權(quán)有向圖(如下圖所示)G=(V,E),其中每條邊的權(quán)是非負實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。解法：現(xiàn)采用Dijkstra算法計算從源頂點1到其它頂點間最短路徑。請將迭代Sudist2dist3dist4dist5初始1-10maxint30100123

17、44 .請寫出用回溯法解裝載問題的函數(shù)。裝載問題：有一批共n個集裝箱要裝上2艘載重量分別為cl和c2的輪船,nWi-CiC2其中集裝箱i的重量為wi,且0。裝載問題要求確定是否有一個合理的裝載方案可將這n個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。解：voidbacktrack(inti)/搜索第i層結(jié)點if(i>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);

18、r+=wi;5.用分支限界法解裝載問題時，對算法進行了一些改進，下面的程序段給出了改進部分；試說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法在執(zhí)行上有什么不同。/檢查左兒子結(jié)點Typewt=Ew+wi;/左兒子結(jié)點的重量if(wt<=c)/可行結(jié)點if(wt>bestw)bestw=wt;/加入活結(jié)點隊列if(i<n)Q.Add(wt);/檢查右兒子結(jié)點if(Ew+r>bestw&&i<n)Q.Add(Ew);/可能含最優(yōu)解Q.Delete(Ew);/取下一擴展結(jié)點解答：斜線標識的部分完成的功能為：提前更新bestw值；這樣做可

19、以盡早的進行對右子樹的剪枝。具體為：算法Maxloading初始時將bestw設(shè)置為0,直到搜索到第一個葉結(jié)點時才更新bestw。因此在算法搜索到第一個葉子結(jié)點之前，總有bestw=0,r>0故Ew+r>bestw總是成立。也就是說，此時右子樹測試不起作用。為了使上述右子樹測試盡早生效，應(yīng)提早更新bestw0又知算法最終找到的最優(yōu)值是所求問題的子集樹中所有可行結(jié)點相應(yīng)重量的最大值。而結(jié)點所相應(yīng)得重量僅在搜索進入左子樹是增加，因此，可以在算法每一次進入左子樹時更新bestw的值。7 .最長公共子序列問題：給定2個序列X=x1,x2,xmDY=y1,y2,yn,找出X和Y的最長公共子序

20、列。由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列Xi和Yj的最長公共子序列的長度。其中，Xi=x1,x2,xi;Yj=y1,y2,yj。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時Cij=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立0i=0,j=0遞歸關(guān)系如下：cij=ci-1j-1+1i,j>0;xi=yjmaxcij-1,ci-1ji,j>0為豐yjJ在程序中，bij記錄Cij的值是由哪一個子問題的解得到的。(1)請?zhí)顚懗绦蛑械目崭瘢允购瘮?shù)LCSLength完成計算最優(yōu)值的功能。voidLCSLength(intm,intn,c

21、har*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;for(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;bij=3;（2）函數(shù)LC對現(xiàn)由g據(jù)b的內(nèi)容打印出Xi和Yj的最長公共子序列。請?zhí)顚懗绦蛑械目崭?，以使函?shù)LCS完成構(gòu)造最長公共子序列的功能（請將bij的取值與（1）中您填寫的取值對應(yīng)，否則視為錯

22、誤）。voidLCS(inti,intj,char*x,int*b)(if(i=0|j=0)return;if(bij=1)LCS(i-1,j-1,x,b);cout<<xi;elseif(bij=2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);8 .對下面的遞歸算法，寫出調(diào)用f(4)的執(zhí)行結(jié)果voidf(intk)if(k>0)printf("%dn",k);f(k-1);f(k-1);算法分析與設(shè)計期末復(fù)習題(二)一、簡要回答下列問題：1 .算法重要特性是什么？2 .算法分析的目的是什么？3 .算法的時間復(fù)雜性與問題的什么因素相

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

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

25、以用T(n)的數(shù)量級(階)評價算法。時間復(fù)雜度T(n)的數(shù)量級(階)稱為漸進時間復(fù)雜性。5 .最壞情況下的時間復(fù)雜性和平均時間復(fù)雜性考察的是n固定時，不同輸入實例下的算法所耗時間。最壞情況下的時間復(fù)雜性取的輸入實例中最大的時間復(fù)雜度：W(n)=maxT(n,I),ICDn平均時間復(fù)雜性是所有輸入實例的處理時間與各自概率的乘積和：A(n)=12P(I)T(n,I)ICDn6 .設(shè)輸入是一個按非降次序排列的元素表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找

26、x。上述過程被反復(fù)遞歸調(diào)用?；厮莘ǖ乃阉魈攸c是什么7 .不相同。目標函數(shù)：獲得最大利潤。最優(yōu)量度：最大利潤/重量比。8 .問題的解可以表示為n元組：(xi,x2,xn),xieS,Si為有窮集合，xies,(xi,x2,xn)具備完備性，即(x1,x2,xn)是合理的，則(*1展2,xi)(i<n)一定合理。9 .在解空間樹上跳躍式地深度優(yōu)先搜索，即用判定函數(shù)考察xk的取值，如果xk是合理的就搜索xk為根節(jié)點的子樹，如果xk取完了所有的值，便回溯到xk-1。10 .將第K行的皇后分別與前k-1行的皇后比較，看是否與它們相容，如果不相容就返回false,測試完畢則返回true。11 .子問

27、題的規(guī)模還很大時，必須繼續(xù)使用分治法，反復(fù)分治，必然要用到遞歸。12 最壞情況下的時間復(fù)雜性決定算法的優(yōu)劣，并且最壞情況下的時間復(fù)雜性較平均時間復(fù)雜性游可操作性。13 .T(n)是某算法的時間復(fù)雜性函數(shù)，f(n)是一簡單函數(shù)，存在正整數(shù)No和C,nNo,有T(n)<f(n),這種關(guān)系記作T(n)=O(f(n)。14 .二分檢索算法的最多的比較次數(shù)為logn。15.1. 壞情況下快速排序退化成冒泡排序，需要比較n2次。2 .是一種依據(jù)最優(yōu)化量度依次選擇輸入的分級處理方法?；舅悸肥牵菏紫雀鶕?jù)題意，選取一種量度標準；然后按這種量度標準對這n個輸入排序，依次選擇輸入量加入部分解中。如果當前這個

28、輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。3 .回溯法的解(Xi,X2,xn)的隱約束一般指個元素之間應(yīng)滿足的某種關(guān)系。4 .講數(shù)組一分為二，分別對每個集合單獨排序，然后將已排序的兩個序列歸并成一個含n個元素的分好類的序列。如果分割后子問題還很大，則繼續(xù)分治，直到一個元素。5 .快速排序的基本思想是在待排序的N個記錄中任意取一個記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復(fù)上述過程，直到每一部分內(nèi)只有一個記錄為止。6 .在定義一個過程

29、或者函數(shù)的時候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成分，既調(diào)用它自己本身，這稱為直接遞歸。如果過程或者函數(shù)P調(diào)用過程或者函數(shù)Q,Q又調(diào)用巳這個稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)。7 .哈密頓環(huán)是指一條沿著圖G的N條邊環(huán)行的路徑，它的訪問每個節(jié)點一次并且返回它的開始位置。8 .當前選擇的節(jié)點Xk是從未到過的節(jié)點，即XkwXi(i=1,2,k-1)，且C(Xk-1,Xk)woo,如果k=-1,則C(Xk,X1)woo。9 .思路是：最初生成樹T為空，依次向內(nèi)加入與樹有最小鄰接邊的n-1條邊。處理過程：首先加入最小代價的一條邊到T,根據(jù)各節(jié)點到T的鄰接邊排序，選擇最小邊加入，新邊加入后，修改由于

30、新邊所改變的鄰接邊排序，再選擇下一條邊加入，直至加入n-1條邊。、復(fù)雜性分析1、MERGESORT(lowhigh)iflow<high;thenmid(low,high)/2;MERGESORT(low,mid);MERGESORT(mid+1,high);MERGE(low,mid,high);endifendMERGESORT答：1、遞歸方程T(n)=，a2T(n/2)cnT(n)=2(2T(n/4)cn/2)cn=4T(n/4)2cn=2kTkcn=ancnlogn設(shè)n=2k解遞歸方程：2、procedureS1(P,VVMX,n)4 1;a-0whilei<ndoifW(

31、i)>Mthenreturnendifaa+i3) -i+1;repeatend解：i1;s0時間為：O(1)whilei<ndo循環(huán)n次循環(huán)體內(nèi)所用時間為O(1)所以總時間為：T(n)=O(1)+nO(1)=O(n)3.procedurePARTITION(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)

32、;A(p)-vEndPARTITION解：最多的查找次數(shù)是p-m+1次4.procedureF1(n)ifn<2thenreturn(1)elsereturn(F2(2,n,1,1)endifendF1procedureF2(i,n,x,y)ifi<nthencallF2(i+1,n,y,x+y)endifreturn(y)endF2解：F2(2,n,1,1)的時間復(fù)雜度為：T(n)=O(n-2);因為iWn時要遞歸調(diào)用F2,一共是n-2次當n=1時F1(n)的時間為0(1)當n>1時F1(n)的時間復(fù)雜度與F2(2,n,1,1)的時間復(fù)雜度相同即為為O(n)5.proced

33、ureMAX(A,n,j)xmaxA(1);j-1fori2tondoifA(i)>xmaxthenxmaxrepeatendMAX解：xmaxA(1);j-1fori2tondo所以總時間為：A(i);ji;endif時間為：O(1)循環(huán)最多n-1次T(n)=O(1)+(n-1)O(1)=O(n)6.procedureBINSRCH(A,n,x,j)integerlow,high,mid,j,n;low-1;highnwhilelow<highdomid|_(low+high)/2_|case:x<A(mid):highmid-1:x>A(mid):low-mid+1

34、:else:jmid;returnendcaserepeatj0endBINSRCH解：log2n+1三、算法理解1、寫出多段圖最短路經(jīng)動態(tài)規(guī)劃算法求解下列實例的過程，并求出最優(yōu)值。各邊的代價如下:C(1,2)=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=8Cost(2,4)

35、=minC(4,6)+Cost(3,6),C(4,5)+Cost(3,5)=min1+5,2+4=6D4=6Cost(2,3)=minC(3,6)+Cost(3,6)=min4+5=9D3=5Cost(2,2)=minC(2,6)+Cost(3,6),C(2,7)+Cost(3,7)=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=4(1) 一4一6一82、寫出maxmin算法對下列實例中找最大數(shù)和最小數(shù)的過程。數(shù)組A=(48,12,61,3

36、,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、6132355、6133、快速排序算法對下列實例排序，算法執(zhí)行過程中，寫出數(shù)組A第一次被分割的過程。A=(65,70,75,80,85,55,50,2)解：第一個分割元素為65(1) (2)(3)(4)(5)(6)(7)(8)ip65707580855550228652.7580_8555507037.65250808555757046+652505585807570465570

37、758085655024、歸并排序算法對下列實例排序，寫出算法執(zhí)行過程。A=(48,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是否合理的過程。解：i0whilei<kdoifGk,i=1andXk=Xithenreturnfalsei-i+1repeatifi=kthenreturntrueX1-1,返回trueX2-1,返回false;X2-X2+1=2,返回trueX

38、3-1,返回false;X3-X3+1=2,返回false;X3-X3+1=3,返回trueX4-1,返回false;X4-X4+1=2,返回false;X4-X4+1=3,返回true找到一個解(1,2,3,3)7、寫出第7題的狀態(tài)空間樹。解：8、寫出歸并排序算法對下列實例排序的過程。(6,2,9,3,5,1,8,7)分成兩個子問題分成四個子問題分成八個子問題返回上一層返回上一層排序結(jié)束，返回主函數(shù)解：調(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

39、,91,5,7,8第一層歸并1,2,3,5,6,7,8,99、寫出用背包問題貪心算法解決下列實例的過程。P=(18,12,4,1)W=(12,10,8,3)M=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的結(jié)點時，經(jīng)過多少次比較后查找成功并給出過程。解：有一個有序

40、表為1,3,9,12,32,41,45,62,75,77,82,95,100,當使用二分查找值為82的結(jié)點時，經(jīng)過多少次比較后查找成功并給出過程。一共要要執(zhí)行四次才能找到值為82的數(shù)。12、使用prim算法構(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)=6解：使用普里姆算法構(gòu)造出如下圖G的一棵最小生成樹。12436511143336611422433566dist(1,2)=6

41、;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=613、有如下函數(shù)說明intf(intx,inty)(f=xMody+1;)已知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的值是多少并寫出詳細過程。k的值是多少并寫出詳細過程。)K的值是514、McCathy

42、函數(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;當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、設(shè)計一個算法在一個向量A中找出最大數(shù)和最小數(shù)的元素。解：設(shè)計一個算法在一個向量A中找出最大數(shù)和最小數(shù)的元素。Voidmaxmin(A,n)Vecto

43、rA;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("max=%d,min=%dn',max,min);)四、設(shè)計算法a. 設(shè)有n項獨立的作業(yè)1,2,，n),由m臺相同的機器加工處理。作業(yè)i所需要的處理時間為ti。約定：任何一項作業(yè)可在任何一臺機器上處理，但未完工前不準中斷處理；任何作業(yè)不能拆分更小的子作業(yè)。多機調(diào)度問題要求給出一種調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器處理完。設(shè)計算法，并討論是否可獲最優(yōu)

44、解。解：對于處理機j,用Sj表示處理機j已有的作業(yè)數(shù)，用Pj,k表示處理機j的第k個作業(yè)的序號。1)將作業(yè)按照t1>t2>>tn排序b. S1:m清零j-0/從第一個處理機開始安排c. fori-1tondo/安排n個作業(yè)jjmodm+1/選下一個處理機Sj-Sj+1;Pj,Sji;Repeat(1) .設(shè)有n種面值為：d1>d2>>dn的錢幣，需要找零錢M,如何選擇錢幣dk,的數(shù)目X,滿足d1XX+dnX乂皿,使得X+X最小請選擇貪心策略，并設(shè)計貪心算法。解：貪心原則：每次選擇最大面值硬幣。CUHM;i1;X-0/X為解向量WhileCUw0doXi-CU

45、divdi/Xi為第i中硬幣數(shù)Cl>CU-di*Xii-i+1;repeat(2) .有n個物品，已知n=7,利潤為P=(10,5,15,7,6,18,3),重量W=(2,3,5,7,1,4,1),背包容積M=15，物品只能選擇全部裝入背包或不裝入背包，設(shè)計貪心算法，并討論是否可獲最優(yōu)解。解：定義結(jié)構(gòu)體數(shù)組G,將物品編號、利潤、重量彳為一個結(jié)構(gòu)體：例如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/34,7,7,1算法procedureKNAPSACK(P,WMXn)/P(1:n)和W(1

46、;n)分別含有按P(i)/W(i)>P(i+1)/W(i+1)排序的n件物品的效益值和重量。M是背包的容量大小，而x(1：n)是解向量realP(1:n),W(1：n),X(1：n),M,cu;integeri,n；X0/將解向量初始化為零/cuM/cu是背包剩余容量fori1tondoifW(i)>cuthenexitendifX(i)-1cucu-W(i)repeatendGREEDY-KNAPSACK根據(jù)算法得出的解：X=(1,1,1,1,1,0,0)獲禾1J潤52,而解(1,1,1,1,0,1,0)可獲利潤54因此貪心法不一定獲得最優(yōu)解。1. .設(shè)計只求一個哈密頓環(huán)的回溯算

47、法。解：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;fori1tok-1doifxi=xkthenreturnfalse;endifrepeatreturntrue;2. .利用對稱性設(shè)計算法，求n為偶數(shù)的皇后問題所有解。解：利用對稱性設(shè)計算法，

48、求n為偶數(shù)的皇后問題所有解。procedureNQUEENS1(n)a-0/計數(shù)器清零X(1)-0;k-1/k是當前行；X(k)是當前列Whilek>0do/對所有的行執(zhí)彳T以下語句1)X(k)-X(k)+1/移到下一列WhileX(k)&nandnotPLACE(k)do2)X(k)-X(k)十lifX(k)&nthenifk=n/thenprint(X),aa+1/找到一個解計數(shù)器a加1/ifa=n/2thenreturn/找到n/2個解算法結(jié)束1 elsekk+1;X(k)-0;2 elsek-k1/回溯endNQUEENS武漢工業(yè)學院工商學院2008N009學年第

49、1學期算法分析考試試卷(A卷)課程名稱算法分析編號03080121題號一一三四五六七八總分得分評閱人注：1、考生必須填寫班級、姓名、學號；2、試題紙共J頁。1、對于下列各組函數(shù)f(n)和g(n),確定f(n)=O(g(n)或f(n)=J(g(n)或f(n)=e(g(n),并簡述理由。(12分)27、 f(n)=logn;g(n)=logn5;8、 f(n)=2n;g(n)=100n2;f(n)=2n;g(n)=3n;解：簡答如下：10、 logn2=8(logn+5),(2)2n=Q(100n2),(3)2n=o(3n)2、試用分治法實現(xiàn)有重復(fù)元素的排列問題：設(shè)=1,2,.,7)是要進行排列的

50、n個元素，其中元素一乃,.可能相同,試計算R的所有不同排列。(13分)解：解答如下：Template<classType>voidPerm(Typelist,intk,intm)if(k=m)for(inti=0;i<=m;i+)cout<<listi;.(4分)cout<<endl;elsefor(inti=k;i<=m;i+)if(ok(list,k,i)swap(listk,listi);Perm(list,k+1,m);swap(listk,listi);.(8分);其中ok用于判別重復(fù)元素。Template<class>in

51、tok(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)/假定數(shù)組a已按非遞減有序排列，本算法找到x后返回其在數(shù)組a口中的位置，/否則返回-1intleft=0,right=n-1;while(left<=right)intmiddle=(left+right)/2;.(

52、4分)if(x=amiddle)returnmiddle+1;if(x>amiddle)left=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