(完整word版)算法分析復(fù)習(xí)題(含答案)(word文檔良心出品)

1、一、選擇題1、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（A）運(yùn)行速度快（B）占用空間少2、記號(hào)0的定義正確的是（A）（B）（C）C )。（A）。存在正常數(shù)存在正常數(shù)（C）時(shí)間復(fù)雜度低（D）代碼短c和n0使得對(duì)所有n n0有：0 n0有：0 0，存在正數(shù)和O（g（ n） = f（n） |O（g（ n） = f（n） |O（g（ n） = f（n） |有：0 f（n）0，存在正數(shù)和有：0 蘭 cg（n） 0使得對(duì)所有 cg(n) 0使得對(duì)所有nn0）實(shí)現(xiàn)的算法。（C）貪心法A ）?；厮莘ǎ˙）子問(wèn)題不能夠重復(fù)（D）原問(wèn)題和子問(wèn)題使用相同的方法解 ）實(shí)現(xiàn)的算法。動(dòng)態(tài)規(guī)劃法C ）的算法。動(dòng)態(tài)規(guī)劃法D（C）貪心法（C）

2、分治策略(D)(D)回溯法回溯法7、以下不可以使用分治法求解的是（A）棋盤覆蓋問(wèn)題（B）選擇問(wèn)題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、矩陣連乘問(wèn)題的算法可由（C）歸并排序）。貪心法）。（C）貪心法0/1背包問(wèn)題(D回溯法(D)回溯法（A）分支界限算法（B）動(dòng)態(tài)規(guī)劃算法11、實(shí)現(xiàn)大整數(shù)的乘法是利用的算法（A）貪心法（B）動(dòng)態(tài)規(guī)劃法12、最長(zhǎng)公共子序列算法利用的算法是（A）分支界限法（B）動(dòng)態(tài)規(guī)劃法B ）設(shè)計(jì)實(shí)現(xiàn)。（C）貪心算法）。（C）分治策略B ）。（C ）貪心法B13、下列算法中通常以自底向上的方式求解

3、最優(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)解的問(wèn)題，一（A）最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)（C）最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問(wèn)題性質(zhì)（C）貪心法D ）。（C）算出最優(yōu)解A ）。（C算出最優(yōu)解(D)回溯算法（D）回溯法(D)。(D)回溯法回溯法子問(wèn)題重疊性質(zhì)（D）定義最優(yōu)解A ）般具有的重要性質(zhì)為：（B）重疊子問(wèn)題性質(zhì)與貪心選擇性質(zhì)（D）預(yù)排序與遞歸調(diào)用17、下面問(wèn)題（B ）不能使用貪心法解決。（A）單源最短路徑問(wèn)題（B）（C）最小花費(fèi)

4、生成樹問(wèn)題（D）18、以下不可以使用分治法求解的是（ D ）。（A）棋盤覆蓋問(wèn)題（B）選擇問(wèn)題N皇后問(wèn)題 背包問(wèn)題（C）歸并排序（D） 0/1背包問(wèn)題219、 備忘錄方法是那種算法的變形（B ）。（A）分治法（B）動(dòng)態(tài)規(guī)劃法20、下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的是（A）備忘錄法（B）動(dòng)態(tài)規(guī)劃法（C）貪心法21、下面哪種函數(shù)是回溯法中為避免無(wú)效搜索采取的策略（A）遞歸函數(shù)（B）剪枝函數(shù)22、回溯法在問(wèn)題的解空間樹中，按（A）廣度優(yōu)先（B）活結(jié)點(diǎn)優(yōu)先23、回溯法的效率不依賴于下列哪些因素（A）.滿足顯約束的值的個(gè)數(shù) （ C） 計(jì)算限界函數(shù)的時(shí)間（C）貪心法D（C）隨機(jī)數(shù)函數(shù)（D）回溯法

5、D）D)）?；厮莘ǎ┧阉骱瘮?shù)24、回溯法解 0-1 背包問(wèn)題時(shí)的解空間樹是（A）子集樹（B）排列樹生成樹25、回溯法解旅行售貨員問(wèn)題時(shí)的解空間樹是（A）子集樹（B）排列樹生成樹D ）策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。（C擴(kuò)展結(jié)點(diǎn)優(yōu)先（D）深度優(yōu)先D（B）計(jì)算約束函數(shù)的時(shí)間D） 確定解空間的時(shí)間A（C）。）。深度優(yōu)先生成樹（D）廣度優(yōu)先BC)）。深度優(yōu)先生成樹（D）廣度優(yōu)先26、一個(gè)問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問(wèn)題的（A）重疊子問(wèn)題 （B）27、下列算法中不能解決（A）貪心法（B）28、下面問(wèn)題（ B ）（A）單源最短路徑問(wèn)題29、矩陣連乘問(wèn)題的算法可由（A）分支界限算法（B）動(dòng)

6、態(tài)規(guī)劃算法30、貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是（A）最優(yōu)子結(jié)構(gòu)（B）貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)（C）貪心選擇性質(zhì)0/1 背包問(wèn)題的是（ A ）動(dòng)態(tài)規(guī)劃（C）回溯法不能使用貪心法解決。（B） N皇后問(wèn)題（C）最小生成樹問(wèn)題B ）設(shè)計(jì)實(shí)現(xiàn)。（C）貪心算法 B ）。（C）構(gòu)造最優(yōu)解D)）。B定義最優(yōu)解分支限界法（D背包問(wèn)題（D）回溯算法（D）定義最優(yōu)解二、簡(jiǎn)答題1.2.3.4.5.6.算法重要特性是什么？ 算法分析的目的是什么？ 算法的時(shí)間復(fù)雜性與問(wèn)題的什么因素相關(guān)？ 算法的漸進(jìn)時(shí)間復(fù)雜性的含義？ 最壞情況下的時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性有什么不同？ 簡(jiǎn)述二分檢索（折半查找）算法的基本過(guò)程。 背包

7、問(wèn)題的目標(biāo)函數(shù)和貪心算法最優(yōu)化量度相同嗎？ 采用回溯法求解的問(wèn)題，其解如何表示？有什么規(guī)定？ 回溯法的搜索特點(diǎn)是什么？7.8.9.10. n 皇后問(wèn)題回溯算法的判別函數(shù) place 的基本流程是什么？11. 為什么用分治法設(shè)計(jì)的算法一般有遞歸調(diào)用？12. 為什么要分析最壞情況下的算法時(shí)間復(fù)雜性？13. 簡(jiǎn)述漸進(jìn)時(shí)間復(fù)雜性上界的定義。 二分檢索算法最多的比較次數(shù)？ 快速排序算法最壞情況下需要多少次比較運(yùn)算？ 貪心算法的基本思想？15.14.16.417.18.19.20.21.22.23.24.回溯法的解(Xi,X 2, Xn)的隱約束一般指什么？ 闡述合并排序的分治思路?？焖倥判虻幕舅枷胧鞘?/p>

8、么。什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？ 試述分治法的基本思想。設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法有哪些主要步驟？ 分治法與動(dòng)態(tài)規(guī)劃法的異同？ 備忘錄方法和動(dòng)態(tài)規(guī)劃算法相比有何異同？簡(jiǎn)述之。6參考答案:輸入、輸出、確定性、有限性、可實(shí)現(xiàn)性。 分析算法占用計(jì)算機(jī)資源的情況,對(duì)算法做出比較和評(píng)價(jià),設(shè)計(jì)出更好的算法。算法的時(shí)間復(fù)雜性與問(wèn)題的規(guī)模相關(guān)，是問(wèn)題大小n的函數(shù)。當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，影響算法效率的重要因素是T(n)的數(shù)量級(jí)，而其他因素僅是使時(shí)間復(fù)雜度相差常數(shù)倍,因此可以用 T(n) 的數(shù)量級(jí) (階)評(píng)價(jià)算法。時(shí)間復(fù)雜度 T(n) 的數(shù)量級(jí) (階)稱為漸進(jìn)時(shí)間復(fù)雜性。最壞情況下的時(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 Dn設(shè)輸入是一個(gè)按非降次序排列的元素表 Ai : j 和A(i+j)/2=x ,則返回 (i+j)/2 ,如果 A(i+j)/2xA (i+j)/2+1: j找x。上述過(guò)程被反復(fù)遞歸調(diào)用。不相同。目標(biāo)函數(shù)：獲得最大利潤(rùn)。最優(yōu)量度：最大利潤(rùn)1.2.3.45.6.7.8.9.x，選取 A(i+j)/2 與x比較，如果 ，貝y

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

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

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

13、程或者函數(shù)的時(shí)候又出現(xiàn)了調(diào)用本過(guò)程或者函數(shù)的成分，既調(diào)用它自己本身，這稱為直接遞歸。如果過(guò)程或者函數(shù)P調(diào)用過(guò)程或者函數(shù) Q Q又調(diào)用P,這個(gè)稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)。21. 分治法的基本思想是將一個(gè)規(guī)模為 n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相 獨(dú)立且與原問(wèn)題相同。 遞歸地解這些子問(wèn)題， 然后將各個(gè)子問(wèn)題的解合并得到原問(wèn)題的解。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)是：將待求解的問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題， 然后從這些子問(wèn)題的解得到原問(wèn)題的解。兩者的不同點(diǎn)是：適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú) 立的。而用分治法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往是互相獨(dú)立的。24. 備忘錄方法是動(dòng)態(tài)規(guī)劃算法的變