算法分析與設(shè)計(jì) 知到智慧樹網(wǎng)課答案

算法分析與設(shè)計(jì)-知到答案、智慧樹答案第一章單元測試1、問題：算法是指解決問題的方法或過程，它包含一系列步驟，用來將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)果。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】2、問題：使用偽代碼描述算法具有（）等優(yōu)點(diǎn)。選項(xiàng)：A:易于轉(zhuǎn)化為程序語言代碼B:簡單易懂C:格式統(tǒng)一規(guī)范D:容易修改答案:【易于轉(zhuǎn)化為程序語言代碼;簡單易懂;容易修改】3、問題：算法通常具有（）的性質(zhì)。選項(xiàng)：A:輸入：有零個(gè)或多個(gè)輸入B:確定性：組成算法的每條指令清晰、無歧義C:有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限D(zhuǎn):輸出：至少有一個(gè)輸出答案:【輸入：有零個(gè)或多個(gè)輸入;確定性：組成算法的每條指令清晰、無歧義;有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限;輸出：至少有一個(gè)輸出】4、問題：程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)，程序需滿足算法的所有性質(zhì)。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】5、問題：常用的描述算法的形式有（）。選項(xiàng)：A:自然語言B:程序流程圖C:機(jī)器語言D:偽代碼答案:【自然語言;程序流程圖;偽代碼】6、問題：函數(shù)f(n)=20log3^n的漸進(jìn)表達(dá)式是（）。選項(xiàng)：A:0（n^2）B:0(log(n))C:O(n)D:0(1)答案:【O(n)】7、問題：一個(gè)算法的優(yōu)劣由（）決定。選項(xiàng)：A:代碼長度B:空間復(fù)雜度C:時(shí)間復(fù)雜度D:使用的編程語言答案:【空間復(fù)雜度;時(shí)間復(fù)雜度】8、問題：如果存在正的常數(shù)C和自然數(shù)N0,使得當(dāng)N≥N0時(shí)有f(N)≤Cg(N),則稱函數(shù)f(N)當(dāng)N充分大時(shí)上有界，且g(N)是它的一個(gè)上界，記為f(N)=O(g(N)),即f(N)的階不高于g(N）的階。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】9、問題：分析以下代碼的時(shí)間復(fù)雜度：intfunc(intn){inti=1,k=0;while(i<=n){k++;i=i*2;}returnk;}選項(xiàng)：A:O(n/2)B:O(n)C:O(logn)D:O(n^2)答案:【O(logn)】10、問題：對(duì)于f(n)=n，下列說法正確的是（）。選項(xiàng)：A:f(n)=O(n)B:f(n)=O(n^2)C:f(n)=O(1/n)D:f(n)=O(n^3)答案:【f(n)=O(n);f(n)=O(n^2);f(n)=O(n^3)】第二章單元測試1、問題：遞歸函數(shù)是指在一個(gè)函數(shù)體中出現(xiàn)直接或間接調(diào)用該函數(shù)自身的函數(shù)。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】2、問題：已知f(1)=1，f(n)=f(n-1)+n，那么f(50)的作用是()。選項(xiàng)：A:計(jì)算1到50的乘積。B:計(jì)算50個(gè)1的和。C:計(jì)算1到50的和。D:計(jì)算斐波拉契數(shù)列的第50個(gè)元素的值。答案:【計(jì)算1到50的和。】3、問題：遞歸的優(yōu)點(diǎn)包括()。選項(xiàng)：A:容易用數(shù)學(xué)歸納法來證明算法的正確性B:可讀性強(qiáng)C:結(jié)構(gòu)清晰D:運(yùn)行效率高答案:【容易用數(shù)學(xué)歸納法來證明算法的正確性;可讀性強(qiáng);結(jié)構(gòu)清晰】4、問題：在經(jīng)典的漢諾塔問題中，如果有5個(gè)圓盤需要從A柱移至C柱，最少需要移動(dòng)()步。選項(xiàng)：A:28B:31C:32D:41答案:【31】5、問題：分治法能解決的問題一般具有（）等特征。選項(xiàng)：A:分解出的子問題的解可以合并為原問題的解B:最優(yōu)子結(jié)構(gòu)C:子問題相互獨(dú)立D:該問題縮小到一定程度時(shí)可以容易地解決答案:【分解出的子問題的解可以合并為原問題的解;最優(yōu)子結(jié)構(gòu);子問題相互獨(dú)立;該問題縮小到一定程度時(shí)可以容易地解決】6、問題：在使用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相同，即將一個(gè)問題分成大小相等的多個(gè)子問題的處理方法是行之有效的。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】7、問題：給定遞歸公式T(n)=4T(n/2)+O(n),由主定理可以得知T(n)=()。選項(xiàng)：A:O(n)B:O(logn)C:O(n^2)D:O(nlogn)答案:【O(n^2)】8、問題：已知某樓房共20層，如果采用二分查找，請(qǐng)問最多猜()次就能猜出任意一個(gè)樓層。選項(xiàng)：A:3B:4C:5D:6答案:【5】9、問題：關(guān)于快速排序的時(shí)間復(fù)雜度，()是正確的。選項(xiàng)：A:在最壞情況下時(shí)間復(fù)雜度為O(n^2)B:在平均情況下時(shí)間復(fù)雜度為O(nlogn)C:在最好情況下時(shí)間復(fù)雜度為O(nlogn)D:在平均情況下時(shí)間復(fù)雜度為O(n^2)答案:【在最壞情況下時(shí)間復(fù)雜度為O(n^2);在平均情況下時(shí)間復(fù)雜度為O(nlogn);在最好情況下時(shí)間復(fù)雜度為O(nlogn)】10、問題：快速排序是對(duì)傳統(tǒng)排序算法()的一種改進(jìn)。選項(xiàng)：A:選擇排序B:冒泡排序C:歸并排序D:插入排序答案:【冒泡排序】第三章單元測試1、問題：能夠使用動(dòng)態(tài)規(guī)劃算法來求解的問題通常需要具備兩個(gè)重要的性質(zhì)，它們分別是()。選項(xiàng)：A:遞歸調(diào)用B:最優(yōu)子結(jié)構(gòu)C:貪心選擇性質(zhì)D:重疊子問題答案:【最優(yōu)子結(jié)構(gòu);重疊子問題】2、問題：關(guān)于備忘錄法，以下說法正確的是()。選項(xiàng)：A:備忘錄法可以避免相同子問題的重復(fù)求解。B:備忘錄法的控制結(jié)構(gòu)與直接使用遞歸方法的控制結(jié)構(gòu)相同。C:備忘錄法又稱為記憶化搜索，它采用一種自底向上的方式求解問題。D:備忘錄法為每個(gè)解過的子問題建立備忘錄以備需要時(shí)查看，又稱查表法。答案:【備忘錄法可以避免相同子問題的重復(fù)求解。;備忘錄法的控制結(jié)構(gòu)與直接使用遞歸方法的控制結(jié)構(gòu)相同。;備忘錄法為每個(gè)解過的子問題建立備忘錄以備需要時(shí)查看，又稱查表法?！?、問題：字符序列abcde與字符序列abdge的最長公共子序列長度為()，最長公共子串長度為()。選項(xiàng)：A:4,2B:4,1C:3,5D:4,6答案:【4,2】4、問題：使用動(dòng)態(tài)規(guī)劃算法求兩條長度分別為m和n的序列的最長公共子序列，其時(shí)間復(fù)雜度為()。選項(xiàng)：A:O(n^2)B:O(n*m)C:O(nlogm)D:O(m^n)答案:【O(n*m)】5、問題：輸入數(shù)組（-1,0,1,-2,3），它的最大子段和是()。選項(xiàng)：A:2B:3C:4D:1答案:【3】6、問題：序列（1，7，3，4，9，2，3）的最長遞增子序列的長度為()。選項(xiàng)：A:3B:4C:1D:2答案:【4】7、問題：使用窮舉法求解最長遞增子序列的時(shí)間復(fù)雜度為()。選項(xiàng)：A:O(n^2)B:O(n^n)C:O(nlogn)D:O(n*2^n)答案:【O(n*2^n)】8、問題：使用動(dòng)態(tài)規(guī)劃算法求最大子段和的時(shí)間復(fù)雜度為()。選項(xiàng)：A:O(nlogn)B:O(n)C:O(logn)D:O(2^n)答案:【O(n)】9、問題：某工廠預(yù)計(jì)明年有A,B,C,D四個(gè)新建項(xiàng)目，每個(gè)項(xiàng)目的投資額分別為15,10,12,8（萬元），投資收益分別為12,8,9,5（萬元），投資總額為30萬元，選擇項(xiàng)目()可以使總收益最大。（不允許部分投資某個(gè)項(xiàng)目）選項(xiàng)：A:AB:CC:BD:D答案:【C;B;D】10、問題：在使用動(dòng)態(tài)規(guī)劃算法求解0-1背包問題時(shí)，若m[i][j]=m[i+1][j-w[i]]+v[i]，說明第i個(gè)物品在剩余背包容量為j時(shí)可以裝入，并且裝入比不裝入的背包總價(jià)值更大，裝入后，背包剩余容量減少w[i]，價(jià)值增加v[i]。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【對(duì)】第四章單元測試1、問題：能夠使用貪心算法求解的問題需具備的基本要素包括()。選項(xiàng)：A:遞歸調(diào)用B:平衡子問題C:最優(yōu)子結(jié)構(gòu)性質(zhì)D:貪心選擇性質(zhì)E:重復(fù)子問題答案:【最優(yōu)子結(jié)構(gòu)性質(zhì);貪心選擇性質(zhì)】2、問題：下列關(guān)于貪心算法與動(dòng)態(tài)規(guī)劃算法說法正確的是()。選項(xiàng)：A:貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是動(dòng)態(tài)規(guī)劃算法要求問題具有貪心選擇性質(zhì)B:貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是貪心算法要求問題具有貪心選擇性質(zhì)C:貪心算法與動(dòng)態(tài)規(guī)劃算法求解的問題都具備最優(yōu)子結(jié)構(gòu)性質(zhì)D:貪心算法與動(dòng)態(tài)規(guī)劃算法求解的問題都具有重復(fù)子問題性質(zhì)答案:【貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是貪心算法要求問題具有貪心選擇性質(zhì);貪心算法與動(dòng)態(tài)規(guī)劃算法求解的問題都具備最優(yōu)子結(jié)構(gòu)性質(zhì)】3、問題：在解決活動(dòng)安排問題時(shí)應(yīng)首先對(duì)活動(dòng)進(jìn)行排序，排序的依據(jù)是()。選項(xiàng)：A:按照活動(dòng)結(jié)束時(shí)間降序排列B:按照活動(dòng)開始時(shí)間升序排列C:按照活動(dòng)結(jié)束時(shí)間升序排列D:按照活動(dòng)開始時(shí)間降序排列答案:【按照活動(dòng)結(jié)束時(shí)間升序排列】4、問題：使用貪心算法求解最優(yōu)裝載問題，其時(shí)間復(fù)雜度為()。選項(xiàng)：A:O(n3n)B:O(n5n)C:O(nlogn)D:O(n2n)答案:【O(nlogn)】5、問題：()能夠使用貪心算法求解。選項(xiàng)：A:最優(yōu)裝載問題B:0-1背包問題C:最小生成樹問題D:單源最短路徑問題E:活動(dòng)安排問題F:部分背包問題答案:【最優(yōu)裝載問題;最小生成樹問題;單源最短路徑問題;活動(dòng)安排問題;部分背包問題】6、問題：0-1背包問題與部分背包問題的區(qū)別在于()。選項(xiàng)：A:沒有區(qū)別，它們的含義相同B:若用貪心算法解決0-1背包問題，只能得到近似最優(yōu)解C:在0-1背包問題中，物品只有裝入和不裝入兩種情況，而部分背包問題允許只裝入物品的一部分D:若用貪心算法解決部分背包問題，只能得到近似最優(yōu)解答案:【若用貪心算法解決0-1背包問題，只能得到近似最優(yōu)解;在0-1背包問題中，物品只有裝入和不裝入兩種情況，而部分背包問題允許只裝入物品的一部分】7、問題：在求解部分背包問題時(shí)采用的貪心策略是()。選項(xiàng)：A:選擇重量最輕的物品B:選擇單位價(jià)值下重量最大的物品C:選擇價(jià)值最大的物品D:選擇單位重量下價(jià)值最大的物品答案:【選擇單位重量下價(jià)值最大的物品】8、問題：Dijkstra算法可用于求解()。選項(xiàng)：A:單源最短路徑問題B:每對(duì)頂點(diǎn)間最短路徑問題C:單終點(diǎn)最短路徑問題D:單對(duì)頂點(diǎn)最短路徑問題答案:【單源最短路徑問題;每對(duì)頂點(diǎn)間最短路徑問題;單終點(diǎn)最短路徑問題;單對(duì)頂點(diǎn)最短路徑問題】9、問題：Prim算法適合稀疏圖，其時(shí)間復(fù)雜度只與邊的數(shù)目有關(guān)。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】10、問題：在對(duì)Dijkstra算法進(jìn)行初始化時(shí)，如果兩個(gè)頂點(diǎn)之間沒有邊，則它們之間的距離為()。選項(xiàng)：A:無窮大B:無窮小C:0D:-1答案:【無窮大】第五章單元測試1、問題：回溯法中的剪枝函數(shù)包括()。選項(xiàng)：A:隨機(jī)數(shù)生成函數(shù)B:約束函數(shù)C:虛函數(shù)D:遞歸函數(shù)E:靜態(tài)函數(shù)F:限界函數(shù)答案:【約束函數(shù);限界函數(shù)】2、問題：回溯法采用的搜索策略是()。選項(xiàng)：A:啟發(fā)式搜索B:層次搜索C:深度優(yōu)先搜索D:廣度優(yōu)先搜索答案:【深度優(yōu)先搜索】3、問題：回溯法的主要用途包括求問題的所有解、求問題的最優(yōu)解和求問題的任一解。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】4、問題：馬的遍歷問題能否有可行解，與()有關(guān)。選項(xiàng)：A:馬的遍歷深度B:馬的遍歷順序C:馬的初始位置D:棋盤大小答案:【馬的初始位置;棋盤大小】5、問題：在N皇后問題中，需要將棋盤當(dāng)做一個(gè)二維數(shù)組來分析，對(duì)于該二維數(shù)組，以下說法正確的是()。選項(xiàng)：A:對(duì)于任意一條左斜線上的兩個(gè)點(diǎn)，它們的橫坐標(biāo)和縱坐標(biāo)相減的值相同。B:對(duì)于任意一條左斜線上的兩個(gè)點(diǎn)，它們的橫坐標(biāo)和縱坐標(biāo)相加的值相同。C:對(duì)于任意一條右斜線上的兩個(gè)點(diǎn)，它們的橫坐標(biāo)和縱坐標(biāo)相加的值相同。D:對(duì)于任意一條右斜線上的兩個(gè)點(diǎn)，它們的橫坐標(biāo)和縱坐標(biāo)相減的值相同。答案:【對(duì)于任意一條左斜線上的兩個(gè)點(diǎn)，它們的橫坐標(biāo)和縱坐標(biāo)相加的值相同。;對(duì)于任意一條右斜線上的兩個(gè)點(diǎn)，它們的橫坐標(biāo)和縱坐標(biāo)相減的值相同?！?、問題：四皇后問題一共有2個(gè)可行解，八皇后問題一共有76個(gè)可行解。選項(xiàng)：A:錯(cuò)B:對(duì)答案:【錯(cuò)】7、問題：用m種顏色給n個(gè)頂點(diǎn)著色、且使一條邊的兩個(gè)頂點(diǎn)顏色不同，則對(duì)應(yīng)的解空間樹是一棵()。選項(xiàng)：A:高為m的m叉樹B:高為n的m叉樹C:高為m的n叉樹D:高為n的n叉樹答案:【高為n的m叉樹】8、問題：任何一張地圖只用()種顏色就能使具有共同邊界的國家著上不同的顏色。選項(xiàng)：A:4B:6C:3D:2答案:【4】9、問題：使用回溯法求解0-1背包問題時(shí)，計(jì)算右子樹上界的方法是通過貪心策略求得上界，即將剩余物品依其單位重量價(jià)值排序，然后依次裝入物品，直至裝不下時(shí)，再裝入該物品的一部分而裝滿背包，此時(shí)得到的價(jià)值就是右子樹中解的上界。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】10、問題：關(guān)于使用回溯法求解0-1背包問題，以下說法正確的是()。選項(xiàng)：A:使用約束函數(shù)剪去不合理的左子樹（裝該物品）。B:使用限界函數(shù)剪去得不到更優(yōu)解的左子樹（裝該物品）。C:使用限界函數(shù)剪去得不到更優(yōu)解的右子樹（不裝該物品）。D:使用約束函數(shù)剪去不合理的右子樹（不裝該物品）。答案:【使用約束函數(shù)剪去不合理的左子樹（裝該物品）。;使用限界函數(shù)剪去得不到更優(yōu)解的右子樹（不裝該物品）?！康诹聠卧獪y試1、問題：分支限界法采用的搜索策略是()。選項(xiàng)：A:遞歸搜索B:啟發(fā)式搜索C:深度優(yōu)先搜索D:廣度優(yōu)先搜索答案:【廣度優(yōu)先搜索】2、問題：根據(jù)活結(jié)點(diǎn)表的組織方式不同，分支限界法包括()等形式。選項(xiàng)：A:單調(diào)隊(duì)列式分支限界法B:棧式分支限界法C:優(yōu)先隊(duì)列式分支限界法D:隊(duì)列式分支限界法E:二叉樹式分支限界法答案:【優(yōu)先隊(duì)列式分支限界法;隊(duì)列式分支限界法】3、問題：關(guān)于回溯法和分支限界法，以下說法正確的是()。選項(xiàng)：A:回溯法通常用于求滿足約束條件的所有解B:分支限界法通常用于求滿足約束條件的一個(gè)解或特定意義下的最優(yōu)解C:在分支限界法中，每個(gè)結(jié)點(diǎn)只有一次成為擴(kuò)展結(jié)點(diǎn)的機(jī)會(huì)D:在回溯法中，活結(jié)點(diǎn)的所有可行子結(jié)點(diǎn)均被遍歷后才從棧中彈出答案:【回溯法通常用于求滿足約束條件的所有解;分支限界法通常用于求滿足約束條件的一個(gè)解或特定意義下的最優(yōu)解;在分支限界法中，每個(gè)結(jié)點(diǎn)只有一次成為擴(kuò)展結(jié)點(diǎn)的機(jī)會(huì);在回溯法中，活結(jié)點(diǎn)的所有可行子結(jié)點(diǎn)均被遍歷后才從棧中彈出】4、問題：應(yīng)用分支限界法的三個(gè)關(guān)鍵問題包括()。選項(xiàng)：A:如何設(shè)計(jì)合適的剪枝函數(shù)B:如何組織活結(jié)點(diǎn)表C:如何限制搜索的層次D:如何確定最優(yōu)解的解向量答案:【如何設(shè)計(jì)合適的剪枝函數(shù);如何組織活結(jié)點(diǎn)表;如何確定最優(yōu)解的解向量】5、問題：關(guān)于分支限界法的基本思想，下列描述正確的是()。選項(xiàng)：A:一直持續(xù)到找到所求的解或活結(jié)點(diǎn)表為空時(shí)為止B:從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)結(jié)點(diǎn)擴(kuò)展過程C:那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的子結(jié)點(diǎn)被舍棄，其余子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中D:活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有子結(jié)點(diǎn)E:每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)答案:【一直持續(xù)到找到所求的解或活結(jié)點(diǎn)表為空時(shí)為止;從活結(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)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有子結(jié)點(diǎn);每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)】6、問題：優(yōu)先隊(duì)列式分支限界法將活結(jié)點(diǎn)表組織成一個(gè)優(yōu)先隊(duì)列，按優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)選取優(yōu)先級(jí)最高的下一個(gè)結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】7、問題：隊(duì)列具有()的性質(zhì)。選項(xiàng)：A:先進(jìn)先出B:僅進(jìn)不出C:進(jìn)出無序D:先進(jìn)后出答案:【先進(jìn)先出】8、問題：使用隊(duì)列式分支限界法求解裝載問題時(shí)，每次從隊(duì)列Q中取出隊(duì)首元素作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。取隊(duì)首元素后，判斷當(dāng)前Q是否為空。如Q非空，則將尾部標(biāo)記-1加入Q，算法開始處理下一層的活結(jié)點(diǎn)。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】9、問題：如果一個(gè)給定裝載問題有解，則采用的裝載策略為：首先將第一艘輪船盡可能裝滿；再將剩余的集裝箱裝上第二艘輪船。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】10、問題：在裝載問題中，如果右子樹表示不將此集裝箱裝上船。設(shè)bestw是當(dāng)前最優(yōu)解；ew是當(dāng)前擴(kuò)展結(jié)點(diǎn)所相應(yīng)的重量；r是剩余集裝箱的重量，則當(dāng)()時(shí)，可將其右子樹剪去。選項(xiàng)：A:ew+r<=bestwB:rC:r>=bestwD:ew+r>bestw答案:【ew+r<=bestw】第七章單元測試1、問題：動(dòng)態(tài)規(guī)劃算法把原問題分為交叉的子問題，解決子問題，記錄子問題的解，合并為原問題的解。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】2、問題：0/1背包問題的動(dòng)態(tài)規(guī)劃算法是多項(xiàng)式時(shí)間算法。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】3、問題：對(duì)于稀疏圖，F(xiàn)loyd算法的效率要高于執(zhí)行n次Dijkstra算法，也要高于執(zhí)行n次算法。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】4、問題：Dijkstra算法在求解過程中，源點(diǎn)到集合S內(nèi)各頂點(diǎn)的最短路徑一旦求出，則之后不變了，修改的僅僅是源點(diǎn)到還沒選擇的頂點(diǎn)的最短路徑長度。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】5、問題：含負(fù)權(quán)的最短路問題一般使用（）求解。選項(xiàng)：A:動(dòng)態(tài)規(guī)劃B:貪心算法C:分治算法D:網(wǎng)絡(luò)流算法答案:【動(dòng)態(tài)規(guī)劃】6、問題：動(dòng)態(tài)規(guī)劃算法的基本要素有（）和最優(yōu)子結(jié)構(gòu)性質(zhì)。選項(xiàng)：A:分解合并性質(zhì)B:獨(dú)立子問題性質(zhì)C:貪心選擇性質(zhì)D:重疊子問題性質(zhì)答案:【重疊子問題性質(zhì)】7、問題：下面不是動(dòng)態(tài)規(guī)劃的基本方法有（）。選項(xiàng)：A:多重選擇B:增加變量C:舍入D:區(qū)間變量答案:【舍入】8、問題：最短路算法中適用于稀疏圖的是（）選項(xiàng)：A:Floyd算法算法C:Bellman算法D:Dijkstra算法答案:【算法;Bellman算法;Dijkstra算法】9、問題：動(dòng)態(tài)規(guī)劃算法的特點(diǎn)（）選項(xiàng)：A:自底向上計(jì)算B:自頂向下計(jì)算C:從大到小計(jì)算D:從小到大計(jì)算答案:【自底向上計(jì)算;從小到大計(jì)算】10、問題：備忘錄算法的特點(diǎn)（）選項(xiàng)：A:自底向上計(jì)算B:自頂向下計(jì)算C:從大到小計(jì)算D:從小到大計(jì)算答案:【自頂向下計(jì)算;從大到小計(jì)算】第八章單元測試1、問題：回溯法是按廣度優(yōu)先策略搜索解空間樹。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】2、問題：死結(jié)點(diǎn)是正在產(chǎn)生兒子的結(jié)點(diǎn)。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】3、問題：回溯法的一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】第九章單元測試1、問題：分支限界法在對(duì)問題的解空間樹進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)有多次機(jī)會(huì)成為活結(jié)點(diǎn)。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】2、問題：分支限界法找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】3、問題：隊(duì)列式分支限界法以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】4、問題：優(yōu)先隊(duì)列式分支限界法按照隊(duì)列先進(jìn)先出的原則，選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】5、問題：下列算法中不能解決0/1背包問題的是選項(xiàng)：A:貪心法B:動(dòng)態(tài)規(guī)劃C:回溯法D:分支限界法答案:【貪心法】6、問題：分支限界法解旅行商問題時(shí)的解空間樹是選項(xiàng)：A:子集樹B:排列樹C:深度優(yōu)先生成樹D:廣度優(yōu)先生成樹答案:【排列樹】7、問題：優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是選項(xiàng)：A:先進(jìn)先出B:后進(jìn)先出C:結(jié)點(diǎn)的優(yōu)先級(jí)D:隨機(jī)答案:【結(jié)點(diǎn)的優(yōu)先級(jí)】8、問題：用分支限界法設(shè)計(jì)算法的步驟是：選項(xiàng)：A:針對(duì)所給問題，定義問題的解空間（對(duì)解進(jìn)行編碼）B:確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）C:定義最優(yōu)子結(jié)構(gòu)D:以廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索答案:【針對(duì)所給問題，定義問題的解空間（對(duì)解進(jìn)行編碼）;確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）;以廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索】9、問題：分支限界法與回溯法的不同點(diǎn)是什么？選項(xiàng)：A:求解目標(biāo)不同B:搜索方式不同C:對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同D:存儲(chǔ)空間的要求不同答案:【求解目標(biāo)不同;搜索方式不同;對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同;存儲(chǔ)空間的要求不同】10、問題：FIFO是（）的搜索方式。選項(xiàng)：A:回溯算法B:分支限界C:動(dòng)態(tài)規(guī)劃D:貪心算法答案:【分支限界】第十章單元測試1、問題：網(wǎng)絡(luò)流滿足容量約束，但一般不滿足流量守恒約束。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】2、問題：設(shè)G=為二分圖,|V1|≤|V2|,M為G中一個(gè)最大匹配,且|M|=|V1|,則稱M為G的完備匹配，也是最大匹配。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】3、問題：存在割(A,B)使流值v(f)=割的容量cap(A,B).，則割(A,B)是最小割。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】4、問題：給定連通圖G,BFS遍歷得到層次圖，如果同一層中的結(jié)點(diǎn)無邊相連，則G是二分圖。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】5、問題：有下界的流通問題不一定有可行流。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】6、問題：Dinic算法的時(shí)間復(fù)雜度為（）選項(xiàng)：A:mn2B:mnC:m2nD:m2logC答案:【mn2】7、問題：如果每條邊的最大容量為1，則時(shí)間復(fù)雜度是O（nm）的網(wǎng)絡(luò)流算法有選項(xiàng)：A:FF算法B:容量縮放算法C:EK算法D:Dinic算法答案:【FF算法】8、問題：給定二分圖G=中無孤立點(diǎn)，|V|=n，其最大流算法求得最大流f,則G的（）=n-f選項(xiàng)：A:最大獨(dú)立數(shù)B:最大匹配數(shù)C:最小頂點(diǎn)覆蓋D:最小邊覆蓋答案:【最大獨(dú)立數(shù);最小邊覆蓋】9、問題：改進(jìn)FF網(wǎng)絡(luò)流算法，可以通過選擇（）增廣路，降低時(shí)間復(fù)雜度。選項(xiàng)：A:最大容量B:最短路徑C:最大瓶頸容量D:邊數(shù)最少答案:【最大容量;最短路徑;最大瓶頸容量;邊數(shù)最少】10、問題：帶需求的流通必須滿足供給和=需求和選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】第十一章單元測試1、問題：蒙特卡羅算法的結(jié)果肯定是一個(gè)正確解。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】2、問題：Sherwood算法隨機(jī)選擇一個(gè)數(shù)組元素作為劃分標(biāo)準(zhǔn)求解k小元素問題,保證線性時(shí)間的平均性能。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】3、問題：借助隨機(jī)預(yù)處理技術(shù)，不改變原有的確定性算法，僅對(duì)其輸入進(jìn)行隨機(jī)洗牌，可收到舍伍德算法的效果。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】4、問題：隨機(jī)算法共同點(diǎn)是計(jì)算時(shí)間越多或運(yùn)行次數(shù)越多,正確性越高.選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】5、問題：增加拉斯維加斯算法的反復(fù)求解次數(shù),可使求解無效的概率任意小。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】6、問題：在下列算法中有時(shí)找不到問題解的是選項(xiàng)：A:蒙特卡羅算法B:拉斯維加斯算法C:舍伍德算法D:數(shù)值隨機(jī)算法答案:【拉斯維加斯算法】7、問題：肯定獲得可行解，但不一定是正確解的算法是選項(xiàng)：A:蒙特卡羅算法B:拉斯維加斯算法C:舍伍德算法D:數(shù)值隨機(jī)算法答案:【蒙特卡羅算法】8、問題：在一般輸入數(shù)據(jù)的程序里，輸入多少會(huì)影響到算法的計(jì)算復(fù)雜度，為了消除這種影響可用（）對(duì)輸入進(jìn)行預(yù)處理。選項(xiàng)：A:蒙特卡羅算法B:拉斯維加斯算法C:舍伍德算法D:數(shù)值隨機(jī)化算法答案:【舍伍德算法】9、問題：（）肯定獲得最優(yōu)解。選項(xiàng)：A:分支限界B:貪心算法C:隨機(jī)算法D:動(dòng)態(tài)規(guī)劃算法答案:【分支限界;動(dòng)態(tài)規(guī)劃算法】10、問題：下面說法正確的是選項(xiàng)：A:現(xiàn)實(shí)計(jì)算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù)B:求解同一實(shí)例用同一隨機(jī)化算法求解兩次，所用時(shí)間和所得結(jié)果可能完全不同。C:蒙特卡羅算法總是能提供問題的一個(gè)解,但可能給出錯(cuò)誤解。D:舍伍德算法的精髓不是避免最壞的情況，而是設(shè)法消除最壞情況和特定實(shí)例的關(guān)聯(lián)性。答案:【現(xiàn)實(shí)計(jì)算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù);求解同一實(shí)例用同一隨機(jī)化算法求解兩次，所用時(shí)間和所得結(jié)果可能完全不同。;蒙特卡羅算法總是能提供問題的一個(gè)解,但可能給出錯(cuò)誤解。;舍伍德算法的精髓不是避免最壞的情況，而是設(shè)法消除最壞情況和特定實(shí)例的關(guān)聯(lián)性?！康谑聠卧獪y試1、問題：有多項(xiàng)式時(shí)間算法的問題是易解問題選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】2、問題：EXP類是所有指數(shù)時(shí)間可解的判定問題組成的問題類選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】3、問題：如果對(duì)于X的任意實(shí)例，通過多項(xiàng)式次的計(jì)算步驟，加多項(xiàng)式次調(diào)用Y的算法，可解決X，則X可多項(xiàng)式時(shí)間歸約到Y(jié)。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【對(duì)】4、問題：如果X問題Y且Y不能多項(xiàng)式時(shí)間解決,那么X也不能多項(xiàng)式時(shí)間解決。選項(xiàng)：A:對(duì)B:錯(cuò)答案:【錯(cuò)】5、問題：下面關(guān)于NP問題說法正確的是（）選項(xiàng)：A:NP問題都是不可能解決的問題B:P類問題包含在NP類問題中C:NP完全問題是P類問題的子集D:NP類問題包含在P類問題中答案:【P類問題包含在NP類問題中】6、問題：P類