计算用链地址法作为解决冲突方法的平均查找长度是（）_京东笔试题

牛客6675933号

链地址法作为解决冲突方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针。

0 1 2 3 4 5 6

15 24 32 27

20

13

因此查找长度为 1、 1、 1、1、 2、3 等概率情况下查找成功时的平均查找长度为 9/6=1.5

编辑于 2017-06-06 21:44:56 回复(6)

张旭8095

拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于 1，但一般均取α≤1。

(32，24，15，27，20，13)对7取模后分别是：{4,3,1,6,6,6}，那么链地址法的结果：

0 1 2 3 4 5 6 7

15 24 32 27

20

13

所以六个数分别查找长度为：1,1,1,1，2,3 所以平均长度为9/6=1.5

发表于 2017-08-31 22:55:37 回复(0)

pcd

32 mod 7 = 4 (不冲突 1次查找)

24 mod 7 = 3 (不冲突 1次查找)

15 mod 7 = 1 (不冲突 1次查找)

27 mod 7 = 6 (冲突 1次查找)

20 mod 7 = 6 (冲突 2次查找)

13 mod 7 = 6 (冲突 3次查找)

平均查找时间 AVL = (1+1+1+1+ 4+2+3)/6 = 1.5

发表于 2018-04-10 23:32:56 回复(1)

再拿不到offer就要跳楼啦~~~

在链地址法中，我们对所有的键值码，通过散列函数求的各自的地址，对于具有相同地址的键值码，我们把它们放到一个桶里，构成叫做同义链表，如果此时有n个键值码，通过散列函数分配到m个桶中，那么解决冲突的平均查找长度为n/m。应该是这样，欢迎讨论，该题为6/4=1.5.和前面几个回答不一样，求解答。。

发表于 2017-07-13 11:10:30 回复(1)

果冻Bryce

取模运算，对于两个整数a和b，a对b取模，公式为: (1) 先取整 c = a / b, (2) 取模 r = a - c * b ;

发表于 2018-03-13 07:25:50 回复(0)

MOMO50

http://blog.csdn.net/u011080472/article/details/51177412

发表于 2017-09-08 10:47:40 回复(0)

天涯追梦的航帆

发表于 2017-06-24 15:48:49 回复(5)

xxxxxxxxxxxxxxxa

A successful search requires that about 1 + (γ /2) links be traversed, since there is a guarantee that one link must be traversed (since the search is successful)

open hash的表比较简单，谁都能很快画出来。但是平均搜索长度计算，前面几位都说的不太清楚：

Load factor= 6/8=0.75 所以1+0.75/2=1.325 ，答案没有

但是如果按照实际的次数计算（1+1+1+1+2+3）/6=1.5次。

那么到底按照什么标准呢？如果表的大小比较大，数据量比较多，负载因子远远大于1，那么此时使用上面的公式，应该是最接近正确答案的。

编辑于 2018-05-22 16:40:42 回复(0)

Waterbig

b

编辑于 2017-05-20 01:05:03 回复(0)

计算用链地址法作为解决冲突方法的平均查找长度是（）

问题信息

热门推荐

相关试题

计算用链地址法作为解决冲突方法的平均查找长度是（ ）

问题信息

热门推荐

相关试题

计算用链地址法作为解决冲突方法的平均查找长度是（）