數(shù)據(jù)結(jié)構(gòu)課件第九章(參考版)
2025-05-18 21:41本頁面
【正文】 問其中哪幾種輸入序列所構(gòu)造的二叉排序樹的高度為 3？ 。 ? 向一棵二叉排序樹中插入一個元素時，若元素的值小于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根結(jié)點(diǎn)的 __________子樹上。 A． O(1) B． O(n) C． O(1og2n) D． O(n2) ? 靜態(tài)查找表與動態(tài)查找表二者的根本差別在于 ( ) 。 A．遞增或遞減 B．遞增 C．遞減 D．無序 ? 向具有 n個結(jié)點(diǎn)的、結(jié)構(gòu)均衡的二叉排序樹中插入一個元素的時間復(fù)雜度為 ( )。 ? 假定有 k個關(guān)鍵字互為同義詞，若用線性探測法將這 k個關(guān)鍵字存入散列表中，至少需要進(jìn)行（ ）次探測。 H(key) 哈希函數(shù) m 哈希表長 di 增量序列 關(guān)鍵如何設(shè)計 di 線性探測法 二次探測法 隨機(jī)探測法 H(key) = ( key + di ) mod m 線性探測法 di = 1 , 2 , 3 , …, m 1 隨機(jī)探測法 di = 隨機(jī)數(shù) 二次探測法 di = 12 , 12 , 22 , 22 , 32 , …, +k 2 例，關(guān)鍵字為 ( 17 , 60 , 29 , 38 ) ，哈希表長 11 ， H(key)=key%11 初始， 0 1 2 3 4 5 6 7 8 9 10 17 60 29 線性探測法 38 沖突 d = 1 沖突 d = 2 沖突 d = 3 無沖突 38 二次探測法 d= 1 無沖突 38 隨機(jī)探測法 不妨設(shè)第一次隨機(jī)數(shù)為 9 d = 9 無沖突 38 (2) 再哈希法 定義雙重哈希函數(shù)。 造成原因 : A. 主觀設(shè)計不當(dāng) 例，數(shù)字分析法中 8 1 3 4 6 5 3 7 7 1 3 7 2 2 4 7 8 1 3 8 7 4 2 2 8 2 3 0 1 3 6 7 8 1 4 2 2 8 1 7 8 1 3 3 8 9 6 7 沖突！ 例，除留余數(shù)法中 關(guān)鍵字 28 35 63 77 105 p = 21 哈希地址 7 14 0 14 0 解決方法 : 因地制宜 提高素質(zhì) B. 客觀存在 如何設(shè)計都不可能完全避免沖突的出現(xiàn) ？ 哈希地址是有限的，而記錄是無限的。 (5) 除留余數(shù)法 H(key) = key mod p 例， 關(guān)鍵字 28 33 68 82 107 p
公司管理相關(guān)推薦
鄂ICP備17016276號-1