數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)知識(shí)點(diǎn)(兼容版)

1、數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)復(fù)習(xí)要點(diǎn)：第一章1.相關(guān)基本概念：數(shù)據(jù)、數(shù)據(jù)元素（基本單位）、數(shù)據(jù)項(xiàng)（最小單位）、算法及其特征等；數(shù)據(jù)：所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號總稱。數(shù)據(jù)元素：基本單位。數(shù)據(jù)項(xiàng)：最小單位。算法特征（5點(diǎn)）：有窮性；確定性；可行性；輸入；輸出。2.邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）及其類型；邏輯結(jié)構(gòu)有四種基本類型：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)。數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。注：期中考題目數(shù)據(jù)結(jié)構(gòu)分為兩大類，即為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。其中邏輯結(jié)果又分為 線性結(jié)構(gòu)和非線性結(jié)構(gòu) ，存儲(chǔ)結(jié)構(gòu)一共

2、有四種（順序、鏈接、索引、散列）。3.算法分析：語句頻度（執(zhí)行次數(shù)）計(jì)算、時(shí)間和空間復(fù)雜度分析。表示方法語句頻度：直接寫次數(shù)。時(shí)間復(fù)雜度：O(執(zhí)行次數(shù)),如：O(n)。空間復(fù)雜度：O(所需空間)第二章 1.順序表（數(shù)組）插入、刪除、有序表合并算法及其移動(dòng)次數(shù)計(jì)算；1213212428304277 數(shù)據(jù)元素 序號 1 2 3 4 5 6 7 8表示 L.elem0 1 2 3 4 5 6 7順序表插入 算法思想：如果要在序號5前插入元素e，需要將序號58向后移動(dòng)一個(gè)位置。 移動(dòng)次數(shù)為4次，公式n-i+1 順序表刪除 算法思想：如果要?jiǎng)h除序號5元素，需要將68依次向前移動(dòng)一位移動(dòng)次數(shù)為3次，公式n

3、-i 有序表合并 LA = (3,5,8,11) LB = (2,6,8,9,11,15,20) 則LC = (2,3,5,6,8,8,9,11,11,15,20) 算法思想（以非遞減為例）：La和Lb非遞減排列，La與Lb中元素逐個(gè)比較，較小的先插入Lc中。 注：非遞減是指遞增排序，但元素有可能相等，與之相對的有非遞增排序。 移動(dòng)次數(shù)為（La.length + Lb.length） 2.鏈表（有無頭節(jié)點(diǎn)、單雙、循環(huán)）插入(前、后)、刪除（前、本身、后）的指針掛接、建立（不帶頭節(jié)點(diǎn)）算法。單鏈表 每個(gè)節(jié)點(diǎn)有數(shù)據(jù)域和指針域 data next 頭 a1 a2 a3 a4 a5 a6帶頭節(jié)點(diǎn)L P

4、 a1 a2 a3 a4 a5 a6 不帶頭節(jié)點(diǎn)L P單循環(huán)鏈表 在P（a3）節(jié)點(diǎn)前插入S節(jié)點(diǎn) (1)Q = P; /先讓Q指向a3(2)P = L; /P指向第一個(gè)節(jié)點(diǎn)（帶頭結(jié)點(diǎn)指向頭結(jié)點(diǎn)，不帶頭結(jié)點(diǎn)指向a1）(3)while(P-next != Q) P = P-next; /找到a3的前驅(qū)a2，P指向a2(4)S-next = P-next; /P-next為a3，讓S-next等于a3(5)P-next = S; /a2指針域指向節(jié)點(diǎn)S在P（a3）節(jié)點(diǎn)后插入S節(jié)點(diǎn)(1)S-next = P-next;(2)P-next = S;刪除P（a3）前一個(gè)節(jié)點(diǎn) (1)Q = P; (2)P =

5、 L; (3)while(P-next-next != Q) P = P-next; /找到a1 (4)P-next = P-next-next; /讓a1指針域指向a3，從而刪除a2刪除P（a3）節(jié)點(diǎn) (1)Q = P; (2)P = L; (3)while(P-next != Q) P = P-next; /找到a2 (4)P-next = P-next-next; /讓a2指針域指向a4，從而刪除a3刪除P（a3）后一個(gè)節(jié)點(diǎn) (1)P-next = P-next-next; /讓a3指針域指向a5，從而刪除a4雙鏈表 每個(gè)節(jié)點(diǎn)有前驅(qū)指針、數(shù)據(jù)域、后繼指針 prior data next

6、雙循環(huán)鏈表 頭 a1 a2 a3 a4 在P（a2）節(jié)點(diǎn)前插入S節(jié)點(diǎn) 技巧：先讓S-prior 和S-next與鏈表建立關(guān)系 注：步驟(4)必須在步驟(3)后面 (1)S-next = P; /先讓S-next指向a2 (2)S-prior = P-prior; /S-prior指向a1 (3)P-prior-next = S; /再把a(bǔ)1-next指向S (4)P-prior = S; / a2-prior指向S在P（a2）節(jié)點(diǎn)后插入S節(jié)點(diǎn) 注：步驟(4)必須在步驟(3)后面 (1)S-prior = P; (2)S-next = P-next; (3)P-next-prior = S; /

7、a3-prior指向S (4)P-next = S;刪除P（a2）前一個(gè)節(jié)點(diǎn)a1 (1)Q = P-prior; /Q指向要被刪除的a1; (2)P-prior = P-prior-prior; /P-priro指向頭 (3)P-prior-next = P; /頭-next指向P (4)free(Q); /釋放a1的存儲(chǔ)空間刪除P（a2）節(jié)點(diǎn) (1)P-next-prior = p-prior; (2)P-prior-next = p-next; (3)free(P);刪除P（a2）后一個(gè)節(jié)點(diǎn)a3 (1)Q = P-next; (2)P-next = P-next-next; /a2-nex

8、t指向a4 (3)P-next-prior = P; /a4-prior = P (4)free(Q); /釋放a3存儲(chǔ)空間建立（不帶頭節(jié)點(diǎn)）單鏈表讀程序：設(shè)n為2（i取0，1）i = 0時(shí)， pLqi = 1時(shí)， Lq p Lq p L qp第三章 1.棧的進(jìn)出序列、棧、隊(duì)列、循環(huán)隊(duì)列的滿/空條件; 由于棧的插入、刪除操作是限制在棧頂進(jìn)行的，因而后進(jìn)棧的元素必然是先出棧，0.所以棧是“后進(jìn)先出”表。由于隊(duì)列的輸入、輸出操作分別在隊(duì)的兩端進(jìn)行，因此先入隊(duì)的元素必然先輸出，故隊(duì)列又稱為“先進(jìn)先出”表 棧的進(jìn)出序列 例題：進(jìn)棧序列為123，可能得到的出棧序列是什么？ 答：共五種123/132/21

9、3/231/321 進(jìn)出棧情況（以132序列為例）：1進(jìn)棧1出棧，輸出12進(jìn)棧3進(jìn)棧3出棧2出棧 輸出32棧、隊(duì)列、循環(huán)隊(duì)列的滿/空條件 ?？諚l件：s.top = s.base;棧滿條件：s.top - s.base = stacksize; 隊(duì)空條件：Q.front=Q.rear; 隊(duì)滿條件：q-rear - q-front = MAXSIZE循環(huán)隊(duì)列空條件：Q.front=Q.rear循環(huán)隊(duì)列滿條件：為避免在隊(duì)滿是隊(duì)頭指針和隊(duì)尾指針也是重合的情況，規(guī)定隊(duì)列中還有一個(gè)空的存儲(chǔ)單元時(shí)為隊(duì)滿，即為Q.front=(Q.rear+1)MOD maxsize(MOD為取余運(yùn)算符）。因而，這種循環(huán)隊(duì)列

10、不適合用動(dòng)態(tài)數(shù)組作為存儲(chǔ)結(jié)構(gòu)。 2. 棧、隊(duì)列的存儲(chǔ)結(jié)構(gòu)、基本操作算法（雙向棧）; 棧存儲(chǔ)結(jié)構(gòu)順序棧 typedef structSElemType *base;SElemType *top;int stacksize; SqStack;鏈?zhǔn)綏ｊ?duì)列存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 雙向棧存儲(chǔ)結(jié)構(gòu)：typedef struct Elemtype *base2; Elemtype *top2; BDStacktype; /雙向棧類型初始化：Status Init_Stack(BDStacktype &tws, int m)/初始化一個(gè)大小為m的雙向棧tws tws.base0 = (Elemt

11、ype*)malloc(sizeof(Elemtype)*m); tws.base1 = tws.base0 + m; tws.top0 = tws.base0; tws.top1 = tws.base1; return OK; /Init_Stack入棧：Status push(BDStacktype &tws, int i, Elemtype x)/x入棧,i=0表示低端棧,i=1表示高端棧 if(tws.top0 tws.top1) return OVERFLOW; /注意此時(shí)的棧滿條件 if (i = 0) *tws.top0+ = x; else if (i = 1) *tws.to

12、p1- = x; else return ERROR;return OK; /push出棧：Status pop(BDStacktype &tws, int i, Elemtype &x) /x出棧,i=0表示低端棧,i=1表示高端棧 if (i = 0) if (tws.top0 = tws.base0) return OVERFLOW; x = *-tws.top0; else if(i = 1) if(tws.top1 = tws.base1) return OVERFLOW; x = *+tws.top1; else return ERROR; return OK; /pop第四章 1

13、.字符串模式匹配的簡單算法；int Index(SString S, SString T, int pos) / 算法4.5 / 返回子串T在主串S中第pos個(gè)字符之后的位置。 / 若不存在，則函數(shù)值為0。 / 其中，T非空，1posStrLength(S)。 int i = pos; int j = 1; while (i = S0 & j T0) return i-T0; else return 0; / Index 2.計(jì)算NEXT。 j ：1 2 3 4 5 6 7串 ：a b c a b a anextj：0 1 1 1 2 3 2技巧：第一二個(gè)肯定是0，1！如果要計(jì)算next4，找

14、的字符串必須是以第3個(gè)字符c為結(jié)尾，第1個(gè)字符a為開頭的。以第6個(gè)為例，a前一個(gè)字母是b，以第5個(gè)字符b為結(jié)尾的ab剛好和以第1個(gè)字符為開頭的ab匹配，所以next6 = 2+1 = 3。第五章 1.二維數(shù)組的地址（下標(biāo)）換算；習(xí)題5.1假設(shè)有二維數(shù)組A6*8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000，計(jì)算：（1）數(shù)組A的體積（即存儲(chǔ)量）6*8*6 = 288字節(jié)（3）按行存儲(chǔ)是，元素a14的第一個(gè)字節(jié)的地址 1000+(8*1+4)*6 = 1072 基址+(每行的元素個(gè)數(shù)*行數(shù)+當(dāng)前列序)*每個(gè)元素所占存儲(chǔ)單元（4）按列存儲(chǔ)時(shí)，元素a47的第

15、一個(gè)字節(jié)的地址 1000+(6*7+4)*6 = 6276 基址+(每列的元素個(gè)數(shù)*列數(shù)+當(dāng)前行序)*每個(gè)元素所占存儲(chǔ)單元習(xí)題5.2假設(shè)按低下標(biāo)優(yōu)先存儲(chǔ)整數(shù)組A9*3*5*8時(shí)，第一個(gè)元素的字節(jié)地址是100，每個(gè)整數(shù)占四個(gè)字節(jié)。問下列元素的存儲(chǔ)地址是什么？（2）a1111 地址：100+(3*5*8*1+5*8*1+8*1+1)*4 = 776（3）a3125 地址：100+(3*5*8*3+5*8*1+8*2+5)*4 = 1784（4）a8247 地址：100+(3*5*8*8+5*8*2+8*4+7)*4 = 4416 2.特殊矩陣（三角、其他有規(guī)律）壓縮為一維的下標(biāo)計(jì)算；下三角矩陣壓縮

16、為一維數(shù)組（記憶公式） 技巧：推薦把公式(2)背下來（i,j,R范圍都是從0開始），其他根據(jù)范圍變化公式 (1)若1=j,j=n, 0=R=j時(shí)，k = i(i-1)/2+j-1; 當(dāng)ij時(shí)，k = j(j-1)/2+i-1.(2)若0=i,j=n-1, 0=R=j時(shí)，k = (i+1)i/2+j; 當(dāng)jj時(shí)，k = (j+1)j/2+i.(3)若1=j,j=n, 1=R=j時(shí)，k = i(i-1)/2+j; 當(dāng)ij時(shí)，k = j(j-1)/2+i;(4)若0=j,j=n-1, 1=R=j時(shí)，k = (i+1)i/2+j+1; 當(dāng)i1，則其雙親是i/2。 (2)如果2in，則結(jié)點(diǎn)i無左孩子；

17、如果2in，則其左孩子是2i。 (3)如果2i+1n，則結(jié)點(diǎn)i無右孩子； 如果2i+1n，則其右孩子是2i+1。 2.二叉樹的先序、中序、后序、層次遍歷過程；樹的先序、后序、層次遍歷過程；二叉樹遍歷過程：先（根）序遍歷：根左子樹右子樹中（根）序遍歷：左子樹根右子樹后（根）序遍歷：左子樹右子樹根層次遍歷：從上到下，從左往右，逐個(gè)遍歷樹的遍歷過程：先根（次序）遍歷：先訪問根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹(根子樹)后跟（次序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點(diǎn)（子樹根）層次遍歷：從上到下，從左往右，逐個(gè)遍歷注：樹與二叉樹相互轉(zhuǎn)化后樹的先根遍歷相當(dāng)于二叉樹的先序遍歷樹的后根遍歷相當(dāng)于二叉

18、樹的中序遍歷 3.給出兩個(gè)遍歷序列，畫出樹（二叉樹、樹）習(xí)題6.23畫出和下列已知序列對應(yīng)的樹T：(1)樹的先根次序訪問序列為GFKDAIEBCHJ;(2)樹的后根次序訪問序列為DIAEKFCJHBG。注：樹的后根遍歷相當(dāng)于二叉樹的中序遍歷G 由(1)知G為根； G為根，聯(lián)系(2)知G無右子樹； 觀察(1)，F(xiàn)為G左子樹；F 根據(jù)，觀察(2)知DIAEK在F左邊， CJHB在F右邊；BK 觀察(1)，K為F左子樹； 根據(jù)，觀察(2)知K無右子樹； 觀察(1)，D為K左子樹；CD 根據(jù)，觀察(2)知D無左子樹； 觀察(1)，A為D右子樹； 觀察(2)，IE分別為A左右子樹；AH F的右子樹自行觀

19、察判斷。JEI 4.二叉樹與樹相互轉(zhuǎn)換；樹轉(zhuǎn)化成二叉樹： 規(guī)則：樹的最左孩子變成二叉樹左子樹，該左孩子的兄弟變成二叉樹左子樹的右子樹 注：原樹中B為A最左孩子，C,D為B兄弟，變成二叉樹后C成為B右子樹，D成為C右子樹。 二叉樹轉(zhuǎn)化成樹 5.求哈夫曼樹和給出編碼、帶權(quán)路徑長度計(jì)算。習(xí)題6.26假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07, 0.19, 0.02, 0.06, 0.32, 0.21, 0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼，并求帶權(quán)路徑長度設(shè)這8個(gè)結(jié)點(diǎn)為A、B、C、D、E、F、G、H，其相應(yīng)的權(quán)為7、19、2、6、32、3、21、10。當(dāng)前未用權(quán)：7、

20、19、2、6、32、3、21、10，選出2、3構(gòu)造出5。當(dāng)前未用權(quán)：7、19、6、32、21、10、5，選出5、6構(gòu)造出11。當(dāng)前未用權(quán)：7、19、32、21、10、11，選出7、10構(gòu)造出17。當(dāng)前未用權(quán)：19、32、21、11、17，選出11、17構(gòu)造出28。當(dāng)前未用權(quán)：19、32、21、28，選出19、21構(gòu)造出40。當(dāng)前未用權(quán)：32、28、40，選出32、28構(gòu)造出60。剩下權(quán)：40、60，構(gòu)造出100 編碼：樹的左分支為0，右分支為1。得到哈夫曼編碼為A:1101 B:01 C:11111 D:1110 E:10 F:11110 G:00 H:1100帶權(quán)路徑長度：(7*4+19*2

21、+2*5+6*4+32*2+3*5+21*2+10*4)/100 = 2.61注：該公式為：A路徑長*A權(quán)+B路徑長*B權(quán)+H路徑長*H權(quán)，因?yàn)樵O(shè)的權(quán)值是原來的100倍，所以結(jié)果除以100。第七章 1.鄰接矩陣、鄰接表存儲(chǔ)結(jié)構(gòu)及其特征；注：以有向圖G1為例(有路徑用1，否則0)v1 v2 v3 v4v1 0 1 1 0 v2 0 0 0 0v3 0 0 0 1v4 1 0 0 0 注：以有向圖G1為例標(biāo)號 0 1 2 3 0 0 1 1 0 1 0 0 0 0 2 0 0 0 1 3 1 0 0 0第0行值為1的是1、2，所以有V121。第1行值全為0，所以有V2。第2行值為1的是3，所以有V

22、33。第3行值為1的是0，所以有V40。 2.求最小生成樹（Prim、Kruskal）； 普里姆（Prim）： 以點(diǎn)為基礎(chǔ)從V1開始，找到最小邊(V1,V3)；尋找與V1、V3相關(guān)聯(lián)的最小邊，找到(V3,V6)；尋找與V1、V3、V6相關(guān)聯(lián)的最小邊，找到(V6，V4)；尋找與V1、V3、V6、V4相關(guān)聯(lián)的最小邊，此時(shí)有(V4,V1)和(V3,V2)，因?yàn)?V4,V1)與原來的邊構(gòu)成圈，所以選擇(V3,V2)。（如果(V4,V1)不與原來的邊構(gòu)成圈，則二條邊任選一條）；尋找與V1、V3、V6、V4、V2相關(guān)聯(lián)，并且不與原來邊構(gòu)成圈的最小邊，找到(V2,V5)；克魯斯卡爾(Kruskal)（避圈法

23、）：以邊為基礎(chǔ) 方法介紹：依次尋找權(quán)最小邊，避免生成一個(gè)圈，所有點(diǎn)聯(lián)通時(shí)生成最小樹。 3.拓?fù)渑判?；步驟：（1）在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之。 （2）從圖中刪除該頂點(diǎn)和所有以它為尾的弧。輸出： V6 V1 V4 V2 V5注：拓?fù)渑判虿晃ㄒ弧?.求最短路徑過程（Dijkstra、Floyd）。迪杰斯特拉(Dijkstra) 習(xí)題7.11試?yán)肈ijkstra算法求題7.11圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫出執(zhí)行算法過程中各步狀態(tài)。求解過程：K=1時(shí)，找a能直接到達(dá)的點(diǎn)，有b,c,d，(a,c)權(quán)最小，(a,c)為a到c最短路徑，將c放如終點(diǎn)集S；K=2時(shí)，找a能直接到達(dá)的點(diǎn)，

24、或通過(a,c)能到達(dá)的點(diǎn)，(a,c,f)權(quán)最小，(a,c,f)為a到f的最短路徑，將f放入終點(diǎn)集S；K=3時(shí)，找a能直接到達(dá)的點(diǎn)，或通過(a,c)能到達(dá)的點(diǎn)，或通過(a,c,f)能到達(dá)的點(diǎn)，(a,c,e)權(quán)最小，(a,c,e)為a到e最短路徑，將e放入終點(diǎn)集S；K=4時(shí)，找a能直接到達(dá)的點(diǎn)，或通過(a,c)能到達(dá)的點(diǎn)，或通過(a,c,f)能到達(dá)的點(diǎn)，或通過(a,c,e)能到達(dá)的點(diǎn)，(a,c,f,d)為a到d最短路徑，將d放入終點(diǎn)集S；K=5時(shí)，找a能直接到達(dá)的點(diǎn)，或通過(a,c)能到達(dá)的點(diǎn)，或通過(a,c,f)能到達(dá)的點(diǎn)，或通過(a,c,e)能到達(dá)的點(diǎn)，或通過(a,c,f,d)能到達(dá)的點(diǎn)，(

25、a,c,f,d,g)權(quán)最小，為a到g最短路徑，將g放入終點(diǎn)集S；K=6時(shí)，只剩下(a,b)，(a,b)為a到b最短路徑，將b放入終點(diǎn)集S。弗洛伊德(Floyd) 注：D(1)ij是從Vi到Vj的中間頂點(diǎn)的序號不大于1的最短路徑的長度；D(k) ij是從Vi到Vj的中間頂點(diǎn)的序號不大于k的最短路徑的長度；D(n-1) ij就是從Vi到Vj的最短路徑的長度。D(-1)欄中，ViVj不允許有轉(zhuǎn)折點(diǎn)。直接填鄰接矩陣。D(0)欄中，ViVj只允許通過V0轉(zhuǎn)折，或者不轉(zhuǎn)折。通過V0轉(zhuǎn)折權(quán)值小于原權(quán)值，就把原權(quán)值替換掉。D(1)欄中，ViVj只允許通過V0、V1轉(zhuǎn)折，或者不轉(zhuǎn)折。如果轉(zhuǎn)折后權(quán)值小于原權(quán)值，替

26、換。D(2)欄中，VjVj允許通過V0、V1、V2轉(zhuǎn)折，或者不轉(zhuǎn)折，如果轉(zhuǎn)折后權(quán)值小于原權(quán)值，替換。此時(shí)p(2)中就是各點(diǎn)間的最短路徑。第九章 1.以下所有查找成功平均查找長度2.順序查找；折半查找；順序查找：從表中最后一個(gè)記錄開始，逐個(gè)進(jìn)行比較。平均查找長度 等概率時(shí)，平均查找長度ASL = (n+1)/2 不等概率時(shí)，ASL = nP1 + (n-1)P2 + + 2Pn-1 + Pn折半查找：指針low和high分別指示待查元素所在范圍的下界和上界，mid=(low+high)/2，如果要找的值大于Smid，則讓mid = (mid+1 + high)/2，繼續(xù)比較；如果要找的值小于Sm

27、id，則讓mid = (low + mid-1)/2，繼續(xù)比較。平均查找長度 等概率條件下，ASL= n+1nlog2(n+1)-1當(dāng)n50時(shí)，有近似結(jié)果ASL=log2(n+1)-13.二叉排序樹的插入（建立）、刪除、平衡過程；二叉排序樹建立 (1)若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； (2)若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； (3)它的左、右子樹也分別為二叉排序樹。注：中序遍歷二叉 排序樹，得到從小到大序列根據(jù)字母的先后確定大小插入Jan；F小于J，F(xiàn)eb成為Jan左子樹；M大于J，Mar成為Jan右子樹；Apr小于Jan，且Apr小于

28、Feb，Apr成為Feb左子樹；May大于Jan，且May大于Mar，May成為Mar右子樹；June大于Jan，且June小于Mar，June成為Mar左子樹。剩下的略。二叉排序樹刪除（） 3種情況：(1)*p為葉子節(jié)點(diǎn)，直接刪除。(2) *p只有一個(gè)孩子*child只需將*child和*p的雙親直接連接后，即可刪去*p。(3)*p有兩個(gè)孩子用*p的直接前驅(qū)或直接后繼代替*p，然后刪除它的直接前驅(qū)或直接后繼。平衡二叉樹：樹上任何節(jié)點(diǎn)的左右子樹深度差都不超過1 插入節(jié)點(diǎn)P后不平衡，找到離P最近的不平衡點(diǎn)，根據(jù)二叉排序樹的建立進(jìn)行調(diào)整。 序列：Jan, Feb, Mar, Apr, May, J

29、une, July, Aug, Sep, Oct, Nov, Dec(1) 插入Aug時(shí)，F(xiàn)eb左右子樹深度差超過1不平衡(2) 插入Oct時(shí)，最近不平衡點(diǎn)為May。因?yàn)镾epOctMay，所以O(shè)ct作為雙親(3) 插入Nov時(shí)，Jan不平衡。把Jan左轉(zhuǎn)，Mar的左子樹變成Jan右子樹。最終平衡樹4.哈希表構(gòu)造、沖突解決方法；除留余數(shù)法、線性探測或鏈地址法。構(gòu)造：除留余數(shù)法：H(key) = key MOD p, p=m 沖突解決：線性探測法：Hi = (H(key)+ di) Mod m i = 1, 2, , k(k = m-1)鏈地址法：將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中。

30、例題：已知一個(gè)線性表（38，25，74，63，52，48），假定采用散列函數(shù)h(key)=key%7計(jì)算散列地址，并散列存儲(chǔ)在散列表A0.6中，采用線性探測方法解決沖突。38：38%7 = 3，查找次數(shù)為1。25：25%7 = 4，查找次數(shù)為1。74：74%7 = 4，與25沖突，(4+1)%7 = 5，查找次數(shù)為2。63：63%7 = 0，查找次數(shù)為1.52：52%7 = 3，與38沖突，(3+1)%7 = 4，與25沖突，(4+1)%7 = 5，與74沖突，(5+1)%7 = 6，查找次數(shù)為4。48：48%7=6，與52沖突， (6+1)%7 = 0，與63沖突， (0+1)%7 = 1，

31、查找次數(shù)為3地址： 0 1 2 3 4 5 6633825745248次數(shù)： 1 3 1 1 2 4 等概率成功查找的平均查找長度為： (1+3+1+1+2+4)/6 = 2第十章1.簡單排序（直接插入、選擇、冒泡）的過程；直接插入（略）選擇排序基本思想：依次在序列中選出最小的記錄Rk，將它與第1個(gè)記錄R1交換。模式：for (i = 0; i 10; i+)for (j = i; j 10; j+);冒泡排序： 基本思想：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。 模式：for(i = 0; i n; i+)for(j = 0; j n-i-1; j+);2.先進(jìn)排序（希爾、快速、

32、堆、歸并、基數(shù)）過程；希爾排序：基本思想：先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，所有距離為dl的倍數(shù)的記錄放在同一個(gè)組中，先在各組內(nèi)進(jìn)行直接插人排序；然后，取第二個(gè)增量d2d1重復(fù)上述的分組和排序，直至所取的增量di=1?？焖倥判颍夯舅枷耄哼x第一個(gè)記錄為支點(diǎn)，通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄關(guān)鍵字比支點(diǎn)小，另一個(gè)部分記錄的關(guān)鍵字比支點(diǎn)大。再可分別找兩個(gè)支點(diǎn)，對這兩部分記錄繼續(xù)進(jìn)行快速排序。堆排序：n個(gè)關(guān)鍵字序列Kl，K2，Kn稱為堆，必須所有根大于（或小于）其子樹。例題：無序序列49, 38, 65, 97, 76, 13, 27, 49，進(jìn)行堆排序思路：將次序列寫

33、出完全二叉樹形式，然后從最有一個(gè)非終端結(jié)點(diǎn)開始篩選。歸并排序：基數(shù)排序： 先將個(gè)位數(shù)值與fi中的i值相等的放入相應(yīng)位置 將十位數(shù)值與fi中的i值相等的放入相應(yīng)位置 將百位數(shù)值與fi中的i值相等的放入相應(yīng)位置3.各種排序的特點(diǎn)、穩(wěn)定性、時(shí)間復(fù)雜度（包括平均、最好、最壞）。希爾排序 O(nlogn) O(n2)排序方法穩(wěn)定性插入排序穩(wěn)定選擇排序不穩(wěn)定冒泡排序穩(wěn)定希爾排序不穩(wěn)定快速排序不穩(wěn)定堆排序不穩(wěn)定歸并排序穩(wěn)定基數(shù)排序穩(wěn)定數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)：帶有結(jié)構(gòu)和操作的數(shù)據(jù)元素集合 結(jié)構(gòu)：數(shù)據(jù)元素之間的關(guān)系；操作：對數(shù)據(jù)的加工處理 ； 數(shù)據(jù)結(jié)構(gòu)研究的問題：非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，及如何表示，如何存儲(chǔ)，如

34、何處理。（字符 字符串 文字 圖形 圖象 聲音）v 對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下三方面的問題：v 數(shù)據(jù)的邏輯結(jié)構(gòu)；邏輯結(jié)構(gòu) 它屬于用戶的視圖，是 面向問題的 數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：集合：“屬于同一個(gè)集合”；線性結(jié)構(gòu)：一對一的線性關(guān)系；樹結(jié)構(gòu)：一對多的層次關(guān)系；圖結(jié)構(gòu)：多對多的任意關(guān)系。v 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的物理存儲(chǔ)方式，屬于具體 實(shí)現(xiàn)的視圖 ，是 面向計(jì)算機(jī) 的 通常有兩種存儲(chǔ)結(jié)構(gòu)：1. 順序存儲(chǔ)結(jié)構(gòu)：用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲(chǔ)位置來表示。2. 鏈接存儲(chǔ)結(jié)構(gòu)：用一組任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用指針

35、來表示。 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲(chǔ)結(jié)構(gòu)來存儲(chǔ) 數(shù)據(jù)結(jié)構(gòu)的抽象層次 線性結(jié)構(gòu) 直接存取類 數(shù)組 , 文件 順序存取類 表, 棧, 隊(duì)列 , 優(yōu)先隊(duì)列 廣義索引類 線性索引 , 搜索樹非線性結(jié)構(gòu) 層次結(jié)構(gòu)類 樹，二叉樹，堆 群結(jié)構(gòu)類 集合，圖v 3）數(shù)據(jù)的運(yùn)算，即對數(shù)據(jù)施加的操作 算法分析:時(shí)間復(fù)雜度 算法的概念:算法是求解問題的操作序列（或操作步驟）。 時(shí)間復(fù)雜度T（n）:以求解問題的基本操作（原操作）的執(zhí)行次數(shù)作為算法時(shí)間的度量for (i=1; i=n; i+)for (j=1; j=n; j+)x+;單條語句O（1）一條循環(huán)O（n）兩條循環(huán)O(n2).1、 線性表線性表的邏輯結(jié)構(gòu)：

36、在線性表中，除第一個(gè)元素和最后一個(gè)元素外，其他元素都有且僅有一個(gè)直接前趨，有且僅有一個(gè)直接后繼。 順序表存儲(chǔ)特點(diǎn)：1）元素存儲(chǔ)在一組連續(xù)的內(nèi)存單元中2）通過元素的存儲(chǔ)順序反映線性表中數(shù)據(jù)元素之間的邏輯順序；順序表操作特點(diǎn)：1）可隨機(jī)存取順序表的元素；2）順序表的插入刪除操作要通過移動(dòng)元素實(shí)現(xiàn)線性鏈表存儲(chǔ)特點(diǎn)：1）用任意一組的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素；2） 通過保存直接后繼元素的存儲(chǔ)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系；線性鏈表操作特點(diǎn)1）不能隨機(jī)存取元素； 2）插入、刪除操作通過修改結(jié)點(diǎn)的指針實(shí)現(xiàn)；順序表的插入平均要移動(dòng)表的一半元素 n/2、刪除操作平均要移動(dòng)(n-1)/2順序表能隨機(jī)存取元

37、素的原因是：順序表能通過L.elemi-1或L.elem+(i-1)直接定位元素的存儲(chǔ)地址。線性鏈表不能隨機(jī)存取元素的原因是： 需從線性鏈表的頭指針開始，順著鏈指針定位元素的存儲(chǔ)地址對于經(jīng)常要存取元素的應(yīng)用，線性表應(yīng)采用順序存儲(chǔ)結(jié)構(gòu)10 對于經(jīng)常要插入刪除元素的應(yīng)用，線性表應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2、 棧和隊(duì)列棧：棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表；后進(jìn)先出2 表尾稱為棧頂，表頭稱為棧底；3 棧的滿空判斷4 棧頂元素的位置由一個(gè)棧頂指針指示；5 進(jìn)棧、出棧操作要修改棧頂指針；6 一個(gè)棧的輸入序列為a,b,c，則所有可能的出棧序列為： abc,acb,bac,bca,cba7棧的順序存儲(chǔ)

38、結(jié)構(gòu) 1） 用一組連續(xù)的內(nèi)存單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素； 2） 棧頂元素的位置由棧頂指針指示；8 棧的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) 棧的鏈?zhǔn)酱鎯?chǔ)與線性表的鏈?zhǔn)酱鎯?chǔ)類似，可用帶頭結(jié)點(diǎn)的線性鏈表存儲(chǔ)。注意：棧頂指針就是帶頭結(jié)點(diǎn)的線性鏈表的頭指針隊(duì)列：隊(duì)列是限定僅能在表尾一端插入，表頭一端刪除操作的線性表；先進(jìn)先出2 表尾稱為隊(duì)頭，表頭稱為隊(duì)尾 3 隊(duì)頭、隊(duì)尾元素的位置分別由隊(duì)頭指針和隊(duì)尾指針指示；4 隊(duì)列的滿空判斷5 入隊(duì)操作要修改隊(duì)尾指針，出隊(duì)操作要修改隊(duì)頭指針；6 循環(huán)隊(duì)列隊(duì)列的順序存貯結(jié)構(gòu)3、 數(shù)和二叉樹1 樹的邏輯結(jié)構(gòu)樹：是一種一對多的結(jié)構(gòu)關(guān)系或稱為分枝結(jié)構(gòu)關(guān)系，除了根之外，每個(gè)元素只有一個(gè)直接

39、前趨；，但每個(gè)元素可以有零個(gè)或多個(gè)直接后繼；2 樹的基本術(shù)語：樹的結(jié)點(diǎn) 孩子結(jié)點(diǎn) 雙親結(jié)點(diǎn) 兄弟結(jié)點(diǎn) 結(jié)點(diǎn)層（根為1） 樹的高度（層數(shù)） 結(jié)點(diǎn)的度（結(jié)點(diǎn)子樹的個(gè)數(shù)） 樹的度（樹中最大的結(jié)點(diǎn)度） 葉子結(jié)點(diǎn)（度為0的結(jié)點(diǎn)） 分枝結(jié)點(diǎn)（度不為0的結(jié)點(diǎn)） 森林（互不相交的樹集合）3 二叉樹的定義：或?yàn)榭諛洌蛴筛皟深w不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹。4 二叉樹的五種基本形態(tài)l 5 二叉樹性質(zhì)性質(zhì)1 在二叉樹的第i 層上最多有2(i-1)個(gè)結(jié)點(diǎn)性質(zhì)2 深度為k的二叉樹最多有 2k-1 個(gè)結(jié)點(diǎn)，最少有k個(gè)結(jié)點(diǎn)性質(zhì)3 設(shè)二叉樹葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0 = n2

40、 +1性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2(n+1) 性質(zhì)5 在完全二叉樹中編號為i的結(jié)點(diǎn)，1）若有左孩子，則左孩編號為2i；2）若有右孩子，則有孩子結(jié)點(diǎn)編號為2i+1；3）若有雙親，則雙親結(jié)點(diǎn)編號為i/2；4) 結(jié)點(diǎn)所在層次為log2i+15) 若i為奇數(shù)，且i！=1，它處于右兄弟位置，則它的左兄弟為結(jié)點(diǎn)i-16) 若i為偶數(shù)，且i！=n，它處于左兄弟位置，則它的右兄弟為結(jié)點(diǎn)i+16 兩種特殊的二叉樹:滿二叉樹/完全二叉樹7 二叉樹的順序結(jié)構(gòu)8 二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)：二叉鏈表 二叉鏈表中每個(gè)結(jié)點(diǎn)至少包含三個(gè)域：數(shù)據(jù)域、左指針域、右指針域 9 遍歷：按某種搜索路徑訪問二叉樹的每個(gè)結(jié)點(diǎn)，

41、而且每個(gè)結(jié)點(diǎn)僅被訪問一次。先序遍歷、中序遍歷、后序遍歷10 遍歷的遞歸算法、遍歷的非遞歸算法遞歸：若二叉樹為空，結(jié)束 基本項(xiàng)（也叫終止項(xiàng)）若二叉樹非空 遞歸項(xiàng) （1）訪問根結(jié)點(diǎn)； （2）先序遍歷左子樹 （3）先序遍歷右子樹；11 線索二叉樹：加上結(jié)點(diǎn)前趨后繼信息（線索）的二叉樹稱為線索二叉樹l 12 樹與二叉樹的轉(zhuǎn)換樹二叉樹根根結(jié)點(diǎn)X的第一個(gè)孩子 結(jié)點(diǎn)X的左孩子結(jié)點(diǎn)X緊鄰的右兄弟 結(jié)點(diǎn)X的右孩子l 13 哈夫曼樹結(jié)點(diǎn)的帶權(quán)路徑長度：從根到該結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)權(quán)的乘積。帶權(quán)路徑長度最小的二叉樹稱為哈夫曼樹l 14 哈夫曼編碼左0右14、 圖1 生成樹：若T是G的生成樹當(dāng)且僅當(dāng)T滿足如下條件

42、T是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通 T包含G的所有頂點(diǎn) T中無回路2 數(shù)組表示法（鄰接矩陣）是圖的一種順序存儲(chǔ)結(jié)構(gòu)，鄰接表（逆鄰接表）是圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3 無向圖數(shù)組（鄰接矩陣）表示法特點(diǎn)：1）無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次；2）頂點(diǎn)v的度：等于二維數(shù)組對應(yīng)行（或列）中1的個(gè)數(shù)；3）判斷兩頂點(diǎn)v、u是否為鄰接點(diǎn)：只需判二維數(shù)組對應(yīng)分量是否為1；4）頂點(diǎn)不變，在圖中增加、刪除邊：只需對二維數(shù)組對應(yīng)分量賦值1或清0；5）設(shè)存儲(chǔ)頂點(diǎn)的一維數(shù)組大小為m(m圖的頂點(diǎn)數(shù)n), G占用存儲(chǔ)空間：m+m2；G占用存儲(chǔ)空間只與它的頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無關(guān)；適用于邊稠密的圖；對有向圖的數(shù)組表示法可做類似的討論4 有兩種遍歷方法（它們對無向圖，有向圖都適用）： 深度優(yōu)先遍歷 廣度優(yōu)先遍歷5 拓?fù)渑判颍?）在有向圖選一無前趨的頂點(diǎn)v，輸出；2）從有向圖中刪除v及以v為尾的孤；3）重復(fù)1、2、直接全部輸出全部頂點(diǎn)或有向圖中不存在無前趨頂l 6 最小生成樹l