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

學(xué)習(xí) 好資料

《算法分析與設(shè)計(jì)》試卷(A)（時(shí)間90分鐘滿分100分）

D原問題和子問題使用相同的方法解8．用動(dòng)態(tài)規(guī)劃算法解決最大字段和問題，其時(shí)間復(fù)雜性為( B A.logn B.n C.n2 D.nlogn題號(hào)一二三四題號(hào)一二三四合計(jì)核分人復(fù)核人分?jǐn)?shù)閱卷人A.分治B.貪心C.動(dòng)態(tài)規(guī)劃D.窮舉下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（ B ）一、填空題（30分,每題2分）。閱卷人閱卷人得分最長公共子序列算法利用的算法是（ B）。A、分支界限法 B、動(dòng)態(tài)規(guī)劃法 C、貪心法

A．遞歸函數(shù) B.剪枝函數(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ì)列式分支限界法D、回溯法 C.棧式分支限界法 D.FIFO分支限界法在對(duì)問題的解空間樹進(jìn)行搜索的方法中,一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)的是( B ).A.回溯法B.分支限界法C.回溯法和分支限界法D.回溯法求解子集樹問題

.回溯算法和分支限界法的問題的解空間樹不會(huì)是( D A.有序樹B.子集樹C.排列樹D.無序樹優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是（C ）。3．實(shí)現(xiàn)最大子段和利用的算法是（B ）。

A、先進(jìn)先出

B、后進(jìn)先出 C、結(jié)點(diǎn)的優(yōu)先級(jí)D、隨機(jī)A、分治策略 B、動(dòng)態(tài)規(guī)劃法 C、貪心4．.廣度優(yōu)先是（ A ）的一搜索方式。

D、回溯法

14．下面是貪心算法的基本要素的是（ C ）。A、重疊子問題 B、構(gòu)造最優(yōu)解 C、貪心選擇性質(zhì) D、定義最優(yōu)解A、分支界限法 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯5．衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（C ）。A運(yùn)行速度快B占用空間少C時(shí)間復(fù)雜度低D代碼短Strassen矩陣乘法是利用（ A）實(shí)現(xiàn)的算法。A、分治策略 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法使用分治法求解不需要滿足的條件是（A）。A子問題必須是一樣的B子問題不能夠重復(fù)C子問題的解可以合并更多精品文檔

15．回溯法在解空間樹T上的搜索方式是( A ).閱卷人得分A.深度優(yōu)先 B.廣度優(yōu)先 C.最小耗費(fèi)優(yōu)先 D.活結(jié)點(diǎn)優(yōu)二、填空題（20分,每空1閱卷人得分算法由若干條指令組成的又窮序列，且滿足輸入、 輸出 確定性 和 有限性 四個(gè)特性。分支限界法的兩種搜索方式有隊(duì)列式(FIFO)分支限界法 、 優(yōu)先隊(duì)列式支限界法 ，用一個(gè)隊(duì)列來存儲(chǔ)結(jié)點(diǎn)的表叫活節(jié)點(diǎn)表 。學(xué)習(xí) 好資料直接或間接 調(diào)用自身的方法叫遞歸算法 。4、大整數(shù)乘積算法是用 分治算法 來設(shè)計(jì)的。5、以廣度優(yōu)先或以最小耗費(fèi)方式搜索問題解的算法稱為分支限界法 。動(dòng)態(tài)規(guī)劃的子問題重疊 。貪心算法的選擇性質(zhì)是 貪心選擇性質(zhì) 、動(dòng)態(tài)規(guī)劃法的選擇性質(zhì)是最子結(jié)構(gòu)性質(zhì) 。問題的 最優(yōu)子結(jié)構(gòu)性質(zhì) 是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。9．以深度優(yōu)先方式搜索問題解的算法稱為回溯法。10、快速排序法的三個(gè)步驟為： 分解、遞歸求解、合并。11、貪心算法的基本要素是貪心選擇性質(zhì) 和 最有子結(jié)構(gòu)性質(zhì) 性質(zhì)。三、問答題（306分）。閱卷人閱卷人得分1.計(jì)算下列函數(shù)的漸進(jìn)表達(dá)式（1）n2/10 2n（2）10log3n;(3)21+1/n;（1）O(2n)（2）O(n)/O(logn)(3)O(1)更多精品文檔

NPNPNP完全問PNPNPNP－完全問題也可以在多項(xiàng)式時(shí)間內(nèi)求解。4(1)找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；(2).遞歸地定義最優(yōu)值；(3)以自底向上的方式計(jì)算出最優(yōu)值；4.5.用回溯法解題通常包含幾個(gè)步驟？學(xué)習(xí) 好資料針對(duì)所給問題，定義問題的解空間；確定易于搜索的解空間結(jié)構(gòu)；

(1)

最長公共子序列，要求給出過程。以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。5簡述分支限界法與回溯法的異同點(diǎn)。T不同點(diǎn)：1.T達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。而分支限界法則通常采用廣度優(yōu)先搜索。搜索四、算法設(shè)計(jì)與分析（26分,111215）。閱卷人閱卷人得分用動(dòng)態(tài)規(guī)劃策略求解最長公共子序列問題：給出計(jì)算最優(yōu)值的遞歸方程。X={B,C,D,A更多精品文檔

c[][]，c[i][jX[i]Y[j]LCS的長度c[i][j]是通過哪一個(gè)子問題的值求得的，以決定搜索的方向。c