算法設(shè)計與分析期末試卷A卷

1、A卷1、 選擇題1.二分搜索算法是利用（A ）實現(xiàn)的算法。A、分治策略   B、動態(tài)規(guī)劃法   C、貪心法 D、回溯法2. 回溯法解旅行售貨員問題時的解空間樹是（ A ）。A、子集樹B、排列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹3.下列算法中通常以自底向上的方式求解最優(yōu)解的是（B  ）。A、備忘錄法B、動態(tài)規(guī)劃法C、貪心法D、回溯法4下面不是分支界限法搜索方式的是（  D  ）。A、廣度優(yōu)先B、最小耗費優(yōu)先C、最大效益優(yōu)先D、深度優(yōu)先5采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大排序

2、，故算法的時間復(fù)雜度為 ( B ) 。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）6分支限界法解最大團(tuán)問題時，活結(jié)點表的組織形式是（ B）。A、最小堆B、最大堆 C、棧D、數(shù)組7、下面問題（B ）不能使用貪心法解決。A 單源最短路徑問題 B N皇后問題 C 最小花費生成樹問題 D 背包問題8.下列算法中不能解決0/1背包問題的是（A ）A 貪心法 B 動態(tài)規(guī)劃 C 回溯法 D 分支限界法9.背包問題的貪心算法所需的計算時間為（  B   ）A、O（n2n）  B、O（nlogn） C、O（2n）  

3、; D、O（n）10.背包問題的貪心算法所需的計算時間為（B  ）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）2、 填空題1.算法的復(fù)雜性有 復(fù)雜性和 復(fù)雜性之分。2.算法是由若干條指令組成的有窮序列，且要滿足輸入、 、確定性和 四條性質(zhì)。其中算法的“確定性”指的是組成算法的每條 是清晰的，無歧義的。3.解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是 ，需要排序的是 ， 。4.動態(tài)規(guī)劃算法的兩個基本要素是. 性質(zhì)和 性質(zhì) 。5.回溯法是一種既帶有 又帶有 的搜索算法；分支限界法是一種既帶有 又帶有 的搜索算法。6. 用回溯法解題的一個顯

4、著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點到當(dāng)前擴(kuò)展結(jié)點的路徑。如果解空間樹 中從根結(jié)點到葉結(jié)點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為 。7. 用回溯法解圖的m著色問題時，使用下面的函數(shù)OK檢查當(dāng)前擴(kuò)展結(jié)點的每一個兒子所相應(yīng)的顏色的可用性，則需耗時（漸進(jìn)時間上限） 。Bool Color:OK(int k)/ for(int j=1;j<=n;j+)if(akj= =1)&&(xj= =xk) return false;return true;8. 用回溯法解布線問題時，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為的方格陣列

5、，擴(kuò)展每個結(jié)點需O(1)的時間，L為最短布線路徑的長度，則算法共耗時 ，構(gòu)造相應(yīng)的最短距離需要 時間。for (int i = 0; i < NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col; if (gridnbr.rownbr.col = 0) / 該方格未標(biāo)記 gridnbr.rownbr.col = gridhere.rowhere.col + 1; if (nbr.row = finish.row) && (nbr.col = finish.col)

6、 break; / 完成布線 Q.Add(nbr); 9.快速排序算法是基于 的一種排序算法。10. 是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別3 簡答題1. 設(shè)計動態(tài)規(guī)劃算法的主要步驟是怎么的？請簡述。2. 分治法所能解決的問題一般具有哪幾個特征？請簡述。3. 分支限界法的搜索策略是什么？4 計算題1.已知非齊次遞歸方程： ，其中，b、c是常數(shù)，g(n)是n的某一個函數(shù)。則f(n)的非遞歸表達(dá)式為：?，F(xiàn)有Hanoi塔問題的遞歸方程為： ，求h(n)的非遞歸表達(dá)式。2.給定帶權(quán)有向圖（如下圖所示）G =(V,E)，其中每條邊的權(quán)是非負(fù)實數(shù)。另外，還給定V中的一個頂點，

7、稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權(quán)之和?，F(xiàn)采用Dijkstra算法計算從源頂點1到其它頂點間最短路徑。請將此過程填入下表中。43211初始dist5dist4dist3dist2uS迭代5 程序題1. 試用貪心算法求解汽車加油問題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個加油站。試設(shè)計一個有效算法，指出應(yīng)在哪些加油站?？考佑?，使加油次數(shù)最少，請寫出該算法。2.試用動態(tài)規(guī)劃算法實現(xiàn)下列問題：設(shè)A和B是兩個字符串。我們要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串B，這里所說的字符操作包括： （1）刪除一個字符。（2）插入一個字符。（3）將一個字符

8、改為另一個字符。 請寫出該算法。 答案：1、 AABDB BBABB2、1. 時間 空間 2. 輸出 有限性 指令3. 動態(tài)規(guī)劃 回溯法 分支限界法4. 最優(yōu)子結(jié)構(gòu) 重疊子問題5. 系統(tǒng)性 跳躍性 系統(tǒng)性 跳躍性6. （O(h(n)6. ） 7. O（mn）8. O(mn) O(L)9. 分治策略 10. 貪心選擇性質(zhì)3、 1. （1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 （2）遞歸地定義最優(yōu)值。 （3）以自底向上的方式計算出最優(yōu)值。 （4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。2. （1）該問題的規(guī)模縮小到一定的程度就可以容易地解決； （2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問

9、題具有最優(yōu)子結(jié)構(gòu)性質(zhì); （3） 利用該問題分解出的子問題的解可以合并為該問題的解； （4）原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 3. 在擴(kuò)展結(jié)點處，先生成其所有的兒子結(jié)點（分支），然后再從當(dāng)前的活結(jié)點表中選擇下一個擴(kuò)展結(jié)點。為了有效地選擇下一擴(kuò)展結(jié)點，加速搜索的進(jìn)程，在每一個活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有利的結(jié)點作為擴(kuò)展結(jié)點，使搜索朝著解空間上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個最優(yōu)解。4、 1.解：利用給出的關(guān)系式，此時有：b=2, c=1, g(n)=1, 從n遞推到1，有：6030501051，2，3，4

10、，546030501031，2，4，339030501041，2，4210030601021，211003010-1初始dist5dist4dist3dist2uS迭代2.5 程序題1.解：int greedy(vecter<int>x,int n) int sum=0,k=x.size(); for(int j=0;j<k;j+) if(xj>n) cout<<”No solution”<<endl; return -1; For(int i=0,s=0;i<k;i+) S+=xi; if(s>n)sum+;s=xi; return sum; 2.解：此題用動態(tài)規(guī)劃算法求解： int dist() int m=a.size();int n=b.size();vector<int>d(n+1，0);for(i