22道数据结构算法面试题_第1页
22道数据结构算法面试题_第2页
22道数据结构算法面试题_第3页
22道数据结构算法面试题_第4页
22道数据结构算法面试题_第5页
免费预览已结束,剩余7页可下载查看

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、微软的22道数据结构算法面试题(含答案)1、反转一个链表。循环算法1 Listreverse(Listl)2 if(!l)returnl;3 listcur=l.next;4 listpre=l;5 listtmp;6 pre.next=null;7 while(cur)8 tmp=cur;9 cur=cur.next;10 tmp.next=pre;11 pre=tmp;12 13 returntmp;14 2、反转一个链表。递归算法。1 Listresverse(listl)2 if(!l|!l.next)returnl;34 Listn=reverse(l.next);5 l.next.

2、next=l;6 l.next=null;7 8 returnn;9 10 广度优先遍历二叉树。1 voidBST(Treet)2 Queueq=newQueue();3 q.enque(t);4 Treet=q.deque();5 while(t)6 System.out.println(t.value);7q.enque(t.left);6789101112131415161718192021228q.enque(t.right);9t=q.deque();10)11)IclassNode2Treet;3Nodenext;4)5classQueueNodehead;Nodetail;pub

3、licvoidenque(Treet)Noden=newNode();n.t=t;if(!tail)tail=head=n;elsetail.next=n;tail=n;publicTreedeque()if(!head)returnnull;elseNoden=head;23head=head.next;24returnn.t;25264、输出一个字符串所有排列。注意有重复字符1char口p;2voidperm(chars,inti,intn)3intj;4chartemp;5for(j=0;jn;+j)6if(j!=0&sj=sj-1);7elseif(sj!=)8pi=sj;9sj=;1

4、0if(i=n-1)11pn=0;12printf(%s,p);13else14perm(s,i+1,n);15 16 sj=pi;17 18 191voidmain()2 charsN;3 sort(s);4perm(s,0,strlen(s);55、输入一个字符串,输出长型整数longatol(char*str)234567891011 12 if(!p)13 else14char*p=longl=1;m=0;if(*p=-)l=-1;+p;while(isDigit(*p)+p;returnm*l;returnerror;p;6、判断一个链表是否有循环。1intisLoop(List2

5、if(!l)3 Lists=4 while(s5 s=l)return-1;l.next;&s!=l)s.next;if(!s)returnelsereutrn1;1int2345678910)实际上,isLoop(Listl)if(!l)return0;p=l.next;wihle(p!=l&p!=null)l.next=l;l=p;p=p.next;)if(p=l)returnreturn1;0;在我的面试过程中,还问到了不破坏结构的其他算法。我的答案是从链表头开始遍历,如果节点next指针指向自身,则循环存在;否则将next指针指向自身,遍历下一个节点。直至循环。next指针为空,此时链

6、表无7、反转一个字符串。12345)678910)voidreverse(charcharintlenforstr)8、实现strstrtmp;len;strlen(str);(inti=0tmpstristrlen函数。;ilen/2;+chari;strleni-1-1;tmp;1int2345678910strstr(charstr,inti=0;intj=0;while(stri&charpar)strj)if(stri=parj)+i;+j;)elsei=i-j+1;j=0;11 )12 )13 if(!strj)returni-strlen(par);14 elsereturn-1

7、;15 )9、实现strcmp函数。1intstrcmp(char*str1,char*str2)=*str2)2 while(*str1&*str2&*str13 +str1;4 +str2;5 )6 return*str1-*str2;7 )10、求一个整形中1的位数。1 intf(intx)2 intn=0;3 while(x)4 +n;5 x&=x-16 )7 returnn;8 )11、汉诺塔问题。1voidtower(n,x,y,z)2if(n=1)move(x,z);3else4tower(n-1,x,z,y);5move(x,z);6tower(n-1,y,x,z);7)8)1

8、2、三柱汉诺塔最小步数。1intf3(n)2if(f3n)returnf3n;34567891011)elseif(n=1)f3n=1;return1;)f3n=2*f3(n-1returnf3n;)13、四柱汉诺塔最小步数1intf4(n)2if(f4n=0)3if(n=1)4f41=1;567891011121314 )15 )return1;)min=2*f4(1)+f3(n-1);for(inti=2;in;+i)u=2*f4(i)+f3(n-i);if(umin)min=u;)f4n=min;returnmin;elsereturnf4n;14、在一个链表中删除另一个链表中的元素1v

9、oid234567891011121314delete(Listm,Listn)if(!m|!n)return;Listpre=newList();pre.next=m;Lista=m,b=n,head=pre;while(a&b)if(a.valueb.value)b=b.next;)elsea=a.next;pre.next=a;15)16)17m=head.next;18)15、一个数组,下标从0到n,元素为从0到n的整数。判断其中是否有重复元素。1inthasDuplicate(inta,intn)234567891011)for(inti=0;i=0&right=0&left-rig

10、ht=-1)6return(leftb)?(a+1):(b+1);1234567891011121314151617)18、两个链表,一升一降。合并为一个升序链表Listmerge(Lista,Listd)Lista1=reverse(d);Listp=q=newList();while(a&a1)if(a.valuea1.value)p.next=a;a=a.next;elsep.next=a1;a1=a1.next;p=p.next;if(a)p.next=a;elseif(a1)p.next=a1;returnq.next;19、将长型转换为字符串。1char*ltoa(longl)2

11、charNstr;3 inti=1,n=1;4while(!(l/i10)i*=10;+n5 char*str=(char*)malloc(n*sizeof(char);6 intj=0;7 while(l)8 strj+=l/i;9 l=l%i;10 i/=10;11 12 returnstr;1320、用一个数据结构实现1 if(x=0)y=a;2 elsey=b;1 j口=a,b;2 y=jx;21、在双向链表中删除指定元素Ivoiddel(Listhead,Listnode)2 Listpre=newList();3 pre.next=head;4 Listcur=head;5 while(cur&cur!=node)6 cur=cur.next;7 pre=pre.next;8 9 if(!cur)return;10 Listpost=cur.next;11 pre.next=cur.next;12 post.last=cur.last;13 return;14

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论