A．提高查找速度 B．更方便数据的插入和删除 C．节约存储空间 D．很快回收存储空间
（20） 与单链表相比，双链表的优点之一是（ ）。 A．插入和删除操作更简单 B．可以进行随机访问 C．可以省略表头指针或表尾指针 D．访问其后相邻结点更灵活
（21） 带头结点的循环双链表L为空表的条件是（ ）。 A．L->next->prior=NULL B．L->prior=L C．L->next=L D．B和C都对
（22） 在循环双链表的p所指结点后插入s所指结点的操作是（ ）。 A．p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B．p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; C．s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; D．s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
（23） 在双链表中指针pa所指结点后面插入pb所指结点，执行的语句序列是（ ）。 ①pb->next=pa->next; ②pb->prior=pa; ③pa->next=pb; ④pa->next->prior=pb; A．①②③④ B．④③②① C．③④①② D．①④③②
（24） 在一个双链表中，删除结点p的操作是（ ）。 A．p->prior->next=p->next; p->next->prior=p->prior; B．p->prior=p->prior->prior; p->prior->prior=p; C．p->next->prior=p; p->next=p->next->next;
D．p->next=p->prior->prior; p->prior=p->prior->prior;
应用题
（25） 单链表设置头结点的作用是什么？
（26） 线性表的顺序存储结构具有三个弱点：其一，插入或删除操作需要移动大量元
素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。试问，线性表的链接存储结构是否能够克服上述三个弱点？
（27） 若频繁地对一个线性表进行插入和删除操作，该线性表采用什么存储结构比较
好？
（28） 设n表示线性表中的元素个数，P表示指针所需的存储单元大小，E表示存储
数据元素所需的存储单元大小，则使用单链表存储方式存储该线性表需要多少存储空间（不考虑头结点）？
算法设计题
11
（29） 设计算法依次打印单链表中每个结点的数据信息。
（30） 求单链表的长度。
（31） 设计算法将值为x的结点插入到不带头结点的单链表L中值为k的结点之前，
若找不到值为k的结点，则将x插入到链表的末尾。
（32） 判断非空单链表是否递增有序。
（33） 已知非空线性链表由list指出，结点结构为（data，link）。请编写算法，将链
表中数据域最小的结点移到链表的最前面。要求：不得额外申请新的结点。
（34） 给定一个带头结点的单链表，设head为头指针，设计算法按递增次序输出单
链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作辅助空间）。
（35） 已知非空线性链表由list指出，设计算法交换p所指结点与其后续结点在链表中的位置（设p所指结点不是链表的最后一个结点）。
（36） 设计算法实现将单链表就地逆置。
（37） 头插法建立单链表。
（38） 尾插法建立单链表
（39） 复制一个单链表。
（40） 设计算法实现将单链表就地逆置。
（41） 在一个有序单链表（假设从小到大排列）中插入一个元素值为x的结点，使得插入后单链表仍然有序。
（42） 设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结
点。
（43） 已知单链表中各结点的元素值为整型且递增有序，设计算法删除表中大于
mink且小于maxk的所有元素，并释放被删结点的存储空间。
（44） 有两个整数序列A=(a1，a2，?，am)和B=(b1，b2，?，bn)已经存入两个单链
表中，设计算法判断序列B是否是序列A的子序列。
（45） 设线性表C=(a1，b1，a2，b2，?，an，bn)采用带头结点的单链表存储，设计算
法将表C拆分为两个线性表A和B，使得A=(a1，a2，?，an)，B=(b1，b2，?，bn)。
12
（46） 有两个递增有序的单链表la和lb，设计算法将这两个单链表合并为一个有序
链表。
（47） 有两个有序的单链表，一个表为升序，另一个表为降序，设计算法将这两个链
表合并为一个有序链表。
（48） 已知单链表A和B的数据（设为整型）递增有序，设计算法利用原有结点，
将表A中与表B具有相同值的结点删除，将表B中与原表A不同值的结点存入表A中，并保持表A的递增有序。
（49） 设计算法将循环单链表就地逆置。
（50） 已知L为单链表的头结点地址，表中共有m（m＞3）个结点，从表中第i个（1
＜i＜m）结点起到第m个结点构成一个部分循环链表。设计算法将这部分循环链表中所有结点顺序完全倒置。
（51） 假设在长度大于1的循环单链表中，即无头结点也无头指针，s为指向链表中
某个结点的指针，试编写算法删除结点s的前驱结点。
（52） 设循环单链表L1，对其遍历的结果是：x1，x2，x3，?，xn-1，xn。请将该循
环链表拆成两个循环单链表L1和L2，使得L1中含有原L1表中序号为奇数的结点且遍历结果为：x1，x3，?；L2中含有原L1表中序号为偶数的结且遍历结果为：?，x4，x2。
（53） 已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。试编写算
法，构造三个循环单链表，使每个循环链表中只含同一类字符。
（54） 有两个循环链表tail1和tail2（tail1和tail2分别指向循环链表的尾指针），编
写算法将循环链表tail2链接到循环链表tail1之后，并使链接后的链表仍是循环链表。
（55） 已知p指向循环单链表最后一个结点的指针，试编写只包含一个循环的算法，
将线性表（a1，a2，?，an-1，an，）改造成（a1，a2，?，an-1，an，an-1，?，a2，a1）。
（56） 判断带头结点的循环双链表是否对称。
（57） 设计算法实现双链表中第i个结点的前面插入一个值为x的结点。
（58） 已知非空循环双链表head的存储结构为： Struct DNode { TElem info; Struct DNode *left; Struct DNode *right;
13
};
设计算法实现从链表中删除指针p所指结点的前驱结点（假设该结点存在）。
（59） 已知非空双链表由d指出，结点结构为（priordatanext），请设计算法将链表中
数据值最大（假定唯一）的那个结点移至链表的最前面。要求不得额外申请新的双链表结点。
（60） 设计算法实现将双链表中结点p与其后继结点互换位置。
（61） 设有一个双链表，每个结点中除了有prior、data和next三个域外，还有一个
访问频度域freq，在链表被起用之前，其值均初始化为零，每当在双链表上进行一次LOCATE运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。编写算法实现符合上述要求的LOCATE算法。
14
5 静态链表
选择题
（1） 静态链表中指针表示的是（ ）。 A．下一结点在内存中的地址 B．下一元素在数组中的下标 C．左、右孩子的存储位置 D．左、右孩子的地址
（2） 以下说法错误的是（ ）。
①静态链表既有顺序存储的优点又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关
②静态链表中能容纳的元素个数在定义表时必须是确定的
③静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动 A．①，② B．① C．①，②，③ D．②
（3） 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中某结点，
使j沿链移动的操作为（ ）。 A．j=r[j].next B．j=j+1 C．j=j->next D．j=r[j]->next
（4） 线性表的静态链表存储与顺序存储相比，优点是（ ）。 A．所有基本操作的算法实现简单 B．便于随机存取 C．便于插入和删除 D．便于利用零散的存储空间
（5） 下图所示数组中以静态链表形式存储了一个线性表，设头指针为a[0].link，则
该线性表的元素依次为（ ）。
下标 0 1 2 3 4 5 6 7 8
data link
4 60 63 40 45 3 7 6 2 74 25 0 1 A．60，63，40，45，74，25 C．74，25，45，60，40，63
B．45，63，25，60，40，74 D．25，45，60，40，63，74
15