算法設計分析

1、第 1 次作業(yè) 一、單項選擇題（本大題共 60 分，共 20 小題，每小題 3 分）1.設 mi, j為計算矩陣鏈A所需的乘法運算次數(shù)的最小值，則矩陣鏈Ain所需的乘法運算次數(shù)的最小值為（ ）。A. m0,nB. m1,n-1C. m1,n+1D. m1,n2. 二分搜索算法是基于（ ）設計的算法。A. 分治法B. 動態(tài)規(guī)劃法C. 貪心法D. 窮盡法3. 直接或間接的調(diào)用自身的算法稱為（ ）。A. 貪心算法B. 遞歸算法C. 迭代算法D. 動態(tài)規(guī)劃算法4. 算法分析的兩個主要方面是（ ）。A. 空間復雜度和時間復雜度B. 正確性和簡單性C. 可讀性和文檔性5. 下述關于最優(yōu)子結(jié)構的說法，不正確

2、的是（ ）。A. 原問題的最優(yōu)解包含子問題的最優(yōu)解B. 原問題的最優(yōu)解建立在子問題的最優(yōu)解基礎之上C. 原問題的最優(yōu)解依賴于子問題的最優(yōu)解D. 原問題的最優(yōu)解通過子問題的非最優(yōu)解合并而得6. 當 n 越來越大時，下列函數(shù)中，增長速度最快的應該是（）A. y=100nB. y=log100nC. y=D.y=7. 實現(xiàn)歸并排序利用的算法是（）A.分治策略B. 動態(tài)規(guī)劃法？C. 貪心法D. 回溯法8. 算法的時間復雜度是指（）A. 執(zhí)行算法程序所需要的時間B. 算法程序的長度C. 算法執(zhí)行過程中所需要的基本運算次數(shù)D. 算法程序中的指令條數(shù)9. 在活動安排問題中，下述哪項描述中的活動A,B 是相容

3、的（）？A. 活動 A 于活動 B 開始前開始B. 活動 A 于活動 B 結(jié)束前開始C. 活動 A 于活動 B 開始前結(jié)束D. 活動 A 于活動 B 開始后開始10. 衡量一個算法好壞的標準是（ ）。A. 運行速度快B. 占用空間少C. 時間復雜度低D. 代碼短11.在最長公共子序列問題中，如果定義 ci, j 為 X1.i和 Y1.j的最長公共子序列的長度，則長度為 m 的 X 序列與長度為 n 的丫序列的最長公共子序列的長度為（ ）。A. c0,0B. c1,1C. c1,mD. cm,n11. 以下關于貪心算法，不正確的說法是 （ ）。A. 用于解決優(yōu)化問題B. 總是選擇在當前看來最好的

4、選擇C. 期望通過局部最優(yōu)達到全局最優(yōu)D. 所需求解的問題可以不滿足最優(yōu)子結(jié)構性質(zhì)12. 一個 p 行 q 列的矩形同一個 q 行 r 列的矩形相乘，總共要作多少次乘法運算 （）A. p x rB. q2C. p x q x rD. q314.在最優(yōu)二叉搜索樹問題中，考慮如下的 BST:如果要搜索 k3，總共要經(jīng)過多少次比較（）A. 1 次B. 2 次C. 3 次D. 4 次15.JAVA 程序主要有以下兩種類型（）A. 應用程序和 APPLET 應用程序和理論程序B. 系統(tǒng)程序和應用程序C. 系統(tǒng)程序和理論程序D. D 系統(tǒng)程序和 APPLET 應用程序16.A.1010B. 1110C.

5、1111D. 01017. 適用動態(tài)規(guī)劃解決的問題必須滿足最優(yōu)子結(jié)構和（ ）性質(zhì)。A. 無后效性B. 無前效性C. 重疊子問題D. 遞歸18. 對于 n 個元素的排序問題。n = 2 時，只要作（）次比較即可排好序A. 3B. 2C. 1D. 419. 二分搜索算法的基本思想是將 n 個元素分成個數(shù)大致相同的兩半，取 與 x進行比較：如果（），則只要在數(shù)組 a 的左半部繼續(xù)搜索 X。A.xvan/2B. x=an/2C. xan/2D. x=an/220.備忘錄方法的遞歸方式是 （ ）A.自頂向下B.自右向左C.忽上忽下D.自底向上 二、判斷題(本大題共 40 分，共 20 小題，每小題 2

6、分)an/21.應用 Huffmann 編碼的目的是用更少的比特流表達更多的信息。( )2.兩個序列的最長公共子序列可以幫助評價兩個序列的相似度。( )3. 算法就是一組有窮的規(guī)則。 ( )4.要想在電腦上擴大所處理問題的規(guī)模 ,有效的途徑是提高算法的計算復雜度。 ( )5.歸并排序算法是漸近最優(yōu)算法 ( )6.快速排序算法是基于貪心策略的一個算法 ( )。7.二分搜索方法在最壞的情況下用 O(log n)時間完成搜索任務。()8.快速排序法是基于分治策略的。 ( )9. 基于三數(shù)取中劃分的快速排序算法其最壞時間復雜度比基本的快速排序算法 要好( )10.遞歸算法解題通常顯得很簡潔 ,而且運行

7、效率較高 ( ) 11.最壞情況下的時間復雜度和平均時間復雜度一樣。( )12.計算機只能運行在有窮步內(nèi)終止的算法。()13.在活動選擇問題中，如果活動 A 晚于活動 B 開始，則兩個活動相容。( )14.T(n)是某算法的時間復雜性函數(shù)，f(n)是一簡單函數(shù)，存在正整數(shù) no和 c, n no,有 T(n)cf(n),這種關系記作 T(n)=O(f(n)()15. 動態(tài)規(guī)劃的一個重要思想是要記住已經(jīng)計算過的子問題的解。()16. 能否利用分治法完全取決于問題是否具有如下特征：利用該問題分解出的子問 題的解可以合并為該問題的解。 ( )17.貪心算法所做的選擇都是目前最佳的 ( )。18. 任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模有關。 ( )19.矩陣連乘積計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。()2o.對鋼管切割問題反復應用“總是切單位價值最高的允許長度 ”的貪心規(guī)則可以獲 得最優(yōu)解。（ ）x答案： 一、單項選擇題（ 60 分，共 20 題，每小題 3 分）1. D 2. A 3. B 4. A 5. D 6. C 7. A 8. C 9. C 10. C 11. D 12. D 13.