算法分析與設(shè)計(jì)知到智慧樹(shù)章節(jié)測(cè)試課后答案2024年秋山東財(cái)經(jīng)大學(xué)

算法分析與設(shè)計(jì)知到智慧樹(shù)章節(jié)測(cè)試課后答案2024年秋山東財(cái)經(jīng)大學(xué)第一章單元測(cè)試

一個(gè)問(wèn)題的同一實(shí)例可以有不同的表示形式

A:對(duì)B:錯(cuò)

答案:對(duì)同一數(shù)學(xué)模型使用不同的數(shù)據(jù)結(jié)構(gòu)會(huì)有不同的算法，有效性有很大差別。

A:錯(cuò)B:對(duì)

答案:對(duì)問(wèn)題的兩個(gè)要素是輸入和實(shí)例。

A:錯(cuò)B:對(duì)

答案:錯(cuò)算法與程序的區(qū)別是（）

A:輸入B:確定性C:有窮性D:輸出

答案:有窮性解決問(wèn)題的基本步驟是（）。（1）算法設(shè)計(jì)（2）算法實(shí)現(xiàn)（3）數(shù)學(xué)建模（4）算法分析（5）正確性證明

A:(3)(4)(1)(5)(2)B:(3)(1)(5)(4)(2)C:(3)(1)(4)(5)(2)D:(1)(2)(3)(4)(5)

答案:(3)(1)(5)(4)(2)下面說(shuō)法關(guān)于算法與問(wèn)題的說(shuō)法錯(cuò)誤的是（）。

A:同一問(wèn)題可能有幾種不同的算法，解題思路和解題速度也會(huì)顯著不同。B:如果一個(gè)算法能應(yīng)用于問(wèn)題的任意實(shí)例，并保證得到正確解答，稱(chēng)這個(gè)算法解答了該問(wèn)題。C:證明算法不正確，需要證明對(duì)任意實(shí)例算法都不能正確處理。D:算法是一種計(jì)算方法，對(duì)問(wèn)題的每個(gè)實(shí)例計(jì)算都能得到正確答案。

答案:證明算法不正確，需要證明對(duì)任意實(shí)例算法都不能正確處理。下面關(guān)于程序和算法的說(shuō)法正確的是（）。

A:算法的每一步驟必須要有確切的含義，必須是清楚的、無(wú)二義的。B:算法是一個(gè)過(guò)程，計(jì)算機(jī)每次求解是針對(duì)問(wèn)題的一個(gè)實(shí)例求解。C:程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。D:程序總是在有窮步的運(yùn)算后終止。

答案:算法的每一步驟必須要有確切的含義，必須是清楚的、無(wú)二義的。；算法是一個(gè)過(guò)程，計(jì)算機(jī)每次求解是針對(duì)問(wèn)題的一個(gè)實(shí)例求解。；程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。最大獨(dú)立集問(wèn)題和（）問(wèn)題等價(jià)。

A:最大團(tuán)B:穩(wěn)定匹配問(wèn)題C:最小頂點(diǎn)覆蓋D:區(qū)間調(diào)度問(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)復(fù)雜變簡(jiǎn)單(2)未知變已知(3)隱式變顯式(4)難解變易解（5）以上都是。

A:（3）

B:（2）

C:（1）

D:（5）E:（4）

答案:（5）按照霍納法則，計(jì)算p(x)=anxn

+an-1xn-1+…+a1x1+a0

的數(shù)量級(jí)為_(kāi)___。

A:nlogn

B:n

C:n^2

D:logn

答案:n

第二章單元測(cè)試

時(shí)間復(fù)雜度是指算法最壞情況下的運(yùn)行時(shí)間。

A:對(duì)B:錯(cuò)

答案:對(duì)f(n)=3n3+7n2+4nlogn=O（n2）

A:對(duì)B:錯(cuò)

答案:錯(cuò)如果一個(gè)算法是多項(xiàng)式時(shí)間算法，該算法是有效的,是好算法。

A:錯(cuò)B:對(duì)

答案:對(duì)算法復(fù)雜度分析的兩種基本方法為（

）和（

）。

A:結(jié)構(gòu)化方法

面向?qū)ο蠓椒˙:幾何復(fù)雜度

平均復(fù)雜度C:平攤復(fù)雜度

平滑復(fù)雜度D:事后統(tǒng)計(jì)

事前分析

答案:事后統(tǒng)計(jì)

事前分析下面程序的時(shí)間復(fù)雜度為（）

x=1fori=1ton

doforj=1toido

fork=1tojdo

x++

A:O(n^3)B:O(n^2)C:O(nlogn)D:O(n)

答案:O(n^3)對(duì)近似遞增序列的線性表從小到大排序，使用哪種方法好？

A:歸并排序B:快速排序C:堆排序D:插入排序

答案:插入排序順序查找適合的數(shù)據(jù)結(jié)構(gòu)是（）

A:壓縮存儲(chǔ)B:鏈?zhǔn)酱鎯?chǔ)C:順序存儲(chǔ)D:散列存儲(chǔ)

答案:鏈?zhǔn)酱鎯?chǔ)；順序存儲(chǔ)給定n個(gè)元素的數(shù)組A，n=10^3,使用折半查找比使用順序查找大約快___倍。

A:10^(3/2)

B:1000

C:10

D:100

答案:100

則f(n)的漸進(jìn)性態(tài)f(n)=Ω(

)

A:100

B:n^2

C:n

D:1

答案:1

f=O(g)當(dāng)且僅當(dāng)g=Ω(f)

A:錯(cuò)B:對(duì)

答案:對(duì)

第三章單元測(cè)試

0-1背包問(wèn)題的枚舉算法的時(shí)間復(fù)雜度為O（2n）

A:對(duì)B:錯(cuò)

答案:錯(cuò)增量構(gòu)造法生成子集前需要對(duì)集合中元素從小到大排列。

A:錯(cuò)B:對(duì)

答案:對(duì)分塊查找一般設(shè)分塊的長(zhǎng)度是n/2.

A:對(duì)B:錯(cuò)

答案:錯(cuò)枚舉法適用于問(wèn)題的小規(guī)模實(shí)例。

A:錯(cuò)B:對(duì)

答案:對(duì)便于實(shí)現(xiàn)集合操作的子集生成算法是（）

A:二進(jìn)制法B:位向量法C:增量構(gòu)造法

答案:二進(jìn)制法從所有候選答案中去搜索正確的解，這是

（）算法。

A:蠻力B:遞推C:枚舉

答案:枚舉logn2=(

)(logn+5)

A:wB:oC:O

D:θ

答案:θ0-1背包問(wèn)題的枚舉算法，如果在百萬(wàn)次每秒的計(jì)算機(jī)上運(yùn)行，1年可以計(jì)算的問(wèn)題規(guī)模估計(jì)是？

A:50B:60C:30D:40

答案:40分?jǐn)?shù)拆分問(wèn)題的枚舉算法通過(guò)（）方法進(jìn)行了優(yōu)化。

A:減少枚舉變量的值域B:優(yōu)化數(shù)據(jù)結(jié)構(gòu)C:優(yōu)化數(shù)學(xué)模型D:減少枚舉變量

答案:減少枚舉變量的值域；優(yōu)化數(shù)學(xué)模型；減少枚舉變量下面那些算法的時(shí)間復(fù)雜度為O（）?

A:插入排序B:折半查找C:順序查找D:冒泡排序E:折半插入排序

答案:插入排序；冒泡排序；折半插入排序A公司處理器速度是B公司的100倍。對(duì)于復(fù)雜度為n^2的算法，B公司的計(jì)算機(jī)可以在1小時(shí)內(nèi)處理規(guī)模為n的問(wèn)題，A公司的計(jì)算機(jī)在1小時(shí)能處理的問(wèn)題規(guī)模是（）

A:n

B:100n

C:10n

D:n^2

答案:10n

冒泡排序的時(shí)間復(fù)雜度為Ω(n^2)

A:對(duì)B:錯(cuò)

答案:錯(cuò)

第四章單元測(cè)試

貪心算法總能找到可行解，但未必是最優(yōu)解。

A:錯(cuò)B:對(duì)

答案:對(duì)貪心選擇通過(guò)一步步選擇得到問(wèn)題的解，每一步的局部最優(yōu)解都構(gòu)成全局最優(yōu)解的一部分。

A:錯(cuò)B:對(duì)

答案:對(duì)問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用貪心算法或動(dòng)態(tài)規(guī)劃算法求解的關(guān)鍵特征。

A:對(duì)B:錯(cuò)

答案:對(duì)Kruskal算法的貪婪準(zhǔn)則是每一次選取不構(gòu)成環(huán)路的最小邊。

A:對(duì)B:錯(cuò)

答案:對(duì)貪心算法基本要素有（

）和最優(yōu)子結(jié)構(gòu)性質(zhì)。

A:獨(dú)立子問(wèn)題性質(zhì)B:重疊子問(wèn)題性質(zhì)C:貪心選擇性質(zhì)D:分解合并性質(zhì)

答案:貪心選擇性質(zhì)下面不是證明貪心算法證明方法的有（）。

A:優(yōu)化B:界C:交換論證D:領(lǐng)先

答案:優(yōu)化最小生成樹(shù)問(wèn)題可以使用的算法有（

）

A:KruskalB:PrimC:DijkstraD:Solim

答案:Kruskal；Prim；Solim區(qū)間問(wèn)題包含()

A:區(qū)間調(diào)度B:區(qū)間選點(diǎn)C:區(qū)間劃分D:區(qū)間覆蓋

答案:區(qū)間調(diào)度；區(qū)間選點(diǎn)；區(qū)間劃分；區(qū)間覆蓋負(fù)權(quán)的單源最短路問(wèn)題可以使用Dijkstra算法求解

A:對(duì)B:錯(cuò)

答案:錯(cuò)設(shè)C是一個(gè)環(huán)，f是C中的最大邊，那么最小生成樹(shù)中肯定包含f。

A:對(duì)B:錯(cuò)

答案:錯(cuò)

第五章單元測(cè)試

正推是從小規(guī)模的問(wèn)題推解出大規(guī)模間題的一種方法。

A:錯(cuò)B:對(duì)

答案:對(duì)一般來(lái)說(shuō)，遞歸的效率高于遞推。

A:錯(cuò)B:對(duì)

答案:錯(cuò)從大規(guī)模問(wèn)題逐步化為小規(guī)模問(wèn)題的算法是（）

A:遞歸B:正推C:倒推D:迭代

答案:遞歸求解高階遞推方程一般使用（）迭代方法

A:直接迭代B:換元迭代C:差消迭代

答案:差消迭代遞歸函數(shù)的要素是（）

A:邊界條件B:輸入C:迭代D:遞歸方程

答案:邊界條件；遞歸方程遞歸變?yōu)榉沁f歸的方法有（）

A:尾遞歸B:模擬棧C:循環(huán)D:遞推

答案:尾遞歸；模擬棧；遞推T(n)=T(n-1)+n，T(1)=1，則T(n)=（）

A:θ(n^2)B:n(n+1)/2C:Ω(n^2)D:O(n^2)

答案:θ(n^2)；n(n+1)/2；Ω(n^2)；O(n^2)

遞歸一般用于解決問(wèn)題有（）

A:數(shù)據(jù)的定義是按遞歸定義的B:數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的C:迭代問(wèn)題D:問(wèn)題解法按遞歸實(shí)現(xiàn)

答案:數(shù)據(jù)的定義是按遞歸定義的；數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的；問(wèn)題解法按遞歸實(shí)現(xiàn)主方法可以求解滿(mǎn)足T(n)=aT(n/b)+f(n)形式的遞推方程，則下列關(guān)于方程中的約束中不準(zhǔn)確的是？設(shè)

A:若f(n)=O(x)，則T(n)=Θ(xlogn)B:若對(duì)于常數(shù)e>0，f(n)=O(y)，則T(n)=Θ(x)C:對(duì)于系數(shù)a，必須滿(mǎn)足a>=1D:對(duì)于系數(shù)b，必須滿(mǎn)足b>1

答案:若f(n)=O(x)，則T(n)=Θ(xlogn)，則T(n)=（）

A:Ω(n^3)B:O(nlogn)C:O(n)D:Θ(n^2)

答案:Θ(n^2)循環(huán)用于重復(fù)性的工作。循環(huán)體的特點(diǎn)是：“以不變應(yīng)萬(wàn)變”。

A:對(duì)B:錯(cuò)

答案:對(duì)

第六章單元測(cè)試

分治法分解的子問(wèn)題與原問(wèn)題形式相同。

A:對(duì)B:錯(cuò)

答案:對(duì)N個(gè)元素排序的時(shí)間復(fù)雜度不可能是線性時(shí)間。

A:錯(cuò)B:對(duì)

答案:錯(cuò)三分法的判定樹(shù)是三叉樹(shù)。

A:對(duì)B:錯(cuò)

答案:對(duì)減治法減一個(gè)常量就是每次迭代減去一個(gè)相同的常數(shù)因子(一般為2)

A:錯(cuò)B:對(duì)

答案:錯(cuò)設(shè)有5000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用(

)法。

A:合并排序B:基數(shù)排序C:快速排序D:冒泡排序

答案:冒泡排序堆排序的時(shí)間復(fù)雜度是O（）。

A:O（n）B:O（2n）C:O（nlogn）D:O（n2）

答案:O（nlogn）改進(jìn)分治算法的方法有（

）和改進(jìn)劃分的對(duì)稱(chēng)性。

A:擬陣原理B:減少子問(wèn)題數(shù)C:備忘錄D:加速原理

答案:減少子問(wèn)題數(shù)通過(guò)減少子問(wèn)題個(gè)數(shù)，降低分治算法時(shí)間復(fù)雜度的有（）

A:最接近點(diǎn)對(duì)B:大整數(shù)乘法C:Strassen矩陣乘法D:線性時(shí)間選擇

答案:大整數(shù)乘法；Strassen矩陣乘法分治法在每一層遞歸上有三個(gè)步驟（）

A:選擇B:分解C:合并D:解決

答案:分解；合并；解決

使用分治法求解不需要滿(mǎn)足的條件是（）。

A:原問(wèn)題和子問(wèn)題使用相同的方法求解B:子問(wèn)題的解可以合并C:子問(wèn)題必須是一樣的D:子問(wèn)題不能夠重復(fù)

答案:子問(wèn)題必須是一樣的最小堆中每個(gè)元素調(diào)整的次數(shù)不超過(guò)樹(shù)高。

A:對(duì)B:錯(cuò)

答案:對(duì)分治算法的思想是將難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的子問(wèn)題，以便各個(gè)擊破，分而治之。

A:對(duì)B:錯(cuò)

答案:對(duì)任何排序算法至少需要O(nlogn)次比較。

A:錯(cuò)B:對(duì)

答案:錯(cuò)找n個(gè)元素的中位數(shù)的分治算法的時(shí)間復(fù)雜度為O().

A:n^2B:n

C:lognD:nlogn

答案:n

第七章單元測(cè)試

動(dòng)態(tài)規(guī)劃算法把原問(wèn)題分為交叉的子問(wèn)題，解決子問(wèn)題，記錄子問(wèn)題的解，合并為原問(wèn)題的解。

A:對(duì)B:錯(cuò)

答案:對(duì)0/1背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法是多項(xiàng)式時(shí)間算法。

A:對(duì)B:錯(cuò)

答案:錯(cuò)對(duì)于稀疏圖，F(xiàn)loyd算法的效率要高于執(zhí)行n次Dijkstra算法，也要高于執(zhí)行n次SPFA算法。

A:對(duì)B:錯(cuò)

答案:錯(cuò)Dijkstra算法在求解過(guò)程中，源點(diǎn)到集合S內(nèi)各頂點(diǎn)的最短路徑一旦求出，則之后不變了，修改的僅僅是源點(diǎn)到還沒(méi)選擇的頂點(diǎn)的最短路徑長(zhǎng)度。

A:錯(cuò)B:對(duì)

答案:對(duì)含負(fù)權(quán)的最短路問(wèn)題一般使用（）求解。

A:動(dòng)態(tài)規(guī)劃B:貪心算法C:分治算法D:網(wǎng)絡(luò)流算法

答案:動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算法的基本要素有（

）和最優(yōu)子結(jié)構(gòu)性質(zhì)。

A:貪心選擇性質(zhì)B:獨(dú)立子問(wèn)題性質(zhì)C:分解合并性質(zhì)D:重疊子問(wèn)題性質(zhì)

答案:重疊子問(wèn)題性質(zhì)下面不是動(dòng)態(tài)規(guī)劃的基本方法有（）。

A:舍入B:多重選擇C:增加變量D:區(qū)間變量

答案:舍入最短路算法中適用于稀疏圖的是（）

A:Bellman算法B:Dijkstra算法C:Floyd算法D:SPFA算法

答案:Bellman算法；Dijkstra算法；SPFA算法分治算法與動(dòng)態(tài)規(guī)劃算法的相同點(diǎn)是（）

A:最優(yōu)子結(jié)構(gòu)B:遞推關(guān)系C:子問(wèn)題獨(dú)立

D:子問(wèn)題重疊

答案:最優(yōu)子結(jié)構(gòu)；遞推關(guān)系DAG上最短路，固定起點(diǎn)和終點(diǎn)沒(méi)有意義。

A:對(duì)B:錯(cuò)

答案:錯(cuò)DAG圖最長(zhǎng)路的遞推函數(shù)d(i)表示從某個(gè)頂點(diǎn)i出發(fā)的最長(zhǎng)路長(zhǎng)度。

A:錯(cuò)B:對(duì)

答案:對(duì)樹(shù)上最大權(quán)獨(dú)立集不包含u，可能包含兒子結(jié)點(diǎn)，也可能不包含兒子結(jié)點(diǎn)。

A:對(duì)B:錯(cuò)

答案:對(duì)SPFA算法的時(shí)間復(fù)雜度為O（mn）

A:對(duì)B:錯(cuò)

答案:對(duì)

第八章單元測(cè)試

回溯法是按廣度優(yōu)先策略搜索解空間樹(shù)。

A:錯(cuò)B:對(duì)

答案:錯(cuò)死結(jié)點(diǎn)是正在產(chǎn)生兒子的結(jié)點(diǎn)。

A:對(duì)B:錯(cuò)

答案:錯(cuò)回溯法的一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間。

A:對(duì)B:錯(cuò)

答案:對(duì)回溯法不適用于解一些組合數(shù)相當(dāng)大的問(wèn)題。

A:對(duì)B:錯(cuò)

答案:錯(cuò)好的約束函數(shù)能顯著地減少所生成的結(jié)點(diǎn)數(shù)。但這樣的約束函數(shù)往往計(jì)算量較大。因此，在選擇約束函數(shù)時(shí)通常存在生成結(jié)點(diǎn)數(shù)與約束函數(shù)計(jì)算量之間的折衷。

A:對(duì)B:錯(cuò)

答案:對(duì)下列算法中，通常以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的是（

）。

A:回溯法B:動(dòng)態(tài)規(guī)劃法C:貪心法D:備忘錄法

答案:回溯法裝載問(wèn)題的回溯算法所需的計(jì)算時(shí)間為

A:O（n2）B:O（n）C:O（nlogn）D:O（2n）

答案:O（2n）問(wèn)題的狀態(tài)生成法有（）

A:深度優(yōu)先生成法B:寬度優(yōu)先生成法C:子集樹(shù)生成法D:排列樹(shù)生成法

答案:深度優(yōu)先生成法；寬度優(yōu)先生成法回溯法解題步驟

A:以深度優(yōu)先方式搜索解空間，在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。B:針對(duì)所給問(wèn)題，定義問(wèn)題的解空間C:確定易于搜索的解空間結(jié)構(gòu)D:確定最優(yōu)子結(jié)構(gòu)的性質(zhì)

答案:以深度優(yōu)先方式搜索解空間，在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。；針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；確定易于搜索的解空間結(jié)構(gòu)回溯法的效率依賴(lài)于下列哪些因素（

）

A:計(jì)算約束函數(shù)的時(shí)間

B:確定解空間的時(shí)間C:計(jì)算限界函數(shù)的時(shí)間D:滿(mǎn)足顯約束的值的個(gè)數(shù)

答案:計(jì)算約束函數(shù)的時(shí)間

；計(jì)算限界函數(shù)的時(shí)間；滿(mǎn)足顯約束的值的個(gè)數(shù)剪枝函數(shù)包括（）和約束函數(shù)

A:限界函數(shù)

B:最優(yōu)函數(shù)C:估計(jì)函數(shù)D:啟發(fā)式函數(shù)

答案:限界函數(shù)

回溯法搜索解空間時(shí)，在搜索試探時(shí)選取x[i]的值順序是任意的，順序?qū)τ谟?jì)算量沒(méi)有差別。

A:錯(cuò)B:對(duì)

答案:錯(cuò)回溯法中，如果解空間樹(shù)是排列樹(shù)，所給問(wèn)題的規(guī)模為n時(shí)，遍歷排列樹(shù)需O(n!)計(jì)算時(shí)間.

A:對(duì)B:錯(cuò)

答案:對(duì)回溯法的兩種解空間樹(shù)為（）

A:排列樹(shù)

B:子集樹(shù)C:遞歸樹(shù)D:祖先樹(shù)

答案:排列樹(shù)

；子集樹(shù)

第九章單元測(cè)試

分支限界法在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)有多次機(jī)會(huì)成為活結(jié)點(diǎn)。

A:錯(cuò)B:對(duì)

答案:錯(cuò)分支限界法找出滿(mǎn)足約束條件的一個(gè)解，或是在滿(mǎn)足約束條件的解中找出在某種意義下的最優(yōu)解。

A:對(duì)B:錯(cuò)

答案:對(duì)隊(duì)列式分支限界法以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。

A:對(duì)B:錯(cuò)

答案:錯(cuò)優(yōu)先隊(duì)列式分支限界法按照隊(duì)列先進(jìn)先出的原則，選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。

A:對(duì)B:錯(cuò)

答案:錯(cuò)分支限界法解旅行商問(wèn)題時(shí)的解空間樹(shù)是

A:深度優(yōu)先生成樹(shù)B:排列樹(shù)C:子集樹(shù)D:廣度優(yōu)先生成樹(shù)

答案:排列樹(shù)優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是

A:先進(jìn)先出B:隨機(jī)C:結(jié)點(diǎn)的優(yōu)先級(jí)D:后進(jìn)先出

答案:結(jié)點(diǎn)的優(yōu)先級(jí)用分支限界法設(shè)計(jì)算法的步驟是：

A:以廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索B:確定易于搜索的解空間結(jié)構(gòu)（按樹(shù)或圖組織解）C:針對(duì)所給問(wèn)題，定義問(wèn)題的解空間（對(duì)解進(jìn)行編碼）D:定義最優(yōu)子結(jié)構(gòu)

答案:以廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索；確定易于搜索的解空間結(jié)構(gòu)（按樹(shù)或圖組織解）；針對(duì)所給問(wèn)題，定義問(wèn)題的解空間（對(duì)解進(jìn)行編碼）分支限界法與回溯法的不同點(diǎn)是什么？

A:存儲(chǔ)空間的要求不同B:求解目標(biāo)不同C:對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同D:搜索方式不同

答案:存儲(chǔ)空間的要求不同；求解目標(biāo)不同；對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同；搜索方式不同F(xiàn)IFO是（

）的搜索方式。

A:貪心算法

B:動(dòng)態(tài)規(guī)劃C:回溯算法D:分支限界

答案:分支限界

下面說(shuō)法不正確的是（）

A:使用限界函數(shù)作優(yōu)先級(jí),第一個(gè)加入隊(duì)列的葉子就是最優(yōu)解B:回溯和分支限界都是動(dòng)態(tài)生成解空間樹(shù)C:用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿(mǎn)足約束的子樹(shù)D:用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)

答案:使用限界函數(shù)作優(yōu)先級(jí),第一個(gè)加入隊(duì)列的葉子就是最優(yōu)解在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)的是（

）。

A:回溯

B:分支限界

C:回溯和分支限界

D:回溯求解子集樹(shù)問(wèn)題

答案:分支限界

使用限界函數(shù)作優(yōu)先級(jí),第一個(gè)擴(kuò)展的葉子就是最優(yōu)解

A:對(duì)B:錯(cuò)

答案:對(duì)分支限界法不能解決0/1背包問(wèn)題

A:對(duì)B:錯(cuò)

答案:錯(cuò)

第十章單元測(cè)試

網(wǎng)絡(luò)流滿(mǎn)足容量約束，但一般不滿(mǎn)足流量守恒約束。

A:錯(cuò)B:對(duì)

答案:錯(cuò)設(shè)G=<V1,V2,E>為二分圖,|V1|≤|V2|,M為G中一個(gè)最大匹配,且|M|=|V1|,則稱(chēng)M為G的完備匹配，也是最大匹配。

A:錯(cuò)B:對(duì)

答案:對(duì)存在割(A,B)

使流值v(f)=割的容量cap(A,B)，則割(A,B)是最小割。

A:錯(cuò)B:對(duì)

答案:對(duì)給定連通圖G,BFS遍歷得到層次圖，如果同一層中的結(jié)點(diǎn)無(wú)邊相連，則G是二分圖。

A:對(duì)B:錯(cuò)

答案:對(duì)有下界的流通問(wèn)題不一定有可行流。

A:錯(cuò)B:對(duì)

答案:對(duì)Dinic算法的時(shí)間復(fù)雜度為（）

A:m2nB:mn2C:m2logCD:mn

答案:mn2如果每條邊的最大容量為1，則時(shí)間復(fù)雜度是O(nm)的網(wǎng)絡(luò)流算法有

A:容量縮放算法B:Dinic算法C:FF算法D:EK算法

答案:FF算法改進(jìn)FF網(wǎng)絡(luò)流算法，可以通過(guò)選擇（

）增廣路，降低時(shí)間復(fù)雜度。

A:最短路徑B:最大容量C:最大瓶頸容量D:邊數(shù)最少

答案:最短路徑；最大容量；最大瓶頸容量；邊數(shù)最少帶需求的流通必須滿(mǎn)足供給和=需求和

A:對(duì)B:錯(cuò)

答案:對(duì)匈牙利算法中起點(diǎn)和終點(diǎn)都是未匹配點(diǎn)的交錯(cuò)路徑稱(chēng)為可增廣路徑，可增廣路徑有奇數(shù)條邊。

A:錯(cuò)B:對(duì)

答案:對(duì)給定二分圖G=<V,E>中無(wú)孤立點(diǎn)，其最大流算法求得最大流f,則G的最大匹配數(shù)=f.

A:錯(cuò)B:對(duì)

答案:對(duì)設(shè)G=<V,E>中無(wú)孤立點(diǎn)。W為G的最小邊覆蓋,若G中存在相鄰邊就移去其中一條。設(shè)移去的邊集為N，則W-N是G的最大匹配。

A:對(duì)B:錯(cuò)

答案:對(duì)設(shè)f是網(wǎng)絡(luò)N的任意流，(A,B)是N的任意s-t割，則流值f至多等于割的容量。

A:對(duì)B:錯(cuò)

答案:對(duì)

第十一章單元測(cè)試

蒙特卡羅算法的結(jié)果肯定是一個(gè)正確解。

A:錯(cuò)B:對(duì)

答案:錯(cuò)Sherwood算法隨機(jī)選擇一個(gè)數(shù)組元素作為劃分標(biāo)準(zhǔn)求解k小元素問(wèn)題,保證線性時(shí)間的平均性能。

A:對(duì)B:錯(cuò)

答案:對(duì)借助隨機(jī)預(yù)處理技術(shù)，不改變?cè)械拇_定性算法，僅對(duì)其輸入進(jìn)行隨機(jī)洗牌，可收到舍伍德算法的效果。

A:錯(cuò)B:對(duì)

答案:對(duì)隨機(jī)算法共同點(diǎn)是計(jì)算時(shí)間越多或運(yùn)行次數(shù)越多,正確性越高.

A:對(duì)B:錯(cuò)

答案:對(duì)增加拉斯維加斯算法的反復(fù)求解次數(shù),可使求解無(wú)效的概率任意小。

A:錯(cuò)B:對(duì)

答案:對(duì)在下列算法中有時(shí)找不到問(wèn)題解的是

A:數(shù)值隨機(jī)算法B:蒙特卡羅算法C:拉斯維加斯算法D:舍伍德算法

答案:拉斯維加斯算法肯定獲得可行解，但不一定是正確解的算法是

A:蒙特卡羅算法B:舍伍德算法C:拉斯維加斯算法D:數(shù)值隨機(jī)算法

答案:蒙特卡羅算法在一般輸入數(shù)據(jù)的程序里，輸入多少會(huì)影響到算法的計(jì)算復(fù)雜度，為了消除這種影響可用（

）對(duì)輸入進(jìn)行預(yù)處理。

A:數(shù)值隨機(jī)化算法B:舍伍德算法C:蒙特卡羅算法D:拉斯維加斯算法

答案:舍伍德算法下面說(shuō)法正確的是

A:蒙特卡羅算法總是能提供問(wèn)題的一個(gè)解,但可能給出錯(cuò)誤解。B:舍伍德算法的精髓不是避免最壞的情況，而是設(shè)法消除最壞情況和特定實(shí)例的關(guān)聯(lián)性。C:求解同一實(shí)例用同一隨機(jī)化算法求解兩次，所用時(shí)間和所得結(jié)果可能完全不同。D:現(xiàn)實(shí)計(jì)算機(jī)上無(wú)法產(chǎn)生真正的隨機(jī)數(shù)

答案:蒙特卡羅算法總是能提供問(wèn)題的一個(gè)解,但可能給出錯(cuò)誤解。；舍伍德算法的精髓不是避免最壞的情況，而是設(shè)法消除最壞情況和特定實(shí)例的關(guān)聯(lián)性。；求解同一實(shí)例用同一隨機(jī)化算法求解兩次，所用時(shí)間和所得結(jié)果可能完全不同。；現(xiàn)實(shí)計(jì)算機(jī)上無(wú)法產(chǎn)生真正的隨機(jī)數(shù)下面說(shuō)法正確的是（）

A:增加蒙特卡羅算法的求解次數(shù),可使求解錯(cuò)誤的概率任意小。B:隨機(jī)算法是一種使用概率和統(tǒng)計(jì)方法在其執(zhí)行過(guò)程中對(duì)于下一計(jì)算步驟作出隨機(jī)選擇的算法C:當(dāng)最壞和平均情況差別較大時(shí),舍伍德算法可以消除好壞實(shí)例的差別，達(dá)到平均實(shí)例的性能D:線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法

答案:增加蒙特卡羅算法的求解次數(shù),可使求解錯(cuò)誤的概率任意小。；隨機(jī)算法是一種使用概率和統(tǒng)計(jì)方法在其執(zhí)行過(guò)程中對(duì)于下一計(jì)算步驟作出隨機(jī)選擇的算法；當(dāng)最壞和平均情況差別較大時(shí),舍伍德算法可以消除好壞實(shí)例的差別，達(dá)到平均實(shí)例的性能；線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法確定性算法的每一計(jì)算步驟都確定,求解同一實(shí)例用同一算法求解兩次，所得結(jié)果完全相同。

A:對(duì)B:錯(cuò)

答案:對(duì)舍伍德算法總是有解,且解總是正確的，但最壞性能未改變。

A:對(duì)B:錯(cuò)

答案:錯(cuò)拉斯維加斯算法肯定得到一個(gè)正確解。

A:對(duì)B:錯(cuò)

答案:錯(cuò)隨機(jī)抽取數(shù)組元素k次,從最接近搜索元素x的位置順序搜索,

順序搜索的平均比較次數(shù)為O(n/(k+1)).

A:錯(cuò)B:對(duì)

答案:對(duì)

第十二章單元測(cè)試

有多項(xiàng)式時(shí)間算法的問(wèn)題是易解問(wèn)題

A:錯(cuò)B:對(duì)

答案:對(duì)EXP類(lèi)是所有指數(shù)時(shí)間可解的判定問(wèn)題組成的問(wèn)題類(lèi)

A:錯(cuò)B:對(duì)

答案:對(duì)如果對(duì)于X的任意實(shí)例，通過(guò)多項(xiàng)式次的計(jì)算步驟，加多項(xiàng)式次調(diào)用Y的算法，可解決X，則X可多項(xiàng)式時(shí)間歸約到Y(jié)。

A:錯(cuò)B:對(duì)

答案:對(duì)下面關(guān)于NP問(wèn)題說(shuō)法正確的是（

）

A:NP完全問(wèn)題是P類(lèi)問(wèn)題的子集B:NP類(lèi)問(wèn)題包含在P類(lèi)問(wèn)題中C:NP問(wèn)題都是不可能解決的問(wèn)題D:P類(lèi)問(wèn)題包含在NP類(lèi)問(wèn)題中

答案:P類(lèi)問(wèn)題包含在NP類(lèi)問(wèn)題中下面屬于NP完全問(wèn)題的是（）

A:旅行商問(wèn)題B:SATC:最小頂點(diǎn)覆蓋D:最大獨(dú)立集

答案:旅行商問(wèn)題；SAT；最小頂點(diǎn)覆蓋；最大獨(dú)立集以下關(guān)于判定問(wèn)題難易處理的敘述中錯(cuò)誤的是

A:需要超過(guò)多項(xiàng)式時(shí)間算法求解的問(wèn)題是易處理的B:可以由多項(xiàng)式時(shí)間算法求解的問(wèn)題是易處理的C:需要超過(guò)多項(xiàng)式時(shí)間算法求解的問(wèn)題是不能處理的D:可以由多項(xiàng)式時(shí)間算法求解的問(wèn)題是難處理的

答案:需要超過(guò)多項(xiàng)式時(shí)間算法求解的問(wèn)題是易處理的；需要超過(guò)多項(xiàng)式