1、一。選擇題1、二分搜索算法是利用（   A      ）實現的算法。A、分治策略   B、動態規劃法   C、貪心法    D、回溯法2、下列不是動態規劃算法基本步驟的是（   A    ）。A、找出最優解的性質   B、構造最優解   C、算出最優解   D、定義最優解3、最大效益優先是（  A 

2、        ）的一搜索方式。A、分支界限法      B、動態規劃法    C、貪心法    D、回溯法4、在下列算法中有時找不到問題解的是（ B       ）。A、蒙特卡羅算法    B、拉斯維加斯算法   C、舍伍德算法   D、數值概率算法5. 回溯法解旅行售貨員問題

3、時的解空間樹是（ A      ）。A、子集樹B、排列樹C、深度優先生成樹D、廣度優先生成樹6下列算法中通常以自底向上的方式求解最優解的是（   B      ）。A、備忘錄法B、動態規劃法C、貪心法D、回溯法7、衡量一個算法好壞的標準是（C ）。A 運行速度快 B 占用空間少 C 時間復雜度低 D 代碼短8、以下不可以使用分治法求解的是（D ）。A 棋盤覆蓋問題 B 選擇問題 C 歸并排序 D 0/1背包問題9. 實現循環賽日程表利用的算法是（ 

4、;   A      ）。A、分治策略B、動態規劃法C、貪心法D、回溯法10、下列隨機算法中運行時有時候成功有時候失敗的是（C ）A 數值概率算法 B 舍伍德算法 C 拉斯維加斯算法 D 蒙特卡羅算法11下面不是分支界限法搜索方式的是（     D     ）。A、廣度優先B、最小耗費優先C、最大效益優先D、深度優先12下列算法中通常以深度優先方式系統搜索問題解的是（     

5、 D   ）。A、備忘錄法B、動態規劃法C、貪心法D、回溯法13.備忘錄方法是那種算法的變形。（ B ）A、分治法B、動態規劃法C、貪心法D、回溯法14哈弗曼編碼的貪心算法所需的計算時間為（   B     ）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）15分支限界法解最大團問題時，活結點表的組織形式是（    B    ）。A、最小堆B、最大堆 C、棧D、數組16最長公共子序列算法利用的算法是（ 

6、;   B       ）。A、分支界限法B、動態規劃法C、貪心法D、回溯法17實現棋盤覆蓋算法利用的算法是（     A      ）。A、分治法B、動態規劃法C、貪心法D、回溯法18.下面是貪心算法的基本要素的是（      C     ）。A、重疊子問題B、構造最優解C、貪心選擇性質D、定義最優解19.

7、回溯法的效率不依賴于下列哪些因素（ D ）A.滿足顯約束的值的個數 B. 計算約束函數的時間 C. 計算限界函數的時間 D. 確定解空間的時間20.下面哪種函數是回溯法中為避免無效搜索采取的策略（    B    ）A遞歸函數B.剪枝函數 C。隨機數函數D.搜索函數21、下面關于NP問題說法正確的是（B ）A NP問題都是不可能解決的問題B P類問題包含在NP類問題中C NP完全問題是P類問題的子集D NP類問題包含在P類問題中22、蒙特卡羅算法是（   B   &

8、#160;  ）的一種。A、分支界限算法      B、概率算法    C、貪心算法    D、回溯算法23.下列哪一種算法不是隨機化算法（    C     ）A. 蒙特卡羅算法B. 拉斯維加斯算法C.動態規劃算法D.舍伍德算法24. （   D         ）是貪心算法與動態規劃算

9、法的共同點。A、重疊子問題B、構造最優解C、貪心選擇性質D、最優子結構性質25. 矩陣連乘問題的算法可由（          B）設計實現。A、分支界限算法      B、動態規劃算法    C、貪心算法    D、回溯算法26. 分支限界法解旅行售貨員問題時，活結點表的組織形式是（   A    ）。A、最小堆B、最大堆 C、

10、棧D、數組27、Strassen矩陣乘法是利用（    A     ）實現的算法。A、分治策略   B、動態規劃法   C、貪心法    D、回溯法29、使用分治法求解不需要滿足的條件是（A ）。A 子問題必須是一樣的B 子問題不能夠重復C 子問題的解可以合并D 原問題和子問題使用相同的方法解30、下面問題（B ）不能使用貪心法解決。A 單源最短路徑問題 B N皇后問題 C 最小花費生成樹問題 D 背包問題31、下列算法中不能解決0/1背包問題的

11、是（A ）A 貪心法 B 動態規劃 C 回溯法 D 分支限界法32、回溯法搜索狀態空間樹是按照（C ）的順序。A 中序遍歷 B 廣度優先遍歷 C 深度優先遍歷 D 層次優先遍歷33、下列隨機算法中運行時有時候成功有時候失敗的是（C ）A 數值概率算法 B 舍伍德算法 C 拉斯維加斯算法 D 蒙特卡羅算法34實現合并排序利用的算法是（     A    ）。A、分治策略B、動態規劃法C、貪心法D、回溯法35下列是動態規劃算法基本要素的是（  D     ）。

12、A、定義最優解B、構造最優解C、算出最優解D、子問題重疊性質36下列算法中通常以自底向下的方式求解最優解的是（    B     ）。A、分治法B、動態規劃法C、貪心法D、回溯法37采用廣度優先策略搜索的算法是（     A      ）。A、分支界限法B、動態規劃法C、貪心法D、回溯法38、合并排序算法是利用（   A      ）實現

13、的算法。A、分治策略   B、動態規劃法   C、貪心法    D、回溯法39、在下列算法中得到的解未必正確的是（  B      ）。A、蒙特卡羅算法    B、拉斯維加斯算法   C、舍伍德算法   D、數值概率算法40、背包問題的貪心算法所需的計算時間為（  B      ）A、O（n2n）  

14、;   B、O（nlogn）    C、O（2n）      D、O（n）41實現大整數的乘法是利用的算法（      C   ）。A、貪心法B、動態規劃法C、分治策略D、回溯法420-1背包問題的回溯算法所需的計算時間為（  A      ）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）43采用最大效益優先搜索方式的算法是（

15、60;  A        ）。A、分支界限法B、動態規劃法C、貪心法D、回溯法44貪心算法與動態規劃算法的主要區別是（  B         ）。A、最優子結構B、貪心選擇性質C、構造最優解D、定義最優解45. 實現最大子段和利用的算法是（     B      ）。A、分治策略B、動態規劃法C、貪心法D、

16、回溯法46.優先隊列式分支限界法選取擴展結點的原則是（     C      ）。A、先進先出B、后進先出C、結點的優先級D、隨機47.背包問題的貪心算法所需的計算時間為（   B     ）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）48、廣度優先是（    A       ）的一搜索方式。A、分支界限法&

17、#160;     B、動態規劃法    C、貪心法    D、回溯法49、舍伍德算法是（    B     ）的一種。A、分支界限算法      B、概率算法    C、貪心算法    D、回溯算法50、在下列算法中有時找不到問題解的是（  B   

18、0;  ）。A、蒙特卡羅算法    B、拉斯維加斯算法   C、舍伍德算法   D、數值概率算法51下列哪一種算法是隨機化算法（    D     ）A. 貪心算法B. 回溯法C.動態規劃算法D.舍伍德算法52. 一個問題可用動態規劃算法或貪心算法求解的關鍵特征是問題的（   B          ）。A、重疊子問題B

19、、最優子結構性質C、貪心選擇性質D、定義最優解53采用貪心算法的最優裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法的時間復雜度為 ( B ) 。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）54. 以深度優先方式系統搜索問題解的算法稱為 ( D ) 。A、分支界限算法      B、概率算法    C、貪心算法    D、回溯算法55. 實現最長公共子序列利用的算法是（     B  &

20、#160;   ）。A、分治策略B、動態規劃法C、貪心法D、回溯法二、 填空題 1.算法的復雜性有 時間 復雜性和 空間 復雜性之分。2、程序是 算法     用某種程序設計語言的具體實現。3、算法的“確定性”指的是組成算法的每條 指令 是清晰的，無歧義的。4.矩陣連乘問題的算法可由 動態規劃 設計實現。5、拉斯維加斯算法找到的解一定是 正確解。6、算法是指解決問題的 一種方法 或 一個過程 。7、從分治法的一般設計模式可以看出，用它設計出的程序一般是 遞歸算法 。8、問題的 最優子結構性質 是該問題可用動態規劃算法或貪心算

21、法求解的關鍵特征。9、以深度優先方式系統搜索問題解的算法稱為 回溯法 。10、數值概率算法常用于 數值問題 的求解。11、計算一個算法時間復雜度通常可以計算 循環次數 、 基本操作的頻率 或計算步。12、利用概率的性質計算近似值的隨機算法是_數值概率算法，運行時以一定的概率得到正確解的隨機算法是_蒙特卡羅算法_。14、解決0/1背包問題可以使用動態規劃、回溯法和分支限界法，其中不需要排序的是 動態規劃 ，需要排序的是 回溯法 ，分支限界法 。15、使用回溯法進行狀態空間樹裁剪分支時一般有兩個標準：約束條件和目標函數的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時使用約束條件和目標

22、函數的界進行裁剪的是 0/1背包問題 ，只使用約束條件進行裁剪的是 N皇后問題 。16、 貪心選擇性質 是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。17、矩陣連乘問題的算法可由 動態規劃 設計實現。18、拉斯維加斯算法找到的解一定是 正確解。19.貪心算法的基本要素是 貪心選擇 質和 最優子結構 性質 。21. 動態規劃算法的基本思想是將待求解問題分解成若干 子問題 ，先求解 子問題 ，然后從這些 子問題 的解得到原問題的解。22.算法是由若干條指令組成的有窮序列，且要滿足輸入、 輸出 、確定性和 有限性 四條性質。23、大整數乘積算法是用 分治法 來設計的。24、以

23、廣度優先或以最小耗費方式搜索問題解的算法稱為 分支限界法 。25、舍伍德算法總能求得問題的 一個解 。26、 貪心選擇性質 是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。27.快速排序算法是基于 分治策略 的一種排序算法。28.動態規劃算法的兩個基本要素是. 最優子結構 性質和 重疊子問題 性質 。 30.回溯法是一種既帶有 系統性 又帶有 跳躍性 的搜索算法。 31.分支限界法主要有 隊列式（FIFO） 分支限界法和 優先隊列式 分支限界法。32分支限界法是一種既帶有 系統性 又帶有 跳躍性 的搜索算法。33回溯法搜索解空間樹時，常用的兩種剪枝函數為 約束函數 和 限

24、界函數 。34.任何可用計算機求解的問題所需的時間都與其 規模 有關。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;i<=n;i+) if (wi>c) break; xi=1; c - =wi; if (i<=n) xi=c/wi;2.最大子段和: 動態規劃算法int MaxSum(int n, int

25、 a) int sum=0, b=0； /sum存儲當前最大的bj, b存儲bj for(int j=1； j<=n； j+) if (b>0) b+= aj ； else b=ai; ； /一旦某個區段和為負，則從下一個位置累和 if(b>sum) sum=b; return sum； 3.貪心算法求裝載問題template<class Type>void Loading(int x, Type w, Type c, int n) int *t = new int n+1; ; for (int i = 1; i <= n; i+) xi = 0; for

26、 (int i = 1; i <= n && wti <= c; i+) xti = 1; ;4.貪心算法求活動安排問題template<class Type>void GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i<=n;i+) if (si>=fj) Ai=true; j=i; else Ai=false; 5.快速排序template<class Type>void QuickSort (Type a, int p,

27、 int r) if (p<r) int q=Partition(a,p,r); QuickSort (a,p,q-1); /對左半段排序 QuickSort (a,q+1,r); /對右半段排序 6.排列問題Template <class Type>void perm(Type list, int k, int m ) /產生listk:m的所有排列 if(k=m) /只剩下一個元素 for (int i=0;i<=m;i+) cout<<listi; cout<<endl; else /還有多個元素待排列，遞歸產生排列 for (int i=

28、k; i<=m; i+) swap(listk，listi); perm(list,k+1;m); swap(listk,listi); 四、問答題1.分治法的基本思想時將一個規模為n的問題分解為k個規模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。2設計動態規劃算法的主要步驟為：（1）找出最優解的性質，并刻劃其結構特征。（2）遞歸地定義最優值。（3）以自底向上的方式計算出最優值。（4）根據計算最優值時得到的信息，構造最優解。3. 分治法與動態規劃法的相同點是：將待求解的問題分解成若干個子問題，先求解子問題，然后從這些子問題的

29、解得到原問題的解。兩者的不同點是：適合于用動態規劃法求解的問題，經分解得到的子問題往往不是互相獨立的。而用分治法求解的問題，經分解得到的子問題往往是互相獨立的。4. 分支限界法與回溯法的相同點是：都是一種在問題的解空間樹T中搜索問題解的算法。不同點：（1）求解目標不同； （2）搜索方式不同； （3）對擴展結點的擴展方式不同； （4）存儲空間的要求不同。5用回溯法搜索子集樹的算法為：void backtrack (int t) if (t>n) output(x); else for (int i=0;i<=1;i+) xt=i; if (constraint(t)&&

30、;bound(t) backtrack(t+1); 6. 分治法所能解決的問題一般具有的幾個特征是：（1）該問題的規模縮小到一定的程度就可以容易地解決； （2）該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質; （3）利用該問題分解出的子問題的解可以合并為該問題的解； （4）原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。7. 用分支限界法設計算法的步驟是：(1)針對所給問題，定義問題的解空間（對解進行編碼）；分(2)確定易于搜索的解空間結構（按樹或圖組織解） ； (3)以廣度優先或以最小耗費（最大收益）優先的方式搜索解空間，并在搜索過程中用剪枝函數

31、避免無效搜索。8. 常見的兩種分支限界法的算法框架（1）隊列式(FIFO)分支限界法：按照隊列先進先出（FIFO）原則選取下一個節點為擴展節點。 （2）優先隊列式分支限界法：按照優先隊列中規定的優先級選取優先級最高的節點成為當前擴展節點。9. 回溯法中常見的兩類典型的解空間樹是子集樹和排列樹。當所給的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹稱為子集樹。這類子集樹通常有2n個葉結點，遍歷子集樹需O(2n)計算時間 。當所給的問題是確定n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。這類排列樹通常有n!個葉結點。遍歷排列樹需要O(n!)計算時間。10. 分支限界法

32、的搜索策略是： 在擴展結點處，先生成其所有的兒子結點（分支），然后再從當前的活結點表中選擇下一個擴展結點。為了有效地選擇下一擴展結點，加速搜索的進程，在每一個活結點處，計算一個函數值（限界），并根據函數值，從當前活結點表中選擇一個最有利的結點作為擴展結點，使搜索朝著解空間上有最優解的分支推進，以便盡快地找出一個最優解。五、算法題1. 給定已按升序排好序的n個元素a0:n-1，現要在這n個元素中找出一特定元素x，返回其在數組中的位置，如果未找到返回-1。寫出二分搜索的算法，并分析其時間復雜度。1. template<class Type> int BinarySearch(Type a, const Type& x, int n)/在a0:n中搜索x，找到x時返回其在數組中的位置，否則返回-1 I