算法分析復(fù)習(xí)題目及答案(4)

1、.一。選擇題1、二分搜索算法是利用（a）實現(xiàn)的算法。a、分治策略b 、動態(tài)規(guī)劃法c、貪心法d 、回溯法2、下列不是動態(tài)規(guī)劃算法基本步驟的是（a）。a、找出最優(yōu)解的性質(zhì)b 、構(gòu)造最優(yōu)解c 、算出最優(yōu)解d、定義最優(yōu)解3、最大效益優(yōu)先是（a）的一搜索方式。a、分支界限法b 、動態(tài)規(guī)劃法c、貪心法d、回溯法4、在下列算法中有時找不到問題解的是（b）。a、蒙特卡羅算法b 、拉斯維加斯算法c、舍伍德算法d 、數(shù)值概率算法5. 回溯法解旅行售貨員問題時的解空間樹是（b）。a、子集樹b、排列樹c、深度優(yōu)先生成樹d、廣度優(yōu)先生成樹6下列算法中通常以自底向上的方式求解最優(yōu)解的是（b）。a、備忘錄法b、動態(tài)規(guī)劃法c

2、、貪心法d、回溯法7、衡量一個算法好壞的標準是（c ）。a 運行速度快 b 占用空間少 c 時間復(fù)雜度低 d 代碼短8、以下不可以使用分治法求解的是（d ）。a 棋盤覆蓋問題 b 選擇問題 c 歸并排序 d 0/1背包問題9.實現(xiàn)循環(huán)賽日程表利用的算法是（a）。a、分治策略b、動態(tài)規(guī)劃法c、貪心法d、回溯法10、下列隨機算法中運行時有時候成功有時候失敗的是（c ）a 數(shù)值概率算法 b 舍伍德算法 c 拉斯維加斯算法d 蒙特卡羅算法11下面不是分支界限法搜索方式的是（d）。a、廣度優(yōu)先b、最小耗費優(yōu)先c、最大效益優(yōu)先d、深度優(yōu)先12 下 列 算 法 中 通 常 以 深 度 優(yōu) 先 方 式 系 統(tǒng)

3、 搜 索 問 題 解 的 是（d）。a、備忘錄法b、動態(tài)規(guī)劃法c、貪心法d、回溯法13. 備忘錄方法是那種算法的變形。 （b）.a、分治法b、動態(tài)規(guī)劃法c、貪心法d、回溯法14哈弗曼編碼的貪心算法所需的計算時間為（b）。a、o（n2n）b、 o（ nlogn ）c、o（2n）d、o（n）15分支限界法解最大團問題時， 活結(jié)點表的組織形式是 （b）。a、最小堆b、最大堆c、棧d、數(shù)組16最長公共子序列算法利用的算法是（b）。a、分支界限法b、動態(tài)規(guī)劃法c、貪心法d、回溯法17實現(xiàn)棋盤覆蓋算法利用的算法是（a）。a、分治法b、動態(tài)規(guī)劃法c、貪心法d、回溯法18. 下面是貪心算法的基本要素的是（c）

4、。a、重疊子問題b、構(gòu)造最優(yōu)解c、貪心選擇性質(zhì)d、定義最優(yōu)解19. 回溯法的效率不依賴于下列哪些因素（d）a. 滿足顯約束的值的個數(shù)b.計算約束函數(shù)的時間c. 計算限界函數(shù)的時間d.確定解空間的時間20. 下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（b）a遞歸函數(shù)b. 剪枝函數(shù)c。隨機數(shù)函數(shù)d.搜索函數(shù)21、下面關(guān)于 np問題說法正確的是（ b ）a np問題都是不可能解決的問題b p 類問題包含在 np類問題中c np完全問題是 p 類問題的子集d np類問題包含在 p 類問題中22、蒙特卡羅算法是（b）的一種。a、分支界限算法b 、概率算法c、貪心算法d 、回溯算法23. 下列哪一種算

5、法不是隨機化算法（c）a. 蒙特卡羅算法 b. 拉斯維加斯算法 c.動態(tài)規(guī)劃算法 d. 舍伍德算法24.（d ）是貪心算法與動態(tài)規(guī)劃算法的共同點。a、重疊子問題 b 、構(gòu)造最優(yōu)解 c、貪心選擇性質(zhì)d、最優(yōu)子結(jié)構(gòu)性質(zhì)25.矩陣連乘問題的算法可由（b）設(shè)計實現(xiàn)。.a、分支界限算法b 、動態(tài)規(guī)劃算法c 、貪心算法d、回溯算法26. 分 支 限 界 法 解 旅 行 售 貨 員 問 題 時 ， 活 結(jié) 點 表 的 組 織 形 式 是（a）。a、最小堆b、最大堆c、棧d、數(shù)組27、strassen 矩陣乘法是利用（a）實現(xiàn)的算法。a、分治策略b 、動態(tài)規(guī)劃法c、貪心法d 、回溯法29、使用分治法求解不需要

6、滿足的條件是（a ）。a 子問題必須是一樣的b 子問題不能夠重復(fù)c 子問題的解可以合并d 原問題和子問題使用相同的方法解30、下面問題（ b ）不能使用貪心法解決。a 單源最短路徑問題b n 皇后問題c 最小花費生成樹問題d 背包問題31、下列算法中不能解決0/1 背包問題的是（ a ）a 貪心法 b 動態(tài)規(guī)劃 c 回溯法 d 分支限界法33、下列隨機算法中運行時有時候成功有時候失敗的是（c ）a 數(shù)值概率算法 b 舍伍德算法 c 拉斯維加斯算法d 蒙特卡羅算法34實現(xiàn)合并排序利用的算法是（a）。a、分治策略b、動態(tài)規(guī)劃法c、貪心法d、回溯法35下列是動態(tài)規(guī)劃算法基本要素的是（d）。a、定義最

7、優(yōu)解b、構(gòu)造最優(yōu)解c、算出最優(yōu)解d、子問題重疊性質(zhì)37采用廣度優(yōu)先策略搜索的算法是（a）。a、分支界限法b、動態(tài)規(guī)劃法c、貪心法d、回溯法38、合并排序算法是利用（a）實現(xiàn)的算法。a、分治策略b 、動態(tài)規(guī)劃法c、貪心法d 、回溯法.39、在下列算法中得到的解未必正確的是（b）。a、蒙特卡羅算法b 、拉斯維加斯算法c、舍伍德算法d 、數(shù)值概率算法40、背包問題的貪心算法所需的計算時間為（b）a、o（n2n）b 、o（nlogn ）c、o（2n）d、 o（ n）41實現(xiàn)大整數(shù)的乘法是利用的算法（c）。a、貪心法b、動態(tài)規(guī)劃法c、分治策略d、回溯法420-1 背包問題的回溯算法所需的計算時間為（a）

8、a、o（n2n）b、o（nlogn ）c、o（ 2n）d、o（n）43采用最大效益優(yōu)先搜索方式的算法是（a）。a、分支界限法b、動態(tài)規(guī)劃法c、貪心法d、回溯法44貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是（b）。a、最優(yōu)子結(jié)構(gòu)b、貪心選擇性質(zhì)c、構(gòu)造最優(yōu)解d、定義最優(yōu)解45. 實現(xiàn)最大子段和利用的算法是（b）。a、分治策略b、動態(tài)規(guī)劃法c、貪心法d、回溯法46. 優(yōu)先隊列式分支限界法選取擴展結(jié)點的原則是（c）。a、先進先出b、后進先出c、結(jié)點的優(yōu)先級d、隨機47. 背包問題的貪心算法所需的計算時間為（b）。a、o（n2n）b、o（nlogn ）c、o（2n）d、o（n）48、廣度優(yōu)先是（a）的一搜索方

9、式。a、分支界限法b 、動態(tài)規(guī)劃法c、貪心法d、回溯法49、舍伍德算法是（b）的一種。a、分支界限算法b 、概率算法c、貪心算法d 、回溯算法50、在下列算法中有時找不到問題解的是（b）。a、蒙特卡羅算法b 、拉斯維加斯算法c、舍伍德算法d 、數(shù)值概率算法51 下列哪一種算法是隨機化算法（d）.a. 貪心算法 b. 回溯法 c.動態(tài)規(guī)劃算法 d.舍伍德算法52. 一 個問 題可 用動 態(tài)規(guī) 劃算 法或 貪心 算 法求 解的關(guān)鍵 特征 是問 題的（b）。a、重疊子問題b、最優(yōu)子結(jié)構(gòu)性質(zhì)c、貪心選擇性質(zhì)d、定義最優(yōu)解53采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法

10、的時間復(fù)雜度為( b)。a、o（n2n）b、o（nlogn ）c、o（2n）d、o（n）54. 以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為( d )。a、分支界限算法b 、概率算法c、貪心算法d 、回溯算法55. 實現(xiàn)最長公共子序列利用的算法是（b）。a、分治策略b、動態(tài)規(guī)劃法c、貪心法d、回溯法二、 填空題1. 算法的復(fù)雜性有時間復(fù)雜性和空間復(fù)雜性之分。2、程序是算法用某種程序設(shè)計語言的具體實現(xiàn)。3、算法的“確定性”指的是組成算法的每條指令是清晰的，無歧義的。4. 矩陣連乘問題的算法可由動態(tài)規(guī)劃設(shè)計實現(xiàn)。5、拉斯維加斯算法找到的解一定是正確解。6、算法是指解決問題的一種方法或 一個過程。7、從分

11、治法的一般設(shè)計模式可以看出， 用它設(shè)計出的程序一般是遞歸算法 。8、問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。9、以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯法。10、數(shù)值概率算法常用于數(shù)值問題的求解。11、計算一個算法時間復(fù)雜度通?？梢杂嬎阊h(huán)次數(shù)、 基本操作的頻率或計算步。12、利用概率的性質(zhì)計算近似值的隨機算法是_數(shù)值概率算法，運行時以一定的.概率得到正確解的隨機算法是_蒙特卡羅算法 _。14、解決 0/1 背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法， 其中不需要排序的是動態(tài)規(guī)劃，需要排序的是回溯法，分支限界法。15、使用回溯法進行狀態(tài)空間樹裁剪分支時一般有兩

12、個標準：約束條件和目標函數(shù)的界， n 皇后問題和 0/1 背包問題正好是兩種不同的類型，其中同時使用約束條件和目標函數(shù)的界進行裁剪的是0/1背包問題，只使用約束條件進行裁剪的是 n 皇后問題。16、 貪心選擇性質(zhì)是貪心算法可行的第一個基本要素， 也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。17、矩陣連乘問題的算法可由動態(tài)規(guī)劃設(shè)計實現(xiàn)。18、拉斯維加斯算法找到的解一定是正確解。19. 貪心 算法 的 基 本要 素 是貪心 選 擇質(zhì) 和最 優(yōu)子 結(jié) 構(gòu)性質(zhì) 。21. 動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干子問題，先求解 子問題，然后從這些子問題的解得到原問題的解。22. 算法是由若干條指令組成的

13、有窮序列，且要滿足輸入、輸出、確定性和有限性四條性質(zhì)。23、大整數(shù)乘積算法是用分治法來設(shè)計的。24、以廣度優(yōu)先或以最小耗費方式搜索問題解的算法稱為分支限界法。25、舍伍德算法總能求得問題的一個解。26、貪心選擇性質(zhì)是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。27. 快速排序算法是基于分治策略的一種排序算法。28. 動態(tài)規(guī)劃算法的兩個基本要素是.最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題性質(zhì) 。30. 回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。31. 分支限界法主要有隊列式（ fifo）分支限界法和.優(yōu)先隊列式分支限界法。32分支限界法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。3

14、3回溯法搜索解空間樹時， 常用的兩種剪枝函數(shù)為約束函數(shù)和限界函數(shù)。34. 任何可用計算機求解的問題所需的時間都與其規(guī)模有關(guān)。35. 快速排序算法的性能取決于劃分的對稱性。三、算法填空1. 背包問題的貪心算法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 - =wi;if (i=n) xi=c/wi;2. 最大子段和 : 動態(tài)規(guī)劃算法int maxsum(int n, int a)int s

15、um=0, b=0；/sum存儲當前最大的bj, b存儲 bjfor(int j=1； j0) b+= aj；else b=ai;；/一旦某個區(qū)段和為負， 則從下一個位置累.和if(bsum) sum=b;return sum；3. 貪心算法求裝載問題templatevoidloading (int x, type w, type c, int n)int *t = new int n+1;for (int i = 1; i = n; i+) xi = 0;for (int i = 1; i = n & wti = c; i+)xti = 1;4. 貪心算法求活動安排問題templatevoi

16、dgreedyselector (int n, type s, type f, bool a)a1=true;int j=1;for (int i=2;i=fj) ai=true; j=i;.else ai=false;5. 快速排序templatevoidquicksort (type a, int p, int r)if (pr) int q=partition(a,p,r);quicksort (a,p,q-1); /對左半段排序quicksort (a,q+1,r); /對右半段排序6. 排列問題template void perm(type list, int k, int m )

17、/產(chǎn)生 listk:m的所有排列if(k=m) /只剩下一個元素for (int i=0;i=m;i+) coutlisti;coutendl;else /還有多個元素待排列，遞歸產(chǎn)生排列for (int i=k; in) output(x);elsefor (int i=0;i=1;i+) xt=i;if (constraint(t)&bound(t) backtrack(t+1);6. 分治法所能解決的問題一般具有的幾個特征是：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì) ;（3）利用該問題分解出的子問題的解

18、可以合并為該問題的解；（ 4）原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。.7. 用分支限界法設(shè)計算法的步驟是：(1)針對所給問題，定義問題的解空間（對解進行編碼）；分(2)確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）；(3)以廣度優(yōu)先或以最小耗費（最大收益）優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。8. 常見的兩種分支限界法的算法框架（ 1）隊列式 (fifo) 分支限界法：按照隊列先進先出（ fifo）原則選取下一個節(jié)點為擴展節(jié)點。 （2）優(yōu)先隊列式分支限界法：按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當前擴展節(jié)點。9. 回溯法中常見的兩

19、類典型的解空間樹是子集樹和排列樹。當所給的問題是從 n 個元素的集合 s 中找出滿足某種性質(zhì)的子集時， 相應(yīng)的解空間樹稱為子集樹。這類子集樹通常有 2n 個葉結(jié)點，遍歷子集樹需 o(2n) 計算時間 。當所給的問題是確定 n 個元素滿足某種性質(zhì)的排列時， 相應(yīng)的解空間樹稱為排列樹。這類排列樹通常有 n!個葉結(jié)點。遍歷排列樹需要 o(n!)計算時間。10. 分支限界法的搜索策略是：在擴展結(jié)點處，先生成其所有的兒子結(jié)點（分支） ，然后再從當前的活結(jié)點表中選擇下一個擴展結(jié)點。 為了有效地選擇下一擴展結(jié)點，加速搜索的進程， 在每一個活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)函數(shù)值，從當前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點，使搜索朝著解空間上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。五、算法題1. 給定已按升序排好序的 n個元素 a0:n-1 ，現(xiàn)要在這 n個元素中找出一特定元素 x，返回其在數(shù)組中的位置，如果未找到返回-1 。寫出二分搜索的算法，并分析其時間復(fù)雜度。1.templateint binarysearch(type a, const type& x, int n)/ 在 a0:n