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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上A卷1、 選擇題1.二分搜索算法是利用（A ）實(shí)現(xiàn)的算法。A、分治策略   B、動(dòng)態(tài)規(guī)劃法   C、貪心法 D、回溯法2. 回溯法解旅行售貨員問(wèn)題時(shí)的解空間樹(shù)是（ A ）。A、子集樹(shù)B、排列樹(shù)C、深度優(yōu)先生成樹(shù)D、廣度優(yōu)先生成樹(shù)3.下列算法中通常以自底向上的方式求解最優(yōu)解的是（B  ）。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法4下面不是分支界限法搜索方式的是（  D  ）。A、廣度優(yōu)先B、最小耗費(fèi)優(yōu)先C、最大效益優(yōu)先D、深度優(yōu)先5采用貪心算法的最優(yōu)裝載問(wèn)題的主要計(jì)算量在于將

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

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

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

5、果布線區(qū)域劃分為的方格陣列，擴(kuò)展每個(gè)結(jié)點(diǎn)需O(1)的時(shí)間，L為最短布線路徑的長(zhǎng)度，則算法共耗時(shí) ，構(gòu)造相應(yīng)的最短距離需要 時(shí)間。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

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

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

8、一個(gè)字符。（3）將一個(gè)字符改為另一個(gè)字符。 請(qǐng)寫(xiě)出該算法。 答案：1、 AABDB BBABB2、1. 時(shí)間 空間 2. 輸出 有限性 指令3. 動(dòng)態(tài)規(guī)劃 回溯法 分支限界法4. 最優(yōu)子結(jié)構(gòu) 重疊子問(wèn)題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）以自底向上的方式計(jì)算出最優(yōu)值。 （4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。2. （1）該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決； （2）該問(wèn)題可以分解為若干個(gè)

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

10、0501051，2，3，4，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.解：此題用動(dòng)態(tài)規(guī)劃算法求解： int dist() int m=a.size();int n=b.size();vector<int>d(n+1，0);for(int i=1;