2024年微软的道数据结构算法面试题.doc

资源描述

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "">  <DIV id=home> <DIV id=header> <DIV id=blogTitle> <DIV class=title><A class=headermaintitle id=Header1_HeaderTitle href="">Alex iPhone 之旅</A></DIV> <DIV class=subtitle>动手，分享，交流</DIV></DIV> <DIV id=navigator> <UL id=navList> <LI><A class=menu id=MyLinks1_HomeLink href="">博客园</A> </LI> <LI><A class=menu id=MyLinks1_MyHomeLink href="">首页</A> </LI> <LI><A href="">新闻</A> </LI> <LI><A class=menu id=MyLinks1_NewPostLink href="">新随笔</A> </LI> <LI><A class=menu id=MyLinks1_ContactLink accessKey=9 href="">联系</A> </LI> <LI><A class=menu id=MyLinks1_Admin href="">管理</A> </LI> <LI><A class=menu id=MyLinks1_Syndication href="">订阅</A> <A class=aHeaderXML id=MyLinks1_XMLLink href=""><IMG style="BORDER-TOP-WIDTH: 0px; BORDER-LEFT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; BORDER-RIGHT-WIDTH: 0px" alt=订阅 src="微软的22道数据结构算法面试题（含答案） - Alex iPhone 之旅 - 博客园.files/rss.gif"></A> </LI></UL> <DIV class=blogStats>随笔-156  文章-1  评论-358  </DIV></DIV></DIV> <DIV id=main> <DIV id=mainContent> <DIV class=forFlow> <DIV id=topics> <DIV class=post> <H1 class=postTitle><A class=postTitle2 id=ctl04_TitleUrl href="">微软的22道数据结构算法面试题（含答案）</A> </H1> <DIV class=clear></DIV> <DIV class=postBody>   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.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     }     11   }     ----------------------       1class   Node   {       2     Tree   t;       3     Node   next;       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[]   p;       2void   perm(char   s[],   int   i,   int   n){       3   int   j;       4   char   temp;       5   for(j=0;j<n;++j){       6     if(j!=0   &&   s[j]==s[j-1]);       7     elseif(s[j]!='@'){       8       p[i]=s[j];       9       s[j]='@';     10       if(i==n-1){     11         p[n]='\0';     12         printf("%s",   p);     13       }else{     14         perm(s,i+1,n);     15       }     16       s[j]=p[i];     17     }     18   }     19}     --------------------------     1void   main()   {     2     char   s[N];     3     sort(s);     4     perm(s,0,strlen(s));     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   isLoop(List   l){       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             char     tmp;       3             int     len;       4           len     =     strlen(str);       5               for   (   int     i   =   0   ;i   <   len   /   2   ;   ++   i)     {       6                   tmp   =   char   [i];       7                   str[i]     =     str[len   -   i   -   1   ];       8                   str[len   -   i   -   1   ]   =   tmp;       9           }       10   }           8、实现strstr函数。           1int   strstr(char[]   str,   char[]   par){       2         int   i=0;       3         int   j=0;       4         while(str[i]   &&   str[j]){       5                 if(str[i]==par[j]){       6                         ++i;       7                         ++j;       8                 }else{       9                         i=i-j+1;     10                         j=0;     11                 }     12         }     13         if(!str[j])   return   i-strlen(par);     14         else   return   -1;     15} 9、实现strcmp函数。</S

展开阅读全文