1.有以下递归算法：

   public static int foo(int n){
        if(n<=3){
            return 1;
        }else{
            return foo(n-3)+foo(n-5)+1;
        }
    }

计算foo(foo(9))需要计算几次() foo函数？

A.10
B.11
C.12
D.14

解析：

首先分析函数调用  foo(9);
foo(9) => foo(6)+foo(4)+1
foo(6) => foo(3)+foo(1)+1
foo(4) => foo(1)+foo(-1)+1

因此：
foo(9)=> (foo(3)+foo(1)+1)+(foo(1)+foo(-1)+1)+1

而foo(3)、foo(1)和foo(-1)都是返回 1；因此：
foo(9) = (1+1+1)+(1+1+1)+1 = 7

因此 foo(foo(9)) ==> 等同于 foo(7);

foo(7) => foo(4)+foo(2)+1
foo(4) => foo(1)+foo(-1)+1
foo(2) => 1

因此 foo(7) = (foo(1)+foo(-1)+1)+1+1 
而 foo(1)和foo(-1)都返回1，因此：
foo(7) = (1+1+1)+1+1 = 5;

那么整个这次递归一共执行了多少次foo函数呢？我们分别把两次函数调用展开即可：

-----------------首先计算foo(9)----------------
foo(9) = foo(6)+foo(4)+1 ==>3次
foo(6) = foo(3)+foo(1)+1 ==>2次
foo(4) = foo(1)+foo(-1)+1 ==>2次

-----------------其次计算foo(7)-----------------
foo(7) => foo(4)+foo(2)+1 ==>3次
foo(4) => foo(1)+foo(-1)+1 ==>2次

所以：foo(foo(9))调用foo函数的总次数 = 7次+5次 = 12次

2.有以下阶乘算法

 public static int foo(int n) {
      if (n <= 1) {
          return 1;
      } else {
          return n * foo(n - 1);
     }
 }

该算法的时间复杂度是：()
---------------------------------------
 A.2^n
 B.O(n)
 C.O(nlogn)
 D.O(n^2)

解析：

递归函数时间复杂度=单次递归函数中语句执行次数 * 递归函数的总递归次数

因此，递归算法实现N的阶乘算法：
时间复杂度 = 1*N
          = O(n)

3.某计算机字长64位，其中一位是符号位，63位表示尾数。若用定点整数表示，则能表示的最大正整数是多少？

A.2^64-1
B.2^63-1
C.2^63+1
D.2^62+1

解析：

字长64位的机器字能表示带符号的整数范围为[-2^63, 2^63-1],也就是[ -9223372036854775808, 9223372036854775807],大约是[ -0.9×1020, 0.9×1020]。

因为第一位是符号位，最大正整数就是第一位是0，其余各位都是1。可以理解为比第一位是1，其余都是0的数字少一，因此等于 2^63-1

答案：2^63-1

4.一个栈的入栈顺序是：1,2,3,4,5 ，则栈的不可能的输出顺序是：

A. 54321
B. 12345
C. 45321
D. 43512

解析：

因为栈的特点是后进先出(或者先进后出)，所以这种题目很容易找到规律。
规律就是：就是因为5是最后一个入栈的，因此5一旦出栈，后面就只能都是出栈操作，既然是出栈操作，就必须遵循后进先出。

因此，一看可以看出答案D不合理。

答案：D

5.具有三个节点的二叉树有几种形态？

解析：

送分题，有3个结点的二叉树有以上几种形态。
答案： 5种形态。

6.二叉树节点的中序遍历是ABCDEFG，后序遍历是BDCAFGE,则二叉树的前序遍历顺序是：()

A. EGFACDB
B. EACBDGF
C. EAGCFBD
D. EGACDFB

解析：

二叉树中序遍历(LDR)，简称：左根右，中序遍历后可以得到排序的结果。
二叉树后序遍历(LRD)，简称：左右根。
二叉树前序遍历(DLR), 简称：根左右。

根据已知的中序和后序遍历序列，很容易推导出如下二叉树：

 因此，该二叉树的前序遍历序列为：EACBDGF

7.对长度为N的线性表进行顺序查找，在最坏的情况下所需要的比较次数是：( )

A. N+1
B. N/2
C. (N+1)/2
D. N

解析：

送分题：最坏的情况就是要查找的元素刚好是最后一个，所以比较次数是：N

答案：D