近几年微软笔试题汇总分类解析

作者：寒小阳

时间：2013年10月。

出处：http://blog.csdn.net/han_xiaoyang/article/details/12616423。
声明：版权所有，转载请注明出处，谢谢。

        这里对2010年至今的微软笔试题做了一个汇总和分类，然后进行了解答和分析，每一类题中涉及到的知识点和方法在很多别家公司的笔试面试中也有用，希望下面的内容能在大家找工作的时候给大家一些帮助。

1、数组，排序相关

1、合并两个已排好序的数组在最坏情况下需要比较多少次？ （2010年9月校招考题）

(A)2n (B)2n-1 (C)2n+1 (D)2n-2 (E)None of above

分析：最后所生成的数组元素个数为2n个. 最坏情况为: 每比较一次,只确定一个元素的位置(最后一次比较确定两个元素的位置,即倒数第一个和倒数第2个),所以总的最坏比较次数为2n-1.

2、编程题   （2010年9月校招考题）

        一个rotated sorted array是一个在某处交换了元素的sorted array，例如，rotated sorted array[13, 27, 37, 2, 3, 5]是从sorted array[2, 3, 5, 13, 27, 37]变换而来的，这个sorted array是以增序排好序的。

         现在需要计算给定值在rotated sorted array中的索引。例如，27在rotated sorted array[13, 27, 37, 2, 3, 5]中的索引是2。注意：如果想得满分，程序的时间复杂度需要小于O(n)。

分析：旋转数组求下标问题。

     如果数组是有序数组，进行二分查找的时间复杂度是O(logN)。在旋转数组中，二分查找的情况稍微复杂一些，如下图所示，数组平分后一半是有序数组，一半仍是旋转数组。

   确定下次二分查找在前半段区间还是后半段区间进行。
仔细分析该问题，可以发现，每次根据low和high求出mid后，mid左边（[low, mid]）和右边（[mid, high]）至少一个是有序的。
     a[mid]分别与a[left]和a[right]比较，确定哪一段是有序的。
如果左边是有序的，若x<a[mid]且x>a[left], 则right=mid-1；其他情况，left =mid+1；
如果右边是有序的，若x> a[mid] 且x<a[right] 则left=mid+1；其他情况，right =mid-1；

代码如下：

int binary_search_rotate_arry(int *a, int n, int x)
{
    int low = 0, high = n - 1, mid;
    while(low <= high)
    {
        mid = low + ((high - low) >> 1);
        if(a[mid] == x)
            return mid;
        if(a[mid] >= a[low])
        {//左边有序
            if(x < a[mid] && x >= a[low])
                high = mid - 1;
            else
                low = mid + 1;
        }
        else //右边有序
        {
            if(x > a[mid] && x <= a[high])
                low = mid + 1;
            else
                high = mid - 1;
        }
        //cout << low << " " << mid << " " << high << endl;
    }
    return -1;
}

3、一个文件中有多行信息，每一行信息中，第一个为一个key，后面用空格间隔若干symbol，例如： 

B A C D E（每一行中的一个symbol至多出现一次，且不与key重复），表示B<A B<C B<D B<E关联。 

若一行中只有一个值，如 C 则表示无关联。 

现在求写出一个算法，判断一个文件下的所有行中所包含的关联，能否囊括所有元素的关联，使之形成一个sort链，达到例如：A<B<C<D的效果。 

例1 

input: 

A B C 

B C 

C 

（means:A<B A<C B<C） 

output： 

It can be sorted determine. 

例2 

input: 

A B 

B A 

C 

（means:A<B B<A） 

output: 

It can't be sorted determine. 

例3 

input: 

A B 

A C 

C 

(means:A<B A<C) 

output: 

It can't be sorted determine.

分析：貌似是拓扑排序的一道题，这个博主不懂，大家补充，多谢。

4、数组中最大连续子段和问题，求其最优算法的时间复杂度   （2011年4月实习招聘考题）

分析：典型的动态规划问题

若记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。

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

/**********************************************************************
动态规划求最大子序列和
**********************************************************************/
int Maxsum(int * arr, int size)
{
    int maxSum = -INF; //很重要，初始值赋值为负无穷大
    int sum = 0;
    for(int i = 0; i < size; ++i)
{
//小于0则舍弃
        if(sum < 0)
        {
            sum = arr[i];
        }else
        {
            sum += arr[i];
        }
//比现有最大值大，则替换
        if(sum > maxSum)
        {
            maxSum = sum;
        }
    }
    return maxSum;
}

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

5、快排的最优、最坏、平均的复杂度  （2011年4月实习招聘考题）

分析：基础题。最优、平均：O(n log n)，最坏：O(n^2)

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

A O(logN)

B O(N)

C O(NlogN)

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

E 以上都不对

分析： 1）利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：

   1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；

   2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)

        2）利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)

7、给出一个一维的点集，求能够包含[n/2]个点的第一个最小区间的左边界和右边界（实际上就是数组）。例如{5,-3,10，4，-2，-5}，第一个包含[n/2]个点的最小区间就是[-5,-2]。（2011年4月实习招聘考题）

分析：这道题目让求解的是前n/2个数，也就是说，我们找到中位数和最大(小)元素即可。而求中位数的方法，在数组有序的时候显然是二分，但这里的数组是无序的，恩，要时刻记得快排的partition算法，在很多时候很有帮助。代码如下：

int Partition(int* A, int begin, int end)
{
//分治元素
int X = A[end];
//A[begin]...A[i-1]<X
int i=begin;
//A[j]...A[end]>=X
int j=end;
//循环开始前A[j]是等待被填充的元素，该元素已被保存到X
while (i<j)
{
//从前面开始找到小于X的数
while (A[i]<X && i<j)
i++;
//A[j]被填充，A[i]等待被填充
if (i<j)
A[j] = A[i];
while(A[j]>=X && i<j)
j--;
//A[i]被填充，A[j]等待被填充
if (i<j)
A[i]=A[j];
}
A[i] = X;
return i;
}
/*
返回中位数元素
@para:
A[begin...end]为所求数组
middle_index 为中位数的索引
middle_element为中位数元素，返回用
*/
void FindMiddleElement(int* A,int begin ,int end,
  int middle_index,int& middle_element)
{
if (!A || begin>end)
{
return;
}
int split_pos = Partition(A,begin,end);
if (split_pos == middle_index)
{
middle_element = A[split_pos];
return; 
}
FindMiddleElement(A,begin,split_pos-1,middle_index,middle_element);
FindMiddleElement(A,split_pos+1,end,middle_index,middle_element);
}

8、N个数，范围从-N到N,可能重复，排序时间复杂度最好能到多少？（2011年9月招聘考题）

分析：答案是O(n)，使用计数排序和位图排序，桶排序都可以达到这个时间复杂度。

9、假设一个长度为80的数组选择排序已完成主循环32次迭代。现在能保证有多少元素是在他们最终的位置？（2012年4月实习生招聘考题）

A、16    B、31   C、32     D、39   E、40

分析：这个不用过多解释吧，对选择排序不了解的详见找工作知识储备(3)---从头说12种排序算法：原理、图解、动画视频演示、代码以及笔试面试题目中的应用

10、下列哪项陈述是对的？（2012年4月实习招聘考题）

A、我们能从一颗二叉树的先序遍历序列和中序遍历序列，确定这颗二叉树。

B、我们能从一颗二叉树的先序遍历序列和后序遍历序列，确定这颗二叉树。

C、近乎排序的数组，插入排序可以比快排更有效。

D、假设T(n)是解决n个元素的问题时候的运行时间，T(N)= O(1)如果n = 1；T(n)＝2×T(N/2)+ O(n)当n＞1；则T(n)是O(nlgn)

E、上述都不对

11、下面哪项(些)陈述是对的？（2012年4月实习招聘考题）

A、插入排序和冒泡排序在大型数据集下效率很低。

B、快速排序是在最坏情况下比较了O（N^2）次。

C、有一序列7,6,5,4,3,2,1。如果使用选择排序（升序），交换操作次数是6

D、堆排序使用两个堆操作：插入、堆调整

E、上述都不对

分析：常规题，对各种排序算法要熟悉

12、最长递增子序列（LIS）是一个序列满足元素的值不断增加的子序列中最长的序列。

例如，里{ 2,1,4,2,3,7,4,6 }是{ 1,2,3,4,6 }，以及LIS的长度为5。

考虑具有n个元素的数组，则得到LIS的长度的最低的时间复杂度和空间复杂度是多少？（2012年4月实习招聘考题）

A、Time : N^2 , Space : N^2
B、Time : N^2 , Space : N
C、Time : NlogN , Space : N
D、Time : N , Space : N
E、Time : N , Space : C

分析：详见找工作知识储备(2)---数组字符串那些经典算法：最大子序列和，最长递增子序列，最长公共子串，最长公共子序列，字符串编辑距离，最长不重复子串，最长回文子串

13、对于以下的定义（2013年4月实习招聘考题）

int [][] myArray3 =new int[3][]{
  new int[3]{5,6,2},
  new int[5]{6,9,7,8,3},
  new int[2]{3,2}};

则myArray3[2][2]返回的是?

    A. 9

    B. 2

    C. 6

    D. overflow

分析：越界导致overflow

14、以下哪些排序方法是稳定的？ （2013年4月实习招聘考题）

A. 冒泡排序

B. 快速排序

C. 堆排序

D. 归并排序

E. 选择排序

15、快速排序的最好时间复杂度是?（2013年9月招聘考题）

A、O(lgn)
B、O(n)
C、O(nlgn)
D、O(n*n)

分析：好吧，这一题就不解释了，大家都知道的。

2、链表相关

1、下列程序的输出是什么？（2012年4月实习招聘考题）

#include<iostream>
using namespace std;
struct Item
{
char c;
Item *next;
};
Item *Routine1(Item *x)
{
Item *prev = NULL,
*curr = x;
while(curr)
{
Item *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
void Routine2(Item *x)
{
Item *curr = x;
while(curr)
{
cout<<curr->c<<" ";
curr = curr->next;
}
}
int main(void)
{
Item *x,
d = {'d' , NULL},
c = {'c' , &d},
b = {'b' , &c},
a = {'a' , &b};
x = Routine1( &a );
Routine2( x );
return 0;
}

A、 c b a d

B、 b a d c 

C、 d b c a 

D、 a b c d

E、 d c b a

分析：原程序将链表进行翻转了

2、链表和数组的区别是? （2013年4月实习招聘考题）

A. Search complexity when both are sorted

B. Dynamically add/remove

C. Random access efficiency

D. Data storage type

分析：之前看这道题的D选项是有争议的，我这里根据自己的理解还是选上吧

3、给定一个链表L: (L0 , L1 , L2...Ln-1 , Ln). 写程序使得链表中的节点变为(L0 , Ln , L1 , Ln-1 , L2 , Ln-2...).（2013年9月招聘考题）

struct Node
{
int val_;
Node* next;
};

要求：

1）空间复杂度O(1)  2）节点中只有next域可以改动

分析：其实就是把链表的后半部分翻转，之后再对前半部分和后半部分做一个交叉合并就可以了吧。代码如下：

//完成对头为head的链表的反转
Node* ReverseList(Node*& head)
    {
        if ( (head == 0) || (head->next == 0) ) return;// 边界检测
        Node* pNext = 0;
        Node* pPrev = head;// 保存链表头节点
        Node* pCur = head->next;// 获取当前节点
        while (pCur != 0)
        {
            pNext = pCur->next;// 将下一个节点保存下来
            pCur->next = pPrev;// 将当前节点的下一节点置为前节点
            pPrev = pCur;// 将当前节点保存为前一节点
            pCur = pNext;// 将当前节点置为下一节点
        }
        Return Pcur;
    }
//查找中间节点，使用一快一慢两指针，快指针一次走两步，慢指针一次走一步，最后返回慢指针
.Node * GetMiddleNode(Node*& head)
{
if ( (head == 0) || (head->next == 0) ) 
      return NULL;
Node* pFast = head;//快指针
    Node* pSlow = head;// 慢指针
while（pFast ！= Null && pFast->next != Null）
{
    pFast = pFat->next->next;
        pSlow = pSlow->next;
}
return pSlow;
}
// 交叉合并A和B两链表
Node* Merge(Node* & A,Node* & B)
{
     Node *p,*q,*s,*t;
     p=A->next;
     q=B->next;
     while(p&&q)
     {
       s=p->next;
       p->next=q;
       if(s)
       {
            t=q->next;
            q->next=s;
       }
       p=s;
       q=t;
     }
     return A;
}
//完成题目要求的顺序调整
Node* ReorderList(Node* pHead)
{
Node *pMiddle, *pEnd, *nHead;
    pMiddle =  GetMiddleNode(Node*& head);
pEnd = ReverseList(pMiddle);      //后半部分反转
nHead = Merge(pHead , pMiddle);    //链表交叉归并
return nHead;
}

3、树，遍历

1、二叉树的任意两个节点间有一个唯一路径，求出n个节点的二叉树的最长路径的两个节点的最优算法时间复杂度是多少 （2011年4月实习招聘考题）

分析：O(n)就够了:

从叶子节点开始，找到每个结点的经过它能得到的最长路径和它的最长分支，

　　　 (node1)

　　e1/         \e2

  (node2)    (node3)

很明显，经过node1的最长路径为node2和node3的最长分支之和再加上两条边（e1和e2）的长度。

对这道题，多说两句，编程之美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、后续遍历的二叉树：DEBFCA，则下列中可能是其前序排列的是？（2011年4月实习招聘考题）
A：ABFCDE
B：ADBFEC
C：ABDECF
D：ABDCEF
E：none of the above

3、一颗3阶B树有2047个key-words，那这颗树的高度最大为多少？（2012年4月实习招聘考题）

A、11     B、12     C、13    D、14
分析：m阶B-树的根节点至少有两棵子树，其他除根之外的所有非终端节点至少含有m/2(向上取整)棵子树，即至少含有m/2-1个关键字。要想让3阶的B-树达到最大的高度，那么每个节点含有一个关键字，即每个节点含有2棵子树，也就是所谓的完全二叉树了，这样达到的高度是最大的。即含有2047个关键字的完全二叉树的高度是多少。很明显求得高度是11。

4、二叉树的先序遍历结果为abcdefg，则它的中序遍历结果可能是？（2012年9月招聘考题）

A、abcdefg
B、gfedcba
C、efgdcba
D、bceadfg
E、bcdaefg

分析：几种遍历方式，年年考，要特别注意。

5、有n个元素的完全二叉树的深度是：（2012年9月招聘考题）

A. D(n)=log2(n)

B. D(n)=1+log2(n)

C. D(n)=n+log2(n)

D. D(n)=1+n*log2(n)

分析：普遍来说，认为根结点深度为1，所以深度=1+ log2(n)

6、我们在得知下列哪些选项的条件下可以还原二叉树？

A. 先序遍历和中序遍历

B. 先序遍历和后序遍历

C. 中序遍历和后序遍历

D. 后序遍历

分析：一定要有一个中序遍历，才便于区分左侧和右侧部分。先序遍历和后续遍历无法确定一颗二叉树。

7、50 万个学生信息，其中有 id 和 name 字段，id 是 7为数字，name 是字符串；问如果要查询 1) 通过 name 查 id 2) 通过 id 查 name 那么，合适的数据结构是 ?（2013年9月招聘考题）

A. 1）叶子节点为hash(100 bucket)的树 2）叶子节点为链表的树

B. 1）叶子节点为链表的树 2）数组

C. 1）叶子节点为链表的树 2）hash(10000 bucket)

D. 1）排序链表 2）数组

分析：名字可能重复，而编号不会重复。查找名字用二叉查找树，找到节点后，会有若干个编号，所以每个节点存一个单链表。如果查找名字，编号是无重复的，有50万个，10000个桶不够用，直接用数组比较好。

4、堆栈性质

1、有一个序列的n个数字为1,2,3，……，n，现有一个栈最多可以保持M个数。将N个数依次进栈后，随机弹出生成序列。例设n为2 ，m为3，输出序列可以是12或21，所以我们得到了2种不同的序列。设n是7，和m是5，请选择该栈的可能出栈序列。（2012年4月实习招聘考题）

A、1,2,3,4,5,6,7
B、7,6,5,4,3,2,1
C、5,6,4,3,7,2,1
D、1,7,6,5,4,3,2
E、3,2,1,7,5,6,4

分析：这道题目不仅在微软笔试出现过，也被很多别家公司当做笔试题考过，甚至出现过相类似的算法大题。它包含一个隐藏的出栈顺序规则：对于编号较小的出现在较大的编号后面时一定是降序排列的，如：1,4,3,2是合理的，而1,4,2,3就是一个错误出栈序列。这道题还需要考虑的一个问题是栈的大小是有限的，连续的降序段的长度不能大于5。综合这两点可选出答案。

2、下面哪一种操作不是stack的基本操作？（2012年9月招聘考题）

A.  入栈

B.  出栈

C.  检查是否为空

D.  排序栈中元素

3、以下这些序列中，哪些不可以写作一个二叉搜索树后序遍历的结果？（2013年9月招聘考题）

A、1,2,3,4,5
B、3,5,1,4,2
C、1,2,5,4,3
D、5,4,3,2,1

分析：根据左右根的顺序。最后一个元素一定可以将前n-1个数分成前后两部分，一部分比它大，一部分比它小。B无法满足这种性质。

5、字符串与指针

1、读程序写运行结果   （2011年4月实习招聘考题）

#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

2、拷贝字符串当src和dest有overlap时，使用哪个是安全的，memcpy还是memmove？（2011年9月招聘考题）

分析：几个涉及到拷贝字符串的函数的介绍如下

   char *strcpy(char *dest,char *src);  

   功能：把src所指由NULL结束的字符串复制到dest所指的数组中

   说明:src和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串。

   返回指向dest的指针

  

   void *memcpy(void *dest,void *src,unsigned int count);

   功能：由src所指内存区域复制count个字符串到dest所指内存区域.

   说明：src和dest所指内存区域不能重叠，函数返回指向dest的指针.

      

   void *memmove (void *dest, const void *src, size_t n);

   从src所指向的对象复制n个字符到dest所指向的对象中。返回指针为dest的值。不会发生内存重叠。

3、下列程序的运行结果是什么？（2012年4月实习招聘考题）

char *f(char *str , char ch)
{
char *it1 = str;
char *it2 = str;
while(*it2 != '\0')
{
while(*it2 == ch)
{
it2++;
}
*it1++ = *it2++;
}
return str;
}
int main(void)
{
char *a = new char[10];
strcpy(a , "abcdcccd");
cout<<f(a,'c');
return 0;
}

A、abdcccd
B、abdd
C、abcc
D、abddcccd
E、Access violation

4、有长度为n的字符串，假设字符串的每个字符都不一样，有多少不同的子串？（2013年9月招聘考题）

 A. n+1

 B. n^2

 C. n(n+1)/2

 D. 2^n-1

 E. n!

6、递归，菲波拉契数列

1、F(0)= 0;F(1)=1; F(n)=(F(n-1)+F(n-2))%5， 求F(2011)  （2011年4月实习招聘考题）

分析：循环数组，写几个就知道了，不过这里循环的长度确实很长。

0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 ...

(2011+1)%20 = 12 ， F(2011) = 4

2、考虑以下计算e的指数次方的递归函数。（2012年4月实习招聘考题）

int power(int b , int e)
{
if(e == 0)
return 1;
if(e % 2 == 0)
return power(b*b , e/2);
else
return b * power(b*b , e/2);
}

Asymptotically（渐进地） in terms of the exponent e,the number of calls to power that occur as a result of the call power(b,e) is

A、logarithmic
B、linear
C、quadratic
D、exponential

分析：是对数次的。

2、在计算 f(10)的过程中调用函数f()的次数是? （2013年9月招聘考题）

int f(int x)
{
if(x <= 2)
return 1;
return f(x - 2) + f(x - 4) + 1;
}

A、14
B、18
C、20
D、24
E、None of the above.

分析：这道题目博主画了一颗二叉树，数了一下，貌似是14

7、函数、指针与内存管理

1、以下代码执行后的结果是什么？（2012年4月实习招聘考题）

void main()
{
int i = 11;
int const *p = &i;
p++;
printf("%d",*p);
}

A、11
B、12
C、Garbage value
D、Compile error
E、None of above

分析：显然这时候p指向的是未知的内容。

2、以下哪段(些)代码是正确的？C  （2012年4月实习招聘考题）

A  

int f()
{
int *a = new int(3);
return *a;
}

B

int *f()
{
int a[3] = {1,2,3};
return a;
}

C

vector<int> f()
{
vector<int> v(3);
return v;
}

D

void f(int *ret)
{
int a[3] = {1,2,3};
ret = a;
return ;
}

E 都不对

分析：在函数体内，栈上申请的内存，不能返回指针。详见找工作笔试面试那些事儿(3)---内存管理那些事

3、下面哪个是函数指针的声明 ?（2013年9月招聘考题）

A. void *f(int);

B. int (*f)();

C. void (*f(int, void(*)(int)))(int);

D. void (*(*f)(int))();

分析：自己看看函数指针的定义吧。A是返回指针的函数，D是一个返回函数指针的的函数声名。

8、图

1、求下图中S到T的最短路径（2013年4月实习招聘考题）

A. 17

B. 18

C. 19

D. 20

E. 21

分析：反正博主是直接数的

2、下面图的深度优先遍历可能的遍历结果有 :（2013年9月招聘考题）

A. BADECF

B. BADEFC

C. BCAFDE

D. BCFEDA

E. BFDECA

分析：通俗的话讲就是，深搜是每次走到底，无路可走，再重选节点走。

9、类与继承

看程序写结果    （2010年9月校招考题）

class Base 
{ 
protected: 
    int m_value; 
public: 
    Base(){ 
        m_value = 0; 
    } 
    virtual int getValue(){ 
        return --m_value; 
    } 
}; 
class Derived:public Base 
{ 
public: 
    virtual int getValue(){ 
        return ++m_value; 
    } 
}; 
int main() 
{ 
    Derived *pDerived = new Derived(); 
    Base *pBase = pDerived; 
    Base &base = *pBase; 
    pDerived->getValue(); 
    pBase->getValue(); 
    base.getValue(); 
    printf("%d,", pDerived->getValue()); 
    printf("%d,", pBase->getValue()); 
    printf("%d/n", base.getValue()); 
    return 0; 
}

分析：4,5,6

2、下列程序输出的结果是？（2013年9月招聘考题）

class C
{
public:
    long    a;
};
class D:public C
{
public:
    long b;
};
void seta(C *data, int index)
{
    data[index].a = 2;
}
int main()
{
    D data[4];
    cout<<sizeof(C)<<","<<sizeof(D)<<endl;
    for(int i=0;i<4;++i)
    {
        data[i].a = 1;
        data[i].b = 1;
        seta(data,i);
    }
    for(int i=0;i<4;++i)
    {
        cout<<data[i].a<<data[i].b;
    }
    return 0;
}

A. 11111111       B. 12121212             C. 11112222         D.22221111

分析：seta中，参数是基类C类型的指针，然后移动指针取对象并赋值，但是main中往函数seta中传递的是派生类的对象数组的起始地址。

函数seta中，data[index].a=2；

等价于：(*(data+index)).a=2；

这里的data类型是参数列表中的C*，所以如果传进来的data是派生类对象数组的起始地址，那么指针data+index已经不再指向第index个对象了。原因是C和D所占内存不同。

10、数据类型及转换

1、int i, float f, double d, 下面哪个正确？（2011年4月暑期实习招聘考题）

A i = (int)(double)i;

B i = (int)(float)i;

C f = -(-f);

D f = (float)(double)f;

E d = (double)(float)d;

2、有两个32bit的数A、B，使用下面方式得到32bit的数C、D。哪一种可以使用C、D得到A、B的值（2012年4月实习招聘考题）

A. C=（int32）(A+B),D=(int32)(A-B)

B. C=（int32）(A+B),D=(int32)((A-B)>>1)

C. C=（int32）(A+B),D=B

D. C=（int32）(A+B),D=(int32)(A+2*B)

E. C=（int32）(A*B),D=(int32)(A/B)

分析：最主要需要考虑的是数据类型越界问题。

1）A选项假设A>0,B>0;C可能越界使得C=A+B-2^32举个反例：A=B=2^31-1 C=-2,D=0;A=B=-1,C=-2,D=0

2）B选项我们可以考虑Q=A+B, C=Q+B ,D=Q跟C的那个一样，就能求出Q与B Q=A+B，B又已知A可求
3）C选项不管C是否越界总能得到A=C-D, B=D
4）D选项：A=B=-1 A=B=2^31-1
5）E选项：A=B=2^15, A=B=2^31

11、sizeof

读下列程序，写出要求的结果   （2011年4月实习招聘考题）

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)

分析：sizeof的题目各大公司招聘题年年出，答案为sizeof(a)=8很容易理解，sizeof(b)=8因为内存对齐，详见http://blog.csdn.net/han_xiaoyang/article/details/11596001 静态变量不在对象中分配空间而在专门的静态区分配空间，因此不占据空间，sizeof(c)=12因为有虚函数的类会使其对象的开头位置有一个虚函数表的指针，该指针占据4个字节。

12、位运算相关、补码反码

1、如何快速判断一个数是否是2的n次方。（2011年9月招聘考题）

分析：判断x&(x-1)是否等于0。

2、二进制数01011001和0111001相乘再与1101110相加的结果是下面的？（2012年4月实习招聘考题）

A、0001010000111111

B、0101011101110011

C、0011010000110101

D、0101010100110101

分析：木有什么非常好的办法，可以先转换成10进制，算完了再转换回二级制。

2、假设x和y是整型数，则以下那个表达式返回两个数中较小的数？（2012年4月实习招聘考题）

A、y^((x^y) & -(x<y))

B、y^(x^y)

C、x^(x^y)

D、(x^y)^(y^x)

E、None of above

分析：对于A选项，我们分两种情况讨论。x<y的时候，-（x<y）即-1的补码形式就是全1（111111），（x^y）&-（x<y）== x^y。x>y的时候，-（x<y）即0的补码形式就是全0（000000），（x^y）&-（x<y）== 0

3、32位有符号数x，F=x/2，G=x>>1，在哪些情况下F不等于G？（2013年4月实习招聘考题）

A. There is a compiler error

B. X is odd

C. X is negative

D. F - G = 1

E. G - F = 1

13、二分

1、二分查找使用什么数据结构 （2011年4月实习招聘考题）

A.栈 B.队列 C.二叉树 D.链表 E.数组

分析：使用顺序结构，比如数组，且要排好序，容易对半查找。

14、数学题(概率，排列组合等)

1、平面上有一个100*100的正方形，把两个20*20的正方形放入其中，这两个小正方形重合或交叠的概率是多少？（2011年4月实习招聘考题）

   重合的概率应该是面积比，(20*20)/(100*100)，相交的情况大家来讨论一下。

2、99!的阶乘结果末尾0的个数？（2011年9月招聘考题）

分析：任何带0的数之所以能产生尾数0是因为它能拆出一个5和一个2来，99!中显然包含2的个数多于5，所以看5的个数即可，25可以解析出两个5来，99/5 = 19， 19/5 = 3， 3/5 = 0，所以99末尾0的个数为22 

3、excel中列名的规则是A,B,.....Z,AA,AB.....AZ,BA......ZA........ZZ,AAA,AAB........请问10000列的列名？（2011年9月招聘考题）

答案：看似毫无规律，其实本质是一道数制转换的题目，26个字母，进制为26。答案为EKG。

4、对一个5位数字180度旋转后得到一个新的5位数，两数之差为78633，原始5位数为多少？（2012年4月实习招聘考题）
A、60918   B、91086    C、18609    D、10968    E、86901

分析：把答案代入验证即可

5、假设一个完整的扑克牌有52张牌，.2黑色套装（黑葵和梅花）和2红色西装（方块和红心）。如果给你一幅完整的牌，和半副牌（1红色外套和1黑色西装），则两种情况下抽两张牌都是红色的概率是多少？（2012年4月实习招聘考题）

A. 1/2,1/2            

B. 25/102,12/50               

C. 50/51, 24/25             

D. 25/51,12/25          

E. 25/51,1/2

6、1,2,3,…1000 一共出现了多少个0  （2012年9月招聘考题）
A、189
B、191
C、193
D、195

分析：博主一直觉得这道题木有答案，因为我算的是192，大家算算？

7、15个球放在4个袋子中，每个袋子至少有一个球且每个袋子中球的数目不同，总共有多少种放法？（2012年9月招聘考题）
A、4
B、5
C、6
D、7
E、None of above 

分析：博主是，直接数的。。。

8、2月28日出生和2月29日出生的人的比例是多少？2012年2月28日和2012年2月29日出生的人的比例是多少？（2012年9月招聘考题）

A.1:1和1:1

B.4:1和1:1

C.1:1和4:1

D.4:1和4:1

分析：4:1（四年一次闰年）

1:1（如果闰年，则那年28日和29日出生概率相同，与在其他日期出生概率没有差别）

9、1000瓶中有1瓶毒药，喂老鼠，问至少多少只老鼠，才能识别毒药？（2013年4月实习招聘考题）

 A. 9

 B. 10

 C. 32

 D. None of the above

分析：微软总是爱出涉及到01表示和进制的题目。这道题目是一道经典老题了。

2^n > 1000，n=10即可。

10、3*4的表格，可能找出多少个矩形？（2013年4月实习招聘考题）

 A. 18

 B. 20

 C. 40

 D. 60

 E. None of above is correct

11、一条直线可以将平面分2部分，2条可以分4部分，问100条可以分多少部分？（2013年4月实习招聘考题）

A. 5051

B. 5053

C. 5510

D. 5511

分析：当已经有n-1条直线的时候，再加第n条直线，最多可以与前n-1条直线相交，多出n个部分。有递推公式：x(n) - x(n-1) = n , x(0) = 1

12、有N个球，只有一个的质量和其他的不同，给你一个天平(当然是没有刻度的)，允许称3次，问下面可能的N有？（2013年4月实习招聘考题）

A. 12

B. 16

C. 20

D. 24

E. 28

分析：其实<=3^3=27的都可以被解决

13、让我们假设一种类型的癌症可能被误诊。100人有5人有这个癌症但被诊断为没有它，100人中有1人没有这种癌症但会被诊断为有。我们知道获得此癌的几率是0.1%左右。一个人在检查后被诊断为有这种癌症，下列哪个值最接近他真的有癌症的概率？（2013年9月招聘考题）

A、90%
B、50%
C、30%
D、10%

分析：典型的贝叶斯概率公式的应用嘛。所以说，大家还是复习复习概率吧。

15、卡特兰数

1、一个节点可以生成生成一种二叉树，两个相同的节点可以生成两种二叉树，三个相同的节点可以生成5种二叉树，那5种呢？（2011年4月实习招聘考题）

典型的卡特兰数题目，详见找工作知识储备(1)---从头说catalan数及笔试面试里那些相关的问题，答案为42。

2、有一个堆栈和n个数字的序列（即1,2,3，……，n）。将N个数进栈后，随机弹出生成序列。有多少种不同的序列？设n为2，输出序列可以12或21，所以我们得到了2种不同的序列。

A、C_2n^n
B、C_2n^n - C_2n^(n+1)
C、((2n)!)/(n+1)n!n!
D、n!
E、None of above

典型的卡特兰数题目，详见找工作知识储备(1)---从头说catalan数及笔试面试里那些相关的问题

16、数据库

1、下面哪种情况需要用到外连接?（2013年9月招聘考题）

A. 被连接的表有 NOT NULL 列

B. 被连接的表只有匹配的数据

C. 被连接的列有 NULL

D. 被连接的表有不匹配数据

E. 被连接的表既有匹配的也有不匹配的数据

分析：外连接可以将未匹配的字段显示出来。也可以显示NULL字段。

2、关于数据库服务器说法正确的有 ?（2013年9月招聘考题）

A. 数据库服务器不要和 web 服务器放在一起；

B. 数据库服务器不要放在 based server 之上

C. SA 不要使用空密码；

D. 采用集中管理模型；

分析：数据库要与服务器分离。sa用户要设置强力密码。应用集中管理模式，可以加强党的领导。←_←

17、计算机网络

1、当建立连接时，下面哪一个数据包发送顺序是正确的TCP握手协议过程？（2012年9月招聘考题）

A. SYN，SYN+ACK，SYN+ACK

B. SYN+ACK，SYN+ACK，SYN

C. SYN，SYN+ACK，RST

D. SYN，SYN，ACK

E. 以上都不是

分析：貌似应该是SYN，SYN+ACK，ACK吧，于是选 E？

2、关于HTTP协议说明，哪些是正确的（2012年9月招聘考题）

A. 在CS模式下，作为一种request-response协议

B. 无状态，对每一个请求看成独立的

C. WWW和Email使用的协议

D. HTTP响应包括数字状态码，404经常代表“PageNot Found”

E. 以上都不是

分析：Email使用的是STMP协议，HTTP还有一个特性是“无连接”：无连接的含义是限制每次连接只处理一个请求。服务器处理完客户的请求，并收到客户的应答后，即断开连接。采用这种方式可以节省传输时间。

3、下列关于TCP的表述哪些是正确的？（2013年9月招聘考题）

A、TCP提供了一种方式，应用程序发送IP数据报封装并对其他们传输无需建立连接。

B、TCP支持多播。

C、端口数低于1024的称为常用端口，并且为标准服务保存。例如，端口21是预留给FTP协议，端口25是SMTP协议。

D、TCP对丢包可进行可靠的处理。

E、上述表述均不正确。

4、下面哪些是常用的攻击方法 ?（2013年9月招聘考题）

A、Vulnerability scan
B、SQL Injection
C、Drive-by downloading
D、Brute force

18、操作系统

1、对于一个32位的操作系统来说，那些是正确的？（2011年9月招聘考题）

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

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

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

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

2、哪种(些)同步机制可以用来避免在操作系统的进程/线程之间的竞争条件？（2012年4月实习招聘考题）

A、Mutex(互斥)    B、Mailbox  C、Semaphore(信号量)   D、Local procedure 

分析：概念题，利用互斥和信号量可实现同步机制。具体可参见找工作笔试面试那些事儿(13)---操作系统常考知识点总结

四种进程同步的方法：

1、临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。

2、互斥量:为协调共同对一个共享资源的单独访问而设计的。

3、信号量:为控制一个具有有限数量用户资源而设计。

4、事 件:用来通知线程有一些事件已发生，从而启动后继任务的开始

3、下面哪一项不能用于Widows中进程间通信？（2012年9月招聘考题）

A. 命名事件

B. 命名管道

C. 临界区

D. 共享内存

分析：管道，事件和内存共享都可实现进程间通信，临界区不行。详见找工作笔试面试那些事儿(13)---操作系统常考知识点总结

3、两个线程运行在双核机器上，每个线程主程序如下，线程1：x=1;r1=y;线程2：y=1;r2=x。x和y是两个全局变量，初始为0。以下哪一个是r1和r2的可能值？（2012年9月招聘考题）

A. r1=1,r2=1

B. r1=1,r2=0

C. r1=0,r2=1

D. r1=0,r2=0

分析：考察临界区问题，没有设置临界区，所以可能：

A: x=1 => y=1 => r1=y=1 => r2=x=1

B: y=1 => r2=x=0 => x=1 => r1=y=1

C: x=1 => r1=y=0 => y=1 =>r2=x=1

4、下列关于windows中进程和线程的区别，表述正确的是？（2013年4月实习招聘考题）

A. 操作系统下每一个应用都有一个进程，但不一定有一个线程

B. 进程有自己独立的栈，但是线程只能共享父进程的栈资源

C. 线程必须属于某个进程

D. 线程可以改变其所属的进程

5、下面哪些关于线程和进程的表述是正确的？（2013年9月招聘考题）

A、线程共享父进程的地址空间；进程共享父进程的地址空间。

B、改变主线程（取消，优先级的变化等等）过程中的会影响其他线程的行为；对父进程的子进程的变化不影响。

C、多线程可导致死锁，而多个进程不会导致死锁。

D、线程可以直接与其他进程通信；进程必须使用进程间通信与兄弟姐妹进程通信。

E、上述表述均不正确。

6、对于加载到内存中的 DLL，下面可以共享的是：（2013年9月招聘考题）

A. 代码段 

B. 静态数据 

C. 全局数据 

D. 外部链接的定义和引用 

E. BSS 段

7、下面不能加密文本的是 ?（2013年9月招聘考题）

A. MD5 

B. RSA 

C. RC4 

D. DES

分析：MD5是不可逆加密，不可以用来加密文本，RSA是不对称加密，DES和RC4是对称加密，后三种都可以用于文本加密。

8、为了加速数据获取速度，我们建立了缓存系统。假设我们的系统中，缓存L1的失效率是 50%, 缓存L2的失效率是 10%，L1的速度是 5ns，L2的速度是 50ns，内存访问速度是 400ns，问读内存的平均访问时间是 ?（2013年9月招聘考题）

A、5
B、30
C、45
D、50
E、55

分析：介个，简单的概率计算吧。

9、下面哪些可以优化程序性能：（2013年9月招聘考题）

A. 调整程序模式，减少 cache 失效率；

B. 使用一些特殊的指令来代替编译器生成的指令；

C. 将递归改写成迭代；

D. loop unwinding

分析：减少高速缓存的丢页率、将递归转化为循环结构都能加快程序运行。循环展开是一种古老的优化方法，在特别追求效率的程序中（如游戏）仍能见到踪迹。故D对。b是sse2之类的优化，B也对。

19、设计模式

1. MVC模式是现在开发的一种常用设计模式，请问如下可以充当MVC模式中控制器的是？（2011年4月实习招聘考题）

A  CSS

B HTML 模板

C Javascript

D Web Service

E 以上都不是

分析：这个博主不是特别懂，Web Service可以当作是控制器吧

2、下列属于设计模式中 ”creational pattern” （创建型）的是？（2012年9月招聘考题）

A、Facade
B、Singleton
C、Bridge
D、Composite
分析：Facade、bridge 和composite 都属于Structural（结构型）

20、其他(基础知识、运算符、常见算法、复杂度计算，正则等)

1、以下关键词中，哪些即可以用来修饰变量又可以用来修饰函数？（2012年4月实习招聘考题）

A、static   B、virtual   C、extern    D、inline   E、const

2、以下算法用到贪婪算法的是（2012年9月招聘考题）
A.单源最短路径中的Dijkstra算法

B.最小生成树的Prim算法

C.最小生成树的Kruskal算法

D.计算每对顶点最短路径的Floyd-Warshall算法

E.字符串匹配中的KMP算法

分析：算法导论中已明确说明Dijkstra，Prim，Kruskal为贪心算法。

1）Kruskal：初始化每个顶点为只有一个根几点的树，将边的权值按从小到大排序，选择权值最小的边(u,v)，如果u和v不在一颗树中，则将u和v所在两棵树合并，边(u,v)加入到集合中，直到所有的边都找完。

2）Prim：从任意顶点出发，维护一个树A，每一步，选择最小的边连接G(V,A)，将结点V加入到树A中，直到所有的顶点都找完。

3）Floyd-Warshall，KMP为动态规划

3、T(x)=1 (x<=1), T(n)=25*T(n/5)+n^2 求T(n)的时间复杂度（2012年9月招聘考题）
A、O(n*log(n))
B、O(log(n))
C、O(n^2*log(n))
D、O(n^3*log(n))
分析：T(n)=25*(25*T(n/25)+(n/5)^2)+n^2=25^2*T(n/(5^2))+2*n^2=25^(log(n)/log5)+(log(n)/log5)*n^2=n^2+n^2*log(n) =O(n^2*log(n))

4、<word>:: <letter>|<letter><pairlet>|<letter><pairdig>

<pairlet>:: <letter><letter>|<pairlet><letter><letter>

<pairdig>::<digit><digit>|<pairdig><digit><digit>

<letter>::a|b|c|…|y|z

<digit>::0|1|2|…|9

下面哪一个词可以从<word>的规则中产生？Iabcd II bcdef III d22  （2012年9月招聘考题）

A. 都不是

B. 只有I和II

C. 只有I和III

D. 只有II和III

E. I和II和III都是

分析：算是考察形式自动机的题。关键是分析清楚每种模式本质上代表什么。<letter>表示单个字母；<digit>表示单个数字；<pairdig>是两个<digit>，或者递归<pairdig>和两个<digit>，其实表示的是偶数个<digit>，即偶数个数字；同理，<pairlet>是偶数个字母。所以<word>的可能是：1个字母，奇数个字母，或者一个字母和偶数个数字。所以第二个和第三个是正确的。

5、下列程序的运行结果是？（2013年4月实习招聘考题）

{
  int x = 10 ;
  int y = 10 ;
  x = x++ ;
  y = ++y ;
  printf("%d, %d\n",x,y);
}

A. 10, 10

B. 10, 11

C. 11, 10

D. 11, 11

6、下列关于const的用法，对的是？（2013年4月实习招聘考题）

A. const int a;  //const的整型数

B. int const a;  //const的整型数

C. int const *a; //一个指向const整型数的指针

D. const int *a; //一个指向整型数的const指针

E. int const *a;  //一个指向整型数的const指针

分析：关于const的问题，也确实是一个常考的点，一个比较容易的记忆方式是，在const左侧有类型的时候，则左侧的东西是不可变的，例如int const a，则是整型数不可变；int * const a则是指针不可变。

7、下列代码输出值为1的是？（2013年4月实习招聘考题）

A. the return value of main function if program ends normally

B. return (7&1)

C. char *str="microsoft"; return str=="microsoft"

D. return "microsoft"=="microsoft"

E. None of the above

8、初始化整型数i的值为0，则在以下这些操作之后i的值是多少？（2013年9月招聘考题）

i += i > 0 ? i++ : i --;

A、-2
B、-1
C、0
D、1
E、2

9、下面可以匹配 www.microsoft.com 的正则表达式有 ?（2013年9月招聘考题）

A. ^\w+\.\w+\.\w+$

B. [w]{0,3}.[a-z]*.[a-z]+

C. [c-w]{3,10}[.][c-w][.][a]|.+

D. [w][w][w][microsoft]+[com]+

E. \w+

分析：正则这个东西，看看通配符和一些规则就行了。不难。

\w  代表 a-z A-Z 0-9；^ 代表 开头 $ 代表结尾；\. 代表字符；. 代表任意一个字符( 除了 \n)；| 代表或的意思

10、下面计算正整数乘积 A× B 的代码中最大的 bug 在第几行 ?（2013年9月招聘考题）

int mul(int a, int b){
    int c = 0;
    for(int i=0; i<b; ++i)
        c+=c;
    return c;
}

A、Line 1
B、Line 2
C、Line 3
D、Line 4
E、Line 5

分析：应该是应为 c+=a吧

11、下面可以建立一个但不能建立多个的索引的有 ?（2013年9月招聘考题）

A. 无索引

B. clustered 索引

C. clustered 索引和多 non-clustered 索引

D. 多 clustered 索引

分析：clustered索引一个表只能有一个，因为clustered索引是影响物理存贮地址的。