《算法分析與設計》期末考試復習題綱

1、精品文檔精品文檔.算法分析與設計期末復習題一、選擇題算法必須具備輸入、輸出和（ D ）等 4 個特性。A可行性和安全性確定性和易讀C有窮性和安全性有窮性和確定性算法分析中，記號O表示（B ），記號表示（ AA.漸進下界漸進上界C.非緊上界緊漸進界n 時的計算時間為 T(n)=3*2n完成概算法的時間為t 秒。現(xiàn)有另一臺計算機，其運行速度為第一臺的64 倍，那么在這臺新機器上用同一算法在tB 解題方法：3*2n*64=3*2xAn+8Cn+7設問題規(guī)模為 N 時，某遞歸算法的時間復雜度記為 T(N)，已知 T(1)=1T(N)=2T(N/2)+N/2，用O（ C ）。AO(logN)CO(Nlo

2、gN)直接或間接調用自身的算法稱為（B ） 。A貪心算法遞歸算C迭代算法回溯法Fibonacci數(shù)列中，第4個和第11個數(shù)分別是（D ） A5，89C5，144在有8個頂點的凸多邊形的三角剖分中，恰有（ B）。A6條弦和7個三角形條弦和6個三角形C6條弦和6個三角形條弦和5個三角形一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征是問題的（ B）A重疊子問題最優(yōu)子結構性質 C貪心選擇性質定義最優(yōu)解下列哪個問題不用貪心法求解（ C） 。 A哈夫曼編碼問題單源最短路徑問題C最大團問題最小生成樹問下列算法中通常以自底向上的方式求解最優(yōu)解的是（B ） A備忘錄法動態(tài)規(guī)劃法C貪心法回溯法下列算法中不能解決

3、0/1背包問題的是（ A）A貪心法動態(tài)規(guī)劃C回溯法分支限界法下列哪個問題可以用貪心算法求解（D ） 。ALCS問題批處理作業(yè)問題C0-1背包問題哈夫曼編碼問題用回溯法求解最優(yōu)裝載問題時，若待選物品為 m 種，則該問題的解空間樹的結個數(shù)為（）。Am!B2m+1C2m+1-1D2m二分搜索算法是利用（ A）實現(xiàn)的算法。 A分治策略動態(tài)規(guī)劃C貪心法回溯法下列不是動態(tài)規(guī)劃算法基本步驟的是（ B。 P44 A找出最優(yōu)解的性質構造最優(yōu)解C算出最優(yōu)應該是最優(yōu))D定義最優(yōu)下面問題（B）不能使用貪心法解決。 A單源最短路徑問題BN皇后問C最小花費生成樹問題D背包問題使用二分搜索算法在n下搜索的時間復雜性分別為（

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

5、陣連乘的完全加括號和n 個點的凸多邊形的三角剖分對B在有n 個頂點的凸多邊形的三角剖分中，恰有n-3 條弦C該問題可以用動態(tài)規(guī)劃法來求解D在有n 個頂點的凸多邊形的三角剖分中，恰有n-2 個三角形（ C ）P44 A遞歸地定義最優(yōu)值 B分析最優(yōu)解的性質，并刻畫其結構特征 CD以自底向上的方式計算出最優(yōu)值分治法所能解決的問題應具有的關鍵特征是（ C）。P16A該問題的規(guī)?？s小到一定的程度就可以容易地解決 B該問題可以分解為若干個規(guī)模較小的相同問題 CD該問題所分解出的各個子問題是相互獨立的下列關于回溯法的描述不正確的是（D ）P114 A回溯法也稱為試探法 B回溯法有“通用解題法”之稱 C回溯法

6、是一種能避免不必要搜索的窮舉式搜索D用回溯法對解空間作深度優(yōu)先搜索時只能用遞歸方法實現(xiàn)常見的兩種分支限界法為（ D）P161廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；隊列式（FIFO）分支限界法與堆棧式分支限界法；排列樹法與子集樹法；隊列式（FIFO）分支限界法與優(yōu)先隊列式分支限界法；二、填空題1. f(n)=3n2+10的漸近性態(tài)f(n)= O( n2)，g(n)=10log3n的漸近性態(tài)g(n)= O(n。一個“好”的算法應具有正確性、可讀性、健壯性和高效率低存儲量需求等特性。算法的時間復雜性函數(shù)表示為C=F(N,I,A)，分析算法復雜性的目的在于比求解同意問題的兩個不同算法的效率的效率。構

7、成遞歸式的兩個基本要素是 遞歸的邊界條件 和 遞歸的定義。單源最短路徑問題可用 分支限界法 和貪心算法求解。用分治法實現(xiàn)快速排序算法時最好情況下的時間復雜性為 O(nlogn)最壞情況的時間復雜性為O(n2)，該算法所需的時間與 運行時間和劃分兩方面因素有關P260-1n常見的分支限界法有隊列式分支限界法和優(yōu)先隊列式分支限界法。回溯法搜索解空間樹時常用的兩種剪枝函數(shù)為 約束函數(shù) 和 剪枝函數(shù) 。分支限界法解最大團問題時，活結點表的組織形式是最大堆；分支限界解單源最短路徑問題時，活結點表的組織形式是最小堆 。三、算法填空題n(nn(n(n2) 21階乘的非遞歸方式定義：試寫出階乖的遞歸式及算法。

8、遞歸式為： 1n 0邊界條件nn(n 1)! n 0遞歸方程遞歸算法：int factorial (int n) if (n=0) return 1;遞歸出口return n * factorial (n-1);遞歸調用例 2:用遞歸技術求解 Hanoi 塔問題,Hanoi 塔的遞歸算法。P15其中Hanoi (int n, int a, int c, int b表示將塔座A 上的n 個盤子移至塔座B為輔助。Move(a,c)表示將塔座a 上編號為n 的圓盤移至塔座c 上。void hanoi (int n, int a, int c, int b)if (n 0)hanoi(n-1, a,

9、b, move(a,c); hanoi(n-1, b, c, 用分治法求解快速排序問題。快速排序算法P25 、作業(yè)、課件第2章（2）42頁-50templatevoid QuickSort (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 的元

10、素交換到右邊區(qū)域while (true) while (a+i x & ix);if (i = j) Swap(ai, aj);ap = aj; aj = x; return j;用貪心算法求解最優(yōu)裝載問題。最優(yōu)裝載問題 P954(2)3-8templatevoid 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 class Knapprivate:Typep Bound(i

11、nt i); void Backtrack(int i);Typew c; int n; 物品數(shù)Typew *w; Typep *p; Typew cw; 當前重量Typep cp; 當前價值Typep bestp; /當前最優(yōu)價值;void Knap:Backtrack(int i)if(in)bestp=cp;return;if(cw+wibestp) /Backtrack(i+1);Typep Knap:Bound(int i)Typew cleft=c-cw; Typep b=cp; /b/依次裝入單位重量價值高的整個物品while(i=n&wi=cleft) cleft-=wi;b+

12、=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 w,Typew c,int n) /為 Typep Knapsack 初始化Typew W=0; /總重量Typep P=0; /總價值Object* Q=new Objectn; 0for(int i=1;i=n;i

13、+) 初始物品數(shù)組數(shù)據 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=new Typewn+1; for(int 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;delete Q;delete K.w;delete K.p;return K.bestp;例 2：批處理作業(yè)調度 課件第 5

14、章(2)P2-5 問題描述,課本 P125-127算法描述： class Flowshopstaticint m,/ 各作業(yè)所需的處理時間 x,/ 當前作業(yè)調度 bestx, / 當前最優(yōu)作業(yè)調度 f2,/ 2完成處理時間f1,/ 1 完成處理時間f,/ 完成時間和bestf,/ 當前最優(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 f1)?f2i-1:f1)+mxj2;f+=f2i;if (f n) fo

15、r(int j=1;j=n;j+) bestxj=xj; bestn=cn; return;/判斷第 i 個頂點是否與已選頂點都有邊相連int OK=1;for(int j=1;jbestn) /如有可能在右子樹中找到更大的團，則進入右子樹xi=0;Backtrack(i+1);計算時間：O(n2n)四、簡答題4(1)找出最優(yōu)解的性質，并刻劃其結構特征。(2)遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。根據計算最優(yōu)值時得到的信息，構造最優(yōu)解。P44相同點：動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題, 然后從這些子問題的解得到原問題的解。不同點：分治法的子問題互相

16、獨立且與原問題相同。與分治法不同的是，適合于動態(tài)規(guī)劃求解的問題，經分解得到的子問題往往不是互相獨立的。也就是各個子問題包含公共的子子問題。試比較PrimKruskal105-P107相同點：Prim(普里姆)算法和 Kruskal(克魯斯卡爾)算法都可以看作是應用貪心算法構造最小生成樹的例子。利用了最小生成樹性質。不同點：Prim(普里姆)算法：在這個過程中選取到的所有邊恰好構成G 的一棵最小生成樹 中包Gn-1Kruskal通子集來進行貪心選擇。而是通過選擇具有最小權的邊的集合來進行貪心選擇。在選擇的 同時可以進行連通操作以便形成生成樹。P16166(1)分支限界法以廣度優(yōu)先或以最小耗費（最

17、大效益）優(yōu)先的方式搜索問題的解空間樹。(2)每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。結點表中。直持續(xù)到找到所需的解或活結點表為空時為止。P161 課件第 6(15不同點：求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。小耗費優(yōu)先的方式搜索解空間樹。五、算法應用題三角剖分的結構及其相關問題P61語法樹與完全加括號方式一個表達式的完全加括號方式相應于一棵完全二叉樹，稱為表達式的語法樹。例如，完全加括號的矩陣連乘積(A1(A2A3)(

18、A4(A5A6)所相應的語法樹如圖 (a)所示。語法樹與凸多邊形三角剖分凸多邊形P=v0,v1,vn-1的三角剖分也可以用語法樹表示。v0v )v0v 6 是三角形6 的一條邊。2、三角剖分與矩陣連乘P61(1)一般來說，凸多邊形的三角剖分和有n-1 個葉節(jié)點的語法樹存在一一對應關系。(2)N 個矩陣連乘的完全加括號和有n 個葉節(jié)點的語法樹也存在一一對應關系 。n個矩陣連乘的完全加括號和有n+1關系。矩陣連乘積中A1 A2 An 中的每個矩陣Ai (n+1)邊形中的一條邊vi-1vi剖分中的一條弦vivj，ibestp,可以生成右子樹（4 5 步的基礎上沒有H I 的圖形）H,I，得到可行解(

19、 1,1,0,1,0 ),bestp=88(5 步) (6).HJ，得到部分解( 1,1,0,0 ),估計部分解b=9288（6 8 步的基礎上沒有KL的圖形）K，得到可行解( 1,1,0,0, 192bestp=92（7 8 步的基礎上沒有L的圖形）KL，得到可行解( 1,1,0,0,0)8 步) (9).L 向上回溯到結點B,M,得到部分解 (1,0), 估計部分解b=9092,回溯（9 10 步的基礎上沒有N 的圖形）(10). 向上繼續(xù)回溯生成結點N(0b=74+10*(46/27)=91.0392,1,1,0,0, 192.(10 步)練習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=