算法復(fù)習(xí)題1總結(jié)

1、二分搜索算法是利用（

A

）實(shí)現(xiàn)的算法。A、分治策略

B、動(dòng)態(tài)規(guī)劃法

C、貪心法

D、回溯法2、下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（

B

）。A、找出最優(yōu)解的性質(zhì)

B、構(gòu)造最優(yōu)解

C、算出最優(yōu)解

D、定義最優(yōu)解3、最大效益優(yōu)先是（

A

）的一搜索方式。A、分支界限法

B、動(dòng)態(tài)規(guī)劃法

C、貪心法

D、回溯法4、在下列算法中有時(shí)找不到問(wèn)題解的是（

B

）。A、蒙特卡羅算法

B、拉斯維加斯算法

C、舍伍德算法

D、數(shù)值概率算法5.回溯法解旅行售貨員問(wèn)題時(shí)的解空間樹(shù)是（

B

）。A、子集樹(shù) B、排列樹(shù) C、深度優(yōu)先生成樹(shù) D、廣度優(yōu)先生成樹(shù)6．下列算法中通常以自底向上的方式求解最優(yōu)解的是（

B

）。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法7、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（C）。

A運(yùn)行速度快B占用空間少C時(shí)間復(fù)雜度低D代碼短

8、以下不可以使用分治法求解的是（D）。

A棋盤(pán)覆蓋問(wèn)題B選擇問(wèn)題C歸并排序D0/1背包問(wèn)題

9.實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（

A

）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法10、下列隨機(jī)算法中運(yùn)行時(shí)有時(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)先方式系統(tǒng)搜索問(wèn)題解的是（

D

）。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法13.備忘錄方法是那種算法的變形。（B）A、分治法 B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法14．哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為（

B

）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）15．分支限界法解最大團(tuán)問(wèn)題時(shí)，活結(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)棋盤(pán)覆蓋算法利用的算法是（

A

）。A、分治法 B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法18.下面是貪心算法的基本要素的是（

C

）。A、重疊子問(wèn)題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì) D、定義最優(yōu)解19.回溯法的效率不依賴于下列哪些因素（D）A.滿足顯約束的值的個(gè)數(shù) B.計(jì)算約束函數(shù)的時(shí)間C.計(jì)算限界函數(shù)的時(shí)間 D.確定解空間的時(shí)間20.下面哪種函數(shù)是回溯法中為避免無(wú)效搜索采取的策略（

B

）A．遞歸函數(shù) B.剪枝函數(shù) C。隨機(jī)數(shù)函數(shù) D.搜索函數(shù)21、下面關(guān)于NP問(wèn)題說(shuō)法正確的是（B）

ANP問(wèn)題都是不可能解決的問(wèn)題BP類(lèi)問(wèn)題包含在NP類(lèi)問(wèn)題中

CNP完全問(wèn)題是P類(lèi)問(wèn)題的子集DNP類(lèi)問(wèn)題包含在P類(lèi)問(wèn)題中22、蒙特卡羅算法是（

B

）的一種。A、分支界限算法

B、概率算法

C、貪心算法

D、回溯算法23.下列哪一種算法不是隨機(jī)化算法（

C

）A.蒙特卡羅算法B.拉斯維加斯算法C.動(dòng)態(tài)規(guī)劃算法D.舍伍德算法24.（

D

）是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)。A、重疊子問(wèn)題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì) D、最優(yōu)子結(jié)構(gòu)性質(zhì)25.矩陣連乘問(wèn)題的算法可由（

B）設(shè)計(jì)實(shí)現(xiàn)。A、分支界限算法

B、動(dòng)態(tài)規(guī)劃算法

C、貪心算法

D、回溯算法26.分支限界法解旅行售貨員問(wèn)題時(shí)，活結(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子問(wèn)題必須是一樣的B子問(wèn)題不能夠重復(fù)C子問(wèn)題的解可以合并D原問(wèn)題和子問(wèn)題使用相同的方法解

30、下面問(wèn)題（B）不能使用貪心法解決。

A單源最短路徑問(wèn)題BN皇后問(wèn)題C最小花費(fèi)生成樹(shù)問(wèn)題D背包問(wèn)題

31、下列算法中不能解決0/1背包問(wèn)題的是（A）

A貪心法B動(dòng)態(tài)規(guī)劃C回溯法D分支限界法

32、回溯法搜索狀態(tài)空間樹(shù)是按照（C）的順序。

A中序遍歷B廣度優(yōu)先遍歷C深度優(yōu)先遍歷D層次優(yōu)先遍歷33、下列隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是（C）

A數(shù)值概率算法B舍伍德算法C拉斯維加斯算法D蒙特卡羅算法

34．實(shí)現(xiàn)合并排序利用的算法是（

A

）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法35．下列是動(dòng)態(tài)規(guī)劃算法基本要素的是（

D

）。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子問(wèn)題重疊性質(zhì)36．下列算法中通常以自底向上的方式求解最優(yōu)解的是（

B

）。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法37．采用廣度優(yōu)先策略搜索的算法是（

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、蒙特卡羅算法

B、拉斯維加斯算法

C、舍伍德算法

D、數(shù)值概率算法40、背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為（

B

）A、O（n2n）

B、O（nlogn）

C、O（2n）

D、O（n）41．實(shí)現(xiàn)大整數(shù)的乘法是利用的算法（

C

）。A、貪心法B、動(dòng)態(tài)規(guī)劃法C、分治策略D、回溯法42．0-1背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為（

A

）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）43．采用最大效益優(yōu)先搜索方式的算法是（

A

）。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法44．貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是（

B

）。A、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì) C、構(gòu)造最優(yōu)解D、定義最優(yōu)解45.實(shí)現(xiàn)最大子段和利用的算法是（

B

）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法46.優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是（

C

）。A、先進(jìn)先出 B、后進(jìn)先出C、結(jié)點(diǎn)的優(yōu)先級(jí) D、隨機(jī)47.背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為（

B

）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）48、廣度優(yōu)先是（

A

）的一搜索方式。A、分支界限法

B、動(dòng)態(tài)規(guī)劃法

C、貪心法

D、回溯法49、舍伍德算法是（

B

）的一種。A、分支界限算法

B、概率算法

C、貪心算法

D、回溯算法50、在下列算法中有時(shí)找不到問(wèn)題解的是（

B

）。A、蒙特卡羅算法

B、拉斯維加斯算法

C、舍伍德算法

D、數(shù)值概率算法51下列哪一種算法是隨機(jī)化算法（

D

）A.貪心算法B.回溯法C.動(dòng)態(tài)規(guī)劃算法D.舍伍德算法52.一個(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)解53．采用貪心算法的最優(yōu)裝載問(wèn)題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法的時(shí)間復(fù)雜度為(B)。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）54.以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chē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è)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。3、算法的“確定性”指的是組成算法的每條指令是清晰的，無(wú)歧義的。4.矩陣連乘問(wèn)題的算法可由動(dòng)態(tài)規(guī)劃設(shè)計(jì)實(shí)現(xiàn)。5、拉斯維加斯算法找到的解一定是正確解。6、算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。7、從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是遞歸算法。8、問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。9、以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為回溯法。10、數(shù)值概率算法常用于數(shù)值問(wèn)題的求解。11、計(jì)算一個(gè)算法時(shí)間復(fù)雜度通常可以計(jì)算循環(huán)次數(shù)、基本操作的頻率或計(jì)算步。12、利用概率的性質(zhì)計(jì)算近似值的隨機(jī)算法是數(shù)值概率算法，運(yùn)行時(shí)以一定的概率得到正確解的隨機(jī)算法是__蒙特卡羅算法_____________________。14、解決0/1背包問(wèn)題可以使用動(dòng)態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是動(dòng)態(tài)規(guī)劃，需要排序的是回溯法，分支限界法。

15、使用回溯法進(jìn)行狀態(tài)空間樹(shù)裁剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問(wèn)題和0/1背包問(wèn)題正好是兩種不同的類(lèi)型，其中同時(shí)使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是0/1背包問(wèn)題，只使用約束條件進(jìn)行裁剪的是N皇后問(wèn)題。17、矩陣連乘問(wèn)題的算法可由動(dòng)態(tài)規(guī)劃設(shè)計(jì)實(shí)現(xiàn)。18、拉斯維加斯算法找到的解一定是正確解。19.貪心算法的基本要素是貪心選擇質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。21.動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。22算法是由若干條指令組成的有窮序列，且要滿足輸入，輸出、確定性和有限性四條性質(zhì)。23、大整數(shù)乘積算法是用分治法來(lái)設(shè)計(jì)的。24、以廣度優(yōu)先或以最小耗費(fèi)方式搜索問(wèn)題解的算法稱(chēng)為分支限界法。25、舍伍德算法總能求得問(wèn)題的一個(gè)解。貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法主要區(qū)別。27.快速排序算法是基于分治策略的一種排序算法。28.動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是.最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問(wèn)題性質(zhì)。30.回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。31.分支限界法主要有隊(duì)列式（FIFO）分支限界法和優(yōu)先隊(duì)列式分支限界法。32．分支限界法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。33．回溯法搜索解空間樹(shù)時(shí)，常用的兩種剪枝函數(shù)為約束函數(shù)和限界函數(shù)。34.任何可用計(jì)算機(jī)求解的問(wèn)題所需的時(shí)間都與其規(guī)模有關(guān)。35.快速排序算法的性能取決于劃分的對(duì)稱(chēng)性。簡(jiǎn)答題試簡(jiǎn)要回答漸近意義下的記號(hào)：O、Ω、θ、o，各代表什么含義？（6分），設(shè)有算法的時(shí)間表達(dá)式f(n)=10n2+20n,試用三種O，Ω，θ符號(hào)表達(dá)此算法。因此，如果存在limf(n)/g(n)，則：即意味著：f(n)=O(g(n))含義：f(n)的增長(zhǎng)最多象g(n)的增長(zhǎng)那樣快。稱(chēng)O(g(n))是f(n)的上界。因此，如果存在limf(n)/g(n)，則：即意味著：f(n)=?(g(n))含義：f(n)的增長(zhǎng)最少象g(n)的增長(zhǎng)那樣快。稱(chēng)?(g(n))是f(n)的下界。因此，如果存在limf(n)/g(n)，則：即意味著：f(n)=θ(g(n))結(jié)論：若則有：，，因此2、對(duì)下列各組函數(shù)f(n)和g(n)，確定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并簡(jiǎn)要說(shuō)明理由。（10分）(1)f(n)=2n；g(n)=n!(2)f(n)=；g(n)=logn2(3)f(n)=100；g(n)=log100(4)f(n)=n3；g(n)=3n(5)f(n)=3n；g(n)=2n3、問(wèn)題的描述：給定帶權(quán)有向圖（如下圖所示）G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱(chēng)為源。現(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱(chēng)為單源最短路徑問(wèn)題?，F(xiàn)采用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑，請(qǐng)?jiān)嚸枋鯠ijkstra的算法步其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。 初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱(chēng)為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其他頂點(diǎn)之間的最短路徑長(zhǎng)度。Dijkstra算法的迭代過(guò)程迭代 S u dist[2] dist[3]dist[4] dist[5]初始 {1} - 10 maxint 30 1001 {1,2} 2 10 60 30 1002 {1,2,4} 4 10 50 30 903 {1,2,4,3} 3 10 5030 604 {1,2,4,3,5} 5 10 5030 604、請(qǐng)敘述動(dòng)態(tài)規(guī)劃算法與貪心算法的異同，并說(shuō)明什么是最優(yōu)子結(jié)構(gòu)，動(dòng)態(tài)規(guī)劃方法為什么需要最優(yōu)子結(jié)構(gòu)性質(zhì)。計(jì)算分析題根據(jù)下述動(dòng)態(tài)規(guī)劃算法解決矩陣連乘運(yùn)算量最小的乘積順序，各矩陣維數(shù)分別為（30*15,15*20,20*45,45*10，20*30），并將計(jì)算過(guò)程中的相關(guān)數(shù)據(jù)填入表。動(dòng)態(tài)規(guī)劃算法如下：publicstaticvoidmatrixChain(int[]p,int[][]m,int[][]s){intn=p.length-1;for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)for(inti=1;i<=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}算法matrixChain的主要計(jì)算量取決于算法中對(duì)r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O()，而3重循環(huán)的總次數(shù)為O()。因此算法的計(jì)算時(shí)間上界為O()。算法所占用的空間顯然為O()。（4分）ij1234512345m[i][j]ij1234512345s[i][j]2、對(duì)下圖所示的連通網(wǎng)絡(luò)G，用Kruskal算法求G的最小生成樹(shù)T,請(qǐng)寫(xiě)出在算法執(zhí)行過(guò)程中，依次加入T的邊集TE中的邊。說(shuō)明該算法的貪心策略和算法的基本思想，并簡(jiǎn)要分析算法的時(shí)間復(fù)雜度。1212345618111715192126679當(dāng)圖的邊數(shù)為e時(shí)，Kruskal算法所需的計(jì)算時(shí)間是。當(dāng)時(shí)，Kruskal算法比Prim算法差，但當(dāng)時(shí)，Kruskal算法卻比Prim算法好得多。3、證：考慮n=3的批處理作業(yè)調(diào)度實(shí)例：tji機(jī)器1機(jī)器2作業(yè)1110作業(yè)231作業(yè)321其中tji是作業(yè)Ji需要在機(jī)器j上處理的時(shí)間。對(duì)于給定的3個(gè)作業(yè)，制定一個(gè)最佳作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。要求：（1）畫(huà)出該問(wèn)題的解空間樹(shù)；（2）寫(xiě)出該問(wèn)題的剪枝策略(即限界條件)，要求只保留第一個(gè)最優(yōu)解；（3）按優(yōu)先隊(duì)列式分支限界法搜索解空間樹(shù)，并用剪枝策略對(duì)解空間樹(shù)中該剪枝的位置打；（4）給出最優(yōu)解及最優(yōu)值。4、設(shè)n后問(wèn)題的顯約束條件是兩個(gè)皇后不能在同一行及同一列，求解n后問(wèn)題的遞歸的回溯算法如下。它計(jì)算可行解的個(gè)數(shù)，并將所有可行解輸出。請(qǐng)給算法橫線部分的填空（包括部分循環(huán)語(yǔ)句和條件判斷語(yǔ)句后面的注釋?zhuān)?。?5分）解向量：(x1,x2,…,xn)顯約束：xi=1,2,…,n隱約束：1)不同列：Xi≠Xj不處于同一正、反對(duì)角線：|i-j|≠|(zhì)Xi-Xj|privatestaticboolean