对于输入30,20,56,75,31,19和散列函数h(K)=Kmod11,做以 a.构造它们的闭散列表。" b.求在本表中成功查找的最大键值比较次数。 c.求本表中成功查找的平均键值比较次数
时间: 2024-01-24 15:19:42 浏览: 32
a. 首先根据散列函数h(K)=Kmod11计算出每个键值对应的散列地址:
- 30 → 8
- 20 → 9
- 56 → 1
- 75 → 10
- 31 → 9 (发生冲突,采用线性探测法)
- 19 → 8 (发生冲突,采用线性探测法)
根据线性探测法,发生冲突时,继续向后探测直到找到空的散列地址为止。因此,31会依次检查10、0、1、2、3、4、5、6、7、8这些地址,最终插入到地址2的位置;19会依次检查9、10、0、1、2、3、4、5、6、7这些地址,最终插入到地址3的位置。
因此,构造出的闭散列表为:
0 | |
1 | 56 |
2 | 31 |
3 | 19 |
4 | |
5 | |
6 | |
7 | |
8 | 30 |
9 | 20 |
10 | 75 |
b. 在本表中成功查找的最大键值比较次数为2,即找到键值56时需要比较一次散列地址和一次键值。
c. 在本表中成功查找的平均键值比较次数可以通过下面的公式计算:
平均键值比较次数 = 成功查找的键值比较次数 / 成功查找的键值总数
其中,成功查找的键值比较次数为所有成功查找时比较散列地址和键值的次数之和,成功查找的键值总数为表中已有的键值个数。
我们可以模拟查找每个键值的过程,统计比较次数。具体地,查找键值30时需要比较1次;查找键值20时需要比较1次;查找键值56时需要比较2次;查找键值75时需要比较1次;查找键值31时需要比较2次;查找键值19时需要比较2次。因此,成功查找的键值比较次数为1+1+2+1+2+2=9,成功查找的键值总数为6。
平均键值比较次数 = 9 / 6 = 1.5