算法分析復(fù)習(xí)題含答案

一、選擇題1、衡量一種算法好壞的原則是（C）。（A）運(yùn)行速度快（B）占用空間少（C）時(shí)間復(fù)雜度低（D）代碼短2、記號(hào)O的定義對(duì)的的是（A）。（A）O(g(n))={f(n)|存在正常數(shù)c和n0使得對(duì)全部nn0有：0f(n)cg(n)}；（B）O(g(n))={f(n)|存在正常數(shù)c和n0使得對(duì)全部nn0有：0cg(n)f(n)}；（C）O(g(n))={f(n)|對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)全部nn0有：0f(n)<cg(n)}；（D）O(g(n))={f(n)|對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)全部nn0有：0cg(n)<f(n)}；3、二分搜索算法是運(yùn)用（A）實(shí)現(xiàn)的算法。（A）分治方略（B）動(dòng)態(tài)規(guī)劃法（C）貪心法（D）回溯法4、使用分治法求解不需要滿足的條件是（A）。（A）子問題必須是同樣的（B）子問題不能夠重復(fù)（C）子問題的解能夠合并（D）原問題和子問題使用相似的辦法解5、合并排序算法是運(yùn)用（

A）實(shí)現(xiàn)的算法。（A）分治方略 （B）動(dòng)態(tài)規(guī)劃法 （C）貪心法 （D）回溯法6、實(shí)現(xiàn)大整數(shù)的乘法是運(yùn)用（C）的算法。（A）貪心法 （B）動(dòng)態(tài)規(guī)劃法 （C）分治方略 （D）回溯法7、下列不能夠使用分治法求解的是（D）。（A）棋盤覆蓋問題（B）選擇問題（C）歸并排序（D）0/1背包問題8、實(shí)現(xiàn)循環(huán)賽日程表運(yùn)用的算法是（A）。（A）分治方略 （B）動(dòng)態(tài)規(guī)劃法 （C）貪心法 （D）回溯法9、實(shí)現(xiàn)棋盤覆蓋算法運(yùn)用的算法是（A）。（A）分治法 （B）動(dòng)態(tài)規(guī)劃法 （C）貪心法 （D）回溯法10、矩陣連乘問題的算法可由（B）設(shè)計(jì)實(shí)現(xiàn)。（A）分支界限算法（B）動(dòng)態(tài)規(guī)劃算法（C）貪心算法（D）回溯算法11、實(shí)現(xiàn)大整數(shù)的乘法是運(yùn)用的算法（C）。（A）貪心法 （B）動(dòng)態(tài)規(guī)劃法 （C）分治方略 （D）回溯法12、最長(zhǎng)公共子序列算法運(yùn)用的算法是（

B

）。（A）分支界限法（B）動(dòng)態(tài)規(guī)劃法（C）貪心法（D）回溯法13、下列算法中普通以自底向上的方式求解最優(yōu)解的是（B）。（A）備忘錄法 （B）動(dòng)態(tài)規(guī)劃法 （C）貪心法 （D）回溯法14、下列是動(dòng)態(tài)規(guī)劃算法基本要素的是（

D

）。（A）定義最優(yōu)解（B）構(gòu)造最優(yōu)解（C）算出最優(yōu)解（D）子問題重疊性質(zhì)15、下列不是動(dòng)態(tài)規(guī)劃算法基本環(huán)節(jié)的是（A）。（A）找出最優(yōu)解的解空間（B）構(gòu)造最優(yōu)解（C）算出最優(yōu)解（D）定義最優(yōu)解16、能采用貪心算法求最優(yōu)解的問題，普通含有的重要性質(zhì)為：（A）（A）最優(yōu)子構(gòu)造性質(zhì)與貪心選擇性質(zhì)（B）重疊子問題性質(zhì)與貪心選擇性質(zhì)（C）最優(yōu)子構(gòu)造性質(zhì)與重疊子問題性質(zhì)（D）預(yù)排序與遞歸調(diào)用17、下面問題（B）不能使用貪心法解決。（A）單源最短途徑問題 （B）N皇后問題（C）最小耗費(fèi)生成樹問題 （D）背包問題18、下列不能夠使用分治法求解的是（D）。（A）棋盤覆蓋問題（B）選擇問題（C）歸并排序（D）0/1背包問題19、備忘錄辦法是那種算法的變形（

B

）。（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、回溯法在問題的解空間樹中，按（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、回溯法的效率不依賴于下列哪些因素（

D

）。（A）.滿足顯約束的值的個(gè)數(shù)

（B）計(jì)算約束函數(shù)的時(shí)間

（C）

計(jì)算限界函數(shù)的時(shí)間

（D）

擬定解空間的時(shí)間24、回溯法解0-1背包問題時(shí)的解空間樹是（

A

）。

（A）子集樹

（B）排列樹

（C）深度優(yōu)先生成樹

（D）廣度優(yōu)先生成樹

25、回溯法解旅行售貨員問題時(shí)的解空間樹是（

B

）。

（A）子集樹

（B）排列樹

（C）深度優(yōu)先生成樹

（D）廣度優(yōu)先生成樹

26、一種問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的核心特性是問題的（B）。（A）重疊子問題（B）最優(yōu)子構(gòu)造性質(zhì)（C）貪心選擇性質(zhì)（D）定義最優(yōu)解27、下列算法中不能解決0/1背包問題的是（A）（A）貪心法（B）動(dòng)態(tài)規(guī)劃（C）回溯法（D）分支限界法28、下面問題（B）不能使用貪心法解決。（A）單源最短途徑問題（B）N皇后問題（C）最小生成樹問題（D）背包問題29、矩陣連乘問題的算法可由（B）設(shè)計(jì)實(shí)現(xiàn)。（A）分支界限算法（B）動(dòng)態(tài)規(guī)劃算法（C）貪心算法（D）回溯算法30、貪心算法與動(dòng)態(tài)規(guī)劃算法的重要區(qū)別是（

B

）。（A）最優(yōu)子構(gòu)造（B）貪心選擇性質(zhì)（C）構(gòu)造最優(yōu)解（D）定義最優(yōu)解二、簡(jiǎn)答題算法重要特性是什么？算法分析的目的是什么？算法的時(shí)間復(fù)雜性與問題的什么因素有關(guān)？算法的漸進(jìn)時(shí)間復(fù)雜性的含義？最壞狀況下的時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性有什么不同？簡(jiǎn)述二分檢索（折半查找）算法的基本過程。背包問題的目的函數(shù)和貪心算法最優(yōu)化量度相似嗎？采用回溯法求解的問題，其解如何表達(dá)？有什么規(guī)定？回溯法的搜索特點(diǎn)是什么？n皇后問題回溯算法的鑒別函數(shù)place的基本流程是什么？為什么用分治法設(shè)計(jì)的算法普通有遞歸調(diào)用？為什么要分析最壞狀況下的算法時(shí)間復(fù)雜性？簡(jiǎn)述漸進(jìn)時(shí)間復(fù)雜性上界的定義。二分檢索算法最多的比較次數(shù)？快速排序算法最壞狀況下需要多少次比較運(yùn)算？貪心算法的基本思想？回溯法的解（x1,x2,……xn）的隱約束普通指什么？敘述合并排序的分治思路?？焖倥判虻幕舅枷胧鞘裁础Ｊ裁词侵苯舆f歸和間接遞歸？消除遞歸普通要用到什么數(shù)據(jù)構(gòu)造？試述分治法的基本思想。設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法有哪些重要環(huán)節(jié)？分治法與動(dòng)態(tài)規(guī)劃法的異同？備忘錄辦法和動(dòng)態(tài)規(guī)劃算法相比有何異同？簡(jiǎn)述之。參考答案：1.輸入、輸出、擬定性、有限性、可實(shí)現(xiàn)性。2.分析算法占用計(jì)算機(jī)資源的狀況，對(duì)算法做出比較和評(píng)價(jià)，設(shè)計(jì)出更加好的算法。3.算法的時(shí)間復(fù)雜性與問題的規(guī)模有關(guān)，是問題大小n的函數(shù)。4．當(dāng)問題的規(guī)模n趨向無窮大時(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ù)雜性。5.最壞狀況下的時(shí)間復(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)=∑P(I)T(n，I)I∈Dn6.設(shè)輸入是一種按非降次序排列的元素表A[i：j]和x，選用A[(i+j)/2]與x比較，如果A[(i+j)/2]=x，則返回(i+j)/2，如果A[(i+j)/2]<x，則A[i：(i+j)/2-1]找x，否則在A[(i+j)/2+1：j]找x。上述過程被重復(fù)遞歸調(diào)用。7.不相似。目的函數(shù)：獲得最大利潤(rùn)。最優(yōu)量度：最大利潤(rùn)/重量比。8.問題的解能夠表達(dá)為n元組：（x1,x2,……xn），xi∈Si,Si為有窮集合，xi∈Si,（x1,x2,……xn）含有完備性，即（x1,x2,……xn）是合理的，則（x1,x2,……xi）(i<n)一定合理。9.在解空間樹上跳躍式地深度優(yōu)先搜索，即用鑒定函數(shù)考察x[k]的取值，如果x[k]是合理的就搜索x[k]為根節(jié)點(diǎn)的子樹，如果x[k]取完了全部的值，便回溯到x[k-1]。10.將第K行的皇后分別與前k-1行的皇后比較，看與否與它們相容，如果不相容就返回false，測(cè)試完畢則返回true。11.子問題的規(guī)模還很大時(shí)，必須繼續(xù)使用分治法，重復(fù)分治，必然要用到遞歸。12.最壞狀況下的時(shí)間復(fù)雜性決定算法的優(yōu)劣，并且最壞狀況下的時(shí)間復(fù)雜性較平均時(shí)間復(fù)雜性游可操作性。13.T(n)是某算法的時(shí)間復(fù)雜性函數(shù)，f(n)是一簡(jiǎn)樸函數(shù)，存在正整數(shù)No和C，n〉No，有T(n)<f(n)，這種關(guān)系記作T(n)=O(f(n))。14.二分檢索算法的最多的比較次數(shù)為logn。15.最壞狀況下快速排序退化成冒泡排序，需要比較n2次。16.是一種根據(jù)最優(yōu)化量度依次選擇輸入的分級(jí)解決辦法?；舅悸肥牵菏紫雀鶕?jù)題意，選用一種量度原則；然后按這種量度原則對(duì)這n個(gè)輸入排序，依次選擇輸入量加入部分解中。如果現(xiàn)在這個(gè)輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。17.回溯法的解（x1,x2,……xn）的隱約束普通指?jìng)€(gè)元素之間應(yīng)滿足的某種關(guān)系。18.講數(shù)組一分為二，分別對(duì)每個(gè)集合單獨(dú)排序，然后將已排序的兩個(gè)序列歸并成一種含n個(gè)元素的分好類的序列。如果分割后子問題還很大，則繼續(xù)分治，直到一種元素。19.快速排序的基本思想是在待排序的N個(gè)統(tǒng)計(jì)中任意取一種統(tǒng)計(jì)，把該統(tǒng)計(jì)放在最后位置后，數(shù)據(jù)序列被此統(tǒng)計(jì)分成兩部分。全部核心字比該統(tǒng)計(jì)核心字小的放在前一部分，全部比它大的放置在后一部分，并把該統(tǒng)計(jì)排在這兩部分的中間，這個(gè)過程稱作一次快速排序。之后重復(fù)上述過程，直到每一部分內(nèi)只有一種統(tǒng)計(jì)為止。20.在定義一種過程或者函數(shù)的時(shí)候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成分，既調(diào)用它自己本身，這稱為直接遞歸。如果過程或者函數(shù)P調(diào)用過程或者函數(shù)Q，Q又調(diào)用P，這個(gè)稱為間接遞歸。消除遞歸普通要用到棧這種數(shù)據(jù)構(gòu)造。21.分治法的基本思想是將一種規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相似。遞歸地解這些子問題，然后將各個(gè)子問題的解合并得到原問題的解。22.設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的重要環(huán)節(jié)為：（1）找出最優(yōu)解的性質(zhì)，并刻劃其構(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)是：將待求解的問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。兩者的不同點(diǎn)是：適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。而用分治法求解的問