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

1、1一、選擇題1、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（C）。（A）運(yùn)行速度快（B）占用空間少（C）時(shí)間復(fù)雜度低（D）代碼短2、記號(hào)O的定義正確的是（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ù)c0，存在正數(shù)和n00使得對(duì)所有nn0?有：0f(n)0

2、，存在正數(shù)和n00使得對(duì)所有nn0?有：0cg(n)f(n)；?3、二分搜索算法是利用（A）實(shí)現(xiàn)的算法。（A）分治策略（B）動(dòng)態(tài)規(guī)劃法（C）貪心法（D）回溯法4、使用分治法求解不需要滿足的條件是（A）。（A）子問(wèn)題必須是一樣的（B）子問(wèn)題不能夠重復(fù)（C）子問(wèn)題的解可以合并（D）原問(wèn)題和子問(wèn)題使用相同的方法解5、合并排序算法是利用（A）實(shí)現(xiàn)的算法。（A）分治策略（B）動(dòng)態(tài)規(guī)劃法（C）貪心法（D）回溯法6、實(shí)現(xiàn)大整數(shù)的乘法是利用（C）的算法

3、。（A）貪心法（B）動(dòng)態(tài)規(guī)劃法（C）分治策略（D）回溯法7、以下不可以使用分治法求解的是（D）。（A）棋盤覆蓋問(wèn)題（B）選擇問(wèn)題（C）歸并排序（D）01背包問(wèn)題8、實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（A）。（A）分治策略（B）動(dòng)態(tài)規(guī)劃法（C）貪心法（D）回溯法9、實(shí)現(xiàn)棋盤覆蓋算法利用的算法是（A）。（A）分治法（B）動(dòng)態(tài)規(guī)劃法（C）貪心法（D）回溯法10、矩陣連乘問(wèn)題的算法可由（B）設(shè)計(jì)實(shí)現(xiàn)。（A）分支界限算法（B）動(dòng)態(tài)規(guī)劃算法（C）貪心算法

4、（D）回溯算法11、實(shí)現(xiàn)大整數(shù)的乘法是利用的算法（C）。（A）貪心法（B）動(dòng)態(tài)規(guī)劃法（C）分治策略（D）回溯法12、最長(zhǎng)公共子序列算法利用的算法是（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）子問(wèn)題重疊性質(zhì)15、

5、下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（A）。（A）找出最優(yōu)解的解空間（B）構(gòu)造最優(yōu)解（C）算出最優(yōu)解（D）定義最優(yōu)解16、能采用貪心算法求最優(yōu)解的問(wèn)題，一般具有的重要性質(zhì)為：（A）（A）最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)（B）重疊子問(wèn)題性質(zhì)與貪心選擇性質(zhì)（C）最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問(wèn)題性質(zhì)（D）預(yù)排序與遞歸調(diào)用17、下面問(wèn)題（B）不能使用貪心法解決。（A）單源最短路徑問(wèn)題（B）N皇后問(wèn)題（C）最小花費(fèi)生成樹問(wèn)題（D）背包問(wèn)題315.快速排序算法最

6、壞情況下需要多少次比較運(yùn)算？16.貪心算法的基本思想？17.回溯法的解（x1x2……xn）的隱約束一般指什么？18.闡述合并排序的分治思路。19.快速排序的基本思想是什么。20.什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？21.試述分治法的基本思想。22.設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法有哪些主要步驟？23.分治法與動(dòng)態(tài)規(guī)劃法的異同？24.備忘錄方法和動(dòng)態(tài)規(guī)劃算法相比有何異同？簡(jiǎn)述之。參考答案：參考答案：1.輸入、輸出、確定性、有限性、可

7、實(shí)現(xiàn)性。2.分析算法占用計(jì)算機(jī)資源的情況，對(duì)算法做出比較和評(píng)價(jià)，設(shè)計(jì)出更好的算法。3.算法的時(shí)間復(fù)雜性與問(wèn)題的規(guī)模相關(guān)，是問(wèn)題大小n的函數(shù)。4當(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ù)雜性。5.最壞情況下的時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性考察的是n固定時(shí)，不同輸入實(shí)例下的算法所耗時(shí)間。最壞情

8、況下的時(shí)間復(fù)雜性取的輸入實(shí)例中最大的時(shí)間復(fù)雜度：W(n)=maxT(n，I)I∈Dn平均時(shí)間復(fù)雜性是所有輸入實(shí)例的處理時(shí)間與各自概率的乘積和：A(n)=∑P(I)T(n，I)I∈Dn6.設(shè)輸入是一個(gè)按非降次序排列的元素表A[i：j]和x，選取A[(ij)2]與x比較，如果A[(ij)2]=x，則返回(ij)2，如果A[(ij)2]x，則A[i：(ij)21]找x，否則在A[(ij)21：j]找x。上述過(guò)程被反復(fù)遞歸調(diào)用。7.不相同。目標(biāo)

9、函數(shù)：獲得最大利潤(rùn)。最優(yōu)量度：最大利潤(rùn)重量比。8.問(wèn)題的解可以表示為n元組：（x1x2……xn），xi∈SiSi為有窮集合，xi∈Si（x1x2……xn）具備完備性，即（x1x2……xn）是合理的，則（x1x2……xi）(in)一定合理。9.在解空間樹上跳躍式地深度優(yōu)先搜索，即用判定函數(shù)考察x[k]的取值，如果x[k]是合理的就搜索x[k]為根節(jié)點(diǎn)的子樹，如果x[k]取完了所有的值，便回溯到x[k1]。10.將第K行的皇后分別與前k1行

10、的皇后比較，看是否與它們相容，如果不相容就返回false，測(cè)試完畢則返回true。11.子問(wèn)題的規(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ù)為