五、（本题8分）

【解答】树的查找路径是从根结点开始到所要查找的结点的路径，最大不会超过B-树的深度。在B树中，除根结点外所有非终端结点都含有??棵子树，所以有n个关键

?2?字的B-树的最大深度为根结点具有两棵子树，其余非终端点有??m??m?棵子树，设最大路径?2?? 长度是x，由于叶子结点表示查找不成功，叶子结点不含关键字，可知B-树的深度为x+1，

第1层共有1个结点，含1个关键字；

第2层共有2个结点，含2(??m?-1)个关键字； ?2??第3层共有2?……

?m??m??m?2(??-1)个关键字； 个结点，含???22?????2?x?2?m?第x层共有2???2??m?个结点，含2???2?x?2(??m?-1)个关键字； ??2?x?1故，共含有的关键个数为：

?m??m??m??m?1+2(??-1)+2??(??-1)+…+2???2??2??2??2?x?2?m??m?(??-1)＝2???2??2??1

?m?由此可得：n?2???2?x?1?1，解得：x?1?log?m?(?2???n?1)，这就是具有n个关键2宇的B一树的查找的最大路径长度。

六、（本题8分）

【解答】折半查找对应的判定树如下图所示。查找不成功的对应于外部结点。查找不成功所走的路径是从根结点到每个外部结点（图中方块结点），和给定值进行比较的关键字个数等于该路径上内部结点个数。

在不成功情况下，一共比较的次数为3*3+4*10=49次。 平均查找长度为49/13≈3.77 七、（本题8分）

【解答】对于a来说，在S2中总可找到离a最近的祖先结点d，这时ab，也就是说a

八、（本题8分） 【解答】

（1）证明：n=1时显然成立，设n=k时成立，即Ek=Ik＋2k，当n=k+1时，设所增加的结点的路径长度为Dk，则有：

Ik+1=Ik+Dk

Ek+1=Ek-Dk+2(Dk+1)=Ek+Dk+2=Ik+2k+Dk+2=Ik+1+2(k+1)=Ik+1+2n 结论也成立。

（2）根据二叉树性质：度为0的结点数=度为2的结点数+1，所以外结点数=n＋l。 s=查找成功总的比较次数/内结点数=(I+n)/n ① u=查找失败总的比较次数/外结点数=E/(n+1)=(I+2n)/(n+1) ②

由①得：I=ns-n，由②得：I=(n+1)u-2n，所以可得：ns-n=(n+1)u-2n，进一步得：

s?(1?1)u?1。 n九、（本题9分）

【解答】

（1）设第v层有u个结点(m

第1层有1个结点，第2层有m个结点，第3层有m2结点，用数学归纳法易知k层共有mk-1个结点。

mh?1（2）整棵树结点数=1+m+m+…+m=。

m?12

h-1

（3）设编号为i的结点双亲的结点编号为x，将编号为i的结点视为完全二叉树的最后一个结点，因此，此完全m叉树中至少有 x-l个度为 m的结点，而 x号结点的度 d（1

≤d≤m），其余的结点均为叶子结点，而编号i就是此完全m又树的总结局数，于是有：

(x-1)m+d+1=i