1、計算機算法設計與分析復習題一、填空題1、一個算法復雜性的高低體現在計算機運行該算法所需的時間和存儲器資源上，因此算法的復雜性有 時間 復雜性和空間復雜性之分。2、出自于“平衡子問題”的思想，通常分治法在分割原問題，形成若干子問題時，這些子問題的規模都大致 相同 。3、使用二分搜索算法在n個有序元素表中搜索一個特定元素，在最佳情況下，搜索的時間復雜性為O（1），在最壞情況下，搜索的時間復雜性為O（ logn ）。4、已知一個分治算法耗費的計算時間T(n)，T(n)滿足如下遞歸方程：解得此遞歸方可得T(n)= O（ ）。5、動態規劃算法有一個變形方法 備忘錄方法 。這種方法不同于動態規劃算法“自底

2、向上”的填充方向，而是“自頂向下”的遞歸方向，為每個解過的子問題建立了備忘錄以備需要時查看，同樣也可避免相同子問題的重復求解。6遞歸的二分查找算法在divide階段所花的時間是 O(1) ，conquer階段所花的時間是 T(n/2) ，算法的時間復雜度是 O( log n) 。 7Prim算法利用貪心 策略求解 最小生成樹問題，其時間復雜度是 O(n2) 。8背包問題可用 貪心法 ， 回溯法 等策略求解。9用動態規劃算法計算矩陣連乘問題的最優值所花的時間是 O(n3) ， 子問題空間大小是 O(n2) 。10圖的m著色問題可用 回溯 法求解，其解空間樹中葉子結點個數是 mn ，解空間樹中每個

3、內結點的孩子數是 m 。11單源最短路徑問題可用貪心法 、 分支限界 等策略求解。12、一個算法的優劣可以用（時間復雜度）與（空間復雜度）與來衡量。13、回溯法在問題的解空間中，按（深度優先方式）從根結點出發搜索解空間樹。14、直接或間接地調用自身的算法稱為（遞歸算法）。15、q 記號在算法復雜性的表示法中表示（漸進確界或緊致界）。16、在分治法中，使子問題規模大致相等的做法是出自一種（平衡(banlancing)子問題）的思想。17、動態規劃算法適用于解（具有某種最優性質）問題。18、貪心算法做出的選擇只是（在某種意義上的局部）最優選擇。19、最優子結構性質的含義是（問題的最優解包含其子問題

4、的最優解）。20、回溯法按（深度優先）策略從根結點出發搜索解空間樹。21、拉斯維加斯算法找到的解一定是（正確解）。22、按照符號O的定義O(f)+O(g)等于O(maxf(n),g(n)。23、二分搜索技術是運用（分治）策略的典型例子。24、動態規劃算法中，通常不同子問題的個數隨問題規模呈（多項式）級增長。25、（最優子結構性質）和（子問題重疊性質）是采用動態規劃算法的兩個基本要素。26、（最優子結構性質）和（貪心選擇性質）是貪心算法的基本要素。27、（選擇能產生最優解的貪心準則）是設計貪心算法的核心問題。28、分支限界法常以（廣度優先） 或（以最小耗費(最大效益)優先）的方式搜索問題的解空間

5、樹。29、貪心選擇性質是指所求問題的整體最優解可以通過一系列（局部最優）的選擇，即貪心選擇達到。30、按照活結點表的組織方式的不同，分支限界法包括（隊列式(FIFO)分支限界法）和（優先隊列式分支限界法）兩種形式。31、如果對于同一實例，蒙特卡洛算法不會給出兩個不同的正確解答，則稱該蒙特卡洛算法是（一致的）。32、哈夫曼編碼可利用（貪心法）算法實現。33概率算法有數值概率算法，蒙特卡羅（Monte Carlo）算法，拉斯維加斯（Las Vegas）算法和舍伍德（Sherwood）算法34以自頂向下的方式求解最優解的有（貪心算法）35、下列算法中通常以自頂向下的方式求解最優解的是（貪心法）。 3

6、6、在對問題的解空間樹進行搜索的方法中,一個活結點有多次機會成為活結點的是（回溯法）37、旅行售貨員問題不能用（）解決 可以用回溯法解決，分支限界法，NP完全性理論與近似算法38、貪心算法不能解決（0-1背包問題 N皇后問題）。可以解決背包問題39、投點法是（概率算法）的一種。40、若線性規劃問題存在最優解，它一定不在（可行域內部）二、簡答題1、（8分）寫出下列復雜性函數的偏序關系（即按照漸進階從低到高排序）：參考解答：2、（8分）現在有8位運動員要進行網球循環賽，要設計一個滿足以下要求的比賽日程表：（1） 每個選手必須與其他選手各賽一次；（2） 每個選手一天只能賽一次；（3） 循環賽一共進行

7、n 1天。請利用分治法的思想，給這8位運動員設計一個合理的比賽日程。參考解答：12345678214365873412785643218765567812346587214378563412876543213、（8分）某體育館有一羽毛球場出租，現在總共有10位客戶申請租用此羽毛球場，每個客戶所租用的時間單元如下表所示，s(i)表示開始租用時刻，f(i)表示結束租用時刻，10個客戶的申請如下表所示：i12345678910s(i)03153511886f(i)65498713121110同一時刻，該羽毛球場只能租借給一位客戶，請設計一個租用安排方案，在這10位客戶里面，使得體育館能盡可能滿足多位

8、客戶的需求，并算出針對上表的10個客戶申請，最多可以安排幾位客戶申請。參考解答：將這10位客戶的申請按照結束時間f(i)遞增排序，如下表：i12345678910s(i(i)45678910111213選擇申請1（1,4）依次檢查后續客戶申請，只要與已選擇的申請相容不沖突，則選擇該申請。直到所有申請檢查完畢。申請4（5,7）、申請8（8,11）、申請10（11,13）最后，可以滿足：申請1（1,4）、申請4（5,7）、申請8（8,11）、申請10（11,13）共4個客戶申請。這已經是可以滿足的最大客戶人數。4、（8分）對于矩陣連乘所需最少數乘次數問題，其遞歸關系式為：

9、其中mi，j為計算矩陣連乘AiAj所需的最少數乘次數，pi-1為矩陣Ai的行，為矩陣Ai的列。現有四個矩陣，其中各矩陣維數分別為：A1A2A3A450´1010´4040´3030´5p 0´ p 1p 1´ p 2p 2´ p 3p 3´ p 4請根據以上的遞歸關系，計算出矩陣連乘積A1A2A3A4所需要的最少數乘次數。參考解答：5、（8分）有這樣一類特殊0-1背包問題：可選物品重量越輕的物品價值越高。n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n為物品個數，c為背包

10、載重量，P表示物品的價值，W表示物品的重量。請問對于此0-1背包問題，應如何選擇放進去的物品，才能使到放進背包的物品總價值最大，能獲得的最大總價值多少？參考解答：因為該01背包問題比較特殊，恰好重量越輕的物品價值越高，所以優先取重量輕的物品放進背包。最終可以把重量分別為2，3，4，5的三個物品放進背包，得到的價值和為15 + 8 + 6 + 4 = 33，為最大值。6.請用英文寫出三種以上能求解0-1背包問題的設計算法策略。參考解答：Dynamic Programming Backtrack Branch-and-Bound （每答對一條給一分）7.請說明動態規劃方法為什么需要最優子結構性質。

11、參考解答：最優子結構性質是指大問題的最優解包含子問題的最優解。動態規劃方法是自底向上計算各個子問題的最優解，即先計算子問題的最優解，然后再利用子問題的最優解構造大問題的最優解，因此需要最優子結構8.請說明：(1)優先隊列可用什么數據結構實現？(2)優先隊列插入算法基本思想？(3)優先隊列插入算法時間復雜度？參考解答：（1）堆。(1分) （2）在小根堆中，將元素x插入到堆的末尾，然后將元素x的關鍵字與其雙親的關鍵字比較，若元素x的關鍵字小于其雙親的關鍵字，則將元素x與其雙親交換，然后再將元素x與其新雙親的關鍵字相比，直到元素x的關鍵字大于雙親的關鍵字，或元素x到根為止。(4分)（3）O( log

12、 n)（1分）9.設計動態規劃算法的主要步驟是怎么的？請簡述。參考解答：（1）找出最優解的性質，并刻劃其結構特征。(6分) （2）遞歸地定義最優值。 （3）以自底向上的方式計算出最優值。（4）根據計算最優值時得到的信息，構造最優解。10.分治法所能解決的問題一般具有哪幾個特征？請簡述。參考解答：（1）該問題的規模縮小到一定的程度就可以容易地解決；(6分) （2）該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質;（3） 利用該問題分解出的子問題的解可以合并為該問題的解； （4）原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。11.分支限界法的搜索策略是

13、什么？參考解答：在擴展結點處，先生成其所有的兒子結點（分支），然后再從當前的活結點表中選擇下一個擴展結點。為了有效地選擇下一擴展結點，加速搜索的進程，在每一個活結點處，計算一個函數值（限界），并根據函數值，從當前活結點表中選擇一個最有利的結點作為擴展結點，使搜索朝著解空間上有最優解的分支推進，以便盡快地找出一個最優解。(6分)12 算法的要特性是什么？ 參考解答：確定性、可實現性、輸入、輸出、有窮性13 算法分析的目的是什么？參考解答：分析算法占用計算機資源的情況，對算法做出比較和評價，設計出額更好的算法。14 算法的時間復雜性與問題的什么因素相關？參考解答：算法的時間復雜性與問題的規模相關，

14、是問題大小n的函數。15 算法的漸進時間復雜性的含義？參考解答：當問題的規模n趨向無窮大時，影響算法效率的重要因素是T(n)的數量級，而其他因素僅是使時間復雜度相差常數倍，因此可以用T(n)的數量級(階)評價算法。時間復雜度T(n)的數量級(階)稱為漸進時間復雜性。16 最壞情況下的時間復雜性和平均時間復雜性有什么不同？參考解答：最壞情況下的時間復雜性和平均時間復雜性考察的是n固定時，不同輸入實例下的算法所耗時間。最壞情況下的時間復雜性取的輸入實例中最大的時間復雜度：W(n) = max T(n，I) , IDn平均時間復雜性是所有輸入實例的處理時間與各自概率的乘積和：A(n) =P(I)T(

15、n，I) IDn17 簡述二分檢索（折半查找）算法的基本過程。參考解答：設輸入是一個按非降次序排列的元素表Ai：j 和x，選取A(i+j)/2與x比較，如果A(i+j)/2=x，則返回(i+j)/2，如果A(i+j)/2<x，則Ai：(i+j)/2-1找x，否則在A (i+j)/2+1：j 找x。上述過程被反復遞歸調用。18 背包問題的目標函數和貪心算法最優化量度相同嗎？參考解答：不相同。目標函數：獲得最大利潤。最優量度：最大利潤/重量比。19 采用回溯法求解的問題，其解如何表示？有什么規定？參考解答：問題的解可以表示為n元組：（x1,x2,xn），xiSi, Si為有窮集合，xiSi,

16、 （x1,x2,xn）具備完備性，即（x1,x2,xn）是合理的，則（x1,x2,xi）(i<n)一定合理。20 回溯法的搜索特點是什么？ 參考解答：在解空間樹上跳躍式地深度優先搜索，即用判定函數考察xk的取值，如果xk是合理的就搜索xk為根節點的子樹，如果xk取完了所有的值，便回溯到xk-1。21 n皇后問題回溯算法的判別函數place的基本流程是什么？參考解答：將第K行的皇后分別與前k-1行的皇后比較，看是否與它們相容，如果不相容就返回false，測試完畢則返回true。22 為什么用分治法設計的算法一般有遞歸調用？參考解答：子問題的規模還很大時，必須繼續使用分治法，反復分治，必然要

17、用到遞歸.23 為什么要分析最壞情況下的算法時間復雜性？ 參考解答：最壞情況下的時間復雜性決定算法的優劣，并且最壞情況下的時間復雜性較平均時間復雜性游可操作性。24 簡述漸進時間復雜性上界的定義。參考解答：T(n)是某算法的時間復雜性函數，f(n)是一簡單函數，存在正整數No和C，nNo，有T(n)<f(n)，這種關系記作T(n)=O(f(n)。25 二分檢索算法最多的比較次數？參考解答：二分檢索算法的最多的比較次數為 log n 。26 快速排序算法最壞情況下需要多少次比較運算？參考解答：最壞情況下快速排序退化成冒泡排序，需要比較n2次。27 貪心算法的基本思想？參考解答：是一種依據最

18、優化量度依次選擇輸入的分級處理方法。基本思路是：首先根據題意，選取一種量度標準；然后按這種量度標準對這n個輸入排序，依次選擇輸入量加入部分解中。如果當前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中28 回溯法的解（x1,x2,xn）的隱約束一般指什么？參考解答：回溯法的解（x1,x2,xn）的隱約束一般指個元素之間應滿足的某種關系。29 闡述歸并排序的分治思路。參考解答：講數組一分為二，分別對每個集合單獨排序，然后將已排序的兩個序列歸并成一個含n個元素的分好類的序列。如果分割后子問題還很大，則繼續分治，直到一個元素。30 快速排序的基本思想是什么。 參考解答：快速排序的基本思想

19、是在待排序的N個記錄中任意取一個記錄，把該記錄放在最終位置后，數據序列被此記錄分成兩部分。所有關鍵字比該記錄關鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復上述過程，直到每一部分內只有一個記錄為止。31 什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數據結構？參考解答：在定義一個過程或者函數的時候又出現了調用本過程或者函數的成分，既調用它自己本身，這稱為直接遞歸。如果過程或者函數P調用過程或者函數Q，Q又調用P，這個稱為間接遞歸。消除遞歸一般要用到棧這種數據結構。32 什么是哈密頓環問題？參考解答：哈密頓環是指一條沿著圖G的

20、N條邊環行的路徑，它的訪問每個節點一次并且返回它的開始位置。33 用回溯法求解哈密頓環，如何定義判定函數？參考解答：當前選擇的節點Xk是從未到過的節點,即XkXi(i=1,2,k-1)，且C(Xk-1, Xk)，如果k=-1，則C(Xk, X1) 。34 請寫出prim算法的基本思想。參考解答：思路是：最初生成樹T為空，依次向內加入與樹有最小鄰接邊的n-1條邊。處理過程：首先加入最小代價的一條邊到T，根據各節點到T的鄰接邊排序，選擇最小邊加入，新邊加入后，修改由于新邊所改變的鄰接邊排序，再選擇下一條邊加入，直至加入n-1條邊。三、算法設計題1.【最長上升子序列問題】（8分） 提示：此題可采用動

21、態規劃算法實現對于給定的一個序列，。我們可以得到一些遞增上升的子序列，這里。比如，對于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中最長的長度是4，比如子序列(1, 3, 5, 8)。你的任務：就是對于給定的序列，求出最長上升子序列的長度。要求寫出你設計的算法思想及遞推函數的公式表達。.參考解答：設表示：從左向右掃描過來直到以元素結尾的序列，獲得的最長上升子序列的長度，且子序列包含元素（）。即，是從，到中找最大的一個值，再加1。或者就是1。主要是看ai這個元素能否加入到之前已經獲得的最長上升子序列，如果能加入，是之前

22、已獲得的最長上升子序列長度加一；如果不能加入，就取這最后一個元素作為一個單獨子序列，長度為1。最后，所要求的整個序列的最長公共子序列長度為maxf(i): 1<=i<=n例如，對于序列：4 2 6 3 1 5 2i1234567array4263152f(i)1122132評分準則：1) 答到使用動態規劃算法，并且推導出動態規劃算法的遞推函數公式表達，邊界設定清晰，本題即可得滿分；（閱卷時仔細看遞推公式表達，公式表達含義正確即可，因其表達形式可能不唯一）2) 說明使用動態規劃算法，但對遞推函數表達錯誤或含糊，扣2分以上；3) 其它情況酌情考慮。2（10分）對下圖所示的連通網絡G，用

23、克魯斯卡爾(Kruskal)算法求G的最小生成樹T,請寫出在算法執行過程中，依次加入T的邊集TE中的邊。說明該算法的貪心策略和算法的基本思想，并簡要分析算法的時間復雜度。12345618111715192126679參考解答TE=(3,4), (2,3),(1,5),（4,6）（4,5） （5分）貪心策略是每次都在連接兩個不同連通分量的邊中選權值最小的邊。基本思想：首先將圖中所有頂點都放到生成樹中，然后每次都在連接兩個不同連通分量的邊中選權值最小的邊，將其放入生成樹中，直到生成樹中有n-1條邊。（4分）時間復雜度為：O(eloge) （1分）3.（15分）考慮n=3的批處理作業調度實例：tji

24、機器1機器2作業1110作業231作業321其中tji是作業Ji需要在機器j上處理的時間。對于給定的3個作業，制定一個最佳作業調度方案，使其完成時間和達到最小。要求：（1）畫出該問題的解空間樹； （5分）（2）寫出該問題的剪枝策略(即限界條件),要求只保留第一個最優解;(2分)（3）按優先隊列式分支限界法搜索解空間樹，并用剪枝策略對解空間樹中該剪枝的位置打´； （5分）（4）給出最優解及最優值。 （3分）參考解答（1）5分2113231231323V021113491618232325303336361026 （2）若當前代價f >= 當前最優解代價bestf，則剪枝。2分（3

25、）見（1）中所畫的圖。5分（4）最優解為3，1，2，最優值為25。3分4.【Gray碼構造問題】（8分） 提示：此題可采用分治遞歸算法實現問題描述：“格雷碼”是一個長度為的序列，滿足：（a）每個元素都是長度為n比特的串（b）序列中無相同元素（c）連續的兩個元素恰好只有1個比特不同例如：n=2時，格雷碼為00，01，11，10。Gray碼是一種編碼，這種編碼可以避免在讀取時，因各數據位時序上的差異造成的誤讀。格雷碼在工程上有廣泛應用。但格雷碼不便于運算，請你設計一種構造方法，輸入長度序列n，輸出格雷碼（你只要做出一種構造方案即可，格雷碼并不唯一）。參考解答：此題可用分治法解決。當n1時，輸出格雷

26、碼0, 1當n>1時，格雷碼的長度為，即共有個碼序列。此時，將問題一分為二，即上半部分和下半部分。上半部分最高位設為0，下半部分最高位設為1。剩下n-1位的格雷碼的構造采用遞歸的思路。評分準則：1) 答到使用分治算法，并且推導出分治算法的過程，邊界設定清晰（即當僅輸出1位的格雷碼如何處理），本題即可得滿分；2) 說明使用分治算法，但漏邊界條件，扣2分以上；其它情況酌情考慮。5.（13分）給定帶權有向圖（如下圖所示）G =(V,E)，其中每條邊的權是非負實數。另外，還給定V中的一個頂點，稱為源。現在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權之和。現采用Dijkstr

27、a算法計算從源頂點1到其它頂點間最短路徑。請將此過程填入下表中。43211初始dist5dist4dist3dist2uS迭代參考解答：（13分）6030501051，2，3，4，546030501031，2，4，339030501041，2，4210030601021，211003010-1初始dist5dist4dist3dist2uS迭代6.（13分）有0-1背包問題如下：n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n為物品個數，c為背包載重量，P表示物品的價值，W表示物品的重量。請問對于此0-1背包問題，應如何選擇放進去的物品，才能使到放進背包的物品總價值最大。P=(15，8，6，4，3，1) W=(2，3，4，5，8，10)，單位重量物品價值（7.5，2.67，1.5,0.8,0.375,0.1）參考解答：（13分）可知隨著物品的重量增加，物品的價值減少；因此可以用貪心算法來求解。以選取單位重量物品價值高為貪心策略。1.先把重量為2的物品放進背包，此時剩余載重量為17，P為15。2.把重量為3的物品放進背包，