一道 数据结构(哈希表)的练习题...

发表于: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