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

　　15、二叉樹的存儲和線索

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

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

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

　　17、查找：

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

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

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

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

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

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

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

　　18、排序

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

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

　　相關(guān)推薦：

　　2014年計(jì)算機(jī)等考上機(jī)六大注意事項(xiàng)

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

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