微软面试题(数据结构).doc
分析下面的程序，写出结果。void main( )Stack S;Char x,y; InitStack(S);X=c;y=k;Push(S,x);Push(S,'a');Push(S,y);Pop(S,x); Push(S,'t');Push(S,x);Pop(S,x); Push(S,'s');while(!StackEmpty(S) Pop(S,y);printf(y); ;Printf(x);本来这个程序的代码不是很长，而且题意也很清楚，先把元素压栈，然后再出栈即可得到结果：stack刚开始分析到Pop(S,x);时，不明白怎么会从栈中弹出x，按照栈“先进后出”的原则怎么都不可能把元素x弹出栈，.在百思其解不可得时候，终于发现其中的奥秘了：在程序执行到Push(S,y);Pop(S,x);后x=k，然后入栈t，接着x=t，在入栈s，到此程序执行到Push(S,'s');接着用一个循环出栈，得到stac，最后在输入一个k，得到最后的结果：stack Josephus（约瑟夫）问题有n个人围成一个圈，从第1个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，如此反复直到剩下一个人，问此人编号为几？或：有n个人围成一个圈，从第k个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，如此反复直到所有人出列，由此产生一个出队编号的序列。1、数组解法#include<iostream>#include<stdlib.h>using namespace std;const int n=11, m=3;int main() int an,p=0; int i,k=0,number=0; for(i=0; i<n; i+) ai=i+1;while(number<n-1) /number表示出去的人数 if(ap!=0) /p指向正要报数的人 k+; /k为1,2,3.报数 if(k=m) /报到m时，ap出去 ap=0; k=0; number+; p=(p+1) % n; /下一个人 for(i=0; i<n; i+) if(ai!=0) cout<<"最后一个获胜者的编号是："<<i+1<<endl; break; system("pause"); 其中while循环也可改为：while(number<n-1) /number表示出去的人数 while(ap=0) p=(p+1) % n; /找到下一个报数的人 k+; /k为1,2,3.报数 if(k=m) /报到m时，ap出去 ap=0; k=0; number+; p=(p+1) % n;2、链表解法#include<iostream>#include<stdlib.h>using namespace std;const int n=11, m=3;struct node int no;node *next;int main() int k=0;node *p,*q,*r;p=q=new node; /创建第一个节点p->no=1; for(int i=2; i<=n; i+) /建立链表 r=new node; r->no=i; q->next=r; q=r;q->next=p; /构成一个"环" q=p;while(q->next!=q) k+; /k为1,2,3.报数 if(k=m) /报到m时，删除q所指结点 p->next=q->next; delete q; q=p->next; k=0; else p=q; q=q->next; cout<<"最后一个获胜者的编号是："<<q->no<<endl; system("pause");其中while循环也可改为：while(q->next!=q) for(int i=1; i<m; i+) /直接找到报m的人 p=q; q=q->next; p->next=q->next; delete q; q=p->next; 查看文章 微软的22道数据结构算法面试题（含答案）2010-05-11 16:451、反转一个链表。循环算法。 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; 3 4 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、输出一个字符串所有排列。注意有重复字符。 1char p; 2void perm(char s, int i, int n) 3 int j; 4 char temp; 5 for(j=0;j<n;+j) 6 if(j!=0 && sj=sj-1); 7 elseif(sj!='') 8 pi=sj; 9 sj='' 10 if(i=n-1) 11 pn='0' 12 printf("%s", p); 13 else 14 perm(s,i+1,n); 15 16 sj=pi; 17 18 19 - 1void main() 2 char sN; 3 sort(s); 4 perm(s,0,strlen(s); 5 5、输入一个字符串，输出长型整数。 1 long atol(char *str) 2 char *p = str; 3 long l=1;m=0; 4 if (*p='-') 5 l=-1; 6 +p; 7 8 while(isDigit(*p) 9 m = m*10 + p; 10 +p; 11 12 if(!p) return m*l; 13 else return error; 14 6、判断一个链表是否有循环。 1 int isLoop(List l) 2 if ( ! l) return - 1 ; 3 List s = l.next; 4 while (s && s != l) 5 s = s.next; 6 7 if ( ! s) return - 1 ; 8 else reutrn 1 ; 9 - 1int isLoop(List l) 2 if(!l) return 0; 3 p=l.next; 4 wihle(p!=l&&p!=null) 5 l.next=l; 6 l=p;p=p.next; 7 8 if(p=l) return 1; 9 return 0; 10 实际上，在我的面试过程中，还问到了不破坏结构的其他算法。 我的答案是从链表头开始遍历，如果节点next指针指向自身，则循环存在；否则将next指针指向自身，遍历下一个节点。直至next指针为空，此时链表无循环。 7、反转一个字符串。 1 void reverse( char * str) 2 char tmp; 3 int len; 4 len = strlen(str); 5 for ( int i = 0 ;i < len / 2 ; + i) 6 tmp = char i; 7 stri = strlen - i - 1 ; 8 strlen - i - 1 = tmp; 9 10 8、实现strstr函数。 1int strstr(char str, char par) 2 int i=0; 3 int j=0; 4 while(stri && strj) 5 if(stri=parj) 6 +i; 7 +j; 8 else 9 i=i-j+1; 10 j=0; 11 12 13 if(!strj) return i-strlen(par); 14 else return -1; 159、实现strcmp函数。 1int strcmp(char* str1, char* str2) 2 while(*str1 && *str2 && *str1=*str2) 3 +str1; 4 +str2; 5 6 return *str1-*str2; 7 10、求一个整形中1的位数。 1 int f( int x) 2 int n = 0 ; 3 while (x) 4 + n; 5 x &= x - 1 ; 6 7 return n; 8 11、汉诺塔问题。 1void tower(n,x,y,z) 2 if(n=1) move(x,z); 3 else 4 tower(n-1, x,z,y); 5 move(x,z); 6 tower(n-1, y,x,z); 7 8 12、三柱汉诺塔最小步数。 1 int f3(n) 2 if (f3n) return f3n; 3 else 4 if (n = 1 ) 5 f3n = 1 ; 6 return 1 ; 7 8 f3n = 2 * f3(n - 1 ) + 1 ; 9 return f3n; 10 11 四柱汉诺塔最小步数。 1int f4(n) 2 if(f4n=0) 3 if(n=1) 4 f41=1; 5 return 1; 6 7 min=2*f4(1)+f3(n-1); 8 for(int i=2;i<n;+i) 9 u=2*f4(i)+f3(n-i); 10 if(u<min) min=u; 11 12 f4n=min; 13 return min; 14 else return f4n; 15 13、在一个链表中删除另一个链表中的元素。 1void delete(List m, List n) 2 if(!m | !n) return; 3 List pre = new List(); 4 pre.next=m; 5 List a=m, b=n,head=pre; 6 while(a && b) 7 if(a.value < b.value) 8 a=a.next; 9 pre=pre.next; 10 else if(a.value > b.value) 11 b=b.next; 12 else 13 a=a.next; 14 pre.next=a; 15 16 17 m=head.next; 1814、一个数组，下标从0到n，元素为从0到n的整数。判断其中是否有重复元素。 1int hasDuplicate(int a, int n) 2 for(int i=0;i<n;+i) 3 while(ai!=i && ai!=-1) 4 if(aai=-1) return 1; 5 ai=aai; 6 aai=-1; 7 8 if(ai=i) ai=-1; 9 10 return 0; 11 15、判断一颗二叉树是否平衡。 1int isB(Tree t) 2 if(!t) return 0; 3 int left=isB(t.left); 4 int right=isB(t.right); 5 if( left >=0 && right >=0 && left - right <= 1 | left -right >=-1) 6 return (left<right)? (right +1) : (left + 1); 7 else return -1; 8 9 16、返回一颗二叉树的深度。 1int depth(Tree t) 2 if(!t) return 0; 3 else 4 int a=depth(t.right); 5 int b=depth(t.left); 6 return (a>b)?(a+1):(b+1); 7 8 17、两个链表，一升一降。合并为一个升序链表。 1 List merge(List a, List d) 2 List a1 = reverse(d); 3 List p = q = new List(); 4 while ( a && a1 ) 5 if (a.value < a1.value) 6 p.next = a; 7 a = a.next; 8 else 9 p.next = a1; 10 a1 = a1.next; 11 12 p = p.next; 13 14 if (a) p.next = a; 15 elseif(a1) p.next = a1; 16 return q.next; 17 18、将长型转换为字符串。 1char* ltoa(long l) 2 charN str; 3 int i=1,n=1; 4 while(!(l/i<10)i*=10;+n 5 char* str=(char*)malloc(n*sizeof(char); 6 int j=0; 7 while(l) 8 strj+=l/i; 9 l=l%i; 10 i/=10; 11 12 return str; 13 19、用一个数据结构实现 1 if (x = 0) y = a; 2 else y = b; 1 j = a,b; 2 y=jx; 20、在双向链表中删除指定元素。 1void del(List head, List node) 2 List pre=new List(); 3 pre.next = head; 4 List cur = head; 5 while(cur && cur!=node) 6 cur=cur.next; 7 pre=pre.next; 8 9 if(!cur) return; 10 List post = cur.next; 11 pre.next=cur.next; 12 post.last=cur.last; 13 return; 14 21、不重复地输出升序数组中的元素。 1 void outputUnique( char str, int n) 2 if (n <= 0 ) return ; 3 elseif(n = 1 ) putchar(str 0 ); 4 else 5 int i = 0 ,j = 1 ; 6 putchar(str 0 ); 7 while (j < n) 8 if (strj != stri) 9 putchar(strj); 10 i = j; 11 12 + j; 13 14 15 22、面试过程中我还遇到了下面几题： 1、如何删除链表的倒数第m的元素？我的方法是先用pre指针从链表头开始步进m，新建pst节点next指针指向头节点，cur指针指向头节点，然后pre，cur，post三个指针一起步进，当pre指向链表结尾的时候cur指向倒数第m个元素，最后利用pst指针删除cur指向元素。 2、如何判断一个字符串是对称的？如a，aa，aba。设置头尾指针同时向中间比较靠齐直至相遇。 3、如何利用2函数找出一个字符串中的所有对称子串？以子串头指针和尾指针为循环变量设置两个嵌套的循环以找出所有子串，对每个子串应用2函数。 数据结构表达式求值（堆栈）2010-05-18 21:29数据结构表达式求值（堆栈）作者：pearry 时间：10.5.17限于二元运算符的表达式定义：表达式：（操作数）+（运算符）+（操作数）操作数：简单变量|表达式简单变量：标识符|无符号整数在计算机中，表达式可以有三中不同的标识方法设 Exp S1 + OP + S2则，称 op + S1 + S2 为表达式的 “前缀表达式”称 S1 + OP + S2 为表达式的 “中缀表达式”称 S1 + S2 + OP 为表达式的 “后缀表示法”可见，它以运算符所在不同位置命名的。例如： Exp a * b + （c d/e）*f前缀式： + * a b * c / d e f 中缀式： a * b + c - d / e * f后缀式： a b * c d e / - f * +结论： 2）运算符的相对次序不同； 3）中缀式丢去了括弧信息，致使运算次序不正确； 4）前缀式的运算规则为： 连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式； 5）后缀式的运算规则为： 运算符在式中出现的顺序恰为表达式的运算顺序； 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式；由上面可知，后缀式最适合表达式运算的，实际上大多数编译器上用的也是后缀式。那么如何用后缀式求值？后缀式操作的规则： 先找运算符，再找操作数。也就是碰到操作数，保留，碰到运算符，就运算，运算后结果保留在前操作数位置。根据操作的规则，自然能想到用栈来存取。下面来演示下上面的例子：例： Exp a * b + （c d/e）*f;后缀式： a b * c d e / - f * +;入栈顺序：a b * c d e / - f * +;1.a入栈，b入栈；2.遇到“*”操作符，运算“a*b”表达式，保留在a（前操作数）的位置；3.c，d，e，依次进栈；4.遇到“/”操作符，执行“d/e”运算（最近的两个操作数），存入d的位置；5.遇到“”操作符，将c与d位置的值（设为x）执行“cx”运算，存入c，（设为y）；6.f入栈；7.遇到“*”操作符，执行“y*f”运算（设为z），存入y的位置；8.遇到“+”操作符，执行“a+z”运算，存入a位置；9.运算结束，退栈，输出结果；OK，现在解决了如行用后缀式求值，One more thing ：如何得到后缀式表达式。遇到问题我们就要解决。问：如何从 原表达式 求得 后缀式 ？分析：我们看下“原表达式”跟“后缀式”的运算符变化规则：原表达式： a + b * c d / e * f ;后缀式： a b c * d e / f * - ;of course， 变化规则是离不开我们所学的“先加减，后乘除”的。我们要做的就是把操作数按原顺序排列，操作符按“先加减，后乘除”排列First of fist,我们碰到第一个操作符的时候不能确定是否就运算了。例如：a + b * c；大家都知道是先“*”，再“+”；so，先将“a+b”，转换为“ab+”，碰到“*”，排在“+”之前，为“a b c* +”。然而，这时候我们还是不能判断是否就执行“*”操作了，Couse，“*”并不是最高级别的运算符，所以我们再读取原表达式，我们得知下一个为“”操作符，优先级低于“*”，这是我们才能执行“*”操作，故这时才能确定的把“*”存入后缀式。“+”在“”之前，也存入后缀式，至于“”是否存入呢？我们接着往下看。接着往下看，我们发现后面还有“/”操作，显然“”操作得排在“/”之后。我们还是按照上一步中方法，先排列操作数，在遵循“先加减，后乘除”规则进行对操作符。当然，“括弧”内的优先级更高。遇到“括弧”，括弧内的操作符号比外面的高，然后“括弧”内的操作符还是按照“先加减，后乘除”的规则排列。综上所述，得到规律：1)设立操作数栈；2）设表达式的结束符为“#”，予设运算符栈的栈底为“#”；3）若当前字符是操作数，则直接发给后缀式；4）若当前运算符的优先级高于栈顶运算符，则进栈；5）否则，退出栈顶运算符发送给后缀式；6）“（”对它前后的运算符起隔离作用(执行进栈操作)，“）”可视为自相应左括弧开始的表达式结束。伪代码如下：void transform(char suffix, char exp) InitStack(s); Push(S,'#'); /入栈 p = exp; ch = *p; while ( !StackEmpty( S ) ) /判断输入 if ( !IN( ch , OP ) ) Pass(Suffix,ch);/不是操作符则为操作数 else seitch( ch ) /判断操作符 case "(" : Push (S,ch); break; case ")" : if(ch!='#') p +; ch = *p; /遇到#退出
