算法設(shè)計(jì)試卷模式A答案

南陽理工學(xué)院2010－2011學(xué)年第一學(xué)期試卷參考答案課程：算法設(shè)計(jì)與分析 (A)評(píng)卷人(簽名)： 復(fù)核人(簽名)： 題號(hào)一一二三四五總分得分一、選擇題(每小題1分，共10分)算法分析是(c)。A．將算法用某種程序設(shè)計(jì)語言恰當(dāng)?shù)乇硎境鰜鞡.在抽象數(shù)據(jù)集合上執(zhí)行程序，以確定是否會(huì)產(chǎn)生錯(cuò)誤的結(jié)果c.對(duì)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量分析D.證明算法對(duì)所有可能的合法輸入都能算出正確的答案下列(A)不是描述算法的工具。A.數(shù)據(jù)流圖 B.偽代碼 C.自然語言D.程序語言如果某一算法的執(zhí)行時(shí)間不超過輸入規(guī)模的兩倍，那么算法漸進(jìn)時(shí)間復(fù)雜度為(B)oA. 0(n2) B. 0(n) C.0(n) D.O(n)下列程序段的S執(zhí)行的次數(shù)為(D)ofor(inti=0;i<n;i++)for(intj=0;j<i;j++)S;//S是基本操作，耗時(shí)常數(shù)時(shí)間A.n2 B.n2/2 C.n(n+1)/2D.n(n-1)/2使用F(n)=n*F(n)遞歸求F(4)，其中邊界條件為F(0)=1，則遞歸調(diào)用子函數(shù)的次數(shù)為(B)。A. 3次B.4次C.5次D.8次Fibonacci數(shù)列的第1項(xiàng)為0,第2項(xiàng)為1,那么它的第10項(xiàng)為(D)。A. 3B. 13C. 21D.347?下列排序算法不是基于交換的是(C)oA冒泡排序B.快速排序C合并排序D.堆排序8.4個(gè)結(jié)點(diǎn)的二叉查找樹可能的形態(tài)有(C)種。A4種B. 5種 C.14種D. 15種9.如果背包的容量為100,而物品共有10個(gè)，則使用動(dòng)態(tài)規(guī)劃來解0-1背包問題數(shù)組大小為(C)A. 10B. 100C.1000D1000010?對(duì)線性表執(zhí)行折半搜索時(shí)，要求線性表必須(C)oA以數(shù)組方式存儲(chǔ) B以單鏈表形式存儲(chǔ)C以數(shù)組方式存儲(chǔ)且關(guān)鍵字有序 D.以單鏈表形式存儲(chǔ)且關(guān)健字有序二、填空題(每空2分，共30分)請(qǐng)將合并排序的分治算法補(bǔ)充完整。數(shù)組a存放待排序元素，left:為待排序元素最小下標(biāo)‘right:為待排元素最大下標(biāo)。voidMergeSort(Typea[],intleft,intright){Type*b=newint[right-left+1];if(left<right){inti=(left+right}/2 ;MergeSort(a,left,i);MergeSort(a,i+l,right):Merge(a,b,left,i,right);copy(a,b,left,right):}}template<classType>voidMerge(Typea[],Typeb[],intleft,intmid,intright){inti=1eft,j=mid+1,k=left:while((i<=mid)&&j<=right)){if(a[i]<=a[j])b[k++]=a[i++]:elseb[k++]=a[j++]:}if(i>mid)for(intq=j:q<=right:q++)b[k++]=a[q]:elsefor(intq=i:q<=mid:q++)b[k++]=a[q]:}template<classType>voidcopy(Typea[],Typeb[],intleft,intright){for(inti=left:i<=right:i++){a「i]=b「i]:}}

2.動(dòng)態(tài)規(guī)劃的基本要素包括重疊子問題、自底向上的解決方法、最優(yōu)子結(jié)構(gòu)性質(zhì)。3?矩陣連乘問題算法借助于二維數(shù)組存放各子問題的最優(yōu)值。4?給定序列X={SREABEDBWD},Y={RBAEFEA的最長(zhǎng)公共子序列的長(zhǎng)度為_3 。5?活動(dòng)安排問題的貪心策略是一選擇結(jié)束時(shí)間最早的活動(dòng)優(yōu)先安排。6最大團(tuán)問題的解空間樹是一棵一子集_樹，n皇后問題的滿足不同行、不同列要求的解空間樹是一棵排列樹。7隨機(jī)化算法中，蒙特卡羅算法用于求準(zhǔn)確解，數(shù)值隨機(jī)化算法用于求近似解：用于求問題的正確解拉斯維加斯算法算法，但是,算法的每一次運(yùn)行不一定得到解。當(dāng)確定性算法中，最壞情況和最好情況下時(shí)間的相差很大時(shí)，用舍伍德算法削弱這種差異。三、 問答題（每小題5分，共20分）分治算法有何特征。答：分治算法具有以下特征：（1）問題規(guī)模足夠小時(shí)容易解決；（2）將規(guī)模大的問題分成規(guī)模較小的子問題；（3）子問題相互獨(dú)立；（4）子問題的解決方法與原問題相同；（5）遞歸解決子問題；（6）子問題的解能夠合并成原問題的解。簡(jiǎn)述構(gòu)造哈夫曼樹的算法思想。答：將n個(gè)字符看做是n可孤立的樹，組成一個(gè)結(jié)合。重復(fù)做如下操作：從集合中取出兩棵出現(xiàn)頻率最低的樹，讓它們作為左右子樹構(gòu)成一棵新樹，新樹的頻率為左右子樹頻率之和。然后將新樹插入到樹的集合中；算法知道集合中只剩下一棵樹為止。3?簡(jiǎn)述圖的m著色問題解空間的定義。答：圖的m著色問題解的形式為一個(gè)n元組（X],x2,…,xn），其中n表示圖的頂點(diǎn)個(gè)數(shù)。Xi:表示圖中第i個(gè)頂點(diǎn)著第X號(hào)色。每個(gè)分量的取值范圍均為1~~給定的顏色數(shù)m4?簡(jiǎn)述分支限界法的思想。答：從根結(jié)點(diǎn)開始，以廣度優(yōu)先（最小耗費(fèi)優(yōu)先或最大效益優(yōu)先）的方式進(jìn)行搜索。根結(jié)點(diǎn)插入活結(jié)點(diǎn)表中，重復(fù)做如下操作：從活結(jié)點(diǎn)表中取出一個(gè)活結(jié)點(diǎn)作為當(dāng)前的擴(kuò)展結(jié)點(diǎn)，一次性生成擴(kuò)展結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，判斷孩子結(jié)點(diǎn)是舍棄還是保留，保留那些有可能導(dǎo)致可行解或可能導(dǎo)致最優(yōu)解的孩子結(jié)點(diǎn)，將保留下來的孩子結(jié)點(diǎn)插入到活結(jié)點(diǎn)表中。算法直到找到問題的解或活結(jié)點(diǎn)表為空為止。四、 求解題（共28分）1.（8分）用回溯法解如下旅行售貨員問題。假設(shè)當(dāng)前旅行售貨員的住地為1號(hào)城市，邊上的權(quán)為城市之間的交通費(fèi)用，要求從1號(hào)城市出發(fā)，到其它城市各去一次推銷商品，然后再回到住地所花費(fèi)的總交通費(fèi)用最少的路線。（要求：做好搜索前的準(zhǔn)備，然后用搜索樹展示搜索過程）解：（1）解的形式為n元組（x1,x2,x3,x4），其中xi表示第i個(gè)要去推銷商品的城市為X號(hào)城市。令城市集合為S={1,2,3,4}則x1=1,x2={2,3,4}x3=S-{x1?x2},x4=S-{x1,x2,x3}（2）解空間的組織結(jié)構(gòu)：排列樹，深度為4⑶搜索：約束條件:a[x[t-1]][x[t]]!=8限界條件：cf+rcost<bestf或cf+a[x[t-1]][x[t]]<bestf其中a[]□為圖的鄰接矩陣，cf:當(dāng)前已花費(fèi)的費(fèi)用，bestf：當(dāng)前最優(yōu)路線所花費(fèi)的費(fèi)用，rcost：剩余費(fèi)用的最小值。搜索樹如下x1=1x2=2x3=3 4x4=4（8分）給定7個(gè)作業(yè)，要在兩臺(tái)機(jī)器M]、M2組成的流水線上完成加工。每個(gè)作業(yè)都是先在上加工,然后在M上加工。在M上處理時(shí)間為：（a,a,a,a,a,a,a）=（3,8,2,9,5,4,4）,在M上的處理時(shí)間為:2112345672（b,b,b,b,b,b,b）=（2,6,7,10,5,3,8）,按照流水作業(yè)調(diào)度問題的Johnson算法步驟，給出該問題1 2 3 4 5 6 7的最優(yōu)調(diào)度方案。（要求：先寫出Johns。n算法步驟，然后寫出每一個(gè)步驟對(duì)應(yīng)的求解情況）解：1）N’={i|a.<b.}={347} N2={i|a.Mb.}={l256}1ii2ii2） 將叫按照a.非減序排序，將N2按照b.非增序排序。1.2.N={374}N={2561}123） N接N即為所求的最優(yōu)調(diào)度N=NN={3742561}1212（12分）給定下圖的一個(gè)網(wǎng)絡(luò)及網(wǎng)絡(luò)上的可行流，從給定的可行流出發(fā)，采用增廣路算法找出最大網(wǎng)絡(luò)流。有向邊上對(duì)應(yīng)的值為（容量：ap，流量flow）。要求：解答體現(xiàn)在網(wǎng)絡(luò)中標(biāo)號(hào)過程和找到的增廣路，每一次增流后的可行流及最后的最大流。2竺4（3,3）/*1/（1,1）按頂點(diǎn)序號(hào)由小到大的原則選擇已標(biāo)號(hào)未檢查的點(diǎn)）解：(5,1)(1,1)'3.(2,0)■冬(5,3)(3,0)76上5乙1)0,+?0,+?0,+?(3,3)zx1(5,2)五、算法設(shè)計(jì)(-5,1)2 (4,3)IA丄(5,2)4(5,3)(1,1(卜0)n(5,1)丫”5嚴(yán))(1,4) (3,2)(3,3)(5,3)(3,3)(5,3)\o"CurrentDocument"(-5,1) (5,1)\o"CurrentDocument"2 (4,3) 42 4?\Xi一 I(5,4)(1,1(3,1)6 (4,1)3 (13)(2,2)二丫2,2)(3,1)2 (4,3)人__x 、)3)(1,1(3,1)￥、6(2,2)共12分）：說明：任意選擇所使用的算法策略。要求：說明所使用的算法策略；寫出算法實(shí)現(xiàn)的主要步驟（可用自然語言描述，也可以計(jì)算機(jī)編程語言描述）；題目：0-1背包問題解：回溯法（定義解的結(jié)構(gòu)，確定解空間樹，確定限界函數(shù)，深度優(yōu)先方式搜索，判斷當(dāng)前是否到葉子節(jié)點(diǎn)，若到了葉子節(jié)點(diǎn)，則修正最優(yōu)值，若是中間節(jié)點(diǎn)，判斷是否滿足約束函數(shù)和限界函數(shù)，滿足則深一步搜索，若不滿足，則剪枝）分支限界法：（定義解的結(jié)構(gòu)，確定解空間樹，確定限界函數(shù)，深度優(yōu)先方