版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
微软的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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高中地理必修二《世界主要语言及其分布》教学设计
- 初中地理九年级《地球与地球仪》一轮复习教学设计
- 小学四年级英语上册Unit 3 Places we live in Part B Let's talk Let's learn教学设计
- 高中信息技术必修一 文本数据处理 教学设计 基于真实情境的数据清洗与重组实践
- 初中八年级地理黄河调水调沙专题复习教学设计
- 高中英语必修三Unit 4 Amazing art单元首课教学设计
- 九年级化学教学设计:物质变化的实证路径与科学探究首课
- 小学二年级劳动教学设计《自制课程表》时间管理与生活规划实践
- 高中体育与健康必修模块足球选位与盯人教学设计
- 2027年高中地理必修二《人口分布》教学设计:空间规律与区域差异的深度解析
- 2025年中级经济师考试中级保险专业真题及答案
- 学堂在线 高级医学英语 章节测试答案
- 法学派出所实习个人总结
- 高内涵细胞分析系统应用
- 玩偶之家-完整版
- 中国传统文化的海外传播策略研究
- 花之舞 高清钢琴谱五线谱
- 沟通的艺术学习通超星期末考试答案章节答案2024年
- JBT 14910-2024《剪切销安全联轴器》
- 绘本爸爸的手影戏
- GB/T 5356-2021内六角扳手
评论
0/150
提交评论