首页 > 试题广场 >

已知一个线性表{24, 19, 33, 56, 72, 68

[填空题]

已知一个线性表{24, 19, 33, 56, 72, 68}，假定采用hash函数h(key)=key%7计算hash地址，并存储在hash表A[0…6]中，若采用线性探测方法解决冲突（即若发生冲突，则从冲突位置顺序探测hash表中的其他存储单元，直到找到空位置为止），则在该hash表上查找元素68，需要查找多少1步

查看答案及解析

城枫墨凉

散列表的填表过程如下：

1.首先存入第一个元素24，由于h(24)=24%7=3，又因为3号单元现在没有数据，所以把24存入3号单元。

2.接着存入第二个元素19，由于h(19)=19%7=5，又因为5号单元现在没有数据，所以把19存入5号单元。

3.接着存入第三个元素33，由于h(33)=33%7=5，此时的5号单元已经被19占据，所以进行线性再散列，线性再散列的公式为：Hi=（H(key)+di）% m ，其中的di=1，2，3，4...。所以H1=(5+1)%7=6，此时的单元6没有存数据，所以把33存入到6号单元。

4. 接着存入第四个元素56，由于h(56)=56%7=0，此时的0号单元没有数据，所以把56存入0号单元。

5.接着存入第五个元素72，由于h(72)=72%7=2。此时的单元2没有存数据，所以把72存入到2号单元。

6. 最后存入第六个元素68，由于h(68)=68%7=5，此时的5号单元已被占据，所以进行线性再散列：H1=(5+1)%7=6，但6号单元也被占据了，所以再次散列：H2=(5+2)%7=0，但0号单元也被占据了，所以进行线性再散列：H1=(5+3)%7=1，此时的单元1没有存数据，所以把68存入到1号单元。

如果一个元素存入时，进行了N次散列，相应的查找次数也是N，所以24,19,56,72这四个元素的查找长度为1，33的查找长度为2，68的查找长度为4，答案为4。

如果要计算散列表上的平均查找长度，我们首先必须要知道在建立这个散列表时，每个数据存储时进行了几次散列。这样就知道哪一个元素，查找的长度是多少。

所以平均查找长度为：(1+1+1+1+2+4)/6=1.666

发表于 2018-01-10 13:41:29 回复(0)