如果结果不匹配，请 
更多“试证明，由一组共n个互异节点组成的二叉搜索树，总共有（2n)…”相关的问题
第4题
考查实现如134页代码5.20所示的层次遍历算法，设二叉树共含n个节点。a)试证明，只要辅助队列Q的容量不低于[n/2]，就不致于出现中途溢出的问题;b)在规模为n的所有二叉树中，哪些的确会需要如此大容量的辅助队列？c)在层次遍历过程中，若Q中节点的总数的确会达到这么多，则至多可能达到多少次？
第5题
设二叉树共含n个节点，且各节点数据项的类型支持线性累加（类似于整数或浮点数)，试设计并实现一个递归算法，按照如下规则，在o（n)时间内为每个节点设适当的数值：树根为0；对于数值为k的节点，其左孩子数值为2k+1，右孩子为2k+2。
第6题
二叉搜索树可用来对n个元素进行排序。试编写一个排序算法，首先将n个元素a[1..n]插人到一个空的
二叉搜索树中，然后对树进行中序遍历，并将元素按序放人数组a中，为简单起见，假设a中的数据互不相同。试编写一个函数，从一棵二叉搜索树中删除最大元素。要求函数的时间复杂性必须是O(h)，其中h是二叉搜索树的高度。
第7题
就最坏情况而言，红黑树在其重平衡过程中可能需要对多达Ω（logn)个节点做重染色。然而，这并不足以代表红黑树在一般情况下的性能。试证明，就分摊意义而言，红黑树重平衡过程中需重染色的节点不超过o（1)个。
第9题
考查任意阶的B-树T。a)若T的初始高度为1，而在经过连续的若干次插入操作之后，高度增加至h且共有n
考查任意阶的B-树T。
a)若T的初始高度为1，而在经过连续的若干次插入操作之后，高度增加至h且共有n个内部节点，则在此过程中T总共分裂过多少次？
b)在如上过程中，每一关键码的插入，平均引发了多少次分裂操作？
c)若T的初始高度为h且含有n个内部节点，而在经过连续的若干次删除操作之后高度下降至1，则在此过程中T总共合并过多少次？
d)设T的初始高度为1，而且在随后经过若干次插入和删除操作——次序任意，且可能彼此相间。试证明：若在此期间总共做过S次分裂和M次合并，且最终共有n个内部节点，高度为h，则必有：S-M=n-h。
第10题
设主串t和模式串p分别是由d（d≥2)元字符集中随机字符组成的长度为n和m的字符串.试证明简单子串
设主串t和模式串p分别是由d(d≥2)元字符集
中随机字符组成的长度为n和m的字符串.试证明简单子串搜索算法所做比较次数的期望值为
由此可见,对于随机选取的字符串,简单子串搜索算法还是十分有效的.
