算法分析與設(shè)計智慧樹知到課后章節(jié)答案2023年下湖南中醫(yī)藥大學

算法分析與設(shè)計智慧樹知到課后章節(jié)答案2023年下湖南中醫(yī)藥大學湖南中醫(yī)藥大學

第一章測試

算法是指解決問題的方法或過程，它包含一系列步驟，用來將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)果。

A:錯B:對

答案:對

使用偽代碼描述算法具有（）等優(yōu)點。

A:易于轉(zhuǎn)化為程序語言代碼B:格式統(tǒng)一規(guī)范C:簡單易懂D:容易修改

答案:易于轉(zhuǎn)化為程序語言代碼;簡單易懂;容易修改

算法通常具有（）的性質(zhì)。

A:有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限B:確定性：組成算法的每條指令清晰、無歧義C:輸出：至少有一個輸出D:輸入：有零個或多個輸入

答案:有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限;確定性：組成算法的每條指令清晰、無歧義;輸出：至少有一個輸出;輸入：有零個或多個輸入

程序是算法用某種程序設(shè)計語言的具體實現(xiàn)，程序需滿足算法的所有性質(zhì)。

A:對B:錯

答案:錯

常用的描述算法的形式有（）。

A:程序流程圖B:機器語言C:偽代碼D:自然語言

答案:程序流程圖;偽代碼;自然語言

函數(shù)f(n)=20log3^n的漸進表達式是（）。

A:0(log(n))B:0（n^2）C:0(1)D:O(n)

答案:O(n)

一個算法的優(yōu)劣由（）決定。

A:時間復雜度B:代碼長度C:空間復雜度D:使用的編程語言

答案:時間復雜度;空間復雜度

如果存在正的常數(shù)C和自然數(shù)N0,使得當N≥N0時有f(N)≤Cg(N),則稱函數(shù)f(N)當N充分大時上有界，且g(N)是它的一個上界，記為f(N)=O(g(N)),即f(N)的階不高于g(N）的階。

A:對B:錯

答案:對

分析以下代碼的時間復雜度：

intfunc(intn)

{

inti=1,k=0;

while(i<=n){

k++;

i=i*2;

}

returnk;

}

A:O(n)B:O(n^2)C:O(logn)D:O(n/2)

答案:O(logn)

對于f(n)=n，下列說法正確的是（）。

A:f(n)=O(n)B:f(n)=O(1/n)C:f(n)=O(n^2)D:f(n)=O(n^3)

答案:f(n)=O(n);f(n)=O(n^2);f(n)=O(n^3)

第二章測試

遞歸函數(shù)是指在一個函數(shù)體中出現(xiàn)直接或間接調(diào)用該函數(shù)自身的函數(shù)。

A:錯B:對

答案:對

已知f(1)=1，f(n)=f(n-1)+n，那么f(50)的作用是()。

A:計算50個1的和。B:計算1到50的乘積。C:計算斐波拉契數(shù)列的第50個元素的值。D:計算1到50的和。

答案:計算1到50的和。

遞歸的優(yōu)點包括()。

A:容易用數(shù)學歸納法來證明算法的正確性B:可讀性強C:結(jié)構(gòu)清晰D:運行效率高

答案:容易用數(shù)學歸納法來證明算法的正確性;可讀性強;結(jié)構(gòu)清晰

在經(jīng)典的漢諾塔問題中，如果有5個圓盤需要從A柱移至C柱，最少需要移動()步。

A:32B:28C:31D:41

答案:31

分治法能解決的問題一般具有（）等特征。

A:分解出的子問題的解可以合并為原問題的解B:最優(yōu)子結(jié)構(gòu)C:該問題縮小到一定程度時可以容易地解決D:子問題相互獨立

答案:分解出的子問題的解可以合并為原問題的解;最優(yōu)子結(jié)構(gòu);該問題縮小到一定程度時可以容易地解決;子問題相互獨立

在使用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同，即將一個問題分成大小相等的多個子問題的處理方法是行之有效的。

A:錯B:對

答案:對

給定遞歸公式T(n)=4T(n/2)+O(n),由主定理可以得知T(n)=()。

A:O(n)B:O(logn)C:O(nlogn)D:O(n^2)

答案:O(n^2)

已知某樓房共20層，如果采用二分查找，請問最多猜()次就能猜出任意一個樓層。

A:4B:6C:5D:3

答案:5

關(guān)于快速排序的時間復雜度，()是正確的。

A:在最好情況下時間復雜度為O(nlogn)B:在平均情況下時間復雜度為O(nlogn)C:在最壞情況下時間復雜度為O(n^2)D:在平均情況下時間復雜度為O(n^2)

答案:在最好情況下時間復雜度為O(nlogn);在平均情況下時間復雜度為O(nlogn);在最壞情況下時間復雜度為O(n^2)

快速排序是對傳統(tǒng)排序算法()的一種改進。

A:冒泡排序B:歸并排序C:插入排序D:選擇排序

答案:冒泡排序

第三章測試

能夠使用動態(tài)規(guī)劃算法來求解的問題通常需要具備兩個重要的性質(zhì)，它們分別是()。

A:貪心選擇性質(zhì)B:重疊子問題C:最優(yōu)子結(jié)構(gòu)D:遞歸調(diào)用

答案:重疊子問題;最優(yōu)子結(jié)構(gòu)

關(guān)于備忘錄法，以下說法正確的是()。

A:備忘錄法的控制結(jié)構(gòu)與直接使用遞歸方法的控制結(jié)構(gòu)相同。B:備忘錄法為每個解過的子問題建立備忘錄以備需要時查看，又稱查表法。C:備忘錄法又稱為記憶化搜索，它采用一種自底向上的方式求解問題。D:備忘錄法可以避免相同子問題的重復求解。

答案:備忘錄法的控制結(jié)構(gòu)與直接使用遞歸方法的控制結(jié)構(gòu)相同。;備忘錄法為每個解過的子問題建立備忘錄以備需要時查看，又稱查表法。;備忘錄法可以避免相同子問題的重復求解。

字符序列abcde與字符序列abdge的最長公共子序列長度為()，最長公共子串長度為()。

A:3,5B:4,1C:4,2D:4,6

答案:4,2

使用動態(tài)規(guī)劃算法求兩條長度分別為m和n的序列的最長公共子序列，其時間復雜度為()。

A:O(m^n)B:O(nlogm)C:O(n*m)D:O(n^2)

答案:O(n*m)

輸入數(shù)組（-1,0,1,-2,3），它的最大子段和是()。

A:1B:2C:3D:4

答案:3

序列（1，7，3，4，9，2，3）的最長遞增子序列的長度為()。

A:3B:1C:2D:4

答案:4

使用窮舉法求解最長遞增子序列的時間復雜度為()。

A:O(n^n)B:O(n^2)C:O(nlogn)D:O(n*2^n)

答案:O(n*2^n)

使用動態(tài)規(guī)劃算法求最大子段和的時間復雜度為()。

A:O(n)B:O(2^n)C:O(logn)D:O(nlogn)

答案:O(n)

某工廠預計明年有A,B,C,D四個新建項目，每個項目的投資額分別為15,10,12,8（萬元），投資收益分別為12,8,9,5（萬元），投資總額為30萬元，選擇項目()可以使總收益最大。（不允許部分投資某個項目）

A:CB:BC:DD:A

答案:C;B;D

在使用動態(tài)規(guī)劃算法求解0-1背包問題時，若m[i][j]=m[i+1][j-w[i]]+v[i]，說明第i個物品在剩余背包容量為j時可以裝入，并且裝入比不裝入的背包總價值更大，裝入后，背包剩余容量減少w[i]，價值增加v[i]。

A:錯B:對

答案:對

第四章測試

能夠使用貪心算法求解的問題需具備的基本要素包括()。

A:遞歸調(diào)用B:貪心選擇性質(zhì)C:最優(yōu)子結(jié)構(gòu)性質(zhì)D:重復子問題E:平衡子問題

答案:貪心選擇性質(zhì);最優(yōu)子結(jié)構(gòu)性質(zhì)

下列關(guān)于貪心算法與動態(tài)規(guī)劃算法說法正確的是()。

A:貪心算法與動態(tài)規(guī)劃算法求解的問題都具備最優(yōu)子結(jié)構(gòu)性質(zhì)B:貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是動態(tài)規(guī)劃算法要求問題具有貪心選擇性質(zhì)C:貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是貪心算法要求問題具有貪心選擇性質(zhì)D:貪心算法與動態(tài)規(guī)劃算法求解的問題都具有重復子問題性質(zhì)

答案:貪心算法與動態(tài)規(guī)劃算法求解的問題都具備最優(yōu)子結(jié)構(gòu)性質(zhì);貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是貪心算法要求問題具有貪心選擇性質(zhì)

在解決活動安排問題時應首先對活動進行排序，排序的依據(jù)是()。

A:按照活動結(jié)束時間降序排列B:按照活動結(jié)束時間升序排列C:按照活動開始時間降序排列D:按照活動開始時間升序排列

答案:按照活動結(jié)束時間升序排列

使用貪心算法求解最優(yōu)裝載問題，其時間復雜度為()。

A:O(nlogn)B:O(n2n)C:O(n3n)D:O(n5n)

答案:O(nlogn)

()能夠使用貪心算法求解。

A:最優(yōu)裝載問題B:單源最短路徑問題C:部分背包問題D:0-1背包問題E:最小生成樹問題F:活動安排問題

答案:最優(yōu)裝載問題;單源最短路徑問題;部分背包問題;最小生成樹問題;活動安排問題

0-1背包問題與部分背包問題的區(qū)別在于()。

A:若用貪心算法解決0-1背包問題，只能得到近似最優(yōu)解B:在0-1背包問題中，物品只有裝入和不裝入兩種情況，而部分背包問題允許只裝入物品的一部分C:沒有區(qū)別，它們的含義相同D:若用貪心算法解決部分背包問題，只能得到近似最優(yōu)解

答案:若用貪心算法解決0-1背包問題，只能得到近似最優(yōu)解;在0-1背包問題中，物品只有裝入和不裝入兩種情況，而部分背包問題允許只裝入物品的一部分

在求解部分背包問題時采用的貪心策略是()。

A:選擇價值最大的物品B:選擇重量最輕的物品C:選擇單位重量下價值最大的物品D:選擇單位價值下重量最大的物品

答案:選擇單位重量下價值最大的物品

Dijkstra算法可用于求解()。

A:單源最短路徑問題B:單終點最短路徑問題C:單對頂點最短路徑問題D:每對頂點間最短路徑問題

答案:單源最短路徑問題;單終點最短路徑問題;單對頂點最短路徑問題;每對頂點間最短路徑問題

Prim算法適合稀疏圖，其時間復雜度只與邊的數(shù)目有關(guān)。

A:對B:錯

答案:錯

在對Dijkstra算法進行初始化時，如果兩個頂點之間沒有邊，則它們之間的距離為()。

A:-1B:0C:無窮小D:無窮大

答案:無窮大

第五章測試

回溯法中的剪枝函數(shù)包括()。

A:約束函數(shù)B:限界函數(shù)C:虛函數(shù)D:隨機數(shù)生成函數(shù)E:靜態(tài)函數(shù)F:遞歸函數(shù)

答案:約束函數(shù);限界函數(shù)

回溯法采用的搜索策略是()。

A:廣度優(yōu)先搜索B:深度優(yōu)先搜索C:層次搜索D:啟發(fā)式搜索

答案:深度優(yōu)先搜索

回溯法的主要用途包括求問題的所有解、求問題的最優(yōu)解和求問題的任一解。

A:對B:錯

答案:對

馬的遍歷問題能否有可行解，與()有關(guān)。

A:棋盤大小B:馬的遍歷順序C:馬的初始位置D:馬的遍歷深度

答案:棋盤大小;馬的初始位置

在N皇后問題中，需要將棋盤當做一個二維數(shù)組來分析，對于該二維數(shù)組，以下說法正確的是()。

A:對于任意一條右斜線上的兩個點，它們的橫坐標和縱坐標相減的值相同。B:對于任意一條左斜線上的兩個點，它們的橫坐標和縱坐標相加的值相同。C:對于任意一條左斜線上的兩個點，它們的橫坐標和縱坐標相減的值相同。D:對于任意一條右斜線上的兩個點，它們的橫坐標和縱坐標相加的值相同。

答案:對于任意一條右斜線上的兩個點，它們的橫坐標和縱坐標相減的值相同。;對于任意一條左斜線上的兩個點，它們的橫坐標和縱坐標相加的值相同。

四皇后問題一共有2個可行解，八皇后問題一共有76個可行解。

A:錯B:對

答案:錯

用m種顏色給n個頂點著色、且使一條邊的兩個頂點顏色不同，則對應的解空間樹是一棵()。

A:高為m的n叉樹B:高為n的n叉樹C:高為n的m叉樹D:高為m的m叉樹

答案:高為n的m叉樹

任何一張地圖只用()種顏色就能使具有共同邊界的國家著上不同的顏色。

A:3B:4C:6D:2

答案:4

使用回溯法求解0-1背包問題時，計算右子樹上界的方法是通過貪心策略求得上界，即將剩余物品依其單位重量價值排序，然后依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包，此時得到的價值就是右子樹中解的上界。

A:對B:錯

答案:對

關(guān)于使用回溯法求解0-1背包問題，以下說法正確的是()。

A:使用約束函數(shù)剪去不合理的右子樹（不裝該物品）。B:使用約束函數(shù)剪去不合理的左子樹（裝該物品）。C:使用限界函數(shù)剪去得不到更優(yōu)解的左子樹（裝該物品）。D:使用限界函數(shù)剪去得不到更優(yōu)解的右子樹（不裝該物品）。

答案:使用約束函數(shù)剪去不合理的左子樹（裝該物品）。;使用限界函數(shù)剪去得不到更優(yōu)解的右子樹（不裝該物品）。

第六章測試

分支限界法采用的搜索策略是()。

A:遞歸搜索B:廣度優(yōu)先搜索C:深度優(yōu)先搜索D:啟發(fā)式搜索

答案:廣度優(yōu)先搜索

根據(jù)活結(jié)點表的組織方式不同，分支限界法包括()等形式。

A:隊列式分支限界法B:單調(diào)隊列式分支限界法C:優(yōu)先隊列式分支限界法D:二叉樹式分支限界法E:棧式分支限界法

答案:隊列式分支限界法;優(yōu)先隊列式分支限界法

關(guān)于回溯法和分支限界法，以下說法正確的是()。

A:回溯法通常用于求滿足約束條件的所有解B:分支限界法通常用于求滿足約束條件的一個解或特定意義下的最優(yōu)解C:在分支限界法中，每個結(jié)點只有一次成為擴展結(jié)點的機會D:在回溯法中，活結(jié)點的所有可行子結(jié)點均被遍歷后才從棧中彈出

答案:回溯法通常用于求滿足約束條件的所有解;分支限界法通常用于求滿足約束條件的一個解或特定意義下的最優(yōu)解;在分支限界法中，每個結(jié)點只有一次成為擴展結(jié)點的機會;在回溯法中，活結(jié)點的所有可行子結(jié)點均被遍歷后才從棧中彈出

應用分支限界法的三個關(guān)鍵問題包括()。

A:如何確定最優(yōu)解的解向量B:如何設(shè)計合適的剪枝函數(shù)C:如何組織活結(jié)點表D:如何限制搜索的層次

答案:如何確定最優(yōu)解的解向量;如何設(shè)計合適的剪枝函數(shù);如何組織活結(jié)點表

關(guān)于分支限界法的基本思想，下列描述正確的是()。

A:那些導致不可行解或?qū)е路亲顑?yōu)解的子結(jié)點被舍棄，其余子結(jié)點被加入活結(jié)點表中B:從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復結(jié)點擴展過程C:活結(jié)點一旦