1、最新資料歡迎閱讀2020智慧樹知到算法分析與設計章節測試完整答案智慧樹知到算法分析與設計章節測試答案第一章、給定一個實例，如果一個算法能得到正確解答，稱這個算法解答了該問題。答案：錯、一個問題的同一實例可以有不同的表示形式答案：對、同一數學模型使用不同的數據結構會有不同的算法，有效性有很大差別。答案：對、問題的兩個要素是輸入和實例。答案：錯、算法與程序的區別是（）A:輸入B:輸出C:確定性D:有窮性答案：有窮性、解決問題的基本步驟是（）。（1）算法設計算法實現（3）數學最新資料歡迎閱讀建模(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)答案：(1)(5)(4)(2)、下面說法關于算法與問題的說法錯誤的是()。A:如果一個算法能應用于問題的任意實例，并保證得到正確解答，稱這個算法解答了該問題。B:算法是一種計算方法，對問題的每個實例計算都能得到正確答 案。C:同一問題可能有幾種不同的算法，解題思路和解題速度也會顯 著不同。D:證明算法不正確，需要證明對任意實例算法都不能正確處理。答案：證明算法不正確，需要證明對任意實例算法都不能正確處 理。、下面關于程序和算法的說法正確的是()。A:算法的每一步驟必須要有確切的含義，必須是清楚的、無二義的。B:程序是算法用某種程序設計

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

4、)復雜變簡單(2)未知變已知(3)隱式變顯式(4)難解變易解(5)以上都是。A：(1)B：(2)C：(3)D：(4)E：(5)答案：(5)、按照霍納法則，計算 p(x) = anxn + an-1xn-1+a1x1+ a0的數量級為。A：nB:nC:nlognD:logn答案：n第十二章、有多項式時間算法的問題是易解問題答案：、EX陵是所有指數時間可解的判定問題組成的問題類最新資料歡迎閱讀答案：、如果對于X的任意實例，通過多項式次的計算步驟，加多項式次調用Y的算法，可解決X,則X可多項式時間歸約到Y。答案：、如果X問題Y且Y不能多項式時間解決，那么X也不能多項 式時間解決。答案：、下面關于NP

5、問題說法正確的是（）A:NP 問題都是不可能解決的問題B:P 類問題包含在NP類問題中C:NP完全問題是P類問題的子集D:NP類問題包含在P類問題中答案：、P類問題可以（）。A:多項式時間計算B:指數時間計算C:指數時間驗證答案：、下面屬于NP完全問題的是（）A:SATB:最大獨立集C:最小頂點覆蓋最新資料歡迎閱讀D:旅行商問題答案：、以下關于判定問題難易處理的敘述中錯誤的是A:可以由多項式時間算法求解的問題是難處理的B:需要超過多項式時間算法求解的問題是易處理的C:可以由多項式時間算法求解的問題是易處理的D:需要超過多項式時間算法求解的問題是不能處理的答案：、下列說法錯誤的是A:If X多項

6、式時間歸約到 Y and Y多項式時間歸約到 乙then X多項式時間歸約到Z.B:P 包含于NPC:判定問題可多項式時間變換到優化問題D:如果一個NP完全問題有多項式時間算法，那么NP中的每一個 問題都可以有多項式時間算法答案：第二章、時間復雜度是指算法最壞情況下的運行時間。答案：對、f(n)=O(g(n)則 f(n)2=O(g(n)2) 答案：對、f(n)=3n3+7n2+4nlogn =O(n2)最新資料歡迎閱讀答案：錯、如果一個算法是多項式時間算法，該算法是有效的，是好算法答案：對、從資源劃分，算法的復雜度分為()和()。A:時間復雜度空間復雜度B:空間復雜度平均復雜度C:最好復雜度最

7、壞復雜度D:時間復雜度平均復雜度答案：時間復雜度空間復雜度6 、算法復雜度分析的兩種基本方法為()和()。A:結構化方法面向對象方法B:事后統計事前分析C:幾何復雜度平均復雜度D:平攤復雜度平滑復雜度答案：事后統計事前分析第三章、0-1背包問題的枚舉算法的時間復雜度為O(2n)答案:B、增量構造法生成子集前需要對集合中元素從小到大排列最新資料歡迎閱讀答案:A3、分塊查找一般設分塊的長度是n/2.答案:B4 、枚舉法適用于問題的小規模實例。答案:A5、便于實現集合操作的子集生成算法是()A:增量構造法B:位向量法C:二進制法答案:C6、從所有候選答案中去搜索正確的解，這是 ()算法。A:蠻力B:

8、枚舉C:遞推答案:B7、logn2=( )(logn+5)A:B:OC:WD:o答案:A8 、0-1背包問題的枚舉算法，如果在百萬次每秒的計算機上運最新資料歡迎閱讀行，1年可以計算的問題規模估計是？A:40B:60C:30D:50答案:A9、分數拆分問題的枚舉算法通過()方法進行了優化。A:減少枚舉變量B:減少枚舉變量的值域C:優化數據結構D:優化數學模型答案:ABD10 、下面那些算法的時間復雜度為 0()?A:順序查找B:折半查找C:插入排序D:冒泡排序E:折半插入排序答案：插入排序、折半插入排序、冒泡排序第四章、貪心算法總能找到可行解，但未必是最優解。答案:A最新資料歡迎閱讀、貪心選擇通

9、過一步步選擇得到問題的解，每一步的局部最優解都構成全局最優解的一部分。答案:A、問題的最優子結構性質是該問題可用貪心算法或動態規劃算 法求解的關鍵特征。答案:A、如果圖G中每條邊的權重都是互不相同的，圖 G必定只有一 顆最小生成樹。答案:A、Kruskal算法的貪婪準則是每一次選取不構成環路的最小邊。答案:A、貪心算法基本要素有()和最優子結構性質。A:分解合并性質B:獨立子問題性質C:貪心選擇性質D:重疊子問題性質答案:C、下面不是證明貪心算法證明方法的有()。A:領先B:優化C:交換論證10最新資料歡迎閱讀D:界答案:B、未來與過去無關指的是()的性質A:貪心選擇B:無后效性C:最優子結構

10、D:重疊子問題答案:B、最小生成樹問題可以使用的算法有()A:KruskalB:PrimC:SolimD:Dijkstra答案:Kruskal、Prim、Solim、區間問題包含()A:區間調度B:區間劃分C:區間選點D:區間覆蓋11最新資料歡迎閱讀答案:ABCD第五章、正推是從小規模的問題推解出大規模間題的一種方法。答案:A、一般來說，遞歸的效率高于遞推。答案:B、從大規模問題逐步化為小規模問題的算法是（）A:遞歸B:正推C:倒推D:迭代答案:A、求解高階遞推方程一般使用（）迭代方法A:差消迭代B:換元迭代C:直接迭代答案:A、下面有關遞歸與迭代的說法錯誤的是（）A:遞歸與迭代都是解決“重復

11、操作”的機制。B:遞歸算法的實現往往要比迭代算法耗費更多的時間。C:每個迭代算法原則上總可以轉換成與它等價的遞歸算法。D:每個遞歸算法原則上總可以轉換成與它等價的迭代算法12最新資料歡迎閱讀答案:D、遞歸函數的要素是()A:邊界條件B:遞歸方程C:迭代D:輸入答案:AB、遞歸變為非遞歸的方法有()A:模擬棧B:遞推C:尾遞歸D:循環答案：模擬棧、遞推、尾遞歸、T(n) = T(n-1) + n , T(1)=1 ,則 T(n)=()A:(n )B:n(n+1)/2C:O(n )D:(n )答案:(n )、n(n+1)/2、O(n )、(n )、遞歸一般用于解決問題有()A:數據的定義是按遞歸定

12、義的B:問題解法按遞歸實現13最新資料歡迎閱讀C:數據的結構形式是按遞歸定義的D:迭代問題答案:ABC、主方法可以求解滿足 T(n)=aT(n/b) + f (n) 形式的遞推方 程，則下列關于方程中的約束中不準確的是 ？設 A:對于系數a,必須滿足a=1B:對于系數b,必須滿足b1若對于常數 0 , f(n)=O(y),貝U T(n)=(x)D:若 f(n)=O(x),貝U T(n)=(xlogn)答案：若 f(n)=O(nlogba),則 T(n)=(nlogbalogn)第六章、分治法分解的子問題與原問題形式相同。答案:A、 N個元素排序的時間復雜度不可能是線性時間。答案:B、三分法的判

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

14、題個數，降低分治算法時間復雜度的有（）A:大整數乘法B:Strassen矩陣乘法C:線性時間選擇D:最接近點對答案:AB、分治法在每一層遞歸上有三個步驟（）A:分解B:解決C:合并D:選擇答案：分解、解決、合并第七章、動態規劃算法把原問題分為交叉的子問題，解決子問題，記 錄子問題的解，合并為原問題的解。答案:A、0/1背包問題的動態規劃算法是多項式時間算法。16最新資料歡迎閱讀答案:B、對于稀疏圖，Floyd算法的效率要高于執行n次Dijkstra 算 法，也要高于執行n次SPF嶂法。答案:B、Dijkstra算法在求解過程中，源點到集合S內各頂點的最短 路徑一旦求出，則之后不變了，修改的僅僅

15、是源點到還沒選擇的頂點 的最短路徑長度。答案:A、含負權的最短路問題一般使用（）求解。A:動態規劃B:貪心算法C:分治算法D:網絡流算法答案:A、動態規劃算法的基本要素有（）和最優子結構性質。A:分解合并性質B:獨立子問題性質C:貪心選擇性質D:重疊子問題性質答案:D、下面不是動態規劃的基本方法有（）。A:多重選擇17最新資料歡迎閱讀B:增加變量C:舍入D:區間變量答案:C、最短路算法中適用于稀疏圖的是（）A:Floyd 算法B:SPFA算法C: Bellman算法D:Dijkstra算法答案:SPFA算法、Bellman算法、Dijkstra 算法、動態規劃算法的特點（）A:自底向上計算B:

16、自頂向下計算C:從大到小計算D:從小到大計算答案：從小到大計算、自底向上計算、備忘錄算法的特點（）A:自底向上計算B:自頂向下計算C:從大到小計算D:從小到大計算答案：自頂向下計算、從大到小計算18最新資料歡迎閱讀第八章、回溯法是按廣度優先策略搜索解空間樹答案:B、死結點是正在產生兒子的結點。答案:B、回溯法的一個顯著特征是在搜索過程中動態產生問題的解空 間。答案:A第九章、分支限界法在對問題的解空間樹進行搜索的方法中，一個活 結點有多次機會成為活結點。答案:B、分支限界法找出滿足約束條件的一個解，或是在滿足約束條 件的解中找出在某種意義下的最優解。答案:A、隊列式分支限界法以最小耗費優先的方

17、式搜索解空間樹。答案:B、優先隊列式分支限界法按照隊列先進先出的原則，選取下一 個節點為擴展結點19最新資料歡迎閱讀答案:B、下列算法中不能解決0/1背包問題的是A:貪心法B:動態規劃C:回溯法D:分支限界法答案:A、分支限界法解旅行商問題時的解空間樹是A:子集樹B:排列樹C:深度優先生成樹D:廣度優先生成樹答案:B、優先隊列式分支限界法選取擴展結點的原則是A:先進先出B:后進先出C:結點的優先級D:隨機答案:C、用分支限界法設計算法的步驟是：A:針對所給問題，定義問題的解空間（對解進彳f編碼）B:確定易于搜索的解空間結構（按樹或圖組織解）20最新資料歡迎閱讀C:定義最優子結構D:以廣度優先或

18、以最小耗費（最大收益）優先的方式搜索解空間， 并在搜索過程中用剪枝函數避免無效搜索答案:ABD、分支限界法與回溯法的不同點是什么？A:求解目標不同B:搜索方式不同C:對擴展結點的擴展方式不同D:存儲空間的要求不同答案:ABCD、FIFO是（）的搜索方式。A:回溯算法B:分支限界C:動態規劃D:貪心算法答案:B第十章、網絡流滿足容量約束，但一般不滿足流量守恒約束。答案:B、設6=為二分圖，|V1|V2|,M為G中一個最大匹配，且|M| = |V1|, 則稱M為G的完備匹配，也是最大匹配。答案:A21最新資料歡迎閱讀3、存在割(A, B) 使流值v(f)= 割的容量cap(A, B).,則割 (A

19、, B)是最小割。答案:A、給定連通圖G, BFS遍歷得到層次圖，如果同一層中的結點無 邊相連，則G是二分圖。答案:A、有下界的流通問題不一定有可行流。答案:A、Dinic算法的時間復雜度為()A: mn2B:mnC:m2nD: m2logC答案:A7 、如果每條邊的最大容量為1,則時間復雜度是O(nm)的網絡流 算法有A:FF 算法B:容量縮放算法C:EK算法22最新資料歡迎閱讀D: Dinic 算法答案:A、給定二分圖G =中無孤立點，|V|=n ,其最大流算法求得最 大流f,則G的(尸n-fA:最大獨立數B:最大匹配數C:最小頂點覆蓋D:最小邊覆蓋答案：、改進FF網絡流算法，可以通過選擇

20、()增廣路，降低時間復 雜度。A:最大容量B:最短路徑C:最大瓶頸容量D:邊數最少答案:ABCD10 、帶需求的流通必須滿足供給和=需求和答案:A第十一章、蒙特卡羅算法的結果肯定是一個正確解。答案:B、Sherwood算法隨機選擇一個數組元素作為劃分標準求解k小23最新資料歡迎閱讀元素問題，保證線性時間的平均性能。答案:A3、借助隨機預處理技術，不改變原有的確定性算法，僅對其輸 入進行隨機洗牌，可收到舍伍德算法的效果。答案:A4 、隨機算法共同點是計算時間越多或運行次數越多，正確性越高.答案:A5、增加拉斯維加斯算法的反復求解次數，可使求解無效的概率任 意小。答案:A6 、在下列算法中有時找不到問題解的是A:蒙特卡