算法分析與設(shè)計試題

1、選擇題（20分）1 最長公共子序列算法利用的算法是（A、分支界限法 B動態(tài)規(guī)劃法2 實現(xiàn)棋盤覆蓋算法利用的算法是（A、分治法B動態(tài)規(guī)劃法3. 下面是貪心算法的基本要素的是（A、重疊子問題B構(gòu)造最優(yōu)解4. 回溯法的效率不依賴于下列哪些因素（A.滿足顯約束的值的個數(shù)C.計算限界函數(shù)的時間B)0C貪心法D回溯法A)0C、貪心法D回溯法C)0C、貪心選擇性質(zhì)D定義最優(yōu)解D ）B.計算約束函數(shù)的時間D.確定解空間的時間5. 下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（B）A.遞歸函數(shù)B.剪枝函數(shù)C。隨機(jī)數(shù)函數(shù)D.搜索函數(shù)6. 米用最大效益優(yōu)先搜索方式的算法是（A、分支界限法B、動態(tài)規(guī)劃法7. 貪心算

2、法與動態(tài)規(guī)劃算法的主要區(qū)別是（A、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì)優(yōu)解8. 實現(xiàn)最大子段和利用的算法是（A、分治策略B、動態(tài)規(guī)劃法A）。C、貪心法D回溯法B）。C、構(gòu)造最優(yōu)解D、定義最B）。C、貪心法D回溯法9.優(yōu)先隊列式分支限界法選取擴(kuò)展結(jié)點的原則是（C)。A、先進(jìn)先出B、后進(jìn)先出C、結(jié)點的優(yōu)先級D隨機(jī)10.下列算法中通常以廣度優(yōu)先方式系統(tǒng)搜索問題解的是（A ）A、分支限界法B動態(tài)規(guī)劃法C貪心法D、回溯法二、填空題（22分每空2分）1、算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出確定性和有限性 四條性質(zhì)。2、 大整數(shù)乘積算法是用分治法 來設(shè)計的。3、 以廣度優(yōu)先或以最小耗費方式搜索問題解的

3、算法稱為分支限界法 。4、 舍伍德算法總能求得問題的一個解。5、貪心選擇性質(zhì)是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。6快速排序templatevclass Typevoid Quicksort (Type a, int p, int r)if (Pr) int q=Partiti on( a,p,r);Quicksort (a,p,q-1); /對左半段排序Quicksort (a,q+1,r); /對右半段排序7. 哈密頓環(huán)問題的算法可由回溯法設(shè)計實現(xiàn)。8. 貪心算法不一定產(chǎn)生最優(yōu)解。9算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是回溯法 o三、算法設(shè)計與分析(25

4、分)1. 用歐幾里德迭代算法求兩個數(shù)的最小公倍數(shù)(10分)#in cludeusing n amespace std;int Gcd(i nt m,i nt n)if(m=0)return n;if(n=0)return m;int t=mn?n:m;while(m%t| n%t)t-;return t;int main()int a,b;cout In put a & b (0=a ab;int m=a*b/Gcd(a,b);coutThe Least Com mon Multiple is:me ndl;return 0;2、 試用動態(tài)規(guī)劃算法實現(xiàn)最大子矩陣和問題：求m n矩陣A的一個子矩

5、陣，使 其各元素之各為最大。(15分)解：解答如下：int MaxSum2(int m,int n,int *a)int sum=O;int *b=new in t n+1;for(int i=1;i=m;i+)for(int k=1;k=n;k+) bk=O; . (5 分)for(i nt j=i;j=m;j+)for(int k=1;ksum) sum=max;return sum; .(10 分)int MaxSum(int n,int *a)int sum=O,b=O;for(i nt i=1;i0) b+=ai;else b=ai;if(bsum) sum=b; Return su

6、m; . (15 分)四、簡答題(33分)1、假設(shè)有7個物品，它們的重量和價值如下表所示。若這些物品均可以被分割，且背包容 量M = 150,如果使用貪心方法求解此背包問題，使收益最大，請寫出求解過程請寫出求解 過程。(10分)物品ABCDEFG重量35306050401025價值10403050354030解:使用單位價值從大到?。篎BGDECA ,得到貪心解為：FBGD全部放入，而E放入87.5% , 得到價值為190.625。2. 寫出分治算法 MaxMin算法對下列實例中找最大數(shù)和最小數(shù)的過程。(10分)數(shù)組 A=(48,12,61,3,5,19,32,7)解：1、48,12,61,3

7、,5,19,32,7表中元素多于二，對半分割2、 48,12 61,3 5,19 32,7表中元素多于二，對半分割3、48 61, 12 3 19 32, 5 7求前半部分的最大最小和后半部分的最大最小，兩個半部分的大者為最大，小者為最小4、613235 兩個半部分的大者為最大，小者為最小5、 61 3(13 分)尋找結(jié)束3.寫出多段圖最短路經(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，Cost(3,6)= C(6，8)+0=5,Cost(3,5)= C(5，8)+0=4Cost(2,4)= minC(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5)=mi n1+ 5, 2+4=6Cost(2,3)= minC(3，6)+ Cost(3,6) =mi n4+5=9Cost(2,2)= minC(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7)=min