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

会计考友 · 发表于 2012-8-3 00:09: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

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

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

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

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[n])    return    f3[n];
　　3             else       {
　　4                      if (n == 1 )    {
　　5                         f3[n] = 1 ;
　　6                            return    1 ;
　　7                }
　　8                f3[n] = 2 * f3(n - 1 ) + 1 ;
　　9                   return    f3[n];
　　10          }
　　11 }
　　四柱汉诺塔最小步数。
　　1int f4(n){
　　2       if(f4[n]==0){
　　3                if(n==1) {
　　4                      f4[1]==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

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[N] str;
　　3       int i=1,n=1;

　　4       while(!(l/i

		自动登录	找回密码
密码			立即注册

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