面试--微软面试100题全部答案.docx

《面试--微软面试100题全部答案.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本文转载自CSDN大牛的一篇博客：http://blog.csdn.net/v_july_v/article/details/6870251作者：July、阿财时间：二零一一年十月十三日。我能够看到此文，还要多谢陈同学！让我得以及时分享给大家微软面试100题全部答案个人整理的前60题的答案可参见以下三篇文章：1.微软100题第1题-20题答案http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6126406.aspx[博文I]2.微软100题第21-40题答案http://blog.csd

2、n.net/v_JULY_v/archive/2011/01/10/6126444.aspx[博文II]3.微软100题第41-60题答案http://blog.csdn.net/v_JULY_v/archive/2011/02/01/6171539.aspx[博文III]最新整理的全部100题的答案参见如下（重复的，以及一些无关紧要的题目跳过）：1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10/614//481216转换成双向

3、链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下：structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};ANSWER:Thisisatraditionalproblemthatcanbesolvedusingrecursion.Foreachnode,connectthedoublelinkedlistscreatedfr

4、omleftandrightchildnodetoformafulllist./***@paramrootTherootnodeofthetree*@returnTheheadnodeoftheconvertedlist.*/BSTreeNode*treeToLinkedList(BSTreeNode*root){BSTreeNode*head,*tail;helper(head,tail,root);returnhead;}voidhelper(BSTreeNode*&head,BSTreeNode*&tail,BSTreeNode

5、*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函

6、数的栈。定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。ANSWER:StackisaLIFOdatastructure.Whensomeelementispoppedfromthestack,thestatuswillrecovertotheoriginalstatusasbeforethatelementwaspushed.Sowecanrecovertheminimumelement,too.structMinStackElement{intdata;i

7、ntmin;};structMinStack{MinStackElement*data;intsize;inttop;}MinStackMinStackInit(intmaxSize){MinStackstack;stack.size=maxSize;stack.data=(MinStackElement*)malloc(sizeof(MinStackElement)*maxSize);stack.top=0;returnstack;}voidMinStackFree(MinStackstack){free(stack.data);}

8、voidMinStackPush(MinStackstack,intd){if(stack.top==stack.size)error(“outofstackspace.”);MinStackElement*p=stac