Algorithms

DesignTechniquesandAnalysis

算法設計技巧與分析

期末總復習課考試題型各章復習提要

考試題型簡答題(5小題，共20分)快速排序和歸并排序兩者中哪個的平均比較次數(shù)要多。

假定圖用鄰接矩陣表示，圖的寬度優(yōu)先遍歷算法的時間復雜度是什么？如果圖用鄰接表來表示呢？

考試題型計算題(2小題，共10分)解下列遞歸方程：

f(n)=2f(n-1)+3f(n-2),n>2;f(0)=1,f(1)=0.使用記號

表示下列函數(shù)：

n3+

10nlog50n+100n

考試題型算法應用題(4小題，共50分)歸納技術、分治法：

考慮使用歸并排序給序列{10,8,2,4,12,6}排序。請給出算法執(zhí)行中各次劃分、合并的結果。（可畫圖表示）動態(tài)規(guī)劃：使用動態(tài)規(guī)劃法來求解下列0/1背包問題的實例：n=5,W={2,1,2,3,3}，P={8,6,7,9,8}，M=6。給出主要步驟。

考試題型算法應用題(4小題，共50分)貪心法：

考慮用哈夫曼算法來找字符a,b,c,d,e,f的最優(yōu)編碼。這些字符出現(xiàn)在文件中的頻數(shù)之比為8:3:5:4:11:7。試給出字符a,b,c,d,e,f的一種最優(yōu)編碼。要求給出主要步驟的結果。

考試題型算法應用題(4小題，共50分)設計一個回溯算法來求解k-著色問題：給定無向圖G=<V,E>,要求使用k種顏色來給圖中每個結點著色（每個結點使用k種顏色之一），使得沒有兩個相鄰的結點顏色相同。

(a)

給出解向量形式，并畫出當n=3,k=3時的搜索樹。

(b)

給出剪枝操作。

(c)最壞情況下算法在搜索樹上會訪問到多少個結點？分析算法的時間復雜度。

考試題型算法設計與分析題(1小題，共10分)考慮在序列A[1..n]中找最大最小元素的問題。一個分治算法描述如下：如果n≤2就直接求解。否則，將序列等分成兩個子序列A[1..n/2]和A[n/2+1..n]，分別找出這兩子序列的最大最小元素x1,y1和x2,y2；然后據(jù)此可求出A[1..n]的最大元素x=max{x1,x2}及最小元素y=min{y1,y2}。試給出該算法計算時間T(n)滿足的遞歸方程，并解方程來確定算法的時間復雜度。假定n=2k（k為正整數(shù)）。

考試題型

實驗題目（1小題，共10分)[實驗1]快速排序與歸并排序平均運行時間之比較

——根據(jù)實驗內容設計問答題[實驗2]動態(tài)規(guī)劃法的簡單應用

——根據(jù)實驗內容設計問答題[實驗3]回溯法的應用

——根據(jù)實驗內容設計問答題各章復習要點第一章算法分析的基本概念復習范圍

1.1--1.14復習要點評價算法性能的幾個標準正確性、易讀性、健壯性、算法的時間和空間性能：高效率和低存儲空間算法復雜度概念漸近記號

、

、

的含義P14最優(yōu)算法的概念P20最好、最壞、平均時間(空間)復雜度P26分析復雜度的主要步驟，各步驟的要點（包括輸入大小的確定P31、基本操作的選擇P24等）相關習題類型

1.14---1.16各章復習要點

第二章

算法分析的數(shù)學基礎復習范圍2.7--2.8

復習要點簡單求和公式P48定積分近似求和P50兩個重要公式幾個例子2.15~2.17簡單遞歸方程的解法P52相關習題類型

2.16,2.17,2.18,2.19各章復習要點

第五章

歸納技術復習范圍5.3,5.4,5.5,5.7復習要點各算法的基本思想能簡單應用相關習題類型

5.7-5.9,5.17-5.18,5.33各章復習要點

第六章分治法復習范圍6.1--6.4,6.6--6.7,6.8復習要點分治法的適用范圍、基本思想各算法的基本思想、復雜度結論能簡單應用相關習題類型

6.10,6.31,6.36,6.44各章復習要點

第七章動態(tài)規(guī)劃法復習范圍

7.2--7.6

復習要點動態(tài)規(guī)法法的適用范圍、基本步驟各算法的基本思想能簡單應用相關習題類型

7.5,7.9,7.15,7.21,7.32,7.33,7.34各章復習要點

第八章貪心法復習范圍

8.1----8.5

復習要點貪心法的基本思想各算法的基本思想、復雜度結論

(Dijkstra、Prim算法的改進不作要求)

能簡單應用

相關習題類型

8.10,8.13，8.23,8.24，8.31各章復習要點

第九章圖的遍歷復習范圍9.1，9.2，9.4復習要點深度優(yōu)先遍歷和寬度優(yōu)先遍歷的基本思路、時空復雜度注意：應用中需要用到的邊的幾種類型相關習題類型9.1,9.2,9.6,9.19,9.20各章復習要