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

1、一、選擇題1、衡量一個算法好壞的標準是(c )。(a)運行速度快(b)占用空間少(c)時間復雜度低(d)代碼短2、記號。的定義正確的是(a)(b)(c)(d)o(g(n) = f(n) |o(g(n) = f(n) |o(g(n) = f(n) | 有：0 值f(n)cg(n)o(g(n) = f(n) | 有：0 三 cg(n) f(n) (a)。存在正常數(shù)存在正常數(shù)c和n0使得對所有n之n0有：00,存在正數(shù)和對于任何正常數(shù)c0,存在正數(shù)和3、二分搜索算法是利用( a )(a)分治策略(b)動態(tài)規(guī)劃法4、使用分治法求解不需要滿足的條件是(實現(xiàn)的算法。(c)貪心法a )。(d)n0 0使得對

2、所有n0 0使得對所有回溯法m cg(n) 三 f(n) n -n0n -n0(a)子問題必須是一樣的 (c)子問題的解可以合并5、合并排序算法是利用( (a)分治策略(b)6、實現(xiàn)大整數(shù)的乘法是利用(a)貪心法(b)(b)子問題不能夠重復(d)原問題和子問題使用相同的方法解 )實現(xiàn)的算法。動態(tài)規(guī)劃法c )的算法。動態(tài)規(guī)劃法(c)貪心法(c)分治策略(d)(d)回溯法回溯法7、以下不可以使用分治法求解的是(a)棋盤覆蓋問題(b)選擇問題8、實現(xiàn)循環(huán)賽日程表利用的算法是(a)分治策略(b)動態(tài)規(guī)劃法9、實現(xiàn)棋盤覆蓋算法利用的算法是(a(qa(c)歸并排序)。貪心法)。(d)0/1背包問題(d)回

3、溯法(a)分治法(b)動態(tài)規(guī)劃法10、矩陣連乘問題的算法可由( b )(c)貪心法 設(shè)計實現(xiàn)。(d)回溯法(a)分支界限算法(b)動態(tài)規(guī)劃算法11、實現(xiàn)大整數(shù)的乘法是利用的算法(a)貪心法(b)動態(tài)規(guī)劃法12、最長公共子序列算法利用的算法是(a)分支界限法(b)動態(tài)規(guī)劃法(c)貪心算法)。(c)分治策略b )。(c )貪心法(d)回溯算法(d)回溯法13、下列算法中通常以自底向上的方式求解最優(yōu)解的是(a)備忘錄法(b)動態(tài)規(guī)劃法14、下列是動態(tài)規(guī)劃算法基本要素的是(a)定義最優(yōu)解(b)構(gòu)造最優(yōu)解15、下列不是動態(tài)規(guī)劃算法基本步驟的是(a)找出最優(yōu)解的解空間(b)構(gòu)造最優(yōu)解(c)貪心法d )。(

4、c)算出最優(yōu)解a )。(q算出最優(yōu)解(d)。(d)(d)回溯法回溯法子問題重疊性質(zhì)16、能采用貪心算法求最優(yōu)解的問題，- (a)最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì) (c)最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)般具有的重要性質(zhì)為:(d)定義最優(yōu)解a )(b)重疊子問題性質(zhì)與貪心選擇性質(zhì)(d)預排序與遞歸調(diào)用17、下面問題(b )不能使用貪心法解決。(a)單源最短路徑問題(b)(c)最小花費生成樹問題(d)18、以下不可以使用分治法求解的是( d )。n皇后問題背包問題(a)棋盤覆蓋問題(b)選擇問題(c)歸并排序(d) 0/1背包問題519 、備忘錄方法是那種算法的變形（ b ） 。（a）分治法（b）動態(tài)規(guī)劃

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

6、間樹是（ a ） 。（a）子集樹（b）排列樹（q深度優(yōu)先生成樹（d）廣度優(yōu)先生成樹25 、回溯法解旅行售貨員問題時的解空間樹是（b ） 。（a）子集樹（b）排列樹（q深度優(yōu)先生成樹（d）廣度優(yōu)先生成樹26 、一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（b ） 。（a）重疊子問題（b）最優(yōu)子結(jié)構(gòu)性質(zhì)（c）貪心選擇性質(zhì)（d）定義最優(yōu)解27 、下列算法中不能解決0/1 背包問題的是（ a ）（a）貪心法（b）動態(tài)規(guī)劃（c）回溯法（d）分支限界法28 、下面問題（b ）不能使用貪心法解決。（a）單源最短路徑問題（b） n皇后問題 （c）最小生成樹問題（d）背包問題29 、矩陣連乘問題的算

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

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

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

10、例中最大的時間復雜度：w(n) = max t(n , i) , i c dn平均時間復雜性是所有輸入實例的處理時間與各自概率的乘積和：a(n) = ep(i)t(n , i) i c dn6. 設(shè)輸入是一個按非降次序排列的元素表ai ： j 和 x ，選取 a(i+j)/2 與 x 比較，如果a(i+j)/2=x,則返回(i+j)/2,如果 a(i+j)/2卜x,則 ai ： (i+j)/2-1 找 x,否則在a (i+j)/2+1： j 找 x 。上述過程被反復遞歸調(diào)用。7. 不相同。目標函數(shù)：獲得最大利潤。最優(yōu)量度：最大利潤 / 重量比。8. 問題的解可以表示為n元組：(xi,x2, x

11、n) ,xics, s為有窮集合，xys, (xi,x 2,xn)具備完備性，即(xi,x2,xn)是合理的，則(xi,x2,xi) (i no,有t(n)f(n)，這種關(guān)系記作 t(n)=o(f(n)。14. 二分檢索算法的最多的比較次數(shù)為log n 。15. 最壞情況下快速排序退化成冒泡排序，需要比較n2 次。16. 是一種依據(jù)最優(yōu)化量度依次選擇輸入的分級處理方法。基本思路是：首先根據(jù)題意，選取一種 量度標準；然后按這種量度標準對這n 個輸入排序，依次選擇輸入量加入部分解中。如果當前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。17. 回溯法的解(x1,x2,xn)的隱約束

12、一般指個元素之間應(yīng)滿足的某種關(guān)系。18. 講數(shù)組一分為二，分別對每個集合單獨排序，然后將已排序的兩個序列歸并成一個含 n 個 元素的分好類的序列。如果分割后子問題還很大，則繼續(xù)分治，直到一個元素。19. 快速排序的基本思想是在待排序的 n 個記錄中任意取一個記錄， 把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復上述過程，直到每一部分內(nèi)只有一個記錄為止。20. 在定義一個過程或者函數(shù)的時候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成分，既調(diào)用它自己本身，這稱為直接遞歸。如

13、果過程或者函數(shù)p調(diào)用過程或者函數(shù)q q又調(diào)用p,這個稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)。21. 分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。 遞歸地解這些子問題， 然后將各個子問題的解合并得到原問題的解。22. 設(shè)計動態(tài)規(guī)劃算法的主要步驟為：（ 1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 （ 2）遞歸地定義最優(yōu)值。（ 3 ）以自底向上的方式計算出最優(yōu)值。（ 4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。23. 分治法與動態(tài)規(guī)劃法的相同點是：將待求解的問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。兩者的不同點是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨立的。24. 備忘錄方法是動態(tài)規(guī)劃算法的