微软的22道数据结构算法面试题(含答案)_第1页
微软的22道数据结构算法面试题(含答案)_第2页
微软的22道数据结构算法面试题(含答案)_第3页
微软的22道数据结构算法面试题(含答案)_第4页
微软的22道数据结构算法面试题(含答案)_第5页
已阅读5页,还剩4页未读, 继续免费阅读

下载本文档

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

文档简介

微软的22道数据结构算法面试题(含答案)

1、反转一个链表。循环算法。

1Listreverse(ListI){

2if(!l)returnI;

3listcur=I.next;

4listpre=I;

5listtmp;

6pre.next=null;

7while(cur){

8tmp=cur;

9cur=cur.next;

10tmp.next=pre

11pre=tmp;

12)

13returntmp;

14}

2、反转一个链表。递归算法。

1Listresverse(listI){

2if(!l||ll.next)returnI;

3

4Listn=reverse(Lnext);

5Lnext.next=I;

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{

14taiI.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){

6if0!=O&&sO]==sO-1]);

7elseif(sO]!='@'){

8p[i]=sO];

9sO]='@';

10if(i==n-1){

11p[n]='\0,;

12printf(n%sn,p);

13}else{

14perm(s,i+1,n);

15)

16sU]=p[i];

17)

18)

19}

1voidmain(){

2chars[N];

3sort(s);

4perm(s,O,strlen(s));

5)

5、输入一个字符串,输出长型整数。

1longatol(char*str){

2char*p=str;

3longl=1;m=0;

4if(*P=='J){

5l=-1;

6++p;

7}

8while(isDigit(*p)){

9m=m*10+p;

10++p;

11)

12if(!p)returnm*l;

13elsereturnerror;

14}

6、判断一个链表是否有循环。

1intisLoop(ListI){

2if(!I)return-1

3Lists=I.next;

4while(s&&s!=I)

5ss.next;

6)

7if(!s)return-1

8elsereutrn1;

9)

lintisLoop(Listl){

2if(!l)return0;

3p=Lnext;

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}

W)

8、实现strstr函数。

lintstrstr(char[]str,char[]par){

2inti=0;

3intj=0;

4while(str[i]&&str[j]){

5if(str[i]==parO]){

6++i;

7++j;

8}else{

9i=H+1;

10j=0;

11)

12)

13if(!strO])returni-strlen(par);

14elsereturn-1;

15)

9、实现strcmp函数。

lintstrcmp(char*str1,char*str2){

2while(*str1&&*str2&&*str1==*str2){

3++str1;

4++str2;

5}

6return*str1-*str2;

7}

10、求一个整形中1的位数。

1intf(intx){

2intn=0;

3while(x){

4++n;

5x&=x-1;

6}

7returnn;

8)

11、汉诺塔问题。

1voidtower(n,x,y,z){

2if(n==1)move(x,z);

3else{

4tower(n-1,x,z,y);

5move(x,z);

6tower(n-1,y,x,z);

7}

8)

12、三柱汉诺塔最小步数。

1intf3(n){

2if(f3[nl)returnf3[n];

3se

el

4m

5

f3[n

6

return1

7

)

8f3[n]=2*f3(n1+1

9returnf3[n];

10)

11)

四柱汉诺塔最小步数。

lintf4(n){

2if(f4[n]==0){

3if(n==1){

4f4[1]==1;

5return1;

6)

7min=2*f4(1)+f3(n-1);

8for(inti=2;ivn;++i){

9u=2*f4(i)+f3(n-i);

10if(u<min)min=u;

11)

12f4[n]=min;

13returnmin;

14)elsereturnf4[n];

15)

13、在一个链表中删除另一个链表中的元素。

1voiddelete(Listm,Listn){

2if(!m||!n)return;

3Listpre=newList();

4pre.next=m;

5Lista=m,b=n,head=pre;

6while(a&&b){

7if(a.value<b.value){

8a=a.next;

9pre=pre.next;

10}elseif(a.value>b.value){

11b=b.next;

12}else{

13a=a.next;

14pre.next=a;

15)

16)

17m=head.next;

18)

14、一个数组,下标从。到n,元素为从。到n的整数。判断其中是否有重复元素。

linthasDuplicate(int[]a,intn){

2for(inti=0;i<n;++i){

3while(a[i]!=i&&a[i]!=-1){

4if(a[a[i]]==-1)return1;

5a[i]=a[a[i]];

6a[a[i]]=-1;

7)

8if(a[i]==i){a[i]=-1;}

9)

10return0;

11}

15、判断一颗二叉树是否平衡。

lintisB(Treet){

2if(!t)return0;

3intleft=isB(t.left);

4intright=isB(t.right);

5if(left>=0&&right>=0&&left-right<=1||left-right

>=-1)

6return(left<right)?(right+1):(left+1);

7elsereturn-1;

8}

9

16、返回一颗二叉树的深度。

lintdepth(Treet){

2if(!t)return0;

3else{

4inta=depth(t.right);

5intb=depth(t.left);

6return(a>b)?(a+1):(b+1);

7

8}

17、两个链表,一升一降。合并为一个升序链表。

1Listmerge(Lista,Listd)

2Lista1=reverse(d);

3Listp=q=newList();

4while(a&&a1){

5if(a.value<a1.value){

6p.next=a;

7a=a.next;

8}else{

9p.next=a1;

10a1=al.next;

11)

12p=p.next;

13)

14if(a)p.next=a;

15elseif(al)p.next=a1;

16returnq.next;

17)

18、将长型转换为字符串。

1char*ltoa(longl){

2char[N]str;

3inti=1,n=1;

4while(!(l/i<10)){i*=10;++n}

5char*str=(char*)malloc(n*sizeof(char));

6intj=0;

7while(l){

8str[j++]=l/i;

9l=l%i;

10i/=10;

11)

12returnstr;

13)

19、用一个数据结构实现

1if(x==0)y=a;

2elsey=b;

1JO={a,b};

2y=j[x];

20、在双向链表中删除指定元素。

1voiddel(Listhead,Listnode){

2Listpre=newList();

3pre.next=head;

4Listcur=head;

5while(cur&&cur!=node){

6cur=cur.next;

7pre=pre.next;

8)

9if(!cur)return;

10Listpost=cur.next;

11pre.next=cur.next;

12post.last=cur.last;

13return;

14}

21、不重复地输出升序数组中的元素。

1voidoutputUnique(char[]str,intn)

2if(n<=0

温馨提示

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

评论

0/150

提交评论