算法設計與分析復習題目及答案

本文格式為Word版，下載可任意編輯——算法設計與分析復習題目及答案

分治法

1、二分探尋算法是利用（分治策略）實現(xiàn)的算法。9.實現(xiàn)循環(huán)賽日程表利用的算法是（分治策略）

27、Strassen矩陣乘法是利用（分治策略）實現(xiàn)的算法。34．實現(xiàn)合并排序利用的算法是（分治策略）。實現(xiàn)大整數(shù)的乘法是利用的算法（分治策略）。17．實現(xiàn)棋盤覆蓋算法利用的算法是（分治法）。

29、使用分治法求解不需要滿足的條件是（子問題必需是一樣的）。不可以使用分治法求解的是（0/1背包問題）。動態(tài)規(guī)劃

以下不是動態(tài)規(guī)劃算法基本步驟的是（構(gòu)造最優(yōu)解）以下是動態(tài)規(guī)劃算法基本要素的是（子問題重疊性質(zhì)）。

以下算法中尋常以自底向上的方式求解最優(yōu)解的是（動態(tài)規(guī)劃法）備忘錄方法是那種算法的變形。（動態(tài)規(guī)劃法）最長公共子序列算法利用的算法是（動態(tài)規(guī)劃法）。矩陣連乘問題的算法可由（動態(tài)規(guī)劃算法B）設計實現(xiàn)。實現(xiàn)最大子段和利用的算法是（動態(tài)規(guī)劃法）。貪心算法

能解決的問題：單源最短路徑問題，最小花費生成樹問題，背包問題，活動安排問題，

不能解決的問題：N皇后問題，0/1背包問題

是貪心算法的基本要素的是（貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)）。回溯法

回溯法解旅行售貨員問題時的解空間樹是（排列樹）。剪枝函數(shù)是回溯法中為避免無效探尋采取的策略

回溯法的效率不依靠于以下哪些因素（確定解空間的時間）

分支限界法

最大效益優(yōu)先是（分支界限法）的一探尋方式。

分支限界法解最大團問題時，活結(jié)點表的組織形式是（最大堆）。分支限界法解旅行售貨員問題時，活結(jié)點表的組織形式是（最小堆）優(yōu)先隊列式分支限界法選取擴展結(jié)點的原則是（結(jié)點的優(yōu)先級）

在對問題的解空間樹進行探尋的方法中,一個活結(jié)點最多有一次機遇成為活結(jié)點的是(分支限界法).

從活結(jié)點表中選擇下一個擴展結(jié)點的不同方式將導致不同的分支限界法,以下除(棧式分支限界法)之外都是最常見的方式.

（1）隊列式(FIFO)分支限界法：依照隊列先進先出（FIFO）原則選取下一個節(jié)點為擴展節(jié)點。

（2）優(yōu)先隊列式分支限界法：依照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當前擴展節(jié)點。

（最優(yōu)子結(jié)構(gòu)性質(zhì)）是貪心算法與動態(tài)規(guī)劃算法的共同點。貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是（貪心選擇性質(zhì)）?；厮菟惴ê头种藿绶ǖ膯栴}的解空間樹不會是(無序樹).

14．哈弗曼編碼的貪心算法所需的計算時間為（B）。A、O（n2n）

B、O（nlogn）

C、O（2n）

D、O（n）

21、下面關于NP問題說法正確的是（B）ANP問題都是不可能解決的問題BP類問題包含在NP類問題中CNP完全問題是P類問題的子集DNP類問題包含在P類問題中

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

A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）42．0-1背包問題的回溯算法所需的計算時間為（A）A、O（n2n）.

47.背包問題的貪心算法所需的計算時間為（B）。A、O（n2n）

B、O（nlogn）C、O（2n）

D、O（n）

B、O（nlogn）C、O（2n）D、O（n）

53．采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法的時間繁雜度為(B)。A、O（n2n）

B、O（nlogn）C、O（2n）D、O（n）

56、算法是由若干條指令組成的有窮序列，而且滿足以下性質(zhì)（D）（1）輸入：有0個或多個輸入（2）輸出：至少有一個輸出（3）確定性：指令明了，無歧義

（4）有限性：指令執(zhí)行次數(shù)有限，而且執(zhí)行時間有限A(1)(2)(3)B(1)(2)(4)C(1)(3)(4)D(1)(2)(3)(4)57、函數(shù)32n+10nlogn的漸進表達式是(B).A.2nB.32nC.nlognD.10nlogn

59、用動態(tài)規(guī)劃算法解決最大字段和問題，其時間繁雜性為(B).A.lognB.nC.n2D.nlogn

61、設f(N),g(N)是定義在正數(shù)集上的正函數(shù),假使存在正的常數(shù)C和自然數(shù)N0,使得當N≥N0時有f(N)≤Cg(N),則稱函數(shù)f(N)當N充分大時有下界g(N),記作f(N)∈○(g(N)),即f(N)的階(A)g(N)的階.A.不高于B.不低于C.等價于D.迫近

二、填空題

2、程序是算法用某種程序設計語言的具體實現(xiàn)。

3、算法的“確定性〞指的是組成算法的每條指令是明了的，無歧義的。6、算法是指解決問題的一種方法或一個過程。

7、從分治法的一般設計模式可以看出，用它設計出的程序一般是遞歸算法。

11、計算一個算法時間繁雜度尋?？梢杂嬎阊h(huán)次數(shù)、基本操作的頻率或計算步。

14、解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是動態(tài)規(guī)劃，需要排序的是回溯法，分支限界法。15、使用回溯法進行狀態(tài)空間樹裁剪分支時一般有兩個標準：約束條件和目標函數(shù)的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時使用約束條件和目標函數(shù)的界進行裁剪的是0/1背包問題，只使用約束條件進行裁剪的是N皇后問題。

30.回溯法是一種既帶有系統(tǒng)性又帶有騰躍性的探尋算法。

33．回溯法探尋解空間樹時，常用的兩種剪枝函數(shù)為約束函數(shù)和限界函數(shù)。

34.任何可用計算機求解的問題所需的時間都與其規(guī)模有關。35.快速排序算法的性能取決于劃分的對稱性。

36.Prim算法利用貪心策略求解最小生成樹問題，其時間繁雜度是O(n2)。

37.圖的m著色問題可用回溯法求解，其解空間樹中葉子結(jié)點個數(shù)是mn，解空間樹中每個內(nèi)結(jié)點的孩子數(shù)是m。

4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，請給出序列X和Y的一個最長公共子序列{BABCD}或{CABCD}或{CADCD｝。5.用回溯法解問題時，應明確定義問題的解空間，問題的解空間至少應包含一個（最優(yōu)）解

8.0-1背包問題的回溯算法所需的計算時間為__o(n*2n)__,用動態(tài)規(guī)劃算法所需的計算時間為___o(min{nc,2n}_。二、綜合題（50分）

1.寫出設計動態(tài)規(guī)劃算法的主要步驟。

①問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；②構(gòu)造最優(yōu)值的遞歸關系表達式；3最優(yōu)值的算法描述；④構(gòu)造最優(yōu)解；

2.流水作業(yè)調(diào)度問題的johnson算法的思想。

①令N1={i|ai=bi}；②將N1中作業(yè)按ai的非減序排序得到N1’，將N2中作業(yè)按bi的非增序排序得到N2’；③N1’中作業(yè)接N2’中作業(yè)就構(gòu)成了滿足Johnson法則的最優(yōu)調(diào)度。

3.若n=4，在機器M1和M2上加工作業(yè)i所需的時間分別為ai和bi，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4個作業(yè)的最優(yōu)調(diào)度方案，并計算最優(yōu)值。

步驟為：N1={1，3}，N2={2，4}；

N1’={1，3}，N2’={4，2}；最優(yōu)值為：38

4.使用回溯法解0/1背包問題：n=3，C=9，V={6,10,3}，W={3,4,4},其解空間有長度為3的0-1向量組成，要求用一棵完全二叉樹表示其解空間（從根出發(fā)，左1右0），并畫出其解空間樹，計算其最優(yōu)值及最優(yōu)解。

解空間為{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}。解空間樹為：

A1B1D1HI01J0E0K1L1F0M1N0C0G0O

該問題的最優(yōu)值為：16最優(yōu)解為：（1，1，0）5.設S=｛X1，X2，···，Xn｝是嚴格遞增的有序集，利用二叉樹的結(jié)點來存儲S中的元素，在表示S的二叉探尋樹中探尋一個元素X，返回的結(jié)果有兩種情形，（1）在二叉探尋樹的內(nèi)結(jié)點中找到X=Xi，其概率為bi。（2）在二叉探尋樹的葉結(jié)點中確定X∈（Xi，Xi+1），其概率為ai。在表示S的二叉探尋樹T中，設存儲元素Xi的結(jié)點深度為Ci；葉結(jié)點（Xi，Xi+1）的結(jié)點深度為di，則二叉探尋樹T的平均路長p為多少？假設二叉探尋樹T[i][j]=｛Xi，Xi+1，···，Xj｝最優(yōu)值為m[i][j]，W[i][j]=ai-1+bi+···+bj+aj，則m[i][j](1j)

6.描述0-1背包問題。

已知一個背包的容量為C，有n件物品，物品i的重量為Wi，價值為Vi，求應如

2.算法定義：

算法是指在解決問題時，依照某種機械步驟一定可以得到問題結(jié)果的處理過程

3.算法的三要素

1、操作2、控制結(jié)構(gòu)3、數(shù)據(jù)結(jié)構(gòu)

13.分治法與動態(tài)規(guī)劃法的一致點是：

將待求解的問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。

兩者的不同點是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是相互獨立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是相互獨立的。

回溯法中常見的兩類典型的解空間樹是子集樹和排列樹。22.請表達動態(tài)規(guī)劃算法與貪心算法的異同。

共同點：都需要最優(yōu)子結(jié)構(gòu)性質(zhì)，都用來求有優(yōu)化問題。不同點：

動態(tài)規(guī)劃：每一步作一個選擇—依靠于子問題的解。貪心方法：每一步作一個選擇—不依靠于子問題的解。

動態(tài)規(guī)劃方法的條件：子問題的重疊性質(zhì)。

可用貪心方法的條件：最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)。

動態(tài)規(guī)劃：自底向上求解；貪心方法：自頂向下求解?？捎秘澬姆〞r，動態(tài)規(guī)劃方法可能不適用；可用動態(tài)規(guī)劃方法時，貪心法可能不適用。23.請說明動態(tài)規(guī)劃方法為什么需要最優(yōu)子結(jié)構(gòu)性質(zhì)。

答：最優(yōu)子結(jié)構(gòu)性質(zhì)是指大問題的最優(yōu)解包含子問題的最優(yōu)解。

動態(tài)規(guī)劃方法是自底向上計算各個子問題的最優(yōu)解，即先計算子問題的最優(yōu)解，然后再利用子問題的最優(yōu)解構(gòu)造大問題的最優(yōu)解，因此需要最優(yōu)子結(jié)構(gòu).24.請說明：

(1)優(yōu)先隊列可用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)？(2)優(yōu)先隊列插入算法基本思想？(3)優(yōu)先隊列插入算法時間繁雜度？

答：（1）堆。

（2）在小根堆中，將元素x插入到堆的末尾，

然后將元素x的關鍵字與其雙親的關鍵字比較，若元素x的關鍵字小于其雙親的關鍵字，

則將元素x與其雙親交換，然后再將元素x與其新雙親的關鍵字相比，直到元素x的關鍵字大于雙親的關鍵字，或元素x到根為止。（3）O(logn)

26.在算法繁雜性分析中，O、Ω、Θ這三個記號的意義是什么？在忽略常數(shù)因子的狀況

下，O、Ω、Θ分別提供了算法運行時間的什么界？答：

假使存在兩個正常數(shù)c和N0,對于所有的N≥N0，有|f(N)|≤C|g(N)|，則記作：f(N)=O(g(N))。這時我們說f(N)的階不高于g(N)的階。

若存在兩個正常數(shù)C和自然數(shù)N0，使得當N≥N0時有|f(N)|≥C|g(N)|，記為f(N)=?(g(N))。這時我們說f(N)的階不低于g(N)的階。

假使存在正常數(shù)c1，c2和n0，對于所有的n≥n0，有c1|g(N)|≤|f(N)|≤c2|g(N)|則記作f(N)=(g,(N)

O、Ω、Θ分別提供了算法運行時間的上界、下界、平均五、算法設計與分析題

1．用動態(tài)規(guī)劃策略求解最長公共子序列問題：（1）給出計算最優(yōu)值的遞歸方程。

（2）給定兩個序列X={B,C,D,A}，Y={A,B,C,B}，請采用動態(tài)規(guī)劃策略求出

其最長公共子序列，要求給出過程。

答：1

?當i?0或j?0時?0?c[i,j]??c[i?1,j?1]?1當i,j?0且xi?yi時

?max(c[i,j?1],c[i?1,j])當i,j?0且xi?yi時?(2)

ＹＡＢＣＢ

Ｘ0000Ｂ00111Ｃ00122Ｄ00122Ａ01122最長公共子序列：｛ＢＣ｝

2．對以下各組函數(shù)f(n)和g(n)，確定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=

θ(g(n))，并簡要說明理由。

(1)f(n)=2n；g(n)=n!(2)f(n)=n；g(n)=logn2(3)f(n)=100；g(n)=log100(4)f(n)=n3；g(n)=3n(5)f(n)=3n；g(n)=2n答：

(1)f(n)=O(g(n))由于g(n)的階比f(n)的階高。(2)f