计算机 408每日一题2025.9.20

2025年9月20日的计算机408每日一题，考的是数据结构里的散列表问题。

给了个长度11、初始为空的散列表HT，散列函数用H(key)=key%7，冲突解决办法是线性探查（也就是线性探测再散列）。

要把关键字序列87、40、30、6、11、22、98、20挨个插进去。

插入之后，问HT查找失败的平均查找长度是哪个选项？选项是A.4、B.5.25、C.6、D.6.29。

答案：C。

解析得抓住关键点：查找失败的比较次数，得对着每个散列地址算——直到碰到空地址才能确认失败，这中间比了多少次。比如散列地址0，要从地址0查到8（这些位置都不为空），直到地址8是空的，所以一共比了9次。

这题里，散列地址0到6的查找失败比较次数依次是9、8、7、6、5、4、3，平均下来ASL就是（9+8+7+6+5+4+3）除以7，结果正好是6。