牛客刷题总结

1.某火车站要通过一条栈道（先进后出）来调换进入车站的列车顺序，若进站的列车顺序为A、B、C，则下列哪个出站顺序不可能？（）

答案：CAB
第一种方法，根据栈的特性先入先出的顺序，发现当C先出栈的时候只有CBA这一种可能性
第二种方法，参考 https://www.cnblogs.com/hapjin/p/5758083.html 的解题方法，发现出栈的规律
对于出栈序列中的每一个数字，在它后面的、比它小的所有数字，一定是按递减顺序排列的。因此我设ABC分别为1、2、3，CAB的顺序为3 1 2，对于3来说比他小的数字是按照先递减再递增的顺序排列的，故该选项错误。

2.设某棵二叉树的高度为 10 ，则该二叉树上叶子结点最多有（ ）。

答案：512
高度为H的满二叉树叶子结点个数为2^(H - 1)
结点个数为2^H - 1

具有4个顶点的无向图至多应有（ ）条边。

答案：6条
具有N个顶点的无向图之多有N(N-1)/2条边，至少有N-1条边
相当于在4个顶点中随意选两个的组合数C42

对于有n个结点的二叉树,其高度为()

答案：不确定
满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树求节点公式:[log2n]+1其中log2n向下取整
满二叉树公式：N = 2^h - 1
题目中没有限定是满二叉树，因此层数不确定