智慧樹(shù)知道網(wǎng)課《算法分析與設(shè)計(jì)(山東聯(lián)盟)》課后章節(jié)測(cè)試滿分答案

第一章測(cè)試1【判斷題】(10分)一個(gè)問(wèn)題的同一實(shí)例可以有不同的表示形式A.錯(cuò)B.對(duì)2【判斷題】(10分)同一數(shù)學(xué)模型使用不同的數(shù)據(jù)結(jié)構(gòu)會(huì)有不同的算法，有效性有很大差別。A.錯(cuò)B.對(duì)3【判斷題】(10分)問(wèn)題的兩個(gè)要素是輸入和實(shí)例。A.對(duì)B.錯(cuò)4【單選題】(10分)算法與程序的區(qū)別是（）A.有窮性B.確定性C.輸出D.輸入5【單選題】(10分)解決問(wèn)題的基本步驟是（）。（1）算法設(shè)計(jì)（2）算法實(shí)現(xiàn)（3）數(shù)學(xué)建模（4）算法分析（5）正確性證明A.(3)(1)(5)(4)(2)B.(3)(4)(1)(5)(2)C.(1)(2)(3)(4)(5)D.(3)(1)(4)(5)(2)6【單選題】(10分)下面說(shuō)法關(guān)于算法與問(wèn)題的說(shuō)法的是（）。A.算法是一種計(jì)算方法，對(duì)問(wèn)題的每個(gè)實(shí)例計(jì)算都能得到正確答案。B.證明算法不正確，需要證明對(duì)任意實(shí)例算法都不能正確處理。C.如果一個(gè)算法能應(yīng)用于問(wèn)題的任意實(shí)例，并保證得到正確解答，稱(chēng)這個(gè)算法解答了該問(wèn)題。D.同一問(wèn)題可能有幾種不同的算法，解題思路和解題速度也會(huì)顯著不同。7【多選題】(10分)下面關(guān)于程序和算法的說(shuō)法正確的是（）。A.算法的每一步驟必須要有確切的含義，必須是清楚的、無(wú)二義的。B.程序總是在有窮步的運(yùn)算后終止。C.程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。D.算法是一個(gè)過(guò)程，計(jì)算機(jī)每次求解是針對(duì)問(wèn)題的一個(gè)實(shí)例求解。8【多選題】(10分)最大獨(dú)立集問(wèn)題和（）問(wèn)題等價(jià)。A.最大團(tuán)B.穩(wěn)定匹配問(wèn)題C.區(qū)間調(diào)度問(wèn)題D.最小頂點(diǎn)覆蓋9【多選題】(10分)給定兩張喜歡列表，穩(wěn)定匹配問(wèn)題的輸出是（）。A.完美匹配B.最大匹配C.穩(wěn)定匹配D.沒(méi)有不穩(wěn)定配對(duì)10【單選題】(10分)(1)復(fù)雜變簡(jiǎn)單(2)未知變已知(3)隱式變顯式(4（5）以上都是。A.（5）B.（1）C.（2）D.（3）E.（4）11【單選題】(10分) 按照霍納法則，計(jì)算p(x)=axn+axn-1+…+ax1+a n n-1 1 0A.nB.n^2C.lognD.nlogn第二章測(cè)試1【判斷題】(10分)時(shí)間復(fù)雜度是指算法最壞情況下的運(yùn)行時(shí)間。A.錯(cuò)B.對(duì)2【判斷題】(10分)f(n)=3n3+7n2+4nlogn=O（n2）A.錯(cuò)B.對(duì)3【判斷題】(10分)如果一個(gè)算法是多項(xiàng)式時(shí)間算法，該算法是有效的,是好算法。A.錯(cuò)B.對(duì)4【單選題】(10分)算法復(fù)雜度分析的兩種基本方法為（）和（）。A.幾何復(fù)雜度平均復(fù)雜度B.平攤復(fù)雜度平滑復(fù)雜度C.事后統(tǒng)計(jì)事前分析D.結(jié)構(gòu)化方法面向?qū)ο蠓椒?【單選題】(10分)下面程序的時(shí)間復(fù)雜度為x=1fori=1tondoforj=1toidofork=1tojdox++A.O(n)B.O(n^2)C.O(n^3)D.O(nlogn)6【單選題】(10分)對(duì)近似遞增序列的線性表從小到大排序，使用哪種方法好？A.插入排序B.堆排序C.快速排序D.歸并排序7【多選題】(10分)順序查找適合的數(shù)據(jù)結(jié)構(gòu)是（）A.壓縮存儲(chǔ)B.散列存儲(chǔ)C.鏈?zhǔn)酱鎯?chǔ)D.順序存儲(chǔ)8【單選題】(10分)給定n個(gè)元素的數(shù)組A，n=10使用折半查找比使用順序查找大約快 倍。A.100B.10C.1000D.10^(3/2)9【單選題】(10分)則f(n的漸進(jìn)性態(tài)f(n)=Ω()A.nB.n^2C.1D.10010【判斷題】(10分)當(dāng)且僅當(dāng)A.對(duì)B.錯(cuò)第三章測(cè)試1部分總題數(shù):121【判斷題】(10分)0-1背包問(wèn)題的枚舉算法的時(shí)間復(fù)雜度為O（2n）A.對(duì)B.錯(cuò)2【判斷題】(10分)增量構(gòu)造法生成子集前需要對(duì)集合中元素從小到大排列。A.錯(cuò)B.對(duì)3【判斷題】(10分)分塊查找一般設(shè)分塊的長(zhǎng)度是n/2.A.錯(cuò)B.對(duì)4【判斷題】(10分)枚舉法適用于問(wèn)題的小規(guī)模實(shí)例。A.錯(cuò)B.對(duì)5【單選題】(10分)便于實(shí)現(xiàn)集合操作的子集生成算法是（）A.增量構(gòu)造法B.二進(jìn)制法C.位向量法6【單選題】(10分)從所有候選答案中去搜索正確的解，這是（）算法。A.遞推B.枚舉C.蠻力7【單選題】(10分)logn()(logn+5)A.OB.θC.oD.w8【單選題】(10分)0-1背包問(wèn)題的枚舉算法，如果在百萬(wàn)次每秒的計(jì)算機(jī)上運(yùn)行，1年可以計(jì)算的問(wèn)題規(guī)模估計(jì)是？A.40B.60C.30D.509【多選題】(10分)分?jǐn)?shù)拆分問(wèn)題的枚舉算法通過(guò)（）方法進(jìn)行了優(yōu)化。A.減少枚舉變量的值域B.優(yōu)化數(shù)學(xué)模型C.優(yōu)化數(shù)據(jù)結(jié)構(gòu)D.減少枚舉變量10【多選題】(10分)下面那些算法的時(shí)間復(fù)雜度為O（ ）?A.折半插入排序B.順序查找C.冒泡排序D.插入排序E.折半查找11【單選題】(10分)AB100n^2B1nA1（）A.10nB.100nC.nD.n^212【判斷題】(10分)冒泡排序的時(shí)間復(fù)雜度為Ω(n^2)A.錯(cuò)B.對(duì)第四章測(cè)試1【判斷題】(10分)貪心算法總能找到可行解，但未必是最優(yōu)解。A.錯(cuò)B.對(duì)2【判斷題】(10分)貪心選擇通過(guò)一步步選擇得到問(wèn)題的解，每一步的局部最優(yōu)解都構(gòu)成全局最優(yōu)解的一部分。A.對(duì)B.錯(cuò)3【判斷題】(10分)問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用貪心算法或動(dòng)態(tài)規(guī)劃算法求解的關(guān)鍵特征。A.對(duì)B.錯(cuò)4【判斷題】(10分)Kruskal算法的貪婪準(zhǔn)則是每一次選取不構(gòu)成環(huán)路的最小邊。A.錯(cuò)B.對(duì)5【單選題】(10分)貪心算法基本要素有（）和最優(yōu)子結(jié)構(gòu)性質(zhì)。A.分解合并性質(zhì)B.重疊子問(wèn)題性質(zhì)C.獨(dú)立子問(wèn)題性質(zhì)D.貪心選擇性質(zhì)6【單選題】(10分)下面不是證明貪心算法證明方法的有（）。A.領(lǐng)先B.優(yōu)化C.界D.交換論證7【多選題】(10分)最小生成樹(shù)問(wèn)題可以使用的算法有（）A.SolimB.KruskalC.DijkstraD.Prim8【多選題】(10分)區(qū)間問(wèn)題包含()A.區(qū)間調(diào)度B.區(qū)間覆蓋C.區(qū)間選點(diǎn)D.區(qū)間劃分9【判斷題】(10分)負(fù)權(quán)的單源最短路問(wèn)題可以使用Dijkstra算法求解A.對(duì)B.錯(cuò)10【判斷題】(10分)CfC中的最大邊，那么最小生成樹(shù)中肯定包含。A.錯(cuò)B.對(duì)第五章測(cè)試1【判斷題】(10分)正推是從小規(guī)模的問(wèn)題推解出大規(guī)模間題的一種方法。A.對(duì)B.錯(cuò)2【判斷題】(10分)一般來(lái)說(shuō)，遞歸的效率高于遞推。A.對(duì)B.錯(cuò)3【單選題】(10分)從大規(guī)模問(wèn)題逐步化為小規(guī)模問(wèn)題的算法是（）A.正推B.迭代C.遞歸D.倒推4【單選題】(10分)求解高階遞推方程一般使用（）迭代方法A.差消迭代B.換元迭代C.直接迭代5【多選題】(10分)遞歸函數(shù)的要素是（）A.迭代B.邊界條件C.遞歸方程D.輸入6【多選題】(10分)遞歸變?yōu)榉沁f歸的方法有（）A.循環(huán)B.遞推C.模擬棧D.尾遞歸7【多選題】(10分)T(n)=T(n-1)+n，T(1)=1，則T(n)=（）A.n(n+1)/2B.O(n^2)C.Ω(n^2)D.θ(n^2)8【多選題】(10分)遞歸一般用于解決問(wèn)題有（）A.問(wèn)題解法按遞歸實(shí)現(xiàn)B.數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的C.數(shù)據(jù)的定義是按遞歸定義的D.迭代問(wèn)題9【單選題】(10分)主方法可以求解滿足T(n)=aT(n/b)+f(n)形式的遞推方程，則下列關(guān)于方程中的約束中不準(zhǔn)確的是？設(shè)A.對(duì)于系數(shù)a，必須滿足a>=1B.對(duì)于系數(shù)b，必須滿足b>1C.若f(n)=O(x)，則T(n)=Θ(xlogn)D.若對(duì)于常數(shù)e>0，f(n)=O(y)，則T(n)=Θ(x)10【單選題】(10分)T(n)=（）A.O(nlogn)B.O(n)C.Θ(n^2)D.Ω(n^3)11【判斷題】(10分)循環(huán)用于重復(fù)性的工作。循環(huán)體的特點(diǎn)是：“以不變應(yīng)萬(wàn)變”。A.對(duì)B.錯(cuò)第六章測(cè)試1【判斷題】(10分)分治法分解的子問(wèn)題與原問(wèn)題形式相同。A.錯(cuò)B.對(duì)2【判斷題】(10分)N個(gè)元素排序的時(shí)間復(fù)雜度不可能是線性時(shí)間。A.錯(cuò)B.對(duì)3【判斷題】(10分)三分法的判定樹(shù)是三叉樹(shù)。A.對(duì)B.錯(cuò)4【判斷題】(10分)減治法減一個(gè)常量就是每次迭代減去一個(gè)相同的常數(shù)因子(一般為2)A.對(duì)B.錯(cuò)5【單選題】(10分)設(shè)有5000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用()法。A.冒泡排序B.快速排序C.基數(shù)排序D.合并排序6【單選題】(10分)堆排序的時(shí)間復(fù)雜度是O（）。A.O（nlogn）B.C.D.O（n）7【單選題】(10分)改進(jìn)分治算法的方法有（）和改進(jìn)劃分的對(duì)稱(chēng)性。A.備忘錄B.加速原理C.擬陣原理D.減少子問(wèn)題數(shù)8【多選題】(10分)通過(guò)減少子問(wèn)題個(gè)數(shù)，降低分治算法時(shí)間復(fù)雜度的有（）A.大整數(shù)乘法B.Strassen矩陣乘法C.最接近點(diǎn)對(duì)D.線性時(shí)間選擇9【多選題】(10分)分治法在每一層遞歸上有三個(gè)步驟（）A.合并B.分解C.選擇D.解決10【單選題】(10分)使用分治法求解不需要滿足的條件是（）。A.子問(wèn)題不能夠重復(fù)B.子問(wèn)題的解可以合并C.原問(wèn)題和子問(wèn)題使用相同的方法求解D.子問(wèn)題必須是一樣的11【判斷題】(10分)最小堆中每個(gè)元素調(diào)整的次數(shù)不超過(guò)樹(shù)高。A.對(duì)B.錯(cuò)12【判斷題】(10分)分治算法的思想是將難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的子問(wèn)題，以便各個(gè)擊破，分而治之。A.錯(cuò)B.對(duì)13【判斷題】(10分)任何排序算法至少需要O(nlogn)次比較。A.對(duì)B.錯(cuò)14【單選題】(10分)找n個(gè)元素的中位數(shù)的分治算法的時(shí)間復(fù)雜度為O().A.nlognB.nC.n^2D.logn第七章測(cè)試1【判斷題】(10分)的解。A.錯(cuò)B.對(duì)2【判斷題】(10分)0/1背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法是多項(xiàng)式時(shí)間算法。A.錯(cuò)B.對(duì)3【判斷題】(10分)FloydnDijkstran算法。A.錯(cuò)B.對(duì)4【判斷題】(10分)Dijkstra算法在求解過(guò)程中，源點(diǎn)到集合S內(nèi)各頂點(diǎn)的最短路徑一旦求出，則之后不變了，修改的僅僅是源點(diǎn)到還沒(méi)選擇的頂點(diǎn)的最短路徑長(zhǎng)度。A.錯(cuò)B.對(duì)5【單選題】(10分)含負(fù)權(quán)的最短路問(wèn)題一般使用（）求解。A.動(dòng)態(tài)規(guī)劃B.網(wǎng)絡(luò)流算法C.貪心算法D.分治算法6【單選題】(10分)動(dòng)態(tài)規(guī)劃算法的基本要素有（）和最優(yōu)子結(jié)構(gòu)性質(zhì)。A.分解合并性質(zhì)B.獨(dú)立子問(wèn)題性質(zhì)C.重疊子問(wèn)題性質(zhì)D.貪心選擇性質(zhì)7【單選題】(10分)下面不是動(dòng)態(tài)規(guī)劃的基本方法有（）。A.增加變量B.多重選擇C.區(qū)間變量D.舍入8【多選題】(10分)最短路算法中適用于稀疏圖的是（）A.Dijkstra算法B.Bellman算法C.Floyd算法D.SPFA算法9【多選題】(10分)分治算法與動(dòng)態(tài)規(guī)劃算法的相同點(diǎn)是（）A.最優(yōu)子結(jié)構(gòu)B.子問(wèn)題重疊C.子問(wèn)題獨(dú)立D.遞推關(guān)系10【判斷題】(10分)DAG上最短路，固定起點(diǎn)和終點(diǎn)沒(méi)有意義。A.錯(cuò)B.對(duì)11【判斷題】(10分)DAG圖最長(zhǎng)路的遞推函數(shù)d(i

示從某個(gè)頂點(diǎn)i出發(fā)的最長(zhǎng)路長(zhǎng)度。A.對(duì)B.錯(cuò)12【判斷題】(10分)樹(shù)上最大權(quán)獨(dú)立集不包含u，可能包含兒子結(jié)點(diǎn)，也可能不包含兒子結(jié)點(diǎn)。A.對(duì)B.錯(cuò)13【判斷題】(10分)SPFA算法的時(shí)間復(fù)雜度為O（mn）A.錯(cuò)B.對(duì)第八章測(cè)試1【判斷題】(10分)回溯法是按廣度優(yōu)先策略搜索解空間樹(shù)。A.對(duì)B.錯(cuò)2【判斷題】(10分)死結(jié)點(diǎn)是正在產(chǎn)生兒子的結(jié)點(diǎn)。A.錯(cuò)B.對(duì)3【判斷題】(10分)回溯法的一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間。A.錯(cuò)B.對(duì)4【判斷題】(10分)回溯法不適用于解一些組合數(shù)相當(dāng)大的問(wèn)題。A.錯(cuò)B.對(duì)5【判斷題】(10分)在選擇約束函數(shù)時(shí)通常存在生成結(jié)點(diǎn)數(shù)與約束函數(shù)計(jì)算量之間的折衷。A.錯(cuò)B.對(duì)6【單選題】(10分)下列算法中，通常以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的是（）。A.貪心法B.回溯法C.備忘錄法D.動(dòng)態(tài)規(guī)劃法7【單選題】(10分)裝載問(wèn)題的回溯算法所需的計(jì)算時(shí)間為A.O（nlogn）B.O（2n）C.O（n2）D.O（n）8【多選題】(10分)問(wèn)題的狀態(tài)生成法有（）A.子集樹(shù)生成法B.深度優(yōu)先生成法C.寬度優(yōu)先生成法D.排列樹(shù)生成法9【多選題】(10分)回溯法解題步驟A.針對(duì)所給問(wèn)題，定義問(wèn)題的解空間B.確定易于搜索的解空間結(jié)構(gòu)C.確定最優(yōu)子結(jié)構(gòu)的性質(zhì)D.以深度優(yōu)先方式搜索解空間，在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。10【多選題】(10分)回溯法的效率依賴(lài)于下列哪些因素（）A.滿足顯約束的值的個(gè)數(shù)B.確定解空間的時(shí)間C.計(jì)算限界函數(shù)的時(shí)間D.計(jì)算約束函數(shù)的時(shí)間11【單選題】(10分)剪枝函數(shù)包括（）和約束函數(shù)A.限界函數(shù)B.最優(yōu)函數(shù)C.估計(jì)函數(shù)D.啟發(fā)式函數(shù)12【判斷題】(10分)回溯法搜索解空間時(shí)，在搜索試探時(shí)選取x[i差別。A.錯(cuò)B.對(duì)13【判斷題】(10分)回溯法中，如果解空間樹(shù)是排列樹(shù)，所給問(wèn)題的規(guī)模為n時(shí)，遍歷排列樹(shù)需O(n!)計(jì)算時(shí)間.A.對(duì)B.錯(cuò)14【多選題】(10分)回溯法的兩種解空間樹(shù)為（）A.子集樹(shù)B.排列樹(shù)C.祖先樹(shù)D.遞歸樹(shù)第九章測(cè)試1部分第九章測(cè)試總題數(shù):131【判斷題】(10分)分支限界法在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)有多次機(jī)會(huì)成為活結(jié)點(diǎn)。A.對(duì)B.錯(cuò)2【判斷題】(10分)分支限界法找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。A.錯(cuò)B.對(duì)3【判斷題】(10分)隊(duì)列式分支限界法以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。A.對(duì)B.錯(cuò)4【判斷題】(10分)優(yōu)先隊(duì)列式分支限界法按照隊(duì)列先進(jìn)先出的原則，選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。A.錯(cuò)B.對(duì)5【單選題】(10分)分支限界法解旅行商問(wèn)題時(shí)的解空間樹(shù)是A.子集樹(shù)B.深度優(yōu)先生成樹(shù)C.排列樹(shù)D.廣度優(yōu)先生成樹(shù)6【單選題】(10分)優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是A.隨機(jī)B.結(jié)點(diǎn)的優(yōu)先級(jí)C.后進(jìn)先出D.先進(jìn)先出7【多選題】(10分)用分支限界法設(shè)計(jì)算法的步驟是：A.確定易于搜索的解空間結(jié)構(gòu)（按樹(shù)或圖組織解）B.以廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索C.針對(duì)所給問(wèn)題，定義問(wèn)題的解空間（對(duì)解進(jìn)行編碼）D.定義最優(yōu)子結(jié)構(gòu)8【多選題】(10分)分支限界法與回溯法的不同點(diǎn)是什么？A.搜索方式不同B.求解目標(biāo)不同C.存儲(chǔ)空間的要求不同D.對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同9【單選題】(10分)FIFO是（）的搜索方式。A.回溯算法B.貪心算法C.動(dòng)態(tài)規(guī)劃D.分支限界10【單選題】(10分)下面說(shuō)法不正確的是（）A.用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹(shù)B.用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)C.使用限界函數(shù)作優(yōu)先級(jí),第一個(gè)加入隊(duì)列的葉子就是最優(yōu)解D.回溯和分支限界都是動(dòng)態(tài)生成解空間樹(shù)11【單選題】(10分)在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)的是（）。A.分支限界B.回溯C.回溯和分支限界D.回溯求解子集樹(shù)問(wèn)題12【判斷題】(10分)使用限界函數(shù)作優(yōu)先級(jí),第一個(gè)擴(kuò)展的葉子就是最優(yōu)解A.錯(cuò)B.對(duì)13【判斷題】(10分)分支限界法不能解決0/1背包問(wèn)題A.錯(cuò)B.對(duì)第十章測(cè)試1【判斷題】(10分)網(wǎng)絡(luò)流滿足容量約束，但一般不滿足流量守恒約束。A.對(duì)B.錯(cuò)2【判斷題】(10分)G=<V1,V2,E>,|V1|≤|V2|,MG|M|=|V1|,MGA.錯(cuò)B.對(duì)3【判斷題】(10分)存在割(A,B)使流值v(f)=割的容量cap(A,B)，則割(A,B)是最小割。A.錯(cuò)B.對(duì)4【判斷題】(10分)給定連通圖G,BFS遍歷得到層次圖，如果同一層中的結(jié)點(diǎn)無(wú)邊相連，則G是二分圖。A.錯(cuò)B.對(duì)5【判斷題】(10分)有下界的流通問(wèn)題不一定有可行流。A.對(duì)B.錯(cuò)6【單選題】(10分)Dinic算法的時(shí)間復(fù)雜度為（）A.m2logCB.mn2C.mnD.m2n7【單選題】(10分)如果每條邊的最大容量為1，則時(shí)間復(fù)雜度是O(nm)的網(wǎng)絡(luò)流算法有A.FFB.EKC.Dinic算法D.容量縮放算法8【多選題】(10分)改進(jìn)FF網(wǎng)絡(luò)流算法，可以通過(guò)選擇（）增廣路，降低時(shí)間復(fù)雜度。A.邊數(shù)最少B.最大瓶頸容量C.最大容量D.最短路徑9【判斷題】(10分)帶需求的流通必須滿足供給和=需求和A.錯(cuò)B.對(duì)10【判斷題】(10分)條邊。A.對(duì)B.錯(cuò)11【判斷題】(10分)給定二分圖G=<V,E>中無(wú)孤立點(diǎn)，其最大流算法求得最大流f則G的最大匹配數(shù)=f.A.對(duì)B.錯(cuò)12【判斷題】(10分)設(shè)G=<V,E>中無(wú)孤立點(diǎn)。W為G的最小邊覆蓋,若G中存在相鄰邊就移去其中一條。設(shè)移去的邊集為N，則W-N是G的最大匹配。A.對(duì)B.錯(cuò)13【判斷題】(10分)設(shè)f是網(wǎng)絡(luò)N的任意流，(A,B)是N的任意s-t割，則流值f至多等于割的容量。A.對(duì)B.錯(cuò)第十一章測(cè)試1【判斷題】(10分)蒙特卡羅算法的結(jié)果肯定是一個(gè)正確解。A.對(duì)B.錯(cuò)2【判斷題】(10分)Sherwood算法隨機(jī)選擇一個(gè)數(shù)組元素作為劃分標(biāo)準(zhǔn)求解k小元素問(wèn)題,保證線性時(shí)間的平均性能。A.錯(cuò)B.對(duì)3【判斷題】(10分)借助隨機(jī)預(yù)處理技術(shù)，不改變?cè)械拇_定性算法，僅對(duì)其輸入進(jìn)行隨機(jī)洗牌，可收到舍伍德算法的效果。A.對(duì)B.錯(cuò)4【判斷題】(10分)隨機(jī)算法共同點(diǎn)是計(jì)算時(shí)間越多或運(yùn)行次數(shù)越多,正確性越高.A.錯(cuò)B.對(duì)5【判斷題】(10分)增加拉斯維加斯算法的反復(fù)求解次數(shù),可使求解無(wú)效的概率任意小。A.對(duì)B.錯(cuò)6【單選題】(10分)在下列算法中有時(shí)找不到問(wèn)題解的是A.蒙特卡羅算法B.拉斯維加斯算法C.舍伍德算法D.數(shù)值隨機(jī)算法7【單選題】(10分)肯定獲得可行解，但不一定是正確解的算法是A.拉斯維加斯算法B.蒙特卡羅算法C.數(shù)值隨機(jī)算法D.舍伍德算法8【單選題】(10分)在一般輸入數(shù)據(jù)的程序里，輸入多少會(huì)影響到算法的計(jì)算復(fù)雜度，為了消除這種影響可用（）對(duì)輸入進(jìn)行預(yù)處理。A.拉斯維加斯算法B.蒙特卡羅算法C.舍伍德算法D.數(shù)值隨機(jī)化算法9【多選題】(10分)下面說(shuō)法正確的是A.現(xiàn)實(shí)計(jì)算機(jī)上無(wú)法產(chǎn)生真正的隨機(jī)數(shù)B.求解同一實(shí)例用同一隨機(jī)化算法求解兩次，所用時(shí)間和所得結(jié)果可能完全不同。C.蒙特卡羅算法總是能提供問(wèn)題的一個(gè)解,但可能給出解。D.舍伍德算法的精髓不是避免最壞的情況，而是設(shè)法消除最壞情況和特定實(shí)例的關(guān)聯(lián)性。10【多選題】(10分)下面說(shuō)法正確的是（）A.當(dāng)最壞和平均情況差別較大時(shí),舍伍德算法可以消除好壞實(shí)例的差別，達(dá)到平均實(shí)例的性能B.線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法C.增加蒙特卡羅算法的求解次數(shù),可使求解的概率任意小。D.法11【判斷題】(10分)確定性算法的每一計(jì)算步驟都確定,求解同一實(shí)例用同一算法求解兩次，所得結(jié)果完全相同。A.錯(cuò)B.對(duì)12【判斷題】(10分)舍伍德算法總是有解,且解總是正確的，但最壞性能未改變。A.對(duì)B.錯(cuò)13【判斷題】(10分)拉斯維加斯算法肯定得到一個(gè)正確解。A.錯(cuò)B.對(duì)14【判斷題】(10分)隨機(jī)抽取數(shù)組元素k次,從最接近搜索元素x的位置順序搜索,順序搜索的平均比較次數(shù)為O(n/(k+1)).A.對(duì)B.錯(cuò)第十二章測(cè)試1【判斷題】(10分)有多項(xiàng)式時(shí)間算法的問(wèn)題是易解問(wèn)題A.錯(cuò)B.對(duì)2【判斷題】(10分)EXP類(lèi)是所有指數(shù)時(shí)間可解的判定問(wèn)題組成的問(wèn)題類(lèi)A.錯(cuò)B.對(duì)3【判斷題】(10分)如果對(duì)于X的任意實(shí)例，通過(guò)多項(xiàng)式次的計(jì)算步驟，加多項(xiàng)式次調(diào)用Y的算法，可解決X，則X可多項(xiàng)式時(shí)間歸約到Y(jié)。A.對(duì)B.錯(cuò)4【單選題】(10分)下面關(guān)于NP問(wèn)題說(shuō)法正確的是（）A.NP類(lèi)問(wèn)題包含在P類(lèi)問(wèn)題中B.NP問(wèn)題都是不可能解決的問(wèn)題C.NP完全問(wèn)題是P類(lèi)問(wèn)題的子集D.P類(lèi)問(wèn)題包含在NP類(lèi)問(wèn)題中5【多選題】(10分)下面屬于NP完全問(wèn)題的是（）A.最小頂點(diǎn)覆蓋B.SATC.最大獨(dú)立集D.旅行商問(wèn)題6【多選題】(10分)以下關(guān)于判定問(wèn)題難易處理的敘述中的是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)題是難處理的7【單選題】(10分)下列說(shuō)法的是A.判定問(wèn)題可多項(xiàng)式時(shí)間變換到優(yōu)化問(wèn)題B.P包含于NPC.I