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

智慧樹知到《算法分析與設(shè)計(jì)》章節(jié)測(cè)試答案第一章1、給定一個(gè)實(shí)例，如果一個(gè)算法能得到正確解答，稱這個(gè)算法解答了該問題。A:對(duì)B:錯(cuò)答案:錯(cuò)2、一個(gè)問題的同一實(shí)例可以有不同的表示形式A:對(duì)B:錯(cuò)答案:對(duì)3、同一數(shù)學(xué)模型使用不同的數(shù)據(jù)結(jié)構(gòu)會(huì)有不同的算法，有效性有很大差別。A:對(duì)B:錯(cuò)答案:對(duì)4、問題的兩個(gè)要素是輸入和實(shí)例。A:對(duì)B:錯(cuò)答案:錯(cuò)5、算法與程序的區(qū)別是（）A:輸入B:輸出C:確定性D:有窮性答案:有窮性6、解決問題的基本步驟是（）。（1）算法設(shè)計(jì)（2）算法實(shí)現(xiàn)（3）數(shù)學(xué)建模（4）算法分析（5）正確性證明A:(3)(1)(4)(5)(2)B:(3)(4)(1)(5)(2)C:(3)(1)(5)(4)(2)D:(1)(2)(3)(4)(5)答案:(3)(1)(5)(4)(2)7、下面說法關(guān)于算法與問題的說法錯(cuò)誤的是（）。A:如果一個(gè)算法能應(yīng)用于問題的任意實(shí)例，并保證得到正確解答，稱這個(gè)算法解答了該問題。B:算法是一種計(jì)算方法，對(duì)問題的每個(gè)實(shí)例計(jì)算都能得到正確答案。C:同一問題可能有幾種不同的算法，解題思路和解題速度也會(huì)顯著不同。D:證明算法不正確，需要證明對(duì)任意實(shí)例算法都不能正確處理。答案:證明算法不正確，需要證明對(duì)任意實(shí)例算法都不能正確處理。8、下面關(guān)于程序和算法的說法正確的是（）。A:算法的每一步驟必須要有確切的含義，必須是清楚的、無二義的。B:程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。C:程序總是在有窮步的運(yùn)算后終止。D:算法是一個(gè)過程，計(jì)算機(jī)每次求解是針對(duì)問題的一個(gè)實(shí)例求解。答案:算法的每一步驟必須要有確切的含義，必須是清楚的、無二義的。,程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。,算法是一個(gè)過程，計(jì)算機(jī)每次求解是針對(duì)問題的一個(gè)實(shí)例求解。9、最大獨(dú)立集問題和（）問題等價(jià)。A:最大團(tuán)B:最小頂點(diǎn)覆蓋C:區(qū)間調(diào)度問題D:穩(wěn)定匹配問題答案:最大團(tuán),最小頂點(diǎn)覆蓋10、給定兩張喜歡列表，穩(wěn)定匹配問題的輸出是（）。A:完美匹配B:沒有不穩(wěn)定配對(duì)C:最大匹配D:穩(wěn)定匹配答案:完美匹配,沒有不穩(wěn)定配對(duì),最大匹配,穩(wěn)定匹配11、問題變換的目的有（）。(1)復(fù)雜變簡(jiǎn)單(2)未知變已知(3)隱式變顯式(4)難解變易解（5）以上都是。A:（1）B:（2）C:（3）D:（4）E:（5）答案:（5）12、按照霍納法則，計(jì)算p(x)=anxn+an-1xn-1+…+a1x1+a0的數(shù)量級(jí)為____。A:n^2B:nC:nlognD:logn答案:n第十二章1、有多項(xiàng)式時(shí)間算法的問題是易解問題A:對(duì)B:錯(cuò)答案:2、EXP類是所有指數(shù)時(shí)間可解的判定問題組成的問題類A:對(duì)B:錯(cuò)答案:3、如果對(duì)于X的任意實(shí)例，通過多項(xiàng)式次的計(jì)算步驟，加多項(xiàng)式次調(diào)用Y的算法，可解決X，則X可多項(xiàng)式時(shí)間歸約到Y(jié)。A:對(duì)B:錯(cuò)答案:4、如果X問題Y且Y不能多項(xiàng)式時(shí)間解決,那么X也不能多項(xiàng)式時(shí)間解決。A:對(duì)B:錯(cuò)答案:5、下面關(guān)于NP問題說法正確的是（）A:NP問題都是不可能解決的問題B:P類問題包含在NP類問題中C:NP完全問題是P類問題的子集D:NP類問題包含在P類問題中答案:6、P類問題可以（）。A:多項(xiàng)式時(shí)間計(jì)算B:指數(shù)時(shí)間計(jì)算C:指數(shù)時(shí)間驗(yàn)證答案:7、下面屬于NP完全問題的是（）A:SATB:最大獨(dú)立集C:最小頂點(diǎn)覆蓋D:旅行商問題答案:8、以下關(guān)于判定問題難易處理的敘述中錯(cuò)誤的是A:可以由多項(xiàng)式時(shí)間算法求解的問題是難處理的B:需要超過多項(xiàng)式時(shí)間算法求解的問題是易處理的C:可以由多項(xiàng)式時(shí)間算法求解的問題是易處理的D:需要超過多項(xiàng)式時(shí)間算法求解的問題是不能處理的答案:9、下列說法錯(cuò)誤的是A:IfX多項(xiàng)式時(shí)間歸約到Y(jié)andY多項(xiàng)式時(shí)間歸約到Z,thenX多項(xiàng)式時(shí)間歸約到Z.B:P包含于NPC:判定問題可多項(xiàng)式時(shí)間變換到優(yōu)化問題D:如果一個(gè)NP完全問題有多項(xiàng)式時(shí)間算法，那么NP中的每一個(gè)問題都可以有多項(xiàng)式時(shí)間算法答案:第二章1、時(shí)間復(fù)雜度是指算法最壞情況下的運(yùn)行時(shí)間。A:對(duì)B:錯(cuò)答案:對(duì)2、f(n)=O(g(n))則f(n)2=O(g(n)2)A:對(duì)B:錯(cuò)答案:對(duì)3、f(n)=3n3+7n2+4nlogn=O（n2）A:對(duì)B:錯(cuò)答案:錯(cuò)4、如果一個(gè)算法是多項(xiàng)式時(shí)間算法，該算法是有效的,是好算法。A:對(duì)B:錯(cuò)答案:對(duì)5、從資源劃分，算法的復(fù)雜度分為（）和（）。A:時(shí)間復(fù)雜度空間復(fù)雜度B:空間復(fù)雜度平均復(fù)雜度C:最好復(fù)雜度最壞復(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ì)事前分析第三章1、0-1背包問題的枚舉算法的時(shí)間復(fù)雜度為O（2n）A:對(duì)B:錯(cuò)答案:B2、增量構(gòu)造法生成子集前需要對(duì)集合中元素從小到大排列。A:對(duì)B:錯(cuò)答案:A3、分塊查找一般設(shè)分塊的長(zhǎng)度是n/2.A:對(duì)B:錯(cuò)答案:B4、枚舉法適用于問題的小規(guī)模實(shí)例。A:對(duì)B:錯(cuò)答案:A5、便于實(shí)現(xiàn)集合操作的子集生成算法是（）A:增量構(gòu)造法B:位向量法C:二進(jìn)制法答案:C6、從所有候選答案中去搜索正確的解，這是（）算法。A:蠻力B:枚舉C:遞推答案:B7、logn2=()(logn+5)A:θB:OC:WD:o答案:A8、0-1背包問題的枚舉算法，如果在百萬(wàn)次每秒的計(jì)算機(jī)上運(yùn)行，1年可以計(jì)算的問題規(guī)模估計(jì)是？A:40B:60C:30D:50答案:A9、分?jǐn)?shù)拆分問題的枚舉算法通過（）方法進(jìn)行了優(yōu)化。A:減少枚舉變量B:減少枚舉變量的值域C:優(yōu)化數(shù)據(jù)結(jié)構(gòu)D:優(yōu)化數(shù)學(xué)模型答案:ABD10、下面那些算法的時(shí)間復(fù)雜度為O（）?A:順序查找B:折半查找C:插入排序D:冒泡排序E:折半插入排序答案:插入排序、折半插入排序、冒泡排序第四章1、貪心算法總能找到可行解，但未必是最優(yōu)解。A:對(duì)B:錯(cuò)答案:A2、貪心選擇通過一步步選擇得到問題的解，每一步的局部最優(yōu)解都構(gòu)成全局最優(yōu)解的一部分。A:對(duì)B:錯(cuò)答案:A3、問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法或動(dòng)態(tài)規(guī)劃算法求解的關(guān)鍵特征。A:對(duì)B:錯(cuò)答案:A4、如果圖G中每條邊的權(quán)重都是互不相同的，圖G必定只有一顆最小生成樹。A:對(duì)B:錯(cuò)答案:A5、Kruskal算法的貪婪準(zhǔn)則是每一次選取不構(gòu)成環(huán)路的最小邊。A:對(duì)B:錯(cuò)答案:A6、貪心算法基本要素有（）和最優(yōu)子結(jié)構(gòu)性質(zhì)。A:分解合并性質(zhì)B:獨(dú)立子問題性質(zhì)C:貪心選擇性質(zhì)D:重疊子問題性質(zhì)答案:C7、下面不是證明貪心算法證明方法的有（）。A:領(lǐng)先B:優(yōu)化C:交換論證D:界答案:B8、未來與過去無關(guān)指的是（）的性質(zhì)A:貪心選擇B:無后效性C:最優(yōu)子結(jié)構(gòu)D:重疊子問題答案:B9、最小生成樹問題可以使用的算法有（）A:KruskalB:PrimC:SolimD:Dijkstra答案:Kruskal、Prim、Solim10、區(qū)間問題包含()A:區(qū)間調(diào)度B:區(qū)間劃分C:區(qū)間選點(diǎn)D:區(qū)間覆蓋答案:ABCD第五章1、正推是從小規(guī)模的問題推解出大規(guī)模間題的一種方法。A:對(duì)B:錯(cuò)答案:A2、一般來說，遞歸的效率高于遞推。A:對(duì)B:錯(cuò)答案:B3、從大規(guī)模問題逐步化為小規(guī)模問題的算法是（）A:遞歸B:正推C:倒推D:迭代答案:A4、求解高階遞推方程一般使用（）迭代方法A:差消迭代B:換元迭代C:直接迭代答案:A5、下面有關(guān)遞歸與迭代的說法錯(cuò)誤的是（）A:遞歸與迭代都是解決“重復(fù)操作”的機(jī)制。B:遞歸算法的實(shí)現(xiàn)往往要比迭代算法耗費(fèi)更多的時(shí)間。C:每個(gè)迭代算法原則上總可以轉(zhuǎn)換成與它等價(jià)的遞歸算法。D:每個(gè)遞歸算法原則上總可以轉(zhuǎn)換成與它等價(jià)的迭代算法答案: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:Ω(n^2)B:n(n+1)/2C:O(n^2)D:θ(n^2)答案:Ω(n^2)、n(n+1)/2、O(n^2)、θ(n^2)9、遞歸一般用于解決問題有（）A:數(shù)據(jù)的定義是按遞歸定義的B:問題解法按遞歸實(shí)現(xiàn)C:數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的D:迭代問題答案:ABC10、主方法可以求解滿足T(n)=aT(n/b)+f(n)形式的遞推方程，則下列關(guān)于方程中的約束中不準(zhǔn)確的是？設(shè)εA:對(duì)于系數(shù)a，必須滿足a>=1B:對(duì)于系數(shù)b，必須滿足b>1C:若對(duì)于常數(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:對(duì)B:錯(cuò)答案:A2、N個(gè)元素排序的時(shí)間復(fù)雜度不可能是線性時(shí)間。A:對(duì)B:錯(cuò)答案:B3、三分法的判定樹是三叉樹。A:對(duì)B:錯(cuò)答案:A4、減治法減一個(gè)常量就是每次迭代減去一個(gè)相同的常數(shù)因子(一般為2)A:對(duì)B:錯(cuò)答案:B5、設(shè)有5000個(gè)無序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用()法。A:冒泡排序B:快速排序C:合并排序D:基數(shù)排序答案:A6、堆排序的時(shí)間復(fù)雜度是O（）。A:O（n）B:O（2n）C:O（n2）D:O（nlogn）答案:D7、以下不可以使用分治法求解的是（）。A:棋盤覆蓋問題B:線性選擇問題C:歸并排序D:0/1背包問題答案:D8、改進(jìn)分治算法的方法有（）和改進(jìn)劃分的對(duì)稱性。A:減少子問題數(shù)B:備忘錄C:擬陣原理D:加速原理答案:A9、通過減少子問題個(gè)數(shù)，降低分治算法時(shí)間復(fù)雜度的有（）A:大整數(shù)乘法B:Strassen矩陣乘法C:線性時(shí)間選擇D:最接近點(diǎn)對(duì)答案:AB10、分治法在每一層遞歸上有三個(gè)步驟（）A:分解B:解決C:合并D:選擇答案:分解、解決、合并第七章1、動(dòng)態(tài)規(guī)劃算法把原問題分為交叉的子問題，解決子問題，記錄子問題的解，合并為原問題的解。A:對(duì)B:錯(cuò)答案:A2、0/1背包問題的動(dòng)態(tài)規(guī)劃算法是多項(xiàng)式時(shí)間算法。A:對(duì)B:錯(cuò)答案:B3、對(duì)于稀疏圖，F(xiàn)loyd算法的效率要高于執(zhí)行n次Dijkstra算法，也要高于執(zhí)行n次SPFA算法。A:對(duì)B:錯(cuò)答案:B4、Dijkstra算法在求解過程中，源點(diǎn)到集合S內(nèi)各頂點(diǎn)的最短路徑一旦求出，則之后不變了，修改的僅僅是源點(diǎn)到還沒選擇的頂點(diǎn)的最短路徑長(zhǎng)度。A:對(duì)B:錯(cuò)答案:A5、含負(fù)權(quán)的最短路問題一般使用（）求解。A:動(dòng)態(tài)規(guī)劃B:貪心算法C:分治算法D:網(wǎng)絡(luò)流算法答案:A6、動(dòng)態(tài)規(guī)劃算法的基本要素有（）和最優(yōu)子結(jié)構(gòu)性質(zhì)。A:分解合并性質(zhì)B:獨(dú)立子問題性質(zhì)C:貪心選擇性質(zhì)D:重疊子問題性質(zhì)答案:D7、下面不是動(dòng)態(tài)規(guī)劃的基本方法有（）。A:多重選擇B:增加變量C:舍入D:區(qū)間變量答案:C8、最短路算法中適用于稀疏圖的是（）A:Floyd算法B:SPFA算法C:Bellman算法D:Dijkstra算法答案:SPFA算法、Bellman算法、Dijkstra算法9、動(dòng)態(tài)規(guī)劃算法的特點(diǎn)（）A:自底向上計(jì)算B:自頂向下計(jì)算C:從大到小計(jì)算D:從小到大計(jì)算答案:從小到大計(jì)算、自底向上計(jì)算10、備忘錄算法的特點(diǎn)（）A:自底向上計(jì)算B:自頂向下計(jì)算C:從大到小計(jì)算D:從小到大計(jì)算答案:自頂向下計(jì)算、從大到小計(jì)算第八章1、回溯法是按廣度優(yōu)先策略搜索解空間樹。A:對(duì)B:錯(cuò)答案:B2、死結(jié)點(diǎn)是正在產(chǎn)生兒子的結(jié)點(diǎn)。A:對(duì)B:錯(cuò)答案:B3、回溯法的一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間。A:對(duì)B:錯(cuò)答案:A第九章1、分支限界法在對(duì)問題的解空間樹進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)有多次機(jī)會(huì)成為活結(jié)點(diǎn)。A:對(duì)B:錯(cuò)答案:B2、分支限界法找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。A:對(duì)B:錯(cuò)答案:A3、隊(duì)列式分支限界法以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。A:對(duì)B:錯(cuò)答案:B4、優(yōu)先隊(duì)列式分支限界法按照隊(duì)列先進(jìn)先出的原則，選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。A:對(duì)B:錯(cuò)答案:B5、下列算法中不能解決0/1背包問題的是A:貪心法B:動(dòng)態(tài)規(guī)劃C:回溯法D:分支限界法答案:A6、分支限界法解旅行商問題時(shí)的解空間樹是A:子集樹B:排列樹C:深度優(yōu)先生成樹D:廣度優(yōu)先生成樹答案:B7、優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是A:先進(jìn)先出B:后進(jìn)先出C:結(jié)點(diǎn)的優(yōu)先級(jí)D:隨機(jī)答案:C8、用分支限界法設(shè)計(jì)算法的步驟是：A:針對(duì)所給問題，定義問題的解空間（對(duì)解進(jìn)行編碼）B:確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）C:定義最優(yōu)子結(jié)構(gòu)D:以廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索答案:ABD9、分支限界法與回溯法的不同點(diǎn)是什么？A:求解目標(biāo)不同B:搜索方式不同C:對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同D:存儲(chǔ)空間的要求不同答案:ABCD10、FIFO是（）的搜索方式。A:回溯算法B:分支限界C:動(dòng)態(tài)規(guī)劃D:貪心算法答案:B第十章1、網(wǎng)絡(luò)流滿足容量約束，但一般不滿足流量守恒約束。A:對(duì)B:錯(cuò)答案:B2、設(shè)G=<V1,V2,E>為二分圖,|V1|≤|V2|,M為G中一個(gè)最大匹配,且|M|=|V1|,則稱M為G的完備匹配，也是最大匹配。A:對(duì)B:錯(cuò)答案:A3、存在割(A,B)使流值v(f)=割的容量cap(A,B).，則割(A,B)是最小割。A:對(duì)B:錯(cuò)答案:A4、給定連通圖G,BFS遍歷得到層次圖，如果同一層中的結(jié)點(diǎn)無邊相連，則G是二分圖。A:對(duì)B:錯(cuò)答案:A5、有下界的流通問題不一定有可行流。A:對(duì)B:錯(cuò)答案:A6、Dinic算法的時(shí)間復(fù)雜度為（）A:mn2B:mnC:m2nD:m2logC答案:A7、如果每條邊的最大容量為1，則時(shí)間復(fù)雜度是O（nm）的網(wǎng)絡(luò)流算法有A:FF算法B:容量縮放算法C:EK算法D:Dinic算法答案:A8、給定二分圖G=<V,E>中無孤立點(diǎn)，|V|=n，其最大流算法求得最大流f,則G的（）=n-fA:最大獨(dú)立數(shù)B:最大匹配數(shù)C:最小頂點(diǎn)覆蓋D:最小邊覆蓋答案:9、改進(jìn)FF網(wǎng)絡(luò)流算法，可以通過選擇（）增廣路，降低時(shí)間復(fù)雜度。A:最大容量B:最短路徑C:最大瓶頸容量D:邊數(shù)最少答案:ABCD10、帶需求的流通必須滿足供給和=需求和A:對(duì)B:錯(cuò)答案:A第十一章1、蒙特卡羅算法的結(jié)果肯定是一個(gè)正確解。A:對(duì)B:錯(cuò)答案:B2、Sherwood算法隨機(jī)選擇一個(gè)數(shù)組元素作為劃分標(biāo)準(zhǔn)求解k小元素問題,保證線性時(shí)間的平均性能。A:對(duì)B:錯(cuò)答案:A3、借助隨機(jī)預(yù)處理技術(shù)，不改變?cè)械拇_定性算法，僅對(duì)其輸入進(jìn)行隨機(jī)洗牌，可收到舍伍德算法的效果。A:對(duì)B:錯(cuò)答案:A4、隨機(jī)算法共同點(diǎn)是計(jì)算時(shí)間越多或運(yùn)行次數(shù)越多,正確性越高.A:對(duì)B:錯(cuò)答案:A5、增加拉斯維加斯算法的反復(fù)求解次數(shù),可使求解無效的概率任意小。A:對(duì)B:錯(cuò)答案:A6、在下列算法中有時(shí)找不到問題解的是A:蒙特卡羅算法B:拉斯維加斯算法C:舍伍德算法D:數(shù)值隨機(jī)算法答案:拉斯維加斯算法7、肯定獲得可行解，但不一定是正確解的算法是A:蒙特卡羅算法B:拉斯維加斯算法C:舍伍德算法D:數(shù)值隨機(jī)算法答案:A8、在一般輸入數(shù)據(jù)的程序里，輸入多少會(huì)影響到算法的計(jì)算復(fù)雜度，為了消除這種影響可用（）對(duì)輸入進(jìn)行預(yù)處理。A:蒙特卡羅算法B:拉斯維加斯算法C:舍伍德算法D:數(shù)值隨機(jī)化算法答案:C9、