22道数据结构算法面试题.doc

HYPERLINK"http://www.cnblogs.com/henryhu/archive/2010/02/20/1669939.html"微软的22道数据结构算法面试题（含答案）
1、反转一个链表。循环算法。1Listreverse(Listl){2if(!l)returnl;3listcur=l.next;4listpre=l;5listtmp;6pre.next=null;7while(cur){8tmp=cur;9cur=cur.next;10tmp.next=pre;11pre=tmp;12}13returntmp;14}2、反转一个链表。递归算法。1Listresverse(listl){2if(!l||!l.next)returnl;34Listn=reverse(l.next);5l.next.next=l;6l.next=null;7}8returnn;9}3、广度优先遍历二叉树。1voidBST(Treet){2Queueq=newQueue();3q.enque(t);4Treet=q.deque();5while(t){6System.out.println(t.value);7q.enque(t.left);8q.enque(t.right);9t=q.deque();10}11}----------------------1classNode{2Treet;3Nodenext;4}5classQueue{6Nodehead;7Nodetail;8publicvoidenque(Treet){9Noden=newNode();10n.t=t;11if(!tail){12tail=head=n;13}else{14tail.next=n;15tail=n;16}17}18publicTreedeque(){19if(!head){20returnnull;21}else{22Noden=head;23head=head.next;24returnn.t;25}26}
4、输出一个字符串所有排列。注意有重复字符。1char[]p;2voidperm(chars[],inti,intn){3intj;4chartemp;5for(j=0;j<n;++j){6if(j!=0&&s[j]==s[j-1]);7elseif(s[j]!='@'){8p[i]=s[j];9s[j]='@';10if(i==n-1){11p[n]='\0';12printf("%s",p);13}else{14perm(s,i+1,n);15}16s[j]=p[i];17}18}19}--------------------------1voidmain(){2chars[N];3sort(s);4perm(s,0,strlen(s));5}5、输入一个字符串，输出长型整数。1longatol(char*str){2char*p=str;3longl=1;m=0;4if(*p=='-'){5l=-1;6++p;7}8while(isDigit(*p)){9m=m*10+p;10++p;11}12if(!p)returnm*l;13elsereturnerror;14}6、判断一个链表是否有循环。1intisLoop(Listl){2if(!l)return-1;3Lists=l.next;4while(s&&s!=l){5s=s.next;6}7if(!s)return-1;8elsereutrn1;9}-----------1intisLoop(Listl){2if(!l)return0;3p=l.next;4wihle(p!=l&&p!=null){5l.next=l;6l=p;p=p.next;7}8if(p=l)return1;9return0;10}实际上，在我的面试过程中，还问到了不破坏结构的其他算法。我的答案是从链表头开始遍历，如果节点next指针指向自身，则循环存在；否则将next指针指向自身，遍历下一个节点。直至next指针为空，此时链表无循环。7、反转一个字符串。1voidreverse(char*str){2chartmp;3intlen;4len=strlen(str);5for(inti=0;i<len/2;++i){6tmp=char[i];7str[i]=str[len-i-1];8str[len-i-1]=tmp;9}10}8、实现strstr函数。1intstrstr(char[]str,char[]par){2inti=0;3intj=0;4while(str[i]&&str[j]){5if(str[i]==par[j]){6++i;7++j;8}else{9i=i-j+1;10j=0;