已知一个长度为12的表{Jan，Feb，Mar，Apr，May，June，July，Aug， Sep，Oct，Nov，Dec}:

问答题试按照表中元素的顺序依次插入一棵初始为空的二叉排序树（字符之间以字典序比较大小），请画出最终对应的二叉排序树。

【正确答案】正确答案：二叉排序树的构建如图6—9所示。

【答案解析】

问答题若对表中的元素先进行排序构成有序表（字典序），试求在等概率情况下对此有序表进行检索时检索成功的平均检索长度。

【正确答案】正确答案：按字典序对表中元素进行排序，得：Apr，Aug，Dec，Feb，Jan，July， June， Mar，May，Nov，Oct，Sep，其查找成功的平均查找长度为：(5+7+7+4+3+10+7+4+6+8+7+6) /12=74/12=6.2。

【答案解析】

问答题按表中元素的顺序构造一棵平衡二叉树，试求在等概率情况下检索成功的平均检索长度。

【正确答案】正确答案：平衡二叉树的形状如图6—10所示。

【答案解析】