数据结构算法面试题

《数据结构算法面试题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、微软的22道数据结构算法Ifli试题（含答案）反转一个链表。循环算法。Listreverse(ListI){if(!l)returnI;listcur=l.next;listpre=I;listtmp;pre.next=null;while(cur){tmp=cur;cur=cur.next;tmp.next=prepre=tmp;}returntmp;}反转一个链表。递归算法。Listresverse(listI){if(!l11ll.next)returnI;Listn=reverse(l.next);I.next.next=I;l.next=null;}returnn;广度优先遍历

2、二叉树。voidBST(Treet){Queueq=newQueue();q.enque(t);Treet=q.deque();while(t){System.out.println(t.value);8910q.enque(t.left);q.enque(t.right);t=q.deque();11}1classNode{2Treet;3Nodenext;4}5classQueue{6Nodehead;7Nodetail;8publicvoidenque(Treet){9Noden=newNode();10n.t=t;11if(!tail){12tail=head=n;13}else

3、{14tail.next==n;15tail=n:BJ16}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

4、=n-1){11p[n]=,,;12printf(H%sH,p);13}else{14perm(s,i+1,n);3}4s[j]=p[i];5}6}19}1voidmain(){2chars[N];3sort(s);4perm(s,O,strlen(s));5}5、输入一个字符串，输出长型整数。12longatol(char*str){str;char*P=3longl=1;m=0；4if(*p==,-f){5l=-1;6++p;7}8while(isDigit(*p)){9m=m*10+p;10++p;11}12if(!p)returnm*l;13elsereturnerror;1

5、4}6、判断一个链表是否有循环。1intisLoop(ListI){2if(!I)return・13Lists=I.next;4while(S&&s!=I)5s=s.next;6}7if(!s)return・18elsereutrn1;9}1intisLoop(Listl){1if(!l)return0;2p=Lnext;3wihle(p!=l&&p!=null){4l.next=I;51=p;p=p.next;6}7if(p=I)return1;8return0;10}实际上，在我的面试过程屮，还问到了不破坏结构的其他算法。我的答案是从链表头开始遍历，如果节点next指针指向自身，则循

6、环存在；否则将next指针指向自身，遍历下一个节点。直至next指针为空，此吋链表无循环。7、反转一个字符串。1voidreverse(char*str){2chartmp;3intlen;4len=strlen(str);5for(inti=0;i

7、{6++i；7++j；8}else{9i=i-j+1；10j=o；11}12}13if(!str[j])returni-strlen(par);14elsereturn15}9、实现strcmp函数。lintstrcmp(char*str1,char*str2){2while(*str1&&*str2&&*str1==*str2){3++str1;4++str2;5}6return*str1-*str2;7}10、求一个整形中1的位