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