數據結構復習提綱(整理)-資料下載頁
2025-04-17 01:46本頁面
【正文】 開放地址法解決沖突開放定址法是使用某種探查技術在哈希表中形成一個探查序列,當沖突發(fā)生時,沿此序列舉個單元地查找,:線性探查法平方探查法雙哈希函數探查法n 鏈接法解決沖突做法是:把所有關鍵字為同義詞的數據元素存在同一個單鏈表中.樹與二叉樹n 什么是樹？n 根、樹的度、結點樹是由n(n=0),n=0稱為空樹。n,都滿足一下條件:1. 有且僅有一個稱為根的節(jié)點,它比較特殊,沒有前驅結點。2. 其余結點被分成m(m=0)個互不相交的有限集T1,T2,…..Tm,其中每一個集合Ti(i=m)優(yōu)勢一棵樹,稱為根的子樹. 書中所有結點的度的最大值稱為樹的度. .n 雙親結點、葉子結點、兄弟結點結點的前驅稱為該結點的雙親結點.度為0的結點稱為葉子結點具有同一雙親的孩子結點互稱為兄弟結點.n 樹的四個性質性質1樹中的結點等于所有結點的度數加1性質2度為k的樹中第i層上至多有ki1 個結點性質3深度為h的k叉樹至多有(kh1)/(k1)個結點 性質4具有n個結點的k叉樹的最小深度為(logk(n(k1)+1)n 什么是二叉樹？n 二叉樹的四個性質 性質1二叉樹上的終端結點等于雙支結點數加1 性質2二叉樹中第i層上至多有2i1 個結點性質3深度為h的二叉樹至多有2h1個結點性質4對完全二叉樹中編號為不的結點(1≤i≤n,n ≥1,n 為結點數)：若i≤ 235。 n/2 , 即2i≤n,編號為i的結點為分支結點否則為葉子結點， 若n為奇數，則樹中每個分支結點既有左孩子又有右孩子，若n為偶數，則編號最大的分支結點(編號為n/2)只有左孩子，沒有右孩子，其余分支結點左、右孩子都有，若編號為i 的結點有左孩子，則左子結點的編號為2i；若編號為i的結點有右孩子則右子結點為2i+1，除樹根結點外，若一個結點的編號為i，則它的雙親結點的編號為235。 i/2 性質5具有n個（n0）結點的完全二叉樹的深度為235。log2n+1n 二叉樹的遍歷方法（先序、中序、后序）先序遍歷:頭結點224。左子樹224。右子樹中序遍歷:左子樹224。頭結點224。右子樹后續(xù)遍歷:左子樹224。右子樹224。頭結點附:層序遍歷:按照每個元素的下標依次遍歷n 什么是二叉搜索樹n 如何生成二叉搜索樹二叉搜索樹或者是空樹,或者是具有以下性質的二叉樹:,則左子樹上所有結點的關鍵字值均小于它的根節(jié)點的關鍵值.,則右子樹上所有結點的關鍵字值均大于它的根節(jié)點的關鍵值..n 如何在二叉搜索樹實現數據查找 類似于折半查找,過程為: 設待查找數據元素為a ,要比較的二叉排序樹根節(jié)點的關鍵字值為 b若a=b,則查找成功.若ab,則繼續(xù)查找左子樹.若ab,則繼續(xù)查找右子樹.圖n 什么是圖？((重點要看看書))n 有向圖、無向圖、路徑由沒有方向的邊構成的圖稱為無向圖.由有有方向的邊構成的圖稱為有向圖.由頂點vi經過一系列的邊或弧能夠到達頂點vj,則稱這一系列的邊或弧為頂點vi到頂點vj的路徑.n 有向邊、無向邊有方向的邊稱為有向邊,有向邊的終點稱為弧頭沒有方向的邊稱為無向邊,簡稱邊.n 圖的存儲結構n 重點:鄰接矩陣、鄰接表 ,.(P216) .(P221)圖的遍歷方法？n 深度優(yōu)先遍歷(P226)n 廣度優(yōu)先遍歷(P228)
教學教案相關推薦
鄂ICP備17016276號-1