軟件設計師培訓數據結構

1、數據結構1考點分析 模擬練習考綱解讀主 要 內 容數據結構知識點復習2考 綱 解 讀考綱要求數組、線性表（鏈表：單向鏈表、雙向鏈表、循環(huán)鏈表）、隊列、棧、樹（二叉樹、查找樹、平衡樹、線索樹、堆）、圖等的定義、存儲和操作。Hash（存儲地址計算、沖突的處理）。排序算法、查找算法、數值計算方法、字符串處理方法、數據壓縮算法、遞歸算法、圖的相關算法。算法與數據結構的關系、算法效率、算法設計、算法描述、算法復雜性。3考 綱 解 讀考點分布時間分值考核要點2016.510棧、二叉排序樹、二叉樹的性質、圖的遍歷、折半查找、動態(tài)規(guī)劃算法、貪心算法2015.510隊列、棧、二叉樹的遍歷、折半查找、簡單選擇排序

2、、快速排序2015.1111棧、隊列、矩陣的壓縮存儲、二叉樹、圖的遍歷、關鍵路徑、折半查找、插入排序、基數排序、算法時間復雜度2014.59隊列、線性表、二叉樹的順序存儲、折半查找、算法的時間復雜度、貪心算法2014.118線性表、二叉查找樹、模式匹配、快速排序算法、哈夫曼樹2013.59線性結構的時間復雜度、棧、隊列、貪心算法和背包問題、分治算法、二叉樹、哈希查找2013.119線性表的存儲結構、循環(huán)隊列、有向圖拓撲序列、哈夫曼樹、哈希表、插入排序、快速排序、動態(tài)規(guī)劃算法、回溯法4考 點 分 析常用數據結構的性質、定義方式和存儲方法；重要數據結構（樹、二叉樹、圖）的性質、存儲結構和訪問方式；

3、排序算法、查找算法的基本過程及效率；各種算法（如貪心算法、回溯法等）的基本思想。5第一部分 線性表分值：0 1分 （每年） 分數比重：0% 10%重要知識點： 1、順序表的結構特點 2、單鏈表的結構特點 3、雙向鏈表的插入刪除 4、循環(huán)鏈表的結構特點6第一部分 線性表線性表的特點：1）存在唯一的一個稱為“第一個”的數據元素；2）存在唯一的一個稱為“最后一個”的數據元素；3）除第一個之外，每個數據元素有且僅有一個前驅；4）除最后一個之外，每個數據元素有且僅有一個后繼。7第一部分 線性表順序表特點： 利用物理存儲位置的相鄰關系反應元素之間的次序關系優(yōu)點： 1.無需為表示結點間的邏輯關系而增加額外的

4、存儲空間； 2.可方便地隨機存取表中的任一元素。缺點： 1.插入或刪除運算不方便，需要移動大量的結點，其效率較低； 2.需要預先確定順序表的最大表長，由于順序表要求占用連續(xù)的存儲 空間，存儲分配只能預先進行靜態(tài)分配。因此當表長變化較大時， 難以確定合適的存儲規(guī)模。8第一部分 線性表單鏈表lista1d1a2d2a3d3a4d4物理狀態(tài)邏輯狀態(tài)d2d1d3d4a2a3a4a1d3d4d2優(yōu)點： 1.鏈表動態(tài)存儲分配的結構，能有效利用存儲空間；。 2. 插入或刪除時只需要修改指針，而不需要進行大量元素的移動。缺點： 1.必需為表示結點間的邏輯關系而增加額外的存儲空間； 2.不能隨機存取、訪問數據元

5、素。特點：單鏈表中邏輯上相鄰的數據元素在物理上不一定相鄰。數據元素之間的邏輯關系通過鏈指針間接地反映出來。9第一部分 線性表雙向鏈表特點：雙向鏈表中查找某結點的直接前驅結點和直接后繼結點的運算的 時間復雜度均為O(1) es bp a s-prior = p-prior; p-prior-next = s; s-next = p; p-prior = s; p-prior-next = p-next; p-next-prior = p-prior; a b c插入：刪除：p10第一部分 線性表循環(huán)鏈表 循環(huán)鏈表(Circular Linked List)：鏈表中最后一個結點的指針域指向整 個鏈

6、表的頭結點，從而使鏈表形成一個首尾相接的環(huán)形鏈表。特點：從鏈表尾部到鏈表頭部比較方便。從表中任一結點出發(fā)均可找到 表中其它結點。判空：表尾判斷：La1L an L-next= = L;p-next = L;reara1 aiai-1 an 采用尾指針的循環(huán)單鏈表開始結點的存儲位置：rear-next-next 終端結點的存儲位置：rear11第一部分 線性表真題 2011年11月 對于線性表(由n個同類元素構成的線性序列)，采用單向循環(huán)鏈表存儲的特點之一是_。 A從表中任意結點出發(fā)都能遍歷整個鏈表B對表中的任意結點可以進行隨機訪問C對于表中的任意一個結點，訪問其直接前驅和直接后繼結點所用時間相

7、同D第一個結點必須是頭結點12第一部分 線性表真題 2013年11月以下關于線性表存儲結構的敘述，正確的是(57)。A線性表采用順序存儲結構時，訪問表中任意一個指定序號元素的時間復雜度為常量級B線性表采用順序存儲結構時，在表中任意位置插入新元素的運算時間復雜度為常量級C線性表采用鏈式存儲結構時，訪問表中任意一個指定序號元素的時間復雜度為常量級D線性表采用鏈式存儲結構時，在表中任意位置插入新元素的運算時間復雜度為常量級13第一部分 線性表真題 2013年5月51采用順序表和單鏈表存儲長度為n的線性序列，根據序號查找元素，其時間復雜度分別為_。AO(1)、O(I) BO(1)、O(n)CO(n)、

8、O(1) DO(n)、O(n)14第一部分 線性表真題 2014年5月5715第一部分 線性表真題 2014年11月16分值：0 1分 （每年） 分數比重：0% 10%重要知識點： 1、棧的結構特點 2、隊列的結構特點 3、雙端隊列與循環(huán)隊列 4、串的存儲結構、基本操作和模式匹配第二部分 棧、隊列和字符串 17棧特點： 后進先出的線性表雙向棧： 使兩個棧共享一維數組SMAXNUM，利用棧的“棧底位置不變，棧頂位置動態(tài)變化”的特性，將兩個棧底分別設為0 和 MAXNUM-1，而它們的棧頂都往中間方向延伸的棧稱為雙向棧。在一端進行插入和刪除操作的線性表。棧頂：允許插入和刪除的一端。棧底：不允許插入

9、和刪除的一端。a1a2a3an-1an入棧出棧棧頂元素棧底元素 概念：第二部分 棧、隊列和字符串 自由區(qū)0MAXNUM-1lefttoprighttop18隊列特點： 先進先出的線性表隊列是只能在表的一端進行插入操作，在表的另一端進行刪除操作的線性表。隊尾(rear)：允許插入的一端叫做隊尾。隊頭(front)：允許刪除的一端叫做隊頭。第二部分 棧、隊列和字符串 a1 a2 a3 an-1 an入隊列出隊列隊尾元素隊頭元素概念：19雙端隊列分類： 1、 輸出受限的雙端隊列（即一個端點允許插入和刪除，另一個端點只 允許插入）； 2、 輸入受限的雙端隊列（即一個端點允許插入和刪除，另一個端點只 允

10、許刪除）。 3、限定雙端隊列從某個端點插入的元素只能從該端點刪除，則雙端隊 列就蛻變?yōu)閮蓚€棧底相鄰接的棧了。第二部分 棧、隊列和字符串 雙端隊列就是一個兩端都是結尾的隊列。隊列的每一端都可以插入數據項和移除數據項。a1a2aia0an-1端1端220優(yōu)先級隊列優(yōu)先級隊列是一種不同于先進先出隊列的另一種隊列，每次出隊的是隊列中最高優(yōu)先級的元素。通常采用堆來實現(xiàn)。第二部分 棧、隊列和字符串 21串的定義和基本運算第二部分 棧、隊列和字符串 僅由字符組成的有限序列，是取值范圍受限的線性表?？沾?；空格串；子串和子串的位置；主串；串相等。22串的存儲結構第二部分 棧、隊列和字符串 （1）定長順序串：按照

11、預定義的大小，為每個定義的串變量分配一個固定長度的存儲區(qū)（2）塊鏈串：用鏈表存儲時，通常一個結點中存放的不是一個字符，而是一個子串。例：串值為abcdef的結點大小為4的鏈串塊鏈串注意事項：為了提高存儲密度，可使每個結點存放多個字符。當結點大小大于1時，串的長度不一定正好是結點大小的整數倍，因此要用特殊字符來填充最后一個結點，以表示串的終結。會給串的連接操作帶來一定的方便，對模式匹配操作不方便。雖然提高結點的大小使得存儲密度增大，但是插入、刪除運算時，可能會引起大量字符的移動，給運算帶來不便。a b c de f # # S23串的基本操作難掌握的部分第二部分 棧、隊列和字符串 （1）串比較：

12、StrCompare (S, T) 若S T，則返回值 0； 若S T，則返回值 0； 若S T，則返回值 0。 例如：StrCompare(data , state) 0（2）串聯(lián)接：Concat (&T, S1, S2) 用 T 返回由 S1 和 S2聯(lián)接而成的新串。 例如： Concate( T, man , kind ) 求得 T = mankind （3）求子串:SubString (&Sub, S, pos, len) 用 Sub 返回串 S 的第 pos 個字符起長度為 len 的子串。例如：SubString( sub, commander, 4, 3)求得 sub = man

13、 ；（4）串定位：Index (S, T, pos) 若主串 S 中存在和串 T 值相同的子串, 則返回它在主串 S 中第pos個字符之后第一次出現(xiàn)的位置；否則函數值為0。 假設 S = abcaabcaaabc, T = bca Index(S,T,1) = 2； Index(S,T,3) = 6；（5）串替換：Replace (&S, T, V) 用V替換主串S中出現(xiàn)的所有與（模式串）T 相等的不重疊的子串 假設 S = abcaabcaaabca ，T = bca ，若 V = x ， 則經置換后得到 S = axaxaax 24真題 2011年11月57第二部分 棧、隊列和字符串 25

14、真題 2012年5月58在字符串的KMP模式匹配算法中，需要求解模式串p的next函數值，其定義如下所示，若模式串p為“aaabaaa”，則其next函數值為（58）A. 0123123 B. 0123210C.0123432 D. 0123456第二部分 棧、隊列和字符串 26真題 2012年11月57第二部分 棧、隊列和字符串 27真題 2013年5月52設元素序列a,b,c,d,e,f經過初始為空的棧S后，得到出棧序列cedfba,則棧S的最小容量為 (52) A.3 B.4 C.5 D.6第二部分 棧、隊列和字符串 28真題 2013年5月53 輸出受限的雙端隊列是指元素可以從隊列的兩

15、端輸入，但只能從隊列的一端輸出，如下圖所示，若有e1,e2,e3,e4依次進入輸出受限的雙端隊列，則得不到輸出序列 (53)A.e4,e3,e2,e1 B.e4,e2,e1,e3 C.e4,e3,e1,e2 D.e4,e2,e3,e1第二部分 棧、隊列和字符串 29真題 2013年11月58題設循環(huán)隊列的定義中有front和size兩個域變量，其中front表示隊頭元素的指針，size表示隊列的長度，如下圖所示（隊列長度為3，隊頭元素為X，隊尾元素為Z）。設隊列的存儲空間容量為M，則隊尾元素的指針為（58）。（58）A.（Q.front+Q.size-1）B(Q.front+Q.size-1+

16、M)MC(Q.front-Q.size)D(Q.front-Q.size+M)M答案為B第二部分 棧、隊列和字符串 30真題 2014年5月50第二部分 棧、隊列和字符串 A 雙端隊列 B 31真題 2014年11月第二部分 棧、隊列和字符串 32真題 2014年11月60第二部分 棧、隊列和字符串 33真題 2015年5月57第二部分 棧、隊列和字符串 34真題 2015年5月58第二部分 棧、隊列和字符串 35真題 2015年5月62、63第二部分 棧、隊列和字符串 36真題 2015年11月57第二部分 棧、隊列和字符串 37真題 2016年5月57題?第二部分 棧、隊列和字符串 38分

17、值：0 1分 （每年） 分數比重：0% 10%重要知識點： 1、數組的地址計算 2、數組的壓縮存儲 3、廣義表的表示 4、廣義表的表頭、表尾第三部分 數組與廣義表 39數組特點： 1.數組中的數據元素具有相同的數據類型。 2.數組是一種隨機存取結構，只要給定一組下標，就可以訪問與其對應的數組元素。 3.數組中的元素個數是固定的。基本操作存取、修改 對于數組A，一旦給定其維數 n 及各維長度bi（1in），則該數組中元素的個數和元素之間的關系就不再發(fā)生變化了，既不可以對數組做插入和刪除操作，也不涉及移動元素操作。 第三部分 數組與廣義表 多維數組和廣義表是對線性表的擴展線性表中的數據元素本身又是

18、一個多層次的線性表。40數組的地址計算第三部分 數組與廣義表 Locaij = Loca00 + ( n i + j ) size a00 a02 a03 a0j a0,n-1 a10 a11 a12 a1j a1,n-1 a20 a21 a22 a2j a2,n-1 Amn = ai,0 ai,1 aij am-1,0 am-1,1 am-1,2 am-1,n-1Locaij = Loca00 + ( m j + i ) size行序為主序：列序為主序：41特殊矩陣的壓縮存儲對稱矩陣三角矩陣對角矩陣稀疏矩陣第三部分 數組與廣義表 421、A = ( )2、B = ( e )3、C = ( a

19、, ( b , c , d ) )4、D = ( A , A , ( ) )5、E = ( A , B , C )6、F = ( a , F )表示廣義表A是一個空表，其長度為0表示廣義表B長度為1，只有一個原子項e表示廣義表C長度為2，兩個元素分別為原子項a 和子表(b , c , d)。表示廣義表D長度為3，三個元素都是廣義表，分別為A、A 和( )。表示廣義表E長度為3，三個元素A、B、C都是廣義表，代入值以后E=( ( ) , (e) , ( a, ( b , c , d ) ) )。表示廣義表F長度為2，兩個元素分別是原子項a和子表F。這是一個遞歸表，相當于無窮廣義表 F=（a ,

20、F）= (a, (a, (a, , ) ) )。廣義表的表示第三部分 數組與廣義表 43廣義表的長度定義為最外層包含元素個數。廣義表的深度定義為所含括弧的重數;“原子結點”的深度為 0 ; “空表”的深度為 1 。廣義表的表頭、表尾第三部分 數組與廣義表 任何一個非空廣義表 GL = ( d1, d2, , dn )均可分解為 表頭 Head(GL) = d1 和 表尾 Tail(GL) = ( d2, , dn)例如: D = ( E, F ) = (a, (b, c)，F(xiàn) )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = (

21、 ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )44真題 2011年11月21若二維數組arr1.M，1.N的首地址為base，數組元素按列存儲且每個元素占用K個存儲單元，則元素arri，j在該數組空間的地址為_。Abase+(i-1)*M+j-1)*KBbase+(i-1)*N+j-1)*KCbase+(j-1)*M+i-1)*KDbase+(j-1)*N+i-1)*K

22、第三部分 數組與廣義表 45真題 2012年5月21第三部分 數組與廣義表 46真題 2015年11月58第三部分 數組與廣義表 47分值：1 7分 （每年） 分數比重：2% 20%重要知識點： 1、樹和二叉樹的定義 2、二叉樹的重要性質 3、二叉樹的遍歷、線索二叉樹 4、樹與二叉樹的轉換 5、二叉樹的應用哈夫曼樹第四部分 樹與二叉樹 48樹和二叉樹的定義樹的概念和邏輯特點： 1、有且僅有一個結點沒有前驅結點,該結點為樹的根結點。 2、除了根結點外,每個結點有且僅有一個直接前驅結點。 3、包括根結點在內，每個結點可以有多個后繼結點。二叉樹的概念和邏輯特點 1、每個結點的度都不大于2； 2、每個

23、結點的孩子結點次序不能任意顛倒。第四部分 樹與二叉樹 相關術語：結點、結點的度、葉子結點、分支結點、結點的層次、結點的層序編號、樹 的度、樹的高度（深度）、雙親結點、孩子結點、兄弟結點、堂兄弟結點、子孫結點、祖先結點。完全二叉樹、滿二叉樹。49二叉樹的重要性質性質1：在二叉樹的第i層上至多有2i-1個結點(i1)。 性質2：深度為k的二叉樹至多有2k-1個結點（k1）。 性質3：對任意一棵二叉樹T，若終端結點數為n0，而其度數為2的結 點數為n2，則n0= n2+1 。性質4：具有n個結點的完全二叉樹深度為 log2n +1 。 性質5：對于具有n個結點的完全二叉樹，如果按照從上到下和從左 到

24、右的順序對二叉樹中的所有結點從1開始順序編號，則對 于任意的序號為i的結點有： (1)若i = 1, 則 i 無雙親結點 若i 1, 則 i 的雙親結點為i /2 (2)若2*i n, 則 i 無左孩子 若2*in, 則 i 結點的左孩子結點為2*i (3)若 2*i+1 n ,則i 無右孩子 若 2*i+1n, 則i的右孩子結點為2* i+1第四部分 樹與二叉樹 50二叉樹的遍歷第四部分 樹與二叉樹 ABCDKFGIJEH前序遍歷序列: A, B, D, K, J, G, C, F, I, E, H中序遍歷序列: D, B, G, J, K, A, F, I, E, C, H后序遍歷序列:

25、D, G, J, K, B, E, I, F, H, C, A按層次遍歷序列: A, B, C, D, K, F, H, J, I, G, E51例：已知結點的先序序列和中序序列先序序列：A B D E J C F I G中序序列：D B J E A F I C G 則可按上述分解求得整棵二叉樹。 ADCIFGJBE第四部分 樹與二叉樹 例：已知結點的中序序列和后序序列中序序列：A B C E F G H D后序序列：A B F H G E D C 則可按上述分解求得整棵二叉樹。 CADGEHFB52二叉樹的存儲結構1、二叉樹的順序存儲結構2、二叉樹的鏈式存儲結構第四部分 樹與二叉樹 53線索

26、二叉樹第四部分 樹與二叉樹 一.什么是線索二叉樹 二.線索二叉樹的構造 利用二叉鏈表中空的指針域指出結點在遍歷序列中的直接前驅和直接后繼;這些指向前驅和后繼的指針稱為線索, 加了線索的二叉樹稱為線索二叉樹. 利用結點的空的左指針域存放該結點的直接前驅的地址,空的右指針域存放該結點直接后繼的地址; 而非空的指針域仍然存放結點的左孩子或右孩子的地址.注：每棵二叉樹都可以構造先序、中序和后序三種線索二叉樹。54樹的存儲第四部分 樹與二叉樹 1、雙親表示法2、孩子表示法3、孩子兄弟表示法55樹、森林與二叉樹的轉換第四部分 樹與二叉樹 樹轉換成二叉樹： 1、樹中所有相鄰兄弟之間加一條連線。 2、對樹中的

27、每個結點，只保留其與第一個孩子結點之間的連線，刪去其與其它孩子結點之間的連線。 森林轉換為二叉樹的方法為： 1、將森林中的每棵樹轉換成相應的二叉樹。 2、第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連在一起后，即為由森林轉換得到的二叉樹。 ABECDFGHABCDEFIJGH56帶權路徑長度： 設二叉樹有n個帶權值的葉子結點，定義從二叉樹的根結點到二叉樹中所有葉子結點的路徑長度li與相應葉子結點權值wi的乘積之和稱作該二叉樹的帶權路徑長度。WPL(T) =72+52+23+43+92 = 6075249ACBIGFDEHWPL =

28、哈夫曼樹第四部分 樹與二叉樹 5752310515782511110000(011)(010)(10)(11)(00) 字符： s t a e c 字符出現(xiàn)的次數： 3 8 7 5 2 c: 010s: 011e: 00a: 10t: 11哈夫曼編碼第四部分 樹與二叉樹 58堆第四部分 樹與二叉樹 1、堆的定義 大根堆或小根堆（大頂堆、小頂堆）2、堆的判斷方法3、堆的應用 堆排序59真題 2011年5月12、20、21、59第四部分 樹與二叉樹 60真題 2011年5月12、20、21、59第四部分 樹與二叉樹 61真題 2011年11月60、61第四部分 樹與二叉樹 62真題 2012年5月

29、59第四部分 樹與二叉樹 63真題 2012年11月58若某二叉樹的后序遍歷序列為KBFDCAE，中序遍歷序列為BKFEACD，則該二叉樹為（58）第四部分 樹與二叉樹 64真題 2013年5月64 一個高度為h的滿二叉樹的結點總數為2h-1，從根結點開始，自上而下、同層次結點從左至右，對結點按照順序依次編號，即根結點編號為1，其左、右孩子結點編號分別為2和3，再下一層從左到右的編號為4，5，6，7，依此類推。那么，在一棵滿二叉樹中，對于編號為m和n的兩個結點，若n=2m+1,則 (64) A. m是n的左孩子 B. m是n的右孩子 C. n是m的左孩子 D. n是m的右孩子第四部分 樹與二叉

30、樹 65真題 2013年11月60以下關于哈夫曼樹的敘述，正確的是（60）A.哈夫曼樹一定是滿二叉樹，其每層結點樹都達到最大值B.哈夫曼樹一定是平衡二叉樹，其每個結點左右子樹高度差為-1，0，1C.哈夫曼樹中左右孩子結點的權值小于父結點，右孩子結點的權值大于父結點D. 哈夫曼樹中葉子結點的權值越小則距離樹根越遠，葉子結點的權值越大，則距離樹根越近第四部分 樹與二叉樹 66真題 2014年5月58、59某二叉樹如下圖所示，若進行順序存儲（即用一維數組元素存儲該二叉樹中的結點且通過下標反映結點間的關系，例如，對于下標為i 的結點，其左孩子的下標為2i，右孩子的下標為2i+1），則該數組的大小至少為

31、（58）；若采用三叉鏈表存儲該二叉樹（各個結點包括結點的數據、父結點指針、左孩子指針、右孩子指針），則該鏈表的所有結點中空指針的數目為（59）。第四部分 樹與二叉樹 58：59：67真題 2014年11月第四部分 樹與二叉樹 68真題 2014年11月第四部分 樹與二叉樹 69真題 2015年5月59第四部分 樹與二叉樹 70真題 2015年11月59第四部分 樹與二叉樹 71真題 2016年5月58、59第四部分 樹與二叉樹 72真題 2016年5月59一棵二叉樹的高度（即層數）為h，則該二叉樹（59）A. 有2h個結點B. 有2h1一個結點C. 最少有2h1個結點D. 最多有2h1個結點第

32、四部分 樹與二叉樹 73分值：0 5分 （每年） 分數比重：6%重要知識點： 1、圖的基本概念和存儲結構 2、圖的遍歷 3、拓撲排序和最小生成樹 4、關鍵路徑 5、最短路徑第五部分 圖 74圖的基本概念和存儲結構圖的基本概念： 無向圖、有向圖、無向完全圖、有向完全圖、稀疏圖、稠密圖、子圖、有向圖與無向圖的頂點的度、網、回路和環(huán)、路徑長度、簡單路徑、簡單回路、連通圖、連通分量、強連通圖、強連通分量。圖的存儲結構 鄰接矩陣(數組)表示法； 鄰接表第五部分 圖 BACDG1BADEG2C75圖的遍歷深度優(yōu)先搜索：是指按照深度方向搜索，它類似于樹的先根遍歷。廣度優(yōu)先搜索：是指按照廣度方向搜索，它類似于

33、樹的按層次遍歷。第五部分 圖 v1v2v3v4v5v6v7v8v9v1v2v4v7v9v5v3v6v8BAEDCA B C D Ev1v2v3v4v5v9v6v8v7A B C E D76拓撲排序拓撲排序 將一個有向圖中的所有結點排成一個序列，使得圖中所有結點應存在的前驅和后繼關系都能在隊列中體現(xiàn)（前驅在前，后繼在后）。過程 從AOV網中選擇一個沒有前驅的頂點并且輸出； 從AOV網中刪去該頂點并且刪去所有以該頂點為尾的?。?重復上述兩步，直到全部頂點都被輸出; 第五部分 圖 C1C2C3C4C6C5C7拓撲序列：C1, C2, C3, C4, C5, C6, C7 77最小生成樹概念 生成樹是

34、連通圖上的一個極小連通子圖。最小生成樹是一個連通網中所有生成樹中各邊權值之和最小的生成樹。最小生成樹的算法： 1、普里姆算法 2、克魯斯卡爾算法第五部分 圖 abdcef6155542663abdcef15342abdcef153255478關鍵路徑概念 從源點到匯點的最長路徑的長度即為完成整個工程任務所需的時間，該路徑叫做關鍵路徑。關鍵路徑上的活動叫關鍵活動。 關鍵路徑的求法： 事件的最早發(fā)生時間 vek 事件的最遲發(fā)生時間 vlk 活動的最早開始時間 ei 活動的最晚開始時間 li第五部分 圖 v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4

35、a5=1a6=2a3=5a2=479第五部分 圖 v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4vekv2v7v6v5v4v1v3v9v8064577161418a2a7a6a5a4a1a3a9a8ei000645777a10a11161480第五部分 圖 v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4li10778663201614a2a7a6a5a4a1a3a9a8a10a11v2v7v6v5v4v1v3v9v8vlk18141

36、6107866081最短路徑分類1、求圖中的一個結點到其他結點的最短路徑。2、求圖中任意兩點間的最短路徑。最短路徑的求法： 迪杰斯特拉(Dijkstra)算法 Floyd算法第五部分 圖 BAEDC105030101002060S=A, B, D, C, EAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, C, E)60BAEDC10503010100206082最短路徑分類1、求圖中的一個結點到其他結點的最短路徑。2、求圖中任意兩點間的最短路徑。最短路徑的求法： 迪杰斯特拉(Dijkstra)算法 Floyd算法第五部分 圖 abd53863c1

37、2283真題 2011年5月60第五部分 圖 84真題 2011年11月59第五部分 圖 85真題 2012年5月60第五部分 圖 86真題 2012年11月60拓撲排序是將有向圖中所有頂點排成一個線性序列的過程，并且該序列滿足：若在AOV網中從頂點Vi到Vj有一條路徑，則頂點Vi必然在頂點Vj之前。對于下圖所示的有向圖，（60）是其拓撲排序。第五部分 圖 A. 1234576B. 1235467C. 2135476D. 213456787真題 2013年11月59第五部分 圖 88真題 2014年5月第五部分 圖 89真題 2014年11月53、54第五部分 圖 90真題 2015年11月6

38、1第五部分 圖 91真題 2016年5月61第五部分 圖 92分值：5 15分 （每年） 分數比重：10%重要知識點： 1、靜態(tài)表查找順序查找、折半查找 2、動態(tài)表查找二叉排序樹 3、哈希表 4、插入類排序 5、交換類排序 6、選擇類排序 7、分配類排序第六部分 排序與查找 93查找基本概念： 靜態(tài)查找 ：不涉及插入和刪除操作的查找 。 動態(tài)查找 ：涉及插入和刪除操作的查找。 平均查找長度：將查找算法進行的關鍵碼的比較次數的數學期望 值定義為平均查找長度。計算公式為： 其中：n ：問題規(guī)模，查找集合中的記錄個數； pi ：查找第i個記錄的概率； ci ：查找第i個記錄所需的關鍵碼的比較次數。第

39、六部分 排序與查找 94靜態(tài)查找順序查找：從線性表的一端向另一端逐個將關鍵碼與給定值進行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個表檢測完仍未找到與給定值相等的關鍵碼，則查找失敗，給出失敗信息。折半查找：在有序表中，取中間元素作為比較對象 1、若給定值與中間記錄的關鍵字相等，則查找成功； 2、若給定值小于中間記錄的關鍵字，則在中間記錄的左半區(qū)繼續(xù)查找；若給定值大于中間記錄的關鍵字，則在中間記錄的右半區(qū)繼續(xù)查找。 3、不斷重復上述過程，直到查找成功，或所查找的區(qū)域無記錄(lowhigh)，查找失敗。 前提：線性表中的記錄必須按關鍵字有序；必須采用順序存儲。第六部分 排序與查找 95

40、動態(tài)查找二叉排序樹定義：一棵二叉樹中，每一個結點的左子樹上的結點都比它小，右子樹 上的結點都比它大。這種二叉樹稱為二叉排序樹。二叉排序樹的查找：從根結點開始比較，如果比根結點的值小，則到根結點的左子樹上去查找；比根結點大，到根結點的右子樹上去查找；與根結點相等，說明查找成功。依此類推，直到所要查找的結點為空，說明查找失敗。二叉排序樹的構造：將二叉排序樹初始化為一棵空樹，然后按照順序逐個讀入元素，每讀入一個元素，就建立一個新的結點插入到當前已生成的二叉排序樹中，即調用上述二叉排序樹的插入算法將新結點插入。直到所有結點插入完成，二叉排序樹就構造完成了。 注：若二叉排序樹為空樹，則新插入的結點為新的

41、根結點；否則，新插入的結點必為一個新的葉子結點，其插入位置由查找過程得到。第六部分 排序與查找 96動態(tài)查找二叉排序樹結論：對同樣一組數據元素，如果輸入的順序不同，則所建的二叉樹 形態(tài)也不同。特點： 1、一個無序序列可以通過構造一棵二叉排序樹而變成一個有序序列; 2、每次插入的新結點都是二叉排序樹上新的葉子結點; 3、找到插入位置后，不必移動其它結點，僅需修改某個結點的指針； 4、在左子樹/右子樹的查找過程與在整棵樹上查找過程相同； 5、新插入的結點沒有破壞原有結點之間的關系。第六部分 排序與查找 練習：關鍵字的輸入順序為：45, 24 , 53 , 12 , 28 , 90，和 24, 53

42、, 90, 12, 28, 45 ，分別構造二叉排序樹97動態(tài)查找二叉排序樹的刪除1. 若結點p是葉子，則直接刪除結點p；2. 若p結點只有左子樹，或只有右子樹，則 因為該結點只有左子樹或只有右子樹，也就是說，其后繼只有一個分支。刪除該結點時，只要將被刪除結點的唯一后繼（左子樹或右子樹）直接鏈接到被刪除結點的位置即可。3. 若結點p的左右子樹均不空： 首先找到p結點在中序序列中的直接前驅s結點，然后用s結點的值，替代p結點的值，再將s結點刪除,因為s的右指針一定為空，所以只要把s的左孩子鏈接到s結點本身的位置即可。第六部分 排序與查找 98 哈希表定義： 在元素的關鍵字k 和元素的存儲位置p

43、之間建立一個對應關系H，使得p=H(k)，H稱為哈希函數。創(chuàng)建哈希表時，把關鍵字為k的元素直接存入地址為H(k)的單元；以后當查找關鍵字為k的元素時，再利用哈希函數計算出該元素的存儲位置p=H(k)，從而達到按關鍵字直接存取元素的目的。這種查找的方法稱為哈希法。 哈希函數設計原則： 計算簡單。哈希函數不應該有很大的計算量，否則會降低查找效率。 函數值即哈希地址分布均勻。函數值要盡量均勻散布在地址空間，這樣才能保證存儲空間的有效利用并減少沖突。第六部分 排序與查找 99 哈希表沖突：對于兩個不同關鍵碼 kikj，有H(ki)H (kj)，即兩個不同的記錄需要存放在同一個存儲位置。哈希函數沖突的處

44、理方法： 1、開放定址法 (再散列法)：線性探測再散列、二次探測再散列； 2、再哈希法：同時構造多個不同的哈希函數，當哈希地址發(fā)生沖突時，再用其他哈希函數來計算地址，直到沖突不再產生。 3、鏈地址法：將所有哈希地址為i的元素構成一個單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在這個鏈中進行。 4、建立公共溢出區(qū)法：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素，一律填入溢出表。 第六部分 排序與查找 100 哈希表裝填因子：哈希法中影響關鍵字比較次數的因素有三個：哈希函數、處理沖突的方法以及哈希表的裝填因子。哈希表的裝填因子的定義如下： 可描述哈希

45、表的裝滿程度。 越小，發(fā)生沖突的可能性越小； 越大，發(fā)生沖突的可能性也越大。 第六部分 排序與查找 哈希表中元素個數哈希表的長度101 基本概念內部排序：整個排序過程完全在內存中進行，稱為內部排序。 外部排序：由于待排序的記錄個數太多，不能同時放置在內存，而需要將另一部分記錄放置在外存上，整個排序過程需要在內外存之間多次交換數據才能得到排序的結果。排序的穩(wěn)定性：相同關鍵字的相對位置關系在排序過程中沒有發(fā)生變化者，則稱所用的排序方法是穩(wěn)定的 ；反之，則稱為不穩(wěn)定的。第六部分 排序與查找 102 插入類排序直接插入排序：每次將一個待排序的記錄按其關鍵碼的大小插入到一個已經排好序的有序序列中，直到全

46、部記錄排好序為止。折半插入排序：以折半查找和直接插入排序兩種方法結合起來實現(xiàn)排序；希爾排序：根據不同的間距di 將元素分成組，在各組內進行直接插入排序，di 的值是由大到小，最后為1，即將所有元素放在一組里進行排序第六部分 排序與查找 103第六部分 排序與查找 直接插入46741653142640388665273414674165314264038866527342164674531426403886652734316465374142640388665273441416465374264038866527345141626465374403886652734614162640465374

47、38866527347141626384046537486652734814162638404653748665273491416263840465365748627341014162627384046536574863411141626273438404653657486希爾排序467416531426403886652734126341653142740388665467422614164034275338746546863141626273438404653657486104 交換類排序冒泡排序：快速排序：第六部分 排序與查找 快速排序46741653142640388665273413

48、42716381426404686655374226271614343840467465538631416262734384046536574864141626273438404653657486105 選擇類排序：簡單選擇排序、堆排序第六部分 排序與查找 簡單選擇 4674165314264038866527341147416534626403886652734214167453462640388665273431416265346744038866527344141626274674403886655334514162627347440388665534661416262734384074

49、866553467141626273438407486655346814162627343840468665537491416262734384046536586741014162627343840465365867411141626273438404653657486106歸并排序基本思想：將兩個或兩個以上有序表合并成一個新的有序表。假設初始序列含有n個記錄，首先將這n個記錄看成n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到 n/2 個長度為2的有序子序列；在此基礎上，再進行兩兩歸并，如此重復，直至得到一個長度為n的有序序列為止。第六部分 排序與查找 (19) (13) (05)

50、 (27) (01) (26) (31) (16) (13,19) (05,27) (01,26) (16,31) (05,13,19,27) (01,16,26,31) ( 01, 05 , 13 , 16 , 19 , 26 , 27 , 31 )107分配類排序基本思想：設待排序的數據元素關鍵字是m 位d 進制整數（不足m位的關鍵字在高位補0），設置d個桶，分別編號為0,1,2,d-1。 1、首先按關鍵字最低位的數值依次把各數據元素放到相應的桶中，然后按照桶號從小到大和進入桶中數據元素的先后次序收集分配在各桶中的數據元素，這樣就形成了數據元素集合的一個新的排列，我們稱這樣的一次排序過程為

51、一次基數排序； 2、 再對一次基數排序得到的序列按關鍵字次低位的數值依次把各數據元素放到相應的桶中，然后按照桶號從小到大和進入桶中數據元素的先后次序收集分配在各桶中的數據元素； 這樣的過程重復進行，當完成了第m 次基數排序后，就得到了排好序的數據元素序列。第六部分 排序與查找 108數據元素的關鍵字序列為710,342,045,686,006,841,429,134,068,2648411342231342644045568600667068871004299放置710142921343841342045452640686768680060900671042913484134204526406

52、8686收集后的新序列:放置1341264234234294568667107841800604506809006045068134264342429686710841收集后的新序列:放置710841342134264045686006068429收集后的新序列:(a)第一趟基數排序 (b)第二趟基數排序 (c)第三趟基數排序 109排序方法最好情況平均時間最壞情況穩(wěn)定性直接插入O(n)O(n2)O(n2)簡單選擇O(n2)O(n2)O(n2)冒泡O(n)O(n2)O(n2)快速O(nlog2n)O(nlog2n)O(n2)堆排序O(nlog2n)O(nlog2n)O(nlog2n)歸并O(n

53、log2n)O(nlog2n)O(nlog2n)基數O(d(n+rd)O(d(n+rd)O(d(n+rd)第六部分 排序與查找 各種排序方法性能比較110真題2011年5月58、61、65 第六部分 排序與查找 111真題2012年5月61 第六部分 排序與查找 112真題2012年11月59、61、62、63在13個元素構成的有序表M1.13中進行折半查找（向下取整），若找到的元素為M4，則被比較的元素一次為（59）.A. M7、M3、M5、M4 B. M7、M5、M4C.M7、M6、M4 D.M7、M4第六部分 排序與查找 113真題2012年11月59、61、62、63下圖所示為一棵N階

54、B樹，N最有可能的值為（61）。第六部分 排序與查找 A. 1 B. 2 C. 3 D.4114真題2012年11月59、61、62、63將數組1，1，2，4，7，5從小到大排序，若采用（62）排序算法，則元素之間需要進行的比較次數最少，共需要進行（63）次元素之間的比較。 (62) A.直接插入排序 B.歸并 C.堆 D. 快速（63） A.5 B.6 C.7 D. 8第六部分 排序與查找 115真題2013年5月65第六部分 排序與查找 以下關于哈希(Hash,散列)查找敘述中，正確的是(65)。A.哈希函數應盡可能復雜些，以消除沖突B.構造哈希函數時應盡量使關鍵字的所有組成部分都能起作用

55、C.進行哈希查找時，不再需要與查找表中的元素進行比較D.在哈希表中只能添加元素不能刪除元素 116真題2013年11月61、62、63 第六部分 排序與查找 117真題2014年5月61 第六部分 排序與查找 118真題2014年11月61、62、63 第六部分 排序與查找 119真題2015年5月60、61、64、65 第六部分 排序與查找 120真題2015年5月60、61、64、65 第六部分 排序與查找 121真題2015年11月60、64、65 第六部分 排序與查找 122真題2016年5月58、60 第六部分 排序與查找 123真題2016年5月58、60 第六部分 排序與查找 1

56、24分值：2 16分 （每年） 分數比重：22%重要知識點： 1、時間復雜度 2、窮舉法、迭代法、遞推法、遞歸法、 分治法、動態(tài)規(guī)劃法、回溯法、貪心法第七部分 算法 125算法第七部分 算法 算法的5個重要特性： 有窮性、確定性、可行性、輸入、輸出?！昂谩钡乃惴ǖ哪繕耍?正確性、可讀性、健壯性、效率與低存儲需求。算法的表示： 自然語言、流程圖、程序設計語言、偽代碼。時間復雜度： 126 蠻力法（窮舉法）蠻力法(brute force method)：也稱窮舉法(enumerate)法，是蠻力策略的一種表現(xiàn)形式。它是根據問題中的條件將可能的情況一一列舉出來，逐一嘗試從中找出滿足問題條件的解。但有

57、時一一列舉出的情況數目很大，如果超過了我們所能忍受的范圍，則需要進一步考慮，排除一些明顯不合理的情況，盡可能減少問題可能解的列舉數目。用蠻力法解決問題，通常從兩個方面進行算法設計： 1、找出窮舉范圍：分析問題所涉及的各種情況。 2、找出約束條件：分析問題的解需要滿足的條件，并用邏輯表達式表示。應用：順序查找、簡單選擇排序、冒泡排序、0/1背包。第七部分 算法 127 迭代法迭代法是用于求方程或方程組近似根的一種常用算法設計方法。設方程為f(x) = 0，用某種數學方法導出等價的形式x= g(x)，然后按以下步驟執(zhí)行：1）選一個方程的近似根，賦給變量x0;2）將x0的值保存于變量x1，然后計算g

58、(x1)，并將結果存于變量x0;3）當x0與x1的差的絕對值還不小于指定的精度要求時，重復步驟2）的計算；4）若方程有根，并且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根。第七部分 算法 128 遞推法遞推法是利用問題本身所具有的一種遞推關系求問題的一種方法。所謂遞推，是指從已知的初始條件出發(fā)，依據某種遞推關系，逐次推出所要求的各中間結果及最后結果。其中初始條件或是問題本身已經給定，或是通過對問題的分析與化簡后確定?？捎眠f推的算法求解的題目一般有以下兩個特點： 1）問題可以劃分成多個狀態(tài)； 2）除初始狀態(tài)外，其他各個狀態(tài)都可以用固定的遞推關系式來表示。如：整數的階乘、Fib