2011微软校园实习生笔试题

选择题 10题答对一题4分没答0分打错扣1分

1.二叉树的任意两个节点间有一个唯一路径，求出n个节点的二叉树的最长路径的两个节点的最优算法时间复杂度是多少（编程之美3.8，但是树的边是有权的）

分析：我一开始以为就是求关键路径，其实不是的，求关键路径时会告诉你起点和终点。
思考了一会儿，其实O(n)就够了:
从叶子节点开始，找到每个结点的经过它能得到的最长路径和它的最长分支，
　　　 (node1)
　　e1/ e2
(node2) (node3)
很明显，经过node1的最长路径为node2和node3的最长分支之和再加上两条边（e1和e2）的长度

代码如下：
（该方法实际上不只支持二叉树，
   注意：node.getLength()返回的是从node结点的父结点到node结点的边的长度，
   以上如为例，node3.getLength()返回的是e2的长度。
   全局变量longestPath用来记录当前知的最长路径。
）

public static void cal(MSTreeNode node) {
         List<MSTreeNode> children = node.getChildren();
         int fstl = 0, scndl = 0;
         for (int i = 0; i < children.size(); i++) {
             cal(node.getChildren().get(i));
             int tmp = node.getChildren().get(i).longestBranch
                     + node.getChildren().get(i).getLength();
             if (fstl < tmp) {
                 scndl = fstl;
                 fstl = tmp;
             } else if (scndl < tmp) {
                 scndl = tmp;
             }
         }
         node.longestBranch = fstl;
         node.longestPath = fstl + scndl;
         System.out.println("lb:" + node.longestBranch + "	lp:"
                 + node.longestPath);
         longestPath = Math.max(longestPath, node.longestPath);
     }

分析：编程之美3.8有过解答，时间复杂度为O(v)。但是这里有点不同：树的边有权值。

第一种解法：最大距离的节点一定是叶子节点，首先将二叉树看成一个连通图，首先应该求根节点到所有叶节点的最大距离叶节点A，然后求A到所有其他节点的最大距离。假设要求节点A到其他节点之间的最长路径，题目的转换为求解以A为源点的最长路径。采用单源最短路径（dijkstra）的思想求解。这里要求最长路径，因此，每次选择时，应该从未知最大距离的节点集合中选择最大距离的节点加入已知最大距离的节点集合。如果采用堆结构来维护未知节点到A的最大距离，那么时间复杂度为O（vlogv）。

第二种解法：采用编程之美3.8节的递归方法，递归遍历二叉树一次，得出最大距离，时间复杂度为O（v）

思路：对于一路径，其有两种情况
1. 经过根节点，
2. 不经过根节点，
首先来考虑经过根节点的情况，这样把路径分成两部分，一是左子树起点为根节点的最长路径，
二是右子树起点为根节点的最长路径。
从根节点开始的最长路径可以通过遍历该树的叶子节点得到。

然后再考虑不经过根节点的情况，
不经过根节点，那么最长路径要不存在于左子树，要么存在于右子树。这样，我们就把问题
分解成了两个小问题，即取左子树最长路径和右子树最长路径的最大值。

现在，来分析算法复杂度，不妨记二叉树有n个节点，其复杂度为f(n).
经过根节点的复杂度为O(n)，因为其必须遍历所有叶子节点，因此必须遍历所有的节点。
不经过根节点的复杂度为2*f(n/2)，假设左子树和右子树的节点数目相同。从而得到：
f(n) = O(n) + 2*f(n/2)
= O(nlogn)

2.最大子段和问题的最优算法的时间复杂度

最大子段和问题的动态规划算法

在对于上述分治算法的分析中我们注意到，若记b[j]=max(a[i]+a[i+1]+..+a[j]),其中1<=i<=j,并且1<=j<=n。则所求的最大子段和为max b[j]，1<=j<=n。

由b[j]的定义可易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。故b[j]的动态规划递归式为:

b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。

据此，可设计出求最大子段和问题的动态规划算法如下：

public class SubSegment
{
    public static int maxSum(int[] a)
    {
        int sum=0;
        int b=0;
        for(int i=0;i<a.length;i++)
        {
            if(b>0) 
                b+=a[i];
           else 
                b=a[i];
           if(b>sum)
               sum=b;
        }
        return sum;
    }
}

上述算法只用到了O(n)的时间复杂度和O(1)的空间复杂度。

3.快排的最优、最坏、平均的复杂度

最优、平均：O(logn)，最坏：O(n^2)
4.F(0)= 0;F(1)=1;
F(n)=(F(n-1)+F(n-2))%5
求F(2011)

5.
class A{
    A();
    ~A();
    int a;
    int b;
}
class B{
    B();
    ~B();
    int a;
    char b;
    static char c;
}
class C{
    C();
    virtual ~C();
    int a;
    int b;
}

求sizeof(a) sizeof(b) sizeof(c)

分析：8 8 12

前面介绍过struct的对齐方式，这里又加入了静态变量和虚函数，由于静态变量不在对象中分配空间而在专门的静态区分配空间，因此不占据空间，有虚函数的类会使其对象的开头位置有一个虚函数表的指针，该指针占据4个字节。

7. 二分查找使用什么数据结构（使用顺序结构。。比如数组，且要排好序）

A.栈 B.队列 C.二叉树 D.链表 E.哈希表

8.读程序写运行结果：

#include<iostream>
using namespace std;
int func(int *s,int row,int col)
{
    int count = 0;
    int start = 1;
    int current = start;
    int pending = s[current];
    do{
          int r = current/col;
          int c = current%col;
          int next = c*row+r;
          int tmp = pending;
          pending = s[current];
          s[current] = tmp;
  
          ++count;
          current = next;
    }while(current != start);
    return count;
}
void test()
{
    int s[12];
    int r = func(s,3,4);
    cout<<r<<endl;
}
int main()
{
    test();
    system("pause");
    return 0;
}

运行结果：5

9.平面上有一个100*100的正方形，把两个20*20的正方形放入其中，这两个小正方形重合或交叠的概率是多少
10.已知二叉树后序遍历，选择可能正确的先序遍历

后续遍历的二叉树：DEBFCA，则下列中可能是其前序排列的是？
A：ABFCDE
B：ADBFEC
C：ABDECF
D：ABDCEF
E：none of the above

11. 给定一个整形数组，数组的大小为N，数组内的数的范围为-N到N，问最好的排序时间复杂度是多少?

A O(logN)

B O(N)

C O(NlogN)

D O(N2) /*（代表平方）*/

E 以上都不对

应该是B，采用位图排序，google位图排序

12. MVC模式是现在开发的一种常用设计模式，请问如下可以充当MVC模式中控制器的是？

A CSS

B HTML 模板

C Javascript

D Web Service

E 以上都不是

分析：Web Service可以当作是控制器吧

13. 在编译进程中，会产生Parse Tree的是？

A 语法分析过程

B 语意分析过程

C 汇编代码过程

D 目标代码过程

百度了一下，貌似是在语法分析上，学过编译原理不懂，后面百度链接http://baike.baidu.com/view/29903.htm

14. 寻找最短路径，给定一个还算不是很复杂的图。图不记得了，选项也不记得了。

google 普鲁姆算法克鲁斯卡尔算法

15. 一个节点可以生成生成一种二叉树，两个相同的节点可以生成两种二叉树，三个相同的节点可以生成5种二叉树？那5种呢？

典型的卡特兰数：备选答案忘记了。刚查了一下，42。公式是C(2n, n)/(n+1)

16. 对于一个32位的操作系统来说，那些是正确的？

A. 操作系统可以访问到的物理内存为4G

B. 用户空间可访问的内存为4G

C. 碎片会极大的减缓程序的运行速度

D. 虚拟内存对应的实际内存不一定要连续

我觉得是ACD

17. 给定一个二进制串，001110101如何变成001110010。

选项忘记了，反正就是一个符号运算符，应该是考补码的表示的。还有就是或与运算符。

18. 找出一个数组中，第M大的数，时间复杂度是？

A O(logN)

B O(N)

C O(NlogN)

D O(N2) /*（代表平方）*/

E 以上都不对

编程珠玑上看到了的，就是O（N）

19. 强制转换问题，int i, float f, double d, 下面哪个正确？

A i = (int)(double)i;

B i = (int)(float)i;

C f = -(-f);

D f = (float)(double)f;

E d = (double)(float)d;

编程题：
给出一个一维的点集，求能够包含[n/2]个点的第一个最小区间的左边界和右边界（实际上就是数组）
例如
{5,-3,10，4，-2，-5}
第一个包含[n/2]个点的最小区间就是[-5,-2]
1. 写一个函数，参数是数组及其长度，返回第一个包含[n/2]个点的最小区间的左边界和右边界，不能引用任
何头文件和使用任何库函数，要求完整可运行，效率尽可能高（35分）
2. 给出一些测试用例来进行测试，同时要给出每组测试用例的测试目的，要包括边界情况，错误情况（15分)