1、算法設計與分析復習要點一、單項選擇題（本大題共15小題，每小題2分，共30分）二、填空題（本大題共15空，每空1分，共15分）三、分析題（本大題共5小題，每小題5分，共25分）四、綜合題（本大題共4小題，1、2題每題6分，3題8分，4題10分，共30分）第2章，導引與基本數據結構：什么是算法, 算法的5個特性；對一個算法作出全面分析的兩個階段。P24O(g(n)，(g(n)，Q(g(n)的含義。多項式時間算法：可用多項式（函數）對其計算時間限界的算法。 常見的多項式限界函數所表示算法時間復雜度的排序： (1) <(logn) < (n) < (nlogn) < (n2)

2、 < (n3)Ø 指數時間算法：計算時間用指數函數限界的算法 常見的指數時間限界函數： (2n) < (n！) < (nn)什么是算法的復雜性：是該算法所需要的計算機資源的多少，它包括時間和空間資源。復習棧和隊列、樹、圖的基本知識，了解二元樹、完全二元樹，滿二元樹、二分檢索樹、了解圖的鄰接矩陣和鄰接表存儲方法。能寫出圖的深度優先序列和廣度優先序列。會求如下一些簡單的函數的上界表達式：3n2+10n =O(n2)第3、4章 遞歸與分治算法理解遞歸算法的優缺點，深刻理解遞歸算法的執行過程。如能寫出解決n階漢諾塔問題的解，并能分析寫出3階漢諾塔問題的遞歸執行軌跡。遞歸算法

3、的優點：結構清晰，可讀性強，容易用數學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。遞歸算法的缺點：運行效率較低，耗費的計算時間和占用的存儲空間都多。為了達到此目的，根據具體程序的特點對遞歸調用工作棧進行簡化，盡量減少棧操作，壓縮棧存儲空間以達到節省計算時間和存儲空間的目的。能求解或證明常見遞歸關系式，如n階漢諾塔問題的算法時間復雜度。分治法的基本思想：是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。掌握二分檢索算法，如給一個實例，可以模擬出low，hig，mid的運行軌跡。知道并

4、能證明二分檢索算法平均時間復雜度是Q( logn)掌握找最大和最小元素的遞歸分治算法。理解并掌握歸并分類（歸并排序）算法，能畫出用二元樹表示的歸并分類調用過程及合并過程。理解并能證明歸并分類算法的時間復雜度。合并排序的時間復雜度是：T(n)=O(nlogn)。利用該遞歸式求取合并排序算法時間復雜度的上界。理解并掌握快速分類（快速排序）算法，給定一個未排序數組，能分步寫出快速分類中劃分的執行過程。理解快速分類算法的時間復雜度。快速排序的時間復雜度是：T(n)=O(nlogn)本章作業：1、寫出用分治法求解循環賽日程表的完整程序。程序語言任意，但必須能上機運行。2、p99-4.22、P99-4.3

5、根據4.2節開始所給出的二分檢索策略，寫一個二分檢索的遞歸過程。3、P99-4.5作一個“三分”檢索算法，它首先檢查n/3處的元素是否等于某個x的值，然后檢查2n/3處的元素。這樣，或者找到x，或者把集合縮小到原來的1/3。分析此算法在各種情況下的計算復雜度。第5章 貪心方法貪心方法:是根據具體的問題, 選取一種量度標準,按此標準對n個輸入進行排序, 然后按該順序一次輸入一個量. 如果這個輸入量和當前的部分最優解加在一起不能產生一個可行解, 則不把此輸入量加入到這個部分解中, 這種能夠得到某種量度意義下的最優解的分級處理方法就是貪心方法。貪心選擇性質：指所求問題的整體最優解可以通過一系列局部最

6、優的選擇。貪心算法的基本要素：貪心選擇性質和最優子結構性質。掌握背包問題的貪心解法，分別以重量、效益值，單位重量效益值為最優量度所得最優解的比較。三元歸并模式的貪心解法和證明，能畫出3元歸并樹單源點最短路徑的貪心解法，算法執行運行蹤跡。如：給出一個帶權圖，能將下表的運行蹤跡圖補充完整迭代S選取的結點udist2dist3dist4dist5置初值1-10maxint30100123作業：P121： 5.2、5.12第6章 動態規劃將問題分解成多級或許多子問題，然后順序求解子問題，前一個子問題的解為后一個子問題的求解提供有用的信息。最優子結構性質：該問題的最優解包含著其子問題的最優解。動態規劃算

7、法的基本要素：最優子結構性質和子問題重疊性質。理解并掌握多段圖的動態規劃求解過程，包括遞推步驟。如，下面是一個多段圖問題，為了求出源點s到終點t的最短距離，假設用cost(i)表示節點i到終點t的距離(節點i是指下圖中圓圈中的數字為i的結點)。試根據cost(i)的含義用動態規劃的方法求出該多段圖問題的解。（要求根據cost(i)的含義，用遞推的方法寫出求解步驟，得到結果）理解并掌握0/1背包問題的動態規劃求解過程，會采用序偶直接解n值不大的0/1背包問題。第8章 回溯法回溯法：是一個既帶有系統性又帶有跳躍性的搜索算法。這在問題的解空間樹中，按深度優先策略，從根結點出發搜索解空間樹。算法搜索至

8、解空間樹的任一結點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續按深度優先策略搜索。理解回溯法的基本思想，掌握狀態空間樹的畫法及各種含義。掌握n皇后問題的算法及執行蹤跡。能畫出0/背包問題的狀態空間樹及子集樹。回溯法效率的因素：（1）產生xk的時間。（2）滿足顯約束的xk值的個數。（3）計算約束函數constraint的時間。（4）計算上界函數bound的時間。（5）滿足約束函數和上界函數約束的所有xk的個數第9章 分支限界法（了解）分支限界法的基本思想：(1)分支限界法常以廣度優先或以最小耗費(最大效益)優先的方式 搜索問題的解空間樹。(2)在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優解的兒子結點被舍棄，其余兒子結點被加入活結點表中。(3)此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程，這個過程一直持續到找到所需的解或活結點表這空時為止。最常見的分支限界法有兩種：隊