數據結構考研分類復習真題 第九章 集合[28]

　　 試為下列關鍵字設計哈希表要求所設計的表在查找成功時的平均查找長度不超過並請驗證你造的哈希表的實際平均查找長度是否滿足要求(CHACAILANWENLONGZHAOWULIUCHENLIWANGCAOYUNCHANGYANG)【清華大學 五】

　　 設abcde五個字符的編碼分別為並設標識符依以下次序出現acbdaabeabadcdbcaece要求用哈希(Hash)方法將它們存入具有個位置的表中

　　()將上述關鍵字(標識符)構造一個哈希函數使得發生沖突盡可能地少;()線性探測再散列法解決沖突

　　寫出上述各關鍵字在表中位置【南開大學 六 (分)】

　　 對以下關鍵字序列建立哈希表(SUNMONTUEWEDTHUFRISAT)哈希函數為H(K)=(關鍵字中第一個字母在字母表中的序號)MOD 用線性探測法處理沖突求構造一個裝填因子為的哈希表;並分別計算出在等概率情況下查找成功與不成功的平均查找長度【西北大學   二  (分)】

　　 設散列表為HT []即表的大小為m=現采用雙散列法解決沖突散列函數和再散列函數分別為

　　H(key)=key % ;      注:%是求余數運算(=mod)

　　Hi=(Hi+REV(key+)%+) % ;  i=…m

　　其中函數REV(x)表示顛倒進制數x的各位如REV()=REV()=等若插入的關鍵碼序列為()

　　()(分)試畫出插入這個關鍵碼後的散列表;()(分)計算搜索成功的平均搜索長度ASL【清華大學八(分)】

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []