PAGEPAGE1系系專業班級姓名學號課程：算法設計與分析A3卷答案（啟用前保密）題號一二三四五總分得分一、選擇題（每小題2分，共10分）1．下列說法錯誤的是（C）。A．算法是程序在計算機上的具體實現。B．算法是用計算機編程語言翻譯的結果。C．算法能直接在計算機上執行。D．程序能直接在計算機上執行。2．對于函數f(n)=10，g(n)=log10，下列說法錯誤的是（D）。A．f(n)=(g(n))B．f(n)=(g(n))C．f(n)=(g(n))D．以上說法不全對3．用貪心法解決背包問題時所用的貪心策略是（C）。A．重量小的物品優先裝入背包B．價值大的物品優先裝入背包C．單位重量的價值大的物品優先裝入背包D．單位重量的價值小的物品優先裝入背包4.回溯法求解n個頂點的圖的m著色問題時，算法在最壞情況下的時間復雜度是（A）。A．O(nmn)B．O(n2)C．O(n2n)D．O(2n)5給定有序序列T[]={1,4,6,8,10,12}，現在要用二分搜索算法查找指定元素x=9是否出現在序列T中，元素x要和序列元素比較（B）次能夠得出結論。A．5B．3C．4D．2二、填空題（每空2分，共30分）1．算法復雜性是指算法在計算機上運行時所消耗的計算機資源的量。最重要的計算機資源是時間資源和空間資源。2．二分搜索算法在最壞情況下的時間復雜度是logn。3．回溯法算法框架中定義問題的解空間時，解的形式是(x1,x2,…,xn)；解空間結構的組織形式通常有子集樹、排列樹、滿m叉樹。4．分支限界法中，從活結點表中選擇下一個擴展結點的不同方式導致了不同的分支限界法，最常見的有隊列式分支限界法和優先隊列式分支限界法。5．一般情況下，可將隨機化算法大致分成4類，分別是數值隨機化算法、拉斯維加斯算法、舍伍德算法、蒙特卡羅算法。6．一般線性規劃問題的約束條件如果是大于等于的約束，可以通過去掉一個非負變量的方法將其轉換為等于的約束7．給定一個網絡G=(V,E)及其上的可行流flow，假設網絡G上的某條邊(v,w)的流量為0，容量為105，那么該邊對應于殘流網絡中同方向的一條邊，它的容量為105。8．用A[1:n]表示A1…An連乘，給定A[1:10]，用動態規劃算法求解時，用來存儲各子問題最優值的二維數組共有100個存儲單元。三、簡答題（每小題5分，共20分）1．簡述分治法的特征。答：分治算法具有以下特征：（1）問題規模足夠小時容易解決；（2）將規模大的問題分成規模較小的子問題；（3）子問題相互獨立；（4）子問題的解決方法與原問題相同；（5）遞歸解決子問題；（6）子問題的解能夠合并成原問題的解。2．簡述動態規劃求解最優化問題的步驟。答：動態規劃求解最優化問題的步驟有如下四步：找出最優解的性質，并刻劃其結構特征。遞歸地定義最優值。以自底向上的方式計算出最優值。根據計算最優值時得到的信息，構造最優解3．簡述求解單源最短路徑問題的Dijkstra算法思想。答：初始時令S={源點}，Dist數組記錄最短特殊路徑長度，重復做如下操作：選擇一條特殊路徑長度最短的，將其連接的V-S中的點加入到S中。同時考察有沒有更優的特殊路徑出現。若有，則修正。算法直到S=頂點全集V為止。根據前驅數組的記錄，構造最優解。4．簡述數值隨機化算法的特點并舉例說明。答：數值隨機化算法是用隨機的方法估算數值的大小，一般用于求問題的近似解，近似解的精確程度取決于算法的運行時間，運行時間越多，近似解的精確程度越高。如用投點實驗估算的大小，估算的精確程度取決于做實驗的次數，做實驗的次數越多，估算值的精度越高，耗時就越多，反之，做實驗的次數越少，估算值的精度越低，耗時就越少。四、求解題（5+5+9+11=30分）1．（5分）采用快速排序算法將給定序列5,3,8,2,1,9,23,12,16由小到大排序。(要求：只寫出首次分解得到兩個子問題的過程、遞歸的結果、子問題的解合并成原問題的解的過程)解：（1）基準元素為5；（2）劃分的過程和結果如下：設置兩個工作指針i和j，i指向元素5，j指向元素16所在的位置加1，第一次指針i停留在元素8的位置，指針j停留在元素1的位置，將元素8和1交換位置得到序列5,3,1,2,8,9,23,12,16。在上述得到的序列基礎上重復，第二次指針i停留在元素8的位置，指針j停留在元素2的位置，此時i>j，故將元素2和基準元素交換位置，得到序列[2,3,1]5[8,9,23,12,16]。（3）得到的兩個子問題分別是[2,3,1]和[8,9,23,12,16]（4）遞歸的結果為[1,2,3]和[8,9,12,16,23]此時整個序列有序，即：1,2,3,5,8,9,12,16,23。2．（5分）請用Prim算法求解如下圖所示的最小生成樹（要求：寫出生成最小生成樹的過程）解：生成最小生成樹的過程如下：3．（9分）給定7個作業，要在兩臺機器M1、M2組成的流水線上完成加工。每個作業都是現在M1上加工，然在M2上加工。在M1上處理時間為（a1,a2,a3,a4,a5,a6,a7）=(2,5,7,10,5,3,8)，在M2上處理時間為(b1,b2,b3,b4,b5,b6,b7)=(3,8,2,11,5,4,4)，按照流水作業調度問題的Johnson算法步驟，給出該問題的最優調度方案。（要求：先寫Johnson算法步驟，再給出每一步的結果）解：1)N1={i|ai<bi}={1246}N2={i|ai≥bi}={357}2)將N1按照ai非減序排序，將N2按照bi非增序排序。N1={1624}N2={573}3）N1接N2即為所求的最優調度N=N1N2={1624573}4．（11分）用單純形算法求解下列線性規劃問題。解：將線性規劃問題轉化為約束標準型如下：令=-z，則由約束標準形式可知：x1,x5,x6是基本變量，x2,x3,x4是非基本變量，建立初始單純形表如表7-2所示。由此可得，基本可行解為X(0)=（7,0,0,0,12,10），=0。初始單純形表如表1所示。由表1可知：x3為入基變量，x5為離基變量，根據迭代公式得出如表2所示的單純形表。由此可得，基本可行解為X(1)=（10,0,3,0,0,1）,=9由表2可知：x2為入基變量，x1為離基變量，根據迭代公式迭代得如表3所示的單純形表。由此可得，基本可行解為X(2)=（0,4,5,0,0,11）,=11。同時，由表3可知，所有檢驗數均小于等于0，故X(2)=（0,4,5,0,0,11）為該線性規劃問題的唯一最優解，其最優值z=-11。五、算法設計（10分）說明：選用任意算法設計策略。要求：寫出算法策略的思想；寫出算法實現的主要步驟；題目：n后問題，給出一種放置方案。解：策略1：回溯法（定義解的結構，確定解空間樹，確定約束函數和限界函數，深度優先方式搜索，判斷當前是否到葉子節點，若到了葉子節點，則修正最優值，若是中間節點，左子樹判斷是否滿足約束條件，若滿足，則深一步搜索，否則剪枝。右子樹判斷是否滿足限界函數，若滿足，則深一步搜索，若不滿足，則剪枝）策略2：分支限界法（定義解的結構，確定解空間樹，確定約束函數和限界函數，當前背包的價值上界高者優先方式搜索