如果结果不匹配，请 
更多“试证明，含n个节点的二叉树的最小高度为[log2n]——这也…”相关的问题
第1题
考查实现如134页代码5.20所示的层次遍历算法，设二叉树共含n个节点。a)试证明，只要辅助队列Q的容量不低于[n/2]，就不致于出现中途溢出的问题;b)在规模为n的所有二叉树中，哪些的确会需要如此大容量的辅助队列？c)在层次遍历过程中，若Q中节点的总数的确会达到这么多，则至多可能达到多少次？
第2题
设二叉树共含n个节点，且各节点数据项的类型支持线性累加（类似于整数或浮点数)，试设计并实现一个递归算法，按照如下规则，在o（n)时间内为每个节点设适当的数值：树根为0；对于数值为k的节点，其左孩子数值为2k+1，右孩子为2k+2。
第3题
考查任意阶的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。
第4题
考查教材5.4.2、5.4.3、5.4.4和5.4.5节所介绍的各种迭代式二叉树遍历算法。a)试证明，这些算法都是正确的——亦即，的确会访问每个节点一次且仅一次；b)试证明，无论递归式或迭代式，这些算法都具有线性时间复杂度；c)这些算法的空间复杂度呢？
第7题
a)试证明，在从堆顶通往任一叶节点的沿途上，各节点对应的关键码必然单调变化;b)试给出一个算法，对于秩为r的任一节点，在O（1)时间内确定其在任何高度h上祖先的秩;c)试改进percolateUp算法（代码10.7)，将其中执行的关键码比较减少至O（loglogn)次;d)经过以上改进，percolateUp算法总体的渐进复杂度是否有所优化？
第9题
就最坏情况而言，红黑树在其重平衡过程中可能需要对多达Ω（logn)个节点做重染色。然而，这并不足以代表红黑树在一般情况下的性能。试证明，就分摊意义而言，红黑树重平衡过程中需重染色的节点不超过o（1)个。
