信息技术岗位知识竞赛
一棵n个结点的完全二叉树，则二叉树的高度h为（）。A、n/2B、log2nC、（log2n）/2D、[log2n]+1E、2n-1
题目
一棵n个结点的完全二叉树，则二叉树的高度h为（）。
- A、n/2
- B、log2n
- C、（log2n）/2
- D、[log2n]+1
- E、2n-1
相似问题和答案
第1题：
设一棵完全二叉树共有699个结点，则该二叉树的叶子结点数为【】
A．349
B．350
C．255
D．351
[解析]若一棵完全二又树有n个结点，则其叶子结点数为n／2个（向上取整）．
第2题：
设一棵完全二叉树共有699个结点，则该二叉树中的叶子结点数为( )。
A．349
B．350
C．255
D．351
解析：所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其父结点数为int(n/2)，而叶子结点数等于总结点数减去父结点数。本题n=699，故父结点数等于int(699/2)＝349，叶子结点数等于 699-349＝350。
第3题：
此题为判断题(对，错)。
第4题：
第5题：
关于满二叉树、完全二叉树有以下说法：
①满二叉树不仅是一种特殊形态的二叉树，而且是一种特殊的完全二叉树。
②具有n个结点的满二叉树的高度为
+1。
③具有n个结点的完全二叉树的高度为+1。
④具有n个结点的满二叉树的高度为log2(n+1)。
⑤具有n个结点的满二叉树共有叶子结点
。
其中______最全面、最准确。
A．①②④
B．③④⑤
C．①③④⑤
D．全对
解析：若二叉树的每一层的结点数都是最大结点数，也就是说每一层都是满的，那么此时的二叉树便成为一棵满二叉树。若二叉树除最后一层外都是满的，而且最后一层的结点都连续紧挨靠左，那么称此时的二叉树为完全二叉树。所谓的“完全”，指的是在给其结点按层次自上而下、同一层自左至右编号时，n个结点(设完全二叉树结点总数为n)与同深度的满二叉树中编号从1到n的结点一一对应。因此，①正确。显然，③是正确的。注意到，满二叉树是特殊的二叉树，因此②也正确。值得指出的是，②和③中的n分别满足不同的条件，因此，②和③都正确。设具有n个结点的满二叉树的高度为h，那么根据二叉树的性质有n=2h-1，从而有h=log2(n+1)，叶子结点的个数为n-2h-1-1=2h-1=(n+1)/2，因此④和⑤都正确。值得指出的是②和④是等价的，只是表述不同而已。综上所述，由于题干要求选最全面、最准确的，因此选D。
第6题：
一棵二叉树有10个度为l的结点，7个度为2的结点，则该二叉树共有_______个结点。
25 解析：在任意一棵二叉树中，度数为0的结点(即叶子结点)总比度为2的结点多一个，因此该二叉树中叶子结点为7+1=8，8+17=25。
第7题：
● 若用n个权值构造一棵最优二叉树 （哈夫曼树）， 则该二叉树的结点总数为 （59） 。
第8题：
设一棵完全二叉树共有700个结点,则在该二叉树中有( )个叶子结点
（提示：1、n1=1,n为偶数；n1=0,n为奇数；
2、n0=n2+1
3、n=n0+n1+n2)
2) 350
第9题：
若一棵二叉树的高度(即层数)为h，则该二叉树()。
A.有2h个结点
B.有2h-1个结点
C.最少有2h-1个结点
D.最多有2h-1个结点
第10题：
