22道數(shù)據(jù)結構算法面試題

1、微軟的 22 道數(shù)據(jù)結構算法面試題（含答案）1 、反轉一個鏈表。循環(huán)算法。1 List reverse(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 return tmp;14 2 、反轉一個鏈表。遞歸算法。1 List resverse(listl) 2 if(!l | !l.next)return l;34 List n

2、 =reverse(l.next);5 l.next.next= l;6 l.next=null;7 8 return n;9 3 、廣度優(yōu)先遍歷二叉樹。1 void BST(Treet)2 Queue q=newQueue();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 1classNode2Tree t3Nodenext;4 5classQueue 6Nodehead;7Nod

3、etail;8publicvoid enque(Treet)9Node n= new Node()10n.t= t;11if(!tail)12tail =head = n;13else 14tail.next =n;15tail= n;161718publicTreedeque() 19if(!head)20returnnull;21else 22Node n= head;23head =head.next;24returnn.t;25 264、輸出一個字符串所有排列。注意有重復字符。1char p;2void perm(char s, int i,int3int j;4char temp;5

4、for(j=0;j<n;+j)6if(j!=0 && sj=sj-1);7elseif(sj!='')8pi=sj;9sj=''10if(i=n-1)11pn='0'12printf("%s", p);13else14perm(s,i+1,n);n)15 16 sj=pi;17 18 191void main() 2 char sN;3 sort(s);4 perm(s,0,strlen(s);55 、輸入一個字符串，輸出長型整數(shù)。1 long atol(char *str)2 char *p =str;

5、3 long l=1;m=0;4 if (*p='-') 5 l=-1;6 +p;7 8 while(isDigit(*p)9m =m*1010+p;1112if(!p)returnm*l;13elsereturnerror;14+ p;6 、判斷一個鏈表是否有循環(huán)。1int isLoop(Listl) 2if (! l)return- 1 ;3List s=l.next;4while(s&& s!= l)5s=s.next;67if (! s)return- 18elsereutrn1 ;91int isLoop(List l)72 if(!l) return

6、 0;3 p=l.next;4 wihle(p!=l&&p!=null)5 l.next=l;6 l=p;p=p.next;78if(p=l)return9return0;1;10實際上，在我的面試過程中，還問到了不破壞結構的其他算法。next 指針我的答案是從鏈表頭開始遍歷，如果節(jié)點 next 指針指向自身，則循環(huán)存在；否則將 指向自身，遍歷下一個節(jié)點。直至 next 指針為空，此時鏈表無循環(huán)。7 、反轉一個字符串1void reverse( char *str) 2char tmp;3int len;4len = strlen(str);5for ( int i = 0;i

7、 < len / 2; + i)6tmp = char i;7stri = strlen- i - 1 ;8strlen - i - 1 = tmp;910 8 、實現(xiàn) strstr 函數(shù)。1intstrstr(char str, char par)2int i=0;3int j=0;4while(stri && strj)5if(stri=parj)6+i;7+j;8else9i=i-j+1;10j=0;111213if(!strj) return i-strlen(par);14else return -1;9 、實現(xiàn) strcmp 函數(shù)。1intstrcmp(cha

8、r* str1,char*str2)2while(*str1 &&*str2&& *str1=*str2)3+str1;4+str2;56return*str1-*str2;710、求一個整形中 1的位數(shù)。1int f( int x) 2intn = 0 ;3while(x) 4+ n;5x&= x - 167returnn;811 、漢諾塔問題。1void tower(n,x,y,z)2 if(n=1) move(x,z);3else 4tower(n-1,x,z,y);5move(x,z);6tower(n-1,y,x,z);7812 、三柱漢諾塔最

9、小步數(shù)。1int f3(n)2if (f3n)returnf3n;3else4if(n =1 ) 5f3n =1 ;6return1 ;789f3n = 2 * f3(n - 1 ) + 1 return f3n;1011 四柱漢諾塔最小步數(shù)。1intf4(n)2if(f4n=0)3if(n=1) 4f41=1;56return 1;7min=2*f4(1)+f3(n-1);89for(int i=2;i<n;+i)u=2*f4(i)+f3(n-i);10if(u<min) min=u;1112f4n=min;13return min;1415 else return f4n;13

10、 、在一個鏈表中刪除另一個鏈表中的元素1voiddelete(List m, List n) 2if(!m | !n) return;3List pre = new List();4pre.next=m;5List a=m, b=n,head=pre;67while(a && b)if(a.value < b.value) 8a=a.next;9pre=pre.next;10else if(a.value > b.value)11b=b.next;12else1314a=a.next; pre.next=a;15161718 m=head.next;14 、一個數(shù)組

11、，下標從 0 到 n ，元素為從 0 到 n 的整數(shù)。判斷其中是否有重復元素1int hasDuplicate(int a, int n)2 for(int i=0;i<n;+i)3 while(ai!=i && ai!=-1)4 if(aai=-1) return 1;5 ai=aai;6 aai=-1;7 8 if(ai=i)ai=-1;10 return 0;1115 、判斷一顆二叉樹是否平衡。1intisB(Treet)2if(!t)return0;3intleft=isB(t.left);4intright=isB(t.right);5if(left >=

12、0&& right>=0&& left - right <= 1 | left-right>=-1)6return(left<right)?(right+1) : (left + 1);7elsereturn-1;8916 、返回一顆二叉樹的深度1intdepth(Treet)2if(!t)return 0;3else4int a=depth(t.right);5int b=depth(t.left);6return (a>b)?(a+1):(b+1);78List merge(List a, List d) 17 、兩個鏈表，一升

13、一降。合并為一個升序鏈表2List a1= reverse(d);3List p= q= newList();4while( a&& a1 )5if (a.value< a1.value)6p.next= a;7a =a.next;8else9p.next= a1;10a1 =a1.next;1112p= p.next;1314if (a)p.next= a;15elseif(a1)p.next =a1;16returnq.next;17 18 、將長型轉換為字符串。1char* ltoa(long l)2charN str;3int i=1,n=1;4 while(!(

14、l/i<10)i*=10;+n5 char* str=(char*)malloc(n*sizeof(char);6 int j=0;7 while(l)8 strj+=l/i;9 l=l%i;10 i/=10;11 12 returnstr;1319、用一個數(shù)據(jù)結構實現(xiàn)1 if (x = 0) y = a;2 else y = b;1 j = a,b;2 y=jx;1void del(List head, List node)20 、在雙向鏈表中刪除指定元素。23456789101112131421、123456789101112131415List pre=new List(); pre.next = head;List cur = head; while(cur && cur!=node) cur=cur.next; pre=pre.next;if(!cur) return;List post = cur.next; pre.next=cur.