首页 > 试题广场 >

试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查

[问答题]

试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过 2.0 。并请验证你造的哈希表的实际平均查找长度是否满足要求。（ CHA,CAI,LAN,WEN,LONG,ZHAO,WU,LIU,CHEN,LI,WANG,CAO,YUN,CHANG,YANG ）

Letitia

设用线性探测再散列解决冲突，根据公式Snl≈（1+1/（1-α）） /2 。可求出负载因子为α=0.67。再根据数据个数和装载因子，可求出表长m=15/0.67，取m=23。设哈希函数H（key）=（关键字首尾字母在字母表中序号之和）MOD 23。

从上表求出查找成功时的平均查找长度为ASL_succ=19/15<2.0，满足要求。

发表于 2017-05-23 20:38:01 回复(0)

提交观点

问题信息

哈希

上传者：Letitia

难度：

1条回答 1收藏 881浏览

扫一扫，把题目装进口袋