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

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

下列對(duì)算法的理解不正確的是（）。

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

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

A:低階項(xiàng)和常系數(shù)的精確計(jì)算B:最高次項(xiàng)的系數(shù)C:實(shí)際運(yùn)行時(shí)間的精確測(cè)量D:最高次項(xiàng)并忽略常系數(shù)

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

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

答案:最壞情況使用漸近符號(hào)的函數(shù)通?？坍嬎惴ǖ倪\(yùn)行時(shí)間，但是漸近符號(hào)也可以適用于刻畫算法的某個(gè)其他方面的函數(shù)，甚至可以適用于和算法沒有任何關(guān)系的函數(shù)。（）

A:錯(cuò)B:對(duì)

答案:對(duì)在算法分析中，常用大O記號(hào)限制算法的（）。

A:平均情況運(yùn)行時(shí)間B:最好情況運(yùn)行時(shí)間C:最壞情況運(yùn)行時(shí)間

答案:最壞情況運(yùn)行時(shí)間

第二章單元測(cè)試

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

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

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

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

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

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

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

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

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

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

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

第三章單元測(cè)試

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

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

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

A:

O(1)

B:

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

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

A:對(duì)B:錯(cuò)

答案:錯(cuò)在計(jì)算矩陣乘法時(shí)，Strassen算法提升性能的主要策略是什么？（）

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

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

A:對(duì)B:錯(cuò)

答案:錯(cuò)

第四章單元測(cè)試

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

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

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

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

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

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

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

A:錯(cuò)B:對(duì)

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

A:對(duì)B:錯(cuò)

答案:對(duì)

第五章單元測(cè)試

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

A:對(duì)B:錯(cuò)

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

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

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

A:對(duì)B:錯(cuò)

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

A:錯(cuò)B:對(duì)

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

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

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

第六章單元測(cè)試

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

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

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

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

答案:圖的邊著色問題；圖的頂點(diǎn)著色問題。（）

A:對(duì)B:錯(cuò)

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

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

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

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

答案:價(jià)值

第七章單元測(cè)試

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

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

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

A:錯(cuò)B:對(duì)

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