微软面试一百道题目精选.docx

第9题判断整数序列是不是二元查找树的后序遍历结果题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:8/\610/\/\57911因此返回true。如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。ANSWER:-constructedfrommid/post/(binary)trees,recursionisthefirstchoice. Inthisproblem,weknowinpost-orderresults,. intisPostorderResult(inta[],intn){ returnhelper(a,0,n-1);}inthelper(inta[],ints,inte){ if(e==s)return1; inti=e-1; while(a[e]>a[i]&&i>=s)i--; if(!helper(a,i+1,e-1))   return0; intk=l; while(a[e]<a[i]&&i>=s)i--; returnhelper(a,s,l);}第10题翻转句子中单词的顺序。题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。例如输入“Iamastudent.”,则输出“”。Answer:...如果我们把二叉树看成一个图,父子节点之间的连线看成是双向的,我们姑且定义"距离"为两节点之间边的个数。写一个程序,求一棵二叉树中相距最远的两个节点之间的距离。ANSWER:Thisisinteresting...Alsorecursively,thelongestdistancebetweentwonodesmustbeeitherfromroottooneleaf,,it’,itshouldbethesumoftheheightsofleftandrightsubtreesofthetwoleaves’,justtheheight+(Node*root){ intdepth; returnhelper(root,depth);}inthelper(Node*root,int&depth){ if(root==NULL){   depth=0;return0; } intld,rd; intmaxleft=helper(root->left,ld); intmaxright=helper(root->right,rd); depth=max(ld,rd)+1; returnmax(maxleft,max(maxright,ld+rd));}第12题题目:求1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句(A?B:C)。ANSWER:1+..+n=n*(n+1)/2=(n^2+n)/2itiseasytogetx/2,sotheproblemistogetn^2thoughnoif/elseisallowed,wecaneasillygoaroundusingshort-:#define T(X,Y,i)(Y&(1<<i))&&X+=(Y<<i)intfoo(intn){ intr=n; T(r,n,0);T(r,n,1);T(r,n,2);…T(r,n,31); returnr>>1;}第13题:题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下:s