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

1、第 2 次作業(yè) 一、單項(xiàng)選擇題(本大題共 60 分，共 20 小題，每小題 3 分)1.一個(gè)長度為 n 英寸的鋼管的最優(yōu)切割問題，總共有多少個(gè)不同的子問題？ ()A. n+1B.n2C.nlognD.logn2. 實(shí)現(xiàn)快速排序算法如下：QuickSort (A, p, r)IF p 1) 的遞歸出口是 ( ) 。A. f(0)=0B. f(1)=1C. f(0)=1D. f(n)=n13.在最優(yōu)二叉搜索樹問題中，定義 ei, j 期望搜索成本，而我們確定根結(jié)點(diǎn)下標(biāo)為 ( )。為 k i ,.,k j 的最優(yōu)二叉查找樹的 r, 則其左子樹的下標(biāo)范圍是A. i.rB. i.r-1C. i.r+1D

2、. i+1.r14. 下面是貪心算法的基本要素的是( )。A. 重疊子問題B. 構(gòu)造最優(yōu)解C. 貪心選擇性質(zhì)D. 定義最優(yōu)解15. 分治法所能解決的問題應(yīng)具有的關(guān)鍵特征是( )A. 該問題的規(guī)?？s小到一定的程度就可以容易地解決B. 該問題可以分解為若干個(gè)規(guī)模較小的相同問題C. 利用該問題分解出的子問題的解可以合并為該問題的解D. 該問題所分解出的各個(gè)子問題是相互獨(dú)立的16. 在鋼管切割問題里，如果用 r n表示長度為 n 英寸的鋼管的最優(yōu)切割方案所 獲得的最大收益，且已知 r n所代表的最優(yōu)解里，第一刀切下了 3 英寸，則下述 公式哪一個(gè)是正確的？（ ）A. r n = p 3 + r n-3

3、B.rn = r n 3C.rn = r n-3 + 3D.rn = r 3 + p 317. （ ）是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)A. 重疊子問題B. 構(gòu)造最優(yōu)解C. 貪心選擇性質(zhì)D. 最優(yōu)子結(jié)構(gòu)性質(zhì)18.使用分治法求解不需要滿足的條件是（ ）。A. 子問題必須是一樣的B. 子問題不能夠重復(fù)C. 子問題的解可以合并D. 原問題和子問題使用相同的方法解19. 遞歸算法不能適用以下場合（ ）A. 數(shù)據(jù)的定義形式按遞歸定義B. 數(shù)據(jù)之間的關(guān)系 （即數(shù)據(jù)結(jié)構(gòu) ）按遞歸定義C. 問題解法按遞歸算法實(shí)現(xiàn)D. 概率問題20. 程序可以不滿足算法性質(zhì)的（ ）A. 輸入B. 輸出C. 確定性D. 有限性二、

4、判斷題(本大題共 40 分，共 20 小題，每小題 2 分)1.對于矩陣鏈連乘的子問題 mi,j ，當(dāng) i=j 時(shí)表明該矩陣鏈有兩個(gè)矩陣。 ()2. 如果各子問題是不獨(dú)立的，一般用動(dòng)態(tài)規(guī)劃法比分治法較差 ( ) 。3.一般認(rèn)為，執(zhí)行一次加法或乘法運(yùn)算所需的計(jì)算時(shí)間當(dāng)作一個(gè)僅取決于計(jì)算機(jī) 硬件處理速度的常數(shù)。 ( )4.如果兩個(gè)序列的最后一個(gè)字符相同，則其最長公共子序列必以那個(gè)相同的字符 結(jié)尾。( )5.適宜于用貪心策略來解的問題都有兩個(gè)特點(diǎn) : 貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。 ( )6.Huffmann 編碼樹一定是滿樹。()7.分治法設(shè)計(jì)出的程序一般是一個(gè)遞歸過程 ( )8.f(n)=6 2n+

5、n2，f(n) 的漸進(jìn)性態(tài) f(n)= (2 n)( )9.算法分析的目的是分析算法占用計(jì)算機(jī)資源的情況，對算法做出比較和評(píng)價(jià)， 設(shè)計(jì)出額更好的算法 ( )10.快速排序是一個(gè)遞歸的算法 ( )11.對于最優(yōu)二叉搜索樹問題，搜索概率最高的元素一定在根結(jié)點(diǎn)上。( )12.0-1 背包問題，貪心選擇能得到最優(yōu)解。 ( )13.貪心算法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。 ( )14.絕大多數(shù)情況下，快速排序算法的時(shí)間復(fù)雜度位 O(n log(n) 。 ( )15.最優(yōu)子結(jié)構(gòu)性質(zhì)特征反映了遞歸思想的應(yīng)用 ( )16.如果全部元素的搜索概率是相等的，此時(shí)最優(yōu)二叉搜索樹應(yīng)接近一棵完美二叉 樹

6、，其搜索代價(jià)與折半查找法相當(dāng)。( )17. 分治法的基本思想是將一個(gè)規(guī)模較大的問題分解成若干個(gè)規(guī)模較小的問 題，這些子問題之間并不一定相互獨(dú)立 ( )18.操作系統(tǒng)，它是一個(gè)在無限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。 ( )19.對同一個(gè)問題，動(dòng)態(tài)規(guī)劃算法和分治算法計(jì)算復(fù)雜性是一樣的。（ ）20.對于 01背包問題的動(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. 2. 3.