第1题
将关键字序列 20, 3, 11, 18, 9, 14, 7 依次存储到初始为空、长度为 11 的散列表HT 中，散列函数H(key) = (key×3)%11。H(key)计算出的初始散列地址为H0，发生冲突时探查地址序列是H1 , H2 , H3 , …，其中，Hk =(H0 + k2)%11，k = 1, 2, 3, …。
请回答下列问题。
（1）画出所构造的HT，并计算HT 的装填因子。
（2）给出在HT 中查找关键字 14 的关键字比较序列。
（3）在HT 中查找关键字 8，确认查找失败时的散列地址是多少？
参考答案
1）
填装因子是7/11。
2）H(14)=(14×3)%11=42%11=9，H₁=（H₀+1¹)%11=(9+1)%11=10。H₂=（H₀+2²)%11=(9+4)%11=2，找到关键字 14。
3）H(8)=(8×3)%11=24%11=2，H₁=（H₀+1¹)%11=(2+1)%11=3，H₂=（H₀+2²)%11=(2+4)%11=6，H₃=（H₀+3²)%11=(2+9)%11=0，H₄=（H₀+4²)%11=(2+16)%11=7。