2. 从业资格
  3. 对于任意一个结点数为n（n>0）的二叉树，其高度h（ ）。A.一定大于n B

对于任意一个结点数为n（n>0）的二叉树，其高度h（ ）。A.一定大于n B

题库2022-08-02  56
问题 对于任意一个结点数为n（n>0）的二叉树，其高度h（  ）。A.一定大于nB.一定小于nC.一定小于log2nD.一定大于log2n
选项 A.一定大于n
B.一定小于n
C.一定小于log2n
D.一定大于log2n
答案 D
解析 本题考查数据结构基础知识。
首先，考虑共x层最多可以放多少个结点，如果要容纳最多的结点数，肯定是看满二叉树。

那满二叉树每层是放多少个？1层是放1个，2层是2个，3层是4个，i层是2^(i-1)个。

对于x层，最多是（1+2+4+……+2^(x-1))=2^x-1

因此，如果为log2n层，则最多可以放置2^( log2n)-1=n-1，因此放不下n个结点。则还要+1层。

所以任意一个结点数为n（n>0）的二叉树，其高度都一定大于log2n。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2427536.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)