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

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