[第1题-60题汇总]微软数据结构+算法面试100题

面试微软必备22道数据结构算法面试题（含答案）1、反转一个链表。

循环算法。

1 List reverse(List l) {2 if(!l) return l;3 list cur = l.next;4 list pre = l;5 list tmp;6 pre.next = null;7 while ( cur ) {8 tmp = cur;9 cur = cur.next;10 tmp.next = pre;11 pre = tmp;12 }13 return tmp;14 }2、反转一个链表。

递归算法。

1 List resverse(list l) {2 if(!l || !l.next) return l;34 List n = reverse(l.next);5 l.next.next = l;6 l.next=null;7 }8 return n;9 }3、广度优先遍历二叉树。

1 void BST(Tree t) {2 Queue q = new Queue();3 q.enque(t);4 Tree t = q.deque();5 while(t) {6 System.out.println(t.value);7 q.enque(t.left);8 q.enque(t.right);9 t = q.deque();10 }11 }----------------------1class Node {2 Tree t;3 Node next;4 }5class Queue {6 Node head;7 Node tail;8 public void enque(Tree t){9 Node n = new Node();10 n.t = t;11 if(!tail){12 tail = head = n;13 } else {14 tail.next = n;15 tail = n;16 }17 }18 public Tree deque() {19 if (!head) {20 return null;21 } else {22 Node n = head;23 head = head.next;24 return n.t;25 }26}4、输出一个字符串所有排列。

算法面试经典100题算法面试是计算机领域的重要环节，经典的算法问题往往能够考验求职者的解决问题的能力和思维属性。

在这里，我们将介绍100道经典的算法面试题，让你在面试中迎刃而解。

字符串：1. 判断一个字符串是否为回文字符串。

2. 给定一个字符串，求出其中出现次数最多的字符和出现的次数。

3. 实现一个函数，将字符串中的空格替换为"%20"。

4. 判断一个字符串是否与另一个字符串的字符种类和数量相同。

5. 找出一个字符串中出现次数为1的字符。

数组和矩阵：6. 寻找数组中的最大值和最小值。

7. 给定一个有序数组，实现两数之和。

8. 给定一个数组和一个目标值，找出数组中两数之和等于目标值的下标。

9. 给定一个有序数组和一个目标值，找出目标值在数组中第一次出现的下标。

10. 给定一个二维矩阵和一个目标值，找出目标值在矩阵中的位置。

链表：11. 反转链表。

12. 删除链表中的重复节点。

13. 找到链表的中间节点。

14. 找到链表的倒数第k个节点。

15. 判断链表是否为回文链表。

树：16. 实现二叉查找树，并对其进行插入和查找操作。

17. 实现二叉查找树的前序、中序和后序遍历。

18. 实现二叉查找树的广度优先遍历。

19. 判断两棵二叉树是否相同。

20. 判断一棵二叉树是否为平衡二叉树。

图：21. 判断一张图是否为二分图。

22. 实现拓扑排序。

23. 实现最短路径算法（如Dijkstra算法）。

24. 实现最小生成树算法（如Prim算法和Kruskal算法）。

25. 实现图的遍历（如深度优先遍历和广度优先遍历）。

排序和查找：26. 实现冒泡排序。

27. 实现快速排序。

28. 实现选择排序。

29. 实现插入排序。

30. 实现归并排序。

31. 实现希尔排序。

32. 实现堆排序。

33. 实现计数排序。

34. 实现基数排序。

35. 实现查找算法（如二分查找和哈希查找）。

动态规划：36. 实现斐波那契数列。

微软的22道数据结构算法面试题（含答案）1、反转一个链表。

循环算法。

1 List reverse(List l) {2 if(!l) return l;3 list cur = l.next;4 list pre = l;5 list tmp;6 pre.next = null;7 while ( cur ) {8 tmp = cur;9 cur = cur.next;10 tmp.next = pre;11 pre = tmp;12 }13 return tmp;14 }2、反转一个链表。

递归算法。

1 List resverse(list l) {2 if(!l || !l.next) return l;34 List n = reverse(l.next);5 l.next.next = l;6 l.next=null;7 }8 return n;9 }3、广度优先遍历二叉树。

1 void BST(Tree t) {2 Queue q = new Queue();3 q.enque(t);4 Tree t = q.deque();5 while(t) {6 System.out.println(t.value);7 q.enque(t.left);9 t = q.deque();10 }11 }----------------------1class Node {2 Tree t;3 Node next;4 }5class Queue {6 Node head;7 Node tail;8 public void enque(Tree t){9 Node n = new Node();10 n.t = t;11 if(!tail){12 tail = head = n;13 } else {14 tail.next = n;15 tail = n;16 }17 }18 public Tree deque() {19 if (!head) {20 return null;21 } else {22 Node n = head;23 head = head.next;24 return n.t;25 }26}4、输出一个字符串所有排列。

第⼀组题答案： 1）三根绳，第⼀根点燃两端，第⼆根点燃⼀端，第三根不点，第⼀根绳烧完（30分钟）后，点燃第⼆根绳的另⼀端，第⼆根绳烧完（45分钟）后，点燃第三根绳⼦两端，第三根绳烧完（1⼩时15分）后，计时完成 2）根据抽屉原理，4个 3）3升装满；3升-〉5升（全注⼊）；3升装满；3升-〉5升（剩1升）；5升倒掉；3升-〉5升（注⼊1升）；3升装满；3升-〉5升；完成（另：可⽤回溯法编程求解） 4）问其中⼀⼈：另外⼀个⼈会说哪⼀条路是通往诚实国的？回答者所指的那条路必然是通往说谎国的。

5）12个球： 第⼀次：4，4 如果平了：那么剩下的球中取3放左边,取3个好球放右边，称：如果左边重，那么取两个球称⼀下，哪个重哪个是次品，平的话第三个重，是次品，轻的话同理，如果平了，那么剩下⼀个次品，还可根据需要称出次品⽐正品轻或者重，如果不平：那么不妨设左边重右边轻，为了便于说明，将左边4颗称为重球，右边4颗称为轻球，剩下4颗称为好球，取重球2颗，轻球2颗放在左侧，右侧放3颗好球和⼀颗轻球，如果左边重，称那两颗重球，重的⼀个次品，平的话右边轻球次品。

如果右边重，称左边两颗轻球，轻的⼀个次品。

如果平，称剩下两颗重球，重的⼀个次品，平的话剩下那颗轻球次品 13个球： 第⼀次：4，4，如果平了。

剩5颗球⽤上⾯的⽅法仍旧能找出次品，只是不能知道次品是重是轻。

如果不平，同上 6） o o o o o o o o o 7） 23次，因为分针要转24圈，时针才能转1圈，⽽分针和时针重合两次之间的间隔显然>1⼩时，它们有23次重合机会，每次重合中秒针有⼀次重合机会，所以是23次 重合时间可以对照⼿表求出，也可列⽅程求出 8） 在地球表⾯种树，做⼀个地球内接的正四⾯体，内接点即为所求 第⼆组⽆标准答案 第三组 1. 分成1,2,4三段，第⼀天给1，第⼆天给2取回1，第3天给1，第4天给4取回1、2，第5天给1，第6天给2取回1，第七天给1 2. 求出⽕车相遇时间，鸟速乘以时间就是鸟飞⾏的距离 3. 四个罐⼦中分别取1,2,3,4颗药丸，称出⽐正常重多少，即可判断出那个罐⼦的药被污染 4. 三个开关分别：关，开，开10分钟，然后进屋，暗且凉的为开关1控制的灯，亮的为开关2控制的灯，暗且热的为开关3控制的灯 5. 因为可以⽤1，2，5，10组合成任何需要的货币值，⽇常习惯为10进制 6. 题意不理解...*_* 7. 012345 0126(9)78 第四组都是很难的题⽬ 第⼀题：97 0 1 2 0 或者 97 0 1 0 2 （提⽰：可⽤逆推法求出） 第⼆题：3架飞机5架次，飞法： ABC 3架同时起飞，1/8处，C给AB加满油，C返航，1/4处，B给A加满油，B返航，A到达1/2处，C从机场往另⼀⽅向起飞，3/4处，C同已经空油箱的A平质Ｓ嘤⼟浚 盉从机场起飞，AC到7/8处同B平分剩余油量，刚好3架飞机同时返航。

微软面试100题及答案【篇一：微软技术面试100题答案1】p class=txt>1.把二元查找树转变成排序的双向链表（树）题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

10/ /6 14/ / / /4 8 12 16转换成双向链表4=6=8=10=12=14=16。

首先我们定义的二元查找树节点的数据结构如下：struct bstreenode{int m_nvalue; // value of nodebstreenode *m_pleft; // left child of nodebstreenode *m_pright; // right child of node};sorehead：第一题：基本就是采用一次遍历即可，楼主采用的是递归方法。

但有两个建议：1、函数里面最好不好使用全局变量，采用参数传递的方式可能更好。

全局变量能少用就少用。

2、if (null == pcurrent)这种方式我也不是很推荐。

我知道采用这种方式的好处是一旦少写了一个等号，编译器会报错，null不是一个合法左值。

其实我最开始写代码时也是这么写的，很长时间都觉得挺好。

但这有个悖论，就是一个开发者能够想起来这么写的时候，这说明他知道这么是要做等值判断，自然也会知道该写==而不是=，想不起来的时候自然也就该犯错误还是犯错误，并不能起到原本初衷。

代码写多了，会发现这么写真有点多此一举。

july关于第一题，我再多说点：我们可以中序遍历整棵树。

按照这个方式遍历树，比较小的结点先访问。

如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。

当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

view plaincopy to clipboard? // 遍历二元查找树中序??????????????????????????????????????????????????? { if (null == pcurrent) {return; } if (null != pcurrent-m_pleft) { ergodicbstree(pcurrent-m_pleft); } // 节点接到链表尾部converttodoublelist(pcurrent); // 右子树为空 if (null != pcurrent-m_pright) { ergodicbstree(pcurrent-m_pright); }}// 二叉树转换成listvoid converttodoublelist(bstreenode * pcurrent){ pcurrent-m_pleft = plistindex; if (null != plistindex) { plistindex-m_pright = pcurrent; } else??????????phead = pcurrent; } plistindex = pcurrent; coutpcurrent-m_nvalueendl;}或者网友何海涛所述：view plaincopy to clipboard???????????????????????????????????????? void convertnode(bstreenode* pnode, bstreenode* plastnodeinlist){if(pnode == null)return; bstreenode *pcurrent = pnode; // convert the left sub-tree if (pcurrent-m_pleft != null) convertnode(pcurrent-m_pleft, plastnodeinlist); // put the current node into the double-linked list pcurrent-m_pleft = plastnodeinlist; if(plastnodeinlist != null)plastnodeinlist-m_pright = pcurrent;plastnodeinlist = pcurrent; // convert the right sub-treeif (pcurrent-m_pright !=null)convertnode(pcurrent-m_pright, plastnodeinlist);}?????????????????????? bstreenode* convert_solution1(bstreenode* pheadoftree){bstreenode *plastnodeinlist =null;convertnode(pheadoftree, plastnodeinlist); // get the head of the double-linked listbstreenode *pheadoflist = plastnodeinlist;while(pheadoflist pheadoflist-m_pleft)pheadoflist = pheadoflist-m_pleft;return pheadoflist;}但显然，以下这种思路更容易理解些：view plaincopy to clipboard ???????????????????????????????? bstreenode* convertnode(bstreenode* pnode, bool asright){if(!pnode)return null;bstreenode *pleft =null;bstreenode *pright = null;// convert the left sub-treeif(pnode-m_pleft)pleft = convertnode(pnode-m_pleft, false);// connect the greatest node in the left sub-tree to the current nodeif(pleft){pleft-m_pright = pnode;?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ?????? }// convert the right sub-treeif(pnode-m_pright)pright = convertnode(pnode-m_pright, true);// connect the least node in the right sub-tree to the current nodeif(pright){pnode-m_pright = pright;pright-m_pleft = pnode;}bstreenode *ptemp = pnode;//if the current node is the right child of its parent, // return the least node in the tree whose root is the currentnodeif(asright){while(ptemp-m_pleft)ptemp = ptemp-m_pleft;}// if the current node is the left child of its parent, // return the greatest node in the tree whose root is the currentnodeelse{while(ptemp-m_pright)ptemp = ptemp-m_pright;}【篇二：微软面试100题】ss=txt>题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

[整理III]微软等公司数据结构+算法面试第1-100题汇总---首次一次性汇总公布1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

10/ \6 14/ \ / \4 8 12 16转换成双向链表4=6=8=10=12=14=16。

首先我们定义的二元查找树节点的数据结构如下：struct BSTreeNode{int m_nV alue; // value of nodeBSTreeNode *m_pLeft; // left child of nodeBSTreeNode *m_pRight; // right child of node};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_nV alue; // value of nodeBinaryTreeNode *m_pLeft; // left child of nodeBinaryTreeNode *m_pRight; // right child of node};5.查找最小的k个元素题目：输入n个整数，输出其中最小的k个。

第一组1.烧一根不均匀的绳，从头烧到尾总共需要1个小时。

现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢?2.你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。

抓取多少个就可以确定你肯定有两个同一颜色的果冻?3.如果你有无穷多的水，一个3公升的提捅，一个5公升的提捅，两只提捅形状上下都不均匀，问你如何才能准确称出4公升的水?4.一个岔路口分别通向诚实国和说谎国。

来了两个人，已知一个是诚实国的，另一个是说谎国的。

诚实国永远说实话，说谎国永远说谎话。

现在你要去说谎国，但不知道应该走哪条路，需要问这两个人。

请问应该怎么问?5.12个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。

13个呢?(注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑)6.在9个点上画10条直线，要求每条直线上至少有三个点?7.在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次?都分别是什么时间?你怎样算出来的?8.怎么样种植4棵树木，使其中任意两棵树的距离相等?第二组1.为什么下水道的盖子是圆的?2.中国有多少辆汽车?3.将汽车钥匙插入车门，向哪个方向旋转就可以打开车锁?4.如果你要去掉中国的34个省(含自治区、直辖市和港澳特区及台湾省)中的任何一个，你会去掉哪一个，为什么?5.多少个加油站才能满足中国的所有汽车?6.想象你站在镜子前，请问，为什么镜子中的影象可以颠倒左右，却不能颠倒上下?7.为什么在任何旅馆里，你打开热水，热水都会瞬间倾泻而出?8.你怎样将Excel的用法解释给你的奶奶听?9.你怎样重新改进和设计一个ATM银行自动取款机?10.如果你不得不重新学习一种新的计算机语言，你打算怎样着手来开始?11.如果你的生涯规划中打算在5年内受到奖励，那获取该项奖励的动机是什么?观众是谁?12.如果微软告诉你，我们打算投资五百万美元来启动你的投资计划，你将开始什么样商业计划?为什么?13.如果你能够将全世界的电脑厂商集合在一个办公室里，然后告诉他们将被强迫做一件事，那件事将是什么?第三组1.你让工人为你工作7天，回报是一根金条，这个金条平分成相连的7段，你必须在每天结束的时候给他们一段金条。

微软面试100题微软面试100题1为什么下水道的井盖是圆的？答案-1.节省材料2.方便运输3.方便安装4.美观5.受力均匀2美国有多少辆车？（一个常见的类似问题是：美国有多少家加油站？）答案：美国有多少人？这些人里又有多少人会开车？而会开车的人里又有多少有这样的经济能力可以购买汽车？可以购买汽车的人里是不是都已经买了？这些问题解决了3美国有多少个下水道井盖？4你让某些人为你工作了七天，你要用一根金条作为报酬。

这根金条要被分成七块。

你必须在每天的活干完后交给他们一块。

如果你只能将这根金条切割两次，你怎样给这些工人分？答案是：把金段切割成1/7、2/7、4/7第一天给工人1/7第二天给工人2/7 工人返回1/7第三天给工人1/7第四天给工人4/7 工人返回1/7+2/7第五天给工人1/7第六天给工人2/7 工人返回1/7第七天给工人1/75一列火车以每小时15英里的速度离开洛杉矶，朝纽约进发。

另外一列火车以每小时20英里的速度离开纽约，朝洛杉矶进发。

如果一只每小时飞行25英里的鸟同时离开洛杉矶，在两列火车之间往返飞行，请问当两列火车相遇时，鸟飞了多远？答案：你这么想：鸟飞了多远呢？鸟的飞行速度一直是每小时25英里不变的，那么只要能知道鸟飞了多久，就能知道鸟飞了多远。

那么鸟飞了多久呢？鸟从最开始一直飞到两列火车相遇的时候。

那么两列火车要多久才能相遇呢？这取决于洛杉矶到纽约有多远。

理论中，纽约到洛杉矶有大约3000英里，两列火车要相遇需要3000除以（15+20），也就是85.7小时。

在这段时间里，鸟飞了2142.5 英里。

实际中，一来铁路不一定是直的（确切的铁路距离无法知晓），二来火车路上走走停停还可能晚点，三来两辆火车不一定就会彼此相遇，最后是鸟一路上也需要花些时间吃喝拉撒——所以答案还真不好说。

6假设一张圆盘像唱机上的唱盘那样转动。

这张盘一半是黑色，一半是白色。

假设你有数量不限的一些颜色传感器。

要想确定圆盘转动的方向，你需要在它周围摆多少个颜色传感器？它们应该被摆放在什么位置？7假设时钟到了12点。

经典的微软面试题目及参考答案经典的面试题目是微软求职者求职面试成功的开路先锋，对面试题目的回答直接影响微软求职者的面试成败。

下面是店铺为大家精心推荐的经典的微软面试题，希望能够对您有所帮助。

经典的微软面试题(一)1、烧一根不均匀的绳，从头烧到尾总共需要1个小时。

现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢?2、你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。

抓取多少个就可以确定你肯定有两个同一颜色的果冻?3、如果你有无穷多的水，一个3公升的提捅，一个5公升的提捅，两只提捅形状上下都不均匀，问你如何才能准确称出4公升的水?4、一个岔路口分别通向诚实国和说谎国。

来了两个人，已知一个是诚实国的，另一个是说谎国的。

诚实国永远说实话，说谎国永远说谎话。

现在你要去说谎国，但不知道应该走哪条路，需要问这两个人。

请问应该怎么问?5、12个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。

13个呢?(注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑)6、在9个点上画10条直线，要求每条直线上至少有三个点?7、在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次?都分别是什么时间?你怎样算出来的?8、怎么样种植4棵树木，使其中任意两棵树的距离相等?经典的微软面试题(二)1、为什么下水道的盖子是圆的?2、中国有多少辆汽车?3、将汽车钥匙插入车门，向哪个方向旋转就可以打开车锁?4、如果你要去掉中国的34个省(含自治区、直辖市和港澳特区及台湾省)中的任何一个，你会去掉哪一个，为什么?5、多少个加油站才能满足中国的所有汽车?6、想象你站在镜子前，请问，为什么镜子中的影象可以颠倒左右，却不能颠倒上下?7、为什么在任何旅馆里，你打开热水，热水都会瞬间倾泻而出?8、你怎样将Excel的用法解释给你的奶奶听?9、你怎样重新改进和设计一个ATM银行自动取款机?10、如果你不得不重新学习一种新的计算机语言，你打算怎样着手来开始?11、如果你的生涯规划中打算在5年内受到奖励，那获取该项奖励的动机是什么?观众是谁?12、如果微软告诉你，我们打算投资五百万美元来启动你的投资计划，你将开始什么样商业计划?为什么?13、如果你能够将全世界的电脑厂商集合在一个办公室里，然后告诉他们将被强迫做一件事，那件事将是什么?经典的微软面试题(三)1、你让工人为你工作7天，回报是一根金条，这个金条平分成相连的7段，你必须在每天结束的时候给他们一段金条。

本文自CSDN大牛的一篇博客：/v_july_v/article/details/6870251作者：July、阿财时间：二零一一年十月十三日。

我能够看到此文，还要多同学！让我得以及时分享给大家微软面试100题全部答案个人整理的前60题的答案可参见以下三篇文章：1.微软100题第1题-20题答案/v_JULY_v/archive/2011/01/10/6126406.aspx [博文 I]2.微软100题第21-40题答案/v_JULY_v/archive/2011/01/10/6126444.aspx[博文II]3.微软100题第41-60题答案/v_JULY_v/archive/2011/02/01/6171539.aspx[博文III]最新整理的全部100题的答案参见如下（重复的，以及一些无关紧要的题目跳过）：1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

10/ \6 14/ \ / \4 8 12 16转换成双向链表4=6=8=10=12=14=16。

首先我们定义的二元查找树节点的数据结构如下：struct BSTreeNode{int m_nValue; // value of nodeBSTreeNode *m_pLeft; // left child of nodeBSTreeNode *m_pRight; // right child of node};ANSWER:This is a traditional problem that can be solved using recursion.For each node, connect the double linked lists created from left and right child node to form a full list./*** param root The root node of the tree* return The head node of the converted list.*/BSTreeNode * treeToLinkedList(BSTreeNode * root) {BSTreeNode * head, * tail;helper(head, tail, root);return head;}void helper(BSTreeNode *& head, BSTreeNode *& tail, BSTreeNode *root) {BSTreeNode *lt, *rh;if (root == NULL) {head = NULL, tail = NULL;return;}helper(head, lt, root->m_pLeft);helper(rh, tail, root->m_pRight);if (lt!=NULL) {lt->m_pRight = root;root->m_pLeft = lt;} else {head = root;}if (rh!=NULL) {root->m_pRight=rh;rh->m_pLeft = root;} else {tail = root;}}2.设计包含min 函数的栈。

第1篇一、最基本题型1. 题目：从1到100有多少个9？解答思路：这个问题考察的是对数字的敏感度和基本的数学运算能力。

从1到100的数字中，个位和十位上都会出现9，但要注意100这个数字本身不算在内。

我们可以分别计算个位和十位上出现9的次数，然后将两者相加。

解答过程：- 个位上出现9的次数：9, 19, 29, 39, 49, 59, 69, 79, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99，共18次。

- 十位上出现9的次数：90, 91, 92, 93, 94, 95, 96, 97, 98, 99，共10次。

- 总计：18 + 10 = 28次。

2. 题目：连续整数之和为1000的共有几组？解答思路：这个问题需要我们找出所有可能的连续整数序列，它们的和为1000。

可以通过试错法或者数学公式来解决这个问题。

解答过程：- 通过试错法，我们可以找到以下几组连续整数序列：- 1 + 2 + 3 + ... + 33 = 1000- 2 + 3 + 4 + ... + 34 = 1000- 3 + 4 + 5 + ... + 35 = 1000- ...（以此类推）- 总计：共有33组连续整数序列的和为1000。

二、逻辑推理题3. 题目：一个人从一座桥的一端出发，到另一端需要17分钟。

一次最多可以带一个人过桥，过桥时必须持有手电筒。

四个人过桥，他们的过桥速度分别是1分钟、2分钟、5分钟和10分钟。

如何安排他们的过桥顺序，使得总用时最短？解答思路：这个问题考察的是对时间管理能力的理解和优化策略的制定。

解答过程：- 首先，最慢的三个人（速度为10分钟、5分钟和2分钟）一起过桥，用时2分钟。

- 然后，速度为2分钟的人回来，用时2分钟。

- 接着，速度为1分钟的人过桥，用时1分钟。

- 最后，速度为10分钟和5分钟的人一起过桥，用时5分钟。

- 总用时：2 + 2 + 1 + 5 = 10分钟。

微软的面试题及答案－超变态但是很经典第一组? ???1.烧一根不均匀的绳，从头烧到尾总共需要1个小时。

现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢?2.你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。

抓取多少个就可以确定你肯定有两个同一颜色的果冻?3.如果你有无穷多的水，一个3公升的提捅，一个5公升的提捅，两只提捅形状上下都不均匀，问你如何才能准确称出4公升的水?4.一个岔路口分别通向诚实国和说谎国。

来了两个人，已知一个是诚实国的，另一个是说谎国的。

诚实国永远说实话，说谎国永远说谎话。

现在你要去说谎国，但不知道应该走哪条路，需要问这两个人。

请问应该怎么问?5.12个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。

13个呢?(注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑)6.在9个点上画10条直线，要求每条直线上至少有三个点?7.在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次?都分别是什么时间?你怎样算出来的?8.怎么样种植4棵树木，使其中任意两棵树的距离相等?第二组? ???1.为什么下水道的盖子是圆的?2.中国有多少辆汽车?3.将汽车钥匙插入车门，向哪个方向旋转就可以打开车锁?4.如果你要去掉中国的34个省(含自治区、直辖市和港澳特区及台湾省)中的任何一个，你会去掉哪一个，为什么?5.多少个加油站才能满足中国的所有汽车?6.想象你站在镜子前，请问，为什么镜子中的影象可以颠倒左右，却不能颠倒上下?7.为什么在任何旅馆里，你打开热水，热水都会瞬间倾泻而出?8.你怎样将Excel的用法解释给你的奶奶听?9.你怎样重新改进和设计一个ATM银行自动取款机?10.如果你不得不重新学习一种新的计算机语言，你打算怎样着手来开始?11.如果你的生涯规划中打算在5年内受到奖励，那获取该项奖励的动机是什么?观众是谁?12.如果微软告诉你，我们打算投资五百万美元来启动你的投资计划，你将开始什么样商业计划?为什么?13.如果你能够将全世界的电脑厂商集合在一个办公室里，然后告诉他们将被强迫做一件事，那件事将是什么???第三组? ???1.你让工人为你工作7天，回报是一根金条，这个金条平分成相连的7段，你必须在每天结束的时候给他们一段金条。

1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

10/ \6 14/ \ / \4 8 12 16转换成双向链表4=6=8=10=12=14=16。

首先我们定义的二元查找树节点的数据结构如下：struct BSTreeNode{int m_nValue; // value of nodeBSTreeNode *m_pLeft; // left child of nodeBSTreeNode *m_pRight; // right child of node};ANSWER:This is a traditional problem that can be solved using recursion.For each node, connect the double linked lists created from left and right child node to form a full list./*** @param root The root node of the tree* @return The head node of the converted list.*/BSTreeNode * treeToLinkedList(BSTreeNode * root) {BSTreeNode * head, * tail;helper(head, tail, root);return head;}void helper(BSTreeNode *& head, BSTreeNode *& tail, BSTreeNode *root) { BSTreeNode *lt, *rh;if (root == NULL) {head = NULL, tail = NULL;return;}helper(head, lt, root->m_pLeft);helper(rh, tail, root->m_pRight);if (lt!=NULL) {lt->m_pRight = root;root->m_pLeft = lt;} else {head = root;}if (rh!=NULL) {root->m_pRight=rh;rh->m_pLeft = root;} else {tail = root;}}2.设计包含min 函数的栈。

第9 题判断整数序列是不是二元查找树的后序遍历结果题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。

如果是返回true，否则返回false。

例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：8/ \6 10/ \ / \5 7 9 11因此返回true。

如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。

ANSWER:This is an interesting one. There is a traditional question that requires the binary tree to be re-constructed from mid/post/pre order results. This seems similar. For the problems related to (binary) trees, recursion is the first choice.In this problem, we know in post-order results, the last number should be the root. So we have known the root of the BST is 8 in the example. So we can split the array by the root. int isPostorderResult(int a[], int n) {return helper(a, 0, n-1);}int helper(int a[], int s, int e) {if (e==s) return 1;int i=e-1;while (a[e]>a[i] && i>=s) i--;if (!helper(a, i+1, e-1))return 0;int k = l;while (a[e]<a[i] && i>=s) i--;return helper(a, s, l);}第10 题翻转句子中单词的顺序。

微软的22道数据结构算法面试题（含答案）1、反转一个链表。

循环算法。

1 List reverse(List l) {2 if(!l) return l;3 list cur = l.next;4 list pre = l;5 list tmp;6 pre.next = null;7 while ( cur ) {8 tmp = cur;9 cur = cur.next;10 tmp.next = pre11 pre = tmp;12 }13 return tmp;14 }2、反转一个链表。

递归算法。

1 List resverse(list l) {2 if(!l || !l.next) return l;34 List n = reverse(l.next);5 l.next.next = l;6 l.next=null;7 }8 return n;9 }3、广度优先遍历二叉树。

1 void BST(Tree t) {2 Queue q = new Queue();3 q.enque(t);4 Tree t = q.deque();5 while(t) {6 System.out.println(t.value);7 q.enque(t.left);8 q.enque(t.right);9 t = q.deque();10 }11 }----------------------1class Node {2 Tree t;3 Node next;4 }5class Queue {6 Node head;7 Node tail;8 public void enque(Tree t){9 Node n = new Node();10 n.t = t;11 if(!tail){12 tail = head = n;13 } else {14 tail.next = n;15 tail = n;16 }17 }18 public Tree deque() {19 if (!head) {20 return null;21 } else {22 Node n = head;23 head = head.next;24 return n.t;25 }26}4、输出一个字符串所有排列。