2017年重大算法設(shè)計分析第二次作業(yè)及答案

1、第2次作業(yè)次作業(yè)一、單項選擇題（本大題共一、單項選擇題（本大題共4040分，共分，共2020小題，每小題小題，每小題2分）分）1.在找零錢問題中，收銀員算法中所應(yīng)用的貪心規(guī)則的最恰當(dāng)描述是（）。A.總是選擇面值最高的硬幣B.總是選擇不超過剩余應(yīng)找錢數(shù)的最大面值的硬幣C.總是選擇面值是10，5的倍數(shù)的硬幣D.總是選擇面值最小的硬幣2.由邊界條件出發(fā)通過遞推式求f(n)的值從邊界到求解的全過程十分清楚的是（）A.貪心B.遞推C.遞歸D.概率

2、3.考慮最長公共子序列問題的下述遞歸表達(dá)式，[P_C53CE8FF336AA43839D03B6A499D5422]如果全部子問題組織在一個c[ij]的二維表格中，則c[ij]不依賴于下述哪個子問題：（）。A.同一行的上一列B.同一列的上一行C.上一行的上一列D.同一行的下一列4.找零錢問題中，定義C[j]為兌換j所需要的硬幣的最少數(shù)量，如果找出的第一個硬幣為5分，則下述公式哪個是對的（）。A.C[j]=1C[j5]B.C[j]=5C[

3、j1]C.C[j]=5C[j5]D.C[j]=1C[j1]5.大型程序設(shè)計一般用（）數(shù)據(jù)類型來描述算法。A.邏輯B.抽象C.簡明D.復(fù)雜6.在最優(yōu)二叉搜索樹問題中，我們的優(yōu)化目標(biāo)是（）。A.只經(jīng)過最少次數(shù)的比較就可以找到概率最大的元素B.經(jīng)過最多次數(shù)的比較就可以找到概率最小的元素C.找到每個元素所需要的平均比較次數(shù)為最小D.元素搜索代價的數(shù)學(xué)期望為最小7.EdmondsKarp算法中尋找增廣路徑的方法是（）。15.在鋼管切割問題里，如果

4、用rn表示長度為n英寸的鋼管的最優(yōu)切割方案所獲得的最大收益，且已知rn所代表的最優(yōu)解里，第一刀切下了3英寸，則下述公式哪一個是正確的？（）A.rn=p3rn3B.rn=rn–3C.rn=rn33D.rn=r3p316.程序可以不滿足算法性質(zhì)的（）A.輸入B.輸出C.確定性D.有限性17.考慮關(guān)于01背包問題的如下遞歸表達(dá)式，[P_8BD35526A3C2328AA5A3718BBF7E29D3]如果物品i的重量小于背包的剩余容量，并且我

5、們選擇裝入了物品i則OPT(i，w)的取值為（）。A.OPT(i1w)B.OPT(i1wwi)C.viOPT(i1wwi)D.viOPT(i1wi)18.以下關(guān)于Huffmann樹的描述，哪一項是錯誤的（）。A.Huffman樹是滿樹B.字符均在葉子結(jié)點上C.最低頻度的兩個字符處于樹的最底層，且互為兄弟D.在樹的同一層，字符的出現(xiàn)順序會影響平均編碼長度的數(shù)學(xué)期望19.一般地講，當(dāng)一個問題的所有子問題都至少要解一次時，用動態(tài)規(guī)劃算法和備忘