數據結構課件第九章-資料下載頁
2025-05-14 21:41本頁面
【正文】 在 key mod m 的基礎上，若發(fā)現沖突，則使用增量 di 進行新的探測，直至無沖突出現為止。 H(key) 哈希函數 m 哈希表長 di 增量序列 關鍵如何設計 di 線性探測法 二次探測法 隨機探測法 H(key) = ( key + di ) mod m 線性探測法 di = 1 , 2 , 3 , …, m 1 隨機探測法 di = 隨機數 二次探測法 di = 12 , 12 , 22 , 22 , 32 , …, +k 2 例，關鍵字為 ( 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 隨機探測法 不妨設第一次隨機數為 9 d = 9 無沖突 38 (2) 再哈希法 定義雙重哈希函數。 H(key) R (key) 若 H(key)出現沖突，則再使用 R (key)求取哈希地址。 ? 假定有 k個關鍵字互為同義詞，若用線性探測法將這 k個關鍵字存入散列表中，至少需要進行（ ）次探測。 A． k1 B． k C． k+1 D． k(k+1)/2 ? 二分查找法要求查找表中各元素的鍵值必須是 ( )排列。 A．遞增或遞減 B．遞增 C．遞減 D．無序 ? 向具有 n個結點的、結構均衡的二叉排序樹中插入一個元素的時間復雜度為 ( )。 A． O(1) B． O(log2n) C． O(n) D． O(nlog2n) ? 從一棵二叉排序樹中查找一個元素時，其平均時間復雜度為 ( )。 A． O(1) B． O(n) C． O(1og2n) D． O(n2) ? 靜態(tài)查找表與動態(tài)查找表二者的根本差別在于 ( ) 。 A．它們的邏輯結構不一樣 B．施加在其上的操作不同 C．所包含的數據元素的類型不一樣 D．存儲實現不一樣 ? 從有序表 (12， 18， 30， 43， 56， 78， 82，95)中依次二分查找 43和 56元素時，其查找長度分別為 __________和 __________。 ? 向一棵二叉排序樹中插入一個元素時，若元素的值小于根結點的值，則應把它插入到根結點的 __________子樹上。 ? 設 a a a3是不同的關鍵字，且a1a2a3,可組成六種不同的輸入序列。問其中哪幾種輸入序列所構造的二叉排序樹的高度為 3？
公司管理相關推薦
鄂ICP備17016276號-1