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

算法設(shè)計(jì)與剖析期末試卷A卷卷一、選擇題二分搜尋算法是利用（A）實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)向規(guī)劃法C、貪心法D、回溯法2.回溯法解旅游售貨員問題時(shí)的解空間樹是（A）。A、子集樹B、排列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹3.下列算法中往常以自底向上的方式求解最優(yōu)解的是（B）。A、備忘錄法B、動(dòng)向規(guī)劃法C、貪心法D、回溯法4．下面不是分支界線法搜尋方式的是（D）。A、廣度優(yōu)先B、最小耗資優(yōu)先C、最大效益優(yōu)先D、深度優(yōu)先5．采用貪心算法的最優(yōu)裝載問題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法的時(shí)間復(fù)雜度為(B)。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）6．分支限界法解最大團(tuán)問題時(shí)，活結(jié)點(diǎn)表的組織形式是（B）。A、最小堆B、最大堆C、棧D、數(shù)組7、下面問題（B）不能使用貪心法解決。A單源最短路徑問題BN皇后問題C最小花費(fèi)生成樹問題D背包問題下列算法中不能解決0/1背包問題的是（A）A貪心法B動(dòng)向規(guī)劃C回溯法D分支限界法背包問題的貪心算法所需的計(jì)算時(shí)間為（A、O（n2n）B、O（nlogn）C、O（2n）

）、O（n）背包問題的貪心算法所需的計(jì)算時(shí)間為（B）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）二、填空題1.算法的復(fù)雜性有復(fù)雜性和復(fù)雜性之分。2.算法是由若干條指令組成的有窮序列，且要知足輸入、、確定性和四條性質(zhì)。其中算法的“確定性”指的是組成算法的每條是清晰的，無歧義的。解決0/1背包問題能夠使用動(dòng)向規(guī)劃、回溯法和分支限界法，其中不需要排序的是，需要排序的是，。4.動(dòng)向規(guī)劃算法的兩個(gè)基本要素是.性質(zhì)和性質(zhì)。1/7算法設(shè)計(jì)與剖析期末試卷A卷5.回溯法是一種既帶有又帶有的搜尋算法；分支限界法是一種既帶有又帶有的搜尋算法。用回溯法解題的一個(gè)顯著特點(diǎn)是在搜尋過程中動(dòng)向產(chǎn)生問題的解空間。在任何時(shí)刻，算法只保留從根結(jié)點(diǎn)到目前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h(n)，則回溯法所需的計(jì)算空間往常為。用回溯法解圖的m著色問題時(shí)，使用下面的函數(shù)OK檢查目前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色的可用性，則需耗時(shí)（漸進(jìn)時(shí)間上限）。BoolColor::OK(intk){//for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}用回溯法解布線問題時(shí)，求最優(yōu)解的主要程序段如下。如果布線地區(qū)區(qū)分為m的方格陣列，擴(kuò)展每個(gè)結(jié)點(diǎn)需O(1)的時(shí)間，L為最短布線路徑的長(zhǎng)度，則算法共耗時(shí)，結(jié)構(gòu)相應(yīng)的最短距離需要時(shí)間。for(inti=0;i<NumOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0){//該方格未標(biāo)記grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//達(dá)成布線Q.Add(nbr);}}9.迅速排序算法是鑒于的一種排序算法。10.是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)向規(guī)劃算法的主要區(qū)別三．簡(jiǎn)答題設(shè)計(jì)動(dòng)向規(guī)劃算法的主要步驟是怎么的？請(qǐng)簡(jiǎn)述。2/7算法設(shè)計(jì)與剖析期末試卷A卷分治法所能解決的問題一般擁有哪幾個(gè)特點(diǎn)？請(qǐng)簡(jiǎn)述。分支限界法的搜尋策略是什么？四．計(jì)算題f(n)bf(n1)g(n)是常數(shù)，g(n)1.已知非齊次遞歸方程：，其中，b、cf(0)cn是n的某一個(gè)函數(shù)。則f(n)的非遞歸表達(dá)式為：f(n)cbnbnig(i)。i1現(xiàn)有Hanoi塔問題的遞歸方程為：h(n)2h(n1)1，求h(n)的非遞歸表達(dá)式。h(1)12.給定帶權(quán)有向圖（如下列圖所示）G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。此外，還給定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)將此過程填入下表中。迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}1234五．程序題3/7算法設(shè)計(jì)與剖析期末試卷A卷1.試用貪心算法求解汽車加油問題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個(gè)加油站。試設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站?？考佑?，使加油次數(shù)最少，請(qǐng)寫出該算法。2.試用動(dòng)向規(guī)劃算法實(shí)現(xiàn)下列問題：設(shè)A和B是兩個(gè)字符串。我們要用最少的字符操作，將字符串A變換為字符串B，這里所說的字符操作包括：1）刪除一個(gè)字符。2）插入一個(gè)字符。3）將一個(gè)字符改為另一個(gè)字符。請(qǐng)寫出該算法。答案：一、AABDBBBABB二、1.時(shí)間空間2.輸出有限性指令3.動(dòng)向規(guī)劃回溯法分支限界法4.最優(yōu)子結(jié)構(gòu)重疊子問題5.系統(tǒng)性跳躍性系統(tǒng)性跳躍性（O(h(n))）O（mn）O(mn)O(L)分治策略貪心選擇性質(zhì)三、1.（1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特點(diǎn)。（2）遞歸地定義最優(yōu)值。4/7算法設(shè)計(jì)與剖析期末試卷A卷（3）以自底向上的方式計(jì)算出最優(yōu)值。（4）根據(jù)計(jì)算最優(yōu)值時(shí)獲得的信息，結(jié)構(gòu)最優(yōu)解。（1）該問題的規(guī)?？s小到一定的程度就能夠容易地解決；（2）該問題能夠分解為若干個(gè)規(guī)模較小的相同問題，即該問題擁有最優(yōu)子結(jié)構(gòu)性質(zhì);（3）利用該問題分解出的子問題的解能夠歸并為該問題的解；（4）原問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)（分支），然后再?gòu)哪壳暗幕罱Y(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，加快搜尋的進(jìn)度，在每一個(gè)活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值（限界），并根據(jù)函數(shù)值，從目前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜尋朝著解空間上有最優(yōu)解的分支推進(jìn)，以便趕快地找出一個(gè)最優(yōu)解。四、解：利用給出的關(guān)系式，此時(shí)有：b=2,c=1,g(n)=1,從n遞推到1，有：n1h(n)cbn1bn1ig(i)i12n12n2...22212n12.迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10301001{1，2}21060301002{1，2，4}4105030903{1，2，4，3}3105030604{1，2，3，4，5}510503060五．程序題解：intgreedy(vecter<int>x,intn){5/7算法設(shè)計(jì)與剖析期末試卷A卷intsum=0,k=x.size( );for(intj=0;j<k;j++)if(x[j]>n){cout<<”Nosolution”<<endl;return-1;}For(inti=0,s=0;i<k;i++){S+=x[i];if(s>n){sum++;s=x[i];}}returnsum;}2.解：本題用動(dòng)向規(guī)劃算法求解：intdist( ){intm=a.size( );intn=b.size( );vector<int>d(n+1，0);for(inti=1;i<=n;i++)d[i]=i;for(i=