2. 计算机
  3. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是(3)。

一棵完全二叉树上有1001个结点，其中叶子结点的个数是(3)。

admin2013-05-11  72
问题 一棵完全二叉树上有1001个结点，其中叶子结点的个数是(3)。
选项 A、490
B、500
C、501
D、505
答案C
解析 这棵完全--X．树的高度为根据二叉树的性质，从第1层到第 9层共有结点29-1＝511个。第10层全部是叶子结点，因此处于第10层的叶子结点数为 1001-511＝490。同时注意到，第9层有29-1-490/2＝11个叶子结点。因此共有490+11 =501个叶子结点。也可以用另外一种方法来做。设二叉树的总结点数为n，叶子结点数为n0，度为1的结点数为n1，度为2的结点数为n2，根据二叉树的性质有：n0=n2+1，n=n1+2n2+1，于是可得，n=n1+2n0-1，由于在完全二叉树中，度为1的结点总数n1要么为0要么为1，此题中显然为0，这样才能保证等式两边都是奇数，因此1001＝2n0-1，解得n0＝501。
转载请注明原文地址:https://www.kaotiyun.com/show/r2RZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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