算法設(shè)計(jì)與分析考試重點(diǎn)歸納

1、.算法設(shè)計(jì)考試重點(diǎn)整理題型：一 選擇題 （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)系)用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表稱為順序表用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的線性表稱為鏈表。樹形結(jié)構(gòu)(元素之間是一對多的關(guān)系)圖(網(wǎng))狀結(jié)構(gòu)(元素之間是多對多的關(guān)系)棧：是一種只允許在表的一端進(jìn)行插入或刪除操作的線性表。

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

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

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

5、的思想對單邏輯關(guān)鍵字進(jìn)行排序。 算法 時(shí)間復(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)定第四章（考一個(gè)算法題，課后，不在書上）算法思想：基于歸納的遞歸算法解規(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 的某種運(yùn)算或處理為求問題 P(n) 的解an，先求問題 P(n 1) 的解an-

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

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

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

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

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

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

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

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