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

作者：寒小阳

时间：2013年10月。

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

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

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；

代码如下：

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月实习招聘考题）
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月校招考题）
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索引是影响物理存贮地址的。