数据结构考研分类复习真题 第九章 集合[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【清华大学八(分)】

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