《算法分析與設(shè)計》期末考試復(fù)習(xí)題綱完整

1、算法分析與設(shè)計期末復(fù)習(xí)題選 擇題1.算法必須具備輸入、輸出和（2.A,可行性和安全性C.有窮性和安全性算法分析中，記號A. 漸進下界C. 非緊上界O 表示（B.D.4 個特性。確定性和易讀性有窮性和確定性A漸進上界緊漸進界3.假設(shè)某算法在輸入規(guī)模為n時的計算時間為 T（n）=3*2An的時間為t 秒?，F(xiàn)有另一臺計算機，其運行速度為第一臺的一算法在t 秒內(nèi)能解輸入規(guī)模為多大的問題？（/、）：在某臺計算機上實現(xiàn)并完成概算法64 倍，那么在這臺新機器上用同解題方法：3*2歷*64=3*2”A n+8BC n+7Dn+6n+54.設(shè)問題規(guī)模為 N時，某遞歸算法的時間復(fù)雜度記為T（N）,已知T（1）=1

2、 , T（N）=2T（N/2）+N/2 ,用 O 表示的時間復(fù)雜度為（ C）。A O(logN)B O(N)C O(NlogN)D O(N2logN)5. 直接或間接調(diào)用自身的算法稱為（B ）。A.貪心算法B遞歸算法C.迭代算法D回溯法6. Fibonacci 數(shù)列中，第 4 個和第11 個數(shù)分別是（ D ）。A 5， 89B 3， 89C 5， 144D 3， 1447. 在有 8 個頂點的凸多邊形的三角剖分中，恰有（ B ）。A 6 條弦和 7 個三角形B 5 條弦和 6 個三角形C 6 條弦和 6 個三角形D 5 條弦和 5 個三角形8. 一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征

3、是問題的（ B ）。A.重疊子問題C.貪心選擇性質(zhì)9. 下列哪個問題不用貪心法求解（A.哈夫曼編碼問題C.最大團問題B 最優(yōu)子結(jié)構(gòu)性質(zhì)D 定義最優(yōu)解C ）。B 單源最短路徑問題D 最小生成樹問題10. 下列算法中通常以自底向上的方式求解最優(yōu)解的是（ B ）。A.備忘錄法C.貪心法B 動態(tài)規(guī)劃法D 回溯法11.下列算法中不能解決0/1 背包問題的是（A.貪心法BC.回溯法DA ）。.動態(tài)規(guī)劃.分支限界法12 . 下列哪個問題可以用貪心算法求解（ D ）。A LCS 問題C 0-1 背包問題.批處理作業(yè)問題 .哈夫曼編碼問題13 .用回溯法求解最優(yōu)裝載問題時，若待選物品為m種，則該問題的解空間樹的

4、結(jié)點個數(shù)為）。m+1A m!B 2C 2m+1-1D 2m14.二分搜索算法是利用（？A?）實現(xiàn)的算法。A分治策略？BC.貪心法？D15. 下列不是動態(tài)規(guī)劃算法基本步驟的是（A找出最優(yōu)解的性質(zhì)？ BC.算出最優(yōu)解（應(yīng)該是最優(yōu)值）？動態(tài)規(guī)劃法？回溯法？B？ ）。P44構(gòu)造最優(yōu)解？D.定義最優(yōu)解A.單源最短路徑問題B N 皇后問題C.最小花費生成樹問題D 背包問題17. 使用二分搜索算法在n 個有序元素表中搜索一個特定元素，在最好情況和最壞情況下搜索的時間復(fù)雜性分別為（ A ）。P17A O(1) ， O(logn)BC O(1) ， O(nlogn)DO(n) ， O(logn)O(n) ， O

5、(nlogn)18. 優(yōu)先隊列式分支限界法選取擴展結(jié)點的原則是（ ？C？）。P162A.先進先出C.結(jié)點的優(yōu)先級19. 下面不是分支界限法搜索方式的是（A.廣度優(yōu)先BB 后進先出D 隨機D ）。P161最小耗費優(yōu)先C.最大效益優(yōu)先D 深度優(yōu)先20. 分支限界法解最大團問題時，活結(jié)點表的組織形式是（ B ）。A.最小堆B.最大堆C.棧D.數(shù)組21. 下列關(guān)于計算機算法的描述不正確的是（ C ）。 P1A算法是指解決問題的一種方法或一個過程B.算法是若干指令的有窮序列C. 算法必須要有輸入和輸出D.算法是編程的思想22. 下列關(guān)于凸多邊形最優(yōu)三角剖分問題描述不正確的是（ A ）。A n+1 個矩陣

6、連乘的完全加括號和n 個點的凸多邊形的三角剖分對應(yīng)B.在有n個頂點的凸多邊形的三角剖分中，恰有n-3條弦C.該問題可以用動態(tài)規(guī)劃法來求解D.在有n個頂點的凸多邊形的三角剖分中，恰有n-2個三角形23. 動態(tài)規(guī)劃法求解問題的 基本步驟 不包括（ C ）。P44A.遞歸地定義最優(yōu)值B.分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征C.根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解（ 可以省去的 ）16. 下面問題（ B ）不能使用貪心法解決。D.以自底向上的方式計算出最優(yōu)值24. 分治法所能解決的問題應(yīng)具有的關(guān)鍵特征是（C )。P16A.該問題的規(guī)?？s小到一定的程度就可以容易地解決B.該問題可以分解為若干個規(guī)模較小的

7、相同問題C.利用該問題分解出的子問題的解可以合并為該問題的解D.該問題所分解出的各個子問題是相互獨立的25 .下列關(guān)于回溯法的描述不正確的是( D )。P114A.回溯法也稱為試探法B.回溯法有“通用解題法”之稱C.回溯法是一種能避免不必要搜索的窮舉式搜索法D.用回溯法對解空間作深度優(yōu)先搜索時只能用遞歸方法實現(xiàn)26 . 常見的兩種分支限界法為( D )。P161A.廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B.隊列式(FIFO)分支限界法與堆棧式分支限界法；C.排列樹法與子集樹法；D.隊列式(FIFO)分支限界法與優(yōu)先隊列式分支限界法；二、填空題1. f=3n 2+10的漸近性態(tài) f(n尸O(?

8、n 2 ), g(n)=10log3 n 的漸近性態(tài) g(n)= O(? n ?)。2. 一個“好”的算法應(yīng)具有正確性、可讀性 、 健壯性 和高效率和低存儲量需求等特性。3. 算法的時間復(fù)雜性函數(shù)表示為C=F(N,I,A) ,分析算法復(fù)雜性的目的在于比較求解同意問題的兩個不同算法的效率的效率。4. 構(gòu)成遞歸式的兩個基本要素是遞歸的邊界條件 和 遞歸的定義 。5. 單源最短路徑問題可用分支限界法和 貪心算法 求解。6. 用分治法實現(xiàn)快速排序算法時，最好情況下的時間復(fù)雜性為O(nlogn) ,最壞情況下的時間復(fù)雜性為 O(M2),該算法所需的時間與運行時間和 劃分兩方面因素有關(guān)。P267. 0-1

9、背包問題的解空間樹為完全二叉 樹;n后問題的解空間樹為 排列 樹;8. 常見的分支限界法有隊列式(FIFO)分支限界法和優(yōu)先隊列式分支限界法。9. 回溯法搜索解空間樹時常用的兩種剪枝函數(shù)為約束函數(shù) 和剪枝函數(shù)。10. 分支限界法解最大團問題時，活結(jié)點表的組織形式是最大堆;分支限界法解單源最短路徑問題時，活結(jié)點表的組織形式是最小堆。三、算法填空題1. 遞歸求解Hanoi塔問題/階乘問題。例1 :階乘函數(shù)n!P12階乘的非遞歸方式定義：n! n (n 1) (n 2)2 1試寫出階乖的遞歸式及算法。n!n(n 1)! n0遞歸方程遞歸出口遞歸式為：1 n 0邊界條件遞歸算法:int factori

10、al (int n)if (n=0) return 1;遞歸調(diào)用return n * factorial (n-1);例 2:用遞歸技術(shù)求解Hanoi 塔問題 ,Hanoi 塔的遞歸算法。 P15其中Hanoi (int n, int a, int c, int b)表示將塔座 A上的n個盤子移至塔座 C,以塔座 B為輔助。Move(a,c) 表示將塔座a 上編號為 n 的圓盤移至塔座c 上。void hanoi (int n, int a, int c, int b) if (n > 0) hanoi(n-1, a, b, c); move(a,c);hanoi(n-1, b, c,

11、a); 2. 用分治法求解快速排序問題?？焖倥判蛩惴≒25 、作業(yè)、課件第 2 章( 2) 42 頁-50 頁template<class Type>void QuickSort (Type a, int p, int r) if (p<r) int q=Partition(a,p,r); QuickSort (a,p,q-1); QuickSort (a,q+1,r)； Partition 函數(shù)的具體實現(xiàn) template<class Type> int Partition (Type a, int p, int r) int i = p, j = r + 1;

12、Type x=ap;/將 < x 的元素交換到左邊區(qū)域/將 > x 的元素交換到右邊區(qū)域while (true) while (a+i <x && i<r);while (a- -j >x);if (i >= j) break;Swap(ai, aj);ap = aj;aj = x;return j;3. 用貪心算法求解最優(yōu)裝載問題。最優(yōu)裝載問題 P95 課件第 4 章 (2) 第 3-8 頁template<class Type>void Loading(int x, Type w, Type c, int n)int *t =

13、 new int n+1;Sort(w, t, n);for (int i = 1; i <= n; i+) xi = 0;for (int j = 1; j <= n && wtj <= c; j+)xti = 1; c -= wtj;4. 用回溯法求解0-1 背包 / 批處理作業(yè)調(diào)度 / 最大團問題，要會畫解空間樹。例 1：用回溯法求解0-1 背包 P133 課件第 5 章 (2) 第 24-38 頁template<typename Typew,typename Typep>class Knapprivate:Typep Bound(int

14、i); /計算上界void Backtrack(int i);Typew c; / 背包容量int n; /物品數(shù)Typew *w; /物品重量數(shù)組Typep *p; /物品價值數(shù)組Typew cw; /當(dāng)前重量Typep cp; /當(dāng)前價值Typep bestp; / 當(dāng)前最優(yōu)價值;void Knap<Typew,Typep>:Backtrack(int i) if(i>n) bestp=cp; return; if(cw+wi<=c) /進入左子樹 cw+=wi;cp+=pi;Backtrack(i+1);cw-=wi;cp-=pi; if(Bound(i+1)&g

15、t;bestp) /進入右子樹Backtrack(i+1);Typep Knap<Typew,Typep>:Bound(int i)Typew cleft=c-cw; / 剩余的背包容量Typep b=cp; /b 為當(dāng)前價值/ 依次裝入單位重量價值高的整個物品while(i<=n&&wi<=cleft) cleft-=wi; b+=pi;i+; if(i<=n) / 裝入物品的一部分b+=pi*cleft/wi;return b; / 返回上界class Object / 物品類friend int Knapsack(int *,int *,in

16、t,int);public:int operator <(Object a) constint ID; / 物品編號float d; /單位重量價值;Typep Knapsack( Typep p,Typew w,Typew c,int n) / 為 Typep Knapsack 初始化Typew W=0; /總重量Typep P=0; /總價值Object* Q=new Objectn; /創(chuàng)建物品數(shù)組，下標(biāo)從0 開始for(int i=1;i<=n;i+) /初始物品數(shù)組數(shù)據(jù) Qi-1.ID=i;Qi-1.d=1.0*pi/wi;P+=pi;W+=wi;if(W<=c)

17、/能裝入所有物品return P;if(W<=c) /能裝入所有物品return P;QuickSort(Q,0,n-1); /依物品單位重量價值非增排序Knap<Typew,Typep> K;K.p=new Typepn+1;K.w=new Typewn+1;for(int i=1;i<=n;i+) K.pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0; K.Backtrack(1);delete Q; delete K.w;delete K.p; return K.bestp;例2:批處理

18、作業(yè)調(diào)度課件第5章(2)P2-5問題描述，課本P125-127解空間：排列樹算法描述：class Flowshopstatic int m, / 各作業(yè)所需的處理時間 x,/ 當(dāng)前作業(yè)調(diào)度 bestx, / 當(dāng)前最優(yōu)作業(yè)調(diào)度 f2,/ 機器 2 完成處理時間f1,/ 機器1 完成處理時間f,/ 完成時間和bestf, / 當(dāng)前最優(yōu)的完成時間和n;/ 作業(yè)數(shù)static void Backtrack(int i)if (i > n) for (int j = 1; j <= n; j+)bestxj = xj; bestf = f; elsefor (int j = i; j <

19、;= n; j+) f1+=mxj1;/第 j 個作業(yè)在第一臺機器上所需時間f2i=(f2i-1>f1)?f2i-1:f1)+mxj2;f+=f2i;if (f < bestf) / 約束函數(shù) Swap(xi, xj); Backtrack(i+1); Swap(xi, xj);f1 - =mxj1;f - =f2i;例 3：最大團問題，要會畫解空間樹。class Cliquefriend int MaxClique(int *,int ,int);public:void Print(); /輸出最優(yōu)解private:void Backtrack(int i);int *a; /圖

20、 G 的鄰接矩陣，下標(biāo)從1 開始int n; /圖 G 的頂點數(shù)int *x; /當(dāng)前解int *bestx; / 當(dāng)前最優(yōu)解int cn; /當(dāng)前團的頂點數(shù)int bestn; / 當(dāng)前最大團的頂點數(shù);void Clique:Backtrack(int i) if(i>n) for(int j=1;j<=n;j+) bestxj=xj; bestn=cn; return; / 判斷第 i 個頂點是否與已選頂點都有邊相連int OK=1;，已入選的頂點集與當(dāng)前團中的頂點無邊相連只要與當(dāng)前團中一個頂點無邊相連，則中止for(int j=1;j<i;j+) /x1:i-1if(x

21、j&&aij=0) /i OK=0; break; /if(OK) / 進入左子樹 xi=1;cn+; Backtrack(i+1); xi=0; cn-; if(cn+n-i>bestn) /如有可能在右子樹中找到更大的團，則進入右子樹 xi=0; Backtrack(i+1); 計算時間：O(n2n)四、簡 答題1. 請簡述使用動態(tài)規(guī)劃算法解題的基本步驟。P44動態(tài)規(guī)劃的設(shè)計分為以下4 個步驟：(1) 找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2) 遞歸地定義最優(yōu)值。(3) 以自底向上的方式計算出最優(yōu)值。(4) 根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。2. 簡述動態(tài)規(guī)劃方

22、法與分治法的異同。 P44相同點：動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題 , 然后從這些子問題的解得到原問題的解。不同點：分治法的子問題互相獨立且與原問題相同。與分治法不同的是，適合于動態(tài)規(guī)劃求解的問題，經(jīng)分解得到的子問題往往不是互相獨立的。也就是各個子問題包含公共的子子問題。3. 試比較 Prim 算法與 Kruskal 算法的異同。 105-P107相同點： Prim( 普里姆 ) 算法和 Kruskal( 克魯斯卡爾 )算法都可以看作是應(yīng)用貪心算法構(gòu)造最小生成樹的例子。利用了最小生成樹性質(zhì)。不同點：Prim(普里姆)算法：在這個過程中選取到的所有邊恰好構(gòu)成

23、G的一棵最小生成樹T, T中包含G的n-1條邊，且不形成回路。Kruskal( 克魯斯卡爾) 算法：是構(gòu)造最小生成樹的另一個常用算法。該算法不是通過擴充連通子集來進行貪心選擇。而是通過選擇具有最小權(quán)的邊的集合來進行貪心選擇。在選擇的同時可以進行連通操作以便形成生成樹。4. 請簡述分支限界法的搜索策略。 P161 課件第 6 章(1) 第 6 頁(1) 分支限界法以廣度優(yōu)先或以最小耗費(最大效益)優(yōu)先的方式搜索問題的解空間樹。(2) 每一個活結(jié)點只有一次機會成為擴展結(jié)點。(3) 活結(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。(4) 兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其

24、余兒子結(jié)點被加入活結(jié)點表中。(5) 從活結(jié)點表中取 下一結(jié)點 成為當(dāng)前擴展結(jié)點，并重復(fù)上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。5. 試比較分支限界法與回溯法的異同。 P161 課件第 6 章(1) 第 5 頁不同點：(1) 求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。(2) 搜索方式：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。五、算 法應(yīng)用題1.用動態(tài)規(guī)劃求解凸多邊形最優(yōu)三角剖分問題。三角剖

25、分的結(jié)構(gòu)及其相關(guān)問題 P61(1)語法樹與完全加括號方式一個表達式的完全加括號方式相應(yīng)于一棵完全二叉樹，稱為表達式的語法樹。例如，完全加括號的矩陣連乘積(A1(A2A3)(A4(A5A6)所相應(yīng)的語法樹如圖(a)所示。(2)語法樹與凸多邊形三角剖分凸多邊形P=v0,v1, vn-l的三角剖分也可以用語法樹表示。如圖：根結(jié)點是邊 v0v 6( 可以任選)。其他邊則是語法樹的葉子節(jié)點。v0v 6 是三角形 v0v3v 6 的一條邊。2、三角剖分與矩陣連乘 P61(1) 一般來說，凸多邊形的三角剖分和有n-1 個葉節(jié)點的語法樹存在一一對應(yīng)關(guān)系。(2)N 個矩陣連乘的完全加括號和有n 個葉節(jié)點的語法樹

26、也存在一一對應(yīng)關(guān)系 。(3)所以， n 個矩陣連乘的完全加括號和有n+1 個節(jié)點的凸多邊形的三角剖分也存在一一對應(yīng)關(guān)系。矩陣連乘積中A1 A2An中的每個矩陣 Ai對應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦 vivj ， i<j ，對應(yīng)于矩陣連乘積Ai+1:j 。(5)矩陣連乘積的最優(yōu)計算次序問題是凸多邊形最優(yōu)三角剖分問題的特殊情況。課后習(xí)題(第3 章小結(jié) * )對于如下矩陣鏈P=10,100,5,50,30,20,60,45,50 ，請按照構(gòu)造其最優(yōu)完全加括號方式，并列出相應(yīng)的語法樹和最優(yōu)三角剖分圖。2 .用貪心算法求解活動安排問題/最小生成樹問題/哈夫曼編碼問題

27、。貪心算法求解活動安排問題例：設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下:最小生成樹問題 P103-P105哈夫曼編碼問題，前綴碼二叉樹表示法例子：圖a:與固定長度編碼對應(yīng)的樹(葉子高度一致)圖b:與可變長度編碼對應(yīng)的樹(葉子高度不一致)3 .用回溯法求解0-1背包問題/最優(yōu)裝載問題。用回溯法求0-1背包問題。P133,實例:n=5,M=50N12345W155252730P3012444650P/W22.41.761.701.67(1) .令bestp=0,將物體的序號按價值體積比排序結(jié)果是(2,1,3,4,5)N21345W515252730P1230444650P

28、/W2.421.761.701.67(2) .根據(jù)排序得到部分解 (1,1,1,0),估計當(dāng)前部分解的價值b,86+(50-45)*1.67=94.3, b >bestp.(3) .繼續(xù)向下搜索生成結(jié)點 F,得到可行解(1,1,1,0,0),得到價值為 86,更新bestp=86(如圖第3步) 第3步第5步第8步(4) .回溯：沿E回溯到左孩子 D,生成相應(yīng)右孩子G,得到部分解(1,1,0,1 )，此時b=93.1 b>bestp,可以生成右子樹(第4步在第5步的基礎(chǔ)上沒有H和I的圖形)(5) .繼續(xù)生成結(jié)點 H,I ,得到可行解(1,1,0,1,0 (價值為88,更新bestp=

29、88(如圖第5步)(6) .回溯H生成J,得到部分解(1,1,0,0 ),估計部分解b=92>88 (第6步在第8步的基礎(chǔ)上沒有 K和L的圖形).繼續(xù)生成結(jié)點 K,得到可行解(1,1,0,0, 1 ), 價值為92,更新bestp=92 (第7步在第8步的基 礎(chǔ)上沒有L的圖形)(8). K 是左孩子，生成其對應(yīng)的右孩子L,得到可行解(1,1,0,0,0)(如圖第8步).回溯，沿結(jié)點L向上回溯到結(jié)點B,生成結(jié)點M,得到部分解(1,0), 估計部分解b=90<92,回溯(第9步在第10步的基礎(chǔ)上沒有 N的圖形)(10) .向上繼續(xù)回溯生成結(jié)點N,得到部分解(0),此時得到的 b=74+10*(46/27) =91.03<92, 回溯，此時已回到根結(jié)點，結(jié)束。最優(yōu)解 (1,1,0,0, 1 ),價值為92.(如圖第10步)練習(xí)n=8, M=110 ,W=( 1, 11,21,23,33,43,45,55 )P=(11,21,31,33,43,53,55,65 )用回溯法求此0-1背包問題的最優(yōu)解。