2011微软校园实习生笔试题-白红宇

2011微软校园实习生笔试题

阅读量：6473 次

发布时间：2019-06-23

本文共 4823 字，大约阅读时间需要 16 分钟。

选择题 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
     
       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 + "\tlp:"                 + 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
     
      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

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

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

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

8.读程序写运行结果：

#include
     
      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<
      
       <

运行结果：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)