[第一部分]精选微软等公司数据结构+算法经典面试100题[1-40题]

《[第一部分]精选微软等公司数据结构+算法经典面试100题[1-40题]》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、[第一部分]精选微软等公司数据结构+算法经典面试100题[1-40题]本人自学c++近一年，对算法尤其感兴趣。此为我个人自己搜集整理的，精选微软等大公司，有关数据结构和算法，面试100题之前40题。如果你对以下的前40题，有好的思路，和算法，欢迎跟帖回复，或者，联系我，发至我的邮箱，zhoulei0907@yahoo.cn。若想得到这40题的思路，源码和解决方案，也请联系我。MyCSDNBlog：http://blog.csdn.net/v_JULY_vMysinaBlog：http://blog.sina.com.cn/shitou009帖子维护

2、地址：1.算法面试：精选微软经典的算法面试100题[每周更新](已结贴)http://topic.csdn.net/u/20101011/16/2befbfd9-f3e4-41c5-bb31-814e9615832e_5.html2.[整理]算法面试：精选微软经典的算法面试100题[前40题]http://topic.csdn.net/u/20101023/20/5652ccd7-d510-4c10-9671-307a56006e6d.html3.[总帖]精选微软等公司，结构+算法面试100题（前40题）http://topic.csdn.net/

3、u/20101023/20/75a0ba48-6dd3-475c-8672-5a352a27c66a.htmlJuly、2010/10/23。1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10/614//481216转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下：structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftch

4、ildofnodeBSTreeNode*m_pRight;//rightchildofnode};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

5、。4.在二元树中找出和为某一值的所有路径题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数22和如下二元树10/512/47则打印出两条路径：10,12和10,5,7。二元树节点的数据结构定义为：structBinaryTreeNode//anodeinthebinarytree{intm_nValue;//valueofnodeBinaryTreeNode*m_pLeft;//leftchildofnodeBinaryTreeNode*m_pRigh

6、t;//rightchildofnode};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】初看此题，貌似很难，10分钟过去了，可能有的人，题目都还没看懂。举一个例子，数值:0,1,2,3,4

7、,5,6,7,8,9分配:6,2,1,0,0,0,1,0,0,00在下排出现了6次，1在下排出现了2次，2在下排出现了1次，3在下排出现了0次....以此类推..昨天，用c++实现了此题。(*^__^*)第7题------------------------------------微软亚院之编程判断俩个链表是否相交给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。为了简化问题，我们假设俩个链表均不带环。问题扩展：1.如果链表可能有环列?2.如果需要求出俩个链表相交的第一个节点列?第8题------------------------

8、------------此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。1.有两个房间，