目录 请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中，查找失败时的平均查找长度如何计算？ 例：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=15， 设每个记录的查找概率相等，采用以上两种方法处理冲突，查找失败时的平均查找长度各是多少 这题可真得是出到点子上去啦，看视频，找资料，网上有得解释真的是有点误人子弟，随后加上问了老师一番才有了确定的结果 没错我们主要得难点还是查找失败得分母到底是什么呢，还有一个网上解释错得，但广为流传得， 但是还是全部体系得去写吧毕竟也许以后就忘了 线性探测 有第一个H（19） = 19MOD 13 = 6，后面得以此类推，位置有冲突得向后面移动，直到有位置 可以得到散列表为 查找失败得平均长度：分母是MOD后面得数也就是13 也就是：（1+13+12+11+10+9+8+7+6+5+4+3+2）/13 = 7 链地址法： 注意了，它的分母也是mod后面的数13 ，并且查的范围是0-12； 查找失败的平均长度：（1+5+1+3+1+1+3+2+1+1+3+2+1）/13 = 25/13； 将关键字序列（14、15、9、4、16、2、21）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为： H(key) = (key x 3) MOD 7，处理冲突采用线性探测再散列法，要求装填因子为0.7。 当时由于老师让及时做出来，就有点匆忙，能懂哪个意思就行 题目 1mod11=1，所以数据1是属于地址1 链地址法处理冲突构造所得的哈希表如下： 查找不成功时：ASL=(3+4+2+1+1+3+1+1+1+1+1)/11=19/11；或者 ASL=(7×1+1×2+2×3+1×4 )/11=19/11， 这个地址就是9 全部少加一个1
查找失败平均查找长度例题
19
14
23
1
68
20
84
27
55
11
10
79
6
1
10
1
3
7
6
1
3
11
10
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
14
1
68
27
55
19
20
84
79
23
11
10
线性探测法例题
(1) 请画出所构造的散列表；
(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。
链地址法例题
将关键字序列{1 13 12 34 38 33 27 22} 散列存储到散列表中。散列函数为：H(key)=key mod 11，处理冲突采用链地址法，求在等概率下查找成功和查找不成功的平均查找长度
13mod11=2，所以数据13是属于地址2
12mod11=1，所以数据12也是属于地址1（这个数据是数据1指针的另一个新数据）
34mod11=1，所以数据34是属于地址1（这个数据是数据12指针的另一个新数据）
38mod11=5，所以数据38是属于地址5
33mod11=0，所以数据33是属于地址0
27mod11=5，所以数据27是属于地址5，（这个数据是数据38指针的另一个新数据）
22mod11=0，所以数据22是属于地址0，（这个数据是数据33指针的另一个新数据）
查找成功时： ASL=（3×1+2×3+1×4）/8=13/8，网上一些博客错误的指正
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
