2018年6月算法設(shè)計分析 ( 第2次 )作業(yè)

1、<p>　　第2次作業(yè)一、單項選擇題（本大題共60分，共 20 小題，每小題 3 分）1. </p><p>　　一個長度為n英寸的鋼管的最優(yōu)切割問題，總共有多少個不同的子問題？（   ）</p><p>　　A. n+1B. </p><p><b>　　n2</b></p><p>

2、;<b>　　C. </b></p><p><b>　　nlogn</b></p><p><b>　　D. </b></p><p><b>　　logn</b></p><p>　　2. 實現(xiàn)快速排序算法如下： QuickSort (A, p, r

3、) IF p < r THEN 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. 在鋼管切割問題里，我們用如下遞歸表達式表達原問題的最優(yōu)解的最優(yōu)

4、值：請問，其中的i是指什么？（  ）A. 1英寸鋼管的價值B. 子問題的鋼管長度C. 第一刀所切割的鋼管長度D. 價值/長度比4. 在最優(yōu)二叉搜索樹問題中，我們的優(yōu)化目標(biāo)是（   ）。A. 只經(jīng)過最少次數(shù)的比較就可以找到概率最大的元素B. 經(jīng)過最多次數(shù)的比較就可以找到概率最小的元素C. 找到每個元素所需要的平均比較次數(shù)為最小D. 元素搜索代價的數(shù)學(xué)期望為最小5. Edmonds-Karp

5、算法中尋找增廣路徑的方法是（  ）。A. 深度優(yōu)先算法B. 廣度優(yōu)先算法C. Prim算法D. Dijkstra算法6. </p><p>　　關(guān)于0，1背包問題的下述形式化公式描述：</p><p>　　下述說法不正確的是（  ）。</p><p>　　A. i 表示物品的重量B. C表示背包容量C. xi=0表示編號為i的物品不

6、被選擇D. 求解目標(biāo)是最大化裝入背包內(nèi)的物品的總價值7. 在活動安排問題中，如果把全部活動按照結(jié)束時間遞增序排序后，按貪心算法，我們總是安排 （   ）。A. 當(dāng)前可選活動中結(jié)束時間最早的活動B. 當(dāng)前可選活動中開始時間最早的活動C. 當(dāng)前可選活動中沖突數(shù)量最少的活動D. 當(dāng)前可選活動中持續(xù)時間最長的活動8. </p><p>　　找零錢問題中，定義 C[j]為兌換j 所需要的硬

7、幣的最少數(shù)量，考慮下述遞歸表達式，</p><p>　　下列關(guān)于對i的尋優(yōu)的最恰當(dāng)描述是（   ）。</p><p>　　A. 考慮找出的第一個硬幣面值的各種可能性B. 考慮先找給客戶幾分錢C. 考慮最多可以用幾個硬幣D. 考慮最少可以用幾個硬幣9. 算法必須具備輸入、輸出和（ ）等5個特性。A. 可執(zhí)行性、可移植性和可擴充性B. 可行性、確定性和有窮性C

8、. 確定性、有窮性和穩(wěn)定性D. 易讀性、穩(wěn)定性和安全性10. 當(dāng)問題的規(guī)模n趨向無窮大時，（ ）的數(shù)量級(階)稱為算法的漸進時間復(fù)雜度。A. 時間復(fù)雜度B. 空間復(fù)雜度C. 冗余度D. 迭代次數(shù)11. 最優(yōu)二叉搜索樹的時間復(fù)雜度為（  ）。A. O(n)B. O(n!)C. O(n2)D. O(n3)12. 遞歸函數(shù)f(n)=f(n-1)+n(n>1)的遞歸出口是( )。A. f(0)=0B.

9、 f(1)=1C. f(0)=1D. f(n)=n13. </p><p>　　在最優(yōu)二叉搜索樹問題中，定義e[i, j ]為  ki,...,kj的最優(yōu)二叉查找樹的期望搜索成本，而我們確定根結(jié)點下標(biāo)為r, 則其左子樹的下標(biāo)范圍是（   ）。</p><p>　　A. i..rB. i..r-1C. i..r+1D. i+1..r14. 下面是貪

10、心算法的基本要素的是（   ）。A. 重疊子問題B. 構(gòu)造最優(yōu)解C. 貪心選擇性質(zhì)D. 定義最優(yōu)解15. 分治法所能解決的問題應(yīng)具有的關(guān)鍵特征是（ ）。A. 該問題的規(guī)?？s小到一定的程度就可以容易地解決B. 該問題可以分解為若干個規(guī)模較小的相同問題C. 利用該問題分解出的子問題的解可以合并為該問題的解D. 該問題所分解出的各個子問題是相互獨立的16. 在鋼管切割問題里，如果用rn表示長度為n英寸的

11、鋼管的最優(yōu)切割方案所獲得的最大收益，且已知rn所代表的最優(yōu)解里，第一刀切下了3英寸，則下述公式哪一個是正確的？（    ）A. rn  = p3 + rn-3B. </p><p>　　rn  = rn – 3</p><p><b>　　C. </b></p><p>　　rn  

12、;= rn-3 + 3</p><p><b>　　D. </b></p><p>　　rn  = r3 + p3</p><p>　　17. （   ）是貪心算法與動態(tài)規(guī)劃算法的共同點。A. 重疊子問題B. 構(gòu)造最優(yōu)解C. 貪心選擇性質(zhì)D. 最優(yōu)子結(jié)構(gòu)性質(zhì)18. </p><p>

13、;　　使用分治法求解不需要滿足的條件是（ ）。</p><p>　　A. 子問題必須是一樣的B. 子問題不能夠重復(fù)C. 子問題的解可以合并D. 原問題和子問題使用相同的方法解19. 遞歸算法不能適用以下場合（  ）A. 數(shù)據(jù)的定義形式按遞歸定義B. 數(shù)據(jù)之間的關(guān)系(即數(shù)據(jù)結(jié)構(gòu))按遞歸定義C. 問題解法按遞歸算法實現(xiàn)D. 概率問題20. 程序可以不滿足算法性質(zhì)的（  ）A.

14、輸入B. 輸出C. 確定性D. 有限性二、判斷題（本大題共40分，共 20 小題，每小題 2 分）1. </p><p>　　對于矩陣鏈連乘的子問題m[i,j]，當(dāng)i=j時表明該矩陣鏈有兩個矩陣。（   ）</p><p><b>　　2. </b></p><p>　　如果各子問題是不獨立的，一般用動態(tài)規(guī)劃法比分

15、治法較差( )。</p><p><b>　　3. </b></p><p>　　一般認為，執(zhí)行一次加法或乘法運算所需的計算時間當(dāng)作一個僅取決于計算機硬件處理速度的常數(shù)。(  )   </p><p><b>　　4. </b></p><p>　　如果兩個序列的最后一

16、個字符相同，則其最長公共子序列必以那個相同的字符結(jié)尾。（  ）</p><p><b>　　5. </b></p><p>　　適宜于用貪心策略來解的問題都有兩個特點:貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。( )</p><p><b>　　6. </b></p><p>　　Huffmann編碼樹一

17、定是滿樹。（   ）</p><p><b>　　7. </b></p><p>　　分治法設(shè)計出的程序一般是一個遞歸過程( )</p><p><b>　　8. </b></p><p>　　f(n)=6×2n+n2，f(n)的漸進性態(tài)f(n)=(2n)（ ）<

18、/p><p><b>　　9. </b></p><p>　　算法分析的目的是分析算法占用計算機資源的情況，對算法做出比較和評價，設(shè)計出額更好的算法  ( )</p><p><b>　　10. </b></p><p>　　快速排序是一個遞歸的算法( )</p><p&g

19、t;<b>　　11. </b></p><p>　　對于最優(yōu)二叉搜索樹問題，搜索概率最高的元素一定在根結(jié)點上。（  ）</p><p><b>　　12. </b></p><p>　　0-1背包問題，貪心選擇能得到最優(yōu)解。 ( )</p><p><b>　　13. <

20、/b></p><p>　　貪心算法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。( )</p><p><b>　　14. </b></p><p>　　絕大多數(shù)情況下，快速排序算法的時間復(fù)雜度位O(n log(n))。 （ ）</p><p><b>　　15. </b></p&g

21、t;<p>　　最優(yōu)子結(jié)構(gòu)性質(zhì)特征反映了遞歸思想的應(yīng)用 ( )</p><p><b>　　16. </b></p><p>　　如果全部元素的搜索概率是相等的，此時最優(yōu)二叉搜索樹應(yīng)接近一棵完美二叉樹，其搜索代價與折半查找法相當(dāng)。（  ）</p><p>　　17. 分治法的基本思想是將一個規(guī)模較大的問題分解成若干個規(guī)模

22、較小的問題，這些子問題之間并不一定相互獨立( )18. </p><p>　　操作系統(tǒng)，它是一個在無限循環(huán)中執(zhí)行的程序，因而不是一個算法。( )</p><p><b>　　19. </b></p><p>　　對同一個問題，動態(tài)規(guī)劃算法和分治算法計算復(fù)雜性是一樣的。（ ）</p><p><b>　　20.

23、 </b></p><p>　　對于01背包問題的動態(tài)規(guī)劃算法，背包容量越大，算法執(zhí)行所花費的時間越多。 （  ）</p><p>　　答案：一、單項選擇題（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. B 14. C 15. C 16