1、系部_ 班級_ 姓名_ 學號_-密-封-線-算法分析與設計試卷(a)（時間90分鐘 滿分100分）題號一二三四合計核分人復核人分數(shù)閱卷人一、填空題（30分,每題2分）。閱卷人得分1最長公共子序列算法利用的算法是（ b ）。a、分支界限法b、動態(tài)規(guī)劃法c、貪心法d、回溯法2在對問題的解空間樹進行搜索的方法中,一個活結(jié)點最多有一次機會成為活結(jié)點的是( b ).a.回溯法 b.分支限界法c.回溯法和分支限界法 d.回溯法求解子集樹問題3 實現(xiàn)最大子段和利用的算法是（ b   ）。a、分治策略b、動態(tài)規(guī)劃法c、貪心法d、回溯法4.廣度優(yōu)先是（  a&#

2、160; ）的一搜索方式。a、分支界限法      b、動態(tài)規(guī)劃法    c、貪心法    d、回溯法5衡量一個算法好壞的標準是（ c ）。a 運行速度快 b 占用空間少 c 時間復雜度低 d 代碼短6strassen矩陣乘法是利用（ a）實現(xiàn)的算法。a、分治策略 b、動態(tài)規(guī)劃法 c、貪心法 d、回溯法7. 使用分治法求解不需要滿足的條件是 （ a ）。a 子問題必須是一樣的b 子問題不能夠重復c 子問題的解可以合并d 原問題和子問題使用相同的方法解8用動態(tài)規(guī)劃算法解決最大字段和問題，

3、其時間復雜性為( b ).a.logn b.n c.n2 d.nlogn9.解決活動安排問題，最好用（ b ）算法a.分治 b.貪心c.動態(tài)規(guī)劃 d.窮舉10.下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（ b ）a遞歸函數(shù)b.剪枝函數(shù) c。隨機數(shù)函數(shù)d.搜索函數(shù)11. 從活結(jié)點表中選擇下一個擴展結(jié)點的不同方式將導致不同的分支限界法,以下除( c )之外都是最常見的方式.a.隊列式分支限界法 b.優(yōu)先隊列式分支限界法c.棧式分支限界法 d.fifo分支限界法12. .回溯算法和分支限界法的問題的解空間樹不會是( d ).a.有序樹 b.子集樹c.排列樹 d.無序樹13.優(yōu)先隊列式分支限界法選

4、取擴展結(jié)點的原則是（ c    ）。a、先進先出b、后進先出c、結(jié)點的優(yōu)先級d、隨機14下面是貪心算法的基本要素的是（ c ）。a、重疊子問題b、構(gòu)造最優(yōu)解c、貪心選擇性質(zhì)d、定義最優(yōu)解15回溯法在解空間樹t上的搜索方式是( a ).a.深度優(yōu)先 b.廣度優(yōu)先 c.最小耗費優(yōu)先 d.活結(jié)點優(yōu)先二、填空題（20分,每空1分）。閱卷人得分1. 算法由若干條指令組成的又窮序列，且滿足輸入、 輸出 、 確定性 和 有限性 四個特性。2.分支限界法的兩種搜索方式有 隊列式(fifo)分支限界法 、 優(yōu)先隊列式分支限界法 ，用一個隊列來存儲結(jié)點的表叫 活節(jié)點表 。3

5、. 直接或間接 調(diào)用自身的方法叫 遞歸算法 。4、大整數(shù)乘積算法是用 分治算法 來設計的。5、以廣度優(yōu)先或以最小耗費方式搜索問題解的算法稱為 分支限界法 。6動態(tài)規(guī)劃的子問題 重疊 。7貪心算法的選擇性質(zhì)是 貪心選擇性質(zhì) 、動態(tài)規(guī)劃法的選擇性質(zhì)是 最優(yōu)子結(jié)構(gòu)性質(zhì) 。8問題的 最優(yōu)子結(jié)構(gòu)性質(zhì) 是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。9以深度優(yōu)先方式搜索問題解的算法稱為 回溯法 。10、快速排序法的三個步驟為： 分解 、 遞歸求解 、 合并 。11、貪心算法的基本要素是 貪心選擇性質(zhì) 和 最有子結(jié)構(gòu)性質(zhì) 性質(zhì) 。三、問答題（30分，每題6分）。閱卷人得分1. 計算下列函數(shù)的漸進表達式（1

6、）（2）10log3n; (3) 21+1/n; （1）o(2n) （2）o(n)/ o(logn) (3)o(1)2.解釋什么是np類問題。np問題是指還未被證明是否存在多項式算法能夠解決的問題，而其中np完全問題又是最有可能不是p問題的問題類型。所有的np問題都可以用多項式時間劃歸到他們中的一個。所以顯然np完全的問題具有如下性質(zhì)：它可以在多項式時間內(nèi)求解，當且僅當所有的其他的np完全問題也可以在多項式時間內(nèi)求解。3.動態(tài)規(guī)劃法的4個步驟設計是什么?(1)找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；(2).遞歸地定義最優(yōu)值；(3)以自底向上的方式計算出最優(yōu)值；4. 用回溯法解題通常包含幾個步驟？（

7、1）針對所給問題，定義問題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)；（3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。5 簡述分支限界法與回溯法的異同點。相同點：二者都是一種在問題的解空間樹t上搜索問題解的算法。不同點：1.在一般情況下，分支限界法與回溯法的求解目標不同。回溯法的求解目標是找出t中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標函數(shù)值達到極大或極小的解，即在某種意義下的最優(yōu)解。2.回溯法與分支-限界法對解空間的搜索方式不同，回溯法通常采用嘗試優(yōu)先搜索，而分支限界法則通常采用廣度優(yōu)先搜索。3.對節(jié)點存儲的常用數(shù)據(jù)結(jié)構(gòu)以及節(jié)點存儲特性也各不相同，除由搜索方式?jīng)Q定的不同的存儲結(jié)構(gòu)外，分支限界法通常需要存儲一些額外的信息以利于進一步地展開搜索四、算法設計與分析（26分,1題11分，2題15分）。閱卷人得分用動態(tài)規(guī)劃策略求解最長公共子序列問題： （1）給出計算最優(yōu)值的遞歸方程。 （2）給定兩個序列x=b,c,d,a ，y=a,b,c,b，請采用動態(tài)規(guī)劃策略求出其最長公共子序列，要求給出過程。(1)引進一個二維數(shù)組c，用cij記錄xi與yj 的lcs 的長度，bij記錄cij是通過哪一個子問題的值求得的，以決定搜索的方向。我們是自底向上進行遞推計算，那么在計算ci,j之前，ci-