聊城大學《算法設計與分析》復習題及參考答案

《算法設計與分析》練習題及參考答案一、填空題1．與遞歸像一對孿生兄弟，經(jīng)常同時應用在算法設計之中，并由此產(chǎn)生許多高效算法2.在搜索解空間樹T時，每一個活結(jié)點只有一次機會成為擴展結(jié)點的方法是。3．動態(tài)規(guī)劃的兩個基本要素為和。4.當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有。5．有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用。6.是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。二、簡答題1.分支限界法與回溯法有什么不同點？2.回溯算法的效率在很大程度上依賴于哪些因素？三、綜合題給定無向圖G=(V，E)。如果UV，且對任意u，vU有(u，v)E，則稱U是G的完全子圖。G的完全子圖U是G的團當且僅當U不包含在G的更大的完全子圖中。G的最大團是指G中所含頂點數(shù)最多的團。SHAPE124512453（1）畫出上圖中的最大團。（2）用C++語言寫出使用回溯法解決最大團問題的算法。（3）分析該算法的時間復雜度。2.下圖為G=(V,E)是連通帶權(quán)圖，構(gòu)造G的最小生成樹的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jV-S，且c[i][j]最小的邊，將頂點j添加到S中。這個過程一直進行到S=V時為止。參考答案一、填空題1.分治2.分支限界法3.最優(yōu)子結(jié)構(gòu) 重疊字問題4．最優(yōu)子結(jié)構(gòu)性質(zhì)5．回溯法6.貪心算法二、簡答題1.分支限界法與回溯法有什么不同點？答：求解目標不同：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。2.回溯算法的效率在很大程度上依賴于哪些因素？答：回溯算法的效率在很大程度上依賴于以下因素：(1)產(chǎn)生x[k]的時間；(2)滿足顯約束的x[k]值的個數(shù)；(3)計算約束函數(shù)constraint的時間；(4)計算上界函數(shù)bound的時間；(5)滿足約束函數(shù)和上界函數(shù)約束的所有x[k]的個數(shù)。三、綜合題1.給定無向圖G=(V，E)。如果UV，且對任意u，vU有(u，v)E，則稱U是G的完全子圖。G的完全子圖U是G的團當且僅當U不包含在G的更大的完全子圖中。G的最大團是指G中所含頂點數(shù)最多的團。（1）請畫出上圖中的最大團。（6分）541352521541352521（2）用C++語言寫出使用回溯法解決最大團問題的算法。voidClique::Backtrack(inti){//計算最大團if(i>n){//到達葉結(jié)點for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn;return;}//檢查頂點i與當前團的連接intOK=1;for(intj=1;j<i;j++)if(x[j]&&a[i][j]==0){//i與j不相連OK=0;break;}if(OK){//進入左子樹x[i]=1;cn++;Backtrack(i+1);x[i]=0;cn--;}if(cn+n-i>bestn){//進入右子樹x[i]=0;Backtrack(i+1);}（3）分析該算法的時間復雜度。答：算法所需要的時間為O(n2n)。。2.下圖為G=(V,E)是連通帶權(quán)圖，構(gòu)造G的最小生成樹的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jV-S，且c[i][j]最小的邊，將頂點j添加到S中。這個過程一直進行到S=V時為止。對于上圖中的帶權(quán)圖，請畫出按Prim算法選取邊的過程。答：給出解活動安排問題的貪心算法GreedySelector。template<classType>voidPrim(intn,Type**c){Typelowcost[maxint];intclosest[maxint];bools[maxint];s[1]=true;for(inti=2;i<=n;i++){lowcost[i]=c[1][i];closest[i]=1;s[i]=false;}for(inti=1;i<n;i++){Typemin=inf;//inf=0xfffffff,外部設定intj=1;for(intk=2;k<=n;k++)if((lowcost[k]<min)&&(!s[k])){min=lowcost[k];j=k;}cout<<j<<""<<closest[j]<<endl;