算法分析復習題(含答案)

《算法分析復習題(含答案)》由會員分享，可在線閱讀，更多相關《算法分析復習題(含答案)（4頁珍藏版）》請在裝配圖網上搜索。

1、 一、選擇題 1、衡量一個算法好壞的標準是（ C ）。 （ A）運行速度快 （ B）占用空間少 （ C）時間復雜度低 （ D）代碼短 2、記號 O 的定義正確的是（ A）。 （ A） O(g(n) = f(n) | 存在正常數 c 和 n0 使得對所有 n n0 有： 0 f(n) cg(n) ； （ B） O(g(n) = f(n) | 存在正常數 c 和 n0 使得對所有 n n0 有： 0 cg(n) f(n) ； （ C） O(g(n) = f(n) | 對于任何正常數 c0，存在正數和 n0 0 使得對所有 n n0 有： 0 f(n)0，存在正數和 n0 0 使得對所有 n n0

2、有： 0 cg(n) f(n) ； 3、二分搜索算法是利用（ A ）實現的算法。 （ A）分治策略 （ B）動態規劃法 （ C）貪心法 （ D）回溯法 4、使用分治法求解不需要滿足的條件是（ A ）。 （ A）子問題必須是一樣的 （ B）子問題不能夠重復 （ C）子問題的解可以合并 （ D）原問題和子問題使用相同的方法解 5、合并排序算法是利用（ A ）實現的算法。 （ A）分治策略 （ B）動態規劃法 （ C）貪心法 （ D）回溯法 6、實現大整數的乘法是利用（ C ）的算法。 （ A）貪心法 （ B）動態規劃法 （ C）分治策略 （ D）回溯法 7、以下不可以使用分治法求解的是（ D ）。

3、 （ A）棋盤覆蓋問題 （ B）選擇問題 （ C）歸并排序 （ D） 0/1 背包問題 8、實現循環賽日程表利用的算法是（ A ）。 （ A）分治策略 （ B）動態規劃法 （ C）貪心法 （ D）回溯法 9、實現棋盤覆蓋算法利用的算法是（ A ）。 （ A）分治法 （ B）動態規劃法 （ C）貪心法 （ D）回溯法 10、矩陣連乘問題的算法可由（ B ）設計實現。 （ A）分支界限算法 （B）動態規劃算法 （ C）貪心算法 （ D）回溯算法 11、實現大整數的乘法是利用的算法（ C ）。 （ A）貪心法 （ B）動態規劃法 （ C）分治策略 （ D）回溯法 12、最長公共子序列算法利用的算法是

4、（ B ）。 （ A）分支界限法 （ B）動態規劃法 （ C ）貪心法 （ D）回溯法 13、下列算法中通常以自底向上的方式求解最優解的是（ B ）。 （ A）備忘錄法 （ B）動態規劃法 （ C）貪心法 （ D）回溯法 14、下列是動態規劃算法基本要素的是（ D ）。 （ A）定義最優解 （ B）構造最優解 （ C）算出最優解 （ D）子問題重疊性質 15、下列不是動態規劃算法基本步驟的是（ A ）。 （ A）找出最優解的解空間 （ B）構造最優解 （ C）算出最優解 （D）定義最優解 16、能采用貪心算法求最優解的問題，一般具有的重要性質為： （ A ） （ A）最優子結構性質與貪心選擇性

5、質 （ B）重疊子問題性質與貪心選擇性質 （ C）最優子結構性質與重疊子問題性質 （ D）預排序與遞歸調用 17、下面問題（ B ）不能使用貪心法解決。 （ A）單源最短路徑問題 （ B） N 皇后問題 （ C）最小花費生成樹問題 （ D）背包問題 18、以下不可以使用分治法求解的是（ D ）。 （ A）棋盤覆蓋問題 （ B）選擇問題 （ C）歸并排序 （ D） 0/1 背包問題 1 19、備忘錄方法是那種算法的變形（ B ）。 （ A）分治法 （ B）動態規劃法 （ C）貪心法 （ D）回溯法 20、下列算法中通常以深度優先方式系統搜索問題解的是（ D ）。 （ A）備忘錄法 （ B）動態規

6、劃法 （ C）貪心法 （ D）回溯法 21、下面哪種函數是回溯法中為避免無效搜索采取的策略（ B ） （ A）遞歸函數 （ B）剪枝函數 （ C）隨機數函數 （ D）搜索函數 22、回溯法在問題的解空間樹中，按（ D ）策略，從根結點出發搜索解空間樹。 （ A）廣度優先 （ B）活結點優先 （ C）擴展結點優先 （ D）深度優先 23、回溯法的效率不依賴于下列哪些因素（ D ）。 （ A） . 滿足顯約束的值的個數 （ B）計算約束函數的時間 （ C） 計算限界函數的時間 （ D） 確定解空間的時間 24、回溯法解 0-1 背包問題時的解空間樹是（ A ）。 （ A）子集樹 （B）排列樹 （

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

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

9、解的問題，其解如何表示？有什么規定？ 9. 回溯法的搜索特點是什么？ 10. n 皇后問題回溯算法的判別函數 place 的基本流程是什么？ 11. 為什么用分治法設計的算法一般有遞歸調用？ 12. 為什么要分析最壞情況下的算法時間復雜性？ 13. 簡述漸進時間復雜性上界的定義。 14. 二分檢索算法最多的比較次數？ 15. 快速排序算法最壞情況下需要多少次比較運算？ 16. 貪心算法的基本思想？ 2 17. 回溯法的解（ x1,x 2, xn）的隱約束一般指什么？ 18. 闡述合并排序的分治思路。 19. 快速排序的基本思想是什么。 20. 什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數

10、據結構？ 21. 試述分治法的基本思想。 22. 設計動態規劃算法有哪些主要步驟？ 23. 分治法與動態規劃法的異同？ 24. 備忘錄方法和動態規劃算法相比有何異同？簡述之。 參考答案： 1. 輸入、輸出、確定性、有限性、可實現性。 2. 分析算法占用計算機資源的情況，對算法做出比較和評價，設計出更好的算法。 3. 算法的時間復雜性與問題的規模相關，是問題大小 n 的函數。 4當問題的規模 n 趨向無窮大時，影響算法效率的重要因素是 T(n) 的數量級，而其他因素僅 是使時間復雜度相差常數倍，因此可以用 T(n) 的數量級 ( 階 ) 評價算法。時間復雜度 T(n) 的數量級 ( 階 ) 稱為

11、漸進時間復雜性。 5. 最壞情況下的時間復雜性和平均時間復雜性考察的是 n 固定時，不同輸入實例下的算法所 耗時間。最壞情況下的時間復雜性取的輸入實例中最大的時間復雜度： W(n) = max T(n ，I) , I Dn 平均時間復雜性是所有輸入實例的處理時間與各自概率的乘積和： A(n) = P(I)T(n ，I) I Dn 6. 設輸入是一個按非降次序排列的元素表 Ai ： j 和 x，選取 A(i+j)/2 與 x 比較，如果 A(i+j)/2=x ，則返回 (i+j)/2 ，如果 A(i+j)/2x ，則 Ai ： (i+j)/2-1 找 x，否則在 A (i+j)/2+1 ：j 找

12、 x。上述過程被反復遞歸調用。 7. 不相同。目標函數：獲得最大利潤。最優量度：最大利潤 / 重量比。 8. 問題的解可以表示為 n 元組：（ x1,x 2, xn），xi Si , Si 為有窮集合， xi Si , （ x1,x 2, xn）具備完備性，即（ x1,x 2, xn）是合理的，則（ x1,x 2, xi ） (in) 一定合理。 9. 在解空間樹上跳躍式地深度優先搜索，即用判定函數考察 xk 的取值，如果 xk 是合理 的就搜索 xk 為根節點的子樹，如果 xk 取完了所有的值，便回溯到 xk-1 。 10. 將第 K 行的皇后分別與前 k-1 行的皇后比較， 看是否與它們相

13、容， 如果不相容就返回 false ，測試完畢則返回 true 。 11. 子問題的規模還很大時，必須繼續使用分治法，反復分治，必然要用到遞歸。 12. 最壞情況下的時間復雜性決定算法的優劣，并且最壞情況下的時間復雜性較平均時間復雜 性游可操作性。 13.T(n) 是某算法的時間復雜性函數， f(n) 是一簡單函數，存在正整數 No 和 C， n No，有 T(n)f(n) ，這種關系記作 T(n)=O(f(n) 。 14. 二分檢索算法的最多的比較次數為 log n 。 15. 最壞情況下快速排序退化成冒泡排序，需要比較 n2 次。 16. 是一種依據最優化量度依次選擇輸入的分級處理方法?；?/p>

14、本思路是：首先根據題意，選取 一種 量度標準；然后 按這種量度標準對這 n 個輸入排序，依次選擇輸入量加入部分解中。如果當前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。 17. 回溯法的解（ x1,x 2, xn）的隱約束一般指個元素之間應滿足的某種關系。 18. 講數組一分為二，分別對每個集合單獨排序，然后將已排序的兩個序列歸并成一個含 n 個 元素的分好類的序列。如果分割后子問題還很大，則繼續分治，直到一個元素。 3 19. 快速排序的基本思想是在待排序的 N 個記錄中任意取一個記錄， 把該記錄放在最終位置后，數據序列被此記錄分成兩部分。所有關鍵字比該記錄關鍵字小的放在前

15、一部分，所有比它 大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復上述過程，直到每一部分內只有一個記錄為止。 20. 在定義一個過程或者函數的時候又出現了調用本過程或者函數的成分，既調用它自己本 身，這稱為直接遞歸。如果過程或者函數 P 調用過程或者函數 Q，Q 又調用 P，這個稱為間接遞歸。消除遞歸一般要用到棧這種數據結構。 21. 分治法的基本思想是將一個規模為 n 的問題分解為 k 個規模較小的子問題，這些子問題互相獨立且與原問題相同。 遞歸地解這些子問題， 然后將各個子問題的解合并得到原問題的解。 22. 設計動態規劃算法的主要步驟為： （ 1）找出

16、最優解的性質，并刻劃其結構特征。 （ 2）遞歸地定義最優值。 （ 3）以自底向上的方式計算出最優值。 （ 4）根據計算最優值時得到的信息，構造最優解。 23. 分治法與動態規劃法的相同點是：將待求解的問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。 兩者的不同點是：適合于用動態規劃法求解的問題，經分解得到的子問題往往不是互相獨立的。而用分治法求解的問題，經分解得到的子問題往往是互相獨立的。 24. 備忘錄方法是動態規劃算法的變形。與動態規劃算法一樣，備忘錄方法用表格保存已解決的子問題的答案，在下次需要解此問題時，只要簡單地查看該子問題的解答，而不必重新計算。 備忘錄方法與動態規劃算法不同的是，備忘錄方法的遞歸方式是自頂向下的，而動態規劃 算法則是自底向上遞歸的。 因此，備忘錄方法的控制結構與直接遞歸方法的控制結構相同，區別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同的子 問題的重復求解，而直接遞歸方法沒有此功能。 4