首页 > 试题广场 >

回答下面问题

[问答题]

将关键字序列(7 . 8 . 30 . 11 . 18 . 9 . 14)散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组。散列函数是： H(key)=(key x3)MOD 7 ，处理冲突采用线性探测再散列法。要求装填（载）因子为0.7 。
问题 .
(1)请画出所构造的散列表。
⑵分别计算等概率情况下查找成功和查找不成功的平均查找长度。

查看答案及解析

城市里的养猫者

（1）构造的散列表如下：

下标	0	1	2	3	4	5	6	7	8	9
关键字	7	14		8		11	30	18	9

【评分说明】所画的散列表长度正确，给1 分。插入的关键字中，前 4 个无冲突的关键字填写正确，给 2 分。后 3 个关键字填写正确，每个给 1 分。考生可以不写出计算过程。若解答部分正确，酌情给分。

（2）
查找成功的平均查找长度：ASL 成功=12/7。
查找不成功的平均查找长度：ASL 不成功=18/7。

发表于 2016-11-19 16:12:23 回复(4)

雨中漫步888

2.查找不成功的平均查找长度
（待查找的数字肯定不在散列表中）
【解题的关键之处】根据哈希函数地址为MOD7，因此任何一个数经散列函数计算以后的初始地址只可能在0~6的位置

地址0，到第一个关键字为空的地址2需要比较3次，因此查找不成功的次数为3.
地址1，到第一个关键字为空的地址2需要比较2次，因此查找不成功的次数为2.
地址2，到第一个关键字为空的地址2需要比较1次，因此查找不成功的次数为1.
地址3，到第一个关键字为空的地址4需要比较2次，因此查找不成功的次数为2.
地址4，到第一个关键字为空的地址4需要比较1次，因此查找不成功的次数为1.
地址5，到第一个关键字为空的地址2(比较到地址6，再循环回去)需要比较5次，因此查找不成功的次数为5.
地址6，到第一个关键字为空的地址2(比较到地址6，再循环回去)需要比较4次，因此查找不成功的次数为4.

发表于 2020-06-02 17:06:09 回复(0)