智慧樹知到《算法分析與設計》章節(jié)測試答案

1、智慧樹知到算法分析與設計章節(jié)測試答案第一章1、給定一個實例，如果一個算法能得到正確解答，稱這個算法解答了該問題。A:對B:錯答案: 錯2、一個問題的同一實例可以有不同的表示形式A:對B:錯答案: 對3、同一數(shù)學模型使用不同的數(shù)據(jù)結構會有不同的算法，有效性有很大差別。A:對B:錯答案: 對4、問題的兩個要素是輸入和實例。A:對B:錯答案: 錯5、算法與程序的區(qū)別是（）A:輸入B:輸出C:確定性D:有窮性答案: 有窮性6、解決問題的基本步驟是（）。（1）算法設計（2）算法實現(xiàn)（3）數(shù)學建模（4）算法分析（5）正確性證明A:(3)(1)(4)(5)(2)B:(3)(4)(1)(5)(2)C:(3)(

2、1)(5)(4)(2)D:(1)(2)(3)(4)(5)答案: (3)(1)(5)(4)(2)7、下面說法關于算法與問題的說法錯誤的是（）。A:如果一個算法能應用于問題的任意實例，并保證得到正確解答，稱這個算法解答了該問題。B:算法是一種計算方法，對問題的每個實例計算都能得到正確答案。C:同一問題可能有幾種不同的算法，解題思路和解題速度也會顯著不同。D:證明算法不正確，需要證明對任意實例算法都不能正確處理。答案: 證明算法不正確，需要證明對任意實例算法都不能正確處理。8、下面關于程序和算法的說法正確的是（）。A:算法的每一步驟必須要有確切的含義，必須是清楚的、無二義的。B:程序是算法用某種程序

3、設計語言的具體實現(xiàn)。C:程序總是在有窮步的運算后終止。D:算法是一個過程，計算機每次求解是針對問題的一個實例求解。答案: 算法的每一步驟必須要有確切的含義，必須是清楚的、無二義的。,程序是算法用某種程序設計語言的具體實現(xiàn)。,算法是一個過程，計算機每次求解是針對問題的一個實例求解。9、最大獨立集問題和（）問題等價。A: 最大團B:最小頂點覆蓋C:區(qū)間調(diào)度問題D:穩(wěn)定匹配問題答案:  最大團,最小頂點覆蓋10、給定兩張喜歡列表，穩(wěn)定匹配問題的輸出是（  ） 。A:完美匹配B:沒有不穩(wěn)定配對C:最大匹配D:穩(wěn)定匹配答案: 完美匹配,沒有不穩(wěn)定配對,最大匹配,穩(wěn)

4、定匹配11、問題變換的目的有（）。(1)復雜變簡單 (2)未知變已知 (3)隱式變顯式 (4)難解變易解 （5）以上都是。A:（1）B:（2）C:（3）D:（4）E:（5）答案: （5）12、按照霍納法則，計算p(x) = anxn + an-1xn-1+ +a1x1+ a0  的數(shù)量級為_ 。A:n2B:nC:nlognD:logn答案: n第十二章1、有多項式時間算法的問題是易解問題A:對B:錯答案:2、EXP類是所有指數(shù)時間可解的判定問題組成的問題類A:對B:錯答案:3、如果對于X的任意實例，通過多項式次的計算步驟，加多項式次調(diào)用Y的算法，可解決X，則 X可多項式時間

5、歸約到Y。A:對B:錯答案:4、如果X問題Y且 Y不能多項式時間解決,那么X也不能多項式時間解決。A:對B:錯答案:5、下面關于NP問題說法正確的是（ ）A:NP問題都是不可能解決的問題B:P類問題包含在NP類問題中C:NP完全問題是P類問題的子集D:NP類問題包含在P類問題中答案:6、P類問題可以（ ）。A:多項式時間計算B:指數(shù)時間計算C:指數(shù)時間驗證答案:7、下面屬于NP完全問題的是（）A:SATB:最大獨立集C:最小頂點覆蓋D:旅行商問題答案:8、以下關于判定問題難易處理的敘述中錯誤的是A:可以由多項式時間算法求解的問題是難處理的B:需要超過多項式時間算法求解的問題是易處理的C:可以由

6、多項式時間算法求解的問題是易處理的D:需要超過多項式時間算法求解的問題是不能處理的答案:9、下列說法錯誤的是A:If X多項式時間歸約到Y and Y多項式時間歸約到Z, then X多項式時間歸約到Z.B:P包含于NPC:判定問題可多項式時間變換到優(yōu)化問題D:如果一個NP完全問題有多項式時間算法，那么NP中的每一個問題都可以有多項式時間算法答案:第二章1、時間復雜度是指算法最壞情況下的運行時間。A:對B:錯答案: 對2、f(n)=O(g(n)  則 f(n)2=O(g(n)2)A:對B:錯答案: 對3、f(n)=3n3+7n2+4nlogn =O（n2）A:對B:錯答案:

7、 錯4、如果一個算法是多項式時間算法，該算法是有效的,是好算法。A:對B:錯答案: 對5、從資源劃分，算法的復雜度分為（ ）和（）。A:時間復雜度  空間復雜度B: 空間復雜度   平均復雜度C:最好復雜度 最壞復雜度D:時間復雜度   平均復雜度答案: 時間復雜度  空間復雜度6、算法復雜度分析的兩種基本方法為（  ）和（    ）。A:結構化方法 面向?qū)ο蠓椒˙:事后統(tǒng)計  事前分析C:幾何復雜度  平均復雜度D:平攤復雜度 平滑復

8、雜度答案: 事后統(tǒng)計  事前分析第三章1、0-1背包問題的枚舉算法的時間復雜度為O（2n）A:對B:錯答案:B2、增量構造法生成子集前需要對集合中元素從小到大排列。A:對B:錯答案:A3、分塊查找一般設分塊的長度是n/2.A:對B:錯答案:B4、枚舉法適用于問題的小規(guī)模實例。A:對B:錯答案:A5、便于實現(xiàn)集合操作的子集生成算法是（）A:增量構造法B:位向量法C:二進制法答案:C6、從所有候選答案中去搜索正確的解，這是 （）算法。A:蠻力B:枚舉C:遞推答案:B7、logn2=(  )(logn+5)A:B:OC:WD:o答案:A8、0-1背包問題的枚舉

9、算法，如果在百萬次每秒的計算機上運行，1年可以計算的問題規(guī)模估計是？A:40B:60C:30D:50答案:A9、分數(shù)拆分問題的枚舉算法通過（）方法進行了優(yōu)化。A:減少枚舉變量B:減少枚舉變量的值域C:優(yōu)化數(shù)據(jù)結構D:優(yōu)化數(shù)學模型答案:ABD10、下面那些算法的時間復雜度為O（）?A:順序查找B:折半查找C:插入排序D:冒泡排序E:折半插入排序答案:插入排序、折半插入排序、冒泡排序第四章1、貪心算法總能找到可行解，但未必是最優(yōu)解。A:對B:錯答案:A2、貪心選擇通過一步步選擇得到問題的解，每一步的局部最優(yōu)解都構成全局最優(yōu)解的一部分。A:對B:錯答案:A3、問題的最優(yōu)子結構性質(zhì)是該問題可用貪心算法

10、或動態(tài)規(guī)劃算法求解的關鍵特征。A:對B:錯答案:A4、如果圖G中每條邊的權重都是互不相同的，圖G必定只有一顆最小生成樹。A:對B:錯答案:A5、Kruskal算法的貪婪準則是每一次選取不構成環(huán)路的最小邊。A:對B:錯答案:A6、貪心算法基本要素有（   ）和最優(yōu)子結構性質(zhì)。A:分解合并性質(zhì)B:獨立子問題性質(zhì)C:貪心選擇性質(zhì)D:重疊子問題性質(zhì)答案:C7、下面不是證明貪心算法證明方法的有（）。A:領先B:優(yōu)化C:交換論證D:界答案:B8、未來與過去無關指的是（  ）的性質(zhì)A:貪心選擇B:無后效性C:最優(yōu)子結構D:重疊子問題答案:B9、最小生成樹問題可以使用的

11、算法有（ ）A:KruskalB:PrimC:SolimD:Dijkstra答案:Kruskal、Prim、Solim10、區(qū)間問題包含()A:區(qū)間調(diào)度B:區(qū)間劃分C:區(qū)間選點D:區(qū)間覆蓋答案:ABCD第五章1、正推是從小規(guī)模的問題推解出大規(guī)模間題的一種方法。A:對B:錯答案:A2、一般來說，遞歸的效率高于遞推。A:對B:錯答案:B3、從大規(guī)模問題逐步化為小規(guī)模問題的算法是（）A:遞歸B:正推C:倒推D:迭代答案:A4、求解高階遞推方程一般使用（）迭代方法A:差消迭代B:換元迭代C:直接迭代答案:A5、下面有關遞歸與迭代的說法錯誤的是（）A:遞歸與迭代都是解決“重復操作”的機制。B:遞歸算法的

12、實現(xiàn)往往要比迭代算法耗費更多的時間。C:每個迭代算法原則上總可以轉(zhuǎn)換成與它等價的遞歸算法。D:每個遞歸算法原則上總可以轉(zhuǎn)換成與它等價的迭代算法答案:D6、遞歸函數(shù)的要素是（）A:邊界條件B:遞歸方程C:迭代D:輸入答案:AB7、遞歸變?yōu)榉沁f歸的方法有（）A:模擬棧B:遞推C:尾遞歸D:循環(huán)答案:模擬棧、遞推、尾遞歸8、T(n) = T(n-1) + n，T(1)=1，則 T(n) =（）A:(n2)B:n(n+1)/2C:O(n2)D:(n2)答案:(n2)、n(n+1)/2、O(n2)、(n2)9、 遞歸一般用于解決問題有（）A:數(shù)據(jù)的定義是按遞歸定義的B:問題解法按遞歸實現(xiàn)C:數(shù)據(jù)的結構形

13、式是按遞歸定義的D:迭代問題答案:ABC10、主方法可以求解滿足T(n)=aT(n/b) + f (n)形式的遞推方程，則下列關于方程中的約束中不準確的是？設A:對于系數(shù)a，必須滿足a>=1B:對于系數(shù)b，必須滿足b>1C:若對于常數(shù)>0，f(n)=O(y)，則T(n)=(x)D:若f(n)=O(x)，則T(n)=(xlogn)答案:若f(n)=O(nlogba)，則T(n)=(nlogbalogn)第六章1、分治法分解的子問題與原問題形式相同。A:對B:錯答案:A2、N個元素排序的時間復雜度不可能是線性時間。A:對B:錯答案:B3、三分法的判定樹是三叉樹。A:對B:錯答案:

14、A4、減治法減一個常量就是每次迭代減去一個相同的常數(shù)因子(一般為2)A:對B:錯答案:B5、設有5000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用(   )法。A:冒泡排序B:快速排序C:合并排序D:基數(shù)排序答案:A6、堆排序的時間復雜度是O（）。A: O（n）B:O（2n）C:O（n2）D: O（nlogn）答案:D7、以下不可以使用分治法求解的是（  ）。A:棋盤覆蓋問題B:線性選擇問題C:歸并排序D:0/1背包問題答案:D8、改進分治算法的方法有（ ）和改進劃分的對稱性。A:減少子問題數(shù)B:備忘錄C:擬陣原理D:加速原理答

15、案:A9、通過減少子問題個數(shù)，降低分治算法時間復雜度的有（）A:大整數(shù)乘法B:Strassen矩陣乘法C:線性時間選擇D:最接近點對答案:AB10、 分治法在每一層遞歸上有三個步驟（）A:分解B:解決C:合并D:選擇答案:分解、解決、合并第七章1、動態(tài)規(guī)劃算法把原問題分為交叉的子問題，解決子問題，記錄子問題的解，合并為原問題的解。A:對B:錯答案:A2、0/1背包問題的動態(tài)規(guī)劃算法是多項式時間算法。A:對B:錯答案:B3、對于稀疏圖，F(xiàn)loyd算法的效率要高于執(zhí)行n次Dijkstra算法，也要高于執(zhí)行n次SPFA算法。A:對B:錯答案:B4、Dijkstra算法在求解過程中，源點到集合S內(nèi)各頂

16、點的最短路徑一旦求出，則之后不變了，修改的僅僅是源點到還沒選擇的頂點的最短路徑長度。A:對B:錯答案:A5、含負權的最短路問題一般使用（）求解。A:動態(tài)規(guī)劃B:貪心算法C:分治算法D:網(wǎng)絡流算法答案:A6、動態(tài)規(guī)劃算法的基本要素有（ ）和最優(yōu)子結構性質(zhì)。A:分解合并性質(zhì)B:獨立子問題性質(zhì)C:貪心選擇性質(zhì)D:重疊子問題性質(zhì)答案:D7、下面不是動態(tài)規(guī)劃的基本方法有（）。A:多重選擇B:增加變量C:舍入D:區(qū)間變量答案:C8、最短路算法中適用于稀疏圖的是（）A:Floyd算法B:SPFA算法C: Bellman算法D:Dijkstra算法答案:SPFA算法、Bellman算法、Dijkstra算法9

17、、動態(tài)規(guī)劃算法的特點（）A:自底向上計算B:自頂向下計算C:從大到小計算D:從小到大計算答案:從小到大計算、自底向上計算10、 備忘錄算法的特點（）A:自底向上計算B:自頂向下計算C:從大到小計算D:從小到大計算答案:自頂向下計算、從大到小計算第八章1、回溯法是按廣度優(yōu)先策略搜索解空間樹。A:對B:錯答案:B2、死結點是正在產(chǎn)生兒子的結點。A:對B:錯答案:B3、回溯法的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。A:對B:錯答案:A第九章1、分支限界法在對問題的解空間樹進行搜索的方法中，一個活結點有多次機會成為活結點。A:對B:錯答案:B2、分支限界法找出滿足約束條件的一個解，或是在滿足

18、約束條件的解中找出在某種意義下的最優(yōu)解。A:對B:錯答案:A3、隊列式分支限界法以最小耗費優(yōu)先的方式搜索解空間樹。A:對B:錯答案:B4、優(yōu)先隊列式分支限界法按照隊列先進先出的原則，選取下一個節(jié)點為擴展結點。A:對B:錯答案:B5、下列算法中不能解決0/1背包問題的是A:貪心法B:動態(tài)規(guī)劃C:回溯法D:分支限界法答案:A6、分支限界法解旅行商問題時的解空間樹是A:子集樹B:排列樹C:深度優(yōu)先生成樹D:廣度優(yōu)先生成樹答案:B7、優(yōu)先隊列式分支限界法選取擴展結點的原則是A:先進先出B:后進先出C:結點的優(yōu)先級D:隨機答案:C8、用分支限界法設計算法的步驟是：A:針對所給問題，定義問題的解空間（對解

19、進行編碼）B:確定易于搜索的解空間結構（按樹或圖組織解）C:定義最優(yōu)子結構D:以廣度優(yōu)先或以最小耗費（最大收益）優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索答案:ABD9、分支限界法與回溯法的不同點是什么？A:求解目標不同B:搜索方式不同C:對擴展結點的擴展方式不同D:存儲空間的要求不同答案:ABCD10、FIFO是（  ）的搜索方式。A:回溯算法B:分支限界C:動態(tài)規(guī)劃D:貪心算法答案:B第十章1、網(wǎng)絡流滿足容量約束，但一般不滿足流量守恒約束。A:對B:錯答案:B2、設G = <V1, V2, E>為二分圖, |V1|V2|, M為G中一個最大匹

20、配, 且|M| = |V1|, 則稱M為G的完備匹配，也是最大匹配。A:對B:錯答案:A3、存在割 (A, B) 使流值 v(f) = 割的容量cap(A, B).，則割 (A, B)是最小割。A:對B:錯答案:A4、給定連通圖G, BFS遍歷得到層次圖，如果同一層中的結點無邊相連，則G是二分圖。A:對B:錯答案:A5、有下界的流通問題不一定有可行流。A:對B:錯答案:A6、Dinic算法的時間復雜度為（）A: mn2B:mnC:m2nD:  m2logC答案:A7、如果每條邊的最大容量為1，則時間復雜度是O（nm）的網(wǎng)絡流算法有A:FF算法B:容量縮放算法C:EK算法D:

21、 Dinic算法答案:A8、給定二分圖G = <V, E>中無孤立點，|V|=n，其最大流算法求得最大流f,則 G的（）=n-fA:最大獨立數(shù)B:最大匹配數(shù)C:最小頂點覆蓋D:最小邊覆蓋答案:9、改進FF網(wǎng)絡流算法，可以通過選擇（  ）增廣路，降低時間復雜度。A:最大容量B:最短路徑C: 最大瓶頸容量D:邊數(shù)最少答案:ABCD10、帶需求的流通必須滿足供給和 = 需求和A:對B:錯答案:A第十一章1、蒙特卡羅算法的結果肯定是一個正確解。A:對B:錯答案:B2、Sherwood算法隨機選擇一個數(shù)組元素作為劃分標準求解k小元素問題,保證線性時間的平均性能。A:對B:

22、錯答案:A3、借助隨機預處理技術，不改變原有的確定性算法，僅對其輸入進行隨機洗牌，可收到舍伍德算法的效果。A:對B:錯答案:A4、隨機算法共同點是計算時間越多或運行次數(shù)越多,正確性越高.A:對B:錯答案:A5、增加拉斯維加斯算法的反復求解次數(shù),可使求解無效的概率任意小。A:對B:錯答案:A6、在下列算法中有時找不到問題解的是A:蒙特卡羅算法B:拉斯維加斯算法C:舍伍德算法D:數(shù)值隨機算法答案:拉斯維加斯算法7、肯定獲得可行解，但不一定是正確解的算法是A:蒙特卡羅算法B:拉斯維加斯算法C:舍伍德算法D:數(shù)值隨機算法答案:A8、在一般輸入數(shù)據(jù)的程序里，輸入多少會影響到算法的計算復雜度，為了消除這種影響可用（  ）對輸入進行預處理。A:蒙特卡羅算法B:拉斯維加斯算法C:舍伍德算法D:數(shù)