最新《算法分析與設(shè)計(jì)試卷-》

1、學(xué)習(xí) - 好資料算法分析與設(shè)計(jì)試卷（A）（時(shí)間 90 分鐘 滿分 100 分）題號-一一-二二-三四合計(jì)核分人復(fù)核人分?jǐn)?shù)閱卷人、填空題（ 30 分海題 2 分）。閱卷人得分1 ?最長公共子序列算法利用的算法是（B ）0A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D 回溯法2. 在對問題的解空間樹進(jìn)行搜索的方法中 ，一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會成為活結(jié)點(diǎn)的是（B ）.A.回溯法 B.分支限界法 C.回溯法和分支限界法D.回溯法求解子集樹問題3.實(shí)現(xiàn)最大子段和利用的算法是（B ）A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D 回溯法4. .廣度優(yōu)先是（A ）的一搜索方式。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法 5.

2、 衡量D、回溯法一個(gè)算法好壞的標(biāo)準(zhǔn)是（C ）A 運(yùn)行速度快 B 占用空間少 C 時(shí)間復(fù)雜度低 D 代碼短D 原問題和子問題使用相同的方法解6.Strassen 矩陣乘法是利用（A ）實(shí)現(xiàn)的算法A、分治策略 B、動(dòng)態(tài)規(guī)劃法C、貪心法D 、回溯法7.使用分治法求解不需要滿足的條件是（A ）A 子問題必須是一樣的B 子冋題不能夠重復(fù)8.用動(dòng)態(tài)規(guī)劃算法解決最大字段和問題，其時(shí)間復(fù)雜性為（B ）.A.log n B.n C.n2D.n log n9. 解決活動(dòng)安排問題，最好用（ B ）算法A.分治 B.貪心 C.動(dòng)態(tài)規(guī)劃 D.窮舉10.下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（B ）A.遞歸函數(shù)B

3、.剪枝函數(shù)C。隨機(jī)數(shù)函數(shù)D.搜索函數(shù)11.從活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)的不同方式將導(dǎo)致不同的分支限界法，以下除（ C ）之外都是最常見的方式.A.隊(duì)列式分支限界法B.優(yōu)先隊(duì)列式分支限界法C.棧式分支限界法D.FIFO 分支限界法12.?回溯算法和分支限界法的問題的解空間樹不會是（ D ）.A.有序樹 B.子集樹 C.排列樹 D.無序樹13.優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是（C）oA、先進(jìn)先出B、后進(jìn)先出C、結(jié)點(diǎn)的優(yōu)先級D 隨機(jī)14. 下面是貪心算法的基本要素的是（ C ） oA、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D 定義最優(yōu)解15. 回溯法在解空間樹 T 上的搜索方式是 （A

4、）.A.深度優(yōu)先B.廣度優(yōu)先C.最小耗費(fèi)優(yōu)先D.活結(jié)點(diǎn)優(yōu)先二、填空題（ 20 分,每空 1 分）。閱卷人得分C 子問題的解可以合并1. 算法由若干條指令組成的又窮序列，且滿足輸入、輸出 、確定性 和 有限性 四個(gè)特性。2. 分支限界法的兩種搜索方式有隊(duì)列式（FIFO ）分支限界法、優(yōu)先隊(duì)列式分更多精品文檔支限界法，用一個(gè)隊(duì)列來存儲結(jié)點(diǎn)的表叫活節(jié)點(diǎn)表。更多精品文檔學(xué)習(xí) - 好資料3.直接或間接調(diào)用自身的方法叫遞歸算法4、 大整數(shù)乘積算法是用分治算法來設(shè)計(jì)的。5、 以廣度優(yōu)先或以最小耗費(fèi)方式搜索問題解的算法稱為分支限界法。6、動(dòng)態(tài)規(guī)劃的子問題重疊 。7 ?貪心算法的選擇性質(zhì)是貪心選擇性質(zhì)、動(dòng)態(tài)規(guī)劃

5、法的選擇性質(zhì)是最優(yōu)子結(jié)構(gòu)性質(zhì)。8.問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。9.以深度優(yōu)先方式搜索問題解的算法稱為回溯法 。10、 快速排序法的三個(gè)步驟為：分解 、遞歸求解、閱卷人得分1.計(jì)算下列函數(shù)的漸進(jìn)表達(dá)式( 1) n2/10 2 n ( 2) 10log3n; 21+1/n;( 1) O(2 n)( 2) O(n)/ O(logn) 0(1)合并。11 、 貪心算法的基本要素是貪心選擇性質(zhì)和最有子結(jié)構(gòu)性質(zhì)性質(zhì)。三、問答題 ( 30 分，每題 6 分) 。2. 解釋什么是 NP 類問題。NP 冋題是指還未被證明是否存在多項(xiàng)式算法能夠解決的冋題，而其中NP 完全

6、冋題又是最有可能不是P 問題的問題類型。所有的NP 問題都可以用多項(xiàng)式時(shí)間劃歸到他們中的一個(gè)。所以顯然NP 完全的問題具有如下性質(zhì)：它可以在多項(xiàng)式時(shí)間內(nèi)求解，當(dāng)且僅當(dāng)所有的其他的NP 完全問題也可以在多項(xiàng)式時(shí)間內(nèi)求解。3. 動(dòng)態(tài)規(guī)劃法的 4 個(gè)步驟設(shè)計(jì)是什么 ？(1) 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征 ;(2) . 遞歸地定義最優(yōu)值；(3) 以自底向上的方式計(jì)算出最優(yōu)值；4.4. 用回溯法解題通常包含幾個(gè)步驟？更多精品文檔學(xué)習(xí) - 好資料(1) 針對所給問題，定義問題的解空間；(2) 確定易于搜索的解空間結(jié)構(gòu)；(3) 以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索5 簡述分支

7、限界法與回溯法的異同點(diǎn)。相同點(diǎn)：二者都是一種在問題的解空間樹T 上搜索問題解的算法。不同點(diǎn)： 1.在一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出T 中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。2. 回溯法與分支 -限界法對解空間的搜索方式不同，回溯法通常采用嘗試優(yōu)先搜索，而分支限界法則通常采用廣度優(yōu)先搜索。3. 對節(jié)點(diǎn)存儲的常用數(shù)據(jù)結(jié)構(gòu)以及節(jié)點(diǎn)存儲特性也各不相同，除由搜索方式?jīng)Q定的不同的存儲結(jié)構(gòu)外，分支限界法通常需要存儲一些額外的信息以利于進(jìn)一步地展開

8、搜索四、算法設(shè)計(jì)與分析 ( 26 分,1 題 11 分， 2 題 15 分)閱卷人得分用動(dòng)態(tài)規(guī)劃策略求解最長公共子序列問題:( 1) 給出計(jì)算最優(yōu)值的遞歸方程。(2) 給定兩個(gè)序列 X=B,C,D,A ，Y=A,B,C,B ，請采用動(dòng)態(tài)規(guī)劃策略求出其最長公共子序列，要求給出過程。(1)引進(jìn)一個(gè)二維數(shù)組 c，用 cij 記錄 Xi 與丫j的 LCS 的長度， bij 記錄 cij 是通過哪一個(gè)子問題的值求得的，以決定搜索的方向。我們是自底向上進(jìn)行遞推計(jì)算，那么在計(jì)算ci,j 之前， ci-1j-1,ci-1j與 cij-1均已計(jì)算出來。此時(shí)我們根據(jù)Xi = Yj 還是 Xi != Yj ，就可以計(jì)算出 cij 。問題的遞歸式寫成：0if / = 0 or y