现有长度为 7、初始为空的散列表 HT,散列函数 H(k)=k % 7,用线性探测再散列法解决 冲突。将关键字 22、43、15 依次插入到 HT 后,查找成功的平均查找长度是
时间: 2024-04-03 08:33:31 浏览: 241
分析二分查找成功时的平均查找长度
首先,根据散列函数 H(k)=k % 7,关键字 22、43、15 的散列地址分别为 1、1、1。
接下来,用线性探测再散列法解决冲突。由于关键字 22、43、15 的散列地址都为 1,因此需要进行线性探测再散列:
1. 将关键字 22 插入到散列表中,位置为 1,查找长度为 1。
2. 将关键字 43 插入到散列表中,位置为 2,查找长度为 1。
3. 将关键字 15 插入到散列表中,位置为 3,查找长度为 1。
因此,查找成功的平均查找长度为 (1+1+1)/3 = 1,即平均只需要查找 1 个元素就能找到目标关键字。
阅读全文