c 面试编程题模拟.doc

常用经典编程例子一个链表的结点结构structNode{intdata;Node*next;};typedefstructNodeNode;文档来自于网络搜索(1)已知链表的头结点head,写一个函数把这个链表逆序(Intel)Node*ReverseList(Node*head)//链表逆序{if(head==NULL||head->next==NULL)returnhead;Node*p1=head;Node*p2=p1->next;Node*p3=p2->next;p1->next=NULL;while(p3!=NULL){p2->next=p1;p1=p2;p2=p3;p3=p3->next;}p2->next=p1;head=p2;returnhead;}(2)已知两个链表head1和head2各自有序,请把它们合并成一个链表依然有序.(保留所有结点,即便大小相同)Node*Merge(Node*head1,Node*head2){if(head1==NULL)returnhead2;if(head2==NULL)returnhead1;Node*head=NULL;Node*p1=NULL;Node*p2=NULL;if(head1->data<head2->data){head=head1;p1=head1->next;p2=head2;}else{head=head2;p2=head2->next;p1=head1;}Node*pcurrent=head;while(p1!=NULL&&p2!=NULL){if(p1->data<=p2->data){pcurrent->next=p1;pcurrent=p1;p1=p1->next;}else{pcurrent->next=p2;pcurrent=p2;p2=p2->next;}}if(p1!=NULL)pcurrent->next=p1;if(p2!=NULL)pcurrent->next=p2;returnhead;}(3)已知两个链表head1和head2各自有序,请把它们合并成一个链表依然有序,这次要求用递归方法进行.(Autodesk)答案:Node*MergeRecursive(Node*head1,Node*head2){if(head1==NULL)returnhead2;if(head2==NULL)returnhead1;Node*head=NULL;if(head1->data<head2->data){head=head1;head->next=MergeRecursive(head1->next,head2);}else{head=head2;head->next=MergeRecursive(head1,head2->next);}returnhead;文档来自于网络搜索写一个函数找出一个整数数组中,第二大的数(microsoft)答案:constintMINNUMBER=-32767;intfind_sec_max(intdata[],intcount){intmaxnumber=data[0];intsec_max=MINNUMBER;for(inti=1;i<count;i++){if(data[i]>maxnumber){sec_max=maxnumber;maxnumber=data[i];}else{if(data[i]>sec_max)sec_max=data[i];}}returnsec_max;}文档来自于网络搜索编程实现单链表的插入Node*InsertNode(Node*Head,intnum){Node*newNode=newNode; newNode->data=num; if(!Head)//此时为空链表 { newNode->next=NULL; returnnewNode; } Node*p=Head; Node*q=NULL;//q指向p结点之前的结点 while(p)//此时寻找位置 { if(p->data<num) {q=p; p=p->next; } else//此时找到了位置 break; } if(p==Head)//插入到头结点之前 { newNode->next=Head; Head=newNode; } elseif(!p)//插入到尾结点之后,此时q指向尾结点 { q->next=newNode; newNode->next=NULL; } else//插入到p结点和q结点之间 { newNode->next=q->next; q->next=newNode; } returnHead;}编程实现双链表删除结点(注意它和单链表删除结点的情况有所不同)Node*DoubleLink