微软面试100题系列

《微软面试100题系列》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、微软面试100题系列　　1.把二元查找树转变成排序的双向链表　　题目：　　输入一棵二元查找树，将该转换成个排序的双向链表。　　要求不能创建任何新的结点，只调整指针向。　　10　　/　　614　　//　　481216　　转换成双向链表　　4=6=8=10=12=14=16　　首先我们定义的二元查找树节点的数据结构如下：　　viewplaincopystructBSTreeNode　　{　　intm_nValue;//valueofnode　　BSTreeNode*m_pLeft;//leftchildofnode　　BSTreeNode*m_pRi

2、ght;//rightchildofnode　　};　　解答：　　这是一个可以使用递归的传统问题。显然可以使用中序遍历(左-根-右)。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。　　viewplaincopyBSTreeNode*pHead=NULL;　　BSTreeNode*pListIndex=NULL;　　//遍历二元查找树中序　　voidergodicBSTree(

3、BSTreeNode*pCurrent)　　{　　if(NULL==pCurrent){　　return;　　}　　if(NULL!=pCurrent->m_pLeft){　　ergodicBSTree(pCurrent->m_pLeft);　　}　　//节点接到链表尾部　　convertToDoubleList(pCurrent);　　//右子树为空　　if(NULL!=pCurrent->m_pRight){　　ergodicBSTree(pCurrent->m_pRight);　　}　　}　　//二叉树转换成list　　voidconver

4、tToDoubleList(BSTreeNode*pCurrent)　　{　　pCurrent->m_pLeft=pListIndex;　　if(NULL!=pListIndex){　　pListIndex->m_pRight=pCurrent;　　}else{　　pHead=pCurrent;　　}　　pListIndex=pCurrent;　　cout　　}　　2.设计包含min函数的栈。定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。　　ANSWER:　　Stack

5、isaLIFOdatastructure.Whensomeelementispoppedfromthestack,thestatuswillrecovertotheoriginalstatusasbeforethatelementwaspushed.Sowecanrecovertheminimumelement,too.　　viewplaincopy#defineSTACK_LEN50　　typedefstruct　　{　　intval;　　intmin;　　}stack_item;　　typedefstruct　　{　　stack_itemda

6、ta;　　inttop;　　}stack;　　voidpush(stack*stk,intval)　　{　　stk->data.val=val;　　if(stk->top>0)　　{　　if(valdata.min)　　//如果当前push进的元素小于栈中最小元素　　stk->data.min=val;//把当前元素置为栈中最小元素　　else　　//否则，不更新　　stk->data.min=stk->data.min;　　}　　else　　stk->data.min=val;　　}　　intpop(stack*stk)　　{　　returns

7、tk->data.val;　　}　　intmin(stack*stk)　　{　　returnstk->data.min;　　}　　3.求子数组的最大和　　题目：　　输入一个整形数组，数组里有正数也有负数。　　数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。　　求所有子数组的和的最大值。要求时间复杂度为O(n)。　　例如输入的数组为1,-2,3,10,-4,7,2,-5，和最大的子数组为3,10,-4,7,2，　　因此输出为该子数组的和18。　　ANSWER:　　Atraditionalgreedyapproach.　　Keepcu

8、rrentsum,slidefromlefttoright,whensum　　viewplaincopyintmaxSubarray(i