第一章測試1【判斷題】(10分)程序運(yùn)行結(jié)果往往與輸入相關(guān)，所以程序可以不滿足確定性（）A.對(duì)B.錯(cuò)2【多選題】(20分)有關(guān)算法分析的事后統(tǒng)計(jì)法正確的是（）。A.從理論上講，在各種軟硬件環(huán)境下進(jìn)行算法測試，得到的資源耗費(fèi)都是一樣的。B.結(jié)果與測試的樣本數(shù)據(jù)有關(guān)C.測試的結(jié)果與程序的編譯和運(yùn)行環(huán)境有關(guān)D.結(jié)果是面向機(jī)器，面向程序員，面向語言的3【多選題】(20分)下面哪些內(nèi)容是算法設(shè)計(jì)之前要完成的內(nèi)容?()A.是求精確解還是近似解B.證明算法的正確性。C.確定合適的數(shù)據(jù)結(jié)構(gòu)D.使用何種計(jì)算機(jī)語言設(shè)計(jì)程序4【單選題】(20分)函數(shù)10logn3+5logn2的漸近表達(dá)式為（）：A.O（logn2）B.O(logn)C.O(logn3)D.O(nlogn)5【單選題】(20分)下列函數(shù)根據(jù)漸近階從低到高順序是（）A.n1/2＜logn＜2n＜n3＜3n＜n!B.logn＜n1/2＜2n＜n3＜n!＜3nC.n1/2＜logn＜2n＜n3＜n!＜3nD.logn＜n1/2＜2n＜n3＜3n＜n!6【判斷題】(10分)研究NPC問題的意義:一旦某個(gè)NPC問題找到了多項(xiàng)式時(shí)間復(fù)雜性的算法，那么所有的NP問題都找到了多項(xiàng)式時(shí)間算法。()A.錯(cuò)B.對(duì)第二章測試1【單選題】(10分)直接或間接的調(diào)用自身的算法稱為（）。A.貪心算法B.遞歸算法C.迭代算法D.動(dòng)態(tài)規(guī)劃算法2【單選題】(10分)Hanoi塔問題如下圖所示?，F(xiàn)要求將塔座A上的的所有圓盤移到塔座B上，并仍按同樣順序疊置。移動(dòng)圓盤時(shí)遵守Hanoi塔問題的移動(dòng)規(guī)則。由此設(shè)計(jì)出解Hanoi塔問題的遞歸算法正確的為：（）A.

B.

C.

D.

3【單選題】(10分)分治法的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問題分割成規(guī)模較小的子問題分別解決子問題最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題（）。A.問題規(guī)模相同，問題性質(zhì)不同B.問題規(guī)模相同，問題性質(zhì)相同C.問題規(guī)模不同，問題性質(zhì)不同D.問題規(guī)模不同，問題性質(zhì)相同4【單選題】(10分)利用二分搜索，最壞情況下的計(jì)算時(shí)間復(fù)雜性為（）。A.O（n）B.O(2n)C.O(logn)D.O(n2)5【單選題】(10分)二分搜索算法只適用（）存儲(chǔ)結(jié)構(gòu)。A.任意順序B.順序C.堆D.棧6【單選題】(10分)使用二分搜索算法在1000個(gè)有序元素表中搜索一個(gè)特定元素，在最壞情況下，搜索總共需要比較的次數(shù)為（）。A.10B.500C.1000D.117【單選題】(10分)線性時(shí)間選擇的時(shí)間復(fù)雜度為（）。A.O(n)B.O（nlogn）C.O(n2)D.O(logn)8【單選題】(10分)利用合并排序，其輔助空間為（）：A.O(logn)B.O（n）C.O(nlogn)D.O(n2)9【單選題】(10分)利用快速排序，對(duì)數(shù)的序列{16,27,13,2,15,38}，選擇基準(zhǔn)16，進(jìn)行一次劃分，結(jié)果為（）：A.{13,2,15}16{38,27}B.{15,13,2}16{27,38}C.{2,13,15}16{38,27}D.{13,2,15}16{27,38}10【判斷題】(10分)分治策略解決棋盤覆蓋問題是一個(gè)漸近意義下最優(yōu)的算法.（）A.錯(cuò)B.對(duì)第三章測試1【單選題】(10分)設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk}，若xm=yn則（）。A.zk=xm=yn，且zk-1是Xm-1和Yn-1的最長公共子序列。B.zk≠xm=yn，且zk是Xm-1和Yn-1的最長公共子序列。C.zk=xm=yn，且zk是Xm-1和Yn-1的最長公共子序列。D.zk≠xm=yn，且zk-1是Xm-1和Yn-1的最長公共子序列。2【單選題】(10分)當(dāng)(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10)=(-1,5,-2,1,-7,-4,2,3,-1,2)時(shí)，最大子段和為().A.6B.9C.10D.73【單選題】(10分)設(shè)有四個(gè)矩陣A,B,C,D,它們的維數(shù)分別是A=50*10,B=10*40,C=40*30,D=30*50,，則計(jì)算其乘積至少需要（）次乘法A.16000,B.10500,C.87500D.36000,4【多選題】(20分)下面關(guān)于動(dòng)態(tài)規(guī)劃解題的步驟內(nèi)容描述正確的是哪些？（）A.分析最優(yōu)解的結(jié)構(gòu)：將一個(gè)一般化問題可以分解為幾個(gè)性質(zhì)相同的子問題，并且問題的最優(yōu)解可以通過子問題的最優(yōu)解合并得到，也就是要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。B.構(gòu)造最優(yōu)解：根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息構(gòu)造出問題的最優(yōu)解，通常是用遞歸算法完成最優(yōu)解的構(gòu)造。C.建立遞歸關(guān)系：建立關(guān)于問題最優(yōu)值的遞歸定義，即問題的最優(yōu)值通過子問題的最優(yōu)值合并得到。D.計(jì)算最優(yōu)值：以自頂往下的方法計(jì)算問題的最優(yōu)值，也就是先求解規(guī)模較大的問題的最優(yōu)值。5【單選題】(15分)問題用動(dòng)態(tài)規(guī)劃算法求解效率較高的原因？()A.遞歸性質(zhì).B.最優(yōu)子結(jié)構(gòu)性質(zhì)C.子問題重疊性質(zhì)D.貪心選擇性質(zhì)6【單選題】(15分)對(duì)0-1背包問題，n=5，c=12，w={3,7,5,4，4}，v={6,3,5,4，6}，則其最優(yōu)解為（）A.（0，1，1，1，1）B.（1，1，1，1，1）C.（0，1，0，1，1）D.（1，0，1，0，1）7【判斷題】(10分)一般來說解同一個(gè)問題，動(dòng)態(tài)規(guī)劃法的效率高于分治算法（）A.錯(cuò)B.對(duì)8【判斷題】(10分)圖象的變位壓縮存儲(chǔ)采用數(shù)據(jù)頭和數(shù)據(jù)存儲(chǔ)的編碼式存儲(chǔ)方式，節(jié)省存儲(chǔ)空間，實(shí)現(xiàn)壓縮。（）A.對(duì)B.錯(cuò)第四章測試1【單選題】(15分)在某通訊系統(tǒng)中用到了a，b，c，d，e，f8個(gè)字符，字符頻度（百分比）為45，13，12，16，9，5則字符a的編碼為()：A.0B..111C.11002【單選題】(15分)活動(dòng)安排問題利用貪心法求解，則其復(fù)雜度為（）A.O(n)B.O(nlogn)C.O(n2)D.O(logn)3【判斷題】(15分)在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。()A.對(duì)B.錯(cuò)4【判斷題】(15分)背包問題與0-1背包問題求解方法類似，都能用貪心法或動(dòng)態(tài)規(guī)劃方法得到最優(yōu)解（）A.錯(cuò)B.對(duì)5【多選題】(20分)有關(guān)分治法、貪心算法和動(dòng)態(tài)規(guī)劃算法的描述，正確的是（）A.問題能用動(dòng)態(tài)規(guī)劃法解的不一定能用貪心算法解；B.貪心算法和動(dòng)態(tài)規(guī)劃算法共同特征為最優(yōu)子結(jié)構(gòu)性質(zhì);C.用貪心法一定能用動(dòng)態(tài)規(guī)劃法，但是，動(dòng)態(tài)規(guī)劃法的效率一般高于貪心算法。D.適用三種方法所解的問題都是可分解成子問題的；6【多選題】(20分)下列哪些問題能適用貪心法高效求解？（）A.最小生成樹問題B.單源最短路徑問題C.哈夫曼編碼問題D.0-1背包問題第五章測試1【判斷題】(10分)使用回溯法求解0-1背包問題時(shí)，計(jì)算右子樹上界的方法是通過貪心策略求得上界（）A.錯(cuò)B.對(duì)2【判斷題】(10分)適用回溯法解旅行售貨員問題，只有當(dāng)搜索到最后一個(gè)城市時(shí)，才能判斷當(dāng)前路徑是否是該問題的一個(gè)解。（）A.對(duì)B.錯(cuò)3【多選題】(25分)下面關(guān)于用回溯法解題說法，正確的是().A.這種方法適用于解一些組合數(shù)相當(dāng)大的問題。B.在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間；C.顯式地存儲(chǔ)整個(gè)解空間；D.解空間樹有子集樹與排列樹兩種;4【多選題】(20分)回溯法中的剪枝函數(shù)包括()。A.遞歸函數(shù)B.隨機(jī)數(shù)生成函數(shù)C.約束函數(shù)D.限界函數(shù)5【多選題】(25分)回溯法解題步驟,正確的是（）A.確定最優(yōu)子結(jié)構(gòu)的性質(zhì);B.針對(duì)所給問題，定義問題的解空間;C.以深度優(yōu)先方式搜索解空間，在搜索過程中用剪枝函數(shù)避免無效搜索;D.確定易于搜索的解空間結(jié)構(gòu);6【判斷題】(10分)四色定理是第一個(gè)主要由計(jì)算機(jī)證明的理論（）A.對(duì)B.錯(cuò)第六章測試1【單選題】(15分)在對(duì)問題的解空間樹進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)的是()。A.回溯法求解子集樹問題B.回溯法C.回溯法和分支限界法D.分支限界法2【單選題】(15分)分支限界法與回溯法的相同點(diǎn)是：都是一種在問題的（）中搜索