历年链表考题及答案

}

return h; }

[2001秋II.14]设链表上结点的数据结构定义如下：

struct PNODE

{ int x;

PNODE *next;

};

设已建立了一条链表，h为链首指针。函数DelAdd的功能为：若链表上能找到结点的x值为value，则从链表上删除该结点（假定链表上各个结点的值是不同的）；否则构造一个新结点，其x的值为value，并将新结点插入链尾。该函数返回新链表的首指针。 [程序]（4分）

PNODE *DelAdd(PNODE *h, int value) { PNODE *p1, *p2;

int flag=0; // 值为1时，表示已删除值为value的结点

p1=h;

while(p1&&flag==0) { if(p1->x==value) { flag=1; if(p1==h)

{ h= (27) ; delete p1; } // p1->next else

{ p2->next= (28) ; delete p1; } // p1->next

} else

{ p2=p1; p1= (29) ; } // p1->next }

if(flag==0)

{ p1=new PNODE; p1->x=value; p1->next=0; if(h==0) h==p1;

else (30) ; // p2->next=p1 } return h; }

[2001春II.13]下面程序中，函数padd的功能为调整pa指向的链表中结点的位置，使得所有x值为偶数的结点出现在链表的前半部，所有x值为奇数的结点出现在链表的后半部。如本程序的输出为：10,8,6,4,2,1,3,5,7,9。 #include struct NODE { int x;

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->next p->next=pa; __________________; //pa=p

}

else { p2=p1; p1=p1->next; } }

return pa; }

void main(void)

{ NODE a[10]={{1},{2},{3},{4},{5},{6},{7},{8},{9},{10}}, *ha=a, *p;

int i;

for(i=0; i<9; i++) a[i].next=______________; // 拉成链表 // &a[i+1]

a[9].next=NULL; ha=padd(ha); p=ha; while(p)

{ cout<x<<’,’ ; p=p->next; } cout<<’\\n’;

}

*[2000秋II.11]设结点的数据结构定义如下：

struct PNODE

{ int x,y ; PNODE *next; };

函数padd的功能为：根据pa，pb指向的两个链表（按结点的y值升序排列）生成一个新链表(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) ; // PNODE pt->x=pa->x+pb->x; pt->y=pa->y;pt->next=NULL; if(pc==NULL) pc=pcr=pt; else

{ pcr->next=pt; (29) ; } // pcr=pt; pa=pa->next; pb=pb->next;

} else

if( (30) ) pb=pb->next; // pa->y>pb->y

else pa=pa->next; }

return pc; }

[05级试卷A]学生的记录由学号和成绩组成，设若干名学生的数据已在主函数中存放到链表中。下列函数fun的功能是：用链表中高于或等于平均分的学生数据构成一个由头指针h所指向的新链表，建立新链表时每次都将新生成的结点插入到头结点的前面。形参head是链表头指针，平均分通过形参aver带回，函数返回新链表的头指针h。 #include #include struct student {

char no[10]; // 学号 float grade; // 成绩 student *next; };

student *fun(student *head, float &aver) { student *h, *p, *p1; float sum=0;

int n=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>=aver { p1=new student;

; // strcpy(p1->no, p->no); p1->grade = p->grade; p1->next=h; }

}

h=p1;

; // p=p->next; }

return h;

[05级试卷B] 以下用面向对象的方法实现一个单向链表，主要实现在链表尾追加一个结点的功能。

要求：

List head Node data next Node data next Node data NULL (1) 定义一个结点类Node，结构如上图所示。 data是一个整型数据。

(2) 定义一个链表类List作为Node类的友元类，其私有数据成员Node *head为指向链表首结点的指针。

各成员函数的功能见程序中的注释，请完善程序。 #include class Node {

int data; Node *next;

public: Node(int d=0) //构造函数

{ data=d; next=NULL; }

________________________________; //将List类说明成本类的友元类

// friend class List; };

class List { Node *head;

public: List( ) //缺省构造函数，建立一个空链表

{ _____________________________; // head = NULL; }

List (int d); //构造一个第1个结点数据值为 d 的结点 void append(int d=0); //追加一个数据值为d的结点到链表尾部 void print( ); //输出链表各结点值

~List( ); //析构函数，释放链表各结点空间

};

List::List(int d) //构造一个第1个结点数据值为 d 的结点 { head=new Node(d); }

void List::append(int d) //追加一个数据值为d的结点到链表尾部 {

if(head==NULL) {

head = new Node(d);

}

else { Node *p=head;