算法分析與設計知到智慧樹章節(jié)測試課后答案2024年秋山東財經大學

算法分析與設計知到智慧樹章節(jié)測試課后答案2024年秋山東財經大學第一章單元測試

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

A:對B:錯

答案:對同一數學模型使用不同的數據結構會有不同的算法，有效性有很大差別。

A:錯B:對

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

A:錯B:對

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

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

答案:有窮性解決問題的基本步驟是（）。（1）算法設計（2）算法實現（3）數學建模（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)下面說法關于算法與問題的說法錯誤的是（）。

A:同一問題可能有幾種不同的算法，解題思路和解題速度也會顯著不同。B:如果一個算法能應用于問題的任意實例，并保證得到正確解答，稱這個算法解答了該問題。C:證明算法不正確，需要證明對任意實例算法都不能正確處理。D:算法是一種計算方法，對問題的每個實例計算都能得到正確答案。

答案:證明算法不正確，需要證明對任意實例算法都不能正確處理。下面關于程序和算法的說法正確的是（）。

A:算法的每一步驟必須要有確切的含義，必須是清楚的、無二義的。B:算法是一個過程，計算機每次求解是針對問題的一個實例求解。C:程序是算法用某種程序設計語言的具體實現。D:程序總是在有窮步的運算后終止。

答案:算法的每一步驟必須要有確切的含義，必須是清楚的、無二義的。；算法是一個過程，計算機每次求解是針對問題的一個實例求解。；程序是算法用某種程序設計語言的具體實現。最大獨立集問題和（）問題等價。

A:最大團B:穩(wěn)定匹配問題C:最小頂點覆蓋D:區(qū)間調度問題

答案:最大團；最小頂點覆蓋給定兩張喜歡列表，穩(wěn)定匹配問題的輸出是（

）

。

A:最大匹配B:沒有不穩(wěn)定配對C:完美匹配D:穩(wěn)定匹配

答案:最大匹配；沒有不穩(wěn)定配對；完美匹配；穩(wěn)定匹配問題變換的目的有（）。(1)復雜變簡單(2)未知變已知(3)隱式變顯式(4)難解變易解（5）以上都是。

A:（3）

B:（2）

C:（1）

D:（5）E:（4）

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

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

的數量級為____。

A:nlogn

B:n

C:n^2

D:logn

答案:n

第二章單元測試

時間復雜度是指算法最壞情況下的運行時間。

A:對B:錯

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

A:對B:錯

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

A:錯B:對

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

）和（

）。

A:結構化方法

面向對象方法B:幾何復雜度

平均復雜度C:平攤復雜度

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

事前分析

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

事前分析下面程序的時間復雜度為（）

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)對近似遞增序列的線性表從小到大排序，使用哪種方法好？

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

答案:插入排序順序查找適合的數據結構是（）

A:壓縮存儲B:鏈式存儲C:順序存儲D:散列存儲

答案:鏈式存儲；順序存儲給定n個元素的數組A，n=10^3,使用折半查找比使用順序查找大約快___倍。

A:10^(3/2)

B:1000

C:10

D:100

答案:100

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

)

A:100

B:n^2

C:n

D:1

答案:1

f=O(g)當且僅當g=Ω(f)

A:錯B:對

答案:對

第三章單元測試

0-1背包問題的枚舉算法的時間復雜度為O（2n）

A:對B:錯

答案:錯增量構造法生成子集前需要對集合中元素從小到大排列。

A:錯B:對

答案:對分塊查找一般設分塊的長度是n/2.

A:對B:錯

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

A:錯B:對

答案:對便于實現集合操作的子集生成算法是（）

A:二進制法B:位向量法C:增量構造法

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

（）算法。

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

答案:枚舉logn2=(

)(logn+5)

A:wB:oC:O

D:θ

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

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

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

A:減少枚舉變量的值域B:優(yōu)化數據結構C:優(yōu)化數學模型D:減少枚舉變量

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

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

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

A:n

B:100n

C:10n

D:n^2

答案:10n

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

A:對B:錯

答案:錯

第四章單元測試

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

A:錯B:對

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

A:錯B:對

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

A:對B:錯

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

A:對B:錯

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

）和最優(yōu)子結構性質。

A:獨立子問題性質B:重疊子問題性質C:貪心選擇性質D:分解合并性質

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

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

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

）

A:KruskalB:PrimC:DijkstraD:Solim

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

A:區(qū)間調度B:區(qū)間選點C:區(qū)間劃分D:區(qū)間覆蓋

答案:區(qū)間調度；區(qū)間選點；區(qū)間劃分；區(qū)間覆蓋負權的單源最短路問題可以使用Dijkstra算法求解

A:對B:錯

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

A:對B:錯

答案:錯

第五章單元測試

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

A:錯B:對

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

A:錯B:對

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

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

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

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

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

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)

遞歸一般用于解決問題有（）

A:數據的定義是按遞歸定義的B:數據的結構形式是按遞歸定義的C:迭代問題D:問題解法按遞歸實現

答案:數據的定義是按遞歸定義的；數據的結構形式是按遞歸定義的；問題解法按遞歸實現主方法可以求解滿足T(n)=aT(n/b)+f(n)形式的遞推方程，則下列關于方程中的約束中不準確的是？設

A:若f(n)=O(x)，則T(n)=Θ(xlogn)B:若對于常數e>0，f(n)=O(y)，則T(n)=Θ(x)C:對于系數a，必須滿足a>=1D:對于系數b，必須滿足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)用于重復性的工作。循環(huán)體的特點是：“以不變應萬變”。

A:對B:錯

答案:對

第六章單元測試

分治法分解的子問題與原問題形式相同。

A:對B:錯

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

A:錯B:對

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

A:對B:錯

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

A:錯B:對

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

)法。

A:合并排序B:基數排序C:快速排序D:冒泡排序

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

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

答案:O（nlogn）改進分治算法的方法有（

）和改進劃分的對稱性。

A:擬陣原理B:減少子問題數C:備忘錄D:加速原理

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

A:最接近點對B:大整數乘法C:Strassen矩陣乘法D:線性時間選擇

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

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

答案:分解；合并；解決

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

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

答案:子問題必須是一樣的最小堆中每個元素調整的次數不超過樹高。

A:對B:錯

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

A:對B:錯

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

A:錯B:對

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

A:n^2B:n

C:lognD:nlogn

答案:n

第七章單元測試

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

A:對B:錯

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

A:對B:錯

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

A:對B:錯

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

A:錯B:對

答案:對含負權的最短路問題一般使用（）求解。

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

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

）和最優(yōu)子結構性質。

A:貪心選擇性質B:獨立子問題性質C:分解合并性質D:重疊子問題性質

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

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

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

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

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

A:最優(yōu)子結構B:遞推關系C:子問題獨立

D:子問題重疊

答案:最優(yōu)子結構；遞推關系DAG上最短路，固定起點和終點沒有意義。

A:對B:錯

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

A:錯B:對

答案:對樹上最大權獨立集不包含u，可能包含兒子結點，也可能不包含兒子結點。

A:對B:錯

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

A:對B:錯

答案:對

第八章單元測試

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

A:錯B:對

答案:錯死結點是正在產生兒子的結點。

A:對B:錯

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

A:對B:錯

答案:對回溯法不適用于解一些組合數相當大的問題。

A:對B:錯

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

A:對B:錯

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

）。

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

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

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

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

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

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

A:以深度優(yōu)先方式搜索解空間，在搜索過程中用剪枝函數避免無效搜索。B:針對所給問題，定義問題的解空間C:確定易于搜索的解空間結構D:確定最優(yōu)子結構的性質

答案:以深度優(yōu)先方式搜索解空間，在搜索過程中用剪枝函數避免無效搜索。；針對所給問題，定義問題的解空間；確定易于搜索的解空間結構回溯法的效率依賴于下列哪些因素（

）

A:計算約束函數的時間

B:確定解空間的時間C:計算限界函數的時間D:滿足顯約束的值的個數

答案:計算約束函數的時間

；計算限界函數的時間；滿足顯約束的值的個數剪枝函數包括（）和約束函數

A:限界函數

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

答案:限界函數

回溯法搜索解空間時，在搜索試探時選取x[i]的值順序是任意的，順序對于計算量沒有差別。

A:錯B:對

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

A:對B:錯

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

A:排列樹

B:子集樹C:遞歸樹D:祖先樹

答案:排列樹

；子集樹

第九章單元測試

分支限界法在對問題的解空間樹進行搜索的方法中，一個活結點有多次機會成為活結點。

A:錯B:對

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

A:對B:錯

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

A:對B:錯

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

A:對B:錯

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

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

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

A:先進先出B:隨機C:結點的優(yōu)先級D:后進先出

答案:結點的優(yōu)先級用分支限界法設計算法的步驟是：

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

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

A:存儲空間的要求不同B:求解目標不同C:對擴展結點的擴展方式不同D:搜索方式不同

答案:存儲空間的要求不同；求解目標不同；對擴展結點的擴展方式不同；搜索方式不同FIFO是（

）的搜索方式。

A:貪心算法

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

答案:分支限界

下面說法不正確的是（）

A:使用限界函數作優(yōu)先級,第一個加入隊列的葉子就是最優(yōu)解B:回溯和分支限界都是動態(tài)生成解空間樹C:用約束函數在擴展結點處剪去不滿足約束的子樹D:用限界函數剪去得不到最優(yōu)解的子樹

答案:使用限界函數作優(yōu)先級,第一個加入隊列的葉子就是最優(yōu)解在對問題的解空間樹進行搜索的方法中，一個活結點最多有一次機會成為活結點的是（

）。

A:回溯

B:分支限界

C:回溯和分支限界

D:回溯求解子集樹問題

答案:分支限界

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

A:對B:錯

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

A:對B:錯

答案:錯

第十章單元測試

網絡流滿足容量約束，但一般不滿足流量守恒約束。

A:錯B:對

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

A:錯B:對

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

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

A:錯B:對

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

A:對B:錯

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

A:錯B:對

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

A:m2nB:mn2C:m2logCD:mn

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

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

答案:FF算法改進FF網絡流算法，可以通過選擇（

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

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

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

A:對B:錯

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

A:錯B:對

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

A:錯B:對

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

A:對B:錯

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

A:對B:錯

答案:對

第十一章單元測試

蒙特卡羅算法的結果肯定是一個正確解。

A:錯B:對

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

A:對B:錯

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

A:錯B:對

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

A:對B:錯

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

A:錯B:對

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

A:數值隨機算法B:蒙特卡羅算法C:拉斯維加斯算法D:舍伍德算法

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

A:蒙特卡羅算法B:舍伍德算法C:拉斯維加斯算法D:數值隨機算法

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

）對輸入進行預處理。

A:數值隨機化算法B:舍伍德算法C:蒙特卡羅算法D:拉斯維加斯算法

答案:舍伍德算法下面說法正確的是

A:蒙特卡羅算法總是能提供問題的一個解,但可能給出錯誤解。B:舍伍德算法的精髓不是避免最壞的情況，而是設法消除最壞情況和特定實例的關聯性。C:求解同一實例用同一隨機化算法求解兩次，所用時間和所得結果可能完全不同。D:現實計算機上無法產生真正的隨機數

答案:蒙特卡羅算法總是能提供問題的一個解,但可能給出錯誤解。；舍伍德算法的精髓不是避免最壞的情況，而是設法消除最壞情況和特定實例的關聯性。；求解同一實例用同一隨機化算法求解兩次，所用時間和所得結果可能完全不同。；現實計算機上無法產生真正的隨機數下面說法正確的是（）

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

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

A:對B:錯

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

A:對B:錯

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

A:對B:錯

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

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

A:錯B:對

答案:對

第十二章單元測試

有多項式時間算法的問題是易解問題

A:錯B:對

答案:對EXP類是所有指數時間可解的判定問題組成的問題類

A:錯B:對

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

A:錯B:對

答案:對下面關于NP問題說法正確的是（

）

A:NP完全問題是P類問題的子集B:NP類問題包含在P類問題中C:NP問題都是不可能解決的問題D:P類問題包含在NP類問題中

答案:P類問題包含在NP類問題中下面屬于NP完全問題的是（）

A:旅行商問題B:SATC:最小頂點覆蓋D:最大獨立集

答案:旅行商問題；SAT；最小頂點覆蓋；最大獨立集以下關于判定問題難易處理的敘述中錯誤的是

A:需要超過多項式時間算法求解的問題是易處理的B:可以由多項式時間算法求解的問題是易處理的C:需要超過多項式時間算法求解的問題是不能處理的D:可以由多項式時間算法求解的問題是難處理的

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