我考网社区 › 微软认证 › 22道微软数据结构算法面试题

会计考友 发表于 2012-8-3 00:09:22

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.next);
　　5         l.next.next   =   l;
　　6         l.next=null;
　　7   }
　　8   return   n;

　　9   }

会计考友 发表于 2012-8-3 00:09:23

22道微软数据结构算法面试题

</p>　　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}

会计考友 发表于 2012-8-3 00:09:24

22道微软数据结构算法面试题

</p>　　4、输出一个字符串所有排列。注意有重复字符。
　　1char[]   p;
　　2void   perm(char   s[],   int   i,   int   n){
　　3   int   j;
　　4   char   temp;

　　5   for(j=0;j

会计考友 发表于 2012-8-3 00:09:25

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.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

会计考友 发表于 2012-8-3 00:09:26

22道微软数据结构算法面试题

11、汉诺塔问题。 　　1void   tower(n,x,y,z){
　　2         if(n==1)   move(x,z);
　　3         else   {
　　4               tower(n-1,   x,z,y);
　　5               move(x,z);
　　6               tower(n-1,   y,x,z);
　　7         }
　　8}
　　12、三柱汉诺塔最小步数。
　　1       int   f3(n)   {
　　2             if   (f3)   return   f3;
　　3               else         {
　　4                     if   (n   ==   1   )   {
　　5                           f3   =   1   ;
　　6                           return       1   ;
　　7                   }
　　8                   f3   =   2   *   f3(n   -   1   )   +   1   ;
　　9                     return   f3;
　　10         }
　　11   }
　　四柱汉诺塔最小步数。
　　1int   f4(n){
　　2         if(f4==0){
　　3               if(n==1)   {
　　4                         f4==1;
　　5                         return   1;
　　6               }
　　7               min=2*f4(1)+f3(n-1);

　　8               for(int   i=2;i

会计考友 发表于 2012-8-3 00:09:27

22道微软数据结构算法面试题

17、两个链表，一升一降。合并为一个升序链表。 　　1       List   merge(List   a,   List   d)   {
　　2         List   a1   =   reverse(d);
　　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         char   str;
　　3         int   i=1,n=1;

　　4         while(!(l/i

查看完整版本: 22道微软数据结构算法面试题