算法分析與設(shè)計(jì)（山東聯(lián)盟）-知到答案、智慧樹答案第一章單元測(cè)試1、問(wèn)題：一個(gè)問(wèn)題的同一實(shí)例可以有不同的表示形式選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】2、問(wèn)題：同一數(shù)學(xué)模型使用不同的數(shù)據(jù)結(jié)構(gòu)會(huì)有不同的算法，有效性有很大差別。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】3、問(wèn)題：?jiǎn)栴}的兩個(gè)要素是輸入和實(shí)例。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】4、問(wèn)題：算法與程序的區(qū)別是（）選項(xiàng)：A:確定性B:輸出C:輸入D:有窮性答案:【有窮性】5、問(wèn)題：解決問(wèn)題的基本步驟是（）。（1）算法設(shè)計(jì)（2）算法實(shí)現(xiàn)（3）數(shù)學(xué)建模（4）算法分析（5）正確性證明選項(xiàng)：A:(3)(4)(1)(5)(2)B:(1)(2)(3)(4)(5)C:(3)(1)(5)(4)(2)D:(3)(1)(4)(5)(2)答案:【(3)(1)(5)(4)(2)】6、問(wèn)題：下面說(shuō)法關(guān)于算法與問(wèn)題的說(shuō)法錯(cuò)誤的是（）。選項(xiàng)：A:證明算法不正確，需要證明對(duì)任意實(shí)例算法都不能正確處理。B:如果一個(gè)算法能應(yīng)用于問(wèn)題的任意實(shí)例，并保證得到正確解答，稱這個(gè)算法解答了該問(wèn)題。C:同一問(wèn)題可能有幾種不同的算法，解題思路和解題速度也會(huì)顯著不同。D:算法是一種計(jì)算方法，對(duì)問(wèn)題的每個(gè)實(shí)例計(jì)算都能得到正確答案。答案:【證明算法不正確，需要證明對(duì)任意實(shí)例算法都不能正確處理?！?、問(wèn)題：下面關(guān)于程序和算法的說(shuō)法正確的是（）。選項(xiàng)：A:程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。B:算法的每一步驟必須要有確切的含義，必須是清楚的、無(wú)二義的。C:算法是一個(gè)過(guò)程，計(jì)算機(jī)每次求解是針對(duì)問(wèn)題的一個(gè)實(shí)例求解。D:程序總是在有窮步的運(yùn)算后終止。答案:【程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。;算法的每一步驟必須要有確切的含義，必須是清楚的、無(wú)二義的。;算法是一個(gè)過(guò)程，計(jì)算機(jī)每次求解是針對(duì)問(wèn)題的一個(gè)實(shí)例求解?！?、問(wèn)題：最大獨(dú)立集問(wèn)題和（）問(wèn)題等價(jià)。選項(xiàng)：A:最小頂點(diǎn)覆蓋B:區(qū)間調(diào)度問(wèn)題C:穩(wěn)定匹配問(wèn)題D:最大團(tuán)答案:【最小頂點(diǎn)覆蓋;最大團(tuán)】9、問(wèn)題：給定兩張喜歡列表，穩(wěn)定匹配問(wèn)題的輸出是（）。選項(xiàng)：A:最大匹配B:沒有不穩(wěn)定配對(duì)C:完美匹配D:穩(wěn)定匹配答案:【最大匹配;沒有不穩(wěn)定配對(duì);完美匹配;穩(wěn)定匹配】10、問(wèn)題：?jiǎn)栴}變換的目的有（）。(1)復(fù)雜變簡(jiǎn)單(2)未知變已知(3)隱式變顯式(4)難解變易解（5）以上都是。選項(xiàng)：A:（2）B:（5）C:（3）D:（4）E:（1）答案:【（5）】11、問(wèn)題：按照霍納法則，計(jì)算p(x)=anxn+an-1xn-1+…+a1x1+a0的數(shù)量級(jí)為____。選項(xiàng)：A:lognB:nC:n^2D:nlogn答案:【n】第二章單元測(cè)試1、問(wèn)題：時(shí)間復(fù)雜度是指算法最壞情況下的運(yùn)行時(shí)間。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】2、問(wèn)題：f(n)=3n3+7n2+4nlogn=O（n2）選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】3、問(wèn)題：如果一個(gè)算法是多項(xiàng)式時(shí)間算法，該算法是有效的,是好算法。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】4、問(wèn)題：算法復(fù)雜度分析的兩種基本方法為（）和（）。選項(xiàng)：A:平攤復(fù)雜度平滑復(fù)雜度B:結(jié)構(gòu)化方法面向?qū)ο蠓椒–:事后統(tǒng)計(jì)事前分析D:幾何復(fù)雜度平均復(fù)雜度答案:【事后統(tǒng)計(jì)事前分析】5、問(wèn)題：下面程序的時(shí)間復(fù)雜度為（）x=1fori=1tondoforj=1toidofork=1tojdox++選項(xiàng)：A:O(nlogn)B:O(n^3)C:O(n)D:O(n^2)答案:【O(n^3)】6、問(wèn)題：對(duì)近似遞增序列的線性表從小到大排序，使用哪種方法好？選項(xiàng)：A:歸并排序B:插入排序C:堆排序D:快速排序答案:【插入排序】7、問(wèn)題：順序查找適合的數(shù)據(jù)結(jié)構(gòu)是（）選項(xiàng)：A:順序存儲(chǔ)B:壓縮存儲(chǔ)C:散列存儲(chǔ)D:鏈?zhǔn)酱鎯?chǔ)答案:【順序存儲(chǔ);鏈?zhǔn)酱鎯?chǔ)】8、問(wèn)題：給定n個(gè)元素的數(shù)組A，n=10^3,使用折半查找比使用順序查找大約快___倍。選項(xiàng)：A:100B:10C:1000D:10^(3/2)答案:【100】9、問(wèn)題：則f(n)的漸進(jìn)性態(tài)f(n)=Ω()選項(xiàng)：A:nB:100C:n^2D:1答案:【1】10、問(wèn)題：f=O(g)當(dāng)且僅當(dāng)g=Ω(f)選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】第三章單元測(cè)試1、問(wèn)題：0-1背包問(wèn)題的枚舉算法的時(shí)間復(fù)雜度為O（2n）選項(xiàng)：A:錯(cuò)B:對(duì)答案:【錯(cuò)】2、問(wèn)題：增量構(gòu)造法生成子集前需要對(duì)集合中元素從小到大排列。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】3、問(wèn)題：分塊查找一般設(shè)分塊的長(zhǎng)度是n/2.選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】4、問(wèn)題：枚舉法適用于問(wèn)題的小規(guī)模實(shí)例。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】5、問(wèn)題：便于實(shí)現(xiàn)集合操作的子集生成算法是（）選項(xiàng)：A:位向量法B:二進(jìn)制法C:增量構(gòu)造法答案:【二進(jìn)制法】6、問(wèn)題：從所有候選答案中去搜索正確的解，這是（）算法。選項(xiàng)：A:遞推B:枚舉C:蠻力答案:【枚舉】7、問(wèn)題：logn2=()(logn+5)選項(xiàng)：A:oB:OC:θD:w答案:【θ】8、問(wèn)題：0-1背包問(wèn)題的枚舉算法，如果在百萬(wàn)次每秒的計(jì)算機(jī)上運(yùn)行，1年可以計(jì)算的問(wèn)題規(guī)模估計(jì)是？選項(xiàng)：A:30B:60C:50D:40答案:【40】9、問(wèn)題：分?jǐn)?shù)拆分問(wèn)題的枚舉算法通過(guò)（）方法進(jìn)行了優(yōu)化。選項(xiàng)：A:優(yōu)化數(shù)據(jù)結(jié)構(gòu)B:減少枚舉變量的值域C:優(yōu)化數(shù)學(xué)模型D:減少枚舉變量答案:【減少枚舉變量的值域;優(yōu)化數(shù)學(xué)模型;減少枚舉變量】10、問(wèn)題：下面那些算法的時(shí)間復(fù)雜度為O（）?選項(xiàng)：A:冒泡排序B:順序查找C:折半插入排序D:折半查找E:插入排序答案:【冒泡排序;折半插入排序;插入排序】11、問(wèn)題：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ī)模是（）選項(xiàng)：A:10nB:100nC:n^2D:n答案:【10n】12、問(wèn)題：冒泡排序的時(shí)間復(fù)雜度為Ω(n^2)選項(xiàng)：A:錯(cuò)B:對(duì)答案:【錯(cuò)】第四章單元測(cè)試1、問(wèn)題：貪心算法總能找到可行解，但未必是最優(yōu)解。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】2、問(wèn)題：貪心選擇通過(guò)一步步選擇得到問(wèn)題的解，每一步的局部最優(yōu)解都構(gòu)成全局最優(yōu)解的一部分。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】3、問(wèn)題：?jiǎn)栴}的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用貪心算法或動(dòng)態(tài)規(guī)劃算法求解的關(guān)鍵特征。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】4、問(wèn)題：Kruskal算法的貪婪準(zhǔn)則是每一次選取不構(gòu)成環(huán)路的最小邊。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】5、問(wèn)題：貪心算法基本要素有（）和最優(yōu)子結(jié)構(gòu)性質(zhì)。選項(xiàng)：A:重疊子問(wèn)題性質(zhì)B:分解合并性質(zhì)C:獨(dú)立子問(wèn)題性質(zhì)D:貪心選擇性質(zhì)答案:【貪心選擇性質(zhì)】6、問(wèn)題：下面不是證明貪心算法證明方法的有（）。選項(xiàng)：A:界B:優(yōu)化C:領(lǐng)先D:交換論證答案:【優(yōu)化】7、問(wèn)題：最小生成樹問(wèn)題可以使用的算法有（）選項(xiàng)：A:KruskalB:SolimC:PrimD:Dijkstra答案:【Kruskal;Solim;Prim】8、問(wèn)題：區(qū)間問(wèn)題包含()選項(xiàng)：A:區(qū)間劃分B:區(qū)間選點(diǎn)C:區(qū)間覆蓋D:區(qū)間調(diào)度答案:【區(qū)間劃分;區(qū)間選點(diǎn);區(qū)間覆蓋;區(qū)間調(diào)度】9、問(wèn)題：負(fù)權(quán)的單源最短路問(wèn)題可以使用Dijkstra算法求解選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】10、問(wèn)題：設(shè)C是一個(gè)環(huán)，f是C中的最大邊，那么最小生成樹中肯定包含f。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】第五章單元測(cè)試1、問(wèn)題：正推是從小規(guī)模的問(wèn)題推解出大規(guī)模間題的一種方法。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】2、問(wèn)題：一般來(lái)說(shuō)，遞歸的效率高于遞推。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【錯(cuò)】3、問(wèn)題：從大規(guī)模問(wèn)題逐步化為小規(guī)模問(wèn)題的算法是（）選項(xiàng)：A:遞歸B:倒推C:正推D:迭代答案:【遞歸】4、問(wèn)題：求解高階遞推方程一般使用（）迭代方法選項(xiàng)：A:差消迭代B:直接迭代C:換元迭代答案:【差消迭代】5、問(wèn)題：遞歸函數(shù)的要素是（）選項(xiàng)：A:迭代B:輸入C:遞歸方程D:邊界條件答案:【遞歸方程;邊界條件】6、問(wèn)題：遞歸變?yōu)榉沁f歸的方法有（）選項(xiàng)：A:遞推B:尾遞歸C:循環(huán)D:模擬棧答案:【遞推;尾遞歸;模擬棧】7、問(wèn)題：T(n)=T(n-1)+n，T(1)=1，則T(n)=（）選項(xiàng)：A:O(n^2)B:Ω(n^2)C:n(n+1)/2D:θ(n^2)答案:【O(n^2);Ω(n^2);n(n+1)/2;θ(n^2)】8、問(wèn)題：遞歸一般用于解決問(wèn)題有（）選項(xiàng)：A:迭代問(wèn)題B:數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的C:數(shù)據(jù)的定義是按遞歸定義的D:問(wèn)題解法按遞歸實(shí)現(xiàn)答案:【數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的;數(shù)據(jù)的定義是按遞歸定義的;問(wèn)題解法按遞歸實(shí)現(xiàn)】9、問(wèn)題：主方法可以求解滿足T(n)=aT(n/b)+f(n)形式的遞推方程，則下列關(guān)于方程中的約束中不準(zhǔn)確的是？設(shè)選項(xiàng)：A:對(duì)于系數(shù)a，必須滿足a>=1B:若對(duì)于常數(shù)e>0，f(n)=O(y)，則T(n)=Θ(x)C:對(duì)于系數(shù)b，必須滿足b>1D:若f(n)=O(x)，則T(n)=Θ(xlogn)答案:【若f(n)=O(x)，則T(n)=Θ(xlogn)】10、問(wèn)題：，則T(n)=（）選項(xiàng)：A:Ω(n^3)B:O(n)C:Θ(n^2)D:O(nlogn)答案:【Θ(n^2)】11、問(wèn)題：循環(huán)用于重復(fù)性的工作。循環(huán)體的特點(diǎn)是：“以不變應(yīng)萬(wàn)變”。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】第六章單元測(cè)試1、問(wèn)題：分治法分解的子問(wèn)題與原問(wèn)題形式相同。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】2、問(wèn)題：N個(gè)元素排序的時(shí)間復(fù)雜度不可能是線性時(shí)間。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】3、問(wèn)題：三分法的判定樹是三叉樹。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】4、問(wèn)題：減治法減一個(gè)常量就是每次迭代減去一個(gè)相同的常數(shù)因子(一般為2)選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】5、問(wèn)題：設(shè)有5000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用()法。選項(xiàng)：A:合并排序B:冒泡排序C:基數(shù)排序D:快速排序答案:【冒泡排序】6、問(wèn)題：堆排序的時(shí)間復(fù)雜度是O（）。選項(xiàng)：A:O（nlogn）B:O（2n）C:O（n）D:O（n2）答案:【O（nlogn）】7、問(wèn)題：改進(jìn)分治算法的方法有（）和改進(jìn)劃分的對(duì)稱性。選項(xiàng)：A:備忘錄B:擬陣原理C:減少子問(wèn)題數(shù)D:加速原理答案:【減少子問(wèn)題數(shù)】8、問(wèn)題：通過(guò)減少子問(wèn)題個(gè)數(shù)，降低分治算法時(shí)間復(fù)雜度的有（）選項(xiàng)：A:最接近點(diǎn)對(duì)B:Strassen矩陣乘法C:大整數(shù)乘法D:線性時(shí)間選擇答案:【Strassen矩陣乘法;大整數(shù)乘法】9、問(wèn)題：分治法在每一層遞歸上有三個(gè)步驟（）選項(xiàng)：A:解決B:合并C:分解D:選擇答案:【解決;合并;分解】10、問(wèn)題：使用分治法求解不需要滿足的條件是（）。選項(xiàng)：A:子問(wèn)題必須是一樣的B:子問(wèn)題不能夠重復(fù)C:原問(wèn)題和子問(wèn)題使用相同的方法求解D:子問(wèn)題的解可以合并答案:【子問(wèn)題必須是一樣的】11、問(wèn)題：最小堆中每個(gè)元素調(diào)整的次數(shù)不超過(guò)樹高。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】12、問(wèn)題：分治算法的思想是將難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的子問(wèn)題，以便各個(gè)擊破，分而治之。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】13、問(wèn)題：任何排序算法至少需要O(nlogn)次比較。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】14、問(wèn)題：找n個(gè)元素的中位數(shù)的分治算法的時(shí)間復(fù)雜度為O().選項(xiàng)：A:nB:nlognC:lognD:n^2答案:【n】第七章單元測(cè)試1、問(wèn)題：動(dòng)態(tài)規(guī)劃算法把原問(wèn)題分為交叉的子問(wèn)題，解決子問(wèn)題，記錄子問(wèn)題的解，合并為原問(wèn)題的解。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】2、問(wèn)題：0/1背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法是多項(xiàng)式時(shí)間算法。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】3、問(wèn)題：對(duì)于稀疏圖，F(xiàn)loyd算法的效率要高于執(zhí)行n次Dijkstra算法，也要高于執(zhí)行n次算法。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】4、問(wèn)題：Dijkstra算法在求解過(guò)程中，源點(diǎn)到集合S內(nèi)各頂點(diǎn)的最短路徑一旦求出，則之后不變了，修改的僅僅是源點(diǎn)到還沒選擇的頂點(diǎn)的最短路徑長(zhǎng)度。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】5、問(wèn)題：含負(fù)權(quán)的最短路問(wèn)題一般使用（）求解。選項(xiàng)：A:動(dòng)態(tài)規(guī)劃B:分治算法C:貪心算法D:網(wǎng)絡(luò)流算法答案:【動(dòng)態(tài)規(guī)劃】6、問(wèn)題：動(dòng)態(tài)規(guī)劃算法的基本要素有（）和最優(yōu)子結(jié)構(gòu)性質(zhì)。選項(xiàng)：A:重疊子問(wèn)題性質(zhì)B:獨(dú)立子問(wèn)題性質(zhì)C:貪心選擇性質(zhì)D:分解合并性質(zhì)答案:【重疊子問(wèn)題性質(zhì)】7、問(wèn)題：下面不是動(dòng)態(tài)規(guī)劃的基本方法有（）。選項(xiàng)：A:增加變量B:區(qū)間變量C:多重選擇D:舍入答案:【舍入】8、問(wèn)題：最短路算法中適用于稀疏圖的是（）選項(xiàng)：算法B:Bellman算法C:Floyd算法D:Dijkstra算法答案:【算法;Bellman算法;Dijkstra算法】9、問(wèn)題：分治算法與動(dòng)態(tài)規(guī)劃算法的相同點(diǎn)是（）選項(xiàng)：A:子問(wèn)題獨(dú)立B:子問(wèn)題重疊C:最優(yōu)子結(jié)構(gòu)D:遞推關(guān)系答案:【最優(yōu)子結(jié)構(gòu);遞推關(guān)系】10、問(wèn)題：DAG上最短路，固定起點(diǎn)和終點(diǎn)沒有意義。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】11、問(wèn)題：DAG圖最長(zhǎng)路的遞推函數(shù)d(i)表示從某個(gè)頂點(diǎn)i出發(fā)的最長(zhǎng)路長(zhǎng)度。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】12、問(wèn)題：樹上最大權(quán)獨(dú)立集不包含u，可能包含兒子結(jié)點(diǎn)，也可能不包含兒子結(jié)點(diǎn)。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】13、問(wèn)題：算法的時(shí)間復(fù)雜度為O（mn）選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】第八章單元測(cè)試1、問(wèn)題：回溯法是按廣度優(yōu)先策略搜索解空間樹。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】2、問(wèn)題：死結(jié)點(diǎn)是正在產(chǎn)生兒子的結(jié)點(diǎn)。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【錯(cuò)】3、問(wèn)題：回溯法的一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】4、問(wèn)題：回溯法不適用于解一些組合數(shù)相當(dāng)大的問(wèn)題。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【錯(cuò)】5、問(wèn)題：好的約束函數(shù)能顯著地減少所生成的結(jié)點(diǎn)數(shù)。但這樣的約束函數(shù)往往計(jì)算量較大。因此，在選擇約束函數(shù)時(shí)通常存在生成結(jié)點(diǎn)數(shù)與約束函數(shù)計(jì)算量之間的折衷。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】6、問(wèn)題：下列算法中，通常以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的是（）。選項(xiàng)：A:貪心法B:動(dòng)態(tài)規(guī)劃法C:備忘錄法D:回溯法答案:【回溯法】7、問(wèn)題：裝載問(wèn)題的回溯算法所需的計(jì)算時(shí)間為選項(xiàng)：A:O（nlogn）B:O（n2）C:O（2n）D:O（n）答案:【O（2n）】8、問(wèn)題：?jiǎn)栴}的狀態(tài)生成法有（）選項(xiàng)：A:深度優(yōu)先生成法B:子集樹生成法C:寬度優(yōu)先生成法D:排列樹生成法答案:【深度優(yōu)先生成法;寬度優(yōu)先生成法】9、問(wèn)題：回溯法解題步驟選項(xiàng)：A:確定易于搜索的解空間結(jié)構(gòu)B:針對(duì)所給問(wèn)題，定義問(wèn)題的解空間C:確定最優(yōu)子結(jié)構(gòu)的性質(zhì)D:以深度優(yōu)先方式搜索解空間，在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。答案:【確定易于搜索的解空間結(jié)構(gòu);針對(duì)所給問(wèn)題，定義問(wèn)題的解空間;以深度優(yōu)先方式搜索解空間，在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索?！?0、問(wèn)題：回溯法的效率依賴于下列哪些因素（）選項(xiàng)：A:滿足顯約束的值的個(gè)數(shù)B:計(jì)算約束函數(shù)的時(shí)間C:確定解空間的時(shí)間D:計(jì)算限界函數(shù)的時(shí)間答案:【滿足顯約束的值的個(gè)數(shù);計(jì)算約束函數(shù)的時(shí)間;計(jì)算限界函數(shù)的時(shí)間】11、問(wèn)題：剪枝函數(shù)包括（）和約束函數(shù)選項(xiàng)：A:最優(yōu)函數(shù)B:限界函數(shù)C:估計(jì)函數(shù)D:啟發(fā)式函數(shù)答案:【限界函數(shù)】12、問(wèn)題：回溯法搜索解空間時(shí)，在搜索試探時(shí)選取x[i]的值順序是任意的，順序?qū)τ谟?jì)算量沒有差別。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】13、問(wèn)題：回溯法中，如果解空間樹是排列樹，所給問(wèn)題的規(guī)模為n時(shí)，遍歷排列樹需O(n!)計(jì)算時(shí)間.選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】14、問(wèn)題：回溯法的兩種解空間樹為（）選項(xiàng)：A:遞歸樹B:祖先樹C:子集樹D:排列樹答案:【子集樹;排列樹】第九章單元測(cè)試1、問(wèn)題：分支限界法在對(duì)問(wèn)題的解空間樹進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)有多次機(jī)會(huì)成為活結(jié)點(diǎn)。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【錯(cuò)】2、問(wèn)題：分支限界法找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】3、問(wèn)題：隊(duì)列式分支限界法以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【錯(cuò)】4、問(wèn)題：優(yōu)先隊(duì)列式分支限界法按照隊(duì)列先進(jìn)先出的原則，選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】5、問(wèn)題：分支限界法解旅行商問(wèn)題時(shí)的解空間樹是選項(xiàng)：A:排列樹B:深度優(yōu)先生成樹C:廣度優(yōu)先生成樹D:子集樹答案:【排列樹】6、問(wèn)題：優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是選項(xiàng)：A:結(jié)點(diǎn)的優(yōu)先級(jí)B:隨機(jī)C:先進(jìn)先出D:后進(jìn)先出答案:【結(jié)點(diǎn)的優(yōu)先級(jí)】7、問(wèn)題：用分支限界法設(shè)計(jì)算法的步驟是：選項(xiàng)：A:定義最優(yōu)子結(jié)構(gòu)B:以廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索C:確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）D:針對(duì)所給問(wèn)題，定義問(wèn)題的解空間（對(duì)解進(jìn)行編碼）答案:【以廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索;確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）;針對(duì)所給問(wèn)題，定義問(wèn)題的解空間（對(duì)解進(jìn)行編碼）】8、問(wèn)題：分支限界法與回溯法的不同點(diǎn)是什么？選項(xiàng)：A:搜索方式不同B:對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同C:求解目標(biāo)不同D:存儲(chǔ)空間的要求不同答案:【搜索方式不同;對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同;求解目標(biāo)不同;存儲(chǔ)空間的要求不同】9、問(wèn)題：FIFO是（）的搜索方式。選項(xiàng)：A:分支限界B:動(dòng)態(tài)規(guī)劃C:回溯算法D:貪心算法答案:【分支限界】10、問(wèn)題：下面說(shuō)法不正確的是（）選項(xiàng)：A:用限界函數(shù)剪去得不到最優(yōu)解的子樹B:用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹C:使用限界函數(shù)作優(yōu)先級(jí),第一個(gè)加入隊(duì)列的葉子就是最優(yōu)解D:回溯和分支限界都是動(dòng)態(tài)生成解空間樹答案:【使用限界函數(shù)作優(yōu)先級(jí),第一個(gè)加入隊(duì)列的葉子就是最優(yōu)解】11、問(wèn)題：在對(duì)問(wèn)題的解空間樹進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)的是（）。選項(xiàng)：A:回溯和分支限界B:回溯C:回溯求解子集樹問(wèn)題D:分支限界答案:【分支限界】12、問(wèn)題：使用限界函數(shù)作優(yōu)先級(jí),第一個(gè)擴(kuò)展的葉子就是最優(yōu)解選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】13、問(wèn)題：分支限界法不能解決0/1背包問(wèn)題選項(xiàng)：A:錯(cuò)B:對(duì)答案:【錯(cuò)】第十章單元測(cè)試1、問(wèn)題：網(wǎng)絡(luò)流滿足容量約束，但一般不滿足流量守恒約束。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【錯(cuò)】2、問(wèn)題：設(shè)G=為二分圖,|V1|≤|V2|,M為G中一個(gè)最大匹配,且|M|=|V1|,則稱M為G的完備匹配，也是最大匹配。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】3、問(wèn)題：存在割(A,B)使流值v(f)=割的容量cap(A,B)，則割(A,B)是最小割。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】4、問(wèn)題：給定連通圖G,BFS遍歷得到層次圖，如果同一層中的結(jié)點(diǎn)無(wú)邊相連，則G是二分圖。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】5、問(wèn)題：有下界的流通問(wèn)題不一定有可行流。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】6、問(wèn)題：Dinic算法的時(shí)間復(fù)雜度為（）選項(xiàng)：A:m2nB:mnC:mn2D:m2logC答案:【mn2】7、問(wèn)題：如果每條邊的最大容量為1，則時(shí)間復(fù)雜度是O(nm)的網(wǎng)絡(luò)流算法有選項(xiàng)：A:FF算法B:容量縮放算法C:Dinic算法D:EK算法答案:【FF算法】8、問(wèn)題：改進(jìn)FF網(wǎng)絡(luò)流算法，可以通過(guò)選擇（）增廣路，降低時(shí)間復(fù)雜度。選項(xiàng)：A:最大容量B:最短路徑C:最大瓶頸容量D:邊數(shù)最少答案:【最大容量;最短路徑;最大瓶頸容量;邊數(shù)最少】9、問(wèn)題：帶需求的流通必須滿足供給和=需求和選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】10、問(wèn)題：匈牙利算法中起點(diǎn)和終點(diǎn)都是未匹配點(diǎn)的交錯(cuò)路徑稱為可增廣路徑，可增廣路徑有奇數(shù)條邊。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】11、問(wèn)題：給定二分圖G=中無(wú)孤立點(diǎn)，其最大流算法求得最大流f,則G的最大匹配數(shù)=f.選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】12、問(wèn)題：設(shè)G=中無(wú)孤立點(diǎn)。W為G的最小邊覆蓋,若G中存在相鄰邊就移去其中一條。設(shè)移去的邊集為N，則是G的最大匹配。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】13、問(wèn)題：設(shè)f是網(wǎng)絡(luò)N的任意流，(A,B)是N的任意s-t割，則流值f至多等于割的容量。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】第十一章單元測(cè)試1、問(wèn)題：蒙特卡羅算法的結(jié)果肯定是一個(gè)正確解。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】2、問(wèn)題：Sherwood算法隨機(jī)選擇一個(gè)數(shù)組元素作為劃分標(biāo)準(zhǔn)求解k小元素問(wèn)題,保證線性時(shí)間的平均性能。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】3、問(wèn)題：借助隨機(jī)預(yù)處理技術(shù)，不改變?cè)械拇_定性算法，僅對(duì)其輸入進(jìn)行隨機(jī)洗牌，可收到舍伍德算法的效果。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】4、問(wèn)題：隨機(jī)算法共同點(diǎn)是計(jì)算時(shí)間越多或運(yùn)行次數(shù)越多,正確性越高.選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】5、問(wèn)題：增加拉斯維加斯算法的反復(fù)求解次數(shù),可使求解無(wú)效的概率任意小。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】6、問(wèn)題：在下列算法中有時(shí)找不到問(wèn)題解的是選項(xiàng)：A:蒙特卡羅算法B:數(shù)值隨機(jī)算法C:拉斯維加斯算法D:舍伍德算法答案:【拉斯維加斯算法】7、問(wèn)題：肯定獲得可行解，但不一定是正確解的算法是選項(xiàng)：A:蒙特卡羅算法B:拉斯維加斯算法C:數(shù)值隨機(jī)算法D:舍伍德算法答案:【蒙特卡羅算法】8、問(wèn)題：在一般輸入數(shù)據(jù)的程序里，輸入多少會(huì)影響到算法的計(jì)算復(fù)雜度，為了消除這種影響可用（）對(duì)輸入進(jìn)行預(yù)處理。選項(xiàng)：A:蒙特卡羅算法B:舍伍德算法C:拉斯維加斯算法D:數(shù)值隨機(jī)化算法答案:【舍伍德算法】9、問(wèn)題：下面說(shuō)法正確的是選項(xiàng)：A:現(xiàn)實(shí)計(jì)算機(jī)上無(wú)法產(chǎn)生真正的隨機(jī)數(shù)B:蒙特卡羅算法總是能提供問(wèn)題的一個(gè)解,但可能給出錯(cuò)誤解。C:舍伍德算法的精髓不是避免最壞的情況，而是設(shè)法消除最壞情況和特定實(shí)例的關(guān)聯(lián)性。D:求解同一實(shí)例用同一隨機(jī)化算法求解兩次，所用時(shí)間和所得結(jié)果可能完全不同。答案:【現(xiàn)實(shí)計(jì)算機(jī)上無(wú)法產(chǎn)生真正的隨機(jī)數(shù);蒙特卡羅算法總是能提供問(wèn)題的一個(gè)解,但可能給出錯(cuò)誤解。;舍伍德算法的精髓不是避免最壞的情況，而是設(shè)法消除最壞情況和特定實(shí)例的關(guān)聯(lián)性。;求解同一實(shí)例用同一隨機(jī)化算法求解兩次，所用時(shí)間和所得結(jié)果可能完全不同?！?0、問(wèn)題：下面說(shuō)法正確的是（）選項(xiàng)：A:線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法B:當(dāng)最壞和平均情況差別較大時(shí),舍伍德算法可以消除好壞實(shí)例的差別，達(dá)到平均實(shí)例的性能C:隨機(jī)算法是一種使用概率和統(tǒng)計(jì)方法在其執(zhí)行過(guò)程中對(duì)于下一計(jì)算步驟作出隨機(jī)選擇的算法D:增加蒙特卡羅算法的求解次數(shù),可使求解錯(cuò)誤的概率任意小。答案:【線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法;當(dāng)最壞和平均情況差別較大時(shí),舍伍德算法可以消除好壞實(shí)例的差別，達(dá)到平均實(shí)例的性能;隨機(jī)算法是一種使用概率和統(tǒng)計(jì)方法在其執(zhí)行過(guò)程中對(duì)于下一計(jì)算步驟作出隨機(jī)選擇的算法;增加蒙特卡羅算法的求解次數(shù),可使求解錯(cuò)誤的概率任意小?！?1、問(wèn)題：確定性算法的每一計(jì)算步驟都確定,求解同一實(shí)例用同一算法求解兩次，所得結(jié)果完全相同。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】12、問(wèn)題：舍伍德算法總是有解,且解總是正確的，但最壞性能未改變。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】13、問(wèn)題：拉斯維加斯算法肯定得到一個(gè)正確解。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【錯(cuò)】14、問(wèn)題：隨機(jī)抽取數(shù)組元素k次,從最接近搜索元素x的位置順序搜索,順序搜索的平均比較次數(shù)為O(n/(k+1)).選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】第十二章單元測(cè)試1、問(wèn)題：有多項(xiàng)式時(shí)間算法的問(wèn)題是易解問(wèn)題選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】2、問(wèn)題：EXP類是所有指數(shù)時(shí)間可解的判定問(wèn)題組成的問(wèn)題類選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】3、問(wèn)題：如果對(duì)于X的任意實(shí)例，通過(guò)多項(xiàng)式次的計(jì)算步驟，加多項(xiàng)式次調(diào)用Y的算法，可解決X，則X可多項(xiàng)式時(shí)間歸約到Y(jié)。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】4、問(wèn)題：下面關(guān)于NP問(wèn)題說(shuō)法正確的是（）選項(xiàng)：A:NP完全問(wèn)題是P類問(wèn)題的子集B:NP類問(wèn)題包含在P類問(wèn)題中C:P類問(wèn)題包含在NP類問(wèn)題中D:NP問(wèn)題都是不可能解決的問(wèn)題答案:【P類問(wèn)題包含在NP類問(wèn)題中】5、問(wèn)題：下面屬于NP完全問(wèn)題的是（）選項(xiàng)：A:旅行商問(wèn)題B:最大獨(dú)立集C:最小頂點(diǎn)覆蓋答案:【旅行商問(wèn)題;最大獨(dú)立集;最小頂點(diǎn)覆蓋;】6、問(wèn)題：以下關(guān)于判定問(wèn)題難易處理的敘述中錯(cuò)誤的是選項(xiàng)：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)題是不能處理的答案:【需要超過(guò)多項(xiàng)式時(shí)間算法求解的問(wèn)題是易處理的;可以由多項(xiàng)式時(shí)間算法求解的問(wèn)題是難處理的;需要超過(guò)多項(xiàng)式時(shí)間算法求解