数据结构面试题及答案

1、数据结构面试题及答案 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

2、 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 = que(); 5 while(t) 6 System.out.println(t.value); 7 q.enque(t.left); 8 q.enque(t.right); 9 t = que(); 10 11 - 1class Node 2 Tree t; 3 N

3、ode 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 retur

4、n 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;jn;+j) 6 if(j!=0 & sj=sj-1); 7 elseif(sj!=) 8 pi=sj; 9 sj=; 10 if(i=n-1) 11 pn=0; 12 printf(%s, p); 13 else 14 perm(s,i+1,n); 15 16 sj=pi; 17 18 19 - 1void main() 2 char sN; 3 sort(s); 4 per

5、m(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 whil

6、e (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指针指向自身，遍历下一个节点。

7、直至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 stri = strlen - i - 1 ; 8 strlen - i - 1 = tmp; 9 10 8、实现strstr函数。 1int strstr(char str, char par) 2 int i=0; 3 int j=0; 4 while(stri & strj) 5

8、 if(stri=parj) 6 +i; 7 +j; 8 else 9 i=i-j+1; 10 j=0; 11 12 13 if(!strj) return i-strlen(par); 14 else return -1; 15 9、实现strcmp函数。 1int strcmp(char* str1, char* str2) 2 while(*str1 & *str2 & *str1=*str2) 3 +str1; 4 +str2; 5 6 return *str1-*str2; 7 10、求一个整形中1的位数。 1 int f( int x) 2 int n = 0 ; 3 while

9、(x) 4 + n; 5 x &= x - 1 ; 6 7 return n; 8 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 (f3n) return f3n; 3 else 4 if (n = 1 ) 5 f3n = 1 ; 6 return 1 ; 7 8 f3n = 2 * f3(n - 1 ) + 1 ; 9 return f3n;

10、10 11 四柱汉诺塔最小步数。 1int f4(n) 2 if(f4n=0) 3 if(n=1) 4 f41=1; 5 return 1; 6 7 min=2*f4(1)+f3(n-1); 8 for(int i=2;in;+i) 9 u=2*f4(i)+f3(n-i); 10 if(u 11 12 f4n=min; 13 return min; 14 else return f4n; 15 13、在一个链表中删除另一个链表中的元素。 1void delete(List m, List n) 2 if(!m | !n) return; 3 List pre = new List(); 4 p

11、re.next=m; 5 List a=m, b=n,head=pre; 6 while(a & b) 7 if(a.value b.value) 11 b=b.next; 12 else 13 a=a.next; 14 pre.next=a; 15 16 17 m=head.next; 18 14、一个数组，下标从0到n，元素为从0到n的整数。判断其中是否有重复元素。 1int hasDuplicate(int a, int n) 2 for(int i=0;i=0 & right =0 & left - right =-1) 6 return (left 7 else return -1;

12、 8 9 16、返回一颗二叉树的深度。 1int depth(Tree t) 2 if(!t) return 0; 3 else 4 int a=depth(t.right); 5 int b=depth(t.left); 6 return (ab)?(a+1):(b+1); 7 8 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 =

13、 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 charN str; 3 int i=1,n=1; 4 while(!(l/i 5 char* str=(char*)malloc(n*sizeof(char); 6 int j=0; 7 while(l) 8 strj+=l/i;

14、 9 l=l%i; 10 i/=10; 11 12 return str; 13 19、用一个数据结构实现 1 if (x = 0) y = a; 2 else y = b; 1 j = a,b; 2 y=jx; 20、在双向链表中删除指定元素。 1void del(List head, List node) 2 List pre=new List(); 3 pre.next = head; 4 List cur = head; 5 while(cur & cur!=node) 6 cur=cur.next; 7 pre=pre.next; 8 9 if(!cur) return; 10 Li

15、st post = cur.next; 11 pre.next=cur.next; 12 post.last=cur.last; 13 return; 14 21、不重复地输出升序数组中的元素。 1 void outputUnique( char str, int n) 2 if (n = 0 ) return ; 3 elseif(n = 1 ) putchar(str 0 ); 4 else 5 int i = 0 ,j = 1 ; 6 putchar(str 0 ); 7 while (j n) 8 if (strj != stri) 9 putchar(strj); 10 i = j;

16、 11 12 + j; 13 14 15 数据结构面试题 以及答案xx-11-01 9:20 | #2楼 1.把一个链表反向 #include typedef struct List int num; struct List *next; test; test *create_list() test *head; test *first; test *temp =NULL; first=head=new test; for(int i=0;inum=i; temp=new test; /偷懒，用C+的new了，C用内存分配函数 head-next=temp; temp-next=NULL; h

17、ead=temp; return first; void print(test *head) while(head-next!=NULL) printf(%dn,head-num); head=head-next; test *change_list(test *head) test *temp,*sixer; temp=head-next; head-next=NULL; while(temp-next!=NULL) sixer=temp-next; temp-next=head; printf(%d-head-,temp-num); head=temp; temp=sixer; print

18、f(%d-temp-,temp-num); temp-next=head; return temp; int main() test *onelist; onelist = create_list(); print(onelist); onelist = change_list(onelist); print(onelist); 2. 一个二叉树的三种遍历方法的输出结果 前序遍历，先根接点。中序，根左边的根右边的，例子： abdgcefh,中序遍历访问顺序是dgbaechf,则其后续遍历的结点访问顺序是 a为根，dgb为左子树,echf为右子树 接下来看左子树的前序遍历为bdg b首先被访问 可以知道b为左子树的根，与a相连 再看左子树的中序遍历dgb d和g都在b之前就被访问 所以b和g应该在b的左子树上 而dg的确定再根据前序遍历 d先被访问 则d为根 再看中序遍历也是d先被访问 可以确定g为d的右子树 左边就可以确定出来了 如果上面看懂了 右边就很简单，一样的道理 前序遍历cefh 确定c为右子树的根 再看中序遍历echf e为c的左子树，hf为c的右子树 hf