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

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

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

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

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

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

6、 DO(mlogm)推薦精選19.回溯法搜索狀態(tài)空間樹(shù)是按照（C ）的順序。A.中序遍歷 B.廣度優(yōu)先遍歷 C.深度優(yōu)先遍歷 D.層次優(yōu)先遍歷20.采用廣度優(yōu)先策略搜索的算法是（ A ）。A.分支界限法B.動(dòng)態(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.二分搜索算法的時(shí)間復(fù)雜性為（ C ）。A.O() B.O() C.O() D. O()23、快速排序算法的時(shí)間復(fù)雜性為（ D ）。A.O() B.O() C.O() D. O()24、算法是由若干條指令

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

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

9、0; ）。A、重疊子問(wèn)題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背包問(wèn)題可以使用動(dòng)態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是 動(dòng)態(tài)規(guī)劃 ，需要排序的是 回溯法 ，分支限界法 。2、使用回溯法進(jìn)行狀態(tài)空間樹(shù)裁剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問(wèn)題和0/1背包問(wèn)題正好是兩種不同的類(lèi)型，其中同時(shí)使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是 0/1背包問(wèn)題 ，只使用約束條件進(jìn)行裁剪的是 N皇后問(wèn)題 。3.貪心算法基本要素有 最優(yōu)度量標(biāo)準(zhǔn) 和 最優(yōu)子結(jié)構(gòu) 。4.回溯法解

10、旅行售貨員問(wèn)題時(shí)的解空間樹(shù)是 排列樹(shù) 。5.二分搜索算法是利用 分治策略 實(shí)現(xiàn)的算法。6.算法的復(fù)雜性有 時(shí)間 復(fù)雜性和 空間 復(fù)雜性之分。7、程序是 算法     用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。8、算法的“確定性”指的是組成算法的每條 指令 是清晰的，無(wú)歧義的。9.矩陣連乘問(wèn)題的算法可由 動(dòng)態(tài)規(guī)劃 設(shè)計(jì)實(shí)現(xiàn)。10回溯法搜索解空間樹(shù)時(shí)，常用的兩種剪枝函數(shù)為 約束函數(shù) 和 限界函數(shù) 推薦精選 。11.任何可用計(jì)算機(jī)求解的問(wèn)題所需的時(shí)間都與其 規(guī)模 有關(guān)。12.快速排序算法的性能取決于 劃分的對(duì)稱(chēng)性 。13.背包問(wèn)題的貪心算法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下面算法的基本運(yùn)算是 加法（或：賦值） 運(yùn)算，該算法中第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.算法是由若干條指令組成的有窮序列，且要滿(mǎn)足輸入、 輸出、確定性和 有限性四條性質(zhì)。16.快速排序、插入排序和選擇排序算法中， 快速排序 算法是分治算法。17. 下面算法的基本語(yǔ)句是_ S = S + i*j;_, 算法的時(shí)間復(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. 最小生成樹(shù)的prim算法應(yīng)

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

14、向連通圖G的鄰接矩陣graph。輸出：圖G的m著色問(wèn)題的所有解,若無(wú)解，則輸出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下面是求解矩陣鏈乘問(wèn)題的動(dòng)態(tài)規(guī)劃算法。矩陣鏈乘問(wèn)題：給出n個(gè)矩陣M1, M2, , Mn , Mi 為riri+1階矩陣，i=1, 2, , n，求計(jì)算M1M2Mn所需的最少數(shù)量乘法次數(shù)。記 Mi, j=MiMi+1Mj , i<=j。設(shè)Ci, j, 1<=i<=j<=n, 表示計(jì)算Mi, j的所需的最少數(shù)量乘法次數(shù)，則推薦精選 算法 MATCHAIN輸入：矩陣鏈長(zhǎng)度n, n個(gè)矩陣的階r1.n+1, 其中r1.n為n個(gè)矩陣的行數(shù)，rn+1為第n個(gè)矩陣的列數(shù)。輸出：n個(gè)矩陣鏈乘所需的數(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皇后問(wèn)題的算法（求出所有解）。n皇后問(wèn)題：在n x n棋盤(pán)上放置n個(gè)皇后使得任何兩個(gè)皇后不能互相攻擊。（如果兩個(gè)皇后處在同一行，或同一列，或同一斜線上，則她們能互相攻擊

17、。）推薦精選算法 NQUEENS輸入：正整數(shù)n。輸出：n皇后問(wèn)題的所有解x1.n,若無(wú)解，則輸出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過(guò)程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后問(wèn)題的遞歸的回溯算法，設(shè)

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

20、(02)再求解下一個(gè)階段的子問(wèn)題，有：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、對(duì)于字符集合M=A,B,C,D,E,F，設(shè)這些字符在文本中出現(xiàn)的頻率分

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