试画出链表L的结构图，并编写算法判断环上任意两个相邻元素值之差的绝对值是否不超过2。
【解析】画出链表L的结构图如图2-3所示。
【解析】根据双循环链表的两个最重要的特点：
1）所有结点都有前驱指针和后继指针；
2）尾结点的后继指针指向第一个结点。
可以写出满足要求的语句
P->next=L;
【5】带头结点的双循环链表L为空表的条件是。
【解析】如图2- 所示，当带头结点的双循环链表的头结点L的前驱和后继指针都志向自己时，链表为空。
图2-
(5)能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
2.2习题解析
一判断题(y/n)
1,顺序存储的线性表可以随机存取。
2,顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。
3,由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活。
或者S->prior->next=S。
【3】在单链表中，删除指针P所指结点的后继结点的语句是。
【解析】根据单链表的存储特点，即每个结点包括数据域和后继结点指针域两个部分，可以容易地写出语句：
P->next=P->next->next;
为本题答案。
【4】在双循环链表L中，指针P所指结点为尾结点的条件是。
【解析】线性表长度的定义是它所包含的元素的个数。元素的类型决定了元素所占用存储空间的大小，但元素的个数不等价于元素的类型。因此本题答案为×。
【3】双循环链表中。任意一个结点的后继指针均指向其逻辑后继。
【解析】在双链表中，所有结点的后继指针指向的均为其逻辑后继。但对于双循环链表就有了一个特殊值——最后一个结点，它的后继指针指向的是链表中的第一个结点。因此，本题的答案为×。
写成语句是：
L->prior=L->next;
或
L->next=L；
或
L->prior=L;
【6】在带头结点L的双循环链表中，最后一个结点的指针是。
【解析】如图2- 所示，带头结点的双循环链表中，最后一个结点的地址记录在
图2-
头结点L的前驱指针域中。因此，本题的答案是L->prior。
【7】在只有尾指针R的单循环链表中，在表尾插入一个结点S（S为指向该结点的指针）的语句序列是。
【解析】本题考察对链表结构的基本特点的掌握。链表是一种线性表，它具有线性表的特点，所需空间与元素个数成正比。同时，它的每个元素由数据和指针两个域组成，因此，对元素的插入和删除操作只需修改指针即可。所以，（B）、（C）、（D）是正确的，而（A）不是链表的特点。
【2】如果一个链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用存储方式最节省运算时间。
S->prior=P.prior; //
P->prior=S; //
=S;
【解析】题目中的三条语句的效果如图2-2所示：
图2-2
第四条语句该处理P的前驱结点T的后继next指针的指向，因此应当是
P->prior->prior->next=S（注意：不能写成P->prior ->next=S！为什么？因为P-prior已经发生了变化，原来是指向T，而现在指向S）
图2-
2.2.3填空题
【1】在带有头结点H的单链表中，第一个元素结点的指针是。
【解析】带头结点的单链表中，第一个元素结点的指针存放在头结点H的指针域中，如图2-1所示：
因此答案为：H->next。
【2】在双循环链表中，在指针P所指结点前插入指针S所指的结点，需执行下列语句：
S->next=P; //
2.2.2判断题
判断下列叙述是否正确，正确的打√，错误的打×。
【1】在顺序表中取出第i个元素所花费的时间与i成正比。
【解析】在顺序表中，元素的物理位置是由它们的编号决定的。因此，可根据编号（下标）来随机查找任一元素，查找所花费的时间与编号无关。本题答案为×。
【2】线性表的长度是指线性表所占用的存储空间的大小。
【6】如果一个线性表最常用的操作是在最后一个元素后面插入一个元素和删除第一个元素，则采用存储方式最节省运算时间。
（A）单链表（B）双链表（C）只有头指针的单循环链表（D）只有尾指针的单循环链表
【解析】本题中的两种操作要求快速找到最后一个元素和第一个元素，不难想到，带有尾指针的单循环链表正好符合这两个要求。因此，本题的答案为（D）。
一个无限序列，可以为空；
一个无序序列，不能为空。
2，对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时大约要移动表中的（）个元素。
n/2
n+1/2
n-1/2
n
n+1
n-1
3,线性表采用链式存储时，其地址：
必须是连续的；
部分地址必须是连续的；
一定是不连续的；
连续与否均可以。
8,线性表的表元存储方式有（）和链接两种。
循环链接
单向链接
双向链接
顺序链接
三编程题
1，写出将单链表倒置的算法
2，将两个有序表合并成一个有序表
3，设计候选人得票数的算法，并按得票多少为序输出统计结果
2.2.1选择题
【1】链表不具有的特点是。
（A）可随机访问任一元素（B）插入删除不需要移动元素(C)不必事先考虑存储空间(D)所需空间与线性表长度成正比
（4）单循环链表：也只能从第一个结点开始依次找到最后一个结点。
所以本题的答案是（C）。
【5】如果线性表的最常用的操作是存取指定序号的元素和在最后进行插入和删除运算，则采用存储方式最节省时间。
（A）顺序表（B）双链表（C）带头结点的双链表（D）单循环链表
【解析】根据顺序表的适合于随机存取以及不便于在表中进行插入和删除操作的特点，可以确定本题的正确选择是（A）。
（A）单链表（B）双链表(C)带头结点的双循环链表(D)单循环链表
【解析】由于操作涉及寻找最后一个元素，对四种链表分析如下：
（1）单链表：从表中第一个结点开始到最后一个结点，时间耗费为O(n)；
（2ห้องสมุดไป่ตู้双链表：和单链表一样；
（3）带头结点的双循环链表：可以直接从头结点沿前驱指针找到最后一个结点，因此时间耗费为O(1)；
（2）双链表：和单链表一样。
（3）单循环链表：虽然可以从表尾结点直接到达表头结点，但运算开始时也是要从表头结点开始搜索，因此时间复杂度为O(n)。
（4）带头结点的双循环链表：从头结点的前驱指针可以直接到达表尾结点，因此不耗费搜索时间。所以，本题答案为（D）。
【3】如果线性表最常用的操作是存取第I个元素及其前驱的值，则采用方式存储节省时间。
8,线性表的链式存储结构优于顺序存储结构。
9,在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。
10,线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。
二单选题(请从下列A，B，C，D选项中选择一项）
1，线性表是：
一个有限序列，可以为空；
一个有限序列，不能为空；
【解析】如图2- 所示，在只有尾指针的单循环链表中，在表尾插入S指向的结点，
图2-
为了插入S所指向的结点，要修改的指针有3条，在上图中分别用数字标出。对应的语句是：
S->next=R->next;
R->next=S;
R=S;
【8】在单链表中，在指针P所指结点的后面插入一个结点S的语句序列是。
【解析】如图2- 所示，在指针P所指的结点后面插入一个结点S，要修改两条指针，已经标出。
【6】设指针P指向单链表中的一个结点，则语句序列
U=P->next；
U=U->next;
将删除一个结点。
【解析】根据图2- ，我们可以看出，执行上面两条语句的结果只是把指针U向后移动了两个元素，而没有删除结点。因此，本题的答案是×。
图2-
【7】带头结点的单循环链表中，任一结点的后继指针均不空。
【解析】如图2- 是单循环链表的状态，可以看出，每个结点的后继指针均有所指。因此，本题的答案是√。
((p↑.llink)↑.llink)↑.rlink:=p p↑.llink:=(p↑.llink)↑.llink
7,在双向循环链表中，在p所指的结点之后插入指针f所指的结点，其操作是（）。
p↑.rlink:=f; f↑.rlink:=p; (p↑.rlink)↑.llink:=f; f↑.rlink:=p↑.rlink
（A）单链表（B）双链表(C)单循环链表(D)顺序表
【解析】由于顺序表中对元素的存取可以直接根据编号（下标）。因此当指定存取元素的编号时，用顺序表作为链表的存储方式最节省时间。本题的正确答案是D。
【4】如果一个链表最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用方式存储最节省时间。
4,设单链表中指针p指着结点M，指针f指着将要插入的新结点X，问：
X插在链表中两个数据元素M和N之间时，先修改（）。
p↑.link:=f
p↑.link:=p↑.link↑.link
p↑.link:=f↑.link
f↑.link:=p↑.link
f↑.link:=NIL
f↑.link:=P
5,设单链表中指针p指着结点A,若要删除A之后的结点(若存在),则需修改指针的操作为（）。
p↑.rlink:=f; (p↑.rlink)↑.llink:=f; f↑.llink:=p; f↑.rlink:=p↑.rlink
f↑.llink:=p; f↑.rlink:=p↑.rlink; p↑.rlink:=f; (p↑.rlink)↑.llink:=f