首页 > 试题广场 >

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

[单选题]
设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(32，24，15，27，20，13)，计算用链地址法作为解决冲突方法的平均查找长度是（ ） 
  • 1.4
  • 1.5
  • 1.6
  • 2
查看正确选项
添加回答
牛客6675933号头像 牛客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头像 张旭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头像 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就要跳楼啦~~~头像 再拿不到offer就要跳楼啦~~~
在链地址法中，我们对所有的键值码，通过散列函数求的各自的地址，对于具有相同地址的键值码，我们把它们放到一个桶里，构成叫做同义链表，如果此时有n个键值码，通过散列函数分配到m个桶中，那么解决冲突的平均查找长度为n/m。应该是这样，欢迎讨论，该题为6/4=1.5.和前面几个回答不一样，求解答。。
发表于 2017-07-13 11:10:30 回复(1)
果冻Bryce头像 果冻Bryce
取模运算，对于两个整数a和b，a对b取模，公式为: (1) 先取整 c = a / b, (2) 取模 r = a - c * b ; 
发表于 2018-03-13 07:25:50 回复(0)
MOMO50头像 MOMO50
发表于 2017-09-08 10:47:40 回复(0)
天涯追梦的航帆头像 天涯追梦的航帆
发表于 2017-06-24 15:48:49 回复(5)
xxxxxxxxxxxxxxxa头像 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头像 Waterbig
b
编辑于 2017-05-20 01:05:03 回复(0)
提交观点

问题信息

C++工程师 2017 京东 哈希 Java工程师
上传者：齐小乐
难度：
9条回答 15604浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号