数据结构算法面试题.doc

《数据结构算法面试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、微软的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 = t

2、mp;  12  }  13  return tmp;  14 }    2、反转一个链表。递归算法。    1  List resverse(list l) {  2  if(!l 

3、

4、 !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  Que

5、ue 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;  

6、 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() 

7、{  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

8、 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]='';  12    printf("%s", p);  13   }else{  14    perm(s,i+1,n);  15   }  16   s[j]=p[i];  17  }  18 }  19}  --------------------------  1void main() {  2  

9、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    

10、    ++p;  11    }  12    if(!p) return m*l;  13    else return error;  14}      6、判断一个链表是否有循环。    1   int  isL