算法分析與設(shè)計(jì)試題

本文格式為Word版，下載可任意編輯——算法分析與設(shè)計(jì)試題一、選擇題（20分）

1．最長(zhǎng)公共子序列算法利用的算法是（B）。A、分支界限法

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

C、貪心法

D、回溯法

2．實(shí)現(xiàn)棋盤(pán)覆蓋算法利用的算法是（A）。A、分治法

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

C、貪心法

D、回溯法

3.下面是貪心算法的基本要素的是（C）。A、重疊子問(wèn)題

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

C、貪心選擇性質(zhì)

D、定義最優(yōu)解

4.回溯法的效率不依靠于以下哪些因素（D）A.滿(mǎn)足顯約束的值的個(gè)數(shù)C.計(jì)算限界函數(shù)的時(shí)間

B.計(jì)算約束函數(shù)的時(shí)間D.確定解空間的時(shí)間

5.下面哪種函數(shù)是回溯法中為避免無(wú)效探尋采取的策略（B）A．遞歸函數(shù)

B.剪枝函數(shù)

C。隨機(jī)數(shù)函數(shù)

D.探尋函數(shù)

6．采用最大效益優(yōu)先探尋方式的算法是（A）。A、分支界限法

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

C、貪心法

D、回溯法

7．貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是（B）。A、最優(yōu)子結(jié)構(gòu)優(yōu)解

8.實(shí)現(xiàn)最大子段和利用的算法是（B）。A、分治策略

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

C、貪心法

D、回溯法

B、貪心選擇性質(zhì)

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

D、定義最

9.優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是（C）。A、先進(jìn)先出

B、后進(jìn)先出

C、結(jié)點(diǎn)的優(yōu)先級(jí)D、隨機(jī)

10.以下算法中尋常以廣度優(yōu)先方式系統(tǒng)探尋問(wèn)題解的是（A）。

A、分支限界法

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

C、貪心法

D、回溯法

二、填空題（22分每空2分）

1.算法是由若干條指令組成的有窮序列，且要滿(mǎn)足輸入、輸出、確定性和有限性四條性質(zhì)。2、大整數(shù)乘積算法是用分治法來(lái)設(shè)計(jì)的。

3、以廣度優(yōu)先或以最小花費(fèi)方式探尋問(wèn)題解的算法稱(chēng)為分支限界法。4、舍伍德算法總能求得問(wèn)題的一個(gè)解。

5、貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。6.快速排序

template

voidQuickSort(Typea[],intp,intr){

if(pusingnamespacestd;intGcd(intm,intn)

{

if(m==0)

returnn;if(n==0)

returnm;intt=m>n?n:m;while(m%t||n%t)t--;returnt;}

intmain(){

inta,b;

cout>a>>b;

intm=a*b/Gcd(a,b);

coutsum)sum=max;

}}

returnsum;……………..（10分）}

intMaxSum(intn,int*a)

{

intsum=0,b=0;

for(inti=1;i0)b+=a[i];elseb=a[i];if(b>sum)sum=b;}

Returnsum;……………..（15分）}

四、簡(jiǎn)答題（33分）

1、假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均可以被分割，且背寬容量M＝150，假使使用貪心方法求解此背包問(wèn)題，使收益最大，請(qǐng)寫(xiě)出求解過(guò)程請(qǐng)寫(xiě)出求解過(guò)程。（10分）

物品ABCDEFG2530重量353060504010價(jià)值104030503540解：使用單位價(jià)值從大到?。篎BGDECA，得到貪心解為：FBGD全部放入，而E放入87.5%，得到價(jià)值為190.625。

2.寫(xiě)出分治算法MaxMin算法對(duì)以下實(shí)例中找最大數(shù)和最小數(shù)的過(guò)程。（10分）

數(shù)組A=(48,12,61,3,5,19,32,7)

解：1、48,12,61,3,5,19,32,7表中元素多于二，對(duì)半分割2、48,1261,35,1932,7表中元素多于二，對(duì)半分割3、48～61,12～319～32，5～7

求前半部分的最大最小和后半部分的最大最小，兩個(gè)半部分的大者為最大，小者為最小

4、61～323～5兩個(gè)半部分的大者為最大，小者為最小5、613尋覓終止

3.寫(xiě)出多段圖最短路經(jīng)動(dòng)態(tài)規(guī)劃算法求解以下實(shí)例的過(guò)程，并求出最優(yōu)值。（13分）

254843545136221647各邊的代價(jià)如下：

C(1,2)=3，C(1,3)=5，C(1,4)=2

8C(2,6)=8，C(2,7)=4，C(3,5)=5，C(3,6)=4，C(4,5)=2，C(4,6)=1C(5,8)=4，C(6,8)=5，C(7,8)=6

解：Cost(4,8)=0

Cost(3,7)=C(7,8)+0=6，Cost(3,6)=C(6，8)+0=5,Cost(3,5)=C(5，8)+0=4

Cost(2,4)=min{C(4，6)+Cost(3,6),C(4，5)+Cost(3,5)}=min{1+5,2+4}=6

Cost(2,3)=min{C(3，6)+Cost(3,6)}=min{4+5}=9

Cost(2,2)=min{C(2，6)+Cost(3,6),C(2，7)+Cost(3,7)}=min{8+5,4+