第二章 线性表

1. 填空题

(1) 若某线性表采用顺序存储结构，每个元素占四个存储单元，首地址为100，则下标为11的(第12个)元素的存储地址为（ ） 。

(2) 线性表的链式存储结构主要包括（ ）、（ ）和（ ）三种形式。

(3) 线性表的顺序存储结构是通过（ ）来直接反映数据元素之间的逻辑关系，而链式存储结构是通过（ ）间接反映数据元素之间的逻辑关系。

(4) 若对线性表进行的操作主要不是插入和删除，则该线性表宜采用（ ）存储结构；若频繁地对线性表进行插入和删除操作，则该线性表宜采用（ ）存储结构。

2. 设有一线性表e=(e1 , e2 , … , en-1 , en)，其逆线性表定义为e'=( en , en-1 , … , e2 , e1)，请设计一个算法，将线性表置逆，要求逆线性表仍占用原线性表的空间，并且用顺序表和单链表两种方法来表示，写出不同的处理函数。

3. 已知长度为n的线性表A采用顺序存储结构，请写一算法，找出该线性表中值最小的数据元素。

4. 已知线性表A的长度为n，并且采用顺序存储结构。写一算法，删除线性表中所有值为x的元素。

5. 已知list是指向无头结点的线性链表的指针变量，写出删除该链表下标为i的(第i+1个)结点的算法。

6. 已知list是指向无头结点的线性链表的指针变量，写出删除该链表中从下标为i的(第i+1个)结点开始的连续k个结点的算法。

7. 请分别对顺序表和单链表写出求线性表中下标为i的(第i+1个)元素的前驱和后继的算法。

8. 请设计算法求线性表中第一个值为x的元素的前驱和后继的存储位置，要求采用顺序表和单链表两种方法来表示。

9. 编写一算法，删除单链表中值相同的多余结点，即：若链表中有多个结点具有相同的数

据域值，只保留其中一个结点，其余结点均从链表中删去，使得最后得到的链表中的所有结点的数据域都不相同。

10. 请设计一个算法，求出循环表中结点的个数。

11. 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。

12. 设线性表X=( x1, x2, … , xn )与线性表Y=( y1 , y2 , … , ym )都采用单链式存储结构。试写一个算法归并这两个线性表为一个线性表，使

13. 在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？

14. 设线性表的n个结点定义为(a0,a1,…,an-1)，重写顺序表上实现的插入和删除算法：InsertList和DeleteList。

15. 试用顺序表作为存储结构，实现线性表(a0,a1,…,an-1)就地逆置的操作，所谓\"就地\"指辅助空间应为O(1)。

16. 设顺序表L是一个递增有序表，试写一算法将x插入L中，并使L仍是一个有序表。

上 机 题

1. 试将本章介绍的两种Josephus问题的求解过程在计算机中实现，实现时要求输出的不是

整数，而是实际的人名。

2. 设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的指针。请写出并在计算机上实现将这两个链表合并为一个带头结点的有序循环链表的算法。