2021知到答案【 算法分析與設(shè)計】智慧樹網(wǎng)課章節(jié)測試答案

1、第 頁2021知到答案【 算法分析與設(shè)計 】智慧樹網(wǎng)課章節(jié)測試答案 第一章 章節(jié)測試 1、選擇題:算法是指解決選擇題的方法或過程，它包含一系列步驟，用來將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)果。選項：A:對B:錯答案: 【對】2、選擇題:使用偽代碼描述算法具有（ ）等優(yōu)點(diǎn)。選項：A:易于轉(zhuǎn)化為程序語言代碼B:簡單修改C:簡潔易懂D:格式統(tǒng)一規(guī)范答案: 【易于轉(zhuǎn)化為程序語言代碼;簡單修改;簡潔易懂】3、選擇題:算法通常具有（ ）的性質(zhì)。選項：A:輸出：至少有一個輸出B:有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限C:確定性：組成算法的每條指令清楚、無歧義D:輸入：有零個或多個輸入答案: 【輸出

2、：至少有一個輸出;有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限;確定性：組成算法的每條指令清楚、無歧義;輸入：有零個或多個輸入】4、選擇題:程序是算法用某種程序設(shè)計語言的詳細(xì)實現(xiàn)，程序需滿意算法的全部性質(zhì)。選項：A:錯B:對答案: 【錯】5、選擇題:常用的描述算法的形式有（ ）。選項：A:自然語言B:程序流程圖C:偽代碼D:機(jī)器語言答案: 【自然語言;程序流程圖;偽代碼】6、選擇題:函數(shù)f(n)=20log3的漸進(jìn)表達(dá)式是（ ）。選項：A:O(n)B:0（n）C:0(log(n)D:0(1)答案: 【O(n)】7、選擇題:一個算法的優(yōu)劣由（ ）決定。選項：A:代碼長度B:使用

3、的編程語言C:時間簡單度D:空間簡單度答案: 【時間簡單度;空間簡單度】8、選擇題:假如存在正的常數(shù)C和自然數(shù)N0,使得當(dāng)NN0時有f(N)Cg(N),則稱函數(shù)f(N)當(dāng)N充分大時上有界，且g(N)是它的一個上界，記為f(N)=O(g(N),即f(N)的階不高于g(N）的階。選項：A:錯B:對答案: 【對】9、選擇題:分析以下代碼的時間簡單度：int func(int n)int i=1, k=0;while(i=n) k+;i=i*2;return k;選項：A:O(n)B:O(n)C:O(n/2)D:O(logn)答案: 【O(logn)】10、選擇題:對于f(n)=n，下列說法正確的是（

4、 ）。選項：A:f(n)=O(n)B:f(n)=O(1/n)C:f(n)=O(n)D:f(n)=O(n)答案: 【f(n)=O(n);f(n)=O(n);f(n)=O(n)】第二章 章節(jié)測試 1、選擇題:遞歸函數(shù)是指在一個函數(shù)體中消失直接或間接調(diào)用該函數(shù)自身的函數(shù)。選項：A:錯B:對答案: 【對】2、選擇題:已知f(1)=1，f(n)=f(n-1)+n，那么f(50)的作用是( )。選項：A:計算1到50的乘積。B:計算1到50的和。C:計算50個1的和。D:計算斐波拉契數(shù)列的第50個元素的值。答案: 【計算1到50的和?！?、選擇題:遞歸的優(yōu)點(diǎn)包括( )。選項：A:結(jié)構(gòu)清楚B:簡單用數(shù)學(xué)歸納

5、法來證明算法的正確性C:可讀性強(qiáng)D:運(yùn)行效率高答案: 【結(jié)構(gòu)清楚;簡單用數(shù)學(xué)歸納法來證明算法的正確性;可讀性強(qiáng)】4、選擇題:在經(jīng)典的漢諾塔選擇題中，假如有5個圓盤需要從A柱移至C柱，最少需要移動( )步。選項：A:31B:41C:32D:28答案: 【31】5、選擇題:分治法能解決的選擇題一般具有（ ）等特征。選項：A:該選擇題縮小到肯定程度時可以簡單地解決B:分解出的子選擇題的解可以合并為原選擇題的解C:子選擇題相互獨(dú)立D:最優(yōu)子結(jié)構(gòu)答案: 【該選擇題縮小到肯定程度時可以簡單地解決;分解出的子選擇題的解可以合并為原選擇題的解;子選擇題相互獨(dú)立;最優(yōu)子結(jié)構(gòu)】6、選擇題:在使用分治法設(shè)計算法時，

6、最好使子選擇題的規(guī)模大致相同，即將一個選擇題分成大小相等的多個子選擇題的處理方法是行之有效的。選項：A:對B:錯答案: 【對】7、選擇題:給定遞歸公式T(n)=4T(n/2)+O(n),由主定理可以得知T(n)=( )。選項：A:O(logn)B:O(nlogn)C:O(n)D:O(n)答案: 【O(n)】8、選擇題:已知某樓房共20層，假如采用二分查找，請問最多猜( )次就能猜出任意一個樓層。選項：A:5B:3C:6D:4答案: 【5】9、選擇題:關(guān)于快速排序的時間簡單度，( )是正確的。選項：A:在平均情況下時間簡單度為O(nlogn)B:在最壞情況下時間簡單度為O(n)C:在平均情況下時

7、間簡單度為O(n)D:在最好情況下時間簡單度為O(nlogn)答案: 【在平均情況下時間簡單度為O(nlogn);在最壞情況下時間簡單度為O(n);在最好情況下時間簡單度為O(nlogn)】10、選擇題:快速排序是對傳統(tǒng)排序算法( )的一種改進(jìn)。選項：A:歸并排序B:冒泡排序C:插入排序D:選擇排序答案: 【冒泡排序】第三章 章節(jié)測試 1、選擇題:能夠使用動態(tài)規(guī)劃算法來求解的選擇題通常需要具備兩個重要的性質(zhì)，它們分別是( )。選項：A:貪心選擇性質(zhì)B:最優(yōu)子結(jié)構(gòu)C:重疊子選擇題D:遞歸調(diào)用答案: 【最優(yōu)子結(jié)構(gòu);重疊子選擇題】$2、選擇題:關(guān)于備忘錄法，以下說法正確的是( )。選項：A:備忘錄法

8、又稱為記憶化搜索，它采用一種自底向上的方式求解選擇題。B:備忘錄法可以避開相同子選擇題的重復(fù)求解。C:備忘錄法的掌握結(jié)構(gòu)與直接使用遞歸方法的掌握結(jié)構(gòu)相同。D:備忘錄法為每個解過的子選擇題建立備忘錄以備需要時查看，又稱查表法。答案: 【備忘錄法可以避開相同子選擇題的重復(fù)求解。;備忘錄法的掌握結(jié)構(gòu)與直接使用遞歸方法的掌握結(jié)構(gòu)相同。;備忘錄法為每個解過的子選擇題建立備忘錄以備需要時查看，又稱查表法?！?、選擇題:字符序列abcde與字符序列abdge的最長公共子序列長度為( )，最長公共子串長度為( )。選項：A:4,6B:3,5C:4,2D:4,1答案: 【4,2】4、選擇題:使用動態(tài)規(guī)劃算法求兩

9、條長度分別為m和n的序列的最長公共子序列，其時間簡單度為( )。選項：A:O(n)B:O(m)C:O(nlogm)D:O(n*m)答案: 【O(n*m)】5、選擇題:輸入數(shù)組（-1, 0, 1, -2, 3），它的最大子段和是( )。選項：A:1B:4C:3D:2答案: 【3】6、選擇題:序列（1，7，3，4，9，2，3）的最長遞增子序列的長度為( )。選項：A:1B:3C:2D:4答案: 【4】7、選擇題:使用窮舉法求解最長遞增子序列的時間簡單度為( )。選項：A:O(n)B:O(n)C:O(n*2)D:O(nlogn)答案: 【O(n*2)】8、選擇題:使用動態(tài)規(guī)劃算法求最大子段和的時間簡

10、單度為( )。選項：A:O(n)B:O(nlogn)C:O(logn)D:O(2)答案: 【O(n)】9、選擇題:某工廠估計明年有A,B,C,D四個新建項目，每個項目的投資額分別為15,10,12,8（萬元），投資收益分別為12,8,9,5（萬元），投資總額為30萬元，選擇項目( )可以使總收益最大。（不允許部分投資某個項目）選項：A:AB:DC:CD:B答案: 【D;C;B】10、選擇題:在使用動態(tài)規(guī)劃算法求解0-1背包選擇題時，若mij=mi+1j-wi+vi，說明第i個物品在剩余背包涵量為j時可以裝入，并且裝入比不裝入的背包總價值更大，裝入后，背包剩余容量削減wi，價值增加vi。選項：A

11、:錯B:對答案: 【對】第四章 章節(jié)測試 1、選擇題:能夠使用貪心算法求解的選擇題需具備的基本要素包括( )。選項：A:貪心選擇性質(zhì)B:最優(yōu)子結(jié)構(gòu)性質(zhì)C:平衡子選擇題D:遞歸調(diào)用E:重復(fù)子選擇題答案: 【貪心選擇性質(zhì);最優(yōu)子結(jié)構(gòu)性質(zhì)】2、選擇題:下列關(guān)于貪心算法與動態(tài)規(guī)劃算法說法正確的是( )。選項：A:貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是貪心算法要求選擇題具有貪心選擇性質(zhì)B:貪心算法與動態(tài)規(guī)劃算法求解的選擇題都具有重復(fù)子選擇題性質(zhì)C:貪心算法與動態(tài)規(guī)劃算法求解的選擇題都具備最優(yōu)子結(jié)構(gòu)性質(zhì)D:貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是動態(tài)規(guī)劃算法要求選擇題具有貪心選擇性質(zhì)答案: 【貪心算法與動態(tài)規(guī)劃算法

12、的主要區(qū)別是貪心算法要求選擇題具有貪心選擇性質(zhì);貪心算法與動態(tài)規(guī)劃算法求解的選擇題都具備最優(yōu)子結(jié)構(gòu)性質(zhì)】3、選擇題:在解決活動安排選擇題時應(yīng)首先對活動進(jìn)行排序，排序的依據(jù)是( )。選項：A:根據(jù)活動結(jié)束時間降序排列B:根據(jù)活動開始時間降序排列C:根據(jù)活動結(jié)束時間升序排列D:根據(jù)活動開始時間升序排列答案: 【根據(jù)活動結(jié)束時間升序排列】4、選擇題:使用貪心算法求解最優(yōu)裝載選擇題，其時間簡單度為( )。選項：A:O(nlogn)B:O(n3n)C:O(n5n)D:O(n2n)答案: 【O(nlogn)】5、選擇題:( )能夠使用貪心算法求解。選項：A:最小生成樹選擇題B:單源最短路徑選擇題C:活動安

13、排選擇題D:0-1背包選擇題E:部分背包選擇題F:最優(yōu)裝載選擇題答案: 【最小生成樹選擇題;單源最短路徑選擇題;活動安排選擇題;部分背包選擇題;最優(yōu)裝載選擇題】6、選擇題:0-1背包選擇題與部分背包選擇題的區(qū)別在于( )。選項：A:在0-1背包選擇題中，物品只有裝入和不裝入兩種情況，而部分背包選擇題允許只裝入物品的一部分B:若用貪心算法解決0-1背包選擇題，只能得到近似最優(yōu)解C:沒有區(qū)別，它們的含義相同D:若用貪心算法解決部分背包選擇題，只能得到近似最優(yōu)解答案: 【在0-1背包選擇題中，物品只有裝入和不裝入兩種情況，而部分背包選擇題允許只裝入物品的一部分;若用貪心算法解決0-1背包選擇題，只能

14、得到近似最優(yōu)解】7、選擇題:在求解部分背包選擇題時采用的貪心策略是( )。選項：A:選擇重量最輕的物品B:選擇單位價值下重量最大的物品C:選擇價值最大的物品D:選擇單位重量下價值最大的物品答案: 【選擇單位重量下價值最大的物品】8、選擇題:Dijkstra算法可用于求解( )。選項：A:單終點(diǎn)最短路徑選擇題B:每對頂點(diǎn)間最短路徑選擇題C:單源最短路徑選擇題D:單對頂點(diǎn)最短路徑選擇題答案: 【單終點(diǎn)最短路徑選擇題;每對頂點(diǎn)間最短路徑選擇題;單源最短路徑選擇題;單對頂點(diǎn)最短路徑選擇題】9、選擇題:Prim算法適合稀疏圖，其時間簡單度只與邊的數(shù)目有關(guān)。選項：A:對B:錯答案: 【錯】10、選擇題:在

15、對Dijkstra算法進(jìn)行初始化時，假如兩個頂點(diǎn)之間沒有邊，則它們之間的距離為( )。選項：A:-1B:0C:無窮大D:無窮小答案: 【無窮大】第五章 章節(jié)測試 1、選擇題:回溯法中的剪枝函數(shù)包括( )。選項：A:遞歸函數(shù)B:靜態(tài)函數(shù)C:虛函數(shù)D:隨機(jī)數(shù)生成函數(shù)E:限界函數(shù)F:約束函數(shù)答案: 【限界函數(shù);約束函數(shù)】2、選擇題:回溯法采用的搜索策略是( )。選項：A:深度優(yōu)先搜索B:啟發(fā)式搜索C:層次搜索D:廣度優(yōu)先搜索答案: 【深度優(yōu)先搜索】3、選擇題:回溯法的主要用途包括求選擇題的全部解、求選擇題的最優(yōu)解和求選擇題的任一解。選項：A:對B:錯答案: 【對】4、選擇題:馬的遍歷選擇題能否有可行

16、解，與( )有關(guān)。選項：A:馬的初始位置B:馬的遍歷挨次C:馬的遍歷深度D:棋盤大小答案: 【馬的初始位置;棋盤大小】5、選擇題:在N皇后選擇題中，需要將棋盤當(dāng)做一個二維數(shù)組來分析，對于該二維數(shù)組，以下說法正確的是( )。選項：A:對于任意一條左斜線上的兩個點(diǎn)，它們的橫坐標(biāo)和縱坐標(biāo)相減的值相同。B:對于任意一條左斜線上的兩個點(diǎn)，它們的橫坐標(biāo)和縱坐標(biāo)相加的值相同。C:對于任意一條右斜線上的兩個點(diǎn)，它們的橫坐標(biāo)和縱坐標(biāo)相加的值相同。D:對于任意一條右斜線上的兩個點(diǎn)，它們的橫坐標(biāo)和縱坐標(biāo)相減的值相同。答案: 【對于任意一條左斜線上的兩個點(diǎn)，它們的橫坐標(biāo)和縱坐標(biāo)相加的值相同。;對于任意一條右斜線上的兩

17、個點(diǎn)，它們的橫坐標(biāo)和縱坐標(biāo)相減的值相同?！?、選擇題:四皇后選擇題一共有2個可行解，八皇后選擇題一共有76個可行解。選項：A:對B:錯答案: 【錯】7、選擇題:用m種顏色給n個頂點(diǎn)著色、且使一條邊的兩個頂點(diǎn)顏色不同，則對應(yīng)的解空間樹是一棵( )。選項：A:高為n的m叉樹B:高為m的m叉樹C:高為n的n叉樹D:高為m的n叉樹答案: 【高為n的m叉樹】8、選擇題:任何一張地圖只用( )種顏色就能使具有共同邊界的國家著上不同的顏色。選項：A:6B:2C:3D:4答案: 【4】9、選擇題:使用回溯法求解0-1背包選擇題時，計算右子樹上界的方法是通過貪心策略求得上界，即將剩余物品依其單位重量價值排序，然

18、后依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包，此時得到的價值就是右子樹中解的上界。選項：A:錯B:對答案: 【對】10、選擇題:關(guān)于使用回溯法求解0-1背包選擇題，以下說法正確的是( )。選項：A:使用限界函數(shù)剪去得不到更優(yōu)解的左子樹（裝該物品）。B:使用約束函數(shù)剪去不合理的右子樹（不裝該物品）。C:使用限界函數(shù)剪去得不到更優(yōu)解的右子樹（不裝該物品）。D:使用約束函數(shù)剪去不合理的左子樹（裝該物品）。答案: 【使用限界函數(shù)剪去得不到更優(yōu)解的右子樹（不裝該物品）。;使用約束函數(shù)剪去不合理的左子樹（裝該物品）?！康诹?章節(jié)測試 1、選擇題:分支限界法采用的搜索策略是( )。選項：A

19、:廣度優(yōu)先搜索B:遞歸搜索C:深度優(yōu)先搜索D:啟發(fā)式搜索答案: 【廣度優(yōu)先搜索】2、選擇題:依據(jù)活結(jié)點(diǎn)表的組織方式不同，分支限界法包括( )等形式。選項：A:棧式分支限界法B:隊列式分支限界法C:單調(diào)隊列式分支限界法D:二叉樹式分支限界法E:優(yōu)先隊列式分支限界法答案: 【隊列式分支限界法;優(yōu)先隊列式分支限界法】3、選擇題:關(guān)于回溯法和分支限界法，以下說法正確的是( )。選項：A:在回溯法中，活結(jié)點(diǎn)的全部可行子結(jié)點(diǎn)均被遍歷后才從棧中彈出B:分支限界法通常用于求滿意約束條件的一個解或特定意義下的最優(yōu)解C:在分支限界法中，每個結(jié)點(diǎn)只有一次成為擴(kuò)展結(jié)點(diǎn)的機(jī)會D:回溯法通常用于求滿意約束條件的全部解答案

20、: 【在回溯法中，活結(jié)點(diǎn)的全部可行子結(jié)點(diǎn)均被遍歷后才從棧中彈出;分支限界法通常用于求滿意約束條件的一個解或特定意義下的最優(yōu)解;在分支限界法中，每個結(jié)點(diǎn)只有一次成為擴(kuò)展結(jié)點(diǎn)的機(jī)會;回溯法通常用于求滿意約束條件的全部解】4、選擇題:應(yīng)用分支限界法的三個關(guān)鍵選擇題包括( )。選項：A:如何設(shè)計合適的剪枝函數(shù)B:如何組織活結(jié)點(diǎn)表C:如何限制搜索的層次D:如何確定最優(yōu)解的解向量答案: 【如何設(shè)計合適的剪枝函數(shù);如何組織活結(jié)點(diǎn)表;如何確定最優(yōu)解的解向量】5、選擇題:關(guān)于分支限界法的基本思想，下列描述正確的是( )。選項：A:從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)結(jié)點(diǎn)擴(kuò)展過程B:那些導(dǎo)致不可行解或?qū)?/p>

21、致非最優(yōu)解的子結(jié)點(diǎn)被舍棄，其余子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中C:每一個活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn)D:始終持續(xù)到找到所求的解或活結(jié)點(diǎn)表為空時為止E:活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其全部子結(jié)點(diǎn)答案: 【從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)結(jié)點(diǎn)擴(kuò)展過程;那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的子結(jié)點(diǎn)被舍棄，其余子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中;每一個活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn);始終持續(xù)到找到所求的解或活結(jié)點(diǎn)表為空時為止;活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其全部子結(jié)點(diǎn)】6、選擇題:優(yōu)先隊列式分支限界法將活結(jié)點(diǎn)表組織成一個優(yōu)先隊列，按優(yōu)先隊列中規(guī)定的結(jié)點(diǎn)優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。

22、選項：A:對B:錯答案: 【對】7、選擇題:隊列具有( )的性質(zhì)。選項：A:先進(jìn)后出B:進(jìn)出無序C:先進(jìn)先出D:僅進(jìn)不出答案: 【先進(jìn)先出】8、選擇題:使用隊列式分支限界法求解裝載選擇題時，每次從隊列Q中取出隊首元素作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。取隊首元素后，推斷當(dāng)前Q是否為空。如Q非空，則將尾部標(biāo)記-1加入Q，算法開始處理下一層的活結(jié)點(diǎn)。選項：A:錯B:對答案: 【錯】9、選擇題:假如一個給定裝載選擇題有解，則采用的裝載策略為：首先將第一艘輪船盡可能裝滿；再將剩余的集裝箱裝上第二艘輪船。選項：A:對B:錯答案: 【對】10、選擇題:在裝載選擇題中，假如右子樹表示不將此集裝箱裝上船。設(shè)bestw是當(dāng)前最優(yōu)

23、解；ew是當(dāng)前擴(kuò)展結(jié)點(diǎn)所相應(yīng)的重量；r是剩余集裝箱的重量，則當(dāng)( )時，可將其右子樹剪去。選項：A:ew+rbestwB:rbestw span=/bestwC:r=bestwD:ew+r=bestw答案: 【ew+r=bestw】第七章 章節(jié)測試 1、選擇題:動態(tài)規(guī)劃算法把原選擇題分為交叉的子選擇題，解決子選擇題，記錄子選擇題的解，合并為原選擇題的解。選項：A:對B:錯答案: 【對】2、選擇題:0/1背包選擇題的動態(tài)規(guī)劃算法是多項式時間算法。選項：A:對B:錯答案: 【錯】3、選擇題:對于稀疏圖，F(xiàn)loyd算法的效率要高于執(zhí)行n次Dijkstra算法，也要高于執(zhí)行n次SPFA算法。選項：A:

24、對B:錯答案: 【錯】4、選擇題:Dijkstra算法在求解過程中，源點(diǎn)到集合S內(nèi)各頂點(diǎn)的最短路徑一旦求出，則之后不變了，修改的僅僅是源點(diǎn)到還沒選擇的頂點(diǎn)的最短路徑長度。選項：A:對B:錯答案: 【對】5、選擇題:含負(fù)權(quán)的最短路選擇題一般使用（）求解。選項：A:動態(tài)規(guī)劃B:貪心算法C:分治算法D:網(wǎng)絡(luò)流算法答案: 【動態(tài)規(guī)劃】6、選擇題:動態(tài)規(guī)劃算法的基本要素有（）和最優(yōu)子結(jié)構(gòu)性質(zhì)。選項：A:分解合并性質(zhì)B:獨(dú)立子選擇題性質(zhì)C:貪心選擇性質(zhì)D:重疊子選擇題性質(zhì)答案: 【重疊子選擇題性質(zhì)】7、選擇題: 下面不是動態(tài)規(guī)劃的基本方法有（）。選項：A:多重選擇 B:增加變量C:舍入D:區(qū)間變量答案:

25、【舍入】8、選擇題:最短路算法中適用于稀疏圖的是（）選項：A:Floyd算法B:SPFA算法C:Bellman算法D:Dijkstra算法答案: 【SPFA算法;Bellman算法;Dijkstra算法】9、選擇題:動態(tài)規(guī)劃算法的特點(diǎn)（）選項：A:自底向上計算B:自頂向下計算C:從大到小計算D:從小到大計算答案: 【自底向上計算;從小到大計算】10、選擇題:備忘錄算法的特點(diǎn)（）選項：A:自底向上計算B:自頂向下計算C:從大到小計算 D:從小到大計算答案: 【自頂向下計算;從大到小計算 】第八章 章節(jié)測試 1、選擇題:回溯法是按廣度優(yōu)先策略搜索解空間樹。選項：A:對B:錯答案: 【錯】2、選擇題

26、:死結(jié)點(diǎn)是正在產(chǎn)生兒子的結(jié)點(diǎn)。選項：A:對B:錯答案: 【錯】3、選擇題:回溯法的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生選擇題的解空間。選項：A:對B:錯答案: 【對】第九章 章節(jié)測試 1、選擇題:分支限界法在對選擇題的解空間樹進(jìn)行搜索的方法中，一個活結(jié)點(diǎn)有多次機(jī)會成為活結(jié)點(diǎn)。選項：A:對B:錯答案: 【錯】2、選擇題:分支限界法找出滿意約束條件的一個解，或是在滿意約束條件的解中找出在某種意義下的最優(yōu)解。選項：A:對B:錯答案: 【對】3、選擇題:隊列式分支限界法以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。選項：A:對B:錯答案: 【錯】4、選擇題: 優(yōu)先隊列式分支限界法根據(jù)隊列先進(jìn)先出的原則，選取下一個節(jié)

27、點(diǎn)為擴(kuò)展結(jié)點(diǎn)。選項：A:對B:錯答案: 【錯】 5、選擇題:下列算法中不能解決0/1背包選擇題的是選項：A:貪心法B:動態(tài)規(guī)劃C:回溯法D:分支限界法答案: 【貪心法】6、選擇題:分支限界法解旅行商選擇題時的解空間樹是選項：A:子集樹B:排列樹C:深度優(yōu)先生成樹D:廣度優(yōu)先生成樹答案: 【排列樹】7、選擇題:優(yōu)先隊列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是選項：A:先進(jìn)先出B:后進(jìn)先出C:結(jié)點(diǎn)的優(yōu)先級D:隨機(jī)答案: 【結(jié)點(diǎn)的優(yōu)先級】8、選擇題:用分支限界法設(shè)計算法的步驟是：選項：A:針對所給選擇題，定義選擇題的解空間（對解進(jìn)行編碼）B:確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）C:定義最優(yōu)子結(jié)構(gòu)D:以

28、廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避開無效搜索答案: 【針對所給選擇題，定義選擇題的解空間（對解進(jìn)行編碼）;確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）;以廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避開無效搜索】9、選擇題:分支限界法與回溯法的不同點(diǎn)是什么？選項：A:求解目標(biāo)不同B:搜索方式不同C:對擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同D:存儲空間的要求不同答案: 【求解目標(biāo)不同;搜索方式不同;對擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同;存儲空間的要求不同】10、選擇題: FIFO是（ ）的搜索方式。選項：A:回溯算法B:分支限界C:動態(tài)規(guī)劃D:貪

29、心算法答案: 【分支限界】第十章 章節(jié)測試 1、選擇題:網(wǎng)絡(luò)流滿意容量約束，但一般不滿意流量守恒約束。選項：A:對B:錯答案: 【錯】2、選擇題:設(shè)G = V1, V2, E為二分圖, |V1|V2|, M為G中一個最大匹配, 且|M| = |V1|, 則稱M為G的完備匹配，也是最大匹配。選項：A:對B:錯答案: 【對】3、選擇題:存在割 (A, B)使流值 v(f) = 割的容量cap(A, B).，則割 (A, B)是最小割。選項：A:對B:錯答案: 【對】4、選擇題: 給定連通圖G, BFS遍歷得到層次圖，假如同一層中的結(jié)點(diǎn)無邊相連，則G是二分圖。選項：A:對B:錯答案: 【對】 5、選

30、擇題:有下界的流通選擇題不肯定有可行流。選項：A:對B:錯答案: 【對】6、選擇題:Dinic算法的時間簡單度為（）選項：A:mn2B:mnC:m2nD:m2logC答案: 【mn2】7、選擇題:假如每條邊的最大容量為1，則時間簡單度是O（nm）的網(wǎng)絡(luò)流算法有選項：A:FF算法B:容量縮放算法C:EK算法D:Dinic算法答案: 【FF算法】8、選擇題:給定二分圖G = V, E中無孤立點(diǎn)，|V|=n，其最大流算法求得最大流f, 則G的（）=n-f選項：A:最大獨(dú)立數(shù)B:最大匹配數(shù)C:最小頂點(diǎn)掩蓋D:最小邊掩蓋答案: 【最大獨(dú)立數(shù);最小邊掩蓋】9、選擇題:改進(jìn)FF網(wǎng)絡(luò)流算法，可以通過選擇（）增

31、廣路，降低時間簡單度。選項：A:最大容量B:最短路徑C:最大瓶頸容量D:邊數(shù)最少答案: 【最大容量;最短路徑;最大瓶頸容量;邊數(shù)最少】10、選擇題:帶需求的流通必需滿意供應(yīng)和 = 需求和選項：A:對B:錯答案: 【對】第十一章 章節(jié)測試 1、選擇題:蒙特卡羅算法的結(jié)果確定是一個正確解。選項：A:對B:錯答案: 【錯】2、選擇題:Sherwood算法隨機(jī)選擇一個數(shù)組元素作為劃分標(biāo)準(zhǔn)求解k小元素選擇題,保證線性時間的平均性能。選項：A:對B:錯答案: 【對】3、選擇題:借助隨機(jī)預(yù)處理技術(shù)，不轉(zhuǎn)變原有的確定性算法，僅對其輸入進(jìn)行隨機(jī)洗牌，可收到舍伍德算法的效果。選項：A:對B:錯答案: 【對】4、選

32、擇題: 隨機(jī)算法共同點(diǎn)是計算時間越多或運(yùn)行次數(shù)越多,正確性越高.選項：A:對B:錯答案: 【對】 5、選擇題:增加拉斯維加斯算法的反復(fù)求解次數(shù), 可使求解無效的概率任意小。選項：A:對B:錯答案: 【對】6、選擇題:在下列算法中有時找不到選擇題解的是選項：A:蒙特卡羅算法B:拉斯維加斯算法C:舍伍德算法D:數(shù)值隨機(jī)算法答案: 【拉斯維加斯算法】7、選擇題:確定獲得可行解，但不肯定是正確解的算法是選項：A:蒙特卡羅算法B:拉斯維加斯算法C:舍伍德算法D:數(shù)值隨機(jī)算法答案: 【蒙特卡羅算法】8、選擇題:在一般輸入數(shù)據(jù)的程序里，輸入多少會影響到算法的計算簡單度，為了消退這種影響可用（）對輸入進(jìn)行預(yù)處

33、理。選項：A:蒙特卡羅算法B:拉斯維加斯算法C:舍伍德算法D:數(shù)值隨機(jī)化算法答案: 【舍伍德算法】9、選擇題:（）確定獲得最優(yōu)解。選項：A:分支限界B:貪心算法C:隨機(jī)算法D:動態(tài)規(guī)劃算法答案: 【分支限界;動態(tài)規(guī)劃算法】10、選擇題:下面說法正確的是選項：A:現(xiàn)實計算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù)B:求解同一實例用同一隨機(jī)化算法求解兩次，所用時間和所得結(jié)果可能完全不同。C:蒙特卡羅算法總是能供應(yīng)選擇題的一個解,但可能給出錯誤會。D:舍伍德算法的精髓不是避開最壞的情況，而是設(shè)法消退最壞情況和特定實例的關(guān)聯(lián)性。答案: 【現(xiàn)實計算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù);求解同一實例用同一隨機(jī)化算法求解兩次，所用時間和

34、所得結(jié)果可能完全不同。;蒙特卡羅算法總是能供應(yīng)選擇題的一個解,但可能給出錯誤會。;舍伍德算法的精髓不是避開最壞的情況，而是設(shè)法消退最壞情況和特定實例的關(guān)聯(lián)性?！康谑?章節(jié)測試 1、選擇題:有多項式時間算法的選擇題是易解選擇題選項：A:對B:錯答案: 【對】2、選擇題:EXP類是全部指數(shù)時間可解的判定選擇題組成的選擇題類選項：A:對B:錯答案: 【對】3、選擇題:假如對于X的任意實例，通過多項式次的計算步驟，加多項式次調(diào)用Y的算法，可解決X，則X可多項式時間歸約到Y(jié)。選項：A:對B:錯答案: 【對】4、選擇題:假如X選擇題 Y 且Y不能多項式時間解決, 那么X也不能多項式時間解決。選項：A:對B:錯答案: 【錯】5、選擇題:下面關(guān)于NP選擇題說法正確的是（）選項：A:NP選擇題都是不可能解決的選擇題B:P類選擇題包含在NP類選擇題中C:NP完全選擇題是P類選擇題的子集D:NP類選擇題包含在P類選擇題中答案: 【P類選擇題包含在NP類選擇題中】6、選擇題:P類選擇題可以（）。選項：A:多項式時間計算B:指數(shù)時間計算C:指數(shù)時間驗證答案