数据结构自我探索1

答案：A D

第一空：

因为有12个关键字，

所以构成了高度为4的二叉树

前3层关键字总数为7，第4层有5个关键字

则，前3层，查找总长度 =第一层个数 * 第一层查找长度（1） + 第二层个数 * 第二层查找长度（2）+ 第三层个数（4） * 第三层查找长度（3） = 1 + 4 + 12 = 17

第四层，查找总长度 = 第四层查找长度（4） * 第五层个数（5） = 20

总个数为 12个，所以查找成功的平均查找长度 = （17 + 20） / 12

第二空：

其实是找二叉树中叶子结点需要找的次数

根据上边第一问推论的二叉树的样子，可以看出

第4层有3个叶子结点

第5层有 5 * 2 个叶子结点

共13个叶子结点

第四层查找失败的总长度 = 叶子结点个数（3） * 证明它不存在需要经过的关键字（3） = 9

第五层查找失败的总长度 = 叶子结点个数（10） * 证明它不存在需要经过的关键字（4） = 40

所以最后得出查找失败的平均查找长度 = （9 + 40） / 13