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

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

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

算。

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

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

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

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

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

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

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

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

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

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

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

屬于（）的解決方法。

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

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

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

n

2

30、背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為（）。

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

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

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

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

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

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

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

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

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

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

B、剪枝函數(shù)

D、探尋函數(shù)

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

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

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

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

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

二、簡(jiǎn)答題：

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

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

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

6、簡(jiǎn)述分治法所能解決的問(wèn)題一般具有的特征。性提高效率的？

7、簡(jiǎn)述動(dòng)態(tài)規(guī)劃的算法步驟。

三、程序閱讀題：

請(qǐng)閱讀以下程序，描述程序功能，并分析時(shí)間繁雜度。

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