算法設(shè)計與分析A8卷答案

第=page1*2-11頁，共=sectionpages3*26頁第=page1*22頁，共=sectionpages3*26頁南陽理工學(xué)院課程考試參考答案與評分標(biāo)準(zhǔn)考試課程：算法設(shè)計與分析學(xué)年學(xué)期：試卷類型：考試時間：120分鐘一、填空題：（每空2分，共20分）1．Kruskal算法求最小生成樹的過程中，貪心策略是在邊集E中選取權(quán)值最小的邊(i，j)，如果將邊(i，j)加入集合TE中不產(chǎn)生回路（或環(huán)），則將邊(i，j)加入邊集TE中，否則繼續(xù)選擇下一條最短邊。給定n條邊的無向連通圖，該算法的時間復(fù)雜度為O(nlogn)2．用分治法設(shè)計的快速排序算法描述如下，其中R[low:high]存放的待排序序列，請?zhí)顚懣杖辈糠值恼Z句。void

QuickSort(int

R[]，int

low，int

high)

{

int

pivotpos；//記錄基準(zhǔn)元素所在位置

if(low<high){

pivotpos=Partition(R,low,high)；

QuickSort(R,low,pivotpos-1)；

QuickSort(R,pivotpos+1,high)；

}

}3．給定n個城市的交通圖，住地城市為1號城市，旅行售貨員問題的算法描述如下，其中t為當(dāng)前擴展結(jié)點所處的層次，g為鄰接矩陣，x記錄當(dāng)前解，bestx記錄當(dāng)前最優(yōu)解，cl記錄當(dāng)前已經(jīng)走的路徑長度，請?zhí)顚懣杖辈糠值恼Z句。voidTraveling(intt){if(t>n)if(g[x[n]][1]!=&&(cl+g[x[n]][1]<bestl)){for(j=1;j<=n;j++)bestx[j]=x[j];bestl=cl+g[x[n]][1];}elsefor(j=t;j<=n;j++)if(g[x[t-1]][x[j]]!=&&(cl+g[x[t-1]][x[j]]<bestl)){swap(x[t],x[j]);//交換兩個元素的值cl+=g[x[t-1]][x[j]];Traveling(t+1);cl-=g[x[t-1]][x[j]];swap(x[t],x[j]);}}4．動態(tài)規(guī)劃的基本要素有最優(yōu)子結(jié)構(gòu)性質(zhì)、重疊子問題、自底向上的求解方法。5．給定n個頂點的無向圖和m種顏色，圖的m可著色問題的解空間樹是滿m叉樹，該問題回溯法的時間復(fù)雜度為O(mn)二、選擇題：（每題2分，共20分）1．算法必須滿足的特性除了有能行性和確定性外，還有（ABC）。A．輸出B．有限性C．輸入D．無限性2．最長公共子序列問題中，給定兩個序列X={A,B,C,B,D,A,B}和Y={A,C,B,E,D,B}，這兩個序列的最長公共子序的長度為（C）。A．3B．6C．5D．43．背包問題：給定n=4，W=7，w=(3,5,2,1)，p=(9,10,7,4)，該問題的最大價值是（D）。A．19B．20C．21D．224．分支限界法與回溯法的不同主要表現(xiàn)在（ABD）。A．搜索目標(biāo)B．搜索方式C．搜索開始D．?dāng)U展方式5．影響算法時間復(fù)雜度的主要因素除算法本身外，以下說法不正確的是（AB）。A．算法的時間復(fù)雜度一定與輸入序列有關(guān)B．算法的時間復(fù)雜度一定不與輸入序列有關(guān)C．算法的時間復(fù)雜度不一定與輸入序列有關(guān)D．算法的時間復(fù)雜度一般與問題的規(guī)模有關(guān)6．某算法的時間復(fù)雜度表達(dá)式為T(n)=30n4+20n3+40n2+46n+100，該算法的時間復(fù)雜度可以用下列哪個漸進意義下的符號表示。（ABC）A．OB．C．D．以上符號都不能用來表示7．有關(guān)Prim算法和Kruskal算法的描述說法正確的是（CD）A．Prim算法的時間復(fù)雜度為（nlogn），其中n為無向連通圖的頂點數(shù)B．對稠密圖，Kruskal算法比Prim算法有效C．對稀疏圖，Kruskal算法比Prim算法有效D．對稠密圖，Kruskal算法不如Prim算法有效8．給定一個網(wǎng)絡(luò)G=（V,E），假設(shè)s為源點，其標(biāo)號為（0，+∞）。從已標(biāo)號而未檢查的點v出發(fā)，對于邊<w,v>，如果（B），則可以對w進行標(biāo)號。A．flow(v，w)cap(v，w)B．flow(v，w)>0C．flow(v，w)<cap(v，w)D．flow(v，w)09．分治法中，將規(guī)模大的問題分解為多個規(guī)模較小的子問題，子問題必須滿足的條件是（BC）。A．一般不相互獨立B．相互獨立C．與原問題相同D．以上都不對10．二分查找的時間復(fù)雜度為（C）。A．O(nlogn)B．O(n)C．O(logn)D．以上都不對三、簡答題：（每題5分，共20分）1．簡述哈夫曼編碼算法的思想。答：該算法的基本思想是以字符的使用頻率做權(quán)構(gòu)建一棵哈夫曼樹。首先將n的字符分別看做以其為根的樹，構(gòu)成n棵樹的一個集合；（1分）然后每次從樹的集合中取出雙親為0且權(quán)值最小的兩棵樹作為左、右子樹，構(gòu)造一棵新樹；（2分）新樹根結(jié)點的權(quán)值為其左右孩子結(jié)點權(quán)之和，將新樹插入到樹的集合中；（1分）算法直到樹的集合中只有一棵樹為止。（1分）2．簡述合并排序算法的思想。答：（1）分解：將待排序元素分成大小大致相同的兩個子序列。（1分）（2）求解子問題：用合并排序法分別對兩個子序列遞歸地進行排序。（2分）（3）合并：將排好序的有序子序列進行合并，得到符合要求的有序序列。（2分）3．簡述動態(tài)規(guī)劃算法的求解步驟。答：（1）最優(yōu)子結(jié)構(gòu)性質(zhì)分析。（2分）（2）遞歸定義最優(yōu)值（即建立遞歸式或動態(tài)規(guī)劃方程）。（1分）（3）以自底向上的方式計算出最優(yōu)值，并記錄相關(guān)信息。（1分）（4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造出最優(yōu)解。（1分）4．簡述回溯法的搜索思想。答：從根開始，以深度優(yōu)先搜索的方式進行搜索。（1分）根結(jié)點是活結(jié)點并且是當(dāng)前的擴展結(jié)點。在搜索的過程中，當(dāng)前的擴展結(jié)點向縱深方向移向一個新結(jié)點，判斷該新結(jié)點是否滿足隱約束，如果滿足，則新結(jié)點成為活結(jié)點，并且成為當(dāng)前的擴展結(jié)點，繼續(xù)深一層的搜索；（1分）如果不滿足，則換該新結(jié)點的兄弟結(jié)點（擴展結(jié)點的其它分支）繼續(xù)搜索；（1分）如果新結(jié)點沒有兄弟結(jié)點，或其兄弟結(jié)點已全部搜索完畢，則擴展結(jié)點成為死結(jié)點，搜索回溯到其父結(jié)點處繼續(xù)進行。（1分）搜索過程直到找到問題的解或根結(jié)點變成死結(jié)點為止。（1分）四、求解題：（每題10分，共30分）1．用動態(tài)規(guī)劃中的跳躍點算法求解如下問題：有5個物品，其重量分別為2,2,6,5,4，價值分別為6,3,5,4,6。背包容量為10，物品不可分割，求裝入背包的物品和獲得的最大價值。（要求：先寫出求解公式，然后寫出求解過程，最后給出最優(yōu)解和最優(yōu)值）解：p[0]={(0，0)}（1分）q[i-1]=p[i-1](wi，vi)={(j+wi，C[i][j]+vi)|(j，C[i][j])p[i-1]，j+wiW}（1分）p[i]=p[i-1]q[i-1]去掉受控點。（2分）q[0]=p[0](w1，v1)={(2，6)}p[1]=p[0]q[0]={(0，0)，(2，6)}（1分）q[1]=p[1](w2，v2)={(2，3)，(4，9)}p[2]=p[1]q[1]={(0，0)，(2，6)，(4，9)}。（1分）q[2]=p[2](w3，v3)={(6，5)，(8，11)，(10，14)}p[3]={(0，0)，(2，6)，(4，9)，(8，11)，(10，14)}。（1分）q[3]=p[3](w4，v4)={(5，4)，(7，10)，(9，13)}。p[4]={(0，0)，(2，6)，(4，9)，(7，10)，(8，11)，(9，13)，(10，14)}。（1分）q[4]={(4，6)，(6，12)，(8，15)}。p[5]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}。（1分）該問題的最優(yōu)解為(1，1，0，0，1)，最優(yōu)值為15。（1分）不完全正確者酌情扣分。2．用分支限界法解4皇后問題（要求：指明搜索范圍，解空間結(jié)構(gòu)，搜索時用的剪枝函數(shù)，并畫出搜索樹）解：（1）明確搜索范圍，定義解空間（2分）解的形式為（x1,x2,x3,x4）x1的取值均為1,2,3,4,x2的取值均為{1,2,3,4}-{x1},x3的取值均為{1,2,3,4}-{x1,x2},x4的取值均為{1,2,3,4}-{x1,x2,x3}）（2）解空間的組織結(jié)構(gòu)（2分）滿4叉樹（排列樹）（3）搜索時的剪枝函數(shù)（2分）BooLPlace（intk）{for(inti=1;i<k;i++)if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))returnfalse;returntrue;}或BooLPlace（intk）{for(inti=1;i<k;i++)if(abs(x[i]-x[k])==abs(i-k))returnfalse;returntrue;}（4）搜索樹（4分）不完全正確者酌情扣分3．給定下圖所示的網(wǎng)絡(luò)G=（V，E）及網(wǎng)絡(luò)可行流flow，源點為1，匯點為6。找出該網(wǎng)絡(luò)對應(yīng)可行流flow的殘余網(wǎng)絡(luò)G*。（要求：先寫出網(wǎng)絡(luò)G和殘余網(wǎng)絡(luò)G*的對應(yīng)關(guān)系，再畫出殘余網(wǎng)絡(luò)。）解：（1）V(G)=V(G*)，即兩者頂點集合完全相同；（1分）（2）網(wǎng)絡(luò)G中的每一條邊對應(yīng)于G*中的一條邊或兩條邊；設(shè)<x，y>是G的一條邊。當(dāng)flow(x，y)=0時，對應(yīng)G*中同方向的一條邊<x，y>且該邊的容量為cap(x，y)；（1分）當(dāng)flow(x，y)=cap(x，y)時，對應(yīng)G*中反方向的一條邊<y，x>且該邊的容量為cap(x，y)；（1分）當(dāng)0<flow(x，y)<cap(x，y)時，對應(yīng)G*中的兩條邊，一條是同方向的