聊城大學(xué)《算法設(shè)計(jì)與分析》復(fù)習(xí)題及參考答案

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