計(jì)算機(jī)算法設(shè)計(jì)與分析習(xí)題及答案

1、百度文庫(kù)10計(jì)算機(jī)算法設(shè)計(jì)與分析習(xí)題及答案選擇題1、二分搜索算法是利用（/A）實(shí)現(xiàn)的算法。A分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法2、下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（A）。A找出最優(yōu)解的性質(zhì)3、最大效益優(yōu)先是（A分支界限法B、構(gòu)造最優(yōu)解A）的一搜索方式。B、動(dòng)態(tài)規(guī)劃法4.回溯法解旅行售貨員問(wèn)題時(shí)的解空間樹是（A子集樹B、排列樹C、深度優(yōu)先生成樹5.下列算法中通常以自底向上的方式求解最優(yōu)解的是（A備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法6、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（C）。A運(yùn)行速度快B占用空間少C時(shí)間復(fù)雜度低D7、以下不可以使用分治法求解的是（D）。A棋盤覆蓋問(wèn)題B選擇問(wèn)題C歸并排序D0/18 .實(shí)現(xiàn)循環(huán)賽

2、日程表利用的算法是（A分治策略B、動(dòng)態(tài)規(guī)劃法C9 .下面不是分支界限法搜索方式的是（A、廣度優(yōu)先B、最小耗費(fèi)優(yōu)先A）。、貪心法D算出最優(yōu)解D、定義最優(yōu)解C、貪心法、D、回溯法、廣度優(yōu)先生成樹B）。、回溯法代碼短背包問(wèn)題D、回溯法）。C、最大效益優(yōu)先D、深度優(yōu)先10.下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的是（A備忘錄法B、動(dòng)態(tài)規(guī)劃法11.備忘錄方法是那種算法的變形。A分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法（B）C、貪心法D）。、回溯法12.哈夫曼編碼的貪心算法所需的計(jì)算時(shí)間為（AO（n2n）B、O（nlogn）C、O（2n）13.二分支限界法解最大團(tuán)問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是（A最小堆B、最大堆

3、C、棧D、數(shù)組、回溯法）。、O（n）B14 .最長(zhǎng)公共子序列算法利用的算法是（A分支界限法B、動(dòng)態(tài)規(guī)劃法15 .實(shí)現(xiàn)棋盤覆蓋算法利用的算法是（A分治法B、動(dòng)態(tài)規(guī)劃法C16 .下面是貪心算法的基本要素的是（A重疊子問(wèn)題B、構(gòu)造最優(yōu)解17 .回溯法的效率不依賴于下列哪些因素BC、貪心法A）。、貪心法C、回溯法回溯法C、貪心選擇性質(zhì)D）D、定義最優(yōu)解A.滿足顯約束的值的個(gè)數(shù)C.計(jì)算限界函數(shù)的時(shí)間B.D.計(jì)算約束函數(shù)的時(shí)間確定解空間的時(shí)間18 .下面哪種函數(shù)是回溯法中為避免無(wú)效搜索采取的策略（A.遞歸函數(shù)B.剪枝函數(shù)C。隨機(jī)數(shù)函數(shù)D.19 .（D）是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)。B）搜索函數(shù)A、重疊

4、子問(wèn)題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、最優(yōu)子結(jié)構(gòu)性質(zhì)20 .矩陣連乘問(wèn)題的算法可由（B）設(shè)計(jì)實(shí)現(xiàn)。A分支界限算法B、動(dòng)態(tài)規(guī)劃算法C、貪心算法D、回溯算法21 .分支限界法解旅行售貨員問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是（A）。A最小堆B、最大堆C、棧D、數(shù)組22、Strassen矩陣乘法是利用（A）實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法23、使用分治法求解不需要滿足的條件是（A）°A子問(wèn)題必須是一樣的B子問(wèn)題不能夠重復(fù)C子問(wèn)題的解可以合并D原問(wèn)題和子問(wèn)題使用相同的方法解24、下面問(wèn)題（B）不能使用貪心法解決。、A單源最短路徑問(wèn)題BN皇后問(wèn)題C最小生成樹問(wèn)題D背包問(wèn)題25

5、、下列算法中不能解決0/1背包問(wèn)題的是（A）A貪心法B動(dòng)態(tài)規(guī)劃C回溯法D分支限界法'26、回溯法搜索狀態(tài)空間樹是按照（C）的順序。A中序遍歷B廣度優(yōu)先遍歷C深度優(yōu)先遍歷D層次優(yōu)先遍歷27 .實(shí)現(xiàn)合并排序利用的算法是（A）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法28 .下列是動(dòng)態(tài)規(guī)劃算法基本要素的是（D）。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子問(wèn)題重疊性質(zhì)29 .下列算法中通常以自底向下的方式求解最優(yōu)解的是（B）。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法30 .采用廣度優(yōu)先策略搜索的算法是（A）。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法31、合并排序算法是利

6、用（A）實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法32、背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為（B）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）33 .實(shí)現(xiàn)大整數(shù)的乘法是利用的算法（C）。A、貪心法B、動(dòng)態(tài)規(guī)劃法C、分治策略D、回溯法34 .0-1背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為（A）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）35 .采用最大效益優(yōu)先搜索方式的算法是（A）。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法36 .貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是（B）。/A、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì)C、構(gòu)造最優(yōu)解D、定義最優(yōu)解37 .實(shí)現(xiàn)最

7、大子段和利用的算法是（B）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法/38 .優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是（C）。A、先進(jìn)先出B、后進(jìn)先出C、結(jié)點(diǎn)的優(yōu)先級(jí)D、隨機(jī)39 .背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為（B）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）40、廣度優(yōu)先是（A）的一搜索方式。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法.重疊子問(wèn)題性質(zhì)與貪心選擇性質(zhì)41 .一個(gè)問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問(wèn)題的（B）。A、重疊子問(wèn)題B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解42 .采用貪心算法的最優(yōu)裝載問(wèn)題的主要計(jì)算量在于將集裝箱依

8、其重量從小到大排序,故算法的時(shí)間復(fù)雜度為（B）。AO（n2n）B、O（nlogn）C、O（2n）D、O（n）43 .以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱為（D）。A分支界限算法B、概率算法C、貪心算法、D、回溯算法44 .實(shí)現(xiàn)最長(zhǎng)公共子序列利用的算法是（B）。A、分治策略/'B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法45 .Hanoi塔問(wèn)題如下圖所示。現(xiàn)要求將塔座A上的的所有圓盤移到塔座B上，并仍按同樣順序疊置。移動(dòng)圓盤時(shí)遵守Hanoi塔問(wèn)題的移動(dòng)規(guī)則。由此設(shè)計(jì)出解Hanoi塔問(wèn)題的遞歸算乎正確的為：(B)/A.voidhanoi(intn,intA,intC,intB)if(n>0)h

9、anoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);B. voidhanoi(intn,intA,intB,intC)if(n>0)hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);C. voidhanoi(intn,intC,intB,intA)if(n>0)hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);D. voidhanoi(intn,intC,intA,intB)if(n>0)hanoi(n-1,A,C,B);move(n,a,b);hanoi

10、(n-1,C,B,A);46.動(dòng)態(tài)規(guī)劃算法的基本要素為（C、）A.最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)BC.最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問(wèn)題性質(zhì)D.預(yù)排序與遞歸調(diào)用47 .能采用貪心算法求最優(yōu)解的問(wèn)題，一般具有的重要性質(zhì)為：（A）A.最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B.重疊子問(wèn)題性質(zhì)與貪心選擇性質(zhì)C.最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問(wèn)題性質(zhì)/D.預(yù)排序與遞歸調(diào)用48 .回溯法在問(wèn)題的解空間樹中，按（D'）策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。A.廣度優(yōu)先B.活結(jié)點(diǎn)優(yōu)先/C.擴(kuò)展結(jié)點(diǎn)優(yōu)先D.深度優(yōu)先49 .分支限界法在問(wèn)題的解空間樹中，按（A）策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。A.廣度優(yōu)先B.活結(jié)點(diǎn)優(yōu)先C.擴(kuò)展結(jié)點(diǎn)優(yōu)先、D

11、.深度優(yōu)先50 .程序塊（A-）是回溯法中遍歷排列樹的算法框架程序。、A.B.C.D.voidbacktrack(intt)if(t>n)output(x);elsefor(inti=t;i<=n;i+)swap(xt,xi);if(legal(t)backtrack(t+1);swap(xt,xi);voidbacktrack(intt)if(t>n)output(x);elsefor(inti=0;i<=1;i+)xt=i;if(legal(t)backtrack(t+1);Voidbacktrack(intt)if(t>n)output(x);elsefor

12、(inti=0;i<=1;i+)xt=i;if(legal(t)backtrack(t-1);voidbacktrack(intt)if(t>n)output(x);elsefor(inti=t;i<=n;i+)swap(xt,xi);if(legal(t)backtrack(t+1);51.常見的兩種分支限界法為（D）A.廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B.隊(duì)列式（FIFO）分支限界法與堆棧式分支限界法；C.排列樹法與子集樹法；/D.隊(duì)列式（FIFO）分支限界法與優(yōu)先隊(duì)列式分支限界法；二、填空題1.算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分。2、程序是算法用某種程序設(shè)

13、計(jì)語(yǔ)言的具體實(shí)現(xiàn)。3、算法的“確定性”指的是組成算法的每條指令是清晰的,無(wú)歧義的。/4.矩陣連乘問(wèn)題的算法可由動(dòng)態(tài)規(guī)劃設(shè)計(jì)實(shí)現(xiàn)。、5、算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。6、從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是遞歸算法。7、問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。8、以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱為回溯法。9、計(jì)算一個(gè)算法時(shí)間復(fù)雜度通?？梢杂?jì)算循環(huán)次數(shù)、基本操作的頻率或計(jì)算步。'10、解決0/1背包問(wèn)題可以使用動(dòng)態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是動(dòng)態(tài)規(guī)劃，需要排序的是回溯法,分支限界法。11、使用回溯法進(jìn)行狀態(tài)空間樹裁

14、剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問(wèn)題和0/1背包問(wèn)題正好是兩種不同的類型，其中同時(shí)使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是0/1背包問(wèn)題,只使用約束條件進(jìn)行裁剪的是N皇后問(wèn)題。12、貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素,也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。13、矩陣連乘問(wèn)題的算法可由動(dòng)態(tài)規(guī)劃設(shè)計(jì)實(shí)現(xiàn)。14.貪心算法的基本要素是貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。15.動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干子問(wèn)題，先求解子問(wèn)題,然后從這些子問(wèn)題的解得到原問(wèn)題的解。16.算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和有限性四條性質(zhì)。17、大整數(shù)乘積算法

15、是用分治法來(lái)設(shè)計(jì)的。/18、以廣度優(yōu)先或以最小耗費(fèi)方式搜索問(wèn)題解的算法稱為分支限界法。/19 、貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素,也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。20 .快速排序算法是基于分治策略的一種排序算法。21 .動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是.最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問(wèn)題性質(zhì)。22 .回溯法是一種既帶有、系統(tǒng)性又帶有跳躍性的搜索算法。23 .分支限界法主要有隊(duì)列式（FIFO）分支限界法和優(yōu)先隊(duì)列式分支限界法。24 .分支限界法是一種既帶有系統(tǒng)性又帶有/跳躍性的搜索算法。25 .回溯法搜索解空間樹時(shí)，常用的兩種剪枝函數(shù)為約束函數(shù)和限界函數(shù)。26 .任何可用計(jì)算機(jī)求解的問(wèn)題所需

16、的時(shí)間都與其規(guī)模有關(guān)。27 .快速排序算法的性能取決于劃分的對(duì)稱性。28 .所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。29 .所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解。30 .回溯法是指具有限界函數(shù)的深度優(yōu)先生成法。31 .用回溯法解題的一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h(n),則回溯法所需的計(jì)算空間通常為O(h(n)。32 .回溯法的算法框架按照問(wèn)題的解空間一般分為子集樹算法框架與排列樹算法框架。33 .用回溯法解，

17、0/1背包問(wèn)題時(shí)，該問(wèn)題的解空間結(jié)構(gòu)為子集樹結(jié)構(gòu)。34 .用回溯法解批處理作業(yè)調(diào)度問(wèn)題時(shí)，該問(wèn)題的解空間結(jié)構(gòu)為排列樹結(jié)構(gòu)。35 .旅行售貨員問(wèn)題的解空間樹是排列樹。三、算法填空1 .背包問(wèn)題的貪心算法voidKnapsack(intn,floatM,floatv,floatw,floatx口)n,價(jià)值為v1.n的n個(gè)物品，裝入容量為M的背包ninti;Sort(n,v,w);for(i=1;i<=n;i+)xi=0;floatc=M;for(i=1;i<=n;i+)if(wi>c)break;xi=1;c-=wiif(i<=n)xi=c/wi;2.最大子段和：動(dòng)態(tài)規(guī)劃算

18、法intMaxSum(intn,inta)intsum=0,b=0;心算法求活動(dòng)安排問(wèn)題template<classType>voidGreedySelector(intn,Types,Typef,boolA口)A1=true;intj=1;for(inti=2;i<=n;i+)if(si>=fj)/Ai=true;/j=i；/elseAi=false;4.快速排序template<classType>voidQuicksort(Typea口，intp,intr)if(p<r)intq=Partition(a,p,r);/Quicksort(a,p,q-1);回溯法解迷宮問(wèn)題迷宮用二維數(shù)組存儲(chǔ)，用'H'表示墻,'O&#