首页 > 试题广场 >

题目来源于王道论坛 将关键字序列(7、8、30、11、

[问答题]
题目来源于王道论坛

将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为H(key)=(key×3) mod 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。

1)请画出所构造的散列表。

2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。

推荐
1)由装载因子为0.7,数据总数为7,得一维数组大小为7/0.7=10,数组下标为0~9。所构造的散列函数值见表B-3。

B-3

key

7

8

30

11

18

9

14

H(key)

0

3

6

5

5

6

0


采用线性探测再散列法处理冲突,所构造的散列表见表B-4。

B-4

地址

0

1

2

3

4

5

6

7

8

9

关键字

7

14

8

11

30

18

9


B-5

key

7

8

30

11

18

9

14

次数

1

1

1

1

3

3

2

故ASL成功=查找次数/元素个数=(1+2+1+1+1+3+3)/7=12/7。

这里要特别防止惯性思维。查找失败时,是根据查找失败位置计算平均次数,根据散列函数mod 7,初始只可能在0~6的位置。等概率情况下,查找0~6位置查找失败的查找次数见表B-6。

B-6

H(key)

0

1

2

3

4

5

6

次数

3

2

1

2

1

5

4

故ASL不成功=查找次数/散列后的地址个数=(3+2+1+2+1+5+4)/7=18/7。

发表于 2018-09-03 20:23:49 回复(2)
发表于 2021-10-06 16:12:52 回复(0)
这解题哪用到再散列了啊?
发表于 2020-06-02 23:41:12 回复(0)
难道不是再散列法吗????
发表于 2020-03-23 11:24:56 回复(0)

这道题不是用的再散列方法吗


发表于 2019-11-29 16:17:04 回复(0)