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

一、 選擇題（20分）1最長公共子序列算法利用的算法是（B ）。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法2實現(xiàn)棋盤覆蓋算法利用的算法是（A ）。A、分治法B、動態(tài)規(guī)劃法C、貪心法D、回溯法3.下面是貪心算法的基本要素的是（C ）。A、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、定義最優(yōu)解4.回溯法的效率不依賴于下列哪些因素（ D ）A.滿足顯約束的值的個數(shù) B. 計算約束函數(shù)的時間 C. 計算限界函數(shù)的時間 D. 確定解空間的時間5.下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（B ）A遞歸函數(shù)B.剪枝函數(shù) C。隨機(jī)數(shù)函數(shù)D.搜索函數(shù)6采用最大效益優(yōu)先搜索方式的算法是（A ）。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法7貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是（B ）。A、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì)C、構(gòu)造最優(yōu)解D、定義最優(yōu)解8. 實現(xiàn)最大子段和利用的算法是（B ）。A、分治策略B、動態(tài)規(guī)劃法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)先或以最小耗費(fèi)方式搜索問題解的算法稱為 分支限界法 。4、舍伍德算法總能求得問題的 一個解 。5、 貪心選擇性質(zhì) 是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。6.快速排序templatevoid QuickSort (Type a, int p, int r) if (pr) int q=Partition(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)搜索問題解的是 回溯法 。三、 算法設(shè)計與分析（25分）1.用歐幾里德迭代算法求兩個數(shù)的最小公倍數(shù)（10分）#includeusing namespace std;int Gcd(int m,int 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;coutInput a & b (0=aab;int m=a*b/Gcd(a,b);coutThe Least Common Multiple is:mendl;return 0;2、試用動態(tài)規(guī)劃算法實現(xiàn)最大子矩陣和問題：求矩陣A的一個子矩陣，使其各元素之各為最大。（15分）解：解答如下：int MaxSum2(int m,int n,int *a) int sum=0;int *b=new intn+1;for(int i=1;i=m;i+) for(int k=1;k=n;k+) bk=0; .（5分） for(int j=i;j=m;j+) for(int k=1;ksum) sum=max; return sum; .（10分） int MaxSum(int n,int *a) int sum=0,b=0; for(int i=1;i0) b+=ai; else b=ai; if(bsum) sum=b;Return sum; .（15分）四、簡答題（33分）1、假設(shè)有7個物品，它們的重量和價值如下表所示。若這些物品均可以被分割，且背包容量M150，如果使用貪心方法求解此背包問題，使收益最大，請寫出求解過程請寫出求解過程。（10分）物品ABCDEFG重量35306050401025價值10403050354030解：使用單位價值從大到小：FBGDECA，得到貪心解為：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, 5,19,32,7 表中元素多于二， 對半分割2、48,12 61,3 5,19 32,7 表中元素多于二， 對半分割3、 4861, 123 1932，57求前半部分的最大最小和后半部分的最大最小，兩個半部分的大者為最大，小者為最小4、 6132 35 兩個半部分的大者為最大，小者為最小5、 61 3 尋找結(jié)束3. 寫出多段圖最短路經(jīng)動態(tài)規(guī)劃算法求解下列實例的過程，并求出最優(yōu)值。（13分）52 4 8 4 3 8631 5 4 5 2 2 1 674各邊的代價如下：C(1,2)=3， C(1,3)=5 ，C(1,4)=2 C(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=4 Cost(2,4)= minC(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5) = min1+ 5, 2+4=6 Cost(2,3)= minC(3，6)+ Cost(3,6) = min4+5=9 Cost(2,2)= minC(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7) = mi