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

1、算法分析與設(shè)計(jì)試卷(A)算法分析與設(shè)計(jì)試卷(A)-（90100）_-題號(hào)一二三四合計(jì)核分人復(fù)核人-分?jǐn)?shù)號(hào)學(xué)-閱卷人-線一、填空題（30 分,每題 2 分）。_-閱卷人得分-1最長公共子序列算法利用的算法是（B ）。-_-_-A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法名姓-_-_-封-級(jí)班-A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法-4.廣度優(yōu)先是（A）的一搜索方式。-A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法_-_-密5衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（ C）。-A 運(yùn)行速度快 B 占用空間少 C 時(shí)間復(fù)雜度低 D 代碼短-部系-6Strassen矩陣乘法是利用（A）實(shí)現(xiàn)的算法。-A、

2、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法-7. 使用分治法求解不需要滿足的條件是 （ A ）。-A 子問題必須是一樣的-B 子問題不能夠重復(fù)-C 子問題的解可以合并-D 原問題和子問題使用相同的方法解8用動(dòng)態(tài)規(guī)劃算法解決最大字段和問題，其時(shí)間復(fù)雜性為(B).A.lognB.nC.n2D.nlogn解決活動(dòng)安排問題，最好用（ B）算法A.分治 B.貪心 C.動(dòng)態(tài)規(guī)劃 D.窮舉10.下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（B）A遞歸函數(shù)B.剪枝函數(shù)C。隨機(jī)數(shù)函數(shù)D.搜索函數(shù)11. 從活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)的不同方式將導(dǎo)致不同的分支限界法 ,以除(C)之外都是最常見的方式.A.隊(duì)列式

3、分支限界法 B.優(yōu)先隊(duì)列式分支限界C.棧式分支限界法D.FIFO分支限界法2在對(duì)問題的解空間樹進(jìn)行搜索的方法中,2在對(duì)問題的解空間樹進(jìn)行搜索的方法中,一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)12. .回溯算法和分支限界法的問題的解空間樹不會(huì)是(D).的是(B).A.有序樹 B.子集樹 C.排列樹 D.無序樹A.回溯法 B.分支限界法 C.回溯法和分支限界法D.回溯法求解子集樹問題13.優(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í)下面是貪心算法的基本要素的是（C）。A、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、定義最

4、優(yōu)解回溯法在解空間樹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)表。1直接或間接 調(diào)用自身的方法叫遞歸算法4、大整數(shù)乘積算法是用 分治算法來設(shè)計(jì)的。5、以廣度優(yōu)先或以最小耗費(fèi)方式搜索問題解的算法稱為 分支限界法。動(dòng)態(tài)規(guī)劃的子問題 重疊。-2.解釋什么是NP類問題。-貪心算法的選擇性質(zhì)是 貪心選擇性質(zhì)、動(dòng)態(tài)規(guī)劃法的選擇性質(zhì)是最子結(jié)構(gòu)性質(zhì)。

5、問題的 最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)特征。以深度優(yōu)先方式搜索問題解的算法稱為 回溯法。10、快速排序法的三個(gè)步驟為：分解、遞歸求解合并 。11、貪心算法的基本要素是 貪心選擇性質(zhì)和最有子結(jié)構(gòu)性質(zhì)性質(zhì) 。三、問答題（306分）。閱卷人閱卷人得分1.計(jì)算下列函數(shù)的漸進(jìn)表達(dá)式（1）n2 /102n（2）10log3n; (3) 21+1/n;（1）O(2n) （2）O(n)/ O(logn) (3)O(1)NP NP 全問-P NP 劃歸-NP 間內(nèi)-求解，當(dāng)且僅當(dāng)所有的其他的 NP完全問題也可以在多項(xiàng)式時(shí)間內(nèi)求解。 線-動(dòng)態(tài)規(guī)劃法的4個(gè)步驟設(shè)計(jì)是什么?-(1)找出最優(yōu)解

6、的性質(zhì)，并刻畫其結(jié)構(gòu)特征；-(2).遞歸地定義最優(yōu)值；-封(3)以自底向上的方式計(jì)算出最優(yōu)值；-用回溯法解題通常包含幾個(gè)步驟？-針對(duì)所給問題，定義問題的解空間；-確定易于搜索的解空間結(jié)構(gòu)；-。-5 簡述分支限界法與回溯法的異同點(diǎn)。-2T不同點(diǎn)：1.在一般情況下，分支限界法與回溯法的求解目標(biāo)不同。-T-_-_-_-_-_-_-_-達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。_-_-號(hào)_-2.號(hào)-學(xué)-而分支限界法則通常采用廣度優(yōu)先搜索。-線3.對(duì)節(jié)點(diǎn)存儲(chǔ)的常用數(shù)據(jù)結(jié)構(gòu)以及節(jié)點(diǎn)存儲(chǔ)特性也各不相同除由搜索方式?jīng)Q定的_-_-_-000000111001220012201122(2)(2)-_-_-_-_-_-_-最長公共子序列：名-四、算法設(shè)計(jì)與分析（26分,1題11分，2題15分）。姓-_-閱卷人得分-_-_封_-_-_-用動(dòng)態(tài)規(guī)劃策略求解最長公共子序列問題：-_-_-（1）給出計(jì)算最優(yōu)值的遞歸方程。_-級(jí)-班-X=B,C,D,A班-最長公共子序列，要求給出過程。-_-_-(1