2022年軍隊文職-計算機類計算機類-數(shù)據(jù)結(jié)構(gòu)與算法知識點總結(jié)

1、學(xué)習(xí)必備精品知識點數(shù)據(jù)結(jié)構(gòu)知識點總結(jié)內(nèi)容概要：基本概念 線性表 棧與隊列 樹與二叉樹 圖查找算法 排序算法精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點一、基本概念1、數(shù)據(jù)元素是數(shù)據(jù)的基本單位。2、數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。3、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)（抽象的，與實現(xiàn)無關(guān)）物理結(jié)構(gòu)（存儲結(jié)構(gòu)）順序映像（順序存儲結(jié)構(gòu)）位置“相鄰”非順序映像（鏈?zhǔn)酱鎯Y(jié)構(gòu)）指針表示關(guān)系4、算法特性：算法具有正確性、有窮性，確定性，（可行性）、輸入，輸出正確性：能按設(shè)計要求解決具體問題，并得到正確

2、的結(jié)果。有窮性：任何一條指令都只能執(zhí)行有限次，即算法必須在執(zhí)行有限步后結(jié)束。確定性：算法中每條指令的含義必須明確，不允許由二義性可行性：算法中待執(zhí)行的操作都十分基本，算法應(yīng)該在有限時間內(nèi)執(zhí)行完畢。輸入：一個算法的輸入可以包含零個或多個數(shù)據(jù)。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點輸出：算法有一個或多個輸出5、算法設(shè)計的要求：（ 1）正確 性：算法應(yīng)能滿足設(shè)定的功能和要求。（2）可讀 性：思路清晰、層次分明、易讀易懂。（3）健壯 性：輸入非法數(shù)據(jù)時應(yīng)能作適當(dāng)?shù)姆磻?yīng)和處理。

3、（4）高效 性（時間復(fù)雜度） ：解決問題時間越短，算法的效率就越高。（5）低存儲量（空間復(fù)雜度）：完成同一功能，占用存儲空間應(yīng)盡可能少。二、線性表1、線性表list：最常用且最簡單的數(shù)據(jù)結(jié)構(gòu)。含有大量記錄的線性表稱為文件。2、線性表是n 個數(shù)據(jù)元素的有限序列。線性結(jié)構(gòu)的特點：“第一個”“最后一個”前驅(qū)后繼。3、順序表 線性表的順序存儲結(jié)構(gòu)特點a) 邏輯上相鄰的元素在物理位置上相鄰。b) 隨機訪問。1) typedef struct datatype elemmaxsize; int length; sqlist; 2) 表長為 n 時，線性表進行插入和刪除操作的時間復(fù)雜度為o（n） 插入一個元

4、素時大約移動表中的一半元素。刪除一個元素時大約移動表中的（n-1）2 4、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)1) 類型定義簡而言之，“數(shù)據(jù)+ 指針”。typedef struct lnode datatype data; struct lnode *next; lnode, *linklist; 2) 不帶頭結(jié)點的空表判定為l= =null 帶頭結(jié)點的空表判定為l-next= =null 循環(huán)單鏈表為空的判定條件為l.next= =l 線性鏈表的最后一個結(jié)點的指針為null 頭結(jié)點的數(shù)據(jù)域為空，指針域指向第一個元素的指針。5、順序表和單鏈表的比較順序表單鏈表地址相鄰表示關(guān)系指針表示關(guān)系機訪問，取元素o(1)

5、 序訪問，取元素o(n) 入、刪除需要移動元素o(n) 入、刪除不用移動元素o(n)(用于查找位置 ) 6、順序存儲：優(yōu)點：存儲密度大，可隨機存儲缺點：大小固定；不利于增減節(jié)點;存儲空間不能充分利用；容量難擴充0 1 maxsize-1 . l.elem l.elem l.elem l.length=0 l.length=maxsize 0l.lengthtop= =maxlen 1）return 0 ；/ 棧滿不能入棧，且返回0else s-top+；s-datas-top=x；/ 棧不滿，則壓入元素xreturn 1 ； / 進棧成功，返回1出棧 : 出棧運算是指取出棧頂元素，賦給某一個指

6、定變量x。算法步驟：(a)判棧是否為空，若?？眨飨乱缣幚恚⒎祷?；(b)若棧非空，將棧頂元素賦給變量x；(c)指針 top減1，并返回 1。算法實現(xiàn)：datatype pop （seqstack *s） datatypex;if (sempty ( s ) ) return 0 ；/ 若?？詹荒艹鰲?，且返回 0else x=s-datas-top；/ 棧不空則棧頂元素存入*xs-top - -；return x ； / 出棧成功，返回13、隊列先進先出的線性表。隊尾入隊對頭出隊允許插入的一端叫做隊尾允許刪除的一端叫做對頭4、鏈隊列a1/ ans . an-1精品學(xué)習(xí)資料 可選擇p d f

7、 - - - - - - - - - - - - - - 第 4 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點typedef struct queuenodedatatypedata; struct queuenode *next;queuenode; / 鏈隊結(jié)點的類型datatypetypedefstructqueuenode *front,*rear;linkqueue; / 將頭指針、尾指針封裝在一起的鏈隊frontrearpabj圖4-6 鏈隊列示意圖5、 循環(huán)隊列typedef struct datatype elemmaxsize; int front,

8、 rear; / 隊頭、隊尾位置 sqqueue; 循環(huán)隊列判斷隊空的條件為front=rear 循環(huán)隊列判斷隊滿的條件為（rear+1）%m=front 在一個循環(huán)隊列中刪除元素時，首先需要后移隊首指針。6、棧與隊列比較：都是線形結(jié)構(gòu)，棧的操作lifo （后進先出） ，隊列操作fifo （先進先出）。四、樹和二叉樹精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點1.樹的定義樹（ tree ） ：是 n （n 0）個有限數(shù)據(jù)元素的集合。在任意一棵非空樹t中：（1）有且僅有一個特

9、定的稱為樹根（root）的結(jié)點，根結(jié)點無前趨結(jié)點；（2）當(dāng) n1 時，除根結(jié)點之外的其余結(jié)點被分成m(m0)個互不相交的集合t1，t2， tm ，其中每一個集合ti （ 1 i m ）本身又是一棵樹，并且稱為根的子樹。2.基本術(shù)語：結(jié)點的度數(shù)：結(jié)點的非空子樹（即后綴）個數(shù)叫作結(jié)點的度數(shù)樹葉、分支結(jié)點：左（右）子樹均為空二叉樹的結(jié)點稱作樹葉否則稱作分支結(jié)點。結(jié)點的層數(shù)：規(guī)定根的層數(shù)是0，其余結(jié)點的層數(shù)等于其父結(jié)點的層數(shù)加1 孩子和雙親：樹的深度：樹的度數(shù)：樹中度數(shù)最大的結(jié)點度數(shù)叫作樹的度數(shù)樹林：是由零個或多個不相交的樹所組成的集合。3.二叉樹性質(zhì)：1) 二叉樹的第i 層上至多有2i-1 個結(jié)點。

10、2) 深度為 k 的二叉樹至多有2k-1 個結(jié)點。滿二叉樹 ：深度為 k，有 2k-1 個結(jié)點。完全二叉樹 ：給滿二叉樹的結(jié)點編號，從上至下，從左至右，n 個結(jié)點的完全二叉樹中結(jié)點在對應(yīng)滿二叉樹中的編號正好是從1 到 n。3) 葉子結(jié)點n0，度為 2的結(jié)點為n2，則 n0 = n2+1。考慮結(jié)點個數(shù)：n = n0 + n1 + n2考慮分支個數(shù)：n-1 = 2n2 + n1可得 n0 = n2+1 4) n 個結(jié)點的完全二叉樹深度為1log n。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 6 頁，共 23 頁 - - - - - - - - -學(xué)

11、習(xí)必備精品知識點5) n 個結(jié)點的完全二叉樹，結(jié)點按層次編號有：i 的雙親是2/n，如果 i = 1 時為根（無雙親） ；i 的左孩子是2i，如果 2in，則無左孩子；i 的右孩子是2i + 1，如果 2i + 1n 則無右孩子。4.二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)用數(shù)組、編號i 的結(jié)點存放在i-1處。適合于存儲完全二叉樹。鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉鏈表：typedef struct btnode datatype data; struct btnode *lchild, *rchild; btnode, *bintree; 三叉鏈表：typedef struct btnode datatype data;

12、 struct btnode *lchild, *rchild, *parent; btnode, *bintree; 在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，含有n 個結(jié)點的二叉鏈表有n+1 個空鏈域。5.遍歷二叉樹 （先序 dlr 、中序 ldr 、后序 lrd ）方法與c語言描述由二叉樹的遞歸定義可知，一棵二叉樹由根結(jié)點（d） 、根結(jié)點的左子樹（l）和根結(jié)點的右子樹（r）三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個二叉樹。一般有三種方法：先序( 前序 ) 遍歷 dlr （根左右）、中序遍歷ldr （左根右）、 后序遍歷lrd （左右根）。data parent lchild rchild data

13、rchild lchild 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 7 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點1 先序遍歷（dlr ）的遞歸過程void preorder(bt*t) / 先序遍歷二叉樹bt if (t= =null) return; / 遞歸調(diào)用的結(jié)束條件 printf(t-data); / 輸出結(jié)點的數(shù)據(jù)域preorder(t-lchild); / 先序遞歸遍歷左子樹preorder(t-rchild); / 先序遞歸遍歷右子樹2 中序遍歷（l dr）的遞歸過程void inorder(bt

14、*t)/ 中序遍歷二叉樹bt if (t= =null) return; / 遞歸調(diào)用的結(jié)束條件 inorder(t-lchild); / 中序遞歸遍歷左子樹printf(t-data); / 輸出結(jié)點的數(shù)據(jù)域inorder(t-rchild); / 中序遞歸遍歷右子樹3 后序遍歷（l rd）的遞歸過程void postorder(bt*t) / 后序遍歷二叉樹bt if (t= =null) return; / 遞歸調(diào)用的結(jié)束條件 postorder(t-lchild); / 后序遞歸遍歷左子樹postorder(t-rchild); / 后序遞歸遍歷右子樹printf(t-data); /

15、 輸出結(jié)點的數(shù)據(jù)域6.線索二叉樹n 個結(jié)點的二叉鏈表中有n+1 個空指針，可以利用其指向前驅(qū)或后繼結(jié)點，叫線索 ，同時需附加一個標(biāo)志，區(qū)分是子樹還是線索。lchild 有左子樹，則指向左子樹，標(biāo)志ltag = 0；沒有左子樹，可作為前驅(qū)線索，標(biāo)志ltag = 1。rchild 有右子樹，則指向右子樹，標(biāo)志rtag = 0；沒有右子樹，可作為后繼線索，標(biāo)志rtag = 1。7.樹和森林樹的存儲結(jié)構(gòu)雙親表示法 ，孩子表示法 ，孩子兄弟表示法。特點：雙親表示法容易求得雙親，但不容易求得孩子；孩子表示法容易求得孩子，但求雙親麻煩；兩者可以結(jié)合起來使用。孩子兄弟表示法，容易求得孩子和兄弟，求雙親麻煩，也

16、可以增加指向雙親的指針來解決。樹與二叉樹的轉(zhuǎn)換表 錯誤！文檔中沒有指定樣式的文字。.1 樹和二叉樹的對應(yīng)關(guān)系樹對應(yīng)的二叉樹lchild ltag data rtag rchild 0/1 0/1 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 8 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點一個孩子孩子一個兄弟孩子樹的遍歷樹的結(jié)構(gòu)：根，根的子樹。先根遍歷：。例：abcdefghijk 。后根遍歷：。例：cedfbhgjkia 。遍歷森林森林的結(jié)構(gòu)：第一棵樹的根，第一棵樹的根的子樹森林，其余樹 (除第一棵外 )組成的森林。先序

17、遍歷：。例：abcdefghij 。中序遍歷：。例：bdceagfijh 。注：先序遍歷森林，相當(dāng)于依次先根遍歷每一棵樹；中根遍歷森林相當(dāng)于后根遍歷每一棵樹。遍歷樹、森林與遍歷二叉樹的關(guān)系遍歷樹、森林和二叉樹的關(guān)系樹森林二叉樹根遍歷序遍歷序遍歷根遍歷序遍歷序遍歷8.哈夫曼樹：葉子結(jié)點帶有權(quán)值的最小帶權(quán)路徑長度的最優(yōu)二叉樹構(gòu)造赫夫曼樹每次取兩個最小的樹組成二叉樹赫夫曼編碼 (前綴碼 ) 向左分支為0，向右分支為1，從根到葉子的路徑構(gòu)成葉子的前綴編碼。五、圖a b i c d f h g j k e a h b c e g f i j d 樹的結(jié)構(gòu)劃森林的結(jié)構(gòu)劃分精品學(xué)習(xí)資料 可選擇p d f -

18、 - - - - - - - - - - - - - 第 9 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點1完全圖：有12 n(n-1) 條變得無向圖有向完全圖：具有n（n-1）條弧的有向圖。權(quán)：與圖的邊或弧相關(guān)的數(shù)。頂點 v 的度：和v 相關(guān)聯(lián)的邊的數(shù)目。入度：以頂點v 為頭的弧的數(shù)目出度：以頂點v 為尾的弧的數(shù)目回路或環(huán)：第一個頂點和最后一個頂點相同的路徑。簡單路徑：序列中頂點不重復(fù)出現(xiàn)的路徑。2. 圖的存儲結(jié)構(gòu)鄰接矩陣：鄰接表：typedef struct arcnode / 弧結(jié)點intadjvex; / 鄰接點struct arcnode *nextarc;

19、 / 下一個鄰接點 arcnode; typedef struct vexnode / 頂點結(jié)點vertextype data; / 頂點信息arcnode *firstarc; / 第一個鄰接點 vexnode; constint max_vertex = 最大頂點個數(shù) ; typedef struct graph / 圖vexnode vexsmax_vertex; / 頂點向量intvexnum, arcnum; / 頂點和弧的個數(shù) graph; 邊 (弧)多則需要存儲空間多。十字鏈表：十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)?？梢钥闯墒菍⒂邢驁D的鄰接表和逆鄰接表結(jié)合起來的一種鏈表。在十字鏈

20、表中，對應(yīng)于有向圖中每一條弧有一個結(jié)點，對應(yīng)于每個頂點有一個結(jié)點。0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 a b c d e a b c d e 1 2 / 0 1 2 3 4 2 3 / 3 / 0 / 0 3 / 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 10 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點鄰接多重表3. 圖的遍歷1) 深度優(yōu)先（ dfs ）搜索訪問方式：從圖中某頂點v 出發(fā)：a）訪問頂點v；b）從 v 的未被訪問的鄰接點出發(fā)，繼續(xù)對圖進行深

21、度優(yōu)先遍歷，若從某點出發(fā)所有鄰接點都已訪問過，退回前一個點繼續(xù)上述過程，若退回開始點，結(jié)束。2) 廣度（寬度，bfs ）優(yōu)先搜索a）訪問頂點v ；b）訪問同v 相鄰的所有未被訪問的鄰接點w1,w2, wk；c）依次從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰接點; 依此類推， 直到圖中所有訪問過的頂點的鄰接點都被訪問；4. 生成樹和最小生成樹每次遍歷一個連通圖將圖的邊分成遍歷所經(jīng)過的邊和沒有經(jīng)過的邊兩部分，將遍歷經(jīng)過的邊同圖的頂點構(gòu)成一個子圖，該子圖稱為生成樹。因此有dfs生成樹和 bfs生成樹。1) 最小生成樹 kruskal算法一句話，“不構(gòu)成環(huán)的情況下，每次選取最小邊”。 普里姆算法記

22、v 是連通網(wǎng)的頂點集，u 是求得生成樹的頂點集，te是求得生成樹的邊集。普里姆算法：(a) 開始時， u=v0，te=；(b) 計算 u 到其余頂點v-u 的最小代價，將該頂點納入u，邊納入te ；(c) 重復(fù) (b)直到 u=v。普里姆算法和克魯斯卡爾算法的比較法里姆算法魯斯卡爾算法間復(fù)雜度) loge) 點與頂點個數(shù)n 有關(guān)邊的數(shù)目e 無關(guān)用于稠密圖與邊的數(shù)目e 有關(guān)頂點個數(shù)n 無關(guān)用于稀疏圖a b c d e 2 5 3 3 1 7 6 3 a b c d e 2 5 3 3 1 7 6 3 a b c d e 2 5 3 3 1 7 6 3 (a) (b) (c) a b c d e

23、2 5 3 3 1 7 6 3 a b c d e 2 5 3 3 1 7 6 3 a b c d e 2 5 3 3 1 7 6 3 (d) (e) (f) 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 11 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點5.aov- 網(wǎng)用頂點表示活動，邊表示活動的優(yōu)先關(guān)系的有向圖稱為aov 網(wǎng)。拓?fù)渑判颍簩ov網(wǎng)絡(luò)中頂點構(gòu)造拓?fù)溆行蛐蛄械倪^程。拓?fù)渑判虻姆椒?1)在有向圖中選一個沒有前驅(qū)的頂點且輸出之(2)從圖中刪除該頂點和所有以它為尾的弧6. 關(guān)鍵路徑aoe 網(wǎng)，關(guān)鍵路徑aoe 網(wǎng)(

24、activity on edge)帶權(quán)的有向無環(huán)圖，其中頂點表示事件，弧表示活動，權(quán)表示活動持續(xù)時間。在工程上常用來表示工程進度計劃。關(guān)鍵路徑：從源點到匯點的最長的一條路徑，或者全部由關(guān)鍵活動構(gòu)成的路徑。7. 最短路徑(1) 迪杰斯特拉算法求一個頂點到其他各頂點的最短路徑。算法： (a) 初始化：用起點v 到該頂點w 的直接邊 (弧)初始化最短路徑，否則設(shè)為；(b) 從未求得最短路徑的終點中選擇路徑長度最小的終點u：即求得 v 到 u 的最短路徑；(c) 修改最短路徑：計算u 的鄰接點的最短路徑，若(v, ,u)+(u,w)(v, ,w)，則以 (v, ,u,w)代替。(d) 重復(fù) (b)-(

25、c)，直到求得v 到其余所有頂點的最短路徑。特點：總是按照從小到大的順序求得最短路徑。(2) 弗洛伊德算法求每對頂點之間的最短路徑。依次計算a(0)，a(1)， ， a(n)。a(0)為鄰接矩陣，計算a(k)時， a(k)(i,j)=mina(k-1)(i,j), a(k-1)(i,k)+a(k-1)(k,j)。技巧： 計算 a(k)的技巧。 第 k 行、第 k 列、對角線的元素保持不變，對其余元素， 考查 a(i,j)與 a(i,k)+a(k,j) （ “行+列” ） ，如果后者更小則替換a(i,j)，同時修改路徑。六、查找1. 查找分為：靜態(tài)查找表、動態(tài)查找表、哈希查找表2. 靜態(tài)查找表：

26、對查找表只作查找操作的查找表。動態(tài)查找表：查找過程中同時插入表中不含的元素，或者刪除查找表中已有的元素的操作的查找表。3. 順序查找：順序查找又稱線性查找，是最基本的查找方法之一。順序查找既適用于順序表，也適用于鏈表。4. 二分法（折半）查找：是一種效率較高的查找方法，但前提是表中元素必須按關(guān)鍵字有序（按關(guān)鍵字遞精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 12 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點增或遞減）排列。5. 索引順序表查找又稱分塊查找。分塊查找：塊內(nèi)無序、塊間有序、如何分塊效率最高6. 動態(tài)查找表：二叉

27、排序樹查找：二叉排序樹的生成二叉排序樹 (二叉查找樹 )：或者是一顆空樹。或者如下1 若它的左子樹不空，則左子樹上所有的結(jié)點的值均小于他的根結(jié)點的值。2 若右子樹不空，則右子樹所有結(jié)點的值均大于她得根結(jié)點的值。3 左右子樹也分別為二叉排序樹。7. 哈希表：哈希函數(shù)構(gòu)造：直接定址法、除留余數(shù)法、平方取中法，隨機數(shù)法，數(shù)字分析法沖突解決方法：開放定址法、拉鏈法、公共溢出區(qū)法七、排序1. 插入類排序：直接插入排序每次將一個待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。折半插入排序希爾排序基本思想：先將整個待排序記錄序列分成為若干個子序列分

28、別進行直接插入排序，待整個序列中的記錄基本有序時在對全體序列進行一次直接插入排序，子序列的構(gòu)成不是簡單的逐段分割，而是將像個某個增量的記錄組成一個子序列。2. 交換類排序起泡排序也稱冒泡法，每相鄰兩個記錄關(guān)鍵字比大小, 大的記錄往下沉（也可以小的往上?。?。每一遍把最后一個下沉的位置記下，下一遍只需檢查比較到此為止；到所有記錄都不發(fā)生下沉?xí)r，整個過程結(jié)束（每交換一次，記錄減少一個反序數(shù)） ?？焖倥判蛟诋?dāng)前無序區(qū)r1.h 中任取一個數(shù)據(jù)元素作為比較的基準(zhǔn) (不妨記為x)，用此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左右兩個較小的無序區(qū)：r1.i-1 和 ri+1.h ，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，

29、右邊的無序 子 區(qū) 中 數(shù) 據(jù) 元 素 均 大 于 等 于 基 準(zhǔn) 元 素 ， 而 基 準(zhǔn)x則 位 于 最 終 排 序 的 位 置 上 ， 即r1.i- 1 x.keyri+1.h(1i h)，當(dāng) r1.i-1 和 ri+1.h 均非空時，分別對它們進行上述的劃分過程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序為止。3. 選擇類排序簡單選擇排序每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。堆排序堆排序是一樹形選擇排序，在排序過程中，將r1.n 看成是一顆完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選

30、擇最小的元素。4. 歸并類排序二路歸并排序精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 13 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點5. 基數(shù)類排序基數(shù)排序主要特點不需要進行關(guān)鍵字間的比較。多關(guān)鍵字排序：最高為優(yōu)先（ msd 法）從主關(guān)鍵字開始排序，再從次高位排序，一次類推，最后將所有子序列依次連接在一起成為一個有序序列。最低位優(yōu)先（lsd法）從最次位關(guān)鍵字開始排序，在對高一位的進行排序，直到成為一個有序序列。排序方法穩(wěn)定性平均時間最壞情況輔助存儲直接插入排序穩(wěn)定o（n*n）o（n*n ）o（1）快速排序不穩(wěn)定o（n

31、lbn）o（n*n ）o（lbn）歸并排序穩(wěn)定o(nlbn) o（nlbn）o（n）簡單選擇排序穩(wěn)定o（n*n）o（n*n ）o（1）堆排序不穩(wěn)定o（nlbn）o（nlbn）o(1) 基數(shù)排序穩(wěn)定o（d（ n+rd）o（d（n+rd）o（rd）選取排序方法需要考慮的因素：(1) 待排序的元素數(shù)目n；(2) 元素本身信息量的大小；(3) 關(guān)鍵字的結(jié)構(gòu)及其分布情況；(4) 語言工具的條件，輔助空間的大小等。小結(jié)：(1) 若 n 較小 (n = 50) ，則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記錄移動操作較直接選擇排序多，因而當(dāng)記錄本身信息量較大時，用直接選擇排序較好。(2)

32、若文件的初始狀態(tài)已按關(guān)鍵字基本有序，則選用直接插入或冒泡排序為宜。(3) 若 n 較大，則應(yīng)采用時間復(fù)雜度為o(nlog2n) 的排序方法：快速排序、堆排序或歸并排序。快速排序是目前基于比較的內(nèi)部排序法中被認(rèn)為是最好的方法。(4) 在基于比較排序方法中，每次比較兩個關(guān)鍵字的大小之后，僅僅出現(xiàn)兩種可能的轉(zhuǎn)移，因此可以用一棵二叉樹來描述比較判定過程，由此可以證明：當(dāng)文件的n 個關(guān)鍵字隨機分布時，任何借助于比較 的排序算法，至少需要o(nlog2n) 的時間。算法分析知識點總結(jié)算法概述1、算法的五個性質(zhì)：有窮性、確定性、能行性、輸入、輸出。2、算法的復(fù)雜性取決于： （1）求解問題的規(guī)模（n）,（2）

33、具體的輸入數(shù)據(jù)（i） ， （3）算法本身的設(shè)計（ a） ，c=f(n,i,a) 。3、算法的時間復(fù)雜度的上界記號o，下界記號 (記為 f(n) = (g(n)。即算法的實際運行時間至少需要g(n)的某個常數(shù)倍時間)，同階記號 ：f(n)= (g(n)表示 f(n)和 g(n)同階。即算法的實際運行時間大約為g(n)的某個常數(shù)倍時間。低階記號o：f(n)=o(g(n)表示 f(n)比 g(n)低階。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 14 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點多項式算法時間：o(1)o(lo

34、gn)o(n)o(nlogn)o(n2)o(n3) 約定 logn 表示以 2 為底的對數(shù)。指數(shù)時間算法時間：o(2n)o(n!) b1 (d(n) = n) t(n) = o(n2)；對，a = b2 (d(n) = n2) t(n) = o(n2log n)；對，a 0) hanoi(n 1, a, c, b); move(a, b); hanoi(n 1, c, b, a) 4、二分查找代碼精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 16 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點貪心算法（旅行商問題、單源最短路

35、徑問題）以下兩種算法都是為了查找最小生成樹問題的算法：1、prim 算法的基本思想：在保證連通的前提下依次選出權(quán)重較小的n 1 條邊。（在實現(xiàn)中體現(xiàn)為n 個頂點的選擇） 。g=(v, e) 為無向連通帶權(quán)圖，令v=1, 2, , n。設(shè)置一個集合s ，初始化s = 1，t = 。貪心策略：如果vs中的頂點j 與 s中的某個點i 連接且 (i, j) 的權(quán)重最小，于是就選擇j(將 j 加入 s)，并將 (i, j) 加入 t 中 。重復(fù)執(zhí)行貪心策略，直至vs為空。= 證明最小生成樹必然包含最小權(quán)值邊= 若 g 的任何最小生成樹都不包含e1。設(shè) t為 g 的最小生成樹， e1t。于是 t+e1是一

36、個有回路的圖且該回路中包含e1。該回路中必有條不是e 的邊 ei。令 t=t+e1 ei。t 也是 g 的生成樹。又c(t) = c(t) + c(e1) c(ei)，c(e1) c(ei)，從而c(t ) c(t)，t 是 g 的最小生成樹且含有邊e1。矛盾。故必定有圖g的最小生成樹包含了e1。= 2、kruskal算法的基本思想：基本思想：在保證無回路的前提下依次選出權(quán)重較小的n 1 條邊。如果(i, j)是 e中尚未被選中的邊中權(quán)重最小的，并且(i, j)不會與已經(jīng)選擇的邊構(gòu)成回路，于是就選擇(i, j) 。具體做法 :先把所有n 個點畫出來。不畫邊。然后把權(quán)值最小的那條邊畫上去。然后再

37、把當(dāng)前權(quán)值最小的邊(不算畫了的邊)畫上去。如果構(gòu)成回路則舍棄這條邊。然后一直直到畫了n-1 條邊3、 prim 與 kruskal兩算法的復(fù)雜性：prim 算法為兩重循環(huán)，外層循環(huán)為n 次，內(nèi)層循環(huán)為o(n) ，因此其復(fù)雜性為o(n2) 。kruskal 算法中，設(shè)邊數(shù)為e，則邊排序的時間為o(eloge)，最多對 e 條邊各掃描一次，每次確定邊的時間為o(loge)，所以整個時間復(fù)雜性為o(eloge)。當(dāng) e = (n2)時， kruskal 算法要比prim 算法差；當(dāng) e = (n2)時， kruskal 算法比 prim 算法好得多。4、貪心算法的基本要素是：貪心選擇性質(zhì)。5、最小生

38、成樹問題、單源最短路徑問題、旅行商問題、 01 背包問題， 貪心算法不能夠找到最優(yōu)解。6、活動安排問題、最優(yōu)裝載問題，貪心算法可以找到最優(yōu)解。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 17 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點7、dijkstra 算法procedure dijkstra ( 1) s:=1; / 初始化 s (2) for i:= 2 to n do / 初始化 dis (3) disi =c1, i ; / 初始時為源到頂點i 一步的距離。不能一步到達就是無窮(4) for i :=1 to

39、 n do (5) 從 v-s中選取一個頂點u 使得 disu最小；(6) 將 u 加入到 s中； / 將新的最近者加入s (7) for wv-s do / 依據(jù)最近者u 修訂 disw (8) disw := min(disw , disu+cu ,w) 8、活動安排問題:先把活動按結(jié)束時間早晚排序。然后選取最早結(jié)束的。然后選取第一個開始時間比上一個結(jié)束時間大的再用這個原則選取?？偟臅r間復(fù)雜度為o(nlogn) = 代碼 = typedef struct int number; / 活動的編號float start; / 活動開始的時間float end; / 活動結(jié)束的時間bool se

40、lected; / 標(biāo)記活動是否被選擇active; int greedyselector(active activity, int n) quitcksort(activity,n); / 將活動按結(jié)束時間排序activity1.selected=true; j=1;count=1; for(i=2;i=activityj.end) activityi.selected=true; j=i; count+; else activityi.selected=false; 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 18 頁，共 23 頁 - -

41、- - - - - - -學(xué)習(xí)必備精品知識點return count; 9、為什么貪心算法不能求得旅行商問題的最優(yōu)解：最臨近法不保證求得旅行商問題的精確解，只能得到問題地近似解。一般地，貪心選擇只依賴于前面選擇步驟地最優(yōu)性，因此是局部最優(yōu)的，所以貪心法不能夠確保求出問題的最優(yōu)解。10、 最優(yōu)裝載問題：基本思想：這個題目比較簡單，可以用貪心法求解。每次采用重量最輕者優(yōu)先裝入的貪心選擇策略11、貪心算法的特點是什么？怎么樣知道一個問題是否能用貪心算法呢？貪心算法每次選擇目前最優(yōu)的解，即通過一系列局部最優(yōu)來獲得整體最優(yōu)。貪心算法只有在具有貪心選擇性質(zhì)時才能保證獲得整體最優(yōu)。證明貪心選擇性質(zhì)：第一個選

42、擇是對的；在作出貪心選擇后原問題轉(zhuǎn)化為同樣的子問題；由歸納法知問題具有貪心選擇性質(zhì)。若原問題是求帶權(quán)擬陣的最優(yōu)獨立子集問題，則必滿足貪心選擇性質(zhì)。動態(tài)規(guī)劃1、最短路徑問題 :如果是從源點往后推: 階段 1: c(s,1)=w(s,1)=4， c(s,2)=w(s,2)=2, c(s,3)=w(s,3)=3 階段 2: c(s,4)=minw(1,4)+c(s,1), w(2,4)+c(s,2)=min14,8= 8 c(s,5)=minw(1,5)+c(s,1), w(2,5)+c(s,2), w(3,5)+c(s,3) =min13,9,6= 6 c(s,6)=minw(2,6)+c(s,2

43、), w(3,6)+c(s,3)=min12,11= 11 階段 3: c(s,7)=minw(4,7)+c(s,4), w(5,7)+c(s,5), w(6,7)+c(s,6) =min12,15,16= 12 c(s,8)=minw(4,8)+c(s,4), w(5,8)+c(s,5), w(6,8)+c(s,6) =min16,12,15= 12 階段 4: c(s,t)=minw(7,t)+c(s,7), w(8,t)+c(s,8)=min20,16= 16 2、最有子結(jié)構(gòu)的性質(zhì)：最優(yōu)解的子結(jié)構(gòu)也是最優(yōu)的。3、動態(tài)規(guī)劃的基本要素： （1）最優(yōu)子結(jié)構(gòu)：問題的最優(yōu)解是由其子問題的最優(yōu)解所構(gòu)

44、成的。（2）重疊子問題：子問題之間并非相互獨立的，而是彼此有重疊的。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 19 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點4、動態(tài)規(guī)劃算法的步驟：1.找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特性。2.遞歸地定義最優(yōu)解。3.以自底向上的方式計算出各子結(jié)構(gòu)的最優(yōu)值，并流入表格中保存。4.根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。5、在有 n 個頂點的凸多邊形的三角剖分中，恰有n-3 條弦， n-2 個三角形?；厮莘?、三種搜索方法：（1）廣度優(yōu)先搜索的優(yōu)點是一定能找到解；缺點是空間復(fù)雜性和時間復(fù)雜

45、性都大。（2）深度優(yōu)先搜索的優(yōu)點是空間復(fù)雜性和時間復(fù)雜性較小；缺點是不一定能找到解。（3）啟發(fā)式搜索是最好優(yōu)先的搜索，優(yōu)點是一般來說能較快地找到解，即其時間復(fù)雜性更??；缺點是需要設(shè)計一個評價函數(shù)，并且評價函數(shù)的優(yōu)劣決定了啟發(fā)式搜索的優(yōu)劣。2、 回溯法是一種通用的算法，實為深度優(yōu)先的搜索方法。回溯法可以遞歸實現(xiàn)，也可以迭代實現(xiàn)?；厮莘ㄍǔＧ蠼馊悊栴}：(1)求排列：時間復(fù)雜性為o(f(n)n!) ；(2)求子集：時間復(fù)雜性為o(f(n)2n)；(3)求路徑：時間復(fù)雜性為o(f(n)kn)。這里 f(n)為處理一個結(jié)點的時間復(fù)雜性。3、分支限界法回溯法聯(lián)系與區(qū)別：支限界法類似于回溯法，也是一種在問

46、題的解空間樹t上搜索問題解的算法。但在一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出t中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達到極大或極小的解，即在某種意義下的最優(yōu)解。由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法在解空間樹t 上的搜索方式也不相同?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹t，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹 t。分支限界法的搜索策略是：在擴展結(jié)點處，先生成其所有的兒子結(jié)點（分支），然后再從當(dāng)前的活結(jié)點表中選擇下一個擴展對點。為了有效地選擇下一擴展結(jié)點，以加速搜

47、索的進程，在每一活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)這些已計算出的函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。分支界限法1、分支界限法德兩個要點：（1）評價函數(shù)的構(gòu)造。 （2）搜索路徑的構(gòu)造。2、所謂 分支限界法 就是通過評價函數(shù)及其上下界函數(shù)的計算，將狀態(tài)空間中不可能產(chǎn)生最佳解的子樹剪去，減少搜索的范圍，提高效率。因而更準(zhǔn)確的稱呼應(yīng)是“界限剪支法”精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 20 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知

48、識點字符串1、幾個名詞的定義：串的長度，子串，位置，串相等，模式匹配。簡單模式匹配算法在正文設(shè)置一個指針指向第一個然后跟模式串匹配。不行就指針加一直到匹配成功或者正文結(jié)束。時間復(fù)雜度為o(m+n)最壞為 o(mn) 2、kmp 算法 ：時間復(fù)雜度為o(m+n)。next(j) 函數(shù)的計算 (計算到第j 個就是從1 到 j-1 這個子串首位分別截取盡可能長的相同子串。從尾巴那里截取的子串不用倒過來。得到的最長相同子串長+1 就是next(j)的值啦。 next(1)固定等于0。 恒有 next(2) = 1)，int kmp_strmatch(sstring s, sstring p)int i

49、 = 1, j = 1, m = 0; while(i = s0 & j p0) m = i j + 1; return(m); = newnext 函數(shù)的計算 = void get_newnext() int k,j; newnext1=0; j=2; while(j=p0) k=nextj; if(k=0|pk!=pj) newnextj=k; else newnextj=newnextk; j=j+1; 3、bm 算法： boyer-moore 串匹配算法 (簡稱 bm 算法 )。最壞時間復(fù)雜度o(mn) 其思想是在匹配過程中，一旦發(fā)現(xiàn)在正文中出現(xiàn)模式中沒有的字符時就可以將模式、

50、正文大幅度地“滑過”一段距離。同時考慮到多數(shù)不匹配的情形是發(fā)生在最后的若干個字符，采用從左到右的方式掃描將浪費很多時間，因此改自右到左的方式掃描模式和正文精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 21 頁，共 23 頁 - - - - - - - - -學(xué)習(xí)必備精品知識點= dist 函數(shù)的計算 = m c p , 或 c= pm且 c pj(0jm) dist(c) = m j 否則(j=maxc= pj, 0jm) 4、kr算法： 指印函數(shù)的要求： （1）速度快。（2）沖突概率小。 （ 3）相鄰兩個字符串的hash值必須有相關(guān)性。5、kr

51、算法的基本思想：首先計算模式串和正文串所有長度為m 的子串的指印函數(shù)；然后匹配與模式串指印函數(shù)相等的正文串中的子串，找到匹配串。6、kmp 算法， bm 算法， kr算法的優(yōu)缺點：三者中 kmp 算法的最壞情形下的時間復(fù)雜度最低，而平均情形則三者差不多。kmp 算法最早提出，應(yīng)用也最廣泛，而且它的優(yōu)勢在于無需對正文回溯，當(dāng)正文不能一次性讀入內(nèi)存時，這種優(yōu)勢是顯而易見的。bm 算法的平均性能也很出色，但它需要對正文進行回溯，所以當(dāng)正文不能一次性讀入內(nèi)存時，可能會出現(xiàn)“抖動”，需要用雙緩沖區(qū)技術(shù)來處理這一問題。 kr 算法的優(yōu)勢在于可以推廣到二維模型，而且可以并行地處理，所以較多地運用于圖形圖像領(lǐng)域。np完全問題1、np 類問題定義 ：由非確定性圖靈機再多項式時間內(nèi)可以計算的判定問題2、np 困難問題與npc問題是一類問題么？就旅行商問題和判定問題談?wù)勀愕目捶?。不一定：對于問題q，若滿足qnp 且