有一结点的关键字序列F= {129，72，180，105，147，96，45，69}，散列函数为：H (k) =k mod 11，其中k为关键字，散列地址空间为0～10。要求：
问答题
画出相应的散列表。当发生冲突时，以线性探测法解决。该散列表的装填因子是多少？计算在等概率情况下，查找成功和查找不成功时的平均查找长度ASL。
【正确答案】正确答案：采用线性探测法处理冲突建立的散列表如下： H(129)=129 mod 11=8 H(72)=72 mod 11=6 H(180)=180 mod 11=4 H(105)=105 mod 11=6冲突H
1
(105)=(105+1) mod 11=7 H(147)=147 mod 11=4冲突H
1
(147)=(147+1) mod 11=5 H(96)=96 mod 11=8冲突H
1
(96)=(96+1) mod 11=9 H(45)=45mod 11=1 H(69)=69mod 11=3 综上所述，散列表如表4—5所示。
【答案解析】
问答题
画出相应的散列表。当发生冲突时，以链地址法解决。计算在等概率情况下，查找成功和查找不成功时的平均查找长度ASL（只将与关键字的比较次数计算在内即可）。
【正确答案】正确答案：采用链地址法处理冲突建立的散列表如下：
【答案解析】
问答题
试按各关键字在序列F中的次序将它们依次插入一棵初始为空的平衡二叉排序树中，画出每一步插入后平衡二叉排序树的形态。若做了某种旋转，请注明旋转的类型。
【正确答案】正确答案：构造平衡二叉排序树的过程如图4—13所示。
【答案解析】