第一章測(cè)試1【判斷題】(2分)算法就是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問(wèn)題的一系列運(yùn)算。（）A.對(duì)B.錯(cuò)2【判斷題】(2分)計(jì)算機(jī)的資源最重要的是內(nèi)存和運(yùn)算資源。因而，算法的復(fù)雜性有時(shí)間和空間之分。（）A.對(duì)B.錯(cuò)3【判斷題】(2分)時(shí)間復(fù)雜度是指算法最壞情況下的運(yùn)行時(shí)間。（）A.對(duì)B.錯(cuò)4【單選題】(2分)下面關(guān)于算法的說(shuō)法中正確的是。

（1）求解某一問(wèn)題的算法是唯一的。

（2）算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。

（3）算法的每一條指令是清晰無(wú)歧義的。

（4）算法可以用某種程序設(shè)計(jì)語(yǔ)言具體實(shí)現(xiàn)，所以算法和程序是等價(jià)的。（）A.（1）（3）B.（2）（4）C.（2）（3）D.（1）（2）5【單選題】(2分)描述算法的基本方法有。

（1）自然語(yǔ)言

（2）流程圖

（3）偽代碼

（4）程序設(shè)計(jì)語(yǔ)言（）A.（1）（2）（3）B.（1）（3）(4)C.（1）(2)（3）(4)D.（2）（3）(4)6【單選題】(2分)算法分析是（）A.在抽象數(shù)據(jù)數(shù)據(jù)集合上執(zhí)行程序，以確定是否產(chǎn)生結(jié)果B.對(duì)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量分析C.證明算法對(duì)所有可能的合法出入都能算出正確的答案D.將算法用某種程序設(shè)計(jì)語(yǔ)言恰當(dāng)?shù)乇硎境鰜?lái)7【單選題】(2分)算法是由若干條指令組成的有窮序列，而且滿足以下敘述中的性質(zhì)。

(1)輸入：有0個(gè)或多個(gè)輸入

(2)輸出：至少有一個(gè)輸出

(3)確定性：指令清晰、無(wú)歧義

(4)有限性：指令執(zhí)行次數(shù)有限，而且執(zhí)行時(shí)間有限（）A.（1）（3）（4）B.（1）（2）（3）（4）C.（1）（2）（4）D.（1）（2）（3）8【單選題】(2分)下面函數(shù)中增長(zhǎng)率最低的是（）A.log2nB.2nC.nD.n29【多選題】(2分)下面屬于算法的特性有()。A.有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。B.輸出：算法產(chǎn)生至少一個(gè)量作為輸出。C.確定性：組成算法的每條指令是清晰，無(wú)歧義的。D.輸入：有0個(gè)或多個(gè)外部量作為算法的輸入。10【單選題】(2分)當(dāng)m為24，n為60時(shí)，使用歐幾里得算法求m和n的最大公約數(shù)，需要進(jìn)行（）次除法運(yùn)算。A.不確定B.3次C.4次D.2次第二章測(cè)試1【判斷題】(2分)直接或間接調(diào)用自身的算法稱為遞歸算法。（）A.錯(cuò)B.對(duì)2【判斷題】(2分)遞歸算法的基本原則包括基準(zhǔn)情形、不斷推進(jìn)、設(shè)計(jì)法則和合成效益法則。（）A.錯(cuò)B.對(duì)3【判斷題】(2分)使用分治法解決的一個(gè)問(wèn)題時(shí)，需要將一個(gè)大的問(wèn)題分解成若干個(gè)子問(wèn)題，這些子問(wèn)題可以和原問(wèn)題相同，也可以不同。（）A.對(duì)B.錯(cuò)4【判斷題】(2分)適合于用分治法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題可以不是互相獨(dú)立的。（）A.對(duì)B.錯(cuò)5【單選題】(2分)設(shè)當(dāng)n＞1時(shí)，T（n）=2T（n/2）+O（n），則此分治法的時(shí)間復(fù)雜度為（）。A.Θ(n2)B.Θ（n）C.Θ（nlogn）D.Θ（logn）6【單選題】(2分)設(shè)當(dāng)n＞1時(shí)，T（n）=27T（n/3）+O（n2），則此分治法的時(shí)間復(fù)雜度為（）。A.Θ(n3)B.Θ（n）C.Θ（n2logn）D.Θ（n2）7【單選題】(2分)二分查找有序表（2，8，13，24，33，41，52，58，63，100），若查找表中元素51，則其依次和表中元素（）進(jìn)行比較，查找結(jié)果是失敗。A.56，41，52B.33，9，41，52C.56，52D.33，56，41，528【單選題】(2分)對(duì)于棋盤(pán)覆蓋問(wèn)題的分治算法，使用主定理進(jìn)行算法分析時(shí)，k、m、d的值分別為（）。A.k=4，m=2，d=1B.k=2，m=4，d=1C.k=4，m=2，d=0D.k=2，m=4，d=09【單選題】(2分)下列選項(xiàng)中，不可能是快速排序第2趟排序結(jié)果的是（）。A.{2，7，5，6，4，3，9}B.{4，3，2，5，7，6，9}C.{3，2，5，4，7，6，9}D.{2，3，5，4，6，7，9}10【單選題】(2分)采用遞歸方式對(duì)順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是（）。A.遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無(wú)關(guān)B.每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)C.遞歸次數(shù)與初始初始數(shù)據(jù)的排列次序無(wú)關(guān)D.每次劃分后，先處理較長(zhǎng)的分區(qū)可以減少遞歸次數(shù)第三章測(cè)試1【判斷題】(2分)動(dòng)態(tài)規(guī)劃算法是以空間換時(shí)間的時(shí)空權(quán)衡技術(shù)（）。A.對(duì)B.錯(cuò)2【判斷題】(2分)動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。（）A.對(duì)B.錯(cuò)3【判斷題】(2分)適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題不是互相獨(dú)立的。（）A.對(duì)B.錯(cuò)4【判斷題】(2分)0-1背包問(wèn)題實(shí)例的動(dòng)態(tài)規(guī)劃表中某一行值的序列總是非遞減的（）。A.錯(cuò)B.對(duì)5【判斷題】(2分)求解某一問(wèn)題的算法是唯一的。A.對(duì)B.錯(cuò)6【單選題】(2分)下列算法通常以自底向上的方式求解的是（）。A.備忘錄法B.回溯法C.動(dòng)態(tài)規(guī)劃算法D.貪心法7【單選題】(2分)下列是動(dòng)態(tài)規(guī)劃基本要素的是（）A.算出最優(yōu)解B.構(gòu)造最優(yōu)解C.子問(wèn)題重疊性質(zhì)D.定義最優(yōu)解8【單選題】(2分)一個(gè)問(wèn)題使用動(dòng)態(tài)規(guī)劃算法的關(guān)鍵特征是（）。A.定義最優(yōu)解B.重疊子問(wèn)題C.貪心選擇性質(zhì)D.最優(yōu)子結(jié)構(gòu)性質(zhì)9【單選題】(2分)備忘錄法是（）的變形。A.回溯法B.貪心法C.動(dòng)態(tài)規(guī)劃D.分治法10【單選題】(2分)要計(jì)算矩陣連乘積A1A2A3A4A5A6，其中各矩陣維數(shù)分別為A1（30×35），A2（35×15），A3（15×5），A4（5×10），A5（10×20），A6（20×25）。使用動(dòng)態(tài)規(guī)劃算法，記錄最優(yōu)值的數(shù)組中，元素m[2][4]的值為（）。A.4375B.750C.6000D.2625第四章測(cè)試1【判斷題】(2分)貪心算法一定能產(chǎn)生最優(yōu)解。（）A.錯(cuò)B.對(duì)2【判斷題】(2分)貪心算法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須消耗的大量時(shí)間。（）A.對(duì)B.錯(cuò)3【判斷題】(2分)貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。（）A.對(duì)B.錯(cuò)4【單選題】(2分)下列算法中通常以自底向上的方式求解最優(yōu)解的是()A.貪心法B.動(dòng)態(tài)規(guī)劃法C.分治法D.回溯法5【單選題】(2分)背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為()A.O(n2^n)B.O(2^n)C.O(nlogn)D.O(n)6【單選題】(2分)采用貪心算法的最優(yōu)裝載問(wèn)題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法的時(shí)間復(fù)雜度為()A.O(2^n)B.O(nlogn)C.O(n2^n)D.O(n)7【判斷題】(2分)如果e是加權(quán)連通圖中權(quán)重最小的邊，它必定是圖的每一棵最小生成樹(shù)的邊。()A.對(duì)B.錯(cuò)8【判斷題】(2分)Prim算法是一種為加權(quán)連通圖構(gòu)造最小生成樹(shù)的貪心算法。（）A.對(duì)B.錯(cuò)9【判斷題】(2分)Kruskal算法按照權(quán)重的升序把邊包含進(jìn)來(lái)，以構(gòu)造最小生成樹(shù),并使得這種包含不會(huì)產(chǎn)生回路。為了保證這種檢查的效率，需要應(yīng)用一種所謂的并查算法。（）A.錯(cuò)B.對(duì)10【判斷題】(2分)對(duì)于不含有負(fù)權(quán)重值的圖，Dijkstral算法總能產(chǎn)生一個(gè)正確的解。（）A.對(duì)B.錯(cuò)第五章測(cè)試1【單選題】(2分)回溯法在問(wèn)題的解空間樹(shù)中，按（）策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。A.擴(kuò)展結(jié)點(diǎn)優(yōu)先B.深度優(yōu)先C.廣度優(yōu)先D.活結(jié)點(diǎn)優(yōu)先2【單選題】(2分)回溯法的算法框架按照問(wèn)題的解空間一般分為子集樹(shù)算法框架與（）算法框架。A.深度優(yōu)先生成樹(shù)B.排列樹(shù)C.二叉樹(shù)D.廣度優(yōu)先生成樹(shù)3【判斷題】(2分)判斷：回溯算法是嘗試搜索算法中最為基本的一種算法，其采用了一種走不通就掉頭的思想作為其控制結(jié)構(gòu)。（）A.錯(cuò)B.對(duì)4【單選題】(2分)用回溯法解0/1背包問(wèn)題時(shí)，該問(wèn)題的解空間結(jié)構(gòu)為（）結(jié)構(gòu)。A.子集樹(shù)B.都可以C.都不對(duì)D.排列樹(shù)5【單選題】(2分)旅行售貨員問(wèn)題的解空間樹(shù)是（）。A.都可以B.都不對(duì)C.排列樹(shù)D.子集樹(shù)6【單選題】(2分)下面哪種函數(shù)是回溯法中為避免無(wú)效搜索采取的策略（）A.隨機(jī)數(shù)函數(shù)B.搜索函數(shù)C.遞歸函數(shù)D.剪枝函數(shù)7【單選題】(2分)回溯法的效率不依賴于下列哪些因素（）A.計(jì)算約束函數(shù)的時(shí)間B.確定解空間的時(shí)間C.滿足顯約束的值的個(gè)數(shù)D.計(jì)算限界函數(shù)的時(shí)間8【單選題】(2分)關(guān)于回溯搜索法的介紹下面（）是不正確描述。A.回溯法有“通用解題法”之稱，它可以系統(tǒng)地搜索一個(gè)問(wèn)題的所有解或任意解。B.回溯法是一種既帶系統(tǒng)性又帶有跳躍性的搜索算法C.回溯算法需要借助隊(duì)列這種結(jié)構(gòu)來(lái)保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑D.回溯算法在生成解空間的任一結(jié)點(diǎn)時(shí)先判斷該結(jié)點(diǎn)是否可能包含問(wèn)題的解如果肯定不包含則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索逐層向祖先結(jié)點(diǎn)回溯9【單選題】(2分)用回溯法求解子集樹(shù)問(wèn)題，子集樹(shù)有2^n個(gè)葉結(jié)點(diǎn)，遍歷該子集樹(shù)的算法時(shí)間復(fù)雜度通常為（）A.O(n^2)B.O(2^n)C.O(n)D.O(logn)10【單選題】(2分)回溯法主要有迭代回溯法和（）回溯法兩種編程實(shí)現(xiàn)方法。A.深度優(yōu)先B.非遞歸C.并行D.遞歸第六章測(cè)試1【單選題】(2分)分支限界法在問(wèn)題的解空間樹(shù)中，按（）策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)A.深度優(yōu)先B.活結(jié)點(diǎn)優(yōu)先C.廣度優(yōu)先D.擴(kuò)展結(jié)點(diǎn)優(yōu)先2【單選題】(2分)常見(jiàn)的兩種分支限界法為（）A.隊(duì)列式（FIFO）分支限界法與優(yōu)先隊(duì)列式分支限界法B.廣度優(yōu)先分支限界法和深度優(yōu)先分支限界法C.隊(duì)列式（FIFO）分支限界法與堆棧式分支限界法D.排列樹(shù)法和子集樹(shù)法3【單選題】(2分)優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是（）。A.后進(jìn)先出B.先進(jìn)先出C.結(jié)點(diǎn)的優(yōu)先級(jí)D.隨機(jī)4【單選題】(2分)分支限界法的搜索策略是：在擴(kuò)展結(jié)點(diǎn)處，先生成其（）兒子結(jié)點(diǎn)（分支），然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展對(duì)點(diǎn)。A.任意多個(gè)B.所有的C.一個(gè)D.二個(gè)5【單選題】(2分)優(yōu)先隊(duì)列式分支限界法通常用以下（）數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。A.棧B.堆C.隊(duì)列D.二叉查找樹(shù)6【判斷題】(2分)判斷：分支限界法類似于回溯法，也是一種在問(wèn)題的解空間樹(shù)T上搜索問(wèn)題解的算法，兩者的求解目標(biāo)是相同的。（）A.對(duì)B.錯(cuò)7【判斷題】(2分)判斷：旅行商問(wèn)題中，分支限界法的目標(biāo)是找出滿足約束條件的所有解。（）A.對(duì)B.錯(cuò)8【判斷題】(2分)判斷：優(yōu)先