1、
若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数？
答案：11个
第一种解法：
二叉树的性质：度为0的节点数等于度为2的节点数+1
第二种解法：
所有点的入度和出度的和相等，下面等式左边为出度，右边为入度（根节点入度为0，其他节点入度为1）
10*2+5*1=10+5+x-1
x等于11
2、
假设某棵二叉查找树的所有键均为1到10的整数，现在我们要查找5。下面____不可能是键的检查序列。
A、10,9,8,7,6,5
B、2,8,6,3,7,4,5
C、1,2,9,3,8,7,4,6,5
D、2,3,10,4,8,5
E、4,9,8,7,5
F、以上均正确
答案：B
二叉排序树，或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根节点点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
因此，在查找时，对任意点，后面的元素要么全部大于它，要么全部小于它。很显然，B不符合。
3、
有n(n0)个分支结点的满二叉树的深度是？
答案：log2(n+1)+1，即以2为底（n+1）的对数+1
分支节点：树中除了叶子节点外的其他节点就是分支节点。
第一种解法：
假设满二叉树高为h，那么结点总数为2^h-1，叶节点数为2^(h-1)。
2^h-1-2^(h-1)=n
2^(h-1)=n+1
h=log2(n+1)+1
第二种解法：
因为有n个分支结点，所以有n+1个叶子节点，总结点数为2n+1。设树高h，则有
2^h-1=2n+1
2^h=2n+2
h=log2(2n+2)=log2(n+1)+1
4、
在一个有8个int数据的数组中，随机给出数组的数据，找出最大和第二大元素一定需要进行几次比较？
答案：9次。
假设这8个数为A，B，C，D，E，F，G，H。如果是按最简单的求最大值的方法：每个元素与第一个元素逐一比较，求第二大元素时不方便。所以我们换一种思路：
8个元素两两比较，得出四个较大值，假设为A，C，E，G。这四个元素再进行两两比较，得出两个更大值，假设为A，E。那么得出最大值只需要比较A和E的值便可以了，假设为A。
求第二大元素：由上面，我们已经得出了A为最大值，那么第二大元素就从与它比较过的元素中寻找就可以了，为B，C，E。在这三个元素中找最大值只需两次比较。
让我们算一下总的比较次数：求出四个较大值（4次）+求出两个更大值（2次）+求出最大值（1次）+三选一（2次）=9次
欢迎留言交流！
王与坐骑觉得文章不错就赏个鸡腿吧
赞赏
人赞赏