历年链表考题与答案

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

2、果 q的下一个结点数据小于p指向的结点数据，贝Uq指向下一个结点；否则使 p1指向q的下一个结点，将p指向的链表接到q所指向的结点之后，使q指向p所指向的结点，使 p指向p1所指向的链表。直到 p和q所指向的两条链表合并结束为止。注意，在合并链表的过程 中，始终只有两条链表。函数(4分)node * Merge(node *h1, node *h2) n ode *n ewHead, *p, *p1;II使newHead和q指向首结点数据较小链表的首结点，p指向另一链表首结点if( (27) newHead=h1; p=h2; II h1->data<h2->dataelse

3、 n ewHead=h2; p=h1; node *q=n ewHead;II 合并两条链表while( q->n ext)if( q->n ext->data < p->data )(28);II q=q->nextelse(29);II p1=q _>n extq_>n ext=p;q=p;p=p1;q_>n ext=p;(30); II return n ewNead2005春11.11设已建立一条单向链表，指针head指向该链表的首结点。结点的数据结构如下：struct Nodeint data;Node *n ext;以下函数so

4、rt(Node *head)的功能是：将head所指向链表上各结点的数据按data值从小到大的顺序排序。算法提示：初始时，使 p指向链表的首结点，从p之后的所有结点中找出data值最小的结点，让pl指向该结点。将p指向的结点的data值与pl指向的结点的data值进行交换。让p指向下一个结点，依此类推，直至p指向链表的最后一个结点为止。程序(4分)Node *sort(Node *head) Node *p=head, *p1,*p2; if(p=NULL) retur n head; while(p-> next!=NULL) p仁 p;/ p2->data < p1-&g

5、t;data/ p1->data/ p1->data/ p=p->n extp2=p->n ext; while(p2!=NULL) if( )p仁 p2;p2=p2->n ext; if(p!=p1) int t;t=p->data; p->data = = t;retur n head;2004秋11.11已建立一条无序链表，head指向链首。链表上结点的数据结构为:struct Node double num; Node * next;以下函数sort(Node *head)的功能为：将参数head所指向链表上的各个结点，按num值的升序排序，并

6、返回排序后链表的链首指针。算法提示：先让h指向空链，依次从 head所指向的链表上取下一个结点，然后将取下 的结点插入到已排序的h所指向的链表上。Node *sort(Node *head) if (head= 0 ) retur n head;Node *h,*p;h=0;while(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 = 0else if (29)/(29)h->num

7、>= p->num或 p->num<=h->num p_>n ext=h;h=p;elsep2=p1 = h;while (p2->n ext && p2->num <p->num) pl = p2 ;p2=p2->n ext;if ( (30)(30)p2->num< p_>num 或p_>num >p2->nump2->next = p;p_>next =0;else p_>next = p2;p1- >next = p;return (h);200

8、4春11.11输入一行字符串，用单向链表统计该字符串中每个字符出现的次数。方法是：对该字符串中的每个字符，依次查找链表上的结点。若链表结点上有该字符，则将该结点的count值加1;否则产生一个新结点，存放该字符，置count为1,并将该结点插入链首。最后，输出链表上的每个结点的字符及出现次数。链表的结构如下图所示。#in clude <iostream.h>struct node char c;int count;node *n ext;void print(node *head) while(head) cout<<" 字符:"<<he

9、ad->c<<"t 出现"<<head->count<<" 次n"head=head->n ext;void dele( node *head) node *p;while(head!=NULL) p=head;head= (27);delete p;node *search( node *head, char ch) node *p;p=head;while(p) if(p_>c=ch) p->co un t+; break; (28);if(p=0) p=new node;p->

10、c=ch;p->coun t=1;if(head) (29);else p->n ext=0;(30);retur n head;void mai n(void) char s300, *p=s;node *h=0;char c;cout<<"请输入一行字符串：”;cin .getli ne(s,300);while(c=*p+) h=search(h, c);/ (27) head-> next/ (28) p=p-> next/ (29) p-> next=head/ (30) head=pprin t(h); dele(h);2003秋

11、11.12用链表实现对候选人的得票进行统计。函数Statistic 的输入参数：head指向链首，name存放候选人的。该函数的功能为：若在链表的结点上找到 name,则将为name的结点上得得票数加1;否则新建一个结点，初始化其和的票数，并将新结点插入链尾。最 后返回链表的首指针。链表的结构如下图所示。 if (27)/p1->co un t+;break;else/空表，插入第1个结点不是空表，进行结点数值查找找至 U了/ strcmp(p1- >n ame, n ame)=0不是待查结点，移动指针，准备下一结点查找/ p1=p1- >n ext待查结点不存在/ p1=N

12、ULL在尾部插入新结点/ p2-> next=p1输出结果cout<< head->n ame <<" :t"<< head->co unt <<e ndl; head=head->n ext;#i nclude <iostream.h>#in elude <stri ng.h>struct Node char name12; / 候选人 int count; /计数候选人的得票Node * next;；Node *Statistic(Node *head, char *n am

13、e) Node *卩仁 head,*p2;if (head=0)/ head=new Node;strcpy(head->n ame, n ame); head->co un t=1;head->n ext=0;else/ while(p1)p2=p1;(28);if (29)/p1= new Node;/strcpy(p1- >n ame ,n ame); p1->coun t=1;p1- >n ext=0;(30)retur n head;void List(Node *head) / while(head)void Free(Node *head) /

14、 释放链表空间 Node *p;while(head) p=head; head=head->next; delete p;void main( ) / 连续输入得票候选人的，以输入 "0" 结束 Node *head=0;char name12;cout<<" 输入得票候选人的 :"cin>>name;while( strcmp(name,"0")!=0 ) head = Statistic(head,name);cout<<" 输入得票候选人的 :" cin>&g

15、t;name;cout<<" 统计得票结果 :n 得票数 n"List(head);Free(head);2003 春 II.14 以下程序使用递归函数实现单向链表操作， 完成链表的创建、 显示、 释放链 表的结点。#include <iostream.h>struct node float data;node *next;void ShowChain(node *head) / 依次输出每一个结点上的数据 if(head) cout<<head->data<<endl;if (head->next) ShowCh

16、ain(void AddNode(node *p, node *&head) / if(head=NULL) head= ;else AddNode(p, head->next);void DeleteChain(node *head) / node *p=head;if (p); / head->next将 p 所指向的结点插入链尾 / p依次删除链表上的每一个结点 head= ; / head->nextdelete p;if(head) DeleteChai n(head);void mai n(void) n ode *head=NULL, *temp;tem

17、p=new no de;while(2) temp->n ext=NULL;cout<<"输入数据："cin> >temp->data;if(temp->data>0) AddNode(temp, head); /新结点加入链表尾部else delete temp; break; temp=;/ new nodeShowChai n( head);DeleteChai n( head);2002秋11.14 n个人围成一圈，他们的序号依次为1到n,从第一个人开始顺序报数1、2、3、m,报到m者退出圈子，并输出退出圈子的人的序号

18、。接着再顺序报数，直到圈子中留下一个人为止。用一个有 n个结点的环形链表模拟围成一圈的人。假定有 10个人围成一 圈，凡报到5者退出圈子，则退出圈子人的序号依次为5、10、6、2、9、8、1、4、7,最后留在圈中的人是 3号。单向环形链表的结构如下图所示。其中head指向第一个人。#in clude <iostream.h>struct Nodeint x; /围成一圈时，人的序号Node *n ext;Node *DelNode(Node *head, i nt m) /依次输出环形链表中凡报到m者的序号 Node *p;int count;if(head=NULL) retur

19、n;/ headwhile(head!=head-> next) /直到链表上只有一个结点为止 coun t=0;while(co un t<m-2) coun t+; head=head->n ext; p=head->next; /删除p所指向的结点head->next=;/ p->n exthead=head->n ext;cout<<p->x<<endl; delete p;return head; void main(void) /在主函数中，构造环形链表，调用Node *head, *p;/int i;head

20、=new Node;head->x=1; head->next=NULL; p=head;for(i=2; i<=10; i+) p->next=new Node; /p= ;p->x=i;DeiNode函数依次输出报到 m的人的序号最后输出留在圈中最后的人的序号新结点加入链尾/ p->nextp->next=head=DelNode(head, 5);cout<<" 最后的一个人为： "<<head->x<<endl; /构成循环链/ head2002 春 II.14 设链表上结点的数据结

21、构定义如下：struct NODEint x;NODE *next;函数 create( ) 的功能为：创建一个有序的链表(结点中 为链表上要产生的结点的个数， 函数返回该有序链表的头指针。x 的值按升序排序) ，参数 n 算法思想： 每产生一个新的结点，插入到链表的恰当位置，使得插入新结点以后的链表仍然保持有序。 creat(int n) NODE *p, *p1, *p2, *h=NULL;int i=0;if(n<1) return NULL;whiie() p = new NODE;/NODE * 或 struct NODE */i<ncin >> p->

22、x; p->next = NULL;if() h=p;eise p1=p2=h;whiie(p2&&/h=NULL 或 !h/(p->x)>=(p2->x)p1=p2; p2=p2->next; if(p2=h)p->next = p2; h=p; eise p->next = p2; p1->next =p; i+；return h;2001秋11.14设链表上结点的数据结构定义如下：struct PNODE int x;PNODE *n ext;设已建立了一条链表，h为链首指针。函数DelAdd的功能为：若链表上能找到结点的x

23、值为value，则从链表上删除该结点(假定链表上各个结点的值是不同的)；否则构造一个新结点，其x的值为value，并将新结点插入链尾。该函数返回新链表的首指针。程序(4分)PNODE *DelAdd(PNODE *h, i nt value) PNODE *p1, *p2;int flag=0; /值为1时，表示已删除值为 value的结点p仁h;while(p1 &&flag=0) if(p1->x=value) flag=1;if(p1=h) h= (27); delete p1; / p1- >nextelse p2-> next=(28); delet

24、e p1; / p1-> nextelse p2=p1; p1=(29); / p1- >n extif(flag=0) p1= new PNODE;p1->x=value;p1- >n ext=0;if(h=0) h=p1;else (30); / p2->n ext=p1return h;2001春11.13下面程序中，函数padd的功能为调整pa指向的链表中结点的位置，使得所 有x值为偶数的结点出现在链表的前半部，所有x值为奇数的结点出现在链表的后半部。如本程序的输出为：10,8,6,4,2,1,3,5,7,9。#in clude <iostream.

25、h>struct NODE int x;NODE *n ext;；NODE *padd(NODE *pa) NODE *p1, *p2, *p;p1=p2=pa;while(pl) if(p1->x%2=0&&)/ p1!=pa 第1个结点为偶数时不取 p=p1; p1=p1- >n ext;=p1; /从链表上取下偶数结点并插入链首p2-> next p_>n ext=pa;pa=pelse p2=p1; p1=p1- >n ext; return pa;void mai n(void) NODE a10=1,2,3,4,5,6,7,8,9

26、,10, *ha=a, *p;int i;for(i=0; i<9; i+) ai.next=; /拉成链表 / &ai+1a9 .n ext=NULL;ha=padd(ha);p=ha;while(p) cout<<p- >x<<' , ' ; p=p ->next; cout<<' n'；*2000秋11.11设结点的数据结构定义如下：struct PNODE int x,y ; PNODE *n ext; ;函数padd的功能为：根据pa，pb指向的两个链表(按结点的 y值升序排列)生成一个 新

27、链表(pc为链首指针)。新生成链表仍按y值升序排列。生成新链表的规则为：当在pa和pb链表中发现y值相同的结点时，则在 pc链表中增加一个新结点，新结点的 x取值为两链 表中对应的两个结点的 x值之和，新结点的y取值为pa或pb链表中对应结点的 y值。PNODE *padd(PNODE *pa, PNODE *pb) PNODE *pcr,*pt,*pc=0;while( (27) / pa&&pb if(pa_>y=pb_>y) pt= new(28); / PNODEpt->x=pa->x+pb->x; pt->y=pa->y;pt

28、- >n ext=NULL;if(pc=NULL) pc=pcr=pt;else pcr->n ext=pt; (29); / pcr=pt;pa=pa->n ext; pb=pb->n ext;elseif( (30) pb=pb->n ext;/ pa_>y>pb_>yelse pa=pa->n ext;return pc;05级试卷A学生的记录由学号和成绩组成，设若干名学生的数据已在主函数中存放到链表中。下列函数fun的功能是：用链表中高于或等于平均分的学生数据构成一个由头指针h所指向的新链表，建立新链表时每次都将新生成的结点插入到头

29、结点的前面。形参head是链表头指针，平均分通过形参 aver带回，函数返回新链表的头指针 h。#in clude <iostream.h>#in clude <stri ng.h>struct stude nt char no10; /学号float grade; /成绩stude nt *n ext;stude nt *fun( stude nt *head, float &aver) stude nt *h, *p, *p1;float sum=0;int n=0;aver=0;p=head;while(p!=NULL) /求成绩和 sum= ; / su

30、m+p->grade;n+;p=p->n ext;aver=su m/n;h=NULL;p=head;while(p!=NULL) /用高于或等于平均分的学生数据构成一个新的链表 if( ) / p->grade>=aver p1= new stude nt; / strcpy(p1- >no, p->no);p1->grade = p->grade;p1- >n ext=h;h=p1;/ p=p->n ext;return h;05级试卷B以下用面向对象的方法实现一个单向链表，主要实现在链表尾追加一个结点 的功能。要求：(1) 定义

31、一个结点类Node,结构如上图所示。data是一个整型数据。(2) 定义一个链表类List作为Node类的友元类，其私有数据成员Node *head为指向链 表首结点的指针。各成员函数的功能见程序中的注释，请完善程序。#in clude<iostream.h>class Nodeint data;Node *n ext;public:Node(i nt d=0) /构造函数 data=d; next=NULL; ; II 将List 类说明成本类的友元类/ friend class List;class List II缺省构造函数，建立一个空链表Node *head; public

32、:List()II head = NULL;List (i nt d); IIvoid appe nd(i nt d=0); II void print();List();List:List(i nt d) IIhead=new Node(d); void List:appe nd(i nt d) IIIIII构造一个第1个结点数据值为d的结点追加一个数据值为 d的结点到链表尾部 输出链表各结点值析构函数，释放链表各结点空间构造一个第1个结点数据值为d的结点追加一个数据值为d的结点到链表尾部if(head=NULL) head = new Node(d); elseNode *p=head;while() / 循环结束后， p 指向链表最后一个结点/ p->next != NULL p=p->next;p->next = new Node(d);void List:print( ) / 输出链表各结点值 /* 函数体略 */ List:List( ) / 析构函数，释放链表各结点空间Node *p=head;while( ) / head!=NULL p=head->next;delete (head); head=p;void main( )List list; int d; cout<<"Please input a data: