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

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

2、問題的最優(yōu)解建立在子問題的最優(yōu)解基礎(chǔ)之上C.原問題的最優(yōu)解依賴于子問題的最優(yōu)解D.原問題的最優(yōu)解通過子問題的非最優(yōu)解合并而得.當(dāng)n越來越大時，下列函數(shù)中，增長速度最快的應(yīng)該是（y=100ny=log100ny=-二.實現(xiàn)歸并排序利用的算法是（）A.分治策略.動態(tài)規(guī)劃法C.貪心法D.回溯法.算法的時間復(fù)雜度是指（）A.執(zhí)行算法程序所需要的時間算法程序的長度C.算法執(zhí)行過程中所需要的基本運算次數(shù)D.算法程序中的指令條數(shù)在活動安排問題中，下述哪項描述中的活動A,B是相容的（）？A.活動A于活動B開始前開始v1.0可編輯可修改B.活動A于活動B結(jié)束前開始C.活動A于活動B開始前結(jié)束D.活動A于活動B開

3、始后開始.衡量一個算法好壞的標(biāo)準(zhǔn)是（）。A.運行速度快B.占用空間少C.時間復(fù)雜度低D.代碼短 11.在最長公共子序列問題中，如果定義ci, j 為X.i和Yj的最長公共子序列的長度，則長度為m的X序列與長度為n的Y序列的最長公共子序列的長度 為（）。c0,0c1,1c1,mcm,n.以下關(guān)于貪心算法，不正確的說法是（）。A.用于解決優(yōu)化問題B.總是選擇在當(dāng)前看來最好的選擇C.期望通過局部最優(yōu)達到全局最優(yōu)D.所需求解的問題可以不滿足最優(yōu)子結(jié)構(gòu)性質(zhì). 一個p行q列的矩形同一個q行r列的矩形相乘，總共要作多少次乘法運算（）p x rqv1.0可編輯可修改C.D. q3 14.在最優(yōu)二叉搜索樹問題中

4、，考慮如下的 BST:如果要搜索k3 ,總共要經(jīng)過多少次比較1次2次3次4次JAVA程序主要有以下兩種類型（）A.應(yīng)用程序和APPLET應(yīng)用程序和理論程序B.系統(tǒng)程序和應(yīng)用程序C.系統(tǒng)程序和理論程序D. D系統(tǒng)程序和APPLE用程序v1.0可編輯可修改如圖所示的Huffmann樹,A.101011101111010.適用動態(tài)規(guī)劃解決的問題必須滿足最優(yōu)子結(jié)構(gòu)和（）性質(zhì)。A.無后效性B.無前效性C.重疊子問題D.遞歸.對于n個元素的排序問題。n =2時，只要作（）次比較即可排好序3214v1.0可編輯可修改19.二分搜索算法的基本思想是將n個元素分成個數(shù)大致相同的兩半，取 an/2與x進行比較：如

5、果（），則只要在數(shù)組a的左半部繼續(xù)搜索x A.xan/2x=an/220.備忘錄方法的遞歸方式是（）自頂向下自右向左忽上忽下v1.0可編輯可修改自底向上二、判斷題（本大題共40分，共20小題，每小題2分）應(yīng)用Huffmann編碼的目的是用更少的比特流表達更多的信息。（）兩個序列的最長公共子序列可以幫助評價兩個序列的相似度。（）算法就是一組有窮的規(guī)則。（）要想在電腦上擴大所處理問題的規(guī)模，有效的途徑是提高算法的計算復(fù)雜度。（）歸并排序算法是漸近最優(yōu)算法（）快速排序算法是基于貪心策略的一個算法（）。v1.0可編輯可修改二分搜索方法在最壞的情況下用 O（log n）時間完成搜索任務(wù)。（）快速排序法是

6、基于分治策略的。 （）基于三數(shù)取中劃分的快速排序算法其最壞時間復(fù)雜度比基本的快速排序算法要好（）遞歸算法解題通常顯得很簡潔，而且運行效率較高（）最壞情況下的時間復(fù)雜度和平均時間復(fù)雜度一樣。（）計算機只能運行在有窮步內(nèi)終止的算法。（）在活動選擇問題中，如果活動 A晚于活動B開始，則兩個活動相容。（v1.0可編輯可修改T(n)是某算法的時間復(fù)雜性函數(shù)，f(n)是一簡單函數(shù)，存在正整數(shù)n。和c, nno,有 T(n)cf(n),這種關(guān)系記作 T(n)=O(f(n)。()動態(tài)規(guī)劃的一個重要思想是要記住已經(jīng)計算過的子問題的解。()能否利用分治法完全取決于問題是否具有如下特征：利用該問題分解出的子問題的解可以合并為該問題的解。()貪心算法所做的選擇都是目前最佳的()O任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模有關(guān)。()矩陣連乘積計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。()v1.0可編輯可修改對鋼管切割問題反復(fù)應(yīng)用“總是切單位價值最高的允許長度”的貪心規(guī)則可以獲得最優(yōu)解。（）答案:一、單項選擇題（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. C14. C 15. A 16. B 17. C 18. C 19. A 20. A二、判斷題（40分，共20題，