在哈希表中,如果使用线性探测法解决冲突,假设哈希表大小为10,哈希函数为H(key) = key % 10。现在依次插入键值 23, 34, 45, 56, 24,则插入24时,需要探测多少次才能找到合适的位置?
答案解析
核心考点说明:本题考察哈希表的线性探测法解决冲突。重点在于理解线性探测法的规则,即当发生冲突时,依次查找下一个位置,直到找到空闲位置。难点在于模拟插入过程并计算探测次数。
解题思路分析:
1. 插入23: H(23) = 23 % 10 = 3,位置3空闲,插入位置3,探测1次。
2. 插入34: H(34) = 34 % 10 = 4,位置4空闲,插入位置4,探测1次。
3. 插入45: H(45) = 45 % 10 = 5,位置5空闲,插入位置5,探测1次。
4. 插入56: H(56) = 56 % 10 = 6,位置6空闲,插入位置6,探测1次。
5. 插入24: H(24) = 24 % 10 = 4,位置4被34占用,发生冲突,探测下一个位置5,被45占用,继续探测下一个位置6,被56占用,继续探测下一个位置7,位置7为空闲,插入位置7,总计探测4次。
选项分析:
A. 错误。插入24时,需要进行4次探测。
B. 错误。插入24时,需要进行4次探测。
C. 错误。插入24时,需要进行4次探测。
D. 正确。根据线性探测法的规则,插入24需要探测4次。
易错点提醒:容易漏掉探测的次数,或混淆不同键值之间的冲突情况。必须严格按照线性探测法的步骤进行模拟。
正确答案的关键依据:根据线性探测法模拟插入过程,计算插入24时需要探测的次数。
正确答案:D