算法設(shè)計與分析復(fù)習(xí)題最終版

本文格式為Word版，下載可任意編輯——算法設(shè)計與分析復(fù)習(xí)題最終版一、填空題：

1、算法就是一組有窮的_____________，它們規(guī)定了解決某一特定類型問題的一系列運

算。

2、f(n)=6×2+n，f(n)的漸進上界是_____________。3、遞歸與分治算法應(yīng)滿足條件：____________與_____________。4、算法的繁雜性是______的度量，是評價算法優(yōu)劣的重要依據(jù)。

5、以廣度優(yōu)先探尋或以最小花費方式探尋問題解的算法稱為________________。6、算法滿足的性質(zhì)：輸入、______、______、有限性。7、算法的繁雜性是______的度量，是評價算法優(yōu)劣的重要依據(jù)。8、以________________方式探尋問題解的算法稱為分支限界法。

9、貪心算法總是做出在當(dāng)前看來________________的選擇。也就是說貪心算法并不從整

體最優(yōu)考慮，它所做出的選擇只是在某種意義上的________________。

10、算法的“確定性〞指的是組成算法的每條_____________是明了的，無歧義的。11、任何可用計算機求解的問題所需的時間都與其_____________有關(guān)。

12、分支限界法主要有隊列式（FIFO）分支限界法和________________分支限界法。13、貪心算法總是做出在當(dāng)前看來________________的選擇。也就是說貪心算法并不從整

體最優(yōu)考慮，它所做出的選擇只是在某種意義上的________________。14、大整數(shù)乘積算法是用_____________來設(shè)計的。

15、任何可用計算機求解的問題所需的時間都與其_____________有關(guān)。16、衡量一個算法好壞的標(biāo)準是（）。17、二分探尋算法是利用（）實現(xiàn)的算法。

18、用探尋算法解旅行售貨員問題時的解空間樹是（）。19、0-1背包問題的回溯算法所需的計算時間為（）20、以下哪種算法是以深度優(yōu)先策略進行探尋的（）21、（）是貪心算法與動態(tài)規(guī)劃算法的共同點。

22、以下算法中尋常以自底向下的方式求解最優(yōu)解的是（）。23、分支限界法解旅行售貨員問題時，活結(jié)點表的組織形式是（）。24、回溯法探尋狀態(tài)空間樹是依照（）的順序。

25、將一個難以直接解決的大問題，分解成一些規(guī)模較小的一致問題，以便各個擊破。這

屬于（）的解決方法。

26、Strassen矩陣乘法是利用（）實現(xiàn)的算法。27、備忘錄方法是（）算法的變形。28、（）算法是以深度優(yōu)先策略進行探尋的（）29、以下不是動態(tài)規(guī)劃算法基本步驟的是（）。

A、找出最優(yōu)解的空間結(jié)構(gòu)C、算出最優(yōu)解

B、構(gòu)造最優(yōu)解D、定義最優(yōu)解

n

2

30、背包問題的貪心算法所需的計算時間為（）。

31、下面哪種函數(shù)是回溯法中為避免無效探尋采取的策略（）A、遞歸函數(shù)

32、以下描述正確的是（）

A、遞歸算法只能直接調(diào)用自身B、遞歸函數(shù)是由函數(shù)自身給出定義的

C、每個遞歸函數(shù)不一定都要有非遞歸定義的初始值D、以上都不正確

33、以下描述不正確的是（）

A、組成算法的每條指令是沒有歧義的B、算法中每條指令的執(zhí)行時間是有限的

C、在算法的循環(huán)結(jié)構(gòu)中，指令的執(zhí)行次數(shù)可以無限D(zhuǎn)、組成算法的每條指令是明了的

34、下面哪種函數(shù)是回溯法中為避免無效探尋采取的策略（）

A、遞歸函數(shù)C、隨機數(shù)函數(shù)

B、剪枝函數(shù)D、探尋函數(shù)

B、剪枝函數(shù)

D、探尋函數(shù)

C、隨機數(shù)函數(shù)

35、二分探尋算法是利用（）實現(xiàn)的算法。

A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法36、衡量一個算法好壞的標(biāo)準是（）。

37、用探尋算法解旅行售貨員問題時的解空間樹是（）。38、算法分析中,記號O表示()

39、（）算法中尋常以自底向下的方式求解最優(yōu)解的是（）。40、（）是貪心算法與動態(tài)規(guī)劃算法的共同點。41、回溯法探尋狀態(tài)空間樹是依照（）的順序。

二、簡答題：

1.闡述回溯算法與分枝限界算法的區(qū)別和聯(lián)系，各自強調(diào)改善那方面以提高效率，各適合那些問題？

2、采用動態(tài)規(guī)劃算法必需滿足的條件是什么？動態(tài)規(guī)劃算法是通過什么問題的什么特3、陳述算法在最壞狀況下的時間繁雜度和平均時間繁雜度；這兩種評估算法繁雜性的方法各自有什么實際意義？

4、比較貪心算法與動態(tài)規(guī)劃算法的異同，它們都有那些優(yōu)勢和劣勢？5、簡述分支限界法和回溯法的異同

6、簡述分治法所能解決的問題一般具有的特征。性提高效率的？

7、簡述動態(tài)規(guī)劃的算法步驟。

三、程序閱讀題：

請閱讀以下程序，描述程序功能，并分析時間繁雜度。

1、#includeusingnamespacestd;

voidPrintMultiplicationTable(intn){

if(n==1){

coutusingnamespacestd;char*str=\intn=4;intx[4];

voidBackTrack_SubSet(intt){

if(t==n){

for(inti=0;iusingnamespacestd;boolIsPowerOfTwo(intn){

if(nusingnamespacestd;

inlinevoidSwap(inta=b;b=temp;}

voidPerm(intlist[],intm,intk=0){

if(k==m-1){

for(inti=0;iusing