历年链表考题与答案.doc

WORD格式历年链表考题及答案2005秋II.14设已建立了两条单向链表，这两链表中的数据已按从小到大的次序排好，指针h1和h2分别指向这两条链表的首结点。链表上结点的数据结构如下：structnodeintdata;node*next;以下函数node*Merge(node*h1,node*h2)的功能是将h1和h2指向的两条链表上的结点合并为一条链表，使得合并后的新链表上的数据仍然按升序排列，并返回新链表的首结点指针。算法提示：首先，使newHead和q都指向首结点数据较小链表的首结点，p指向另一链表首结点。其次，合并p和q所指向的两条链表。在q不是指向链尾结点的情况下，如果q的下一个结点数据小于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-datadataelsenewHead=h2;p=h1;node*q=newHead;/合并两条链表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);/returnnewNead2005春II.11设已建立一条单向链表，指针head指向该链表的首结点。结点的数据结构如下：structNodeintdata;Node*next;以下函数sort(Node*head)的功能是：将head所指向链表上各结点的数据按data值从小专业资料整理到大的顺序排序。算法提示：初始时，使p指向链表的首结点，从p之后的所有结点中找出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=t;/p1-data;/p=p-nextreturnhead;2004秋II.11已建立一条无序链表，head指向链首。链表上结点的数据结构为：structNodedoublenum;Node*next;以下函数sort(Node*head)的功能为：将参数head所指向链表上的各个结点，按num值的升序排序，并返回排序后链表的链首指针。算法提示：先让h指向空链，依次从head所指向的链表上取下一个结点，然后将取下的结点插入到已排序的h所指向的链表上。Node*sort(Node*head)if(head=0)returnhead;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=0elseif(29)/(29)h-num=p-num或p-numnump-next=h;h=p;elsep2=p1=h;while(p2-next&p2-numnum)p1=p2;p2=p2-next;if(30)/(30)p2-numnum或p-nump2-nump2-next=p;p-next=0;elsep-next=p2;p1-next=p;return(h);2004春II.11输入一行字符串，用单向链表统计该字符串中每个字符出现的次数。方法是：对该字符串中的每个字符，依次查找链表上的结点。若链表结点上有该字符，则将该结点的count值加1；否则产生一个新结点，存放该字符，置count为1，并将该结点插入链首。最后，输出链表上的每个结点的字符及出现次数。链表的结构如下图所示。headcccccountcountcountcountnextnextnextnext#includestructnodecharc;intcount;node*next;voidprint(node*head)while(head)cout字符:ct出现countnext;voiddele(node*head)node*p;while(head!=NULL)p=head;head=(27);/(27)head-nextdeletep;node*search(node*head,charch)node*p;p=head;while(p)if(p-c=ch)p-count+;break;(28);/(28)p=p-nextif(p=0)p=newnode;p-c=ch;p-count=1;if(head)(29);/(29)p-next=headelsep-next=0;(30);/(30)head=preturnhead;voidmain(void)chars300,*p=s;node*h=0;charc;cout请输入一行字符串：;cin.getline(s,300);while(c=*p+)h=search(h,c);print(h);dele(h);2003秋II.12用链表实现对候选人的得票进行统计。函数Statistic的输入参数：head指向链首，name存放候选人的姓名。该函数的功能为：若在链表的结点上找到name，则将姓名为name的结点上得得票数加1；否则新建一个结点，初始化其姓名和的票数，并将新结点插入链尾。最后返回链表的首指针。链表的结构如下图所示。headnamenamenamenamecountcountcountcountnextnextnextnext#include#includestructNodecharname12;/候选人姓名intcount;/计数候选人的得票Node*next;Node*Statistic(Node*head,char*name)Node*p1=head,*p2;if(head=0)/空表，插入第1个结点head=newNode;strcpy(head-name,name);head-count=1;head-next=0;else/不是空表，进行结点数值查找while(p1)if(27)/找到了/strcmp(p1-name,name)=0p1-count+;break;else/不是待查结点，移动指针，准备下一结点查找p2=p1;(28);/p1=p1-nextif(29)/待查结点不存在/p1=NULLp1=newNode;/在尾部插入新结点strcpy(p1-name,name);p1-count=1;p1-next=0;(30);/p2-next=p1returnhead;voidList(Node*head)/输出结果while(head)coutname:tcountnext;voidFree(Node*head)/释放链表空间Node*p;while(head)p=head;head=head-next;deletep;voidmain()/连续输入得票候选人的姓名，以输入0结束Node*head=0;charname12;coutname;while(strcmp(name,0)!=0)head=Statistic(head,name);coutname;cout统计得票结果:n姓名得票数n;List(head);Free(head);2003春II.14以下程序使用递归函数实现单向链表操作，完成链表的创建、显示、释放链表的结点。#includestructnodefloatdata;node*next;voidShowChain(node*head)/依次输出每一个结点上的数据if(head)coutdatanext)ShowChain(_);/head-nextvoidAddNode(node*p,node*&head)/将p所指向的结点插入链尾if(head=NULL)head=_;/pelseAddNode(p,head-next);voidDeleteChain(node*head)/依次删除链表上的每一个结点node*p=head;if(p)head=_;/head-nextdeletep;if(head)DeleteChain(head);voidmain(void)node*head=NULL,*temp;temp=newnode;while(2)temp-next=NULL;couttemp-data;if(temp-data0)AddNode(temp,head);/新结点加入链表尾部elsedeletetemp;break;temp=_;/newnodeShowChain(head);DeleteChain(head);2002秋II.14n个人围成一圈，他们的序号依次为1到n，从第一个人开始顺序报数1、2、3、m，报到m者退出圈子，并输出退出圈子的人的序号。接着再顺序报数，直到圈子中留下一个人为止。用一个有n个结点的环形链表模拟围成一圈的人。假定有10个人围成一圈，凡报到5者退出圈子，则退出圈子人的序号依次为5、10、6、2、9、8、1、4、7，最后留在圈中的人是3号。单向环形链表的结构如下图所示。其中head指向第一个人。head12310#includestructNodeintx;/围成一圈时，人的序号Node*next;Node*DelNode(Node*head,intm)/依次输出环形链表中凡报到m者的序号Node*p;intcount;if(head=NULL)return_;/headwhile(head!=head-next)/直到链表上只有一个结点为止count=0;while(countnext;p=head-next;/删除p所指向的结点head-next=_;/p-nexthead=head-next;coutxx=1;head-next=NULL;p=head;for(i=2;inext=newNode;/新结点加入链尾p=_;/p-nextp-x=i;p-next=_;/构成循环链/headhead=DelNode(head,5);cout最后的一个人为：xendl;2002春II.14设链表上结点的数据结构定义如下：structNODEintx;NODE*next;函数create()的功能为：创建一个有序的链表（结点中x的值按升序排序），参数n为链表上要产生的结点的个数，函数返回该有序链表的头指针。算法思想：每产生一个新的结点，插入到链表的恰当位置，使得插入新结点以后的链表仍然保持有序。_creat(intn)/NODE*或structNODE*NODE*p,*p1,*p2,*h=NULL;inti=0;if(n1)returnNULL;while(_)/ip-x;p-next=NULL;if(_)h=p;/h=NULL或!helsep1=p2=h;while(p2&_)/(p-x)=(p2-x)p1=p2;p2=p2-next;if(p2=h)p-next=p2;h=p;elsep-next=p2;p1-next=p;i+;returnh;2001秋II.14设链表上结点的数据结构定义如下：structPNODEintx;PNODE*next;设已建立了一条链表，h为链首指针。函数DelAdd的功能为：若链表上能找到结点的x值为value，则从链表上删除该结点（假定链表上各个结点的值是不同的）；否则构造一个新结点，其x的值为value，并将新结点插入链尾。该函数返回新链表的首指针。程序（4分）PNODE*DelAdd(PNODE*h,intvalue)PNODE*p1,*p2;intflag=0;/值为1时，表示已删除值为value的结点p1=h;while(p1&flag=0)if(p1-x=value)flag=1;if(p1=h)h=(27);deletep1;/p1-nextelsep2-next=(28);deletep1;/p1-nextelsep2=p1;p1=(29);/p1-nextif(flag=0)p1=newPNODE;p1-x=value;p1-next=0;if(h=0)h=p1;else(30);/p2-next=p1returnh;2001春II.13下面程序中，函数padd的功能为调整pa指向的链表中结点的位置，使得所有x值为偶数的结点出现在链表的前半部，所有x值为奇数的结点出现在链表的后半部。如本程序的输出为：10,8,6,4,2,1,3,5,7,9。#includestructNODEintx;NODE*next;NODE*padd(NODE*pa)NODE*p1,*p2,*p;p1=p2=pa;while(p1)if(p1-x%2=0&_)/p1!=pa第1个结点为偶数时不取p=p1;p1=p1-next;_=p1;/从链表上取下偶数结点并插入链首/p2-nextp-next=pa;_;/pa=pelsep2=p1;p1=p1-next;returnpa;voidmain(void)NODEa10=1,2,3,4,5,6,7,8,9,10,*ha=a,*p;inti;for(i=0;i9;i+)ai.next=_;/拉成链表/&ai+1a9.next=NULL;ha=padd(ha);p=ha;while(p)coutxnext;couty=pb-y)pt=new(28);/PNODEpt-x=pa-x+pb-x;pt-y=pa-y;pt-next=NULL;if(pc=NULL)pc=pcr=pt;elsepcr-next=pt;(29);/pcr=pt;pa=pa-next;pb=pb-next;elseif(30)pb=pb-next;/pa-ypb-yelsepa=pa-next;returnpc;05级试卷A学生的记录由学号和成绩组成，设若干名学生的数据已在主函数中存放到链表中。下列函数fun的功能是：用链表中高于或等于平均分的学生数据构成一个由头指针h所指向的新链表，建立新链表时每次都将新生成的结点插入到头结点的前面。形参head是链表头指针，平均分通过形参aver带回，函数返回新链表的头指针h。#include#includestructstudentcharno10;/学号floatgrade;/成绩student*next;student*fun(student*head,float&aver)student*h,*p,*p1;floatsum=0;intn=0;aver=0;p=head;while(p!=NULL)/求成绩和sum=;/sum+p-grade;n+;p=p-next;aver=sum/n;h=NULL;p=head;while(p!=NULL)/用高于或等于平均分的学生数据构成一个新的链表if()/p-grade=averp1=newstudent;/strcpy(p1-no,p-no);p1-grade=p-grade;p1-next=h;h=p1;/p=p-next;returnh;05级试卷B以下用面向对象的方法实现一个单向链表，主要实现在链表尾追加一个结点的功能。ListNodeNodeNodeheaddatadatadatanextnextNULL要求：(1)定义一个结点类Node，结构如上图所示。data是一个整型数据。(2)定义一个链表类List作为Node类的友元类，其私有数据成员Node*head为指向链表首结点的指针。各成员函数的功能见程序中的注释，请完善程序。#includeclassNodeintdata;Node*next;public:Node(intd=0)/构造函数data=d;next=NULL;_;/将List类说明成本类的友元类/friendclassList;classListNode*head;public:List()/缺省构造函数，建立一个空链表_;/head=NULL;List(intd);/构造一个第1个结点数据值为d的结点voidappend(intd=0);/追加一个数据值为d的结点到链表尾部voidprint();/输出链表各结点值List();/析构函数，释放链表各结点空间;List:List(intd)/构造一个第1个结点数据值为d的结点head=newNode(d);voidList:append(intd)/追加一个数据值为d的结点到链表尾部if(head=NULL)head=newNode(d);elseNode*p=head;while(_)/循环结束后，p指向链表最后一个结点/p-next!=NULLp=p-next;p-next=newNode(d);voidList:print()/输出链表各结点值/*函数体略*/List:List()/析构函数，释放链表各结点空间Node*p=head;while(_)/head!=NULLp=head-next;delete(head);head=p;voidmain()Listlist;intd;coutd;while(d)/假定链表中的值为正数，假定以输入0结束li