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

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

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

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

7、解19.回溯法的效率不依賴于下列哪些因素（ 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、60;   ）的一種。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、最大

10、堆 C、棧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、#160;   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、（   A        ）。A、分支界限法B、動態規劃法C、貪心法D、回溯法44貪心算法與動態規劃算法的主要區別是（  B         ）。A、最優子結構B、貪心選擇性質C、構造最優解D、定義最優解45. 實現最大子段和利用的算法是（     B      ）。A、分治策略B、動態規劃法C、貪

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

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

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

19、子問題B、最優子結構性質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、60;    ）。A、分治策略B、動態規劃法C、貪心法D、回溯法56、算法是由若干條指令組成的有窮序列，而且滿足以下性質（ D ）（1） 輸入：有0個或多個輸入（2） 輸出：至少有一個輸出（3） 確定性：指令清晰，無歧義（4） 有限性：指令執行次數有限，而且執行時間有限 A (1)(2)(3) B(1)(2)(4) C(1)(3)(4) D (1) (2)(3)(4)57、函數32n+10nlogn的漸進表達式是( B ).A. 2n B. 32n C. nlogn D. 10nlogn58、大整數乘法算法是( A ).算法A.分治 B.貪心C.動態規劃 D.窮舉

21、59、用動態規劃算法解決最大字段和問題，其時間復雜性為( B ).A.logn B.n C.n2 D.nlogn60、解決活動安排問題，最好用（B ）算法A.分治 B.貪心C.動態規劃 D.窮舉61、設f(N),g(N)是定義在正數集上的正函數,如果存在正的常數C和自然數N0,使得當NN0時有f(N)Cg(N),則稱函數f(N)當N充分大時有下界g(N),記作f(N)(g(N),即f(N)的階( A )g(N)的階.A.不高于 B.不低于C.等價于 D.逼近62、回溯法在解空間樹T上的搜索方式是( A ).A.深度優先 B.廣度優先 C.最小耗費優先 D.活結點優先63、回溯算法和分支限界法的

22、問題的解空間樹不會是(D ).A.有序樹 B.子集樹C.排列樹 D.無序樹64、在對問題的解空間樹進行搜索的方法中,一個活結點最多有一次機會成為活結點的是( B ).A.回溯法 B.分支限界法C.回溯法和分支限界法 D.回溯法求解子集樹問題65、從活結點表中選擇下一個擴展結點的不同方式將導致不同的分支限界法,以下除( C )之外都是最常見的方式.A.隊列式分支限界法 B.優先隊列式分支限界法C.棧式分支限界法 D.FIFO分支限界法二、 填空題 1.算法的復雜性有 時間 復雜性和 空間 復雜性之分。2、程序是 算法     用某種程序設計語言的

23、具體實現。3、算法的“確定性”指的是組成算法的每條 指令 是清晰的，無歧義的。4.矩陣連乘問題的算法可由 動態規劃 設計實現。5、拉斯維加斯算法找到的解一定是 正確解。6、算法是指解決問題的 一種方法 或 一個過程 。7、從分治法的一般設計模式可以看出，用它設計出的程序一般是 遞歸算法 。8、問題的 最優子結構性質 是該問題可用動態規劃算法或貪心算法求解的關鍵特征。9、以深度優先方式系統搜索問題解的算法稱為 回溯法 。10、數值概率算法常用于 數值問題 的求解。11、計算一個算法時間復雜度通常可以計算 循環次數 、 基本操作的頻率 或計算步。12、利用概率的性質計算近似值的隨機算法是_數值概率

24、算法，運行時以一定的概率得到正確解的隨機算法是_蒙特卡羅算法_。14、解決0/1背包問題可以使用動態規劃、回溯法和分支限界法，其中不需要排序的是 動態規劃 ，需要排序的是 回溯法 ，分支限界法 。15、使用回溯法進行狀態空間樹裁剪分支時一般有兩個標準：約束條件和目標函數的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時使用約束條件和目標函數的界進行裁剪的是 0/1背包問題 ，只使用約束條件進行裁剪的是 N皇后問題 。16、 貪心選擇性質 是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。17、矩陣連乘問題的算法可由 動態規劃 設計實現。18、拉斯維加斯算法找到的

25、解一定是 正確解。19.貪心算法的基本要素是 貪心選擇 質和 最優子結構 性質 。21. 動態規劃算法的基本思想是將待求解問題分解成若干 子問題 ，先求解 子問題 ，然后從這些 子問題 的解得到原問題的解。22.算法是由若干條指令組成的有窮序列，且要滿足輸入、 輸出 、確定性和 有限性 四條性質。23、大整數乘積算法是用 分治法 來設計的。24、以廣度優先或以最小耗費方式搜索問題解的算法稱為 分支限界法 。25、舍伍德算法總能求得問題的 一個解 。26、 貪心選擇性質 是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。27.快速排序算法是基于 分治策略 的一種排序算法。28

26、.動態規劃算法的兩個基本要素是. 最優子結構 性質和 重疊子問題 性質 。 30.回溯法是一種既帶有 系統性 又帶有 跳躍性 的搜索算法。 31.分支限界法主要有 隊列式（FIFO） 分支限界法和 優先隊列式 分支限界法。32分支限界法是一種既帶有 系統性 又帶有 跳躍性 的搜索算法。33回溯法搜索解空間樹時，常用的兩種剪枝函數為 約束函數 和 限界函數 。34.任何可用計算機求解的問題所需的時間都與其 規模 有關。35.快速排序算法的性能取決于 劃分的對稱性 。36. Prim算法利用 貪心 策略求解 最小生成樹 問題，其時間復雜度是 O(n2) 。37. 圖的m著色問題可用 回溯 法求解，

27、其解空間樹中葉子結點個數是 mn ，解空間樹中每個內結點的孩子數是 m 。三、算法填空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 a) int sum=0, b=0； /s

28、um存儲當前最大的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 QuickSort (Type a, int p, int r) if (p<r) int q=Partition(a,p,r); QuickSort (a,p,q-1); /對左半段排序 QuickSort (a,q+1,r); /對右半段排序 4.排列

29、問題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=k; i<=m; i+) swap(listk，listi); perm(list,k+1;m); swap(listk,listi); 5.給定已按升序排好序的n個元素a0:n-1，現要在這n個元素中找出

30、一特定元素x。 據此容易設計出二分搜索算法：template<class Type> int BinarySearch(Type a, const Type& x, int l, int r) while (l<=r ) int m = (l+r)/2); if (x = am) return m; if (x < am) r = m-1; else l = m+1; return -1; 6、合并排序描述如下：template<class Type>void Mergesort(Type a , int left, int right)if (le

31、ft<right)int i=( left+right)/2;Mergesort(a, left, i );Mergesort(a, i+1, right);Merge(a,b, left,i,right);/合并到數組bCopy(a,b, left,right ); /復制到數組a 7、以下是計算xm的值的過程int power ( x, m )/計算xm的值并返回。y=( 1 );i=m;While(i- - >0) y=y*x; (return y) 四、問答題1.用計算機求解問題的步驟：1、問題分析2、數學模型建立3、算法設計與選擇4、算法指標5、算法分析6、算法

32、實現7、程序調試8、結果整理文檔編制2. 算法定義：算法是指在解決問題時，按照某種機械步驟一定可以得到問題結果的處理過程3.算法的三要素1、操作2、控制結構3、數據結構4. 算法具有以下5個屬性：有窮性：一個算法必須總是在執行有窮步之后結束，且每一步都在有窮時間內完成。確定性：算法中每一條指令必須有確切的含義。不存在二義性。只有一個入口和一個出口可行性：一個算法是可行的就是算法描述的操作是可以通過已經實現的基本運算執行有限次來實現的。輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定對象的集合。輸出：一個算法有一個或多個輸出，這些輸出同輸入有著某些特定關系的量。5. 算法設計的質量指標：正

33、確性：算法應滿足具體問題的需求；可讀性：算法應該好讀，以有利于讀者對程序的理解；健壯性：算法應具有容錯處理，當輸入為非法數據時，算法應對其作出反應，而不是產生莫名其妙的輸出結果。效率與存儲量需求：效率指的是算法執行的時間；存儲量需求指算法執行過程中所需要的最大存儲空間。一般這兩者與問題的規模有關。經常采用的算法主要有迭代法、分治法、貪婪法、動態規劃法、回溯法、分支限界法6. 迭代法: 也稱“輾轉法”，是一種不斷用變量的舊值遞推出新值的解決問題的方法。7.利用迭代算法解決問題，需要做好以下三個方面的工作：1)、確定迭代模型。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新

34、值的變量，這個變量就是迭代變量。2)、建立迭代關系式。所謂迭代關系式，指如何從變量的前一個值推出其下一個值的公式（或關系）。迭代關系式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成。3)、對迭代過程進行控制。在什么時候結束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復執行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定。對于前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對于后一種情況，需要進一步分析出用來結束迭代過程的條件。8.分治法的基本思想是：將一個規模為n的問題分解

35、為k個規模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。9.分治法所能解決的問題一般具有以下幾個特征： （1）該問題的規模縮小到一定的程度就可以容易地解決； （2）該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質； （3）利用該問題分解出的子問題的解可以合并為該問題的解； （4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。 10、分治法的基本步驟 分治法在每一層遞歸上都有三個步驟： （1）分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題； （2）解決：若子問題規

36、模較小而容易被解決則直接解，否則遞歸地解各個子問題； （3）合并：將各個子問題的解合并為原問題的解。11. 動態規劃的基本思想前文主要介紹了動態規劃的一些理論依據，我們將前文所說的具有明顯的階段劃分和狀態轉移方程的動態規劃稱為標準動態規劃，這種標準動態規劃是在研究多階段決策問題時推導出來的，具有嚴格的數學形式，適合用于理論上的分析。在實際應用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規模更小的子問題，并且原問題的最優解中包含了子問題的最優解（即滿足最優子化原理），則可以考慮用動態規劃解決。動態規劃的實質是分治思想和解決冗余，因此，動態規劃是

37、一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復的子問題，以解決最優化問題的算法策略。由此可知，動態規劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，并通過求解子問題產生一個全局最優解。貪心法的當前選擇可能要依賴已經作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的（即不包含公共的子問題），因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。不足之處：如果當前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優解；如果各子問題是不獨立的

38、，則分治法要做許多不必要的工作，重復地解公共的子問題。解決上述問題的辦法是利用動態規劃。該方法主要應用于最優化問題，這類問題會有多種可能的解，每個解都有一個值，而動態規劃找出其中最優（最大或最小）值的解。若存在若干個取最優值的解的話，它只取其中的一個。在求解過程中，該方法也是通過求解局部子問題的解達到全局最優解，但與分治法和貪心法不同的是，動態規劃允許這些子問題不獨立，（亦即各子問題可包含公共的子問題）也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，并將結果保存起來，避免每次碰到時都要重復計算。因此，動態規劃法所針對的問題有一個顯著的特征，即它所對應的子問題樹中的子問題呈現大

39、量的重復。動態規劃法的關鍵就在于，對于重復出現的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。12、動態規劃算法的基本步驟設計一個標準的動態規劃算法，通常可按以下幾個步驟進行：（1）劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的（即無后向性），否則問題就無法用動態規劃求解。 （2）選擇狀態：將問題發展到各個階段時所處于的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無后效性。 （3）確定決策并寫出狀態轉移方程：之所以把這兩步放在一起，是因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據

40、上一階段的狀態和決策來導出本階段的狀態。所以，如果我們確定了決策，狀態轉移方程也就寫出來了。但事實上，我們常常是反過來做，根據相鄰兩段的各狀態之間的關系來確定決策。 （4）寫出規劃方程（包括邊界條件）：動態規劃的基本方程是規劃方程的通用形式化表達式。一般說來，只要階段、狀態、決策和狀態轉移確定了，這一步還是比較簡單的。動態規劃的主要難點在于理論上的設計，一旦設計完成，實現部分就會非常簡單。根據動態規劃的基本方程可以直接遞歸計算最優值，但是一般將其改為遞推計算。實際應用當中經常不顯式地按照上面步驟設計動態規劃，而是按以下幾個步驟進行：（1）分析最優解的性質，并刻劃其結構特征。 （2）遞歸地定義最

41、優值。 （3）以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計算出最優值。 （4）根據計算最優值時得到的信息，構造一個最優解。 步驟（1）（3）是動態規劃算法的基本步驟。在只需要求出最優值的情形，步驟（4）可以省略，若需要求出問題的一個最優解，則必須執行步驟（4）。此時，在步驟（3）中計算最優值時，通常需記錄更多的信息，以便在步驟（4）中，根據所記錄的信息，快速地構造出一個最優解。總結：動態規劃實際上就是最優化的問題，是指將原問題的大實例等價于同一最優化問題的較小實例，自底向上的求解最小實例，并將所求解存放起來，存放的結果就是為了準備數據。與遞歸相比，遞歸是不斷的調用子程序求解，是自頂向下

42、的調用和求解。13. 分治法與動態規劃法的相同點是：將待求解的問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。兩者的不同點是：適合于用動態規劃法求解的問題，經分解得到的子問題往往不是互相獨立的。而用分治法求解的問題，經分解得到的子問題往往是互相獨立的。14. 回溯法      回溯法也稱為試探法，該方法首先暫時放棄關于問題規模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當發現當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規模要求外，滿足所有其他要求時，繼續擴大當前候選解的規模，并繼

43、續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。15. 分支限界法：這是一種用于求解組合優化問題的排除非解的搜索算法。類似于回溯法，分枝定界法在搜索解空間時，也經常使用樹形結構來組織解空間。然而與回溯法不同的是，回溯算法使用深度優先方法搜索樹結構，而分枝定界一般用寬度優先或最小耗費方法來搜索這些樹。因此，可以很容易比較回溯法與分枝定界法的異同。相對而言，分枝定界算法的解空間比回溯法大得多，因此當內存容量有限時，回溯法成功的可能性更大。 算法思想：分枝

44、限界（branch and bound）是另一種系統地搜索解空間的方法，它與回溯法的主要區別在于對E-節點的擴充方式。每個活節點有且僅有一次機會變成E-節點。當一個節點變為E-節點時，則生成從該節點移動一步即可到達的所有新節點。在生成的節點中，拋棄那些不可能導出（最優）可行解的節點，其余節點加入活節點表，然后從表中選擇一個節點作為下一個E-節點。從活節點表中取出所選擇的節點并進行擴充，直到找到解或活動表為空，擴充過程才結束。 有兩種常用的方法可用來選擇下一個E-節點（雖然也可能存在其他的方法）： 1) 先進先出（F I F O） 即從活節點表中取出節點的順序與加入節點的順序相同，因此活 節點表

45、的性質與隊列相同。 2) （優先隊列）最小耗費或最大收益法在這種模式中，每個節點都有一個對應的耗費或收益。如果查找 一個具有最小耗費的解，則活節點表可用最小堆來建立，下一個E-節點就是具有最小耗費 的活節點；如果希望搜索一個具有最大收益的解，則可用最大堆來構造活節點表，下一個 E-節點是具有最大收益的活節點16. 分支限界法與回溯法的相同點是：都是一種在問題的解空間樹T中搜索問題解的算法。不同點：（1）求解目標不同； （2）搜索方式不同； （3）對擴展結點的擴展方式不同； （4）存儲空間的要求不同。17. 分治法所能解決的問題一般具有的幾個特征是：（1）該問題的規模縮小到一定的程度就可以容易地

46、解決； （2）該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質; （3）利用該問題分解出的子問題的解可以合并為該問題的解； （4）原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。18. 用分支限界法設計算法的步驟是：(1)針對所給問題，定義問題的解空間（對解進行編碼）； (2)確定易于搜索的解空間結構（按樹或圖組織解） ； (3)以廣度優先或以最小耗費（最大收益）優先的方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。19. 常見的兩種分支限界法的算法框架：（1）隊列式(FIFO)分支限界法：按照隊列先進先出（FIFO）原則選取下一個節點為擴展節

47、點。 （2）優先隊列式分支限界法：按照優先隊列中規定的優先級選取優先級最高的節點成為當前擴展節點。20. 回溯法中常見的兩類典型的解空間樹是子集樹和排列樹。當所給的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹稱為子集樹。這類子集樹通常有2n個葉結點，遍歷子集樹需O(2n)計算時間 。當所給的問題是確定n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。這類排列樹通常有n!個葉結點。遍歷排列樹需要O(n!)計算時間。21. 分支限界法的搜索策略是： 在擴展結點處，先生成其所有的兒子結點（分支），然后再從當前的活結點表中選擇下一個擴展結點。為了有效地選擇下一擴展結點，加速

48、搜索的進程，在每一個活結點處，計算一個函數值（限界），并根據函數值，從當前活結點表中選擇一個最有利的結點作為擴展結點，使搜索朝著解空間上有最優解的分支推進，以便盡快地找出一個最優解。22. 請敘述動態規劃算法與貪心算法的異同。共同點：都需要最優子結構性質，都用來求有優化問題。不同點：動態規劃：每一步作一個選擇依賴于子問題的解。 貪心方法：每一步作一個選擇不依賴于子問題的解。動態規劃方法的條件：子問題的重疊性質。 可用貪心方法的條件：最優子結構性質；貪心選擇性質。動態規劃：自底向上求解； 貪心方法： 自頂向下求解。可用貪心法時，動態規劃方法可能不適用； 可用動態規劃方法時，貪心法可能不適用。23

49、. 請說明動態規劃方法為什么需要最優子結構性質。答：最優子結構性質是指大問題的最優解包含子問題的最優解。動態規劃方法是自底向上計算各個子問題的最優解，即先計算子問題的最優解，然后再利用子問題的最優解構造大問題的最優解，因此需要最優子結構.24. 請說明：(1)優先隊列可用什么數據結構實現？(2)優先隊列插入算法基本思想？(3)優先隊列插入算法時間復雜度？ 答：（1）堆。 （2）在小根堆中，將元素x插入到堆的末尾，然后將元素x的關鍵字與其雙親的關鍵字比較，若元素x的關鍵字小于其雙親的關鍵字，則將元素x與其雙親交換，然后再將元素x與其新雙親的關鍵字相比，直到元素x的關鍵字大于雙親的關鍵字，或元素x

50、到根為止。（3）O( log n) 25. 衡量算法時間效率的方法有哪兩種？請敘述。答：有事前分析法和事后分析法兩種。事后分析法：先將算法用程序設計語言實現，然后度量程序的運行時間。事前分析法：算法的時間效率是問題規模的函數，假如，隨著問題規模n的增長，算法執行時間的增長率和函數f(n)的增長率相同，則可記作： T(n)=(f(n)稱T(n)為算法的漸進時間復雜度。簡稱時間復雜度。26. 在算法復雜性分析中，O、這三個記號的意義是什么？在忽略常數因子的情況 下，O、分別提供了算法運行時間的什么界？答：如果存在兩個正常數c和N0,對于所有的NN0，有|f(N)|C|g(N)|，則記作：f(N)=

51、 O(g(N)。這時我們說f(N)的階不高于g(N)的階。若存在兩個正常數C和自然數N0，使得當N N0時有|f(N)|C|g(N)|，記為f(N)=(g(N)。這時我們說f(N)的階不低于g(N)的階。如果存在正常數c1，c2和n0，對于所有的nn0，有c1|g(N)| |f(N)| c2|g(N)| 則記作 f(N)= (g,(N)O、分別提供了算法運行時間的上界、下界、平均27. 概率算法很多算法的每一個計算步驟都是固定的，而概率算法允許算法在執行的過程中隨機選擇下一個計算步驟。許多情況下，當算法在執行過程中面臨一個選擇時，隨機性選擇常比最優選擇省時。因此概率算法可在很大程度上降低算法的

52、復雜度。 28.概率算法的一個基本特征是對所求解問題的同一實例用同一概率算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時間甚至所得到的結果可能會有相當大的差別。29概率算法大致分為四類:數值概率算法，蒙特卡羅（Monte Carlo）算法，拉斯維加斯（Las Vegas）算法和舍伍德（Sherwood）算法。 30.數值概率算法常用于數值問題的求解。這類算法所得到的往往是近似解。而且近似解的精度隨計算時間的增加不斷提高。在許多情況下，要計算出問題的精確解是不可能或沒有必要的，因此用數值概率算法可得到相當滿意的解。 31.蒙特卡羅算法用于求問題的準確解。對于許多問題來說，近似解毫無意義

53、。例如，一個判定問題其解為“是”或“否”，二者必居其一，不存在任何近似解答。又如，我們要求一個整數的因子時所給出的解答必須是準確的，一個整數的近似因子沒有任何意義。用蒙特卡羅算法能求得問題的一個解，但這個解未必是正確的。求得正確解的概率依賴于算法所用的時間。算法所用的時間越多，得到正確解的概率就越高。蒙特卡羅算法的主要缺點就在于此。一般情況下，無法有效判斷得到的解是否肯定正確。 32.拉斯維加斯算法不會得到不正確的解，一旦用拉斯維加斯算法找到一個解，那么這個解肯定是正確的。但是有時候用拉斯維加斯算法可能找不到解。與蒙特卡羅算法類似。拉斯維加斯算法得到正確解的概率隨著它用的計算時間的增加而提高。

54、對于所求解問題的任一實例，用同一拉斯維加斯算法反復對該實例求解足夠多次，可使求解失效的概率任意小。 33.舍伍德算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性算法在最壞情況下的計算復雜性與其在平均情況下的計算復雜性有較大差別時，可以在這個確定算法中引入隨機性將它改造成一個舍伍德算法，消除或減少問題的好壞實例間的這種差別。舍伍德算法精髓不是避免算法的最壞情況行為，而是設法消除這種最壞行為與特定實例之間的關聯性。舍伍德算法  sherwood algorithm 舍伍德算法 一類概率算法的代稱。此類算法總能給出所求問題的正確的解。.當解決某一問題的確定性算法的平

55、均情形復雜性比最壞情形復雜性低得多時，通過引入隨機性來試圖減少甚至消除“好”、“壞”實體之間這種時間上的差別，以期望較小的運行時間。例 . 五、算法設計與分析題1用動態規劃策略求解最長公共子序列問題： （1）給出計算最優值的遞歸方程。 （2）給定兩個序列X=B,C,D,A，Y=A,B,C,B，請采用動態規劃策略求出其最長公共子序列，要求給出過程。答：(1) (2)0 0 0 00 0 1 1 10 0 1 2 20 0 1 2 20 1 1 2 2 最長公共子序列：2對下列各組函數f (n) 和g (n)，確定f (n) = O (g (n) 或f (n) =(g (n)或f(n) =(g(n)，并簡要說明理由。(1) f(n)=2n； g(n)=n! (2) f(n)=； g (n)=log n2 (3) f(n)=100； g(n)=log100 (4) f(n)=n3； g(n)= 3n(5) f(n)=3n； g(n)=2n答： (1) f(n) = O(g(n) 因為g(n)的階比f(n)的階高。(2) f(n) = (g(n) 因為g(n)的階比f(n)的階低。(3) f