算法分析與設(shè)計智慧樹知到答案章節(jié)測試2023年山東財經(jīng)大學

第一章測試一個問題的同一實例可以有不同的表示形式

A:對

B:錯

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

A:對

B:錯

答案:A問題的兩個要素是輸入和實例。

A:錯

B:對

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

A:輸入

B:輸出

C:確定性

D:有窮性

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

A:(3)(1)(5)(4)(2)

B:(3)(1)(4)(5)(2)

C:(3)(4)(1)(5)(2)

D:(1)(2)(3)(4)(5)

答案:A下面說法關(guān)于算法與問題的說法錯誤的是（）。

A:算法是一種計算方法，對問題的每個實例計算都能得到正確答案。

B:如果一個算法能應用于問題的任意實例，并保證得到正確解答，稱這個算法解答了該問題。

C:證明算法不正確，需要證明對任意實例算法都不能正確處理。

D:同一問題可能有幾種不同的算法，解題思路和解題速度也會顯著不同。

答案:C下面關(guān)于程序和算法的說法正確的是（）。

A:算法的每一步驟必須要有確切的含義，必須是清楚的、無二義的。

B:算法是一個過程，計算機每次求解是針對問題的一個實例求解。

C:程序是算法用某種程序設(shè)計語言的具體實現(xiàn)。

D:程序總是在有窮步的運算后終止。

答案:ABC最大獨立集問題和（）問題等價。

A:最小頂點覆蓋

B:區(qū)間調(diào)度問題

C:最大團

D:穩(wěn)定匹配問題

答案:AC給定兩張喜歡列表，穩(wěn)定匹配問題的輸出是（

）

。

A:完美匹配

B:沒有不穩(wěn)定配對

C:最大匹配

D:穩(wěn)定匹配

答案:ABCD問題變換的目的有（）。(1)復雜變簡單(2)未知變已知(3)隱式變顯式(4)難解變易解（5）以上都是。

A:（2）

B:（4）

C:（3）

D:（1）

E:（5）

答案:E按照霍納法則，計算p(x)=anxn

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

的數(shù)量級為____。

A:n

B:nlogn

C:logn

D:n^2

答案:A第二章測試時間復雜度是指算法最壞情況下的運行時間。

A:錯

B:對

答案:Bf(n)=3n3+7n2+4nlogn=O（n2）

A:錯

B:對

答案:A如果一個算法是多項式時間算法，該算法是有效的,是好算法。

A:對

B:錯

答案:A算法復雜度分析的兩種基本方法為（

）和（

）。

A:平攤復雜度

平滑復雜度

B:幾何復雜度

平均復雜度

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

面向?qū)ο蠓椒?/p>

D:事后統(tǒng)計

事前分析

答案:D下面程序的時間復雜度為（）

x=1fori=1ton

doforj=1toido

fork=1tojdo

x++

A:O(n^3)

B:O(n^2)

C:O(n)

D:O(nlogn)

答案:A對近似遞增序列的線性表從小到大排序，使用哪種方法好？

A:插入排序

B:歸并排序

C:快速排序

D:堆排序

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

A:順序存儲

B:壓縮存儲

C:散列存儲

D:鏈式存儲

答案:AD給定n個元素的數(shù)組A，n=10^3,使用折半查找比使用順序查找大約快___倍。

A:1000

B:10

C:10^(3/2)

D:100

答案:D則f(n)的漸進性態(tài)f(n)=Ω(

)

A:1

B:n^2

C:n

D:100

答案:Af=O(g)當且僅當g=Ω(f)

A:錯

B:對

答案:B第三章測試0-1背包問題的枚舉算法的時間復雜度為O（2n）

A:錯

B:對

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

A:對

B:錯

答案:A分塊查找一般設(shè)分塊的長度是n/2.

A:對

B:錯

答案:B枚舉法適用于問題的小規(guī)模實例。

A:對

B:錯

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

A:增量構(gòu)造法

B:位向量法

C:二進制法

答案:C從所有候選答案中去搜索正確的解，這是

（）算法。

A:枚舉

B:蠻力

C:遞推

答案:Alogn2=(

)(logn+5)

A:θ

B:O

C:w

D:o

答案:A0-1背包問題的枚舉算法，如果在百萬次每秒的計算機上運行，1年可以計算的問題規(guī)模估計是？

A:40

B:60

C:50

D:30

答案:A分數(shù)拆分問題的枚舉算法通過（）方法進行了優(yōu)化。

A:減少枚舉變量

B:減少枚舉變量的值域

C:優(yōu)化數(shù)學模型

D:優(yōu)化數(shù)據(jù)結(jié)構(gòu)

答案:ABC下面那些算法的時間復雜度為O（）?

A:折半查找

B:插入排序

C:冒泡排序

D:順序查找

E:折半插入排序

答案:BCEA公司處理器速度是B公司的100倍。對于復雜度為n^2的算法，B公司的計算機可以在1小時內(nèi)處理規(guī)模為n的問題，A公司的計算機在1小時能處理的問題規(guī)模是（）

A:n^2

B:10n

C:n

D:100n

答案:B冒泡排序的時間復雜度為Ω(n^2)

A:錯

B:對

答案:A第四章測試貪心算法總能找到可行解，但未必是最優(yōu)解。

A:對

B:錯

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

A:對

B:錯

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

A:錯

B:對

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

A:錯

B:對

答案:B貪心算法基本要素有（

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

A:重疊子問題性質(zhì)

B:貪心選擇性質(zhì)

C:分解合并性質(zhì)

D:獨立子問題性質(zhì)

答案:B下面不是證明貪心算法證明方法的有（）。

A:界

B:交換論證

C:領(lǐng)先

D:優(yōu)化

答案:D最小生成樹問題可以使用的算法有（

）

A:Solim

B:Kruskal

C:Dijkstra

D:Prim

答案:ABD區(qū)間問題包含()

A:區(qū)間覆蓋

B:區(qū)間調(diào)度

C:區(qū)間選點

D:區(qū)間劃分

答案:ABCD負權(quán)的單源最短路問題可以使用Dijkstra算法求解

A:對

B:錯

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

A:對

B:錯

答案:B第五章測試正推是從小規(guī)模的問題推解出大規(guī)模間題的一種方法。

A:對

B:錯

答案:A一般來說，遞歸的效率高于遞推。

A:對

B:錯

答案:B從大規(guī)模問題逐步化為小規(guī)模問題的算法是（）

A:倒推

B:正推

C:迭代

D:遞歸

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

A:換元迭代

B:直接迭代

C:差消迭代

答案:C遞歸函數(shù)的要素是（）

A:輸入

B:遞歸方程

C:邊界條件

D:迭代

答案:BC遞歸變?yōu)榉沁f歸的方法有（）

A:尾遞歸

B:遞推

C:模擬棧

D:循環(huán)

答案:ABCT(n)=T(n-1)+n，T(1)=1，則T(n)=（）

A:n(n+1)/2

B:θ(n^2)

C:O(n^2)

D:Ω(n^2)

答案:ABCD遞歸一般用于解決問題有（）

A:數(shù)據(jù)的定義是按遞歸定義的

B:問題解法按遞歸實現(xiàn)

C:數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的

D:迭代問題

答案:ABC主方法可以求解滿足T(n)=aT(n/b)+f(n)形式的遞推方程，則下列關(guān)于方程中的約束中不準確的是？設(shè)

A:若f(n)=O(x)，則T(n)=Θ(xlogn)

B:對于系數(shù)b，必須滿足b>1

C:若對于常數(shù)e>0，f(n)=O(y)，則T(n)=Θ(x)

D:對于系數(shù)a，必須滿足a>=1

答案:A，則T(n)=（）

A:O(n)

B:Θ(n^2)

C:Ω(n^3)

D:O(nlogn)

答案:B循環(huán)用于重復性的工作。循環(huán)體的特點是：“以不變應萬變”。

A:對

B:錯

答案:A第六章測試分治法分解的子問題與原問題形式相同。

A:錯

B:對

答案:BN個元素排序的時間復雜度不可能是線性時間。

A:對

B:錯

答案:B三分法的判定樹是三叉樹。

A:錯

B:對

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

A:錯

B:對

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

)法。

A:基數(shù)排序

B:快速排序

C:冒泡排序

D:合并排序

答案:C堆排序的時間復雜度是O（）。

A:O（n2）

B:O（n）

C:O（2n）

D:O（nlogn）

答案:D改進分治算法的方法有（

）和改進劃分的對稱性。

A:減少子問題數(shù)

B:加速原理

C:備忘錄

D:擬陣原理

答案:A通過減少子問題個數(shù)，降低分治算法時間復雜度的有（）

A:最接近點對

B:Strassen矩陣乘法

C:大整數(shù)乘法

D:線性時間選擇

答案:BC分治法在每一層遞歸上有三個步驟（）

A:合并

B:選擇

C:分解

D:解決

答案:ACD使用分治法求解不需要滿足的條件是（）。

A:子問題的解可以合并

B:子問題必須是一樣的

C:子問題不能夠重復

D:原問題和子問題使用相同的方法求解

答案:B最小堆中每個元素調(diào)整的次數(shù)不超過樹高。

A:錯

B:對

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

A:錯

B:對

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

A:對

B:錯

答案:B找n個元素的中位數(shù)的分治算法的時間復雜度為O().

A:n

B:nlogn

C:logn

D:n^2

答案:A第七章測試動態(tài)規(guī)劃算法把原問題分為交叉的子問題，解決子問題，記錄子問題的解，合并為原問題的解。

A:錯

B:對

答案:B0/1背包問題的動態(tài)規(guī)劃算法是多項式時間算法。

A:錯

B:對

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

A:對

B:錯

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

A:錯

B:對

答案:B含負權(quán)的最短路問題一般使用（）求解。

A:網(wǎng)絡(luò)流算法

B:分治算法

C:動態(tài)規(guī)劃

D:貪心算法

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

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

A:重疊子問題性質(zhì)

B:獨立子問題性質(zhì)

C:分解合并性質(zhì)

D:貪心選擇性質(zhì)

答案:A下面不是動態(tài)規(guī)劃的基本方法有（）。

A:多重選擇

B:舍入

C:增加變量

D:區(qū)間變量

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

A:Floyd算法

B:Bellman算法

C:Dijkstra算法

D:SPFA算法

答案:BCD分治算法與動態(tài)規(guī)劃算法的相同點是（）

A:子問題重疊

B:最優(yōu)子結(jié)構(gòu)

C:子問題獨立

D:遞推關(guān)系

答案:BDDAG上最短路，固定起點和終點沒有意義。

A:對

B:錯

答案:BDAG圖最長路的遞推函數(shù)d(i)表示從某個頂點i出發(fā)的最長路長度。

A:對

B:錯

答案:A樹上最大權(quán)獨立集不包含u，可能包含兒子結(jié)點，也可能不包含兒子結(jié)點。

A:對

B:錯

答案:ASPFA算法的時間復雜度為O（mn）

A:錯

B:對

答案:B第八章測試回溯法是按廣度優(yōu)先策略搜索解空間樹。

A:錯

B:對

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

A:錯

B:對

答案:A回溯法的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。

A:對

B:錯

答案:A回溯法不適用于解一些組合數(shù)相當大的問題。

A:對

B:錯

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

A:對

B:錯

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

）。

A:動態(tài)規(guī)劃法

B:回溯法

C:貪心法

D:備忘錄法

答案:B裝載問題的回溯算法所需的計算時間為

A:O（n）

B:O（nlogn）

C:O（n2）

D:O（2n）

答案:D問題的狀態(tài)生成法有（）

A:排列樹生成法

B:子集樹生成法

C:深度優(yōu)先生成法

D:寬度優(yōu)先生成法

答案:CD回溯法解題步驟

A:以深度優(yōu)先方式搜索解空間，在搜索過程中用剪枝函數(shù)避免無效搜索。

B:確定易于搜索的解空間結(jié)構(gòu)

C:針對所給問題，定義問題的解空間

D:確定最優(yōu)子結(jié)構(gòu)的性質(zhì)

答案:ABC回溯法的效率依賴于下列哪些因素（

）

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

B:計算限界函數(shù)的時間

C:確定解空間的時間

D:滿足顯約束的值的個數(shù)

答案:ABD剪枝函數(shù)包括（）和約束函數(shù)

A:啟發(fā)式函數(shù)

B:最優(yōu)函數(shù)

C:估計函數(shù)

D:限界函數(shù)

答案:D回溯法搜索解空間時，在搜索試探時選取x[i]的值順序是任意的，順序?qū)τ谟嬎懔繘]有差別。

A:錯

B:對

答案:A回溯法中，如果解空間樹是排列樹，所給問題的規(guī)模為n時，遍歷排列樹需O(n!)計算時間.

A:錯

B:對

答案:B回溯法的兩種解空間樹為（）

A:子集樹

B:遞歸樹

C:排列樹

D:祖先樹

答案:AC第九章測試分支限界法在對問題的解空間樹進行搜索的方法中，一個活結(jié)點有多次機會成為活結(jié)點。

A:錯

B:對

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

A:對

B:錯

答案:A隊列式分支限界法以最小耗費優(yōu)先的方式搜索解空間樹。

A:錯

B:對

答案:A優(yōu)先隊列式分支限界法按照隊列先進先出的原則，選取下一個節(jié)點為擴展結(jié)點。

A:錯

B:對

答案:A分支限界法解旅行商問題時的解空間樹是

A:子集樹

B:排列樹

C:深度優(yōu)先生成樹

D:廣度優(yōu)先生成樹

答案:B優(yōu)先隊列式分支限界法選取擴展結(jié)點的原則是

A:結(jié)點的優(yōu)先級

B:隨機

C:先進先出

D:后進先出

答案:A用分支限界法設(shè)計算法的步驟是：

A:以廣度優(yōu)先或以最小耗費（最大收益）優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索

B:針對所給問題，定義問題的解空間（對解進行編碼）

C:定義最優(yōu)子結(jié)構(gòu)

D:確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）

答案:ABD分支限界法與回溯法的不同點是什么？

A:存儲空間的要求不同

B:求解目標不同

C:對擴展結(jié)點的擴展方式不同

D:搜索方式不同

答案:ABCDFIFO是（

）的搜索方式。

A:回溯算法

B:貪心算法

C:動態(tài)規(guī)劃

D:分支限界

答案:D下面說法不正確的是（）

A:用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹

B:回溯和分支限界都是動態(tài)生成解空間樹

C:使用限界函數(shù)作優(yōu)先級,第一個加入隊列的葉子就是最優(yōu)解

D:用限界函數(shù)剪去得不到最優(yōu)解的子樹

答案:C在對問題的解空間樹進行搜索的方法中，一個活結(jié)點最多有一次機會成為活結(jié)點的是（

）。

A:回溯求解子集樹問題

B:分支限界

C:回溯和分支限界

D:回溯

答案:B使用限界函數(shù)作優(yōu)先級,第一個擴展的葉子就是最優(yōu)解

A:對

B:錯

答案:A分支限界法不能解決0/1背包問題

A:錯

B:對

答案:A第十章測試網(wǎng)絡(luò)流滿足容量約束，但一般不滿足流量守恒約束。

A:對

B:錯

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

A:錯

B:對

答案:B存在割(A,B)

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

A:錯

B:對

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

A:錯

B:對

答案:B有下界的流通問題不一定有可行流。

A:對

B:錯

答案:ADinic算法的時間復雜度為（）

A:mn

B:m2n

C:m2logC

D:mn2

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

A:容量縮放算法

B:FF算法

C:Dinic算法

D:EK算法

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

）增廣路，降低時間復雜度。

A:邊數(shù)最少

B:最大容量

C:最短路徑

D:最大瓶頸容量

答案:ABCD帶需求的流通必須滿足供給和=需求和

A:對

B:錯

答案:A匈牙利算法中起點和終點都是未匹配點的交錯路徑稱為可增廣路徑，可增廣路徑有奇數(shù)條邊。

A:對

B:錯

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

A:對

B:錯

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

A:錯

B:對

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

A:對

B:錯

答案:A第十一章測試蒙特卡羅算法的結(jié)果肯定是一個正確解。

A:錯

B:對

答案:ASherwood算法隨機選擇一個數(shù)組元素作為劃分標準求解k小元素問題,保證線性時間的平均性能。

A:對

B:錯

答案:A借助隨機預處理技術(shù)，不改變原有的確定性算法，僅對其輸入進行隨機洗牌，可收到舍伍德算法的效果。

A:對

B:錯

答案:A隨機算法共同點是計算時間越多或運行次數(shù)越多,正確性越高.

A:對

B:錯

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

A:對

B:錯

答案:A在下列算法中有時找不到問題解的是

A:數(shù)值隨機算法

B:舍伍德算法

C:蒙特卡羅算法

D:拉斯維加斯算法

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

A:舍伍德算法

B:數(shù)值隨機算法

C:拉斯維加斯算法

D:蒙特卡羅算法

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

）對輸入進行預處理。

A:舍伍德算法

B:拉斯維加斯算法

C:蒙特卡羅算法

D:數(shù)值隨機化算法

答案:A下面說法正確的是

A:求解同一實例用同一隨機化算法求解兩次，所用時間和所得結(jié)果可能完全不同。

B:舍伍德算法的精髓不是避免最壞的情況，而是設(shè)法消除最壞情況和特定實例的關(guān)聯(lián)性。

C:現(xiàn)實計算機上無法產(chǎn)生真正的隨機數(shù)

D:蒙特卡羅算法總是能提供問題的一個解,但可能給出錯誤解。

答案:ABCD下面說法正確的是（）

A:隨機算法是一種使用概率和統(tǒng)計方法在其執(zhí)行過程中對于下一計算步驟作出隨機選擇的算法

B:線性同余法是產(chǎn)生偽隨機數(shù)的最常用的方法

C:當最壞和平均情況差別較大時,舍伍德算法可以消除好壞實例的差別，達到平均實例的性能

D:增加蒙特卡羅算法的求解次數(shù),可使求解錯誤的概率任意小。

答案:ABCD確定性算法的每一計算步驟都確定,求解同一實例用同一算法求解兩次，所得結(jié)果完全相同。

A:對

B:錯

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

A:對

B:錯

答案:B拉斯維加斯算法肯定得到一個正確解。

A:對

B:錯

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

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

A:錯

B:對

答案:B第十二章測試有多項式時間算法的問題是易解問題

A:對

B:錯

答案:AEXP類是所有指數(shù)時間可解的判定問題組成的問題類

A:對

B:錯

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

A:錯

B:對

答案:B下面關(guān)于NP問題說法正確的是（

）

A:NP問題都是不可能解決的問題

B:NP完全問題是P類問題的子集

C:P類問題包含在NP類問題中

D:NP類問題包含在P類問題中

答案:C下面屬于NP完全問題的是（）

A:最小頂點覆蓋

B:SAT

C:最大獨立集

D:旅行商問題

答案:ABCD以下關(guān)于判定問題難易處理的敘述中錯誤的是

A:可以由多項式時間算法求解的問題是難處理的

B:需要超過多項式時間算法求解的問題是易處理的

C:可以由多項式時間算法求解的問題是易處理的

D:需要超過多項式時間算法求解的問題是不能處理的

答案:ABD下列說法錯誤的是

A:如果一個NP完全問題有多項式