历年链表考题及答案

《历年链表考题及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、历年链表考题及答案[2005秋II.14]设已建立了两条单向链表，这两链表中的数据已按从小到大的次序排好，指针h1和h2分别指向这两条链表的首结点。链表上结点的数据结构如下：structnode{intdata;node*next;};以下函数node*Merge(node*h1,node*h2)的功能是将h1和h2指向的两条链表上的结点合并为一条链表，使得合并后的新链表上的数据仍然按升序排列，并返回新链表的首结点指针。算法提示：首先，使newHead和q都指向首结点数据较小链表的首结点，p指向另一链表首结点。其次，合并p和q所指向的两条链表。在q不是指向链尾结点的情况下，如果q的下一个结点数

2、据小于p指向的结点数据，则q指向下一个结点；否则使p1指向q的下一个结点，将p指向的链表接到q所指向的结点之后，使q指向p所指向的结点，使p指向p1所指向的链表。直到p和q所指向的两条链表合并结束为止。注意，在合并链表的过程中，始终只有两条链表。[函数]（4分）node*Merge(node*h1,node*h2){node*newHead,*p,*p1;//使newHead和q指向首结点数据较小链表的首结点，p指向另一链表首结点if((27)){newHead=h1;p=h2;}//h1->datadataelse{newHead=h2;p=h1;}node*q=newHead;/

3、/合并两条链表while(q->next){if(q->next->datadata)(28);//q=q->nextelse{(29);//p1=q->nextq->next=p;q=p;p=p1;}}q->next=p;(30);//returnnewNead}[2005春II.11]设已建立一条单向链表，指针head指向该链表的首结点。结点的数据结构如下：structNode{intdata;Node*next;};以下函数sort(Node*head)的功能是：将head所指向链表上各结点的数据按data值从小到大的顺序排序。算法提示：初始时，使p指向链表的首结点，从p之后的所

4、有结点中找出data值最小的结点，让p1指向该结点。将p指向的结点的data值与p1指向的结点的data值进行交换。让p指向下一个结点，依此类推，直至p指向链表的最后一个结点为止。[程序]（4分）Node*sort(Node*head){Node*p=head,*p1,*p2;if(p==NULL)returnhead;while(p->next!=NULL){p1=p;p2=p->next;while(p2!=NULL){if()//p2->datadatap1=p2;p2=p2->next;}if(p!=p1){intt;t=p->data;p->data=;//p1->data

5、=t;//p1->data};//p=p->next}returnhead;}[2004秋II.11]已建立一条无序链表，head指向链首。链表上结点的数据结构为：structNode{doublenum;Node*next;};以下函数sort(Node*head)的功能为：将参数head所指向链表上的各个结点，按num值的升序排序，并返回排序后链表的链首指针。算法提示：先让h指向空链，依次从head所指向的链表上取下一个结点，然后将取下的结点插入到已排序的h所指向的链表上。Node*sort(Node*head){if(head==0)returnhead;Node*h,*p;h=0;wh

6、ile(head){p=head;(27);//(27)head=head->next或head=p->nextNode*p1,*p2;if(h==0){h=p;(28);//(28)p->next=0或h->next=0}elseif((29))//(29)h->num>=p->num或p->num<=h->num{p->next=h;h=p;}else{p2=p1=h;while(p2->next&&p2->numnum){p1=p2;p2=p2->next;}if((30))//(30)p2->numnum或p->num>p2->num{p2->next=p;p->nex

7、t=0;}else{p->next=p2;p1->next=p;}}}return(h);}[2004春II.11]输入一行字符串，用单向链表统计该字符串中每个字符出现的次数。方法是：对该字符串中的每个字符，依次查找链表上的结点。若链表结点上有该字符，则将该结点的count值加1；否则产生一个新结点，存放该字符，置count为1，并将该结点插入链首。最后，输出链表上的每个结点的字符及出现次数。链表