剑指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); 
     
    
   

    

     

    
    

     

       }  
     
    
   

    

     

    
    

     

       } 
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

        }
     
    
  
 

2.判断回文串的最大长度。

附 58校招笔试内容总结

    1.根据二叉树的先序遍历、后序遍历，得出中序遍历结果。

    已知前序遍历序列和中序遍历序列，可以唯一确定一颗二叉树。

      已知后序遍历序列和中序遍历序列，可以唯一确定一颗二叉树。

      已知前序遍历序列和后序遍历序列，是不能确定一颗二叉树的。

    2.各种排序算法中时间复杂度为O(nlogn)，且稳定的排序算法

      参考博文:http://blog.csdn.net/sunhuaqiang1/article/details/52060981

3.编程题。斗地主找顺子，随机抽取5张牌，若5张牌为连续，则为顺子。大小王为任意数，A为0，J,Q,K分别为11，12，13.                                                                   

    4.突然想起菜鸟网络面试时面试官所问的问题:快排与冒泡排序算法的对比，时间复杂度的含义。

    在内排序中，主要进行两种操作:比较和移动。其中时间复杂度由比较和移动次数决定。

      原来当时自己的回答是如此的不靠谱啊！

美文美图

文章来源: shq5785.blog.csdn.net，作者：No Silver Bullet，版权归原作者所有，如需转载，请联系作者。

原文链接：shq5785.blog.csdn.net/article/details/52487704