算法設(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+1B.n2C.nlognD.logn2. 實(shí)現(xiàn)快速排序算法如下：Quicksort (A, p, r)IF p rTHEN q J Partitio n(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)值:5

2、= max (pr +)請(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)題的下述形式化公式描述：maxi=1下述說(shuō)法不正確的是（）A. i 表

3、示物品的重量B. C表示背包容量C. x i=0表示編號(hào)為i的物品不被選擇D. 求解目標(biāo)是最大化裝入背包內(nèi)的物品的總價(jià)值6. 在活動(dòng)安排問(wèn)題中，如果把全部活動(dòng)按照結(jié)束時(shí)間遞增序排序后，按貪心算法，我們總是安排（）。A. 當(dāng)前可選活動(dòng)中結(jié)束時(shí)間最早的活動(dòng)B. 當(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.找零錢(qián)問(wèn)題中，定義Cj為兌換j所需要的硬幣的最少數(shù)量，考慮下述遞歸 表達(dá)式，ocif ； = 0,1 + min J-心 if j 1Ki1) 的遞歸出口是 ( ) 。A. f(0)=0B. f(1)=1C. f(0)=1D. f

4、(n)=n13.在最優(yōu)二叉搜索樹(shù)問(wèn)題中，定義 ei, j 期望搜索成本，而我們確定根結(jié)點(diǎn)下標(biāo)為( )。為k i ,.,kj 的最優(yōu)二叉查找樹(shù)的r, 則其左子樹(shù)的下標(biāo)范圍是A. i.rB. i.r-1C. i.r+1D. i+1.r11. 下面是貪心算法的基本要素的是()。A. 重疊子問(wèn)題B. 構(gòu)造最優(yōu)解C. 貪心選擇性質(zhì)D. 定義最優(yōu)解12. 分治法所能解決的問(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)題是相互獨(dú)立的13. 在鋼管切

5、割問(wèn)題里，如果用rn表示長(zhǎng)度為n英寸的鋼管的最優(yōu)切割方案所 獲得的最大收益，且已知rn所代表的最優(yōu)解里，第一刀切下了 3英寸，則下述 公式哪一個(gè)是正確的？（）A. r n = p 3 + r n-3B.C.rn = r n-3 + 3D.rn = r 3 + p 314. （ ）是貪心算法與動(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.使用分治法求解不需要滿(mǎn)足的條件是（ ）。A. 子問(wèn)題必須是一樣的B. 子問(wèn)題不能夠重復(fù)C. 子問(wèn)題的解可以合并D. 原問(wèn)題和子問(wèn)題使用相同的方法解15. 遞歸算法不能適用以下場(chǎng)合（ ）A. 數(shù)據(jù)的定義形式按遞歸定

6、義B. 數(shù)據(jù)之間的關(guān)系 （即數(shù)據(jù)結(jié)構(gòu) ）按遞歸定義C. 問(wèn)題解法按遞歸算法實(shí)現(xiàn)D. 概率問(wèn)題16. 程序可以不滿(mǎn)足算法性質(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.適宜于用貪心策略

7、來(lái)解的問(wèn)題都有兩個(gè)特點(diǎn) : 貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。 ( )6.Huffmann 編碼樹(shù)一定是滿(mǎn)樹(shù)。( )7.分治法設(shè)計(jì)出的程序一般是一個(gè)遞歸過(guò)程 ( )8.f(n)=6 X2n+n2, f(n)的漸進(jìn)性態(tài) f(n)=(2n)()算法分析的目的是分析算法占用計(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)解，只希望得到較為滿(mǎn)意解的方法。 ( )14.絕大多數(shù)情況下，快速排序算法的時(shí)間

8、復(fù)雜度位 O(n log(n) 。 ( )15.最優(yōu)子結(jié)構(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 18. A 19. D 20. D二、判斷題（ 40 分，共 20 題，每小題 2 分）1. x 2.