算法分析與設(shè)計考試復(fù)習(xí)題及參考答案

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

2、索算法最多的比較次數(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. 請寫出prim算法的基本思想。、復(fù)雜性分析1、MERGESORT(lo，whigh)iflowhigh；thenmidJ(low,high)/2;MERGESORT(low，mid)；MERGESORT(mid+1，high)

3、；MERGE(low，mid，high)；endifendMERGESORT2、procedureS1(P，W，M，X，n)iJ1;aJ0whileiMthenreturnendifaJa+iiJi+1;repeatend3. procedurePARTITION(m,p)Integerm,p,i;globalA(m:p-1)vJA(m);ijmloopvrepeatwvrepeatloopiJi+1untilA(i)looppJp-1untilA(p)ifipthencallINTERCHANGE(A(i),A(p)elseexitendifrepeatA(m)JA(p);A(p)JvEnd

4、PARTITION4. procedureF1(n)ifnxmaxthenxmaxJA(i);jJi;endifrepeatendMAX6. procedureBINSRCH(A,n,x,j)integerlow,high,mid,j,n;lowJ1;highJnwhilelowwhighdomidJ|_(low+high)/2_|case:xA(mid):lowJmid+1:else:jJmid;returnendcaserepeatjJ0endBINSRCH三、算法理解1寫出多段圖最短路經(jīng)動態(tài)規(guī)劃算法求解下列實例的過程，并求出最優(yōu)值。C(1,2)=3，C(1,3)=5，C(1,4)=2，C

5、(3,6)=4，C(4,5)=2，C(4,6)=1C(2,6)=8，C(2,7)=4，C(3,5)=5C(5,8)=4，C(6,8)=5，C(7,8)=62、寫出maxmin算法對下列實例中找最大數(shù)和最小數(shù)的過程。數(shù)組A=(48,12,61,3,5,19,32,7)3、給出5個數(shù)(3,6,9,1,7),M=13，用遞歸樹描述sumofsub算法求和數(shù)=M的一個子集的過程。4、快速排序算法對下列實例排序，算法執(zhí)行過程中，寫出數(shù)組A第一次被分割的過程。A=(65,70,75,80,85,55,50,2)5、歸并排序算法對下列實例排序，寫出算法執(zhí)行過程。A=(48,12,61,3,5,19,32,7

6、)6、寫出圖著色問題的回溯算法的判斷Xk是否合理的過程。7、對于下圖，寫出圖著色算法得出一種著色方案的過程。8、寫出第7題的狀態(tài)空間樹。9、寫出歸并排序算法對下列實例排序的過程。(6,2,9,3,5,1,8,7)10、寫出用背包問題貪心算法解決下列實例的過程。P=(18,12,4,1)W=(12,10,8,3)M=2511 、有一個有序表為1,3,9,12,32,41,45,62,75,77,82,95,100，當(dāng)使用二分查找值為82的結(jié)點(diǎn)時，經(jīng)過多少次比較后查找成功并給出過程。12、使用prim算法構(gòu)造出如下圖G的一棵最小生成樹。dist(1,2)=6;dist(2,5)=3;dist(5,

7、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ù)說明intf(intx,inty)f=xMody+1;已知a=10,b=4,c=5則執(zhí)行k=f(f(a+c,b),f(b,c)后，k的值是多少并寫出詳細(xì)過程。14、McCathy函數(shù)定義如下：當(dāng)x100時m(x)=x-10;當(dāng)xd2dn的錢幣，需要找零錢M,如何選擇錢幣dk，的數(shù)目兀，滿足d1XX+dnX%M，使得X+Xn最小請選擇貪心策略，并設(shè)計貪心算法。3. 有n個物品，已知n=7,利潤為P=(10,

8、5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1),背包容積M=15,物品只能選擇全部裝入背包或不裝入背包，設(shè)計貪心算法，并討論是否可獲最優(yōu)解。4. 設(shè)計只求一個哈密頓環(huán)的回溯算法。5利用對稱性設(shè)計算法，求n為偶數(shù)的皇后問題所有解。參考答案一、簡要回答下列問題：1. 確定性、可實現(xiàn)性、輸入、輸出、有窮性2. 分析算法占用計算機(jī)資源的情況，對算法做出比較和評價，設(shè)計出額更好的算法。3. 算法的時間復(fù)雜性與問題的規(guī)模相關(guān)，是問題大小n的函數(shù)。4當(dāng)問題的規(guī)模n趨向無窮大時，影響算法效率的重要因素是T(n)的數(shù)量級，而其他因素僅是使時間復(fù)雜度相差常數(shù)倍，因此可以用T(n)的數(shù)量級(階

9、)評價算法。時間復(fù)雜度T(n)的數(shù)量級(階)稱為漸進(jìn)時間復(fù)雜性。5. 最壞情況下的時間復(fù)雜性和平均時間復(fù)雜性考察的是n固定時，不同輸入實例下的算法所耗時間。最壞情況下的時間復(fù)雜性取的輸入實例中最大的時間復(fù)雜度：W(n)=maxT(n,I),IDn平均時間復(fù)雜性是所有輸入實例的處理時間與各自概率的乘積和：A(n)=刀P(I)T(n,1)IDn6. 設(shè)輸入是一個按非降次序排列的元素表Ai:j和x,選取A(i+j)/2與x比較，如果A(i+j)/2=x,則返回(i+j)/2,如果A(i+j)/2x,則Ai：(i+j)/2-1找x,否則在A(i+j)/2+1:j找x。上述過程被反復(fù)遞歸調(diào)用?；厮莘ǖ乃?/p>

10、索特點(diǎn)是什么7. 不相同。目標(biāo)函數(shù)：獲得最大利潤。最優(yōu)量度：最大利潤/重量比。8. 問題的解可以表示為n元組：(xi,x2,xn),XiSi,Si為有窮集合，XiS,(X1,X2,Xn)具備完備性，即(X1,X2,Xn)是合理的，則(X1,X2,Xi)(in)定合理。9. 在解空間樹上跳躍式地深度優(yōu)先搜索,即用判定函數(shù)考察Xk的取值,如果Xk是合理的就搜索Xk為根節(jié)點(diǎn)的子樹,如果Xk取完了所有的值,便回溯到Xk-1。10. 將第K行的皇后分別與前k-1行的皇后比較，看是否與它們相容，如果不相容就返回false,測試完畢則返回true。11 .子問題的規(guī)模還很大時,必須繼續(xù)使用分治法,反復(fù)分治,

11、必然要用到遞歸。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.最壞情況下快速排序退化成冒泡排序，需要比較n2次。16. 是一種依據(jù)最優(yōu)化量度依次選擇輸入的分級處理方法?；舅悸肥?首先根據(jù)題意,選取一種量度標(biāo)準(zhǔn)；然后按這種量度標(biāo)準(zhǔn)對這n個輸入排序,依次選擇輸入量加入部分解中。如果當(dāng)前這個輸入量的加入,不滿足約束條件,則不把此輸入加到這部分解中。

12、17. 回溯法的解(X1,X2,Xn)的隱約束一般指個元素之間應(yīng)滿足的某種關(guān)系。18. 講數(shù)組一分為二,分別對每個集合單獨(dú)排序,然后將已排序的兩個序列歸并成一個含n個元素的分好類的序列。如果分割后子問題還很大，則繼續(xù)分治，直到一個元素。19. 快速排序的基本思想是在待排序的N個記錄中任意取一個記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復(fù)上述過程，直到每一部分內(nèi)只有一個記錄為止。20. 在定義一個過程或者函數(shù)的時候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成分，既

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

14、加入n-1條邊。、復(fù)雜性分析1、遞歸方程T(n)2(2T(n/4)cn/2)cnan1T(n)設(shè)n=2k解遞歸方程：2、i1;s4T(n/4)2cn2T(n/2)cnn12kT(1)kcnancnlognJ0時間為：0(1)ndo循環(huán)n次循環(huán)體內(nèi)所用時間為0(1)所以總時間為:T(n)=0(1)+n0(1)=0(n)3 、最多的查找次數(shù)是p-m+1次4 、F2(2,n,1,1)的時間復(fù)雜度為：T(n)=0(n-2);因為i1時F1(n)的時間復(fù)雜度與F2(2,n,1,1)的時間復(fù)雜度相同即為為0(n)5 、xmaxA(1);j1時間為：0(1)fori2tondo循環(huán)最多n-1次所以總時間為:

15、T(n)=0(1)+(n-1)0(1)=0(n)6 、log2n+1三、算法理解1、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)=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

16、(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=41t82、寫出maxmin算法對下列實例中找最大數(shù)和最小數(shù)的過程。數(shù)組A=()1、48,12,61,3,5,19,32,72、48,1261,35,1932,73、4861,1231932,574、6132355、6133、給出5個數(shù)(3,6,9,1,7),M=12，用遞歸樹描述sumofsub算法求和數(shù)=M的一個子集的過程。1, 28,02, 25,33, 19,34、第一個分割元素為65(1)(3)(5)(6)(7)(8)iP65

17、70758085555022865275808555507037652508085557570465、V-6525055858075704655707580856550248,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,616、i0whileiP(i+1)/W(i+1)的順序。CU25,X0W1CU:x11;CUCU-W1=13;W2CU:x3CU/W3=3/8;實例的解為：(1,1,3/8,0)11有一個有序表為1,3,9,12,32,41,45,62,75,77

18、,82,95,100，當(dāng)使用二分查找值為82的結(jié)點(diǎn)時，經(jīng)過多少次比較后查找成功并給出過程。一共要要執(zhí)行四次才能找到值為82的數(shù)。G的一棵最小生成樹。12. 使用普里姆算法構(gòu)造出如下圖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)=6COco13. 有如下函數(shù)說明intf(intx,inty)f=xMody+1;已知a=10,b=4,c=5則執(zhí)行k=f(f(a+c,b),f(b,c)后，k的值是多少并寫出詳細(xì)過

19、程。K的值是514. McCathy函數(shù)定義如下：當(dāng)x100時m(x)=x-10;當(dāng)x100)return(x-100);elsey=m(x+11);return(m(y);15設(shè)計一個算法在一個向量A中找出最大數(shù)和最小數(shù)的元素。Voidmaxmin(A,n)VectorA;intn;intmax,min,i;max=A1;min=A1;for(i=2;imax)max=Ai;elseif(Aid2dn的錢幣，需要找零錢M,如何選擇錢幣dk，的數(shù)目Xt2tn排序2)S1:m清零j0/從第一個處理機(jī)開始安排3)fori1tondo/安排n個作業(yè)jjmodm+1/選下一個處理機(jī)SjSj+1;Pj,Sji;Repeat貪心原則：每次選擇最大面值硬幣。CUHM;i1;X0/X為解向量WhileCU工0doXiCUdivdi/Xi為第i中硬幣數(shù)CUCU-di*Xiii+1;repeat3、定義結(jié)構(gòu)體數(shù)組G,將物品編號、利潤、重量作為一個結(jié)構(gòu)體：例如Gk=1,10,2求最優(yōu)解，按利潤