1、一、選擇題1、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是A運(yùn)行速度快B占用空間少2、記號0的定義正確的選項(xiàng)是A。 A B CC 。C時(shí)間復(fù)雜度低D代碼短存在正常數(shù)存在正常數(shù) 對于任何正常數(shù) c>0 ，存在正數(shù)和D0(g(n) = f(n) |0(g(n) = f(n) |0(g(n) = f(n) | 有： 0 f(n)<cg(n) 0(g(n) = f(n) | 有： 0 cg(n) < f(n) 對于任何正常數(shù) c>0 ，存在正數(shù)和n0 有： 0 f(n)cg(n) ；n0 有： 0 cg(n)f(n) ；n0 >0 使得對所有n n0n0 >0 使得對所有n n0c和n

2、O使得對所有n c 和 n0 使得對所有 n3、 二分搜索算法是利用A實(shí)現(xiàn)的算法。A分治策略B動(dòng)態(tài)規(guī)劃法C貪心法4、 使用分治法求解不需要滿足的條件是A 。B子問題不能夠重復(fù) D原問題和子問題使用相同的方法解 實(shí)現(xiàn)的算法。D回溯法A子問題必須是一樣的C子問題的解可以合并5、合并排序算法是利用A分治策略B6、實(shí)現(xiàn)大整數(shù)的乘法是利用A貪心法B動(dòng)態(tài)規(guī)劃法 C 的算法。動(dòng)態(tài)規(guī)劃法DC貪心法c分治策略DD回溯法回溯法7、以下不可以使用分治法求解的是A棋盤覆蓋問題B選擇問題8、實(shí)現(xiàn)循環(huán)賽日程表利用的算法是A分治策略B動(dòng)態(tài)規(guī)劃法9、實(shí)現(xiàn)棋盤覆蓋算法利用的算法是A分治法B動(dòng)態(tài)規(guī)劃法10、矩陣連乘問題的算法可由

3、 B 。DC歸并排序。貪心法。C貪心法設(shè)計(jì)實(shí)現(xiàn)。C貪心算法0/1 背包問題ACD回溯法D回溯法A分支界限算法B動(dòng)態(tài)規(guī)劃算法11、實(shí)現(xiàn)大整數(shù)的乘法是利用的算法A貪心法B動(dòng)態(tài)規(guī)劃法12、最長公共子序列算法利用的算法是A分支界限法B動(dòng)態(tài)規(guī)劃法13、以下算法中通常以自底向上的方式求解最優(yōu)解的是A備忘錄法B動(dòng)態(tài)規(guī)劃法14、以下是動(dòng)態(tài)規(guī)劃算法根本要素的是A定義最優(yōu)解B構(gòu)造最優(yōu)解15、以下不是動(dòng)態(tài)規(guī)劃算法根本步驟的是A找出最優(yōu)解的解空間B構(gòu)造最優(yōu)解16、能采用貪心算法求最優(yōu)解的問題，一A最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì) C最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)17、下面問題 B 不能使用貪心法解決。A單源最短路徑問題B

4、C最小花費(fèi)生成樹問題D18、以下不可以使用分治法求解的是D 。A棋盤覆蓋問題B選擇問題。C分治策略B 。 C 貪心法BC貪心法D 。C算出最優(yōu)解A 。C算出最優(yōu)解D回溯算法D回溯法D 。DD回溯法回溯法子問題重疊性質(zhì)D定義最優(yōu)解A 般具有的重要性質(zhì)為： B重疊子問題性質(zhì)與貪心選擇性質(zhì)D預(yù)排序與遞歸調(diào)用N皇后問題背包問題C歸并排序D 0/1 背包問題A分治法B動(dòng)態(tài)規(guī)劃法C貪心法D回溯法20、 以下算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是D 。A備忘錄法B動(dòng)態(tài)規(guī)劃法C貪心法D回溯法21、 下面哪種函數(shù)是回溯法中為防止無效搜索采取的策略B A遞歸函數(shù)B剪枝函數(shù)C隨機(jī)數(shù)函數(shù) D搜索函數(shù)22、 回溯法

5、在問題的解空間樹中，按D 策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。A廣度優(yōu)先B活結(jié)點(diǎn)優(yōu)先C擴(kuò)展結(jié)點(diǎn)優(yōu)先D深度優(yōu)先23、回溯法的效率不依賴于以下哪些因素 A . 滿足顯約束的值的個(gè)數(shù) C計(jì)算限界函數(shù)的時(shí)間24、回溯法解 0-1 背包問題時(shí)的解空間樹是A子集樹B排列樹生成樹25、回溯法解旅行售貨員問題時(shí)的解空間樹是A子集樹B排列樹D。B計(jì)算約束函數(shù)的時(shí)間D 確定解空間的時(shí)間A。 C深度優(yōu)先生成樹D廣度優(yōu)先B。 C深度優(yōu)先生成樹D廣度優(yōu)先生成樹26、一個(gè)問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的B 。A分支界限算法B動(dòng)態(tài)規(guī)劃算法C貪心算法30、貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是B 。A最優(yōu)子結(jié)構(gòu)B

6、貪心選擇性質(zhì)C構(gòu)造最優(yōu)解D回溯算法D定義最優(yōu)解A重疊子問題B最優(yōu)子結(jié)構(gòu)性質(zhì)C貪心選擇性質(zhì)D定義最優(yōu)解27、以下算法中不能解決0/1 背包問題的是A A貪心法B動(dòng)態(tài)規(guī)劃C回溯法D分支限界法28、下面問題 B 不能使用貪心法解決。A單源最短路徑問題BN皇后問題C最小生成樹問題D背包問題29、矩陣連乘問題的算法可由B 設(shè)計(jì)實(shí)現(xiàn)。、簡答題1. 算法重要特性是什么？2. 算法分析的目的是什么？3. 算法的時(shí)間復(fù)雜性與問題的什么因素相關(guān)？4. 算法的漸進(jìn)時(shí)間復(fù)雜性的含義？5. 最壞情況下的時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性有什么不同？6. 簡述二分檢索折半查找算法的根本過程。7. 背包問題的目標(biāo)函數(shù)和貪心算法最優(yōu)

7、化量度相同嗎？8. 采用回溯法求解的問題，其解如何表示？有什么規(guī)定？9. 回溯法的搜索特點(diǎn)是什么？10. n 皇后問題回溯算法的判別函數(shù) place 的根本流程是什么？11. 為什么用分治法設(shè)計(jì)的算法一般有遞歸調(diào)用？12. 為什么要分析最壞情況下的算法時(shí)間復(fù)雜性？13. 簡述漸進(jìn)時(shí)間復(fù)雜性上界的定義。14. 二分檢索算法最多的比擬次數(shù)？15. 快速排序算法最壞情況下需要多少次比擬運(yùn)算？16. 貪心算法的根本思想？17. 回溯法的解Xi,X2,Xn的隱約束一般指什么？18. 闡述合并排序的分治思路。19. 快速排序的根本思想是什么。20. 什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)

8、？21. 試述分治法的根本思想。22. 設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法有哪些主要步驟？23. 分治法與動(dòng)態(tài)規(guī)劃法的異同？24. 備忘錄方法和動(dòng)態(tài)規(guī)劃算法相比有何異同？簡述之。參考答案：1. 輸入、輸出、確定性、有限性、可實(shí)現(xiàn)性。2. 分析算法占用電腦資源的情況，對算法做出比擬和評價(jià)，設(shè)計(jì)出更好的算法。3. 算法的時(shí)間復(fù)雜性與問題的規(guī)模相關(guān)，是問題大小 n 的函數(shù)。4當(dāng)問題的規(guī)模 n 趨向無窮大時(shí)，影響算法效率的重要因素是 T(n) 的數(shù)量級，而其他因素僅 是使時(shí)間復(fù)雜度相差常數(shù)倍，因此可以用T(n) 的數(shù)量級 (階) 評價(jià)算法。時(shí)間復(fù)雜度 T(n)的數(shù)量級 ( 階)稱為漸進(jìn)時(shí)間復(fù)雜性。5. 最壞情況下的時(shí)間

9、復(fù)雜性和平均時(shí)間復(fù)雜性考察的是 n 固定時(shí)，不同輸入實(shí)例下的算法所 耗時(shí)間。最壞情況下的時(shí)間復(fù)雜性取的輸入實(shí)例中最大的時(shí)間復(fù)雜度：W(n) = max T(n , I) , I Dn平均時(shí)間復(fù)雜性是所有輸入實(shí)例的處理時(shí)間與各自概率的乘積和：A(n)=刀 PT(n ,1) I Dn6. 設(shè)輸入是一個(gè)按非降次序排列的元素表Ai : j和x，選取A(i+j)/2 與x比擬，如果A(i+j)/2=x ，那么返回(i+j)/2 ，如果 A(i+j)/2<x ，貝U Ai : (i+j)/2-1 找 x，否那么在 A (i+j)/2+1: j找x。上述過程被反復(fù)遞歸調(diào)用。7. 不相同。目標(biāo)函數(shù)：獲得

10、最大利潤。最優(yōu)量度：最大利潤 / 重量比。8. 問題的解可以表示為 n元組：xi,x2, Xn，Xi S, S為有窮集合，Xi S, xi,x 2, xn具備完備性，即X1,x 2, xn是合理的，那么X1,x 2, x(i<n) 定合理。9. 在解空間樹上跳躍式地深度優(yōu)先搜索,即用判定函數(shù)考察xk 的取值,如果 xk 是合理的就搜索 xk 為根節(jié)點(diǎn)的子樹,如果 xk 取完了所有的值,便回溯到 xk-1 。10. 將第K行的皇后分別與前 k-1行的皇后比擬，看是否與它們相容，如果不相容就返回false , 測試完畢那么返回 true 。1 1 .子問題的規(guī)模還很大時(shí),必須繼續(xù)使用分治法,

11、反復(fù)分治,必然要用到遞歸。12. 最壞情況下的時(shí)間復(fù)雜性決定算法的優(yōu)劣,并且最壞情況下的時(shí)間復(fù)雜性較平均時(shí)間復(fù)雜 性游可操作性。13. T(n)是某算法的時(shí)間復(fù)雜性函數(shù)，f(n)是一簡單函數(shù)，存在正整數(shù)No和C, nNo,有T(n)<f(n) ,這種關(guān)系記作 T(n)=O(f(n)。14. 二分檢索算法的最多的比擬次數(shù)為 log n 。15. 最壞情況下快速排序退化成冒泡排序，需要比擬n2次。16. 是一種依據(jù)最優(yōu)化量度依次選擇輸入的分級處理方法。根本思路是：首先根據(jù)題意,選取 一種 量度標(biāo)準(zhǔn)；然后 按這種量度標(biāo)準(zhǔn)對這 n 個(gè)輸入排序,依次選擇輸入量參加局部解中。 如果當(dāng)前這個(gè)輸入量的參

12、加,不滿足約束條件,那么不把此輸入加到這局部解中。17. 回溯法的解X1,X2,Xn的隱約束一般指個(gè)元素之間應(yīng)滿足的某種關(guān)系。18. 講數(shù)組一分為二，分別對每個(gè)集合單獨(dú)排序，然后將已排序的兩個(gè)序列歸并成一個(gè)含n個(gè)元素的分好類的序列。如果分割后子問題還很大,那么繼續(xù)分治,直到一個(gè)元素。19. 快速排序的根本思想是在待排序的N個(gè)記錄中任意取一個(gè)記錄， 把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩局部。所有關(guān)鍵字比該記錄關(guān)鍵字小的放在前一局部，所有比它 大的放置在后一局部，并把該記錄排在這兩局部的中間，這個(gè)過程稱作一次快速排序。之 后重復(fù)上述過程，直到每一局部內(nèi)只有一個(gè)記錄為止。20. 在定義一個(gè)

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