已知关键字序列为{17,77,76,66,10 , 98},采用线性探测再散列解决冲突, 哈希函数为H(K)= K %11,表长为12。 (1)构造哈希表 (2)求出等概率下查找成功时的平均查找长度。
时间: 2024-03-30 22:37:54 浏览: 47
好的,问题已经记录下来了。现在回答你的问题:
(1) 构造哈希表:
首先,我们需要创建一个12个元素的哈希表,初始状态下所有元素都为空。然后,我们按照哈希函数H(K) = K % 11的规则,将关键字序列中的每个关键字插入到哈希表中。
具体的插入过程如下:
- 17 % 11 = 6,将17插入到哈希表的第6个位置;
- 77 % 11 = 0,将77插入到哈希表的第0个位置;
- 76 % 11 = 1,将76插入到哈希表的第1个位置;
- 66 % 11 = 0,发生冲突,采用线性探测再散列的方法,将66插入到哈希表的第1 + 1 = 2个位置;
- 10 % 11 = 10,将10插入到哈希表的第10个位置;
- 98 % 11 = 3,将98插入到哈希表的第3个位置。
最终得到的哈希表为:
|0|1|2|3|4|5|6|7|8|9|10|11|
|---|---|---|---|---|---|---|---|---|---|---|---|
|77|76|66|98|||17||||10|
(2) 求出等概率下查找成功时的平均查找长度:
假设哈希表中有n个关键字,m个哈希桶,平均查找长度为ASL。由于这是等概率的情况,我们可以采用公式ASL = (1 + (1/1-p))/2来计算。
其中,p为填装因子,即哈希表中已有关键字数目n与哈希桶数目m的比值。在这个例子中,n = 6,m = 12,因此p = n/m = 0.5。
带入公式ASL = (1 + (1/1-p))/2,可得ASL = 1.67。因此,等概率下查找成功时的平均查找长度为1.67。
阅读全文