已知有一个关键字序列：（19，14,23,1,68,20,8_

推荐

牛客-007

答案：A
这些关键字除以7取余后分别得到5,0,2,1,5,6,0,6，6，4,3,2存储结构如下
位置--存储
0-----14-84 //14查找1次，84需要查找2次，以下类似
1-----1
2-----23-79
3-----10
4-----11
5-----19-68
6-----20-27-55
总查找次数为1+2+1+1+2+1+1+1+2+1+2+3=18
总共有12的关键字
平均查找次数为18/12=1.5

编辑于 2015-01-31 10:39:48 回复(7)

rppp

主要考察哈希表的链地址存储，分别计算每个数据的查找程度，如下所示：

地址为0：14（1） 84（2）

地址为1：1（1）

2：23（1） 79（2）

3：10（1）

4：11（1）

5：19（1） 68（2）

6：20（1） 27（2） 55（3）

平均查找程度=（1+2+1+1+2+1+1+1+2+1+2+3）/12 = 18/12 = 1.5

发表于 2017-07-24 11:47:12 回复(0)

sunlight_run

	0	1	2	3	4	5	6
%7	14，84，	1	23，79	10	11	19，68	20，27，55
次数	1+2	1	1+2	1	1	1+2	1+2+3

总查找次数相加为18，所以平均查找长度为18/12=1.5

发表于 2017-06-16 17:03:38 回复(0)

牛客651205号

我去，我就说怎么没答案，当成开放地址法做了。。。

发表于 2019-02-18 15:33:08 回复(0)

Sc0tt

这12个数取余后依次为：5 0 2 1 5 6 0 6 6 4 3 2

又因为求的是查找成功的ASL，采用链地址法来解决冲突的ASL在成功和不成功的时候分母是不同的；

查找成功时，分母为哈希表元素个数；查找不成功时，分母为哈希表长度。

所以查找成功时，ASL为（1*7+2*4+3*1) / 12=18/12=1.5

发表于 2018-05-21 19:34:22 回复(0)

我是一只小小小小菜鸟

思路：散列表这块，有两道题型，第一种就是hash函数的构造，采用的是除留取余的方法，还有一种是解决冲突的方法，这道题就是如此，用的是链表的方法。

大概过程就不写了，结果就是1+1+1+1+1+1+2+2+3+1+2+2=18，然后再除以长度12就行了。18/12=1.5

发表于 2016-08-16 16:14:00 回复(0)

风声，雨声

查找成功：总查找次数为1+2+1+1+2+1+1+1+2+1+2+3=18
总共有12的关键字

平均查找次数为18/12=1.5

查找不成功： 0---14->84 查地址0没查到所要查的值，需2次遍历

1--1 查地址1没查到所要查的值，需1次遍历

2--23->79 2

3--10 1

4--11 1

5--19->68 2

6--20->27->5 3

（2+1+2+1+1+2+3）/7=1.7

查找成功和查找不成功的分母不一样，这点要区别开来

发表于 2015-09-06 16:10:09 回复(1)

付雨帆

答案：A

这些关键字除以7取余得到地址：5，0，2，1，5，6，0，6，6，4，3，2存储结构如下：

位置----存储

0------14-84 // 14查找1次，84需要查找2次，以下类似

1------1

2------23-79

3------10

4------11

5------19-68

6------20-27-55

查找次数为1+2+1+1+2+1+1+1+2+1+2+3=18

有12个关键字

平均查找次数为18/12=1.5

编辑于 2017-03-11 15:20:23 回复(0)

kainever

查找长度就是找到对应的值要经过几步... 如果没有冲突的话可以直接到找到所以长度为1

发表于 2015-08-02 18:49:19 回复(0)

飞云

答案B

通过哈希函数转换关键序列为：

0---14->84

1--1

2--23->79

3--10

4--11

5--19->68

6--20->27->55

通过上面可以看到这些关键词可以形成7条链

所以平均查找 12/7=1.7

其实本题主要是看能形成几条哈希链总数除以哈希链数就是平均查找长度

-------------------------------------------------
上面的之前的答案，
没有考虑到定位到每条哈希链后，还要进行查找
查找次数为1+2+1+1+2+1+1+1+2+1+2+3=18
平均查找次数为：18/12=1.5

编辑于 2015-04-24 13:06:26 回复(3)

已知有一个关键字序列：（19，14,23,1,68,20,8

问题信息

热门推荐

相关试题