算法設(shè)計與分析考試重點歸納

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

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

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

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

5、字排序的思想對單邏輯關(guān)鍵字進行排序。 算法 時間復(fù)雜度 穩(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. 基礎(chǔ)步：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ī)模較小的子問題，這些子問題相互獨立，且結(jié)構(gòu)與原來問題的結(jié)構(gòu)相同。在解這些子問題時，又對每一個問題進一步的分解，直到某個閥值n0 為止。遞歸地解決這些子問題，再把各個子問題的解合并起來，就得到原來問

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

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

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

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

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

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

13、結(jié)點：正在搜索其兒子結(jié)點的結(jié)點，它也是一個活結(jié)點；死結(jié)點：不滿足約束條件、目標函數(shù)、或其兒子結(jié)點已全部搜索完畢的結(jié)點、或者葉結(jié)點。算法思想、判定函數(shù)，如何判定（約束方程）n后問題（P208）圖的著色問題（P212）哈密爾頓回路問題（P216）簡答題考算法思想之類的。應(yīng)用題考排序、以上各種算法的應(yīng)用（要求寫求解步驟嗯，排序只求移動次數(shù)，不求比較次數(shù)）。算法題預(yù)測題：*1設(shè)計一個分支算法，求二叉樹的高度。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: