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

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

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

3、算法稱為分支限界法 。4、 舍伍德算法總能求得問(wèn)題的一個(gè)解。5、貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(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); /對(duì)左半段排序Quicksort (a,q+1,r); /對(duì)右半段排序7. 哈密頓環(huán)問(wèn)題的算法可由回溯法設(shè)計(jì)實(shí)現(xiàn)。8. 貪心算法不一定產(chǎn)生最優(yōu)解。9算法中通常以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的是回溯法 o三、算法設(shè)計(jì)與分析(25

4、分)1. 用歐幾里德迭代算法求兩個(gè)數(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、 試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)最大子矩陣和問(wèn)題：求m n矩陣A的一個(gè)子矩

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 分)四、簡(jiǎn)答題(33分)1、假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均可以被分割，且背包容 量M = 150,如果使用貪心方法求解此背包問(wèn)題，使收益最大，請(qǐng)寫(xiě)出求解過(guò)程請(qǐng)寫(xiě)出求解 過(guò)程。(10分)物品ABCDEFG重量35306050401025價(jià)值10403050354030解:使用單位價(jià)值從大到小：FBGDECA ,得到貪心解為：FBGD全部放入，而E放入87.5% , 得到價(jià)值為190.625。2. 寫(xiě)出分治算法 MaxMin算法對(duì)下列實(shí)例中找最大數(shù)和最小數(shù)的過(guò)程。(10分)數(shù)組 A=(48,12,61,3,5,19,32,7)解：1、48,12,61,3

7、,5,19,32,7表中元素多于二，對(duì)半分割2、 48,12 61,3 5,19 32,7表中元素多于二，對(duì)半分割3、48 61, 12 3 19 32, 5 7求前半部分的最大最小和后半部分的最大最小，兩個(gè)半部分的大者為最大，小者為最小4、613235 兩個(gè)半部分的大者為最大，小者為最小5、 61 3(13 分)尋找結(jié)束3.寫(xiě)出多段圖最短路經(jīng)動(dòng)態(tài)規(guī)劃算法求解下列實(shí)例的過(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