中）

(1)在p所指向结点之后插入s所指向的结点： 。 (2)在p所指向结点之前插入s所指向的结点： 。 (3)在单链表L首插入s所指向的结点： 。 (4)在单链表L后插入s所指向的结点： 。 提供的语句： A. p->next=s; H. q=p;

B. p->next=p->next->next; I. while(p->next!=q) p=p->next; C. p->next=s->next; J. while(p->next!=NULL) p=p->next; D. s->next=p->next; K. p=q; E. s->next=L; L. p=L; F. s->next=p; M. L=s; G. s->next=NULL; N. L=p;

二、填空题

1．线性表（Linear List）是最简单、最常用的一种数据结构。线性表中的元素存在着__一对一_的相互关系。

2．线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有且仅有一个__直接前驱_，除终端结点外，其他每个元素有且仅有一个_直接后继_。

3．线性表是n（n>=0）个数据元素的__有限序列_。其中n为数据元素的个数，定义为线性表的__长度_。当n为零时的表称为__空表_。

4．所谓顺序表（Sequential LISt）是线性表的__顺序存储结构_，它是将线性表中的结点按其__逻辑顺序_依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在__地址相邻_的存储单元中。

5．单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些_任意__的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的__任意_的位置上，它们在物理上可以是一片连续的存储单元，也可以是__不连续__的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的 逻辑关系。

6．线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的_数据域_；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为_指针域_或___链域__。

7．线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种__非顺序_存储结构，又称为__非顺序映像_。

8．如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了__循环链表_。

9．为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了__双向链表_。

10．双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是_p所指向的结点本身_。

11．在单链表中，删除指针P所指结点的后继结点的语句是__ P->next=p->next->next __。 12．在双循环链表中，删除指针P所指结点的语句序列是P->prior->next＝p->next及_ P->next->prior=P->prior _。

13．单链表是___线性表__的链接存储表示。

5

14．可以使用__双链表__表示树形结构。

15．向一个长度为n的向量的第i个元素(l≤i≤n+1）之前插人一个元素时，需向后移动__n-i+1__个元素。

16．删除一个长度为n的向量的第i个元素（l≤i≤n）时，需向前移动__n-i_个元素。 17．在单链表中，在指针P所指结点的后面插人一个结点S的语句序列是__ S->next=P->next; P->next=S __。

18．在双循环链表中，在指针P所指结点前插人指针S所指的结点，需执行语句_ p->prior->next=S; s->prior=p->prior;s->next=p;p->prior=s;_。

19．取出广义表A＝（（x，（a，b，c，d））中原子c的函数是__ L(tail(tail((L(tail(L(A))))))_。 20．在一个具有n个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为___ O(n)_。

21．写出带头结点的双向循环链表L为空表的条件__(L==L->Next) && (L==L->Prior)_。 22．线性表、栈和队列都是__线性__结构。

23．向栈中插人元素的操作是先移动栈__顶_针，再存人元素。 三、判断题

1．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（×） 2．在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。(× ) 3．顺序存储的线性表不可以随机存取。（×） 4．单链表不是一种随机存储结构。（√） 5．顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。(×)

6．顺序存储结构是动态存储结构，链式存储结构是静态存储结构。（×） 7．线性表的长度是线性表所占用的存储空间的大小。（×） 数组描述的链表叫静态链表

8．双循环链表中，任意一结点的后继指针均指向其逻辑后继。（×） 9．线性表的惟一存储形式是链表。（×） 四、综合题

1．编写一个将带头结点单链表逆置的算法。 void reverse_list( LinkList L) { /*逆置带头结点的单链表*/ LinkList s, p; p=L->next; /*p指向线性表的第一个元素*/ L->next=NULL; /*初始空表*/ while ( p != NULL ) { s=p; p=p->next; s->next=L->next; L->next=s; /*将s结点插入逆表*/ }

} /*reverse_list*/

2．ha和hb分别是两个按升序排列的、带头结点的单链表的头指针，设计一个算法，

6

把这两个单链表合并成一个按升序排列的单链表，并用hC指向它的头结点。

void mergelist(LinkList *La,LinkList *Lb,LinkList *Lc) { LinkList pa,pb,pc; pa=(*La)->next; pb=(*Lb)->next; *Lc= *La ,pc =*La; while (pa&&pb) if(pa->data<=pb->data)

{ pc->next=pa; pc=pa; pa=pa->next; }

else

{ pc->next=pb; pc=pb; pb=pb->next; }

pc->next=pa?pa:pb; free(*Lb); }

3．有一个带头结点的单链表，头指针为L，编写一个算法count．list（）计算所有数据域为X的结点的个数（不包括头结点）。

int count_list(LinkList L ) { /*在带头结点的单链表中计算所有数据域为x的结点的个数*/ LinkList p; int n; p=L->next; /*p指向链表的第一个结点*/ n=0; while (p!=NULL) { if (p->data==x) n++; p=p->next; } return(n); /*返回结点个数*/ } /*count_list*/

4．在一个带头结点的单链表中，头指针为L，它的数据域的类型为整型，而且按由小到大的顺序排列，编写一个算法insertx＿list（），在该链表中插人值为x的元素，并使该链表仍然有序。

void insert_list(LinkList L,int x){ LinkList p,q,s; p=L->next; q=L; while(p&&x>p->data){q=p;p=p->next;} s=(LinkList)malloc(sizeof(Lnode)); s->data=x; s->next=p; q->next=s; }

7

5．在一个带头结点的单链表中，L为其头指针，p指向链表中的某一个结点，编写算法swapin．list（），实现p所指向的结点和p的后继结点相互交换。

int swapin_list(LinkList head, LinkList p) { /*在带头结点的单链表中，实现p所指向的结点和p的后继结点相互交换*/ LinkList q, r, s; q=p->next; /*q为p的后继*/ if (q !=NULL) /*若p有后继结点*/ { if (p==head) /*若p指向头结点*/ { head=head->next; s=head->next; head->next=p; p->next=s; } else /*p不指向头结点*/ { r=head; /*定位p所指向结点的前驱*/ while (r->next != p) r=r->next; r->next=q; /*交换p和q所指向的结点*/ p->next=q->next; q->next=p; } return OK; } else /*p不存在后继*/ return ERROR; }/*swapin_list*/

6．有一个带头结点的单链表，所有元素值以非递减有序排列，L为其头指针，编写算法deldy．list（）将该链表中多余元素值相同的结点删除。

void deldy_list(LinkList head) { /*在带头结点的非递减有序单链表，将该链表中多余的元素值相同的结点删除*/ LinkList q; if (head->next!= NULL)/*判断链表是否为空*/ { p=head->next; while (p->next != NULL ) { if ( p->data != p->next->data ) p=p->next;

8