B．线性顺序表中包含的元素个数不是任意的
C．线性表中的每个结点都有且仅有一个直接前趋和一个直接后继 D．存在这样的线性表，即表中没有任何结点 （20）在（ B ）的运算中，使用顺序表比链表好。
A．插入 B．根据序号查找 C． 删除 D．根据元素查找
四．分析下述算法的功能
（1） ListNode *Demo1(LinkList L,ListNode *p)
{ // L是有头结点的单链表
ListNode *q=L->next;
While (q && q->next!=p)
q=q->next;
if (q)
return q;
else
Error(“*p not in L”);
}
（2） void Demo2(ListNode *p,ListNode *q)
{ // p,*q是链表中的两个结点
DataType temp;
temp=p->data;
p->data=q->data;
q->data=temp;
}
解：
（1）返回结点*p的直接前趋结点地址。 （2）交换结点*p和结点*q（p和q的值不变）。
五． 程序填空
（1）已知线性表中的元素是无序的，并以带表头结点的单链表作存储。试写一算法，删除表中所有大于min，小于max的元素，试完成下列程序填空。
Void delete (lklist head; datatype min, max) { q=head->next; while (p!=NULL)
{ if ((p->data<=min ) | | ( p->data>=max ) {q=p; p= p->next ; }
else
9
{ q->next= p->next ;
delete (p) ; p= q->next ; } } }
（2）在带头结点head的单链表的结点a之后插入新元素x，试完成下列程序填空。
struct node { elemtype data; node *next; };
void lkinsert (node *head, elemtype x) { node *s, *p; s= new node ; s->data= x ; p=head->next;
while (p!=NULL) && ( p->data!=a )
____p=p->next ; if (p==NULL)
cout<< \不存在结点a! \ else {_____s->next=p->next______;
___ p->next=s __________; }
}
六．算法设计题
（1）写一个对单循环链表进行遍历（打印每个结点的值）的算法，已知链表中任意结点的地址为P 。 解：
void Show(ListNode *P) { ListNode *t=P; do { printf(\ t=t->rear; }
while (t!=P); }
（2） 对给定的带头结点的单链表L，编写一个删除L中值为x的结点的直接前趋结点的
算法。
解：
void delete(ListNode *L)
10
{
ListNode *p=L,*q;
if(L->next->data==X) {
printf(“值为x的结点是第一个结点，没有直接前趋结点可以删除”); return; }
For(p->next->data!=X;q=p;p=p->next);// 删除指针p所指向的结点
q->next=p->next; delete p;
}
（3） 已知一个单向链表，编写一个函数从单链表中删除自第i个结点起的k个结点。 解：
void Del(node *head,int i,int k) {
node *p,*q; int j; if(i==1)
for(j=1;j<=k;j++) // 删除前k个元素 {
p=head; // p指向要删除的结点 head=head->next;
delete p; } else {
p=head;
for(j=1;j<=i-2;j++)
p=p->next; // p指向要删除的结点的前一个结点 for(j=1;j<=k;j++) {
q=p->next; // q 指向要删除的结点 p->next=q->next;
delete q;
} } }
（4） 有一个单向链表（不同结点的数据域值可能相同），其头指针为head，编写一个函
数计算值域为x的结点个数。
解：//本题是遍历单链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函数如下：
int counter(head) node *head； { node *p; int n=0;
11
p=head；
while(p!=NULL) { if(p->data==x)
n++； p=p->next; }
return(n); }
（5）有两个循环单向链表，链头指针分别为head1和head2，编写一个函数将链表head1链接到链表head2，链接后的链表仍是循环链表。
解：//本题的算法思想是：先找到两链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，使之成为循环的。函数如下：
node *link (node *head1, *head2) { node *p,*q; p=head1;
while(p->next!=head1)
p=p->next; q=head2;
while(q->next!=head2)
q=q->next; p->next=head2; q->next=head1; return (head1); }
12