算法設(shè)計(jì)分析第2次

1、第2次作業(yè)一、單項(xiàng)選擇題(本大題共60分，共20小題，每小題3分)1.一個(gè)長(zhǎng)度為n英寸的鋼管的最優(yōu)切割問(wèn)題，總共有多少個(gè)不同的子問(wèn)題?A. n+1 B.n2C.nlognD.logn2 .實(shí)現(xiàn)快速排序算法如下：Quicksort (A, p, r)IF p < rTHEN q Partition(A, p, r)()QuickSort(A, q+1, r)A. quickSort(p,q-1)B. quickSort(p+1,q-1)C. quickSort(p,q+1)D. quickSort(p,q-2)3 .在鋼管切割問(wèn)題里，我們用如下遞歸表達(dá)式表達(dá)原問(wèn)題的最優(yōu)解的最優(yōu)值:% =

2、max (pi + %/) 口口請(qǐng)問(wèn)，其中的i是指什么？()A. 1英寸鋼管的價(jià)值B.子問(wèn)題的鋼管長(zhǎng)度C.第一刀所切割的鋼管長(zhǎng)度D.價(jià)值/長(zhǎng)度比4. 在最優(yōu)二叉搜索樹(shù)問(wèn)題中，我們的優(yōu)化目標(biāo)是()。A.只經(jīng)過(guò)最少次數(shù)的比較就可以找到概率最大的元素B.經(jīng)過(guò)最多次數(shù)的比較就可以找到概率最小的元素C.找到每個(gè)元素所需要的平均比較次數(shù)為最小D.元素搜索代價(jià)的數(shù)學(xué)期望為最小5. Edmonds-Karp算法中尋找增廣路徑的方法是（A.深度優(yōu)先算法B.廣度優(yōu)先算法C. Prim算法D. Dijkstra 算法6.關(guān)于0,1背包問(wèn)題的下述形式化公式描述：max耀3=1f=lxt.三0.1 J M下述說(shuō)法不正確

3、的是（）。A. i 表小物品的重量B. C表示背包容量C. xi=0表示編號(hào)為i的物品不被選擇D.求解目標(biāo)是最大化裝入背包內(nèi)的物品的總價(jià)值7 .在活動(dòng)安排問(wèn)題中，如果把全部活動(dòng)按照結(jié)束時(shí)間遞增序排序后，按貪心算 法，我們總是安排 （）。A.當(dāng)前可選活動(dòng)中結(jié)束時(shí)間最早的活動(dòng)8 .當(dāng)前可選活動(dòng)中開(kāi)始時(shí)間最早的活動(dòng)C.當(dāng)前可選活動(dòng)中沖突數(shù)量最少的活動(dòng)D.當(dāng)前可選活動(dòng)中持續(xù)時(shí)間最長(zhǎng)的活動(dòng)8.0,0 1 < ->_找零錢(qián)問(wèn)題中，定義Cj為兌換j所需要的硬幣的最少數(shù)量，考慮下述遞歸 表達(dá)式,XCj =01 + rnrn Cj - l<l<k卜列關(guān)于對(duì)i的尋優(yōu)的最恰當(dāng)描述是（A.考慮

4、找出的第一個(gè)硬幣面值的各種可能性B.考慮先找給客戶幾分錢(qián)C.考慮最多可以用幾個(gè)硬幣D.考慮最少可以用幾個(gè)硬幣9.算法必須具備輸入、輸出和()等5個(gè)特性。A.可執(zhí)行性、可移植性和可擴(kuò)充性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性10.當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，()的數(shù)量級(jí)(階)稱為算法的漸進(jìn)時(shí)間復(fù) 雜度。A.時(shí)間復(fù)雜度B.空間復(fù)雜度C.冗余度D.迭代次數(shù)11 .最優(yōu)二叉搜索樹(shù)的時(shí)間復(fù)雜度為()。A. O(n)B. O(n!) _2C. O(n ) 3D. O(n )12 .遞歸函數(shù)f(n)=f(n-1)+n(n>1)的遞歸出口是()。A. f(0)=0

5、B. f(1)=1C. f(0)=1D. f(n)=n 13.在最優(yōu)二叉搜索樹(shù)問(wèn)題中，定義 ei, j 為 ki,.,k j的最優(yōu)二叉查找樹(shù)的 期望搜索成本，而我們確定根結(jié)點(diǎn)下標(biāo)為r,則其左子樹(shù)的下標(biāo)范圍是( )。A. i.rB. i.r-1C. i.r+1D. i+1.r14 .下面是貪心算法的基本要素的是()。A.重疊子問(wèn)題B.構(gòu)造最優(yōu)解C.貪心選擇性質(zhì)D.定義最優(yōu)解15 .分治法所能解決的問(wèn)題應(yīng)具有的關(guān)鍵特征是()A.該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決B.該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題C.利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解D.該問(wèn)題所分解出的各個(gè)子問(wèn)題是

6、相互獨(dú)立的16 .在鋼管切割問(wèn)題里，如果用rn表示長(zhǎng)度為n英寸的鋼管的最優(yōu)切割方案所 獲得的最大收益，且已知rn所代表的最優(yōu)解里，第一刀切下了 3英寸，則下述 公式哪一個(gè)是正確的？（）A. r n = p 3 + r n-3 B.r n = r n 3C.r n = r n-3 + 3D.r n = r 3 + p 317 .（）是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)A.重疊子問(wèn)題B.構(gòu)造最優(yōu)解C.貪心選擇性質(zhì)D.最優(yōu)子結(jié)構(gòu)性質(zhì)18 .使用分治法求解不需要滿足的條件是（）。A.子問(wèn)題必須是一樣的B.子問(wèn)題不能夠重復(fù)C.子問(wèn)題的解可以合并D.原問(wèn)題和子問(wèn)題使用相同的方法解19 .遞歸算法不能適用以下場(chǎng)

7、合（）A.數(shù)據(jù)的定義形式按遞歸定義B.數(shù)據(jù)之間的關(guān)系（即數(shù)據(jù)結(jié)構(gòu)）按遞歸定義C.問(wèn)題解法按遞歸算法實(shí)現(xiàn)D.概率問(wèn)題20 .程序可以不滿足算法性質(zhì)的（）A.輸入B.輸出C.確定性D.有限性二、判斷題(本大題共40分，共20小題，每小題2分)1.對(duì)于矩陣鏈連乘的子問(wèn)題 mi,j,當(dāng)i=j時(shí)表明該矩陣鏈有兩個(gè)矩陣。( )2.如果各子問(wèn)題是不獨(dú)立的，一般用動(dòng)態(tài)規(guī)劃法比分治法較差()。3.一般認(rèn)為，執(zhí)行一次加法或乘法運(yùn)算所需的計(jì)算時(shí)間當(dāng)作一個(gè)僅取決于計(jì)算機(jī)硬件處理速度的常數(shù)。()4.如果兩個(gè)序列的最后一個(gè)字符相同，則其最長(zhǎng)公共子序列必以那個(gè)相同的字符 結(jié)尾。()5.適宜于用貪心策略來(lái)解的問(wèn)題都有兩個(gè)特點(diǎn)

8、：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。()6.Huffmann編碼樹(shù)一定是滿樹(shù)。()7.分治法設(shè)計(jì)出的程序一般是一個(gè)遞歸過(guò)程()8.f(n)=6 X2n+n2, f(n)的漸進(jìn)性態(tài) f(n)= C(2n)()9.算法分析的目的是分析算法占用計(jì)算機(jī)資源的情況，對(duì)算法做出比較和評(píng)價(jià), 設(shè)計(jì)出額更好的算法 ()10.快速排序是一個(gè)遞歸的算法()11.對(duì)于最優(yōu)二叉搜索樹(shù)問(wèn)題，搜索概率最高的元素一定在根結(jié)點(diǎn)上。(：12.0-1背包問(wèn)題，貪心選擇能得到最優(yōu)解。()13.貪心算法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。()14.絕大多數(shù)情況下，快速排序算法的時(shí)間復(fù)雜度位O(n log(n)。()15.最優(yōu)子結(jié)

9、構(gòu)性質(zhì)特征反映了遞歸思想的應(yīng)用()16.如果全部元素的搜索概率是相等的，此時(shí)最優(yōu)二叉搜索樹(shù)應(yīng)接近一棵完美二叉樹(shù)，其搜索代價(jià)與折半查找法相當(dāng)。()17. 分治法的基本思想是將一個(gè)規(guī)模較大的問(wèn)題分解成若干個(gè)規(guī)模較小的問(wèn)題，這些子問(wèn)題之間并不一定相互獨(dú)立() 18.操作系統(tǒng)，它是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。()19.對(duì)同一個(gè)問(wèn)題，動(dòng)態(tài)規(guī)劃算法和分治算法計(jì)算復(fù)雜性是一樣的。（）20.對(duì)于01背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法，背包容量越大，算法執(zhí)行所花費(fèi)的時(shí)間越 多。（）答案:一、單項(xiàng)選擇題（60分，共20題，每小題3分）1. A 2. A 3. C 4. D 5. B 6. A 7. A 8. A 9. B 10. A 11. D 12. B 13. B14. C 15. C 16. A 17. D