《算法分析與設(shè)計》期末考試復(fù)習(xí)題庫（含答案）

PAGEPAGE1《算法分析與設(shè)計》期末考試復(fù)習(xí)題庫（含答案）一、單選題1.尋找n個元素中第k小元素問題中，如快速排序算法思想，運(yùn)用分治算法對n個元素進(jìn)行劃分，如何選擇劃分基準(zhǔn)？下面（）答案解釋最合理。A、以上皆可行。但不同方法，算法復(fù)雜度上界可能不同B、隨機(jī)選擇一個元素作劃分基準(zhǔn)C、用中位數(shù)作為劃分基準(zhǔn)D、取子序列的第一個元素作為劃分基準(zhǔn)答案：A2.猜數(shù)游戲:隨機(jī)選擇一個0~100內(nèi)的整數(shù)，讓你猜。猜對了，你贏了，游戲結(jié)束。如果沒有猜對會告訴你猜大了，還是猜小了。當(dāng)然，越早猜對越好。問最少需要猜多少次，就能保證一定能猜對?A、6B、7C、51D、101答案：B3.函數(shù)32n+10nlogn的漸進(jìn)表達(dá)式是A、nlognB、32nC、10nlognD、2n答案：B4.含負(fù)權(quán)的最短路問題一般使用（）求解。A、貪心算法B、分治算法C、動態(tài)規(guī)劃D、網(wǎng)絡(luò)流算法答案：C5.下面不是動態(tài)規(guī)劃算法的基本要素的是（）。A、獨(dú)立子問題性質(zhì)B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、重疊子問題性質(zhì)D、無后效性答案：A6.求第n個斐波那契數(shù)的問題，根據(jù)動態(tài)規(guī)劃的二要素分析，是可以用動態(tài)規(guī)劃算法去解決的，下面是用備忘錄方法(遞歸)解決的求第n個斐波那契數(shù)f[n的程序.這里N是一個較大的正整數(shù)常量，注意備忘錄方法的設(shè)計要點(diǎn)(也就是，對于一個問題，首先判斷是否該問題已被解決過，如果解決，不再重復(fù)。另外，解決過的問題，答案要記住)代碼中【1】和【2】位置代碼缺失，請從下列選項(xiàng)中選出合適的語句補(bǔ)齊算法。A、B、C、D、答案：C7.剪枝函數(shù)包括（）和約束函數(shù)A、啟發(fā)式函數(shù)B、最優(yōu)函數(shù)C、估計函數(shù)D、限界函數(shù)答案：D8.能采用貪心算法求最優(yōu)解的問題，一般具有的重要性質(zhì)為A、預(yù)排序與遞歸調(diào)用B、最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)C、重疊子問題性質(zhì)與貪心選擇性質(zhì)D、最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)答案：D9.下面哪些內(nèi)容不是算法設(shè)計之前要完成的內(nèi)容?()A、是求精確解還是近似解B、確定合適的數(shù)據(jù)結(jié)構(gòu)C、使用何種計算機(jī)語言設(shè)計程序D、確定合適的算法策略答案：C10.1.在最長公共子序列問題中，我們用C[i,j]表示序列，X[1.i]和序列Y[1.j]的公共子序列長度。則遞推式應(yīng)為A、B、C、D、答案：B11.最優(yōu)子結(jié)構(gòu)性質(zhì)是A、問題的最優(yōu)解可通過性質(zhì)相同的子問題的最優(yōu)解合并而成B、子問題可同原問題性質(zhì)不同，但是原問題的最優(yōu)解可通過子問題的最優(yōu)解合并而成C、問題的最優(yōu)解可通過一步步局部最優(yōu)的選擇來獲得。D、問題可以分解為性質(zhì)相同的子問題答案：A12.裝載問題的回溯算法所需的計算時間為O（）A、n2B、nC、n!D、2n答案：D13.符號三角形問題的回溯算法如下half=（n+1）*n/4;//(n+1)*n/2是偶數(shù)voidbacktrack(intt){if((count>half)||(t*(t-1)/2-count>half))return;if(t>n)sum++;elsefor(inti=0;i<2;i++){p[1][t]=i;count+=i;for(intj=2;j<=t;j++){p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];count+=p[j][t-j+1];}【】backtrack(t+1);for(intj=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}現(xiàn)要求將紅色代碼去掉，保持算法功能不改變，需在【】添加下面哪段代碼？A、if((count>half)||(t*(t+1)/2-count>half))B、if((count>half)||(t*(t-1)/2-count>half))C、if((count<=half)&&(t*(t-1)/2-count<=half))D、if((count<=half)&&(t*(t+1)/2-count<=half))答案：D14.快速排序算法在最壞情況下的時間復(fù)雜度為（）。A、O(n2)B、O(nlogn)C、O(n3)D、O(n)答案：A15.下面關(guān)于動態(tài)規(guī)劃方法和備忘錄方法，正確的是（）A、動態(tài)規(guī)劃是自頂向下的，備忘錄方法是自底向上的。B、備忘錄算法需要計算所有子問題的最優(yōu)解，動態(tài)規(guī)劃算法不需要。C、動態(tài)規(guī)劃算法和備忘錄方法都需要配合記錄子問題最優(yōu)解的表格。D、動態(tài)規(guī)劃算法和備忘錄方法都可以用直接遞歸的方法計算。答案：C16.0-1背包向題中n=5,c=10,W［］={3,2,4,4,6｝，V［］=｛6,4,3,6,5｝，設(shè)m[i][j]是背包容量為j，可選物品為｛i,i+1.…，n}時背包問題最優(yōu)值，則當(dāng)可選物品只有最后三個物品時，背包的最大價值是（）A、10B、8C、9D、11答案：D17.旅行商問題的回溯算法所需的計算時間為O（）A、n！B、2^nC、nlognD、n^2答案：A18.（）肯定獲得最優(yōu)解A、隨機(jī)算法B、回溯C、動態(tài)規(guī)劃算法D、貪心算法答案：C19.背包問題的貪心算法所需的計算時間為A、O(nlogn)B、O(n)C、O(2n)D、(n2n)答案：A20.動態(tài)規(guī)劃解題的步驟分為四步（1）分析最優(yōu)解的結(jié)構(gòu)（2）建立遞歸關(guān)系（3）計算最優(yōu)值（4）構(gòu)造最優(yōu)解。關(guān)于這四個步驟的內(nèi)容描述不正確的是哪個？A、構(gòu)造最優(yōu)解：根據(jù)計算最優(yōu)值時得到的信息構(gòu)造出問題的最優(yōu)解，通常是用遞歸算法完成最優(yōu)解的構(gòu)造B、建立遞歸關(guān)系：建立關(guān)于問題最優(yōu)值的遞歸定義，即問題的最優(yōu)值通過子問題的最優(yōu)值合并得到。C、分析最優(yōu)解的結(jié)構(gòu)：一個一般化問題可以分解為幾個性質(zhì)相同的子問題，并且問題的最優(yōu)解可以通過子問題的最優(yōu)解合并得到，也就是要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)D、計算最優(yōu)值：以自頂往下的方法計算問題的最優(yōu)值，也就是先求解規(guī)模較大的問題的最優(yōu)值。答案：D21.A、B、C、D、答案：C22.n=12皇后問題的三種不同的解決方案：回溯法、拉斯維加斯算法、拉斯維加斯算法+回溯法。對于給定的一個實(shí)例，(1)平均耗費(fèi)時間最少的是那種方案，(2)平均耗費(fèi)時間最多的是那種方案？A、(1)回溯法(2)拉斯維加斯+回溯法B、(1)拉斯維加斯+回溯(2)回溯法C、（1)回溯法(2)拉斯維加斯D、(1)拉斯維加斯(2)回溯法答案：B23.閱讀該單元測試中關(guān)于0-1背包問題的優(yōu)先隊列分支限界算法代碼，??問左分支的剪枝條件是什么？右分支的剪枝條件是什么？從代碼中找到命令行，使用原代碼回答問題。A、左分支：wt<=c,右分支：up>bestpB、左分支：cp+p[i]>bestp,右分支：up>bestpC、左分支：cp+p[i]>bestp,右分支：wt<=cD、左分支：wt<=c,右分支：cp+p[i]>bestp答案：A24.對于一個采用字符數(shù)組存放的長度為n的字符串str，下面是用分治策略的遞歸算法去判斷字符串str是否為回文，如是回文，數(shù)返回true，否則返回false。比如:“abcba”“abba”是回文，“abc”則不是回文。算法中【】處缺少語句，請分析算法，從如下選項(xiàng)中選擇語句補(bǔ)齊算法。A、(1)n==1(2)str[n](3)str+1(4)n-1B、(1)n==1(2)str[n-1](3)str+1(4)n-2C、(1)str[0]==str[n-1](2)str[n-1](3)str(4)n-1D、(1)str[0]==str[n-1](2)str[n](3)str(4)n-2答案：B25.實(shí)現(xiàn)循環(huán)賽日程表利用的算法是A、分治策略B、動態(tài)規(guī)劃法C、回溯法D、貪心法答案：A26.分支限界法中，擴(kuò)展出的孩子結(jié)點(diǎn)在入隊時，存儲該孩子結(jié)點(diǎn)的父結(jié)點(diǎn)的地址和左孩子標(biāo)志。其目的是什么？A、為了計算最優(yōu)值B、為了方便判定是否已搜索到達(dá)葉子層C、為了構(gòu)造最優(yōu)解D、為了確定其孩子結(jié)點(diǎn)在隊列中的位置答案：C27.一致的p正確的偏y0的蒙特卡洛算法，下面解釋不正確的是?A、當(dāng)正確解是y0,而蒙特卡洛算法得到的解不是y0B、運(yùn)行蒙特卡洛算法p次，至少有一次是正確的。C、一致是指蒙特卡洛算法對于一個實(shí)例，其正確解是唯一的。D、猜硬幣的正反面問題，因?yàn)椴乱淮握_的概率是50%，所以不能使用蒙特卡洛算法解決。答案：B28.以下不可以使用分治法求解的是（）A、選擇問題B、0/1背包問題C、棋盤覆蓋問題D、歸并排序答案：B29.采用最大效益優(yōu)先搜索方式的算法是（）。A、貪心法B、動態(tài)規(guī)劃法C、回溯法D、分支限界法答案：D30.下面關(guān)于分治策略的說法錯誤的是A、需要把問題劃分成幾個規(guī)模較小的不同子問題B、解決劃分的子問題時遞歸使用原問題算法C、一般把問題劃分成若干個規(guī)模較小的相互獨(dú)立的子問題D、需要合并各子問題的解形成原問題的解答案：C31.下面哪個問題不是NPC問題A、最大團(tuán)問題B、最小生成樹問題C、旅行售貨員問題D、子集和問題答案：B32.下面哪些不是遞歸算法的特點(diǎn)A、結(jié)構(gòu)清晰B、可讀性強(qiáng)C、容易用數(shù)學(xué)歸納法證明算法的正確性D、遞歸算法耗費(fèi)的時間和占用的內(nèi)存空間要比解決同一問題的非遞歸算法要少答案：D33.一個問題，針對某個貪心策略，可通過找反例的方法快速判斷出其使用貪心算法不能構(gòu)造出最優(yōu)解。下面是關(guān)于0-1背包問題，貪心策略是優(yōu)先選擇單位重量價值大的物品裝入背包，有二個同學(xué)分別找到一個反例，證明貪心算法不能構(gòu)造出0-1背包問題的最優(yōu)解。（1）背包容量4，三個物品的重量和價值（wi，vi）:（2，4）,（2，3）,（2，2）（2）背包容量5，三個物品的重量和價值（wi，vi）:（1，2）,（2，3）,（4，4）?分析判定哪個反例是對的，哪個反例是錯的，從如下選項(xiàng)中找到你的答案。A、（1）對（2）錯B、（1）錯（2）錯C、（1）錯（2）對D、（1）對（2）對答案：A34.最長公共子序列算法利用的算法是A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：B35.有一個問題的蒙特卡洛算法，給定一個實(shí)例，已知運(yùn)行一次其答案是錯誤的概率是1/8,現(xiàn)運(yùn)行k次該算法，其答案一直不變，問該答案的正確率是？A、7/8B、1-(1/8)^kC、1-(7/8)^kD、(1/8)^k答案：B36.在隊列式分支限界法中，葉子結(jié)點(diǎn)不加入隊列。而在優(yōu)先隊列式分支限界法中，葉子結(jié)點(diǎn)通常要加入到優(yōu)先隊列中。有下列2個解釋：?（1）隊列式分支限界法，活結(jié)點(diǎn)在隊列中的順序是按照搜索解空間樹時擴(kuò)展出該結(jié)點(diǎn)的先后順序存放，每次從隊首取出一個活結(jié)點(diǎn)成為新的擴(kuò)展結(jié)點(diǎn)。擴(kuò)展結(jié)點(diǎn)擴(kuò)展出的兒子結(jié)點(diǎn)是葉子結(jié)點(diǎn)時，會將該葉子結(jié)點(diǎn)的值同當(dāng)前最優(yōu)值比較，檢查更新最優(yōu)值，葉子結(jié)點(diǎn)并不進(jìn)入隊列，等隊列為空時，搜索結(jié)束，記錄的當(dāng)前最優(yōu)值就是問題最優(yōu)值。?（2）優(yōu)先隊列式分支限界法中，當(dāng)優(yōu)先級的定義是限界函數(shù)時，擴(kuò)展出的葉子結(jié)點(diǎn)進(jìn)入隊列，這種做法主要是為了讓搜索過程提前結(jié)束。也就是當(dāng)從優(yōu)先隊列中取出一個活結(jié)點(diǎn)是葉子結(jié)點(diǎn)時，意味著現(xiàn)在優(yōu)先隊列中剩余的所有活結(jié)點(diǎn)其優(yōu)先級都不大于該葉子結(jié)點(diǎn)的優(yōu)先級，葉子結(jié)點(diǎn)的優(yōu)先級等于最優(yōu)值，算法結(jié)束，無論優(yōu)先隊列是否為空。?根據(jù)其正確與否，給出答案A、（1）錯誤，（2）錯誤B、（1）錯誤，（2）正確C、（1）正確，（2）正確D、（1）正確，（2）錯誤答案：C37.子集和問題：給定n個不同的正整數(shù)，已知其和大于c，問有多少個不同的其和等于c的子集？??下面給出的算法，解空間樹是子集樹，且n個數(shù)已按從小到大有序存放于a數(shù)組中。??voidbacktrack(inti)??{??if(sum==c)count++;??elseif(i<=n)??{??if(sum+a[i]<=c)??{sum+=a[i];??backtrack(i+1);??【】??}??}??}????請將【】位置缺失的代碼補(bǔ)齊，從下面選項(xiàng)中找到答案。A、backtrack(i+1);sum-=a[i];B、sum-=a[i];C、sum-=a[i];backtrack(i+1);D、backtrack(i+1);答案：C38.某中學(xué)有一個開水房，只有一個供熱水龍頭，課間時，會有很多同學(xué)去排隊打開水，同學(xué)們的水瓶大小不一，每個同學(xué)打水時都會將自己的水瓶裝滿。管理開水房的師傅是個聰明人，他想到了一個排隊方案，也就是同學(xué)們按照他給出的排隊方法，可以使同學(xué)們的平均等待時間最短。你分析一下，給出這個排隊的方法，假定有n個人，第i個同學(xué)打水所需要的時間為ti，并給出平均等待時間的計算公式。（注意：第i個同學(xué)的等待時間包含前i-1個的打水時間和+自己打水的時間ti）A、按照打水時間從小到大排隊，假定排隊后第i個人的打水時間是ti,平均等待時間T=∑(n-i+1)ti/n1<=i<=nB、按照打水時間從小到大排隊，平均等待時間T=∑ti/n1<=i<=nC、按照打水時間從大到小排隊，假定排隊后第i個人的打水時間是ti,平均等待時間T=∑(n-i+1)ti/n1<=i<=nD、按照打水時間從大到小排隊，平均等待時間T=∑ti/n1<=i<=n答案：A39.下面是優(yōu)先隊列式分支限界算法解0-1背包問題的部分主代碼，分析代碼將【】內(nèi)的代碼補(bǔ)齊。Templete<classTypew,classTypep>Typepknap<Typew,Typep>::MaxKnapsack(){//優(yōu)先隊列分支限界法，返回最大價值，最優(yōu)解bestxH=newMaxHeap<HeapNode<Typep,Typew>>(1000);//定義最大堆的容量為1000bestx=newint[n+1];inti=1;E=0;cw=cp=0;Typepbestp=0;Typepup=Bound(1）；while(【1】){Typewwt=cw+w[i];if(wt<=c){if(cp+p[i]>bestp)【2】；AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up=Bound(i+1);if(up>bestp)AddLiveNode(up,cp,cw,false,i+1);//從優(yōu)先隊列中取下一個擴(kuò)展節(jié)點(diǎn)HeapNode<Typep,Typew>N;H->DeleteMax(N);E=NNaNr;cw=N.weight;cp=N.profit;up=N.upprofit;i=N.level;}//構(gòu)造最優(yōu)解for（intj=n;j>0;j--）{bestx[j]=E->lchild;E=E->parent;}returncp;}A、【1】i<n+1,【2】besp=cp+p[i]B、【1】i!=n+1,【2】cw=cw+w[i]C、【1】i<n,【2】besp=cp+p[i]D、【1】i!=n,【2】cw=cw+w[i]答案：A40.使用快速排序方法對數(shù)組a［］=｛11,34,6,2,21,7,15,9,10,13｝升序排序，partition函數(shù)被調(diào)用（）次完成排序。A、5B、6C、7D、8答案：B41.在商品個數(shù)為n、背包容量為C的0-1背包問題中，蠻力枚舉算法和動態(tài)規(guī)劃算法的時間復(fù)雜度分別為（）A、O（n2），O（）B、O(2n)，O(n2)C、O（n2），O(n·C)D、O(2n)，O(n·C)答案：C42.游艇租賃問題：長江游艇俱樂部在長江上設(shè)置了n個游艇出租站1~n，游客可在這些游艇出租站租用游艇，并在下游的任何出租站歸還游艇，限制只能從上游往下游行進(jìn)，游艇出租站i到出租站j直達(dá)的租金為r(i,j)（1<=i<j<=n），計算從游艇出租站1到出租站n的最小費(fèi)用。該問題可有二種最優(yōu)解的結(jié)構(gòu)形式，如圖所示：如下描述中錯誤的是哪個？A、圖2方案的算法設(shè)計思路：設(shè)定二重循環(huán)：循環(huán)變量i（問題的終點(diǎn)站編號），循環(huán)變量k（斷點(diǎn)位置控制），去計算問題的最優(yōu)值.時間復(fù)雜性為O(）B、圖1是將從i站到j(luò)站最小費(fèi)用問題劃分為2個子問題i到k和k到j(luò)的最小費(fèi)用和，且i<k<j，這些不同方式中的最小值還要同r(i,j)比較，最小者即為cost(i,j)C、圖2是將從1站到i站的最小費(fèi)用問題劃分為2個子問題即從第1站到第k站的最小費(fèi)用問題和從k站到i站的最小費(fèi)用問題D、圖1方案的算法設(shè)計思路：設(shè)定三重循環(huán)：循環(huán)變量r（規(guī)?？刂疲?，循環(huán)遍歷i（規(guī)模為r的問題個數(shù)控制，同時也是問題的首編號），循環(huán)變量k（斷點(diǎn)位置控制），去計算問題的最優(yōu)值,時間復(fù)雜性為O（）答案：C43.下面描述不正確的是？A、當(dāng)解空間樹是子集樹時，約束函數(shù)對0分支剪枝，限界函數(shù)對1分支剪枝。B、剪枝函數(shù)有二種，分別是約束函數(shù)和限界函數(shù)C、對解空間樹是n叉樹（或排列樹）來說，回溯法搜索時對每個分支使用的的剪枝條件（函數(shù)）是完全相同的。D、解空間樹的分類中，盡管子集樹的每個非葉子結(jié)點(diǎn)都有二個分支，但是不能把它稱為n叉樹。答案：A44.在算法設(shè)計與分析過程中，有算法設(shè)計，算法的正確性證明，算法的復(fù)雜性分析,程序設(shè)計等幾個重要步驟，下面哪種順序是正確的?A、算法的正確性證明->算法設(shè)計->算法的復(fù)雜性分析->程序設(shè)計B、算法的正確性證明->算法的復(fù)雜性分析->算法設(shè)計->程序設(shè)計C、算法設(shè)計->算法的正確性證明->算法的復(fù)雜性分析->程序設(shè)計D、算法設(shè)計->算法的復(fù)雜性分析->算法的正確性證明->程序設(shè)計答案：C45.0-1背包問題：現(xiàn)有一背包容量c=5，n=4。4個物品分別為：(Wi,Vi)|(1,3),(3,6),(4,9),(2,7)。如下m表中m[i][j]是前i個物品裝背包容量為j時的最優(yōu)值。其中第四行的數(shù)據(jù)沒有填寫，分析問題，將第四行的數(shù)據(jù)從如下選項(xiàng)中找出。A、037101315B、037101013C、03771013D、0336815答案：B46.下面哪個算法在最壞情況下的時間復(fù)雜性最低A、歸并排序B、插入排序C、快速排序D、冒泡排序答案：A47.最長公共子序列問題：現(xiàn)有兩個字符序列X和Y,下面c矩陣和b矩陣是算法填寫出的信息表。c[i][j]是X序列的前i個字符和Y序列的前j個字符的最長公共子序列的長度，b[i][j]是輔助信息表。已知X=”ABC”?根據(jù)表格內(nèi)容，回答X和Y的最長公共子序列長度及最長公共子序列包含的符號A、長度1“C”B、長度1“A”C、長度2“AB”D、長度2“AC”答案：D48.給定兩個序列分別為“algorithm”和“glorhythm”。則以下分別為兩序列的最長公共子序列和最長公共子串的選項(xiàng)是A、thmgorthmB、glorhthmorthmC、orthmglorhthmD、gorthmthm答案：D49.5個不同元素組成二叉搜索樹可以畫出多少種不同形式A、140B、100C、80D、120答案：D50.回溯法的效率不依賴于以下哪一個因素（）A、產(chǎn)生x［KJ的時間；B、滿足顯約束的x［k］值的個數(shù)；C、問題的解空間的形式；D、計算上界函數(shù)bound的時間答案：C51.在隊列式分支限界法解決裝載問題時，為什么在其改進(jìn)算法中，每次進(jìn)入左分支都要檢查更新bestw，而不是等搜索到達(dá)葉子結(jié)點(diǎn)時才去更新bestw，其目的是什么？A、為了方便構(gòu)造最優(yōu)解B、為了計算最優(yōu)值C、為了及早使右（0）分支剪枝函數(shù)生效。D、為了及早使左（1）分支剪枝函數(shù)生效答案：C52.下面是求最長公共子序列長度和構(gòu)造最優(yōu)解的算法。【】中的語句缺失，請從如下選項(xiàng)中找到正確的答案補(bǔ)齊算法。A、(1)c[i][j]=c[i-1][j](2)c[i][j]=c[i][j-1](3)LCS(i-1,j,x,b)(4)LCS(i,j-1,x,b)B、(1)c[i][j]=c[i][j-1](2)c[i][j]=c[i-1][j](3)LCS(i,j-1,x,b)(4)LCS(i-1,j,x,b)C、(1)c[i][j]=c[i][j-1](2)c[i][j]=c[i-1][j](3)LCS(i-1,j,x,b)(4)LCS(i,j-1,x,b)D、(1)c[i][j]=c[i-1][j](2)c[i][j]=c[i][j-1](3)LCS(i,j-1,x,b)(4)LCS(i-1,j,x,b)答案：A53.將一個遞歸算法改造為非遞歸算法常用的數(shù)據(jù)結(jié)構(gòu)是?A、順序表B、鏈表C、棧D、隊列答案：C54.下列隨機(jī)算法中運(yùn)行時有時候成功有時候失敗的是A、蒙特卡羅算法B、數(shù)値概率算法C、舍伍德算法D、拉斯維加斯算法答案：D55.衡量一個算法好壞的標(biāo)準(zhǔn)是（）。A、時間復(fù)雜度低B、運(yùn)行速度快C、代碼短D、占用空間少答案：A56.n皇后問題是可用回溯法解決的問題。下面描述不正確的是？A、算法搜索至葉子結(jié)點(diǎn)時，就找到了一種新的皇后安排方案，算法可找到所有可行的方案。B、當(dāng)其解空間樹是n叉樹時，剪枝函數(shù)是任一列或任一（正反）對角線只能安排一個皇后。C、兩種不同解空間樹的算法效率比較，排列樹的時間耗費(fèi)高于n叉樹D、當(dāng)其解空間樹是排列樹時，剪枝函數(shù)是任一（正反）對角線只能安排一個皇后。答案：C57.0-1背包問題的回溯算法，下面的解釋不正確的是A、當(dāng)搜索至葉子結(jié)點(diǎn)時，一定是發(fā)現(xiàn)了到目前為止最好的解B、左(1)分支的剪枝：當(dāng)選擇裝入背包的物品重量之和超過背包容量時就剪枝。C、右（0）分支的剪枝：已裝入背包內(nèi)的物品價值和+剩余物品裝剩余背包容量所能獲得的最大價值（物品可分割，即用背包問題的貪心算法求得的最大價值）>當(dāng)前最優(yōu)值bestp,就剪枝.D、解空間樹是子集樹答案：C58.分治法解決問題分為三步走，即分、治、合。下面列出了幾種操作，請按分、治、合順序選擇正確的表述。(1)將各個子問題的解合并為原問題的解(2)將問題分解為各自獨(dú)立的多個子問題，(3)將多個子問題合并為原問題。(4)求各個子問題的解，(5)將問題分解為可重復(fù)的多個子問題。A、(5)(4)(1)B、(2)(4)(1)C、(2)(1)(3)D、(5)(1)(3)答案：B59.下面不是分支界限法搜索方式的是A、最大效益優(yōu)先B、深度優(yōu)先C、最小耗費(fèi)優(yōu)先D、廣度優(yōu)先答案：B60.回溯法解旅行售貨員問題時的解空間樹是（）A、深度優(yōu)先生成樹B、廣度優(yōu)先生成樹C、子集樹D、排列樹答案：D61.已知斐波那契數(shù)列中第n個斐波那契數(shù)F(n)=F(n-1)+F(n-2),問能不能使用分治策略求第n個斐波那契數(shù)，從下面選項(xiàng)中選取答案。A、能，因?yàn)樗鼭M足分治法的四個適應(yīng)條件B、能，因?yàn)樗梢杂梅?、治、合三個步驟完成計算C、不能，因?yàn)樗粷M足分治法的第四個適應(yīng)條件(子問題是相互獨(dú)立的，也就是沒有重復(fù)子問題)D、不能，因?yàn)樗豢梢杂梅?、治、合三個步驟完成計算答案：C62.動態(tài)規(guī)劃算法的基本要素為（）A、最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B、重疊子問題性質(zhì)與貪心選擇性質(zhì)C、最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D、預(yù)排序與遞歸調(diào)用答案：C63.有5個物品，重量數(shù)組是w[]={3,5,2,6,4}，背包容量10，每個物品不可分割，背包最多裝多少個物品？A、3B、5C、2D、4答案：A64.哈夫曼編碼樹是用貪心算法解決的典型問題，分析該算法，回答如下問題，假定有n（n>1)個字符生成的編碼樹，問編碼樹中的結(jié)點(diǎn)總數(shù)是多少？可能的最長的字符編碼是多少位？A、2n-1個結(jié)點(diǎn)n-1位編碼B、2n個結(jié)點(diǎn)n-1編碼C、2n個結(jié)點(diǎn)，n位編碼D、2n-1個結(jié)點(diǎn)n位編碼答案：A65.實(shí)現(xiàn)合并排序利用的算法是（）A、回溯法B、動態(tài)規(guī)劃法C、分治策略D、貪心法答案：C66.二分搜索算法是利用（）實(shí)現(xiàn)的算法A、貪心法B、動態(tài)規(guī)劃法C、回溯法D、分支策略答案：D67.給定n個可能含有重復(fù)的元素存放于x[1:n]，輸出去掉重復(fù)的全排列，這里swap是實(shí)現(xiàn)兩個變量值的交換，下面是算法描述??注意：紅色代碼部分【1】【2】【3】位置有代碼缺失。????voidbacktrack(intt)??{??if(t>n){??for(inti=1;i<=n;i++)??printf("%d",x[i]);??printf("\n");??}??else{??for(inti=t;i<=n;i++){??intok=1;??for(intj=【1】;j<【2】;j++)??if(x[j]==x[i])｛【3】;break；｝??if(ok)??{??swap(x[t],x[i]);??backtrack(t+1);??swap(x[t],x[i]);??}??}????}??}???上面的算法中，紅色代碼部分【1】【2】【3】位置代碼缺失，請從如下選項(xiàng)中找到合適的代碼。A、【1】t，【2】i，【3】ok=0B、【1】t，【2】i，【3】ok=1C、【1】i，【2】t，【3】ok=1D、【1】i，【2】t，【3】ok=0答案：A68.下圖中A~F頂點(diǎn)分別代表6個村莊，圖中的邊代表村莊之間的距離，為了滿足這六個村莊相互通信的需要（任意兩個村莊有線路可達(dá)），需要架設(shè)通信線路，這里要求代價最小化（即線路總長度最小），請你分析問題找到代價最小的方案，并計算出線路總長度，從如下選項(xiàng)中找出答案。A、線路總長度21B、線路總長度22C、線路總長度20D、線路總長度23答案：A69.凸多邊形的三角剖分問題。用動態(tài)規(guī)劃算法求解最優(yōu)三角剖分，首先要分析最優(yōu)解的結(jié)構(gòu)，也就是將問題分解為子問題，并具有最優(yōu)子結(jié)構(gòu)性質(zhì)。下圖是一凸6邊形(ABCDEF)的二種不同劃分為子問題的方法，哪種是正確的將問題劃分為子問題的方案？正確的劃分方案共有幾種不同方式？A、右圖正確，9種B、左圖正確，14種C、右圖正確，14種D、左圖正確，9種答案：B70.當(dāng)所給問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應(yīng)的解空間樹稱為（）A、子集樹B、排列樹C、二叉樹D、平衡樹答案：A71.符號三角形問題，其解空間樹是哪種？A、不規(guī)則樹B、子集樹C、n叉樹（這里n=2）D、排列樹答案：C72.哈夫曼編碼樹算法中用優(yōu)先隊列（堆）存儲生成的結(jié)點(diǎn)，n個字符的哈夫曼編碼樹算法時間復(fù)雜性為A、O(nlogn)B、O(n2)C、O(n2n)D、O(n)答案：A73.分支限界法解0/1背包問題時，優(yōu)先級隊列的組織形式是（）A、循環(huán)隊列B、棧C、小根堆D、大根堆答案：D74.分支限界法與回溯法的不同點(diǎn)體現(xiàn)在哪些方面？（1）求解目標(biāo)不同，分支限界法可求最優(yōu)解或滿足條件的一個解，而回溯法可求最優(yōu)解或滿足條件的所有解?（2）搜索方式不同，回溯法是以深度優(yōu)先狀態(tài)生成樹法搜索解空間樹，分支限界法則以廣度優(yōu)先或最小耗費(fèi)（最大效益）優(yōu)先的狀態(tài)生成樹法搜索解空間樹。?（3）同一個問題在使用回溯法或分支限界法時，該問題的解空間樹的結(jié)構(gòu)不同?（4）回溯法與分支限界法，構(gòu)造最優(yōu)解的方式不同。?從上述選項(xiàng)中找出答案。A、（1）（2）（3）B、（1）（3）（4）C、（1）（2）（4）D、（2）（3）（4）答案：C75.X=1a,b.c,a,d,c,a,dy=（b.b,a,d,c,a.b的最長公類子厚列的長展是（）A、3B、4C、5D、6答案：C76.下面關(guān)于NP問題說法正確的是A、NP類問題包含在P類問題中B、P類問題包含在NP類問題中C、NP問題都是不可能解決的問題D、NP完全問題是P類問題的子集答案：B77.有這樣一種算法，運(yùn)行一次一定能找到問題的解，有時不知其是否正確，可以確定的是該解高概率（大于50%）是正確的。這種算法是？A、蒙特卡洛算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法答案：A78.FIFO是（）的搜索方式。A、分支限界B、動態(tài)規(guī)劃C、回溯算法D、貪心算法答案：A判斷題1.回溯法的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。（）A、正確B、錯誤答案：A2.在隊列式分支限界法解決裝載問題時，在隊列中加入一個-1標(biāo)志，該標(biāo)志所起的作用是表示其后的活結(jié)點(diǎn)在解空間樹中的層數(shù)比-1之前的活結(jié)點(diǎn)更深一層，或者說是同層活結(jié)點(diǎn)的結(jié)束標(biāo)志。A、正確B、錯誤答案：A3.改進(jìn)子問題合并的時間復(fù)雜度可以減少分治算法的時間。（）A、正確B、錯誤答案：A4.Dijkstra算法在求解過程中，源點(diǎn)到集合S內(nèi)各頂點(diǎn)的最短路徑一旦求出，則之后不變了，修改的僅僅是源點(diǎn)到還沒選擇的頂點(diǎn)的最短路徑長度。（）A、正確B、錯誤答案：A5.遞歸程序代碼簡短，結(jié)構(gòu)清晰，易讀性強(qiáng)，相比解決同一問題的非遞歸程序，遞歸程序運(yùn)行時間短。A、正確B、錯誤答案：B6.一個人正站在門口，讓你猜他（她）是否要出門，該問題是不可判定問題，該觀點(diǎn)是否正確？A、正確B、錯誤答案：A7.回溯法使用約束函數(shù)剪去得不到最優(yōu)解的子樹以避免無效搜索。（）A、正確B、錯誤答案：A8.優(yōu)先隊列式分支限界法按照優(yōu)先隊列中規(guī)定的優(yōu)先級，選取優(yōu)先級最高的結(jié)點(diǎn)，成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。（）A、正確B、錯誤答案：A9.如果一個最優(yōu)化問題具備貪心選繹性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，則可以用貪心算法找到問題所有最優(yōu)解。（）A、正確B、錯誤答案：B10.研究NPC問題的意義，一旦一個NPC問題找到了多項(xiàng)式時間復(fù)雜性的確定性算法，那么所有的NPC問題都找到了多項(xiàng)式時間復(fù)雜性的確定性算法。A、正確B、錯誤答案：A11.回溯法搜索解空間時，在搜索試探時選取x[i]的值順序是任意的，順序?qū)τ谟嬎懔繘]有差別。（）A、正確B、錯誤答案：B12.回溯法中，剪枝函數(shù)能夠剪掉的分支越多，算法效率就越高。因此，我們在設(shè)計回溯法時，就要設(shè)計剪枝函數(shù)能夠剪掉盡量多的分支。A、正確B、錯誤答案：B13.備忘錄方法是自頂向下，動態(tài)規(guī)劃方法是自底向上。（）A、正確B、錯誤答案：A14.把大規(guī)模的問題分解成相同子問題，目的是為了在解決子問題時遞歸調(diào)用原問題的算法。（）A、正確B、錯誤答案：A15.0-1背包問題和背包問題的區(qū)別在于物品是否能夠分割，他們都可以使用動態(tài)規(guī)劃方法求解。（）A、正確B、錯誤答案：B16.自然語言、偽代碼都可以描述算法，而流程圖不能描述算法A、正確B、錯誤答案：B17.貪心算法是以自底向上的方式構(gòu)造問題的最優(yōu)解A、正確B、錯誤答案：B18.貪心和遞推算法是線性解決問題，動態(tài)規(guī)劃則是全面分階段地解決問題。（）A、正確B、錯誤答案：A19.回溯法不適用于解一些組合數(shù)相當(dāng)大的問題。（）A、正確B、錯誤答案：A20.回溯法在0-1背包問題的解空間樹的每個內(nèi)結(jié)點(diǎn)都要同時檢直約束函數(shù)和限界函數(shù)。（）A、正確B、錯誤答案：B21.分支界限法采用深度優(yōu)先策略搜索。（）A、正確B、錯誤答案：B22.一個問題，可能有多個最優(yōu)解，但是使用貪心算法最多只能找到一個最優(yōu)解。A、正確B、錯誤答案：A23.分治法解決問題時，平衡子問題思想是指:當(dāng)問題劃分出的子問題規(guī)?；疽恢聲r，算法計算效率高A、正確B、錯誤答案：A24.支限限界法不能解決0/1背包問題。（）A、正確B、錯誤答案：B25.使用動態(tài)規(guī)劃算法和貪心算法的共同點(diǎn)是，問題都必須具備最優(yōu)子結(jié)構(gòu)性質(zhì)。（）A、正確B、錯誤答案：A26.學(xué)習(xí)主定理和遞歸樹等求解遞歸方程方法，主要目的是解決求遞歸算法的時間復(fù)雜性問題A、正確B、錯誤答案：A27.計算機(jī)中的隨機(jī)數(shù)是偽隨機(jī)的，因?yàn)樗蔷哂幸欢ㄒ?guī)律的，是按公式計算出來的。該說法正確嗎？A、正確B、錯誤答案：A28.解決旅行商問題，采用的是優(yōu)先隊列式分支限界法。（）A、正確B、錯誤答案：A29.素數(shù)測試問題的蒙特卡洛算法，n是一個待判定正整數(shù)。當(dāng)n是素數(shù)時，有時會被判定為非素數(shù)。該說法正確嗎??A、正確B、錯誤答案：B30.解決同一個問題的算法策略可能有多個，使用不同算法策略設(shè)計的算法，其算法時間復(fù)雜性可能有顯著差異。A、正確B、錯誤答案：A31.隊列式分支限界法按照隊列中結(jié)點(diǎn)的優(yōu)先級選取優(yōu)先級最高的一個結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。（）A、正確B、錯誤答案：A32.分支限界按廣度優(yōu)先的原則進(jìn)行搜索，每一活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn)。（）A、正確B、錯誤答案：A33.教材例題：多機(jī)調(diào)度問題，是用貪心算法求最優(yōu)解的一個例子，貪心策略是每次從剩余任務(wù)中選擇一個花費(fèi)時間最長的任務(wù)，安排在占用時間最少的機(jī)器上。A、正確B、錯誤答案：B34.剪枝函數(shù)設(shè)計的越好，剩下的結(jié)點(diǎn)數(shù)越少，回溯算法效率越高。（）A、正確B、錯誤答案：A35.回溯法與分支限界法的空間復(fù)雜度是相同的，都是O(h(n)),h(n)是解空間樹的深度。A、正確B、錯誤答案：B36.一個NPC問題，首先是NP問題，另外所有的其他NP問題都能在多項(xiàng)式時間復(fù)雜性規(guī)約為該問題A、正確B、錯誤答案：A37.分治算法的思想是將難以直接解決的大問題，分割成一些規(guī)模較小的子問題，以便各個擊破，分而治之。（）A、正確B、錯誤答案：A填空題1.操場上擺放一行共4堆石頭，從左到右方向編號為1~4，各堆石子的數(shù)目分別為7,10,3,5，現(xiàn)要將石子有次序的合并為一堆，規(guī)定每次只能選相鄰的2堆合并為新的一堆，將新的一堆石子數(shù)記為該次合并的得分，經(jīng)過5次合并，最終合并為一堆。計算這6堆石子合并為一堆的最小得分答案：502.使用回溯法進(jìn)行狀態(tài)空間樹裁剪分支時一般有兩個標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是（），只使用約束條件進(jìn)行裁剪的是（）。答案：0/1背包問題|N皇后問題3.回溯法的算法框架按照問題的解空間一般分為[填空1]算法框架與[填空2]算法框架。答案：子集樹|排列樹4.答案：n5.下面是優(yōu)先隊列式分支限界算法解裝載問題（n個集裝箱裝船）的部分代碼，分析下面代碼答案：r[i-1]6.算法分析中，記號O表示_______，記號Ω表示_______。答案：漸進(jìn)上界|漸進(jìn)下界7.快速排序算法是基于的一種排序算法答案：分治策略解析：分治策略;分治;分治法;分治算法8.下面是優(yōu)先隊列式分支限界算法解裝載問題（n個集裝箱裝船）的部分代碼，分析下面代碼答案：n+1;1+n9.答案：310.答案：A|33|1|2|3|511.答案：A|1|4|7|812.對如下所示連通無向圖G=<V,E,W>，其最小生成樹的權(quán)重為______________-。答案：2313.根據(jù)題中數(shù)據(jù)構(gòu)造哈夫曼樹如下圖所示。由此可以得出相應(yīng)的最優(yōu)編碼a___________，b___________,c___________,d___________,e___________,f___________的一組最優(yōu)的編碼：答案：01|0000|00010|00011|1|00114.分支限界法主要有（）分支限界法和（）分支限界法。答案：隊列式|優(yōu)先隊列式15.下面是一個布線問題,S表示布線的起點(diǎn)，O表示布線的終點(diǎn)，假定布線只能垂直、或水平布線，從一個點(diǎn)按照上、下、左、右的優(yōu)先順序可往四個方向布線，“#"是障礙不能通過。已知從一個位置向其上、下、左、右四個相鄰位置布線的線路長度為1。使用隊列式分支限界法解決該問題，問從S到O的最短布線長度？答案：816.整數(shù)因子分解問題：大于1的正整數(shù)n可以分解為n=x1*x2*…xm。如n=12時有如下形式12=1212=6*212=4*312=3*412=3*2*212=2*612=2*3*212=2*2*38種形式求正整數(shù)n共有多少種分解形式，函數(shù)p(intn)返回值為問題的答案，代碼如下：?代碼中【1】【2】處代碼缺失，請補(bǔ)齊【1】的代碼答案：n==1;1==n17.有11個待安排的活動，它們具有下表所示的開始時間與結(jié)束時間，如果以貪心算法求解這些活動的最優(yōu)安排（即為活動安排問題：在所給的活動集合中選出最大的相容活動子集合）：（格式：以英文輸入法逗號分割，如：1,2,3,4）答案：1,4,8,1118.答案：A|A|C|B19.圖的m著色問題可用回溯法求解，其解空間樹中葉子結(jié)點(diǎn)個數(shù)是填空1，解空間樹中每個內(nèi)結(jié)點(diǎn)的孩子數(shù)是填空2。答案：m^n|m20.答案：n^2|n^221.在0-1背包問題中，若背包容量為20,5個物品的體積分別為c=[15,10,2,5,8]，價格分別為p=[16,10,6,7,9]。則該背包能容納物品的最大總價格為___填空1____答案：2522.答案：A|V1V5V3V6V7|223.Prim算法利用策略求解最小生成樹問題，其時間