算法分析與設(shè)計(jì)期末考試復(fù)習(xí)題綱

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

2、歸算法的時間復(fù)雜度記為T (N),已知T (1) =1 , T (N) =2T (N/2 ) +N/2 ,用0表示的時間復(fù)雜度為(C)。A. 0(logN)B. 0(N)C. 0(NlogN)D. 0(N2logN)5.直接或間接調(diào)用自身的算法稱為(B )。A.貪心算法B.遞歸算法C.迭代算法D.回溯法Fibonacci數(shù)列中，第4個和第11個數(shù)分別是（D ）A. 5, 89B. 3, 89C. 5, 144D, 3, 144.在有8個頂點(diǎn)的凸多邊形的三角剖分中，恰有（B ）。A. 6條弦和7個三角形B . 5條弦和6個三角形C. 6C. 6條弦和6個三角形D . 5條弦和5個三角形.一個問題

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

4、 LCS問題BC. 0-1C. 0-1背包問題哈夫曼編碼問題用回溯法求解最優(yōu)裝載問題時，若待選物品為m種，貝口該問題的解空間樹的結(jié)點(diǎn)個數(shù)為()m+1A. m!B. 2C. 2m+1 -1D . 2m二分搜索算法是利用(A )實(shí)現(xiàn)的算法。A.分治策略B .動態(tài)規(guī)劃法C.貪心法D.回溯法下列不是動態(tài)規(guī)劃算法基本步驟的是( B )。P44A.找出最優(yōu)解的性質(zhì)B構(gòu)造最優(yōu)解C.算出最優(yōu)解(應(yīng)該是最優(yōu)值)D.定義最優(yōu)解下面問題(B )不能使用貪心法解決。A.單源最短路徑問題 B . N皇后問題C.最小花費(fèi)生成樹問題D .背包問題使用二分搜索算法在n個有序元素表中搜索一個特定元素，在最好情況和最壞情況下搜索

5、的時間復(fù)雜性分別為(A )。P17 A, O(1),O(logn)B. O(n) , O(logn)C. O(1), O(nlogn)D. O(n) , O(nlogn)優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原貝是(C)。P162C. 0-1背包問題A.C. 0-1背包問題A.先進(jìn)先出C.結(jié)點(diǎn)的優(yōu)先級19.下面不是分支界限法搜索方式的是（。P161A.19.下面不是分支界限法搜索方式的是（。P161A.廣度優(yōu)先.最小耗費(fèi)優(yōu)先.深度優(yōu)先活結(jié)點(diǎn)表的組織形式是最大堆.數(shù)組 TOC o 1-5 h z C.最大效益優(yōu)先D20.分支限界法解最大團(tuán)問題時，（B ）。A.最小堆BC.棧D21.下列關(guān)于計(jì)算機(jī)算法

6、的描述不正確的是（ C ）。P1A.算法是指解決問題的一種方法或一個過程B.算法是若干指令的有窮序列C.算法必須要有輸入和輸出D.算法是編程的思想22.下列關(guān)于凸多邊形最優(yōu)三角剖分問題描述不正確的是（A ）。A. n+1個矩陣連乘的完全加括號和n個點(diǎn)的凸多邊形的三角剖 分對應(yīng)B.在有n個頂點(diǎn)的凸多邊形的三角剖分中，恰有 n-3條弦C.該問題可以用動態(tài)規(guī)劃法來求解D.在有n個頂點(diǎn)的凸多邊形的三角剖分中，恰有 n-2個三角形23.動態(tài)規(guī)劃法求解問題的基本步驟不包括（C ）。P44A.遞歸地定義最優(yōu)值B.分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征C.根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解（可以省去的）D.以

7、自底向上的方式計(jì)算出最優(yōu)值24.分治法所能解決的問題應(yīng)具有的關(guān)鍵特征是(C）。P16A.該問題的規(guī)?？s小到一定的程度就可以容易地解決B.該問題可以分解為若干個規(guī)模較小的相同問題C.利用該問題分解出的子問題的解可以合并為該問題的解D.該問題所分解出的各個子問題是相互獨(dú)立的下列關(guān)于回溯法的描述不正確的是(D )。P114A.回溯法也稱為試探法B.回溯法有“通用解題法”之稱C.回溯法是一種能避免不必要搜索的窮舉式搜索法D.用回溯法對解空間作深度優(yōu)先搜索時只能用遞歸方法實(shí)現(xiàn)常見的兩種分支限界法為(D )。P161A.廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B.隊(duì)列式(FIFO)分支限界法與堆棧式分支限

8、界法；C.排列樹法與子集樹法；D.隊(duì)列式(FIFO)分支限界法與優(yōu)先隊(duì)列式分支限界法；二、填空題1. f(n)=3n 2+10 的漸近性態(tài) f(n)= 0( n 2 ),g(n)=10log3 n 的漸近性態(tài) g(n)= 0( n)2. 一個“好”的算法應(yīng)具有正確性、可讀性、健壯性和高效率和低存儲量需求等特性。.算法的時間復(fù)雜性函數(shù)表示為C=F(N,I,A),分析算法復(fù)雜性的目的在于比較求解同意問題的兩個不同算法的效率的效率。.構(gòu)成遞歸式的兩個基本要素是遞歸的邊界條件 和 遞歸的定義。.單源最短路徑問題可用分支限界法和貪心算法求解。.用分治法實(shí)現(xiàn)快速排序算法時，最好情況下的時間復(fù)雜性為_O(n

9、logn) ,最壞情況下的時間復(fù)雜性為0(M2)該算法所需的時間與 運(yùn)行時間 和劃匠 兩方面因素有關(guān)。P26. 0-1背包問題的解空間樹為完全二叉樹；n后問題的解空間樹為科匚樹；.常見的分支限界法有隊(duì)列式(FIFO)分支限界法和優(yōu)先隊(duì)列式分支限 界法。.回溯法搜索解空間樹時常用的兩種剪枝函數(shù)為約束函數(shù)和剪枝函數(shù)。.分支限界法解最大團(tuán)問題時，活結(jié)點(diǎn)表的組織形式是最大堆 分支限界法解單源最短路徑問題時，活結(jié)點(diǎn)表的組織形式是最小堆。三、算法填空題.遞歸求解Hanoi塔問題/階乘問題例1 :階乘函數(shù)n! P12階乘的非遞歸方式定義：邊界條件遞歸方程試寫出階乖的遞歸式及算法 1 n =0 n(n 1)!

10、 n . 邊界條件遞歸方程遞歸算法：int factorial (int n)遞歸調(diào)用 if (n=0) retur n 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的圓盤移 至塔座 上。void hanoi (int n, int a, int c, int b)if (n 0)hanoi(n-1, a, b, c);move(a,

11、c);hanoi(n-1, b, c, a);.用分治法求解快速排序問題快速排序算法 P25、作業(yè)、課件第 2章(2)42頁-50頁template void 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ù)的具體實(shí)現(xiàn)templateint Partition (Type a, int p, int r) int i = p, j = r + 1;Type x=ap;/將 x的元素交換到左邊區(qū)域/ 將 X的元素

12、交換到右邊區(qū)域while (true) while (a+i x & ix);if (i = j) break;Swap(ai, aj);ap = aj;aj = x;return j;).用貪心算法求解最優(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 -

13、= wtj;4.用回溯法求解0-1背包/批處理作業(yè)調(diào)度/最大團(tuán)問題，例1:用回溯法求解0-1背包P133課件第5章第4-38頁要會畫解空間樹templateclass Knapprivate:Typep Bound(int i); / void Backtrack(int i);Typew c; / 背包容量 int n; /物品數(shù)計(jì)算上界Typew *w; /Typep *p; /Typew cw; /物品重量數(shù)組物品價(jià)值數(shù)組當(dāng)前重量Typep cp; /當(dāng)前價(jià)值Typep bestp; /當(dāng)前最優(yōu)價(jià)值)；void Knap:Backtrack(int i) if(in) bestp=cp;

14、 return; if(cw+wibestp) / 進(jìn)入右子樹Backtrack(i+1);Typep Knap:Bound(int i)Typew cleft=c-cw; /剩余的背包容量Typep b=cp; /b為當(dāng)前價(jià)值/依次裝入單位重量價(jià)值高的整個物品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 operat

15、or =a.d);int ID; /物品編號float d; /單位重量價(jià)值;Typep Knapsack( Typep p,Typew w,Typew c,int n) / 為 Typep Knapsack 初始化Typew W=0; / 總重量Typep P=0; / 總價(jià)值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;Qu

16、ickSort(Q,0,n-1); /依物品單位重量價(jià)值非增排序Knap K;K.p=new Typepn+1;K.w=new Typewn+1;for(int i=1;i n) for (int j = 1; j = n;j+) bestxj = xj; bestf = f; else各作業(yè)所需的處理時間當(dāng)前作業(yè)調(diào)度當(dāng)前最優(yōu)作業(yè)調(diào)度機(jī)器2完成處理時間機(jī)器1完成處理時間完成時間和當(dāng)前最優(yōu)的完成時間和作業(yè)數(shù)for (int j = i; j f1)?f2i-1:f1)+mxj2;f+=f2i；if (f n) for(int j=1;jbestn) /如有可能在右子樹中找到更大的團(tuán))則進(jìn)入右子樹

17、 xi=0; Backtrack(i+1); 計(jì)算時間：O(n2n)簡答題.請簡述使用動態(tài)規(guī)劃算法解題的基本步驟。P44動態(tài)規(guī)劃的設(shè)計(jì)分為以下4個步驟：找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。(3)以自底向上的方式計(jì)算出最優(yōu)值。(4)根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。.簡述動態(tài)規(guī)劃方法與分治法的異同。P44相同點(diǎn)：動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，然后從這些子問題的解得到原問題的解。不同點(diǎn)：分治法的子問題互相獨(dú)立且與原問題相同。與分治法不同的是，適合于動態(tài)規(guī)劃求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。也就是各個子問題包含公共的子

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

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

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

21、三角剖分與矩陣連乘P61一般來說，凸多邊形的三角剖分和有n-1個葉節(jié)點(diǎn)的語法樹存在對應(yīng)關(guān)系。N個矩陣連乘的完全加括號和有n個葉節(jié)點(diǎn)的語法樹也存在對應(yīng)關(guān) 系。所以，n個矩陣連乘的完全加括號和有n+1個節(jié)點(diǎn)的凸多邊形的三角剖 分也存 在對應(yīng)關(guān)系。矩陣連乘積中A1 A2 - An中的每個矩陣Ai對應(yīng)于凸(n+1)邊形中的一條邊vi- 1vi。三角剖分中的一條弦vivj ,vj ,對應(yīng)于矩F$連乘積Ai+1:j(5)矩陣連乘積的最優(yōu)計(jì)算次序問題是凸多邊形最優(yōu)三角剖分問題的特殊情況。課后習(xí)題(第3章小結(jié)*)對于如下矩陣鏈P=10,100,5,50,30,20,60,45,50,請按照構(gòu)造其最優(yōu)完全加括號

22、方式，并列出相應(yīng)的語法樹和最優(yōu)三角剖分圖。.用貪心算法求解活動安排問題/最小生成樹問題/哈夫曼編碼問題。貪心算法求解活動安排問題例：設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：最小生成樹問題 P103-P105哈夫曼編碼問題，前綴碼二叉樹表示法例子：圖a:與固定長度編碼對應(yīng)的樹（葉子高度一致）圖b:與可變長度編碼對應(yīng)的樹（葉子高度不一致）.用回溯法求解0-1背包問題/最優(yōu)裝載問題。用回溯法求0-1背包問題。P133,根據(jù)排序得到部分解(1,1,1,0)，估計(jì)當(dāng)前部分解的價(jià)值b,86+(50-45)*1.67=94.3,b bestp.繼續(xù)向下搜索生成結(jié)點(diǎn)F得到可行解(1

23、,1,1,0,0),得到價(jià)值為86,更新bestp=86 (如圖第3步)第3步第5步第8步4).回溯：沿E回溯到左孩子D,生成相應(yīng)右孩子G彳導(dǎo)到部分解(1,1,0,1 ),此時b=93.1 bbestp,可以生成右子樹(第4步在第5步的基礎(chǔ)上沒有H和I的圖形).繼續(xù)生成結(jié)點(diǎn)H,I,得到可行解(1,1,0,1,0 ),價(jià)值為88,更新bestp=88 (如圖第5步).回溯H生成J,得到部分解(1,1,0,0 )，估計(jì)部分解b=9288 (第6步在第8步的基礎(chǔ)上沒有K和L的圖形).繼續(xù)生成結(jié)點(diǎn)K,得到可行解(1,1,0,0, 1 )，價(jià)值為92,更新bestp=92 (第7步在第8步的基礎(chǔ)上沒有L

24、的圖形). K是左孩子，生成其對應(yīng)的右孩子L,得到可行解(1,1,0,0,0)(如圖第8步).回溯，沿結(jié)點(diǎn)L向上回溯到結(jié)點(diǎn)B,生成結(jié)點(diǎn)M,得到部分解(1,0)，估計(jì)部分解b=9092,回溯(第9步在第10步的基礎(chǔ)上沒有N的圖形).向上繼續(xù)回溯生成結(jié)點(diǎn)N,得到部分解(0),此時得到的b=74+10*(46/27)=91.0392,回溯，此時已回到根結(jié)點(diǎn)，結(jié)束。最優(yōu)解(1,1,0,0, 1 ),價(jià)值為92.(如圖第10步)練習(xí)n=8, M=110W=( 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)解和