2022年道数据结构算法面试题 .pdf

《2022年道数据结构算法面试题 .pdf》由会员分享，可在线阅读，更多相关《2022年道数据结构算法面试题 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、微软的 22 道数据结构算法面试题（含答案）1、反转一个链表。循环算法。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.

2、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 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 9 页 -11 -1class Node 2 Tree t;3 Node nex

3、t;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

4、 p;2void perm(char s,int i,int n)3 int j;4 char temp;5 for(j=0;jn;+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);名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 9 页 -15 16 sj=pi;17 18 19-1void main()2 char sN;3 sort(s);4 perm(s,0,strlen(s);5 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 isLo

6、op(List l)名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 9 页 -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 ch

7、ar 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;1

8、5 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 9 页 -9、实现 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,

9、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 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 9 页 -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;in;+i)9 u

10、=2*f4(i)+f3(n-i);10 if(umin)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)11 b=b.next;12 else 13 a=a.next;14 pre.next=a;15 16 17 m=h

11、ead.next;18 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 9 页 -14、一个数组，下标从0 到 n，元素为从0 到 n 的整数。判断其中是否有重复元素。1int hasDuplicate(int a,int n)2 for(int i=0;i=0&right=0&left-right=-1)6 return(leftb)?(a+1):(b+1);7 8 17、两个链表，一升一降。合并为一个升序链表。1 List merge(List a,List d)名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 9 页 -2 List a1=reverse(d);

12、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/i10)i*=10;+n 5 char*str=(char*)malloc(n*s

13、izeof(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)名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 9 页 -2 List pre=new List();3 pre.next=head;4 List cur=head;5 while(cur&cur!=node)6 cur=cur.

14、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 名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 9 页 -