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

PAGEPAGE1共3頁系系專業(yè)班級姓名考號（密封線內(nèi)不準答題）課程：算法設(shè)計與分析評卷人（簽名）：復(fù)核人（簽名）：題號一二三四五總分得分一、選擇題（每小題3分，共15分）1．算法與程序的主要區(qū)別在于算法具有（）。A．能行性B．確定性C．有限性D．輸入和輸出答案：C。2．對一個有序序列，以比較為基礎(chǔ)的搜索算法的最壞情況時間復(fù)雜性的下界為（）。A．Ω(n)B．Ω(n2)C.Ω(nlogn)D．Ω(logn)答案：D。3．背包問題：n=6，C=10，V(1:6)=(15,59,21,30,60,5)，W(1:6)=(1,5,2,3,6,1）。該問題的最大價值為（）。A．101B．110C．115D．120答案：C。4．矩陣連乘積問題：M1(5×10),M2(10×4),M3(4×6)。矩陣鏈乘M1M2M3需要的最少乘法次數(shù)為（）。A．348B．328C．720D．320答案：D。5．用貪心策略設(shè)計算法的關(guān)鍵是（）。A．將問題分解為多個子問題來分別處理B．選好貪心策略C．獲取各階段間的遞推關(guān)系式D．滿足最優(yōu)性原理答案：B。二、填空題（每小題4分，共20分）1．某算法的計算時間T(n)滿足遞歸關(guān)系式：T(n)=2T(n-1)+O(1)，n>1；T(1)=1。則T(n)=。答案：2n-1。2．用方法對狀態(tài)空間樹進行搜索時，每個結(jié)點有可能多次成為擴展結(jié)點。3．子集和數(shù)問題一般陳述如下：已知n+1個正數(shù)：wi(1≤i≤n)和M，要求找出wi的和數(shù)是M的所有子集。其解可以表示為n-元組(x1,x2,?,xn)，這里xi∈{0,1}，1≤i≤n。如果沒有選擇wi，則相應(yīng)的xi=0；如果選擇了wi，則xi=1。此解空間的空間樹上有個葉結(jié)點，共有個結(jié)點。答案：2n,2n+1-1。4．已知將兩個分別包含n個和m個記錄的已分類文件歸并在一起得到一個分類文件需作n+m次記錄移動。現(xiàn)有五個已分類文件F1,F2,F3,F4,F5，它們的記錄個數(shù)分別為25,40,15,10,40，將這五個文件歸并成一個分類文件需作次記錄移動。注：每次只能歸并兩個文件。答案：285。5．兩個序列A=“xyxxzxyzxy”和B=“zxzyyzxxyxxz”的最長的公共子序列的長度為________。其中一個最長公共子序列為。答案：6,xzyzxy。三、問答題（每小題5分，共20分）1.快速排序算法是根據(jù)分治策略來設(shè)計的，簡述其基本思想。答：快速分類算法是根據(jù)分治策略設(shè)計出來的算法。其關(guān)鍵步驟就是“劃分”：根據(jù)某個元素v為標準，將序列中的元素重新整理，使得整理后的序列中v之前的元素都不大于v，而v之后的元素都不小于v。此時，元素v即找到了其最終的位置。要得到序列的排序結(jié)果，再只需對v之前的元素和v之后的元素分別排序即可，這可通過遞歸處理來完成。2．簡述蒙特卡羅算法的特點及提高蒙特卡羅算法得到的為正確的概率的措施？答：在某些實際應(yīng)用中經(jīng)常會遇到一些問題，不論采用確定性算法還是概率算法都無法保證每次得到正確的解。蒙特卡羅算法在一般情況下，可以保證對問題的所有實例都以高概率給出正確解，但是通常無法判定一個具體解是否正確。使用蒙特卡羅算法肯定能得到問題的一個解，但是這個解未必是正確的。可以通過重復(fù)調(diào)用同一個蒙特卡洛算法多次來提高獲得正確解的概率。3．簡述回溯法的基本思想。答：回溯法的基本思想是：深度優(yōu)先搜索+剪枝。從根結(jié)點開始，以深度優(yōu)先的方式進行搜索，搜索的過程中，每搜索到一個結(jié)點，檢查是否滿足約束函數(shù)和限界函數(shù)，如果滿足，則更深一層的搜索，如果不滿足，則剪枝，搜索過程直到找到問題的解或所有活結(jié)點變成死結(jié)點為止?；厮莘ㄓ脕砬髥栴}的多個解。4．簡述最小生成樹的Kruskal算法的基本思想。答：按照圖中邊權(quán)由大到小的次序依次考慮每條邊是否加入最小生成樹中。當考慮到某條邊時，如果該邊與已經(jīng)加入到最小生成樹中的邊不形成回路，則將該邊加入進去。四、求解題1．（5分）設(shè)f(N)、g(N)是定義在正數(shù)集上的正函數(shù)。如果存在正的常數(shù)C和自然數(shù)N0，使得當N≥N0時有f(N)≤Cg(N)，則成函數(shù)f(N)當N充分大時上有界，且g(N)是它的一個上界，記為f(N)=O(g(N))。證明：O(f(N))+O(g(N))=O(max{f(N)，g(N)})。解：2．（8分）用動態(tài)規(guī)劃解決0-1背包問題的改進算法求解如下實例：n=4，c=12，v=（18，15，8，12），w=（10，2，3，4）。（要求：先寫出計算公式，再寫具體的求解過程，指出最優(yōu)值和最優(yōu)解）解：p[n+1]={(0,0)}p[i]=p[i+1]∪p[i+1](wi,vi)去掉受控點。P[5]={(0,0)}P[4]={(0,0),(4,12)}P[3]={(0,0),(3,8),(4,12),(7,20)}P[2]={(0,0),(2,15),(5,23),(6,27),(9,35)}P[1]={(0,0),(2,15),(5,23),(6,27),(9,35)}最優(yōu)值為35，最優(yōu)解為（0,1,1,1）3.（10分）用單純性算法求解下面線性規(guī)劃問題：maxz=-x2+3x3-2x4s.t.x1+3x2-x3+2x4=7-4x2+3x3+8x4≤102x2-4x3≥-12xi≥0（i=1,2,3,4）要求：（1）步驟描述（2）寫清每一迭代步的選擇，單純形表，可行解及可行解對應(yīng)的目標函數(shù)的值。解：線性規(guī)劃的約束標準型為：maxz=-x2+3x3-2x4s.t.x1+3x2-x3+2x4=7x5-4x2+3x3+8x4=10x6-2x2+4x3=12xi≥0（i=1,2,3,4,5,6）初始單純形表Cx2x3x4z0-13-2x173-12x510-438x612-240z=0,x=(7,0,0,0,10,12)第一步迭代（1）選入基變量x3（2）選離基變量x6（3）轉(zhuǎn)軸變換Cx2x6x4z91/2-3/4-2x1105/21/42x51-5/2-3/48x33-1/21/40z=9,x=(10,0,3,0,1,0)第二步迭代（1）選入基變量x2（2）選離基變量x1（3）轉(zhuǎn)軸變換Cx1x6x4z11-1/5-4/5-12/5x242/51/104/5x5111-1/210x351/53/102/5Z行非基變量的系數(shù)全部為負，迭代結(jié)束，最大值為11，最優(yōu)解為（0,4,5,0,11,0）4.（10分）單源最短路徑問題：在下圖實例上指定源點為1，目標點為6，應(yīng)用優(yōu)先隊列式分支限界法找出1到6的最短路徑。（要求寫明優(yōu)先級，畫出搜索樹，標出最短路徑）解：優(yōu)先級：當前結(jié)點所代表的最短路徑長度，長度越小，優(yōu)先級越高搜索樹：五、算法設(shè)計（共13分）：說明：任意選擇所使用的算法策略。要求：說明所使用的算法策略；寫出算法實現(xiàn)的主要步驟；題目：n后問題策略1：回溯法（定義解的結(jié)構(gòu)，確定解空間樹，確定約束函數(shù)，深度優(yōu)先方式搜索，判斷當前是否到葉子節(jié)點，若到了葉子節(jié)點，則找到了一種著色方案，將其方案輸出，并將方案個數(shù)加1，若是中間節(jié)點，判斷是否滿足約束條件，若滿足，