广州亿讯公司（国企）部分题目

填空题

1.已知一颗二叉树前序遍历和中序遍历分别为ABDECFGH和DBEACGFH，则该二叉树的后序遍历为（）

解析：

1、前序遍历的第一个节点为根节点，由题中前序遍历可知，A为根节点；

2、中序遍历的根节点前面的节点均为左子树的节点，所以左子树上的节点为DBE；

3、去掉根节点和左子树节点，右子树节点为FGH；

综上可知，二叉树形状如下图：

DEGHFCA

2.下面命令的结果是

echo “hello,GoodJob!”|awk’{print $2}’

3.LinkedList.remove(Object)的时间复杂度 O(1)

ArrayList 是线性表（数组）
get() 直接读取第几个下标，复杂度 O(1)
add(E) 添加元素，直接在后面添加，复杂度O（1）
add(index, E) 添加元素，在第几个元素后面插入，后面的元素需要向后移动，复杂度O（n）
remove（）删除元素，后面的元素需要逐个移动，复杂度O（n）

LinkedList 是链表的操作
get() 获取第几个元素，依次遍历，复杂度O(n)
add(E) 添加到末尾，复杂度O(1)
add(index, E) 添加第几个元素后，需要先查找到第几个元素，直接指针指向操作，复杂度O(n)
remove（）删除元素，直接指针指向操作，复杂度O(1)

4.下面代码中的a的值是（），b的值（）

String content = “0123456789”；

Int rs = content.length(); 10

rs = rs << 8; 10 * 2^8

rs += content.indexOf(“8”); 8+10*2^8

int a = rs & Oxff; 8

Int b = rs >>>8; 10

5.Java中的类的限定词有以下几种：（public），（private），（protect），（default），其中，（public）的限定范围最大。（private）的限定只能内部访问。Java中成员变量用（final）修饰符修饰的是常量。

简答题

1.有两组整数A和B，用什么方法能快速的找出A有而B没有的和B有而A没有的。

利用java语言的特性解决：

算法上优化：

2.Heap和Stack的区别，在JVM中堆和栈有啥区别？

1.heap是堆，stack是栈。

2.stack的空间由操作系统自动分配和释放，heap的空间是手动申请和释放的，heap常用new关键字来分配。

3.stack空间有限，heap的空间是很大的自由区。

在Java中，

若只是声明一个对象，则先在栈内存中为其分配地址空间，

若再new一下，实例化它，则在堆内存中为其分配地址。

4.举例：

数据类型变量名；这样定义的东西在栈区。

如：Object a =null; 只在栈内存中分配空间

new 数据类型();或者malloc(长度); 这样定义的东西就在堆区

如：Object b =new Object(); 则在堆内存中分配空间

3.简述String，StringBuffer，StringBuilder这三个类的区别及应用场合。

最近学习到StringBuffer，心中有好些疑问，搜索了一些关于String，StringBuffer，StringBuilder的东西，现在整理一下。

关于这三个类在字符串处理中的位置不言而喻，那么他们到底有什么优缺点，到底什么时候该用谁呢？下面我们从以下几点说明一下

　　1.三者在执行速度方面的比较：StringBuilder > StringBuffer > String

　　2.String <（StringBuffer，StringBuilder）的原因

　　　　String：字符串常量

　　　　StringBuffer：字符串变量

　　　　StringBuilder：字符串变量

　　　　从上面的名字可以看到，String是“字符串常量”，也就是不可改变的对象。对于这句话的理解你可能会产生这样一个疑问，比如这段代码：

1 String s = "abcd";
2 s = s+1;
3 System.out.print(s);// result : abcd1

　　　我们明明就是改变了String型的变量s的，为什么说是没有改变呢? 其实这是一种欺骗，JVM是这样解析这段代码的：首先创建对象s，赋予一个abcd，然后再创建一个新的对象s用来　　　　执行第二行代码，也就是说我们之前对象s并没有变化，所以我们说String类型是不可改变的对象了，由于这种机制，每当用String操作字符串时，实际上是在不断的创建新的对象，而原来的对象就会变为垃圾被ＧＣ回收掉，可想而知这样执行效率会有多底。

　　　而StringBuffer与StringBuilder就不一样了，他们是字符串变量，是可改变的对象，每当我们用它们对字符串做操作时，实际上是在一个对象上操作的，这样就不会像String一样创建一些而外的对象进行操作了，当然速度就快了。

　　3.一个特殊的例子：

1 String str = “This is only a” + “ simple” + “ test”;
3 StringBuffer builder = new StringBuilder(“This is only a”).append(“ simple”).append(“ test”);

　　　　你会很惊讶的发现，生成str对象的速度简直太快了，而这个时候StringBuffer居然速度上根本一点都不占优势。其实这是JVM的一个把戏，实际上：

　　　　String str = “This is only a” + “ simple” + “test”;

　　　　其实就是：

　　　　String str = “This is only a simple test”;

　　　　所以不需要太多的时间了。但大家这里要注意的是，如果你的字符串是来自另外的String对象的话，速度就没那么快了，譬如：

　　　　String str2 = “This is only a”;

　　　　String str3 = “ simple”;

　　　　String str4 = “ test”;

　　　　String str1 = str2 +str3 + str4;

　　　　这时候JVM会规规矩矩的按照原来的方式去做。

　　4.StringBuilder与 StringBuffer

　　　　StringBuilder：线程非安全的

　　　　StringBuffer：线程安全的

　　　　当我们在字符串缓冲去被多个线程使用是，JVM不能保证StringBuilder的操作是安全的，虽然他的速度最快，但是可以保证StringBuffer是可以正确操作的。当然大多数情况下就是我们是在单线程下进行的操作，所以大多数情况下是建议用StringBuilder而不用StringBuffer的，就是速度的原因。

对于三者使用的总结： 1.如果要操作少量的数据用 = String

　　　　　　　　　　 2.单线程操作字符串缓冲区下操作大量数据 = StringBuilder

　　　　　　　　　　 3.多线程操作字符串缓冲区下操作大量数据 = StringBuffer

当对字符串进行修改的时候，需要使用 StringBuffer 和 StringBuilder 类。

和 String 类不同的是，StringBuffer 和 StringBuilder 类的对象能够被多次的修改，并且不产生新的未使用对象。

StringBuilder 类在 Java 5 中被提出，它和 StringBuffer 之间的最大不同在于 StringBuilder 的方法不是线程安全的（不能同步访问）。

由于 StringBuilder 相较于 StringBuffer 有速度优势，所以多数情况下建议使用 StringBuilder 类。然而在应用程序要求线程安全的情况下，则必须使用 StringBuffer 类。

程序题

1.输入一颗二叉树，求该树的深度。从根节点到叶结点依次经过的结点（含根，叶结点）

的一条路径，最长的长度为树的深度。

解题思路：

①如果一棵树只有一个结点，它的深度为1。

②如果根结点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1；同样如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1。

③如果既有右子树又有左子树，那该树的深度就是其左、右子树深度的较大值再加1。比如在上图的二叉树中，根结点为1的树有左右两个子树，其左右子树的根结点分别为结点2和3。根结点为2的左子树的深度为3，而根结点为3的右子树的深度为2，因此根结点为1的树的深度就是4。

说白了：分两种情况递归求解。

代码：
 public static int GetTreeDepth(BinaryTreeNode root)
    {
        if (root == null)
        {
            return 0;
        }
 
        int left = GetTreeDepth(root.LeftChild);
        int right = GetTreeDepth(root.RightChild);
 
        return left >= right ? left + 1 : right + 1;
    }