算法分析復習題含答案

1、一、選擇題1、衡量一個算法好壞的標準是（A）運行速度快（B）占用空間少2、記號 O 的定義正確的是（ A）。（ A ）（ B）（ C）C ）。（C）時間復雜度低（D）代碼短D)O（g（n） = f（n） | 存在正常數 c 和 n0 使得對所有 nO（g（n） = f（n） | 存在正常數 c 和 n0 使得對所有O（g（n） = f（n） | 對于任何正常數 有： 0 f（n）cg（n） ； O（g（n） = f（n） | 對于任何正常數 有： 0cg（n） 0，存在正數和c0,存在正數和3、 二分搜索算法是利用（A（A）分治策略（B）動態(tài)規(guī)劃法4、使用分治法求解不需要滿足的條件是（B）子問

2、題不能夠重復）實現的算法。（C）貪心法A ）。（A）子問題必須是一樣的（C）子問題的解可以合并5、合并排序算法是利用（ A ）分治策略（6、 實現大整數的乘法是利用（C（A）貪心法（B）動態(tài)規(guī)劃法7、 以下不可以使用分治法求解的是（D（A）棋盤覆蓋問題（B）選擇問題8、實現循環(huán)賽日程表利用的算法是（A）分治策略（B）動態(tài)規(guī)劃法9、實現棋盤覆蓋算法利用的算法是（A）分治法（B）動態(tài)規(guī)劃法10、矩陣連乘問題的算法可由（B）（A）分支界限算法11、實現大整數的乘法是利用的算法（A）貪心法（B）動態(tài)規(guī)劃法12、最長公共子序列算法利用的算法是（A）分支界限法（B）動態(tài)規(guī)劃法13、下列算法中通常以自底向上

3、的方式求解最優(yōu)解的是（A）備忘錄法（B）動態(tài)規(guī)劃法14、下列是動態(tài)規(guī)劃算法基本要素的是（A）定義最優(yōu)解（B）構造最優(yōu)解15、下列不是動態(tài)規(guī)劃算法基本步驟的是（A）找出最優(yōu)解的解空間16、能采用貪心算法求最優(yōu)解的問題，一（A）最優(yōu)子結構性質與貪心選擇性質（C）最優(yōu)子結構性質與重疊子問題性質17、下面問題（ B ）不能使用貪心法解決。（A）單源最短路徑問題（B）（C）最小花費生成樹問題（D）18、以下不可以使用分治法求解的是（D ）。（A）棋盤覆蓋問題（B）選擇問題cg(n) ；f(n) ；n0f(n) cg(n) nn0 有：n0 有： n0 0 使得對所有n0 0 使得對所有（D）回溯法（D）

4、原問題和子問題使用相同的方法解 ）實現的算法。A（B）動態(tài)規(guī)劃法）的算法。C)C)n0）。AC)A貪心法分治策略歸并排序）。貪心法C)D)D)D)D)回溯法回溯法回溯法0/1 背包問題）。（C）貪心法 設計實現。（B）動態(tài)規(guī)劃算法C（C）貪心算法 ）。（C）分治策略D)回溯法（D）回溯算法（D）回溯法B)。C ）貪心法（C）貪心法 ）。（D）回溯法）。（D）回溯法（C）算出最優(yōu)解 A ）。（B）構造最優(yōu)解 （C）算出最優(yōu)解 般具有的重要性質為： （D）子問題重疊性質（D）定義最優(yōu)解A ）（B）重疊子問題性質與貪心選擇性質（D）預排序與遞歸調用N 皇后問題背包問題（C）歸并排序D） 0/1 背包

5、問題19、備忘錄方法是那種算法的變形（B）。（A）分治法（B）動態(tài)規(guī)劃法（C）貪心法（D）回溯法20、下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（A）備忘錄法（B）動態(tài)規(guī)劃法（C）貪心法D ）。（D）回溯法21、下面哪種函數是回溯法中為避免無效搜索采取的策略（B ）（A）遞歸函數（B）剪枝函數（C）隨機數函數（D）搜索函數22、回溯法在問題的解空間樹中，按（A）廣度優(yōu)先（B）活結點優(yōu)先23、回溯法的效率不依賴于下列哪些因素（D ）策略，從根結點出發(fā)搜索解空間樹。（C）擴展結點優(yōu)先（D）深度優(yōu)先D）。（A） 滿足顯約束的值的個數（B）計算約束函數的時間（C）計算限界函數的時間（D）確定解空間

6、的時間24、回溯法解 0-1 背包問題時的解空間樹是（ A）。（D）廣度優(yōu)先生成樹（D）廣度優(yōu)先生成樹（A）子集樹（B）排列樹（C）深度優(yōu)先生成樹25、 回溯法解旅行售貨員問題時的解空間樹是（ B）。（A）子集樹（B）排列樹（C）深度優(yōu)先生成樹26、 一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征是問題的（B ）。（A）重疊子問題 （B）最優(yōu)子結構性質（C）貪心選擇性質（D）定義最優(yōu)解27、下列算法中不能解決 0/1 背包問題的是（ A ）（A）貪心法（B）動態(tài)規(guī)劃（C）回溯法（D）分支限界法28、下面問題（ B ）不能使用貪心法解決。（A）單源最短路徑問題（B） N皇后問題 （C）最小生成

7、樹問題（D）背包問題29、 矩陣連乘問題的算法可由（B ）設計實現。（A）分支界限算法（B）動態(tài)規(guī)劃算法（C）貪心算法（D）回溯算法30、 貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是（B）。（A）最優(yōu)子結構（B）貪心選擇性質（C）構造最優(yōu)解（D）定義最優(yōu)解、簡答題1. 算法重要特性是什么2. 算法分析的目的是什么3. 算法的時間復雜性與問題的什么因素相關4. 算法的漸進時間復雜性的含義5. 最壞情況下的時間復雜性和平均時間復雜性有什么不同6. 簡述二分檢索（折半查找）算法的基本過程。7. 背包問題的目標函數和貪心算法最優(yōu)化量度相同嗎8. 采用回溯法求解的問題，其解如何表示有什么規(guī)定9. 回溯法的搜索特

8、點是什么10. n 皇后問題回溯算法的判別函數 place 的基本流程是什么11. 為什么用分治法設計的算法一般有遞歸調用12. 為什么要分析最壞情況下的算法時間復雜性13. 簡述漸進時間復雜性上界的定義。14. 二分檢索算法最多的比較次數15. 快速排序算法最壞情況下需要多少次比較運算16. 貪心算法的基本思想17. 回溯法的解（X1,X2,xn）的隱約束一般指什么18. 闡述合并排序的分治思路。19. 快速排序的基本思想是什么。20. 什么是直接遞歸和間接遞歸消除遞歸一般要用到什么數據結構21. 試述分治法的基本思想。22. 設計動態(tài)規(guī)劃算法有哪些主要步驟23. 分治法與動態(tài)規(guī)劃法的異同2

9、4. 備忘錄方法和動態(tài)規(guī)劃算法相比有何異同簡述之。參考答案：1. 輸入、輸出、確定性、有限性、可實現性。2. 分析算法占用計算機資源的情況，對算法做出比較和評價，設計出更好的算法。3. 算法的時間復雜性與問題的規(guī)模相關，是問題大小 n 的函數。4. 當問題的規(guī)模 n趨向無窮大時，影響算法效率的重要因素是T(n)的數量級，而其他因素僅是使時間復雜度相差常數倍，因此可以用T(n)的數量級(階)評價算法。時間復雜度T(n)的數量級 (階)稱為漸進時間復雜性。5. 最壞情況下的時間復雜性和平均時間復雜性考察的是 n 固定時，不同輸入實例下的算法所 耗時間。最壞情況下的時間復雜性取的輸入實例中最大的時間

10、復雜度：W(n) = max T(n , I) , l Dn 平均時間復雜性是所有輸入實例的處理時間與各自概率的乘積和：A(n) =E P(I)T(n, I) I Dn6. 設輸入是一個按非降次序排列的元素表Ai：j和x,選取A(i+j)/2與x比較，如果A(i+j)/2=x ,則返回(i+j)/2，如果 A(i+j)/2x，貝U Ai: (i+j)/2-1找 x,否則在 A (i+j)/2+1 : j找 x。上述 過程被反復遞歸調用。7. 不相同。目標函數：獲得最大利潤。最優(yōu)量度：最大利潤 /重量比。8問題的解可以表示為n元組：(X1,X2, xn),XiS, S為有窮集合，XiS,( X1

11、,X2,xn)具備完備性，即(X1 ,X2,Xn)是合理的，則(X1,X2,Xi) (in) 定合理。9. 在解空間樹上跳躍式地深度優(yōu)先搜索，即用判定函數考察 xk的取值，如果xk是合理的就搜索xk為根節(jié)點的子樹，如果xk取完了所有的值，便回溯到xk-1。10. 將第K行的皇后分別與前 k-1行的皇后比較，看是否與它們相容，如果不相容就返回false,測試完畢則返回 true 。11. 子問題的規(guī)模還很大時,必須繼續(xù)使用分治法,反復分治,必然要用到遞歸。12. 最壞情況下的時間復雜性決定算法的優(yōu)劣,并且最壞情況下的時間復雜性較平均時間復雜 性游可操作性。(n)是某算法的時間復雜性函數，f(n)

12、是一簡單函數，存在正整數No和C, nNo,有T(n)f(n),這種關系記作 T(n)=O(f(n)。14. 二分檢索算法的最多的比較次數為log n 。15. 最壞情況下快速排序退化成冒泡排序，需要比較n2次。16. 是一種依據最優(yōu)化量度依次選擇輸入的分級處理方法?；舅悸肥?首先根據題意,選取 一種 量度標準；然后 按這種量度標準對這 n 個輸入排序,依次選擇輸入量加入部分解中。 如果當前這個輸入量的加入,不滿足約束條件,則不把此輸入加到這部分解中。17. 回溯法的解(X1,X2,xn)的隱約束一般指個元素之間應滿足的某種關系。18. 講數組一分為二,分別對每個集合單獨排序,然后將已排序的

13、兩個序列歸并成一個含n 個元素的分好類的序列。如果分割后子問題還很大,則繼續(xù)分治,直到一個元素。19. 快速排序的基本思想是在待排序的N 個記錄中任意取一個記錄, 把該記錄放在最終位置后,數據序列被此記錄分成兩部分。所有關鍵字比該記錄關鍵字小的放在前一部分,所有比它 大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之 后重復上述過程，直到每一部分內只有一個記錄為止。20. 在定義一個過程或者函數的時候又出現了調用本過程或者函數的成分，既調用它自己本身，這稱為直接遞歸。如果過程或者函數P調用過程或者函數 Q, Q又調用P,這個稱為間接遞歸。消除遞歸一般要用到棧這種數據

14、結構。21. 分治法的基本思想是將一個規(guī)模為 n的問題分解為k個規(guī)模較小的子問題，這些子問題互相 獨立且與原問題相同。 遞歸地解這些子問題， 然后將各個子問題的解合并得到原問題的解。22. 設計動態(tài)規(guī)劃算法的主要步驟為：（1）找出最優(yōu)解的性質，并刻劃其結構特征。（ 2）遞歸地定義最優(yōu)值。 （3）以自底向上的方式計算出最優(yōu)值。 （4）根據計算最優(yōu)值時得到的信息，構造最優(yōu)解。23. 分治法與動態(tài)規(guī)劃法的相同點是：將待求解的問題分解成若干個子問題，先求解子問題， 然后從這些子問題的解得到原問題的解。 兩者的不同點是：適合于用動態(tài)規(guī)劃法求解的問題，經分解得到的子問題往往不是互相獨 立的。而用分治法求解的問題，經分解得到的子問題往往是互相獨立的。24. 備忘錄方