历年链表考题及答案
[2005秋II.14]设已建立了两条单向链表，这两链表中的数据已按从小到大的次序排好，指针h1和h2分别指向这两条链表的首结点。链表上结点的数据结构如下：
struct node{
int data;
node *next;
};
以下函数node *Merge(node *h1, node *h2)的功能是将h1和h2指向的两条链表上的结点合并为一条链表，使得合并后的新链表上的数据仍然按升序排列，并返回新链表的首结点指针。
{p1 = p2 ;
p2=p2->next;
}
if ((30))//(30)p2->num < p->num或p->num>p2->num
{p2->next = p;
p->next =0;
}
else
{p->next = p2;
p1->next = p;
}
}
}
return (h);
}
[2004春II.11]输入一行字符串，用单向链表统计该字符串中每个字符出现的次数。方法是：对该字符串中的每个字符，依次查找链表上的结点。若链表结点上有该字符，则将该结点的count值加1；否则产生一个新结点，存放该字符，置count为1，并将该结点插入链首。最后，输出链表上的每个结点的字符及出现次数。链表的结构如下图所示。
if(head==0) //空表，插入第1个结点
{head=new Node;
strcpy(head->name, name);
head->count=1;
head->next=0;
}
else//不是空表，进行结点数值查找
{while(p1)
{if((27))//找到了// strcmp(p1->name, name)==0
print(h); dele(h);
}
[2003秋II.12]用链表实现对候选人的得票进行统计。函数Statistic的输入参数：head指向链首，name存放候选人的姓名。该函数的功能为：若在链表的结点上找到name，则将姓名为name的结点上得得票数加1；否则新建一个结点，初始化其姓名和的票数，并将新结点插入链尾。最后返回链表的首指针。链表的结构如下图所示。
[程序]（4分）
Node *sort(Node *head)
{Node *p=head, *p1,*p2;
if(p==NULL) return head;
while(p->next!=NULL)
{ p1=p;
p2=p->next;
while(p2!=NULL)
{if()// p2->data < p1->d>next);
}
void DeleteChain(node *head)//依次删除链表上的每一个结点
{ node *p=head;
if(p)
{ head=____________ ;// head->next
delete p;
if(head) DeleteChain(head);
#include <iostream.h>
struct Node{
int x; //围成一圈时，人的序号
Node *next;
};
Node *DelNode(Node *head, int m) //依次输出环形链表中凡报到m者的序号
{ Node *p;
int count;
if(head==NULL) return _____________ ;// head
(30);// (30) head=p
}
return head;
}
void main(void)
{ char s[300], *p=s;
node *h=0;
char c;
cout<<"请输入一行字符串：";
cin.getline(s,300);
while(c=*p++) h=search(h, c);
}
[2005春II.11]设已建立一条单向链表，指针head指向该链表的首结点。结点的数据结构如下：
struct Node{
int data;
Node *next;
};
以下函数sort(Node *head)的功能是：将head所指向链表上各结点的数据按data值从小到大的顺序排序。
算法提示：初始时，使p指向链表的首结点，从p之后的所有结点中找出data值最小的结点，让p1指向该结点。将p指向的结点的data值与p1指向的结点的data值进行交换。让p指向下一个结点，依此类推，直至p指向链表的最后一个结点为止。
{ if(head)
{ cout<<head->data<<endl;
if(head->next) ShowChain(_____________);//head->next
}
}
void AddNode(node *p, node *&head) //将p所指向的结点插入链尾
{ if(head==NULL) head=___________ ;// p
cout<<"输入得票候选人的姓名:";
cin>>name;
while( strcmp(name,"0")!=0 )
{head = Statistic(head,name);
cout<<"输入得票候选人的姓名:";
cin>>name;
}
cout<<"统计得票结果:\n姓名得票数\n";
List(head);
head=head->next;
}
}
void dele(node *head)
{ node *p;
while(head!=NULL)
{ p=head;
head=(27);//(27) head->next
delete p;
}
}
node *search(node *head, char ch)
{ node *p;
Node *sort(Node *head)
{if (head== 0 ) return head;
Node *h,*p;
h=0;
while(head)
{p=head;
(27);//(27)head = head->next或head =p->next
Node *p1,*p2;
if (h == 0 )
Free(head);
}
[2003春II.14]以下程序使用递归函数实现单向链表操作，完成链表的创建、显示、释放链表的结点。
#include <iostream.h>
struct node
{ float data;
node *next;
};
void ShowChain(node *head) //依次输出每一个结点上的数据
[函数]（4分）
node * Merge(node *h1, node *h2)
{node *newHead, *p, *p1;
//使newHead和q指向首结点数据较小链表的首结点，p指向另一链表首结点
if((27)){newHead=h1;p=h2;}// h1->data<h2->data
else{newHead=h2;p=h1;}
node *q=newHead;
//合并两条链表
while( q->next)
{if( q->next->data < p->data )
(28);// q=q->next
else
{(29);// p1=q->next
q->next=p;
q=p;
p=p1;
}
}
q->next=p;
(30);// return newNead
#include <iostream.h>
#include <string.h>
struct Node
{char name[12]; //候选人姓名
int count; //计数候选人的得票
Node * next;
};
Node *Statistic(Node *head, char *name)
{Node *p1=head,*p2;
p=head;
while(p)
{ if(p->c==ch)
{ p->count++; break; }
(28);//(28) p=p->next
}
if(p==0)
{ p=new node;
p->c=ch;
p->count=1;
if(head)(29);//(29) p->next=head
else p->next=0;
p1->next=0;
(30);// p2->next=p1
}
}
return head;
}
void List(Node *head) //输出结果
{while(head)
{cout<< head->name <<" :\t"<< head->count <<endl;
head=head->next;