数据结构
2024-42
将关键字序列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的装填因子。（6分）
(2) 给出在HT中查找关键字14的关键字比较序列。（2分）
(3) 在HT中查找关键字8，确认查找失败时的散列地址是多少？（2分）
答案
答案
(1) HT 构造与装填因子
散列表 HT（长度 11，索引 0～10）为：
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 11 | - | 14 | 7 | - | 20 | 9 | - | - | 3 | 18 |
装填因子 alpha=7/11
(2) 查找关键字 14 的比较序列
3, 18, 14
(3) 查找关键字 8 确认失败时的散列地址
7