计算机二级公共基础知识

Question

关于二叉树真是晕死我了啊!

1、二叉树的第K层上,最多有()个结点?
2、深度为M的二叉树最多有()个结点?

3、一个栈的入栈顺序为ABCDE,则不可能的输出顺序是
A\ DECBA B\DCEAB C\ ABCDE D\EDCBA
不是先进后出后进先出吗?我觉得答案ABC都不大对啊,请高手讲解一下

4、 深度为5的满二叉树中，叶子结点的个数为（）
这到底用的哪个公式啊？

5、对于一个长度为10的排好序的表用二分法查找，若查找不成功，至少需要比较的次数为（）
请详细讲解一下方法！

6、假定根结点的层次是0，含有15个结点的二叉树的最小树深是（）
请详细讲解一下方法！

7、深度为H的二叉树上只有度为0和度为2的结点，则此二叉树中包含的结点个数至少为（）
请详细讲解一下方法！

8、设二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为（）
请详细讲解一下方法！急急急！

Answer 1

答案1：二叉树的第K层上,最多有2的(k-1)次方个结点。（k≥1）
根据其性质：在二叉树的第i层上至多有2的（i－1）次方个结点（i≥1）。
2：深度为M的二叉树最多有｛（2的M次方）减1｝个结点。（M≥1）
根据其性质：深度为K的二叉树至多有｛（2的k次方）减1｝个结点。（k≥1）
8：个人算出的后序遍历结果为DEBFCA,根据先序顺序为根－左－右，中序顺序为左－根－右，找出其中的根A，再依次推出其二叉树结构，再按后序顺序左－右－根，排列出后序遍历结果。
由于个人时间问题，其他题目不便解出，第八题其详细讲解过于复杂，且容易混淆，建议看看《数据结构》（c语言版），其中“树和二叉树”已详细讲解方法，且易懂，我也是自学而已。