试题出自试卷《2024届408计算机学科专业基础真题解析（回忆版）》

【答案】
答：
（1）构造的散列表：

HT的装填因子=7/11。
（2）关键字比较次数为3；比较序列为3、18、14。
（3）关键字8的查找过程：
H0(8)=(8*3)%11=2，与14比较失败；
H1(8)=(H0+1^2)%11=(2+1)%11=3，与7比较失败；
H2(8)=(H0+2^2)%11=(2+4)%11=6，与9比较失败；
H3(8)=(H0+3^2)%11=(2+9)%11=0，与11比较失败；
H4(8)=(H0+4^2)%11=(2+16)%11=7，为空，彻底失败，退出查找。

【考点】本题考查数据结构--查找--散列/哈希表--哈希表的应用。
【解析】通过散列函数H(key)计算出每个关键字的地址；再根据题中给定的探测函数Hk来处理冲突。
H(20)=(20*3)%11=5。H(3)=(3*3)%11=9。H(11)=(11*3)%11=0。H(18)=(18*3)%11=10。
H(9)=(9*3)%11=5，冲突；H1(9)=(5+1^2)%11=6。
H(14)=(14*3)%11=9，冲突；H1(14)=(9+1^2)%11=10，冲突；H2(14)=(9+2^2)%11=2。
H(7)=(7*3)%11=10，冲突；H1(7)=(10+1^2)%11=0，冲突；H2(7)=(10+2^2)%11=3。