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

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

2、規(guī)模為N時，某遞歸算法的時間復(fù)雜度記為T(N)，已知T(1)=1，T(N)=2T(N/2)+N/2，用O表示的時間復(fù)雜度為（ C ）。AO(logN) BO(N) CO(NlogN) DO(NlogN) 5. 直接或間接調(diào)用自身的算法稱為（ B ）。A貪心算法 B遞歸算法 C迭代算法 D回溯法6. Fibonacci數(shù)列中，第4個和第11個數(shù)分別是（ D ）。A5，89 B3，89 C5，144 D3，1447. 在有8個頂點的凸多邊形的三角剖分中，恰有（ B ）。A6條弦和7個三角形 B5條弦和6個三角形C6條弦和6個三角形 D5條弦和5個三角形8. 一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的

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

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

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

6、的凸多邊形的三角剖分對應(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)解 (可以省去的) D以自底向上的方式計算出最優(yōu)值24. 分治法所能解決的問題應(yīng)具有的關(guān)鍵特征是（ C ）。P16A該問題的規(guī)?？s小到一定的程度就可以容易地解決B該問題可以分解為若干個規(guī)模較小的相同問題C利用該問題分解出的子問題的解可以合并為該問題的解D該問題所分解出的各個子問題是相互

7、獨立的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(n)=3n2+10的漸近性態(tài)f(n)= O(n2 )，g(n)=10log3n的漸近性態(tài)g(n)= O( n )。2. 一個“好”

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

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

10、歸調(diào)用 例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, a); 2. 用分治法求解快速排序問題。快速排序算法 P25 、作業(yè)、課件第2章（2）42頁-50頁templatevoid QuickSort

11、 (Type a, int p, int r) if (pr) int q=Partition(a,p,r); QuickSort (a,p,q-1); QuickSort (a,q+1,r)； Partition函數(shù)的具體實現(xiàn)templateint Partition (Type a, int p, int r) int i = p, j = r + 1; Type x=ap; / 將 x的元素交換到右邊區(qū)域 while (true) while (a+i x & ix); if (i = j) break; Swap(ai, aj); ap = aj; aj = x; return j;3

12、. 用貪心算法求解最優(yōu)裝載問題。最優(yōu)裝載問題 P95 課件第4章(2)第3-8頁templatevoid Loading(int x, Type w, Type c, int n) int *t = 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)度 /最大團(tuán)問題，要會畫解空間樹。例1：用回溯法求解0-1背包 P133課件第5章(2)第24-38頁templatecl

13、ass Knap private: Typep Bound(int 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:Backtrack(int i) if(in) bestp=cp; return; if(cw+wibestp) /進(jìn)入右子樹 Backtrack(i+1);Typep Knap:Bound(int i) Type

14、w 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 *,int,int); public: int operator =a.d); int ID; /物品編號 float d; /單位重量價值;Typep Knapsack( Typep p,Typew

15、 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) /能裝入所有物品 return P; if(W=c) /能裝入所有物品 return P; QuickSort(Q,0,n-1); /依物品單位重量價值非增排序 Knap K; K.p=new Typepn+1; K.w=

16、new Typewn+1; for(int i=1;i n) for (int j = 1; j = n; j+) bestxj = xj; bestf = f; else for (int j = i; j f1)?f2i-1:f1)+mxj2; f+=f2i; if (f n) for(int j=1;j=n;j+) bestxj=xj; bestn=cn; return;/判斷第i個頂點是否與已選頂點都有邊相連 int OK=1; for(int j=1;jbestn) /如有可能在右子樹中找到更大的團(tuán)，則進(jìn)入右子樹 xi=0; Backtrack(i+1); 計算時間：O(n2n)四、

17、 簡答題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ī)劃方法與分治法的異同。P44相同點：動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題,然后從這些子問題的解得到原問題的解。不同點：分治法的子問題互相獨立且與原問題相同。與分治法不同的是，適合于動態(tài)規(guī)劃求解的問題，經(jīng)分解得到的子問題往往不是互相獨立的。也就是各個子問題包含公共的子子問題。3. 試比較Prim算法與Kruska

18、l算法的異同。105-P107相同點：Prim(普里姆)算法和Kruskal(克魯斯卡爾)算法都可以看作是應(yīng)用貪心算法構(gòu)造最小生成樹的例子。利用了最小生成樹性質(zhì)。不同點：Prim(普里姆)算法：在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹T，T中包含G的n-1條邊，且不形成回路。 Kruskal(克魯斯卡爾)算法：是構(gòu)造最小生成樹的另一個常用算法。該算法不是通過擴(kuò)充連通子集來進(jìn)行貪心選擇。而是通過選擇具有最小權(quán)的邊的集合來進(jìn)行貪心選擇。在選擇的同時可以進(jìn)行連通操作以便形成生成樹。4. 請簡述分支限界法的搜索策略。P161 課件第6章(1)第6頁(1)分支限界法以廣度優(yōu)先或以最小耗費（最

19、大效益）優(yōu)先的方式搜索問題的解空間樹。(2)每一個活結(jié)點只有一次機(jī)會成為擴(kuò)展結(jié)點。(3)活結(jié)點一旦成為擴(kuò)展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。(4)兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。(5)從活結(jié)點表中取 下一結(jié)點 成為當(dāng)前擴(kuò)展結(jié)點，并重復(fù)上述結(jié)點擴(kuò)展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。 5. 試比較分支限界法與回溯法的異同。P161 課件第6章(1)第5頁不同點：(1)求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下

20、的最優(yōu)解。 (2)搜索方式：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。 五、 算法應(yīng)用題1. 用動態(tài)規(guī)劃求解凸多邊形最優(yōu)三角剖分問題。三角剖分的結(jié)構(gòu)及其相關(guān)問題P61(1)語法樹與完全加括號方式一個表達(dá)式的完全加括號方式相應(yīng)于一棵完全二叉樹，稱為表達(dá)式的語法樹。例如，完全加括號的矩陣連乘積(A1(A2A3)(A4(A5A6)所相應(yīng)的語法樹如圖 (a)所示。(2)語法樹與凸多邊形三角剖分凸多邊形P=v0,v1,vn-1的三角剖分也可以用語法樹表示。如圖：根結(jié)點是邊v0v 6(可以任選)。其他邊則是語法樹的葉子節(jié)點。 v0v 6是三角形v0v3

21、v 6的一條邊。2、三角剖分與矩陣連乘P61(1)一般來說，凸多邊形的三角剖分和有n-1個葉節(jié)點的語法樹存在一一對應(yīng)關(guān)系。(2)N個矩陣連乘的完全加括號和有n個葉節(jié)點的語法樹也存在一一對應(yīng)關(guān)系 。(3)所以，n個矩陣連乘的完全加括號和有n+1個節(jié)點的凸多邊形的三角剖分也存在一一對應(yīng)關(guān)系。(4)矩陣連乘積中A1 A2 An中的每個矩陣Ai對應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，ibestp.(3). 繼續(xù)向下搜索生成結(jié)點F，得到可行解(1,1,1,0,0)，得到價值為86，更新bestp=86(如圖第3步) 第3步 第5步 第8步(4). 回溯：沿E回溯到左孩子

22、D，生成相應(yīng)右孩子G，得到部分解( 1,1,0,1 ),此時b=93.1 bbestp,可以生成右子樹（第4步在第5步的基礎(chǔ)上沒有H和I的圖形）(5). 繼續(xù)生成結(jié)點H,I，得到可行解( 1,1,0,1,0 ),價值為88，更新bestp=88(如圖第5步)(6). 回溯H生成J，得到部分解( 1,1,0,0 ),估計部分解b=9288（第6步在第8步的基礎(chǔ)上沒有K和L的圖形）(7). 繼續(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) (如

23、圖第8步)(9). 回溯,沿結(jié)點L向上回溯到結(jié)點B,生成結(jié)點M,得到部分解 (1,0), 估計部分解b=9092,回溯（第9步在第10步的基礎(chǔ)上沒有N的圖形）(10). 向上繼續(xù)回溯生成結(jié)點N，得到部分解(0)，此時得到的b=74+10*(46/27) =91.0392,回溯，此時已回到根結(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)解。 最優(yōu)裝載問題 P119 課件第P37-P54頁 假定n= 4，w= 8 , 6 , 2 , 3 ，c1 = c2 =12.試根據(jù)改進(jìn)后的最優(yōu)裝載算法找出最優(yōu)裝載量及相應(yīng)的最優(yōu)裝載方案。要求：a) 列出問題的解空間。b) 構(gòu)造解空間樹。c) 根據(jù)遞歸回溯算法求出最優(yōu)解和最優(yōu)值。六、