剑指Offer(Java岗)——CVTE校招笔试题+知识点总结

2016.9.3 19:00参加CVTE笔试，笔试内容如下:

需要掌握的知识:Linux基本命令、网络协议、数据库、数据结构。

选择题

1.36进制转换(0~9， A~Z)：28045707425转换结果为...P

2.已知二叉树的节点数，求树的最低深度。

考察二叉树中树的深度与节点数目的关系

二叉树的性质

性质1 在二叉树的第i层上至多有2(i-1)个节点（i>=1）.

性质2 深度为k的二叉树至多有2k-1个节点(k>=1).

性质3 对任何一棵二叉树T，若叶子节点数为m,度为2的节点数为n,则m=n+1.

性质4 具有n个节点的完全二叉树的深度为log2n(向下取整)+1。

性质5：如果对于一棵有n个节点的完全二叉树(其深度depth=log2n+1下取整)的节点按层序编号(从第一层到第depth层，每层从左到右)，对任一节点i（1 <= i <= n）：
1.如果i=1,则节点i是二叉树的根，无双亲；如果i>1,则其双亲节点是i/2（下取整）。
2.如果2i>n,则节点i无左孩子(节点i为叶子节点)；否则其左孩子是节点2i;
3.如果2i+1>n，则节点i无右孩子；否则其右孩子节点为2i+1。

一棵深度为k且有2k-1个结点的二叉树称为满二叉树。

编程题

1.全排列

 public class FullPermutation {/*** @author SHQ*/  public static void main(String[] args) {List<Integer> s = new ArrayList<Integer>();  List<Integer> rs = new ArrayList<Integer>();for(int i = 1; i <= 3; i++)  s.add(i);pl(s,rs);}public static void pl(List<Integer> s,List<Integer> rs){// 递归出口if(s.size()==1){  rs.add(s.get(0));  System.out.println(rs.toString());  rs.remove(rs.size()-1);  }else{for(int i = 0; i < s.size(); i++){rs.add(s.get(i));   List<Integer> tmp = new ArrayList<Integer>();  for(Integer a:s)tmp.add(a);tmp.remove(i);pl(tmp,rs);rs.remove(rs.size()-1);      }  }                     }}