设为首页 加入收藏

TOP

微软的22道数据结构算法面试题(含答案)(一)
2012-03-10 10:13:35 】 浏览:4319
Tags:微软 数据结构 算法 试题 答案

 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}

首页 上一页 1 2 3 下一页 尾页 1/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇2012网易C++笔试题解答 下一篇派生类构造函数和析构函数的执行..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目