2014年計算機三級數(shù)據(jù)庫背誦資料：第二章

　　15、二叉樹的存儲和線索

　　二叉樹的存儲結(jié)構(gòu)：二叉樹的llink一rlink法存儲表示

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

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

　　17、查找：

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

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

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

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

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

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

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

　　18、排序

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

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

　　相關(guān)推薦：

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

　　2014年計算機三級數(shù)據(jù)庫技術(shù)重點筆記匯總

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