算法設(shè)計與分析知到智慧樹章節(jié)測試課后答案2024年秋蘇州大學(xué)

算法設(shè)計與分析知到智慧樹章節(jié)測試課后答案2024年秋蘇州大學(xué)第一章單元測試

下列對算法的理解不正確的是（）。

A:算法要求是一步步執(zhí)行，每一步都能得到唯一的結(jié)果B:算法一般是機(jī)械的，有時要進(jìn)行大量重復(fù)的計算，它的優(yōu)點是一種通法C:算法有一個共同特點就是對一類問題都有效(而不是個別問題)D:任何問題都可以用算法來解決

答案:任何問題都可以用算法來解決算法漸近時間復(fù)雜度的分析主要關(guān)注哪一方面？（）

A:低階項和常系數(shù)的精確計算B:最高次項的系數(shù)C:實際運行時間的精確測量D:最高次項并忽略常系數(shù)

答案:最高次項并忽略常系數(shù)漸近時間復(fù)雜度分析中，通常認(rèn)為哪種情況對算法選擇更重要？（）

A:最壞情況B:最好情況C:最佳和最壞情況的平均D:平均情況

答案:最壞情況使用漸近符號的函數(shù)通常刻畫算法的運行時間，但是漸近符號也可以適用于刻畫算法的某個其他方面的函數(shù)，甚至可以適用于和算法沒有任何關(guān)系的函數(shù)。（）

A:錯B:對

答案:對在算法分析中，常用大O記號限制算法的（）。

A:平均情況運行時間B:最好情況運行時間C:最壞情況運行時間

答案:最壞情況運行時間

第二章單元測試

下面關(guān)于NP問題說法正確的是（）

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

答案:P類問題包含在NP類問題中下面關(guān)于NPC問題說法不正確的是（）

A:所有的NPC問題之間可相互歸約B:非確定性多項式時間不可解決C:如果一個NPC問題在多項式時間可解，則所有NP問題在多項式時間可解D:所有的NP類問題可歸約成該問題

答案:非確定性多項式時間不可解決假設(shè)存在兩個問題X、Y，問題X可以在多項式時間內(nèi)歸約為問題Y，下面說法正確的是（）

A:如果問題X是NPC，那么問題Y是NP-hard的B:如果問題X是NP-hard，那么問題Y也是NP難的C:如果問題X是NP-hard，那么問題Y是NPCD:如果Y是易處理的（多項式時間可解），那么問題X也是易處理的

答案:如果問題X是NP-hard，那么問題Y也是NP難的；如果Y是易處理的（多項式時間可解），那么問題X也是易處理的假設(shè)集合I是圖G的獨立集，集合C是圖G的頂點覆蓋集，下面說法不正確的是（）

A:對于圖G中任意一條邊(u,v)，有u∈I或v∈IB:對于圖G中任意一條邊(u,v)，有u∈C且v∈CC:假設(shè)V為圖G的頂點集合，則有I=V-CD:對于圖G中任意一條邊(u,v)，有u∈C或v∈C

答案:對于圖G中任意一條邊(u,v)，有u∈I或v∈I下列關(guān)于CNF-SAT問題的說法中，正確的是（）

A:對于任意的CNF都存在使得表達(dá)式為真的賦值B:CNF-SAT是一個P問題C:3-CNF可滿足性問題可以在多項式時間內(nèi)被歸約到圖的獨立集問題D:對于一個CNF-SAT問題，可以在多項式時間內(nèi)驗證一個解的正確性

答案:3-CNF可滿足性問題可以在多項式時間內(nèi)被歸約到圖的獨立集問題；對于一個CNF-SAT問題，可以在多項式時間內(nèi)驗證一個解的正確性

第三章單元測試

以下哪些算法或問題是基于分治算法設(shè)計的或者能通過分治算法解決？（）。

A:歸并排序B:快速排序C:二分查找D:漢諾塔

答案:歸并排序；快速排序；二分查找；漢諾塔分治法求解平面最接近點對問題的時間復(fù)雜度是（）。

A:

O(1)

B:

O(n)C:D:O(nlgn)E:F:G:O(n2)H:

答案:O(nlgn)；快速傅里葉變換求解大整數(shù)乘法利用了插值計算的思想，通過將兩個大整數(shù)分別表示為多項式形式，利用FFT求解點值對，最后利用離散傅里葉變換求解出系數(shù)向量。（）

A:對B:錯

答案:錯在計算矩陣乘法時，Strassen算法提升性能的主要策略是什么？（）

A:使用隨機(jī)化技術(shù)選擇子矩陣B:應(yīng)用快速傅里葉變換C:增加矩陣分解的級別D:將8個子問題減少到7個

答案:將8個子問題減少到7個在快速排序的隨機(jī)化版本中，對于所有輸入數(shù)據(jù)，排序的時間復(fù)雜度始終保持不變。（）

A:對B:錯

答案:錯

第四章單元測試

在使用動態(tài)規(guī)劃求解最長公共子序列問題時，下列哪個步驟描述了問題的遞推過程？（）

A:根據(jù)dp[m][n]的值，構(gòu)造最長公共子序列。B:通過遞推關(guān)系式dp[i][j]=max(dp[i-1][j],dp[i][j-1])，填充dp數(shù)組。C:初始化邊界條件，即當(dāng)i或j為0時，dp[i][j]=0。D:定義二維數(shù)組dp，其中dp[i][j]表示序列A的前i個元素和序列B的前j個元素的最長公共子序列長度。

答案:通過遞推關(guān)系式dp[i][j]=max(dp[i-1][j],dp[i][j-1])，填充dp數(shù)組。在0-1背包問題中，動態(tài)規(guī)劃的主要目的是什么？（）

A:找到最輕的物品組合B:最大化背包中物品的總價值C:平衡背包中物品的重量和價值D:最小化背包中物品的數(shù)量

答案:最大化背包中物品的總價值在0-1背包問題的動態(tài)規(guī)劃求解方法中，遞歸式計算的是什么？（）

A:確定哪些物品被選中B:判斷是否超過背包容量C:計算每個物品的價值D:計算達(dá)到當(dāng)前容量下的最大價值

答案:計算達(dá)到當(dāng)前容量下的最大價值矩陣鏈乘實質(zhì)上是一個最優(yōu)括號化問題。（）

A:錯B:對

答案:對在動態(tài)規(guī)劃問題中，最優(yōu)子結(jié)構(gòu)要素描述了問題的最優(yōu)解可以通過子問題的最優(yōu)解來構(gòu)造。（）

A:對B:錯

答案:對

第五章單元測試

多機(jī)調(diào)度問題是用貪心算法求最優(yōu)解的一個例子，貪心策略是每次從剩余任務(wù)中選擇一個花費時間最長的任務(wù)，安排在占用時間最少的機(jī)器上。（）

A:對B:錯

答案:對下列問題中不能用貪心算法求得最優(yōu)解的是（）。

A:單源最短路徑問題B:0-1背包問題C:霍夫曼編碼問題D:最小生成樹問題

答案:0-1背包問題所有可以用貪心法求出最優(yōu)解的問題都可以形式化為在一個加權(quán)擬陣中找到一個權(quán)值最大的獨立子集。（）

A:對B:錯

答案:錯若一應(yīng)用問題能被抽象為在加權(quán)擬陣中尋找最優(yōu)子集，那么一定能用加權(quán)擬陣上的通用貪心算法求出其最優(yōu)解。（）

A:錯B:對

答案:對0-1背包問題中每個物品有固定的重量和價值，要求不能將物品部分放入，需求解放入物品使得總價值最大。對于此問題，以下哪種算法可以獲得最優(yōu)解？（）

A:動態(tài)規(guī)劃B:兩者均可C:無法確定D:貪心算法

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

第六章單元測試

下列不屬于放寬實際問題求解中對時間性能要求的方法的是（）

A:近似算法B:引入不確定性的算法C:超多項式時間啟發(fā)D:啟發(fā)式概率分析

答案:引入不確定性的算法下列問題中，具有絕對近似算法的問題是（）

A:圖的邊著色問題B:團(tuán)問題C:圖的頂點著色問題D:0-1背包問題

答案:圖的邊著色問題；圖的頂點著色問題。（）

A:對B:錯

答案:錯FPTAS算法的時間復(fù)雜度是（）

A:多項式時間B:指數(shù)時間C:不確定，取決于輸入規(guī)模D:對數(shù)時間

答案:多項式時間FPTAS算法的第一步是對0-1背包問題中的什么進(jìn)行適當(dāng)?shù)目s放，以確保算法的多項式性質(zhì)？（）

A:價值B:重量C:物品數(shù)量D:容量

答案:價值

第七章單元測試

在使用數(shù)字型概率算法求解定積分的時候，為達(dá)到一定的精度，假設(shè)一維積分需要1000個采樣點才能達(dá)到一定精度，那么三維積分需要的采樣點數(shù)量可能為（）。

A:1000^2B:1000C:1000^3D:任意數(shù)目的點都可以

答案:1000^3在計算π值的問題中，Crude算法的方差和精度都優(yōu)于HitorMiss算法，因此它總是更優(yōu)的。（）

A:錯B:對

答案:錯在使用有回放抽樣并統(tǒng)計第一次重復(fù)抽樣所用的實驗次數(shù)的方法來估計集合的勢的時候，這種算法的時間復(fù)雜度和空間復(fù)雜度均為θ(√n)(n為集合的勢)