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

3、語(yǔ)言的具體實(shí)現(xiàn)。C:程序總是在有窮步的運(yùn)算后終止。D:算法是一個(gè)過(guò)程，計(jì)算機(jī)每次求解是針對(duì)問(wèn)題的一個(gè)實(shí)例求最新資料歡迎閱讀答案：算法的每一步驟必須要有確切的含義， 必須是清楚的、無(wú)二義的。,程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。,算法是一個(gè)過(guò)程，計(jì)算機(jī)每次求解是針對(duì)問(wèn)題的一個(gè)實(shí)例求解。、最大獨(dú)立集問(wèn)題和()問(wèn)題等價(jià)。A: 最大團(tuán)B:最小頂點(diǎn)覆蓋C:區(qū)間調(diào)度問(wèn)題D:穩(wěn)定匹配問(wèn)題答案：最大團(tuán),最小頂點(diǎn)覆蓋、給定兩張喜歡列表，穩(wěn)定匹配問(wèn)題的輸出是 ()。A:完美匹配B:沒(méi)有不穩(wěn)定配對(duì)C:最大匹配D:穩(wěn)定匹配答案：完美匹配,沒(méi)有不穩(wěn)定配對(duì),最大匹配穩(wěn)定匹配最新資料歡迎閱讀、問(wèn)題變換的目的有()。(1

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

5、問(wèn)題說(shuō)法正確的是（）A:NP 問(wèn)題都是不可能解決的問(wèn)題B:P 類問(wèn)題包含在NP類問(wèn)題中C:NP完全問(wèn)題是P類問(wèn)題的子集D:NP類問(wèn)題包含在P類問(wèn)題中答案：、P類問(wèn)題可以（）。A:多項(xiàng)式時(shí)間計(jì)算B:指數(shù)時(shí)間計(jì)算C:指數(shù)時(shí)間驗(yàn)證答案：、下面屬于NP完全問(wèn)題的是（）A:SATB:最大獨(dú)立集C:最小頂點(diǎn)覆蓋最新資料歡迎閱讀D:旅行商問(wèn)題答案：、以下關(guān)于判定問(wèn)題難易處理的敘述中錯(cuò)誤的是A:可以由多項(xiàng)式時(shí)間算法求解的問(wèn)題是難處理的B:需要超過(guò)多項(xiàng)式時(shí)間算法求解的問(wèn)題是易處理的C:可以由多項(xiàng)式時(shí)間算法求解的問(wèn)題是易處理的D:需要超過(guò)多項(xiàng)式時(shí)間算法求解的問(wèn)題是不能處理的答案：、下列說(shuō)法錯(cuò)誤的是A:If X多項(xiàng)

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

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

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

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

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

11、操作”的機(jī)制。B:遞歸算法的實(shí)現(xiàn)往往要比迭代算法耗費(fèi)更多的時(shí)間。C:每個(gè)迭代算法原則上總可以轉(zhuǎn)換成與它等價(jià)的遞歸算法。D:每個(gè)遞歸算法原則上總可以轉(zhuǎn)換成與它等價(jià)的迭代算法12最新資料歡迎閱讀答案:D、遞歸函數(shù)的要素是()A:邊界條件B:遞歸方程C:迭代D:輸入答案:AB、遞歸變?yōu)榉沁f歸的方法有()A:模擬棧B:遞推C:尾遞歸D:循環(huán)答案：模擬棧、遞推、尾遞歸、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 )、遞歸一般用于解決問(wèn)題有()A:數(shù)據(jù)的定義是按遞歸定

12、義的B:問(wèn)題解法按遞歸實(shí)現(xiàn)13最新資料歡迎閱讀C:數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的D:迭代問(wèn)題答案:ABC、主方法可以求解滿足 T(n)=aT(n/b) + f (n) 形式的遞推方 程，則下列關(guān)于方程中的約束中不準(zhǔn)確的是 ？設(shè) A:對(duì)于系數(shù)a,必須滿足a=1B:對(duì)于系數(shù)b,必須滿足b1若對(duì)于常數(shù) 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)第六章、分治法分解的子問(wèn)題與原問(wèn)題形式相同。答案:A、 N個(gè)元素排序的時(shí)間復(fù)雜度不可能是線性時(shí)間。答案:B、三分法的判

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

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

15、是源點(diǎn)到還沒(méi)選擇的頂點(diǎn) 的最短路徑長(zhǎng)度。答案:A、含負(fù)權(quán)的最短路問(wèn)題一般使用（）求解。A:動(dòng)態(tài)規(guī)劃B:貪心算法C:分治算法D:網(wǎng)絡(luò)流算法答案:A、動(dòng)態(tài)規(guī)劃算法的基本要素有（）和最優(yōu)子結(jié)構(gòu)性質(zhì)。A:分解合并性質(zhì)B:獨(dú)立子問(wèn)題性質(zhì)C:貪心選擇性質(zhì)D:重疊子問(wèn)題性質(zhì)答案:D、下面不是動(dòng)態(tài)規(guī)劃的基本方法有（）。A:多重選擇17最新資料歡迎閱讀B:增加變量C:舍入D:區(qū)間變量答案:C、最短路算法中適用于稀疏圖的是（）A:Floyd 算法B:SPFA算法C: Bellman算法D:Dijkstra算法答案:SPFA算法、Bellman算法、Dijkstra 算法、動(dòng)態(tài)規(guī)劃算法的特點(diǎn)（）A:自底向上計(jì)算B:

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

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

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

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

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