15、二叉樹的存儲和線索

　　二叉樹的存儲結構：二叉樹的llink一rlink法存儲表示

　　線索二叉樹：在有n個節點的二叉樹的且llink - rlink法存儲表示中，必定有n+1個空指針域

　　16、哈夫曼樹：一類帶權路徑長度最短的樹。樹的帶權路徑長度為樹中所有葉子節點的帶權路徑長度之和WPL。

　　17、查找：

　　(1)順序查找：平均查找長度為(n +1 )/2次，時間復雜度為O(n)

　　(2)二分法查找：線性表節點必須按關鍵碼值排序，且線性表是以順序存儲方式存儲的。查找成功比較次數log2n，查找失敗比較次數log2n+1

　　(3)分塊查找：先是塊間查找，然后塊內查找。

　　(4)散列表(哈希表Hash)的存儲和查找：處理沖突的方法：開地址法(線性探測法)、拉鏈法等

　　負載因子(裝填因子)=表實際存儲的結點個數/表的最大能存儲結點個數(即表長)

　　二叉排序樹：每個結點左子樹的所有關鍵碼值都小于該結點關鍵碼值，右子樹所有結點關鍵碼值都大于該結點關鍵碼值。對稱周游二叉排序樹，得到一個有序序列，時間復雜度O(log2n)

　　B樹和B+樹：M階樹，每個結點至多有M-1個關鍵碼，至少有M/2(取上界)-1個關鍵碼。B樹適合隨機查找，不適合順序查找。B+樹適合順序查找。

　　18、排序

　　直接插人排序、希爾排序、直接選擇排序、堆排序、起泡排序、快速排序等排序算法要了解。

　　直接選擇排序、希爾排序、快速排序和堆排序是不穩定排序，其他排序為穩定排序

　　相關推薦：

　　2014年計算機等考上機六大注意事項

　　2014年計算機三級數據庫技術重點筆記匯總

　　2014年計算機三級數據庫技術上機試題及答案匯總