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

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

2、于影響程序執(zhí)行時間的因素有哪些（C ）A. 算法設(shè)計的策略B問題的規(guī)模C.編譯程序產(chǎn)生的機(jī)器代碼質(zhì)量D.計算機(jī)執(zhí)行指令的速度8、使用分治法求解不需要滿足的條件是（A ）。A子問題必須是一樣的B子問題不能夠重復(fù)C子問題的解可以合并D原問題和子問題使用相同的方法解9、下面問題（B ）不能使用貪心法解決。A單源最短路徑問題B N皇后問題C最小花費(fèi)生成樹問題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、分支界限算法B、概率算法C、貪心算法D、回溯算

3、法12.實(shí)現(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. 對算法需要多少計算時間和存儲空間作定量分析D. 證明算法對所有可能的合法輸入都能算出正確的答案15衡量一個算法好壞的標(biāo)準(zhǔn)是（C ）16 A.運(yùn)行速度快B.占用空間少C.時間復(fù)雜度低D.代碼短16. 二分搜索算法是利用（A）實(shí)現(xiàn)的算法。A.分治法B.動態(tài)規(guī)劃法C.貪心法D.回溯法1

4、7. 用貪心法設(shè)計算法的關(guān)鍵是（B ）。A. 將問題分解為多個子問題來分別處理B. 選好最優(yōu)量度標(biāo)準(zhǔn)C. 獲取各階段間的遞推關(guān)系式D. 滿足最優(yōu)性原理1&找最小生成樹的算法Kruskal的時間復(fù)雜度為（D ）（其中n為無向圖 的結(jié)點(diǎn)數(shù)，m為邊數(shù)）A. 0（n2） B. 0 （mlogn） C. 0 （nlogm） D. 0（mlogm）19.回溯法搜索狀態(tài)空間樹是按照（C ）的順序。A中序遍歷B.廣度優(yōu)先遍歷C.深度優(yōu)先遍歷D.層次優(yōu)先遍歷20采用廣度優(yōu)先策略搜索的算法是（A ）oA.分支界限法B.動態(tài)規(guī)劃法C.貪心法D.回溯法21.函數(shù)32n+10nlogn的漸進(jìn)表達(dá)式是（B ） (2n)

5、B. 0( 32)C. 0( nlogn )D. 0( 10nlogD)Oglog)22二分搜索算法的時間復(fù)雜性為（C ）o （心（“）（lg） D.23. 快速排序算法的時間復(fù)雜性為（D ）（心 （“）（10g,?） I24. 算法是由若干條指令組成的有窮序列，而且滿足以下性質(zhì)（D ） A.輸入：有0個或多個輸入 B.輸出：至少有一個輸出C.確定性：指令清晰，無歧義D.有限性：指令執(zhí)行次數(shù)有限，而且執(zhí)行 時間有限A.（3） B.（4） C.（4） D.25. 背包問題的貪心算法所需的計算時間為（B ） A. 0 （n2n）B. 0 （nlogn） （2n）（n）26下列算法中不能解決0/1背

6、包問題的是（A ）A貪心法B動態(tài)規(guī)劃C回溯法D分支限界法27. 在尋找n個元素中第k小元素問題中，若使用快速排序算法思想，運(yùn) 用分治算法對n個元素進(jìn)行劃分，應(yīng)如何選擇劃分基準(zhǔn)下面（D）答案解釋最 合理。A. 隨機(jī)選擇一個元素作為劃分基準(zhǔn)B. 取子序列的第一個元素作為劃分基準(zhǔn)C. 用中位數(shù)的中位數(shù)方法尋找劃分基準(zhǔn)D.以上皆可行。但不同方法，算法復(fù)雜度上界可能不同28. 分治法的設(shè)計思想是將一個難以直接解決的大問題分割成規(guī)模較小的 子問題，分別解決子問題，最后將子問題的解組合起來形成原問題的解。這要 求原問題和子問題（C ）。A.問題規(guī)模相同，問題性質(zhì)相同B.問題規(guī)模相同，問題性質(zhì)不同C.問題規(guī)模

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

8、 N皇后問題 。3. 貪心算法基本要素有最優(yōu)度量標(biāo)準(zhǔn)和最優(yōu)子結(jié)構(gòu)。輸出：count的值。1. count=02. wh訂e n=l3. for j=lto n4. count =count+15. end for6. n=n/27. end whileend COUNT15算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、確定性 和有限性四條性質(zhì)。16快速排序.插入排序和選擇排序算法中，快速排序算法是分治 算法。17.下面算法的基本語句是_ S二S + i*j：_,算法的時間復(fù)雜度是0(心int fun(int n)int S = 0;for (int i=l; i =n; i卄)for(

9、int j=l; j=lwhile (1)xk=xk+lif color (k) thenif thenflag=true; output xl. nelsek=(3)end ifend ifend whileend whileif not flag then output no solutionend m-COLORING(1) x k m(4) xk=0(3) k+1k=n(5) k=k-l2. 下面是求解矩陣鏈乘問題的動態(tài)規(guī)劃算法。矩陣鏈乘問題：給出n個矩陣Mx, M2,此，肚為階矩陣，i=l,2, n,求計算所需的最少數(shù)量乘法次數(shù)。記 Mi.產(chǎn)MiMi+嚴(yán)虬，i=jo 設(shè) Ci, j,

10、 l=i=j=n,表示計算的所需的最少數(shù)量乘法次數(shù)，則JO,i = jCH，jminCi,k-l+Ck ” + 叭如 ,i jI igj算法 MATCHAIN輸入：矩陣鏈長度n, n個矩陣的階rl.n+l,其中rl.n為n個矩 陣的行數(shù)，rn+l為第n個矩陣的列數(shù)。輸出：n個矩陣鏈乘所需的數(shù)量乘法的最少次數(shù)。for i=l to n Ci, i=Q)for d=l to nTfor i=l to ndj= (2)Ci, j= 8for k=i+l to jx=if xCi, j then =xend辻end forend forend forreturn(5)end MATCHAIN(1) 0

11、(2) i+d(3) Ci, k-l+Ck,刃 +ri*rk*rj+l Ci, j (5) Cl, n3. 下面是用回溯法解n皇后問題的算法(求出所有解)。n皇后問題：在nxn棋盤上放置n個皇后使得任何兩個皇后不能互相攻 擊。(如果兩個皇后處在同一行，或同一列，或同一斜線上，則她們能互相攻 擊。)算法 NQUEENS輸入：正整數(shù)n。輸出：n皇后問題的所有解xl. .n,若無解，則輸出No solution。flag=falsek=l ;xl=0while (1)while xknx k二(2)if place(k) thenif k=n thenflag=true； output xl. ne

12、lsek= (3)(41end ifend辻end whileend whileif not flag then output No solution” end NQUEENS過程 place (k)遞歸的快速排序算法：template void Quicksort (Type a , int low, int high) if (1)int i=Partition(a, low, high); Quicksort (a, low, i-1);(2);解：(1) low j, v(i, j)二 V(i - 1, j)若 Wt = j, V(i, j) = max V(i-1, j) , V(i

13、-1, j-wi) + vi)j = 0j = 1J = 2j = 3J = 4j = 5j = 6i=00000000i=100025252525i=2002025254545i=30152035404560i=40152035405560i=50152035405565V(5, 6)即為問題的最優(yōu)解，最大價值為65。經(jīng)過回溯得到物品組合為第3和第5個物品裝入背包。4. 歸并排序算法對下列實(shí)例排序，寫出算法執(zhí)行過程。A=(48, 12,61,3, 5, 19, 32, 7)解：拆分:48, 12, 61, 34& 1261, 348126135, 19, 32, 75,1932, 7519327合并：12, 483, 613, 12,4& 613, 5, 7,12,5,197, 325, 7, 19, 3219, 32, 4&615、簡述分治法的基本思想。答分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的 子問題，這些子問題互相獨(dú)立且與原問題相同；對這k個子問題分別求解。 如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下 去，直到問題規(guī)模足夠小，很容易求出其解為止；將求出的小規(guī)模的問題的 解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。6、由于貪心算法