一道 数据结构(哈希表)的练习题...
发表于:2007-06-08来源:作者:点击数:
标签:
已知一个线性表(38,25,74,63,52,48),采用的散列函数为H(Key)=Key mod 7,将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为(11);若利用拉链法解决冲突,则在该散列表上进行
已知一个线性表(38,25,74,63,52,48),采用的散列函数为H(Key)=Key mod 7,将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为 (11) ;若利用拉链法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为 (12) 。
(11) A、1.5 B、1.7 C、2.0 D、2.3
(12) A、1.0 B、7/6 C、4/3 D、3/2
解答: 使用开放地址法: 1 2 3 4 5 6 7 48 38 25 74 52 63 3次 1次 1次 2次 4次 1次 共查找了12次,所以使用开放地址法的平均查找长度为:12/6=2次
而使拉链法: 38 52 25 74 63 48 这样的话平均查找长度为:(1+2+1+2+1+1)/6=4/3
|
|
-- 使用开放地址法: 1 2 3 4 5 6 7 48 38 25 74 52 63 3次 1次 1次 2次 4次 1次 38/7=3所在存放在3处, 25/7=4所在存放在4处, 74/7=4与25存放的位置冲突,所以下移到5处, 52/7=3与38存放的位置冲突,所以下移到6处, 63/7=0(7)所以放在7处, 48/7=3与38,52冲突所以放在下一个没有补占用的位置1处。 不知是否说明白。 |
请问楼上,此题我也不太懂,11空处的答案是2啊,楼上得出的结果是6,不对啊??另外我对此题的理解是这样的: 1 2 3 4 5 6 7 48 38 25 74 52 63 1次 2次 2次 2次 3次 2次 平均查找长度为:12/6=2 |
- |
-- 作者:caichangzh -- 发布时间:2003-9-10 12:08:00
-- 上面的写错了,
是 12/6=2
|
-- 作者:caichangzh -- 发布时间:2003-9-10 12:28:00
-- 使拉链法:我认为是把有地址冲突的数据形成一个链表(以第一个数据为首地址),不知是否正确.
38 -——> 52 25 -——> 74 63 48 成功查找的次数: 38 1次数 52 2次数 25 1次数 74 2次数 63 1次数 48 1次数
这样的话平均查找长度为:(1+2+1+2+1+1)/6=4/3 |
|
-- |
-- 开放定址法: 38%7=3 //1次 25%7=4 //1次 74%7=4冲突 =5 //2次 63%7=0 //1次 52%7=3冲突 =4冲突 =5冲突 =6 //4次 48%7=6冲突 =0冲突 =1 //3次 一共是1+1+2+1+4+3=12 12/6=2 拉链(链接)法: 38%7=3 //1次 25%7=4 //1次 74%7=4 //2次 63%7=0 //1次 52%7=3 //2次 48%7=6 //1次 一共是 1+1+2+1+2+1=8 8/6=4/3 |
楼主也没有全错,他错的是这句话:“48/7=3与38,52冲突所以放在下一个没有补占用的位置1处。”还有他的/应该是%。 48%7=3是和52,63冲突。 另外我认为他的拉练法是正确的,和你不就是一样么? |
|
原文转自:http://www.ltesting.net