问答题有一结点的关键字序列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(1so)=180 mod 11=4
H(105)=105 mod 11=6冲突H₁(105)=(105+1)mod 11=7
H(147)=147 mod 11=4冲突H₁(147)=(147+1)mod 11=5
H(96)=96 mod 11=8冲突H₁(96)=(96+1)mod 11=9
H(45)=45mod 11=1
H(69)=69mod 11=3
综上所述，散列表如下表所示。

{{B}}线性探测法处理冲突建立的散列表{{/B}}
下标	0	1	2	3	4	5	6	7	8	9	10
k		45		69	180	147	72	105	129	96
探测次数		1		1	1	2	1	2	1	2

装填因子α=8/11。
ASL_succ=5×1+2×3)/8=11/8
ASL_unsucc=1+2+1+8+7+6+5+4+3+2+1)/11=40/11

【答案解析】

问答题画出相应的散列表。当发生冲突时，以链地址法解决。计算在等概率情况下，查找成功和查找不成功时的平均查找长度ASL(只将与关键字的比较次数计算在内即可)。

【正确答案】采用链地址法处理冲突建立的散列表如下：
[*]
ASL_succ=(5×1+3×2)/8=11/8
ASL_unsucc=(0+1+0+1+2+0+2+0+2+0+0)/11=8/11
说明：本题中已经明确指出采用链地址法，只将与关键字的比较计算在内，因此上述ASL_unsucc的解法是正确的。如果本题要求将空指针的比较也包括在内，则
ASL_unsucc=(1+2+1+2+3+1+3+1+3+1+1)/11=19/11

【答案解析】

问答题试按各关键字在序列F中的次序将它们依次插入一棵初始为空的平衡二叉排序树中，画出每一步插入后平衡二叉排序树的形态。若做了某种旋转，请注明旋转的类型。

【正确答案】构造平衡二叉排序树的过程如图所示。 [*]

【答案解析】