微软中国员工笔试试题及答案

笔试分为两大部分，全部是英语题，仅供参考
第一部分 10 道选择题 每道题答对 4 分，不答 0 分，写一个错误选项则会扣除一分。（

共 40 分）
第二部分是一道编程题（C、C 、C#、Java 均可），写完之后要编写 测试用例。

（35 15）
选择题部分
1. 以下哪些不是栈的基本操作
A. push
B. pop
C. 判断栈是否为空
D. 栈排序
2.两个有序数组 大小都是 n，现在要对它们进行合并排序。 问最坏情况下，需要比较多少

次？
A. 2n 1
B. 2n
C.2n-1
D…记不清了
3. （an 表示第 n 个常数， x^5 表示 x 的 5 次方）
f（x）= a0*x^0 a1*x^1 a2*x^2 ……an*x^n
对于固定的 n，f（x）的时间复杂度以及空间复杂度分别是多少？
A. o（n^2），o（n）
B.o（n），o（1）
C
D 都记不住了
4.是个概率题，大概意思是这样的
现在有 800 个人，但是只有 400 份奖品，有一对夫妇都参加抽奖，但是他们最多抽到一

份奖，现在问他们俩能抽到一份奖的概率是多少？
A.0.5
B.0.75
C. （0.5,0.75）
D. （0.75,1）
5. 现有一链表当前指示节点为 currentNode, 生成了一个新节点 newNode,问要把

newNode 插入到 currentNode 之后 ，该怎么做？
A…
B…
C. newNode->next = currentNode->next, currentNode->next = newNode. D…
6. 问以下哪些特征不是 interpreted language（解释型语言）所独有的：
（我们知道一般分为两种：解释型语言 VB,Shell,批处理等；编译型语言，C，java 等。各

有优点 ）
A. 平台无关性。（明显不对，因为 java 才是平台无关的）
B. 执行速度较快（这个问题，以前做作业时就没争论清楚，自己感觉解释型语言不需要编

译，速度能快一些，但是重复执行时，编译型语言只需要编译一次，效率高……）
C. 可以定义动态变量（应该两种都可以）
D.以上都不对
7.给了一个二叉树，让求后序遍历的结果。
这个题如果知道后序遍历，肯定就可以做出来了。
尽管不难 还是要搞清楚三者的区别（哈哈）
先序 左根右
中序 根左右
后序 左右根
8.问以下几种排序方法，在最坏情况下时间复杂度小于 o（n^2）的是哪一种（这个题目

记得不是很清楚了）
A.快排
B.插入排序
C.合并排序
D.栈排序
9. 现有 n 1 这么大的存储空间（可以理解有这么一个大小为 n 1 的数组），中间存了

[1,n 1]范围内的n 个数，说明丢失了一个数，现在要找出这个丢失的数，问最好情况下时间

复杂度是多少
A.o（1）
B.o（n）
C.o（n^2）
D.o（nlogn）
10.是一道程序题，由于太长，无从记忆……
编程题部分
用 C,C ,C#,或 Java 中的一种来编写以下程序。
现在给你一个 字符串，其中特殊的字符只有两种 space（空格） （" "），newline（换行

） （/n）。 现在让你来去除其中多余的空格。
具体要求
1.连续的空格只能当保留其中一个
2. 该字符串的开头不能有空格
3. 该字符串的结尾不能有空格
4. 任何/n 的前面或才后面都不能存在多余的空格
为了得到很高的分数，还需要满足以下条件
1.不能申请新的字符串空间
2.对给出的字符串只能遍历一遍
不能使用任何库函数。
我们给了两个供你调用的函数
int intIsSpace（char str）（）
当字符不为空格时，将返回 0
当字符为空格时，将返回其它任意非 0 值
int intIsNewLine（char str）（）
当字符不为换行时，将返回 0
当字符为换行时，将返回其它任意非 0 值
程序编写完成后，请编写测试用例，并说明它完成的作用。