1、算法分析復(fù)習(xí)題目及答案

一個(gè)。選擇題1，二分搜索算法是利用(a)實(shí)現(xiàn)的算法。a，分割策略b，動(dòng)態(tài)規(guī)劃方法c，貪心方法d，回溯方法2、以下不是動(dòng)態(tài)編程算法的基本步驟(a):a，確定最佳解決方案的特征b，配置最佳解決方案c，計(jì)算最佳解決方案d，定義最佳解決方案3、最大的優(yōu)點(diǎn)是(a)搜索方法。a，分支邊界方法b，動(dòng)態(tài)規(guī)劃方法c，貪心方法d，回溯方法4、以下算法有時(shí)找不到解決問題的方法是(b)。a，Monte Carlo算法b，拉斯維加斯算法c，shewood算法d，數(shù)值概率算法5.以回溯方式解決旅行推銷員問題時(shí)，空間樹為(b)。a、子集樹b、陣列樹c、深度優(yōu)秀教師樹d、寬度優(yōu)秀教師樹6.在以下算法中，通常自下而上解決最佳解決方案是(b):a，備忘錄方法b，動(dòng)態(tài)編程方法c，貪心方法d，回溯方法7、衡量算法好壞的標(biāo)準(zhǔn)是(c)。a快速執(zhí)行速度b占用空間小c時(shí)間復(fù)雜性低d代碼短8、以下無法使用分割方法解決(d):主板封面問題b選擇問題c合并排序D 0/1背包問題9.使用倒圓角日程表的算法為(a)。a，分割策略b，動(dòng)態(tài)規(guī)劃方法c，貪心方法d，回溯方法10，在以下任意算法中運(yùn)行時(shí)成功有時(shí)失敗(c)a數(shù)值概率算法b舍伍德算法c拉斯維加斯算法d蒙特卡羅算法11.以下不是分支邊界方法搜索方法(d):a，寬度優(yōu)先b，最小消費(fèi)優(yōu)先c，最大收益優(yōu)先d，深度優(yōu)先12.在以下算法中，用深度優(yōu)先方案解決問題通常是(d)。a，備忘錄方法b，動(dòng)態(tài)編程方法c，貪心方法d，回溯方法13.備忘錄方法是那種算法的變體。(b)a，分離法b，動(dòng)態(tài)規(guī)劃法c，貪婪法d，回溯法14.赫夫曼編碼的貪心算法所需的計(jì)算時(shí)間為(b)。a、O(n2n)B、O(nlogin) c、O(2n)D、O(n)15.分支邊界方法解決最大組問題時(shí)，活動(dòng)節(jié)點(diǎn)表為(b)。a、最小堆b、最大堆c、堆棧d、數(shù)組16.最長(zhǎng)公共子序列算法使用的算法為(b)。a，分支邊界方法b，動(dòng)態(tài)規(guī)劃方法c，貪心方法d，回溯方法17.實(shí)現(xiàn)電路板覆蓋算法使用的算法是(a)。a，分離法b，動(dòng)態(tài)規(guī)劃法c，貪婪法d，回溯法以下是貪心算法的基本元素(c)。a，重疊子問題b，配置最優(yōu)解c，貪心選擇特性d，定義最優(yōu)解19.回溯方法的效率不依賴以下因素(d)A.滿足顯式約束的值數(shù)b。約束函數(shù)計(jì)算時(shí)間C.邊界函數(shù)計(jì)算時(shí)間d .空間求解時(shí)間的確定20.以下哪項(xiàng)是避免無效搜索的回溯方法的策略(b)A.遞歸函數(shù)b .修剪函數(shù)c .隨機(jī)數(shù)函數(shù)d .搜索函數(shù)21、以下關(guān)于NP問題的陳述是正確的(b)A NP問題是無法解決的問題B P類問題包含在NP類問題中C NP整體問題是p類問題的子集D NP類問題包含在p類問題中22，Monte Carlo算法是(b)之一。a，分支邊界算法b，概率算法c，貪心算法d，回溯算法以下哪種算法不是隨機(jī)算法(c)A.蒙特卡羅算法b .拉斯維加斯算法c .動(dòng)態(tài)編程算法d .舍伍德算法24.(D)貪心算法和動(dòng)態(tài)編程算法的共同點(diǎn)。a，重疊子問題b，構(gòu)造最優(yōu)解c，貪心選擇特性d，最優(yōu)子結(jié)構(gòu)特性矩陣乘法問題的算法可由(b)設(shè)計(jì)實(shí)現(xiàn)。a，分支邊界算法b，動(dòng)態(tài)規(guī)劃算法c，貪心算法d，回溯算法26.用分界法解決旅行推銷員問題，活節(jié)點(diǎn)的組織形式為(a)。a、最小堆b、最大堆c、堆棧d、數(shù)組27，Strassen矩陣乘法是使用(a)實(shí)現(xiàn)的算法。a，分割策略b，動(dòng)態(tài)規(guī)劃方法c，貪心方法d，回溯方法29、使用分割方法解決不能滿足的條件是(a)。a子問題必須相同b子問題不能重復(fù)可以組合c子問題的解決方案d原始問題和子問題使用相同的方法解決30、下一個(gè)問題(b)不能用貪心的方法解決。單源最短路徑問題B N皇后問題c最小支出生成樹問題d背包問題31，以下算法無法解決0/1背包問題：(a)貪心法b動(dòng)態(tài)規(guī)劃c回溯法d分支邊界法33，在以下任意算法中運(yùn)行時(shí)成功有時(shí)失敗(c)a數(shù)值概率算法b舍伍德算法c拉斯維加斯算法d蒙特卡羅算法34.實(shí)現(xiàn)統(tǒng)一排序使用的算法為(a)。a，分割策略b，動(dòng)態(tài)規(guī)劃方法c，貪心方法d，回溯方法以下是動(dòng)態(tài)編程算法的基本元素(d):a，最佳解決方案定義b，最佳解決方案配置c，最佳解決方案d計(jì)算，子問題重疊特性使用寬優(yōu)先級(jí)策略搜索的算法為(a)。a，分支邊界方法b，動(dòng)態(tài)規(guī)劃方法c，貪心方法d，回溯方法38，合并排序算法是使用(a)實(shí)現(xiàn)的算法。a，分割策略b，動(dòng)態(tài)規(guī)劃方法c，貪心方法d，回溯方法39、從以下算法中獲得的解決方案可能不正確(b):a，Monte Carlo算法b，拉斯維加斯算法c，shewood算法d，數(shù)值概率算法40，背包問題的貪心算法所需的計(jì)算時(shí)間為(b)a、O(n2n) B、O(nlogin) c、O(2n) D、O(n)41.實(shí)現(xiàn)大整數(shù)的乘法是使用的算法(c)。a，貪心方法b，動(dòng)態(tài)規(guī)劃方法c，分割策略d，回溯方法42.0-1背包問題的回溯算法所需的計(jì)算時(shí)間為(a)a、O(n2n)B、O(nlogin) c、O(2n)D、O(n)43.使用最有效的優(yōu)先級(jí)搜索方法的算法為(a)。a，分支邊界方法b，動(dòng)態(tài)規(guī)劃方法c，貪心方法d，回溯方法貪心算法和動(dòng)態(tài)編程算法的主要區(qū)別是(b)。a，最優(yōu)子結(jié)構(gòu)b，貪婪選擇特性c，配置最優(yōu)解d，定義最優(yōu)解45.最大子段和利用的算法為(b)。a，分割策略b，動(dòng)態(tài)規(guī)劃方法c，貪心方法d，回溯方法46.優(yōu)先隊(duì)列分支極限法擴(kuò)展節(jié)點(diǎn)選擇原則是(c)。a、FIFO b、LIFO c、節(jié)點(diǎn)的優(yōu)先級(jí)d、隨機(jī)47.背包問題的貪心算法所需的計(jì)算時(shí)間為(b)。a、O(n2n)B、O(nlogin) c、O(2n)D、O(n)48、優(yōu)先級(jí)是(a)搜索方法。a，分支邊界方法b，動(dòng)態(tài)規(guī)劃方法c，貪心方法d，回溯方法49，舍伍德算法是(b)之一。a，分支邊界算法b，概率算法c，貪心算法d，回溯算法50，以下算法有時(shí)找不到解決問題的方法是(b)。a，Monte Carlo算法b，拉斯維加斯算法c，shewood算法d，數(shù)值概率算法51以下隨機(jī)抽取算法(d)A.貪心算法b .回溯方法c .動(dòng)態(tài)規(guī)劃算法d .舍伍德算法52.一個(gè)問題可以通過動(dòng)態(tài)編程算法或貪心算法解決，其核心特征是問題(b)。a，重疊子問題b，最優(yōu)子結(jié)構(gòu)特性c，貪心選擇特性d，定義最優(yōu)解53.使用貪心算法的最優(yōu)裝載問題的主計(jì)算在按重量追溯排序容器時(shí)，算法的時(shí)間復(fù)雜度為(b)。a、O(n2n)B、O(nlogin) c、O(2n)D、O(n)54.以深度優(yōu)先順序在系統(tǒng)中搜尋疑難排解的演算法稱為(d)。a，分支邊界算法b，概率算法c，貪心算法d，回溯算法55.實(shí)現(xiàn)使用最長(zhǎng)公共子序列的算法為(b)。a，分割策略b，動(dòng)態(tài)規(guī)劃方法c，貪心方法d，回溯方法二、填空1.算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性。2、程序是算法用某種編程語言具體實(shí)現(xiàn)的。3、算法的“確定性”意味著構(gòu)成算法的每個(gè)指令都清晰、不模糊。矩陣乘法問題的算法可以通過動(dòng)態(tài)編程設(shè)計(jì)實(shí)現(xiàn)。5、拉斯維加斯算法發(fā)現(xiàn)的解決方案必須是正確的解決方案。6、算法表示解決問題的方法或過程。7，如分割方法的一般設(shè)計(jì)模式所示，用它設(shè)計(jì)的程序通常是遞歸算法。8、問題的最優(yōu)子結(jié)構(gòu)特性是用動(dòng)態(tài)編程算法或貪心算法解決該問題的核心特征。9、以深度優(yōu)先順序在系統(tǒng)中搜索問題解決方案的算法稱為回溯方法。10、數(shù)值概率算法通常用于解決數(shù)值問題。11、一般計(jì)算迭代次數(shù)、基本操作的頻率或計(jì)算步驟的算法時(shí)間復(fù)雜度。12、利用概率特性計(jì)算近似值的概率算法為_ _數(shù)值概率算法，在運(yùn)行時(shí)以一定概率精確解決的概率算法為_ _ Monte Carlo算法14，0/1背包故障診斷可以使用動(dòng)態(tài)編程、回溯方法和分支極限法。這里不需要對(duì)齊的是動(dòng)態(tài)編程，必須對(duì)齊回溯法，分支極限法。15，使用回溯方法的狀態(tài)空間樹修剪分支通常有兩個(gè)標(biāo)準(zhǔn)。約束和目標(biāo)函數(shù)的邊界，皇后問題和0/1背包問題正好是兩種不同的類型。其中，使用約束和目標(biāo)函數(shù)的邊界修剪是0/1背包問題，僅使用約束修剪是皇后問題。16、貪心選擇的特點(diǎn)是貪心算法是第一個(gè)可行的基本要素，貪心算法和動(dòng)態(tài)編程算法的主要區(qū)別。17，矩陣乘法問題的算法可由動(dòng)態(tài)編程設(shè)計(jì)實(shí)現(xiàn)。18、拉斯維加斯算法找到的解決方案必須是正確的解決方案。19.貪心算法的基本要素是貪心選擇質(zhì)量和最佳子結(jié)構(gòu)特性。21.動(dòng)態(tài)編程算法的基本思想是把要解決的問題分成幾個(gè)子問題，先解決子問題，然后解決這些子問題。22.算法是由多個(gè)命令組成的有限序列，滿足輸入、輸出、確定性和有限四個(gè)特性。23、大整數(shù)乘積算法采用分割方法設(shè)計(jì)。24、以面積優(yōu)先或最小消耗的方式搜索問題解決方案的算法稱為分支定界法。25、舍伍德算法總能找到問題的解決方法。26、貪心選擇的特點(diǎn)是貪心算法是第一個(gè)可行的基本要素，貪心算法和動(dòng)態(tài)編程算法的主要區(qū)別。27.快速排序算法是基于分割策略的一種排序算法。28.動(dòng)態(tài)編程算法的兩個(gè)基本要素是。最佳子結(jié)構(gòu)性質(zhì)和復(fù)疊子問題性質(zhì)?；厮莘椒ㄊ且环N既有系統(tǒng)又有跳躍性的搜索算法。31.分支極限法主要有基于隊(duì)列(FIFO)的分支極限法和基于優(yōu)先級(jí)隊(duì)列的分支極限法。32.分支極限法是既有系統(tǒng)又有跳躍性的搜索算法。33.用回溯方法檢索空間樹時(shí)常用的兩種修剪函數(shù)是約束函數(shù)和邊界函數(shù)。34.可用計(jì)算機(jī)解決問題所需的時(shí)間與大小有關(guān)。35.快速排序算法的性能取決于分割對(duì)稱。三、填補(bǔ)空白的算法1.背包問題的貪心算法Void knapsack (int n，float m，float v ，float w ，float x )Sort(n、v、w)；int I；for(I=1)；I=n；I)xI=0；float c=M；for(I=1)；I=n；I) if(wIc)break；xI=1；c-=wI；if(I=n)xI=c/wI；2.最大子段和：動(dòng)態(tài)編程算法Int MaxSum(int n，int a)Int sum=0，b=0；/sum存儲(chǔ)當(dāng)前最大的bj，b存儲(chǔ)bjfor(intj=1；j=n；J) _if(B0)b=aj；else b=aj；/如果一個(gè)部分和為負(fù)數(shù)，則在以下位置累if(bsum)sum=b；Return sum；貪心算法查找裝載問題。第一次V