微软⾯试100题及答案
从百度⽂库下载的下载需要积分，贴在这⼤家随便看就好，不要追究我盗版，哈哈。。。
1.把⼆元查树转变成排序的双向链表
题⽬：
输⼊⼀棵⼆元查树，将该⼆元查树转换成⼀个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4  8 12 16
转换成双向链表
4=6=8=10=12=14=16。
⾸先我们定义的⼆元查树 节点的数据结构如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child ofnode
BSTreeNode *m_pRight; // right child ofnode
};
2.设计包含min函数的栈。
定义栈的数据结构，要求添加⼀个min函数，能够得到栈的最⼩元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
3.求⼦数组的最⼤和
题⽬：
输⼊⼀个整形数组，数组⾥有正数也有负数。
数组中连续的⼀个或多个整数组成⼀个⼦数组，每个⼦数组都有⼀个和。
求所有⼦数组的和的最⼤值。要求时间复杂度为O(n)。
例如输⼊的数组为1, -2, 3, 10, -4, 7, 2, -5，和最⼤的⼦数组为3, 10,-4, 7, 2，
因此输出为该⼦数组的和18。
4.在⼆元树中出和为某⼀值的所有路径
题⽬：输⼊⼀个整数和⼀棵⼆元树。
从树的根结点开始往下访问⼀直到叶结点所经过的所有结点形成⼀条路径。
打印出和与输⼊整数相等的所有路径。
例如 输⼊整数22和如下⼆元树
10
/ \
5 12
/  \
4    7
则打印出两条路径：10, 12和10, 5, 7。
⼆元树节点的数据结构定义为：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
5.查最⼩的k个元素
题⽬：输⼊n个整数，输出其中最⼩的k个。
例如输⼊1，2，3，4，5，6，7和8这8个数字，则最⼩的4个数字为1，2，3和4。
第6题
腾讯⾯试题：
给你10分钟时间，根据上排给出⼗个数，在其下排填出对应的⼗个数
要求下排每个数都是先前上排那⼗个数在下排出现的次数。
上排的⼗个数如下：
【0，1，2，3，4，5，6，7，8，9】
举⼀个例⼦，
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0在下排出现了6次，1在下排出现了2次，
2在下排出现了1次，3在下排出现了0次....
以此类推..
第7题
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，⽐如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第⼀个节点列?
第8题
此贴选⼀些 ⽐较怪的题，，由于其中题⽬本⾝与算法关系不⼤，仅考考思维。特此并作⼀题。
1.有两个房间，⼀间房⾥有三盏灯，另⼀间房有控制着三盏灯的三个开关，
这两个房间是 分割开的，从⼀间⾥不能看到另⼀间的情况。
现在要求受训者分别进这两房间⼀次，然后判断出这三盏灯分别是由哪个开关控制的。
有什么办法呢？
2.你让⼀些⼈为你⼯作了七天，你要⽤⼀根⾦条作为报酬。⾦条被分成七⼩块，每天给出⼀块。如果你只能将⾦条切割两次，你怎样分给这些⼯⼈?
3.　★⽤⼀种算法来颠倒⼀个链接表的顺序。现在在不⽤递归式的情况下做⼀遍。
  ★⽤⼀种算法在⼀个循环的链接表⾥插⼊⼀个节点，但不得穿越链接表。
  ★⽤⼀种算法整理⼀个数组。你为什么选择这种⽅法?
  ★⽤⼀种算法使通⽤字符串相匹配。
  ★颠倒⼀个字符串。优化速度。优化空间。
  ★颠倒⼀个句⼦中的词的顺序，⽐如将“我叫克丽丝”转换为“克丽丝叫我”，
实现速度最快，移动最少。
  ★到⼀个⼦字符串。优化速度。优化空间。
  ★⽐较两个字符串，⽤O(n)时间和恒量空间。
  ★假设你有⼀个⽤1001个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1到1000(包括1000)之间。此外，除⼀个数字出现两次外，其他所有数字只出现⼀次。假设你只能对这个数组做⼀次处理，⽤⼀种算法出重复的那个数字。如果你在运算中使⽤了辅助的存储⽅式，那么你能
到不⽤这种⽅式的算法吗?
  ★不⽤乘法或加法增加8倍。现在⽤同样的⽅法增加7倍。
第9题
判断整数序列是不是⼆元查树的后序遍历结果
题⽬：输⼊⼀个整数数组，判断该数组是不是某⼆元查树的后序遍历的结果。
如果是返回true，否则返回false。
例如输⼊5、7、6、9、11、10、8，由于这⼀整数序列是如下树的后序遍历结果：
8
/  \
6    10
/ \  / \
5  7 9  11
因此返回true。
如果输⼊7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
第10题
翻转句⼦中单词的顺序。
题⽬：输⼊⼀个英⽂句⼦，翻转句⼦中单词的顺序，但单词内字符的顺序不变。
句⼦中单词以空格符隔开。为简单起见，标点符号和普通字母⼀样处理。
例如输⼊“I am a student.”，则输出“student. a am I”。
第11题
求⼆叉树中节点的最⼤距离...
如果我们把⼆叉树看成⼀个图，⽗⼦节点之间的连线看成是双向的，
我们姑且定义"距离"为两节点之间边的个数。
写⼀个程序，
求⼀棵⼆叉树中相距最远的两个节点之间的距离。
第12题
题⽬：求1+2+…+n，
要求不能使⽤乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。
第13题：
题⽬：输⼊⼀个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
第14题：
题⽬：输⼊⼀个已经按升序排序过的数组和⼀个数字，
在数组中查两个数，使得它们的和正好是输⼊的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输⼊的数字，输出任意⼀对即可。
例如输⼊数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
第15题：
题⽬：输⼊⼀颗⼆元查树，将该树转换为它的镜像，
即在转换后的⼆元查树中，左⼦树的结点都⼤于右⼦树的结点。
⽤递归和循环两种⽅法完成树的镜像转换。
例如输⼊：
8
/ \
6 10
/\ /\
5 7 9 11
输出：
8
/ \
10 6
/
\ /\
11 9 7 5
定义⼆元查树的结点为：
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
第16题：
题⽬（微软）：
输⼊⼀颗⼆元树，从上往下按层打印树的每个结点，同⼀层中按照从左往右的顺序打印。  例如输⼊
8
/ \
6 10
/ \ / \
5 7 9 11
输出8 6 10 5 7 9 11。
第17题：
题⽬：在⼀个字符串中到第⼀个只出现⼀次的字符。如输⼊abaccdeff，则输出b。
分析：这道题是2006年google的⼀道笔试题。
第18题：
题⽬：n个数字（0,1,…,n-1）形成⼀个圆圈，从数字0开始，
每次从这个圆圈中删除第m个数字（第⼀个为当前数字本⾝，第⼆个为当前数字的下⼀个数字）。
当⼀个数字删除后，从被删除数字的下⼀个继续删除第m个数字。
求出在这个圆圈中剩下的最后⼀个数字。
July：我想，这个题⽬，不少⼈已经 见识过了。
第19题：
题⽬：定义Fibonacci数列如下：
/ 0 n=0
f(n)= 1 n=1
\ f(n-1)+f(n-2) n=2
输⼊n，⽤最快的⽅法求该数列的第n项。
分析：在很多C语⾔教科书中讲到递归函数的时候，都会⽤Fibonacci作为例⼦。
因此很多程序员对这道题的递归解法⾮常熟悉，但....呵呵，你知道的。。
第20题：
题⽬：输⼊⼀个表⽰整数的字符串，把该字符串转换成整数并输出。
例如输⼊字符串"345"，则输出整数345。
第21题
2010年中兴⾯试题
编程求解：
输⼊两个整数 n 和 m，从数列1，2，3.......n 中 随意取⼏个数,
使其和等于 m ，要求将其中所有的可能组合列出来.
第22题：
有4张红⾊的牌和4张蓝⾊的牌，主持⼈先拿任意两张，再分别在A、B、C三⼈额头上贴任意两张牌，A、B、C三⼈都可以看见其余两⼈额头上的牌，看完后让他们猜⾃⼰额头上是什么颜⾊的牌，
A说不知道，B说不知道，C说不知道，然后A说知道了。
请教如何推理，A是怎么知道的。
如果⽤程序，⼜怎么实现呢？
第23题：
⽤最简单，最快速的⽅法计算出下⾯这个圆形是否和正⽅形相交。"
3D坐标系 原点(0.0,0.0,0.0)
圆形:
半径r = 3.0
圆⼼o = (*.*, 0.0, *.*)
正⽅形:
微软中国下载中心
4个⾓坐标;
1:(*.*, 0.0, *.*)
2:(*.*, 0.0, *.*)
3:(*.*, 0.0, *.*)
4:(*.*, 0.0, *.*)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。