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