聊城大學(xué)《算法設(shè)計與分析》復(fù)習(xí)題及參考答案_第1頁
聊城大學(xué)《算法設(shè)計與分析》復(fù)習(xí)題及參考答案_第2頁
聊城大學(xué)《算法設(shè)計與分析》復(fù)習(xí)題及參考答案_第3頁
聊城大學(xué)《算法設(shè)計與分析》復(fù)習(xí)題及參考答案_第4頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

《算法設(shè)計與分析》練習(xí)題及參考答案一、填空題1.與遞歸像一對孿生兄弟,經(jīng)常同時應(yīng)用在算法設(shè)計之中,并由此產(chǎn)生許多高效算法2.在搜索解空間樹T時,每一個活結(jié)點只有一次機會成為擴展結(jié)點的方法是。3.動態(tài)規(guī)劃的兩個基本要素為和。4.當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時,稱此問題具有。5.有許多問題,當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時,往往要使用。6.是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇,即貪心選擇來達到。二、簡答題1.分支限界法與回溯法有什么不同點?2.回溯算法的效率在很大程度上依賴于哪些因素?三、綜合題給定無向圖G=(V,E)。如果UV,且對任意u,vU有(u,v)E,則稱U是G的完全子圖。G的完全子圖U是G的團當(dāng)且僅當(dāng)U不包含在G的更大的完全子圖中。G的最大團是指G中所含頂點數(shù)最多的團。SHAPE124512453(1)畫出上圖中的最大團。(2)用C++語言寫出使用回溯法解決最大團問題的算法。(3)分析該算法的時間復(fù)雜度。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的團當(dāng)且僅當(dāng)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與當(dāng)前團的連接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)分析該算法的時間復(fù)雜度。答:算法所需要的時間為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,外部設(shè)定intj=1;for(intk=2;k<=n;k++)if((lowcost[k]<min)&&(!s[k])){min=lowcost[k];j=k;}cout<<j<<""<<closest[j]<<endl;

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論