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

1、算法分析與設(shè)計(jì)期末復(fù)習(xí)題目選擇題1列算法中通常以自底向上的方式求解最優(yōu)解的是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 棋盤覆蓋問(wèn)題 B 選擇問(wèn)題 C 歸并排序D 0/1背包問(wèn)題4以下是動(dòng)態(tài)規(guī)劃算法根本要素的是。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子問(wèn)題重疊性質(zhì)5采用廣度優(yōu)先策略搜索的算法是A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法6、合并排序算法是利用實(shí)現(xiàn)的算法A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法7、列不屬于影響程序執(zhí)行時(shí)間的因

2、素有哪些？A算法設(shè)計(jì)的策略問(wèn)題的規(guī)模C編譯程序產(chǎn)生的機(jī)器代碼質(zhì)量 D 計(jì)算機(jī)執(zhí)行指令的速度8、使用分治法求解不需要滿足的條件是 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)解0D、回溯11. 以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱為 D A、分支界限算法B、概率算法C、貪心算法算法12. 實(shí)現(xiàn)最長(zhǎng)公共子序

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

4、 A. 將問(wèn)題分解為多個(gè)子問(wèn)題來(lái)分別處理B. 選好最優(yōu)量度標(biāo)準(zhǔn)C .獲取各階段間的遞推關(guān)系式D.滿足最優(yōu)性原理18. 找最小生成樹(shù)的算法 Kruskal 的時(shí)間復(fù)雜度為 D 其中 n 為無(wú)向圖的結(jié) 點(diǎn)數(shù)，m為邊數(shù)2AOn2 B Omlogn C Onlog m D Omlogm19. 回溯法搜索狀態(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 ).(2 n)B. 0( 32n)C. 0( nlog n

5、 ) D. 0( 10nlogn)22. 二分搜索算法的時(shí)間復(fù)雜性為(C )。(n)(n)(|og n)d. 0(nlogn )23. 快速排序算法的時(shí)間復(fù)雜性為(D)0(n)(n)(log n)D. 0(nlogn )24. 算法是由假設(shè)干條指令組成的有窮序列，而且滿足以下性質(zhì)( D )A.輸入：有0個(gè)或多個(gè)輸入B.輸出：至少有一個(gè)輸出C.確定性：指令清晰，無(wú)歧義 D.有限性：指令執(zhí)行次數(shù)有限，而且執(zhí)行時(shí)間 有限A. (1) (2)(3) B. (1) (2) C. (1) (3)D.(1)25. 背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為( B )A. 0 (n2n)B. 0(nlogn)(2n)

6、(n)26. 以下算法中不能解決0/1背包問(wèn)題的是(A )A貪心法B動(dòng)態(tài)規(guī)劃C回溯法D分支限界法27. 在尋找n個(gè)元素中第k小元素問(wèn)題中，假設(shè)使用快速排序算法思想，運(yùn)用分治 算法對(duì)n個(gè)元素進(jìn)行劃分，應(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 oA.問(wèn)題規(guī)模相同，問(wèn)題性質(zhì)相同B

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

8、問(wèn)題，只使用約束條件進(jìn)行裁剪的是 N 皇后問(wèn)題 o3. 貪心算法根本要素有最優(yōu)度量標(biāo)準(zhǔn)和最優(yōu)子結(jié)構(gòu) 。4. 回溯法解旅行售貨員問(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ù)規(guī)模 有關(guān)。11. 任何可用計(jì)算機(jī)求解的問(wèn)題所需的時(shí)間都與其12. 快速排序算法的性能取決于 劃分的對(duì)稱性13. 背包問(wèn)題的

9、貪心算法void Knapsack(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;ic) break;xi=1;c - =if (i14下面算法的根本運(yùn)算是 _加法或：賦值_運(yùn)算，該算法中第4步執(zhí)行 了 2n-1 次。算法COUNT 輸入：正整數(shù)n (n=2k)輸出：count的值。1. cou nt=O2. while n=13. for j=1 to n4. count =co un t+15. end for6. n=n/27. end

10、 whileend COUNT15. 算法是由假設(shè)干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和 有限性四條性質(zhì)。16. 快速排序、插入排序和選擇排序算法中，快速排序算法是分治算法。17. 下面算法的根本語(yǔ)句是 S = S + i*j;,算法的時(shí)間復(fù)雜 度是2O(n )int fun (i nt n)int S = 0;for (i nt i=1; i =n; i+ )for(i nt j=1; j=1while (1)xk=xk+1if color(k) the nif (2) thenflag=true; output x1. nelsek= (4)end ifend ifend w

11、hile(5)end whileif not flag the n output“no soluti onend m-COLORINGk+1(1) xkm k=n xk=0(5) k=k-1 2 下面是求解矩陣鏈乘問(wèn)題的動(dòng)態(tài)規(guī)劃算法。矩陣鏈乘問(wèn)題：給出n個(gè)矩陣M, M2,M n , Mi為ri ri+1階矩陣，i=1,2,n，求計(jì)算MMM所需的最少數(shù)量乘法次數(shù)。記 Mi, j =MM+ M , i=j 。設(shè) Ci, j, 1=i=j=n,表示計(jì)算 Mj 的所需的最少數(shù)量乘法次數(shù)，那么.0,i jCi,jmin Ci,k-1 Ck, j rgji k j算法 MATCHAIN輸入：矩陣鏈長(zhǎng)度n,

12、 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 d=1 to n-1 for i=1 to n-dj= _J2)Ci, j=%for k=i+1 to jx= if xCi, j the n =xend ifend forend forend forreturn (5)end MATCHAIN(1) 0(2) i+d (3) Ci, k-1+Ck, j+ri*rk*rj+1 Ci, j (5) C1, n3.下面是用回溯法解n皇后問(wèn)題的算法(求出所有解)。n

13、皇后問(wèn)題：在n x n棋盤上放置n個(gè)皇后使得任何兩個(gè)皇后不能互相攻 擊。(如果兩個(gè)皇后處在同一行，或同一列，或同一斜線上，那么她們能互相攻 擊。)算法 NQUEENS輸入：正整數(shù)n。輸出：n皇后問(wèn)題的所有解x1.n, 假設(shè)無(wú)解，那么輸出Nosolutionflag=falsek=1 ; x1=0while while xk nxk=(2)if place(k) the nif k=n the nflag=true ； output x1. nelsek= (4)end ifend ifend while(5)end whileif not flag the n output“ No solut

14、i onend NQUEENS過(guò)程 place (k)遞歸的快速排序算法：template void QuickSort (Type a , i nt low, int high) if ()int i=Partition(a, low, high);Quicksort( a, low, i-1);(2；解：(1) low j, V(i, j) = V(i - 1, j)假設(shè) wi = j, V(i, j) = max V(i-1, j) , V(i-1, j - wi) + vij = 0j = 1j = 2j = 3j = 4j = 5j = 6i = 00000000i = 100025

15、252525i = 2002025254545i = 30152035404560i = 40152035405560i = 50152035405565V5,6即為問(wèn)題的最優(yōu)解，最大價(jià)值為 65。經(jīng)過(guò)回溯得到物品組合為第 3和 第5個(gè)物品裝入背包。4. 歸并排序算法對(duì)以下實(shí)例排序，寫出算法執(zhí)行過(guò)程。A=48,12,61,3,5,19,32,7解：拆分：48,12,61,35,19,32,748,1261,34812 615,1932,73519 32合并:12,483,613, 12,48, 613,5, 7,125,195, 7, 1919，32，48,617,32，325、簡(jiǎn)述分治法的根本思想。答：分治法的根本思想是將一個(gè)規(guī)模為 n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題, 這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同；對(duì)這 k個(gè)子問(wèn)題分別求解。如果子問(wèn) 題的規(guī)模仍然不夠小，那么再劃分為 k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到 問(wèn)題規(guī)模足夠小，很容易求出其解為止；將求出的小規(guī)模的問(wèn)題的解合并為 一個(gè)更