36．第一层有1个结点，第二层至少有2个结点，第三层有2*?m/2?个结点，第四层有2*?m/2?

h-2

个结点，??，第h层至少有2*?m/2?个结点（h≥2）。结点总数是

2h-2h-1

1+2+2*?m/2?+2*?m/2?+?+2*?m/2?=2*?m/2?-1

2

37．

38.

39．

40．（该题答案不唯一。如删P时，亦可将双亲结点中M下来与N一起并入左兄弟成为（K L M N）

41．满二叉检索树可以看作是三阶B-树（2—3树）。B-树的插入和删除算法不适合满二叉检索树。满二叉检索树插入和删除结点后均破坏了“多路平衡查找树”“叶子在同一层上”（查找失败结点）的定义。 42．

43．B+树的查找可从根结点开始随机查找，也可以从最小关键字起顺序查找。

44．含9个叶子结点的3阶B-树至少有4个非叶子结点，当每个非叶子结点均含3棵子树，第三层是叶子结点时就是这种情况。当4层3阶B-树有10个叶子结点时，非叶子结点达到最大值8个，其中第一层一个，第二层两个，第三层五个非叶子结点。

45．在二叉排序树上查找关键字K，走了一条从根结点至多到叶子的路径，时间复杂度是O(logn)，而在中序遍历输出的序列中查找关键字K，时间复杂度是O（n）。按序输入建立的二叉排序树，蜕变为单枝树，其平均查找长度是（n+1）/2，时间复杂度也是O（n）。

46．按中序遍历序列将值1~9依次标上。 47．

ASLsucc=(1*1+2*2+4*3+4*4)/11=33/11

48.

ASLsucc=32/10

49. （2）10,12,15,20,24,28,30,35,46,50,55,68

（3）ASLsucc=41/12 50．

51．

52．序列（2）不可能是二叉排序树中查到363的序列。查到501后，因363<501，后面应出现小于501的数，但序列中出现了623，故不可能。

53．（1）本题的本质是给定中序序列1、2、3、4，有几种不同的二叉排序树，也即该中序序列相当多少不同的前序序列，这是树的计数问题。设中序序列中元素数为n，则二叉数的

n

数目为1/（n+1）C2n，这里n=4，故有14种。图示如下：

（2）最优查找树有4种，上面中⑽ ⑾ ⑿ ⒀ （3）AVL树有，也是（2）中的那4种 （4）完全二叉树有1种，上图中⑽

54．设以Nm表示深度为m的AVL树中含有的最少结点数。显然，N0=0，N1 =1，N2 =2，且Nm = Nm-1 + Nm-2 +1（m≥2）。这个关系与斐波那契序列类似，用归纳法可以证明：当m≥0时，Nm = Fm+2 -1，而Fm约等于Φ/

m

（其中Φ=（1+）/2），则Nm约等于Φ/

m+2

-1（即深

度为m的AVL树具有的最少结点数）

m

当m层的AVL树是满二叉树时，结点数为最大值2-1。

55．树的高度一定增加。因为“查找路径上的任一结点的平衡系数皆为零”，从根结点开始查找，根结点的平衡系数为零，说明根的左右子树等高（不一定是满二叉树）。沿左（或右）子树向下查找时，查找路径上所有结点的平衡系数皆为零，说明任一结点的左右子树等高，查找失败是在叶子结点，插入也是在叶子结点，树的高度自然增加。 56．