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

1、<p>　　第2次作業(yè)一、單項(xiàng)選擇題（本大題共60分，共 20 小題，每小題 3 分）1. </p><p>　　一個(gè)長(zhǎng)度為n英寸的鋼管的最優(yōu)切割問(wèn)題，總共有多少個(gè)不同的子問(wèn)題？（   ）</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. 實(shí)現(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. 在鋼管切割問(wèn)題里，我們用如下遞歸表達(dá)式表達(dá)原問(wèn)題的最優(yōu)解的最優(yōu)

4、值：請(qǐng)問(wèn)，其中的i是指什么？（  ）A. 1英寸鋼管的價(jià)值B. 子問(wèn)題的鋼管長(zhǎng)度C. 第一刀所切割的鋼管長(zhǎng)度D. 價(jià)值/長(zhǎng)度比4. 在最優(yōu)二叉搜索樹問(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

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

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

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

8、. 確定性、有窮性和穩(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í)間復(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)二叉搜索樹問(wèn)題中，定義e[i, j ]為  ki,...,kj的最優(yōu)二叉查找樹的期望搜索成本，而我們確定根結(jié)點(diǎn)下標(biāo)為r, 則其左子樹的下標(biāo)范圍是（   ）。</p><p>　　A. i..rB. i..r-1C. i..r+1D. i+1..r14. 下面是貪

10、心算法的基本要素的是（   ）。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)題是相互獨(dú)立的16. 在鋼管切割問(wèn)題里，如果用rn表示長(zhǎng)度為n英寸的

11、鋼管的最優(yōu)切割方案所獲得的最大收益，且已知rn所代表的最優(yōu)解里，第一刀切下了3英寸，則下述公式哪一個(gè)是正確的？（    ）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. （   ）是貪心算法與動(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. </p><p>

13、;　　使用分治法求解不需要滿足的條件是（ ）。</p><p>　　A. 子問(wèn)題必須是一樣的B. 子問(wèn)題不能夠重復(fù)C. 子問(wèn)題的解可以合并D. 原問(wèn)題和子問(wèn)題使用相同的方法解19. 遞歸算法不能適用以下場(chǎng)合（  ）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.

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

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

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

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

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

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

20、/b></p><p>　　貪心算法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。( )</p><p><b>　　14. </b></p><p>　　絕大多數(shù)情況下，快速排序算法的時(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>　　如果全部元素的搜索概率是相等的，此時(shí)最優(yōu)二叉搜索樹應(yīng)接近一棵完美二叉樹，其搜索代價(jià)與折半查找法相當(dāng)。（  ）</p><p>　　17. 分治法的基本思想是將一個(gè)規(guī)模較大的問(wèn)題分解成若干個(gè)規(guī)模

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

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