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

1、第2次作業(yè)一、單項選擇題(本大題共60分，共20小題，每小題3分)1.一個長度為n英寸的鋼管的最優(yōu)切割問題，總共有多少個不同的子問題?A.n+1B.n2C.nlognD.logn2 .實現(xiàn)快速排序算法如下：Quicksort(A,p,r)IFp<rTHENqPartition(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)值:%=max(pi+%/)日斗請問，其

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

3、容量C. xi=0表示編號為i的物品不被選擇D.求解目標是最大化裝入背包內(nèi)的物品的總價值7 .在活動安排問題中，如果把全部活動按照結(jié)束時間遞增序排序后，按貪心算法，我們總是安排（）。A.當前可選活動中結(jié)束時間最早的活動8 .當前可選活動中開始時間最早的活動C.當前可選活動中沖突數(shù)量最少的活動D.當前可選活動中持續(xù)時間最長的活動8.找零錢問題中，定義Cj為兌換j所需要的硬幣的最少數(shù)量，考慮下述遞歸表達式,0,01<->_XCj=01+rnrnCj-l<l<k卜列關(guān)于對i的尋優(yōu)的最恰當描述是（A.考慮找出的第一個硬幣面值的各種可能性B.考慮先找給客戶幾分錢C.考慮最多可以用

4、幾個硬幣D.考慮最少可以用幾個硬幣9.算法必須具備輸入、輸出和()等5個特性。A.可執(zhí)行性、可移植性和可擴充性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性10.當問題的規(guī)模n趨向無窮大時，()的數(shù)量級(階)稱為算法的漸進時間復(fù)雜度。A.時間復(fù)雜度B.空間復(fù)雜度C.冗余度D.迭代次數(shù)11 .最優(yōu)二叉搜索樹的時間復(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)=0B. f(1)=1C. f(0)=1D. f(n)=n13.在最優(yōu)二叉搜索樹問題中，

5、定義ei,j為ki,.,kj的最優(yōu)二叉查找樹的期望搜索成本，而我們確定根結(jié)點下標為r,則其左子樹的下標范圍是()。A. i.rB. i.r-1C. i.r+1D. i+1.r14 .下面是貪心算法的基本要素的是()。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英寸的鋼管的最優(yōu)切割方案所獲得的最大收益，

6、且已知rn所代表的最優(yōu)解里，第一刀切下了3英寸，則下述公式哪一個是正確的？（）A.rn=p3+rn-3B.rnrn3C.rn=rn-3+3D.rn=r3+p317 .（）是貪心算法與動態(tài)規(guī)劃算法的共同點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.問題解法按遞歸算法實現(xiàn)D.概率問題20 .程序可以不滿足算法性質(zhì)的（）A.輸入B.

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

8、(n)=C(2n)()9.算法分析的目的是分析算法占用計算機資源的情況，對算法做出比較和評價,設(shè)計出額更好的算法()10.快速排序是一個遞歸的算法()11.對于最優(yōu)二叉搜索樹問題，搜索概率最高的元素一定在根結(jié)點上。(：12.0-1背包問題，貪心選擇能得到最優(yōu)解。()13.貪心算法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。()14.絕大多數(shù)情況下，快速排序算法的時間復(fù)雜度位O(nlog(n)。()15.最優(yōu)子結(jié)構(gòu)性質(zhì)特征反映了遞歸思想的應(yīng)用()16.如果全部元素的搜索概率是相等的，此時最優(yōu)二叉搜索樹應(yīng)接近一棵完美二叉樹，其搜索代價與折半查找法相當。()17. 分治法的基本思想是將一個規(guī)模較大的問題分解成若干個規(guī)模較小的問題，這些子問題之間并不一定相互獨立()18.操作系統(tǒng)，它是一個在無限循環(huán)中執(zhí)行的程序，因而不是一個算法。()19.對同一個問題，動態(tài)規(guī)劃算法和分治算法計算復(fù)雜性是一樣的。（）20.對于01背包問題的動態(tài)規(guī)劃算法，背包容量越大，算法執(zhí)行所花費的時間越多。（）答案:一、單項選擇題（60分，共20題，每小題3分）1.A2.A3.C4.D5.B6.A7.A8.A9.B