算法期末復(fù)習(xí)題final

1、 算法分析與設(shè)計期末復(fù)習(xí)題目 一、 選擇題 1下列算法中通常以自底向上的方式求解最優(yōu)解的是（   B      ）。A、備忘錄法B、動態(tài)規(guī)劃法C、貪心法D、回溯法2、衡量一個算法好壞的標(biāo)準(zhǔn)是（C ）。A 運行速度快 B 占用空間少 C 時間復(fù)雜度低 D 代碼短3、以下不可以使用分治法求解的是（D ）。A 棋盤覆蓋問題 B 選擇問題 C 歸并排序 D 0/1背包問題4下列是動態(tài)規(guī)劃算法基本要素的是（  D     ）。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)

2、解D、子問題重疊性質(zhì)5采用廣度優(yōu)先策略搜索的算法是（     A      ）。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法6、合并排序算法是利用（   A      ）實現(xiàn)的算法。A、分治策略   B、動態(tài)規(guī)劃法   C、貪心法    D、回溯法7、下列不屬于影響程序執(zhí)行時間的因素有哪些？ （ C ）A算法設(shè)計的策略 B問題的規(guī)模C編譯程序產(chǎn)

3、生的機器代碼質(zhì)量 D計算機執(zhí)行指令的速度8、使用分治法求解不需要滿足的條件是（A ）。A 子問題必須是一樣的B 子問題不能夠重復(fù)C 子問題的解可以合并D 原問題和子問題使用相同的方法解9、下面問題（B ）不能使用貪心法解決。A 單源最短路徑問題 B N皇后問題 C 最小花費生成樹問題 D 背包問題推薦精選10. 一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（   B    ）。A、重疊子問題B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解11. 以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為 ( D ) 。A、分支界限算法

4、0;     B、概率算法    C、貪心算法    D、回溯算法12. 實現(xiàn)最長公共子序列利用的算法是（     B      ）。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法13下列算法具有最優(yōu)子結(jié)構(gòu)的算法是 （D）A概率算法 B回溯法 C分支限界法 D動態(tài)規(guī)劃法14.算法分析是（ C）A.將算法用某種程序設(shè)計語言恰當(dāng)?shù)乇硎境鰜鞡.在抽象數(shù)據(jù)集合上執(zhí)行程序,以確定是否會產(chǎn)生錯誤的結(jié)果C.對算

5、法需要多少計算時間和存儲空間作定量分析D.證明算法對所有可能的合法輸入都能算出正確的答案15 衡量一個算法好壞的標(biāo)準(zhǔn)是（C ）A.運行速度快 B. 占用空間少 C.時間復(fù)雜度低 D. 代碼短16.二分搜索算法是利用（A）實現(xiàn)的算法。A.分治法 B.動態(tài)規(guī)劃法 C.貪心法 D.回溯法17用貪心法設(shè)計算法的關(guān)鍵是（ B ）。A.將問題分解為多個子問題來分別處理 B.選好最優(yōu)量度標(biāo)準(zhǔn)C.獲取各階段間的遞推關(guān)系式 D.滿足最優(yōu)性原理18.找最小生成樹的算法Kruskal的時間復(fù)雜度為（ D ）（其中n為無向圖的結(jié)點數(shù)，m為邊數(shù)）A O(n2) BO(mlogn) CO(nlogm)

6、 DO(mlogm)推薦精選19.回溯法搜索狀態(tài)空間樹是按照（C ）的順序。A.中序遍歷 B.廣度優(yōu)先遍歷 C.深度優(yōu)先遍歷 D.層次優(yōu)先遍歷20.采用廣度優(yōu)先策略搜索的算法是（ A ）。A.分支界限法B.動態(tài)規(guī)劃法C.貪心法 D.回溯法21.函數(shù)32n+10nlogn的漸進(jìn)表達(dá)式是( B ).A.O( 2n) B. O( 32n) C. O( nlogn ) D. O( 10nlogn)22.二分搜索算法的時間復(fù)雜性為（ C ）。A.O() B.O() C.O() D. O()23、快速排序算法的時間復(fù)雜性為（ D ）。A.O() B.O() C.O() D. O()24、算法是由若干條指令

7、組成的有窮序列，而且滿足以下性質(zhì)（ D ）A.輸入：有0個或多個輸入 B.輸出：至少有一個輸出C. 確定性：指令清晰，無歧義 D.有限性：指令執(zhí)行次數(shù)有限，而且執(zhí)行時間有限 A. (1)(2)(3) B. (1)(2)(4) C. (1)(3)(4) D.(1) (2)(3)(4)25、背包問題的貪心算法所需的計算時間為（ B ）A. O（n2n） B. O（nlogn） C.O（2n） D.O（n）26.下列算法中不能解決0/1背包問題的是（ A ）A 貪心法 B 動態(tài)規(guī)劃 C 回溯法 D 分支限界法27. 在尋找n個元素中第k小元素問題中，若使用快速排序算法思想，運用分治算法對n個元素進(jìn)行

8、劃分，應(yīng)如何選擇劃分基準(zhǔn)？下面 (D) 答案解釋最合理。A隨機選擇一個元素作為劃分基準(zhǔn)B取子序列的第一個元素作為劃分基準(zhǔn)C用中位數(shù)的中位數(shù)方法尋找劃分基準(zhǔn)D以上皆可行。但不同方法，算法復(fù)雜度上界可能不同推薦精選28. 分治法的設(shè)計思想是將一個難以直接解決的大問題分割成規(guī)模較小的子問題，分別解決子問題，最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題 ( C ) 。A問題規(guī)模相同，問題性質(zhì)相同 B問題規(guī)模相同，問題性質(zhì)不同C問題規(guī)模不同，問題性質(zhì)相同 D問題規(guī)模不同，問題性質(zhì)不同29、下面是貪心算法的基本要素的是（  C   

9、0; ）。A、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、定義最優(yōu)解30. 函數(shù)的漸進(jìn)表達(dá)式是（ D ）。A. O() B. O() C. O() D.O()二、填空題1、解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是 動態(tài)規(guī)劃 ，需要排序的是 回溯法 ，分支限界法 。2、使用回溯法進(jìn)行狀態(tài)空間樹裁剪分支時一般有兩個標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是 0/1背包問題 ，只使用約束條件進(jìn)行裁剪的是 N皇后問題 。3.貪心算法基本要素有 最優(yōu)度量標(biāo)準(zhǔn) 和 最優(yōu)子結(jié)構(gòu) 。4.回溯法解

10、旅行售貨員問題時的解空間樹是 排列樹 。5.二分搜索算法是利用 分治策略 實現(xiàn)的算法。6.算法的復(fù)雜性有 時間 復(fù)雜性和 空間 復(fù)雜性之分。7、程序是 算法     用某種程序設(shè)計語言的具體實現(xiàn)。8、算法的“確定性”指的是組成算法的每條 指令 是清晰的，無歧義的。9.矩陣連乘問題的算法可由 動態(tài)規(guī)劃 設(shè)計實現(xiàn)。10回溯法搜索解空間樹時，常用的兩種剪枝函數(shù)為 約束函數(shù) 和 限界函數(shù) 推薦精選 。11.任何可用計算機求解的問題所需的時間都與其 規(guī)模 有關(guān)。12.快速排序算法的性能取決于 劃分的對稱性 。13.背包問題的貪心算法void Knapsa

11、ck(int n,float M,float v,float w,float x) Sort(n,v,w); int i; for (i=1;i<=n;i+) xi=0; float c=M; for (i=1;i<=n;i+) if (wi>c) break; xi=1; c - =wi; if (i<=n) xi=c/wi;14下面算法的基本運算是 加法（或：賦值） 運算，該算法中第4步執(zhí)行了 2n-1 次。算法 COUNT輸入：正整數(shù)n（n=）。輸出：count的值。 1. count=0 2. while n>=1 3. for j=1 to n 4. c

12、ount =count+1 5. end for6. n=n/27. end while 推薦精選 end COUNT15.算法是由若干條指令組成的有窮序列，且要滿足輸入、 輸出、確定性和 有限性四條性質(zhì)。16.快速排序、插入排序和選擇排序算法中， 快速排序 算法是分治算法。17. 下面算法的基本語句是_ S = S + i*j;_, 算法的時間復(fù)雜度是_O()_int fun(int n)int S = 0;for (int i=1; i <=n; i+ )for(int j=1; j<n i ; j+)S = S + i*j;return S;18. 最小生成樹的prim算法應(yīng)

13、用的是 貪心 算法思想。19. 分治算法的基本步驟包括 分解子問題，遞歸求解子問題，合并解 20. 歸并排序和快速排序在平均情況下的時間復(fù)雜度都是O（nlogn）,但是最壞情況下兩種算法有區(qū)別，其中歸并排序為 O（nlogn） ，快速排序為 _O() 二、 算法設(shè)計1下面是用回溯法求解圖的m著色問題的算法（求出所有解）。圖的m著色問題：給定一個無向連通圖G和m種顏色，給圖G的所有頂點著色，使得任何兩相鄰頂點的顏色不同。已有函數(shù)color(k)用于在前k-1個頂點已著色的情況下，判斷第k個頂點是否可著顏色推薦精選xk； 是則返回true, 否則返回false。輸入：正整數(shù)m, n和含n個頂點的無

14、向連通圖G的鄰接矩陣graph。輸出：圖G的m著色問題的所有解,若無解，則輸出no solution。flag=false k=1; x1=0while k>=1 while (1) xk=xk+1 if color(k) then if (2) then flag=true; output x1.n else k= (3) (4) end if end if end while (5) end while if not flag then output “no solution”end m-COLORING(1) xk<m (2) k=n (3) k+1 (4) xk=0 (5)

15、 k=k-12下面是求解矩陣鏈乘問題的動態(tài)規(guī)劃算法。矩陣鏈乘問題：給出n個矩陣M1, M2, , Mn , Mi 為riri+1階矩陣，i=1, 2, , n，求計算M1M2Mn所需的最少數(shù)量乘法次數(shù)。記 Mi, j=MiMi+1Mj , i<=j。設(shè)Ci, j, 1<=i<=j<=n, 表示計算Mi, j的所需的最少數(shù)量乘法次數(shù)，則推薦精選 算法 MATCHAIN輸入：矩陣鏈長度n, n個矩陣的階r1.n+1, 其中r1.n為n個矩陣的行數(shù)，rn+1為第n個矩陣的列數(shù)。輸出：n個矩陣鏈乘所需的數(shù)量乘法的最少次數(shù)。for i=1 to n Ci, i= （1） for

16、d=1 to n-1 for i=1 to n-d j= (2) Ci, j= for k=i+1 to j x= (3) if x<Ci, j then (4) =x end if end for end for end for return (5) end MATCHAIN (1) 0 (2) i+d (3) Ci, k-1+Ck, j+ri*rk*rj+1 (4) Ci, j (5) C1, n3.下面是用回溯法解n皇后問題的算法（求出所有解）。n皇后問題：在n x n棋盤上放置n個皇后使得任何兩個皇后不能互相攻擊。（如果兩個皇后處在同一行，或同一列，或同一斜線上，則她們能互相攻擊

17、。）推薦精選算法 NQUEENS輸入：正整數(shù)n。輸出：n皇后問題的所有解x1.n,若無解，則輸出No solution。flag=false k=1 ; x1=0 while (1) while xk<n xk= (2) if place(k) then if k=n then flag=true；output x1.n else k= (3) (4) end if end if end while (5) end while if not flag then output “No solution” end NQUEENS過程place (k)/判斷第k行皇后是否與前k-1行皇后沖突，

18、是則返回false, 否 /則返回true。end place(1) k>=1 (2) xk+1 (3) k+1 (4) xk=0 推薦精選(5) k=k-1 4. 遞歸的快速排序算法：template <class Type>void QuickSort (Type a , int low, int high) if ( (1) ) int i=Partition(a, low, high); QuickSort（a, low, i-1）; (2) ; 解：（1）low < high （2）QuickSort（a, i+1, high）5、n后問題的遞歸的回溯算法，設(shè)

19、已經(jīng)存在全局變量n代表皇后個數(shù)。void Queen:Backtrack(int t) if ( (1) ) sum+; /sum表示可行解的個數(shù) else for (int i=1; i<=n; i+) xt= i; /xt表示第t個皇后的列數(shù) if ( Place(t) ) / 第t個皇后放在第i列不違背約束條件 (2) ; 解：（1） t > n (2) Backtrack(t+1)三、 簡答、計算題 1、對于圖所示多段圖，用動態(tài)規(guī)劃法求從頂點0到頂點12的最短路徑，寫出求解過程。推薦精選首先求解初始子問題，可直接獲得：d(0, 1)=c015(01)d(0, 2)=c023

20、(02)再求解下一個階段的子問題，有：d(0,3)= d(0, 1)+ c13 =6 (13)d(0,4)=mind(0,1)+ c14 ,d(0,2)+ c24=8(14)d(0,5)=min d(0,1)+ c15, d(0,2)+ c25 = 10(25)d(0,6)= d(0,2)+ c26 = 9 (26)再下一階段：d(0,7) = min d(0,3)+ c37, d(0,4)+ c47 = 11 (47)d(0,8) = min d(0,3)+ c38, d(0,4)+ c48, d(0,5)+ c58, d(0,6)+ c68 = 13(48)d(0,9) = min d(0

21、,5)+ c59, d(0,6)+ c69 = 13 (59)再下一階段：d(0,10) = min d(0,7)+ c7_10, d(0,8)+ c8_10 = 14 (710)d(0, 11) = min d(0,7)+ c7_11, d(0,8)+ c8_11, d(0,8)+ c9_11 = 15 (811)最后：d(0, 12) = min d(0,10)+ c10_12, d(0,11)+ c11_12 = 18 (1012)即，最短路徑為18, 其中一條最短路徑為：01471012 （具體路徑可能不止一條）2、對于字符集合M=A,B,C,D,E,F，設(shè)這些字符在文本中出現(xiàn)的頻率分

22、別為8,1,3,10,6,5，畫出字符集合M的Huffman編碼樹，并給出各字符的Huffman編碼。字符集合M的Huffman編碼樹是：推薦精選 各字符的Huffman編碼：A: 01 B:1000 C: 1001 D: 11 E:00 F: 1013 . 用動態(tài)規(guī)劃法求如下0/1背包問題的最優(yōu)解：有5個物品，其重量分別為（3,2,1,4,5），價值分別為（25,20,15,40,50），背包容量為6. 寫出求解過程（設(shè)計表格和填寫表格）解：設(shè)計一個二維表 V(i, j) 表示將前i個物品裝進(jìn)容量為j的背包所能獲得的最大價值，根據(jù)以下遞推式填表：§ 若wi > j, V(i, j) = V(i 1, j)§ 若 wi <= j, V(i, j) = max V(i-1, j) , V(i-1, j - wi) + vij = 0j = 1j = 2j = 3j = 4j = 5j = 6i = 00000000i =