算法設計與分析考試重點歸納

1、精選文檔算法設計考試重點整理題型：一 選擇題 （10*2=20 分）二 簡答題 （4*5=20 分）三 應用題 （3*10=30 分）四 算法題 （3*10=30 分）第一、二章算法的定義：解某一特定問題的一組有窮規(guī)則的集合 （對特定問題求解步驟的一種描述，是指令的有限序列）算法的特征：1）有限性 2）確定性 3）輸入 4）輸出 5）能行性算法分析的目的：基本數(shù)據結構：線性結構(元素之間是一對一的關系)用順序存儲結構存儲的線性表稱為順序表用鏈式存儲結構存儲的線性表稱為鏈表。樹形結構(元素之間是一對多的關系)圖(網)狀結構(元素之間是多對多的關系)棧：是一種只允許在表的一端進行插入或刪除操作的線

2、性表。允許進行插入、刪除操作的一端稱為棧頂，另一端稱為棧底。當棧中沒有數(shù)據元素時，稱之為空棧。棧的插入操作稱為進壓棧，刪除操作稱為出棧。隊列：只允許在一端進行插入操作，在另一端進行刪除操作的線性表。允許進行插入操作的一端稱為隊尾。允許進行刪除操作的一端稱為隊頭。當隊列中沒有數(shù)據元素時，稱之為空隊列。隊列的插入操作稱為進隊或入隊。隊列的刪除操作稱為退隊或出隊。樹：樹型結構是一種非線性結構，它用于描述數(shù)據元素之間的層次關系圖圖：G(V，E)是一個二元組 其中：V是圖G中數(shù)據元素（頂點）的非空有限集集合 E是圖G中關系的有限集合 由表達式求漸進表達式：例：(n2+n)/4 n2/4 （增長速率最快的

3、那一項）時間復雜度的計算：（P23）性能的比較：O(1) O(log2n) O(n) O(nlog2n) =O(nlogn) O(n2) O(n3) O(nk) O(2n)第三章算法思想、穩(wěn)定性、時間復雜度、應用、排序的移動次數(shù)：希爾排序（數(shù)據結構P265）：先將待排序列分割為若干個子序列分別進行直接插入排序；待整個序列基本有序時，再對全體記錄進行一次直接插入排序 。也稱縮小增量的直接插入排序。希爾排序的時間復雜度在O(nlog2n)和 O(n2)之間，大致為O(n1.3) 合并排序（P59）：設初始序列含有n個記錄，則可看成n個表長為1的有序表將這n個有序表兩兩合并，則可得n/2個表長為2的

4、有序表再將這n/2個有序表兩兩合并，則可得n/4個長為4的有序表依次重復，直到對2個表長為n/2的有序表兩兩合并得1個表長為n的有序表為止。 堆排序、堆調整（P62）：初始時把要排序的n個數(shù)的序列看作是一棵順序存儲的二叉樹（一維數(shù)組存儲二叉樹），調整它們的存儲序，使之成為一個堆，將堆頂元素輸出，得到n 個元素中最小(或最大)的元素，這時堆的根節(jié)點的數(shù)最?。ɑ蛘咦畲螅Ｈ缓髮η懊?n-1)個元素重新調整使之成為堆，輸出堆頂元素，得到n 個元素中次小(或次大)的元素。依此類推，直到只有兩個節(jié)點的堆，并對它們作交換，最后得到有n個節(jié)點的有序序列?；鶖?shù)排序（P71）：不進行記錄關鍵字的比較，借助多關鍵

5、字排序的思想對單邏輯關鍵字進行排序。 算法 時間復雜度 穩(wěn)定性希爾排序 O(n1.3) 不穩(wěn)定快速排序 O(nlogn) 不穩(wěn)定堆排序 O(nlogn) 不穩(wěn)定寧歸(合)并排序 O(nlogn) 穩(wěn)定基數(shù)排序 O(n) 穩(wěn)定第四章（考一個算法題，課后，不在書上）算法思想：基于歸納的遞歸算法解規(guī)模為 n 的問題 P(n),歸納法的思想如下：1. 基礎步：a1 是問題 P(1) 的解2. 歸納步：對所有的 k (1 k n)，若ak 是問題 P(k) 的解， 則p(ak)是問題 P(k+1) 的解， 其中p(ak)是對ak 的某種運算或處理為求問題 P(n) 的解an，先求問題 P(n 1) 的解

6、an-1再對an-1進行p(an-1)運算或處理，得到an為求問題 P(n 1) 的解an-1，先求問題 P(n 2) 的解an-2再進行p(an-2)運算或處理，得到an-1如此等等，不斷地進行遞歸求解，直到 P(1) 的解a1為止當?shù)玫?P(1) 的解之后，再回過頭來，不斷地把所得到的解進行 p 運算或處理，直到得到 P(n) 的解為止 分治法：對于一個規(guī)模為n的問題p(n)，可以把它分解為k個規(guī)模較小的子問題，這些子問題相互獨立，且結構與原來問題的結構相同。在解這些子問題時，又對每一個問題進一步的分解，直到某個閥值n0 為止。遞歸地解決這些子問題，再把各個子問題的解合并起來，就得到原來問

7、題的解。分治法設計的3個步驟：1）劃分步：把輸入的問題實例劃分為 k 個子問題。盡量使 k 個子問題的規(guī)模大致相同。例如，k = 2，如最大最小問題取其中的一部分，而丟棄另一部分，如二叉檢索問題用分治法處理的情況2）治理步：由 k 個遞歸調用組成3）組合步：把 k 個子問題的解組合起來 算法思想、應用：快速排序（數(shù)據結構P269）：把序列就地劃分為兩個子序列，使第一個子序列的所有元素都小于第二個子序列的所有元素，不斷地進行這樣的劃分，最后構成 n 個子序列，每個子序列只有一個元素，這時，整個序列就是按遞增順序排序的序列了不穩(wěn)定選擇算法：（P125）1）選擇問題：用遞歸方法以 O(n) 時間選取

8、數(shù)組的中值元素、或任意的第 k 小元素的算法2）選擇問題的思想方法：在遞歸調用的每一步，放棄固定部分的元素，對其余元素進行遞歸，使問題的規(guī)模以幾何級數(shù)遞減 殘缺棋盤問題（P131）：把棋盤劃分為四個區(qū)域，每個區(qū)域是一個2k-12k-1個方格的子棋盤，其中有一個是殘缺子棋盤。用一個 L 型三格板覆蓋在其余三個非殘缺子棋盤的交界處，把覆蓋一個2k2k 個方格的殘缺棋盤，轉化為覆蓋4 個2k-12k-1 個方格的殘缺子棋盤。對每一個子棋盤繼續(xù)進行這樣處理，直到要覆蓋的子棋盤轉化為22個方格的殘缺子棋盤為止。這時只要用一個 L 型三格板覆蓋三個非殘缺方格即可。第五章（考一個算法題）可行解：滿足約束方程

9、的向量最優(yōu)解：使目標函數(shù)達極值的向量貪婪發(fā)的設計思：貪婪算法采用的是逐步構造最優(yōu)解的方法。從某個初始狀態(tài)出發(fā)，根據當前局部的而不是全局的最優(yōu)決策(因此所構造的可行解不一定是問題的最優(yōu)解)，以滿足約束方程為條件、以使得目標函數(shù)的值增加最快或最慢為準則，選擇一個能夠最快地達到要求的輸入元素(選擇一旦做出，就不再更改)，以便盡快地構成問題的可行解。作出這個局部最優(yōu)決策所依照的標準稱為貪心準則。貪婪發(fā)求解步驟：首先根據問題確定約束條件和貪心準則，然后根據貪心準則獲得當前每一步的最優(yōu)解，最終得出解向量。貪婪法求解的問題需滿足2個性質：1）貪心選擇性質：指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇來

10、達到2）最優(yōu)子結構性質：當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質。算法思想、應用：狄斯奎諾：（P146）貪心算法：Dijkstra 提出按路徑長度遞增的次序產生最短路徑。貪心準則：使當前已經加入的所有路徑的長度之和最小。為了符合這一準則，其中每一條單獨的路徑都必須具有最小的長度。 最小生成樹的應用：（P151）克魯斯卡爾，普里姆哈夫曼中的一個基本概念（P159）第六章最優(yōu)性原理：無論過程的初始狀態(tài)和初始決策是什么，其余決策都必須相對于初始決策所產生的狀態(tài)，構成一個最優(yōu)決策序列 多段圖的概念、應用、求最短路徑有向連通賦權圖 G = ，頂點集合 V 劃分成k 個不相交的

11、子集vi，1 i k，k 2，使得 E 中的任一邊 (u, v)，必有 u vi，v vi+m，m 1，稱 G 為多段圖。數(shù)塔問題的應用：如圖所示的一個數(shù)塔，從頂部出發(fā)，在每一結點可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的數(shù)值和最大。 算法思想、應用：0/1背包（P190）第七章（考一個算法題，一個簡答題）回溯法的基本思想：在確定了解空間的組織結構后，回溯法就從開始結點（根結點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，并成為當前擴展結

12、點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止?；厮莘ǖ那蠼獠襟E1） 對所給定的問題，定義問題的解空間2）確定狀態(tài)空間樹的結構3）用深度優(yōu)先搜索方法搜索解空間，用約束方程和目標函數(shù)的界對狀態(tài)空間樹進行修剪，生成搜索樹，取得問題的解。 狀態(tài)空間樹：問題解空間的樹形式表示活結點：所搜索到的結點不是葉結點，且滿 足約束條件和目標函數(shù)的界，其兒子結點還未全部搜索完畢擴展

13、結點：正在搜索其兒子結點的結點，它也是一個活結點；死結點：不滿足約束條件、目標函數(shù)、或其兒子結點已全部搜索完畢的結點、或者葉結點。算法思想、判定函數(shù)，如何判定（約束方程）n后問題（P208）圖的著色問題（P212）哈密爾頓回路問題（P216）簡答題考算法思想之類的。應用題考排序、以上各種算法的應用（要求寫求解步驟嗯，排序只求移動次數(shù)，不求比較次數(shù)）。算法題預測題：*1設計一個分支算法，求二叉樹的高度。int Height(BTree t)int h1,h2;if(t=NULL) return 0;elseh1=Height(t-lchild)+1;h2=Height(t-rchild)+1;return h1h2?h1: