第二章习题
一判断题
1．线性表的逻辑顺序与存储顺序总是一致的。

×
2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

×
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

×
6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

×9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

×
11.线性表中每个元素都有一个直接前驱和一个直接后继。

（×）
12.线性表中所有元素的排列顺序必须由小到大或由小到小。

（×）
13.静态链表的存储空间在可以改变大小。

（×）
14.静态链表既有顺序存储结构的优点，又有动态链表的优点。

所以它存取表中第i个元素的时间与i无关。

（×）
15.静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加。

（）
16.静态链表与动态链表的插入、删除操作类似，不需要做元素的移动。

（）
17.线性表的顺序存储结构优于链式结构。

（×）
18.在循环单链表中，从表中任一结点出发都可以通过前后的移动操作扫描整个循环链表。

（×）
19.在单链表中，可以从头结点开始查找任何一个结点。

（）
20.在双链表中，可以从任何一结点开始沿同一方向查找到任何其他结点。

（×）
二单选题 (请从下列A，B，C，D选项中选择一项)
1．线性表是( ) 。

(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空；
(C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。

，在任何位置上插入或删除操作都是等概率的。

插n．对顺序存储的线性表，设其长度为2．
入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B) n+1/2 (C) （n -1）/2 (D) n
3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的； (B) 部分地址必须是连续的；
(C) 一定是不连续的； (D) 连续与否均可以。

4．用链表表示线性表的优点是（）。

(A)便于随机存取
(B)花费的存储空间较顺序存储少
(C)便于插入和删除
(D)数据元素的物理顺序与逻辑顺序相同
5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

(A)单链表
(B)双链表
(C)单循环链表
(D)带头结点的双循环链表
6．循环链表的主要优点是( ) 。

(A)不在需要头指针了
(B)已知某个结点的位置后，能够容易找到他的直接前趋
(C)在进行插入、删除运算时，能更好的保证链表不断开
(D)从表中的任意结点出发都能扫描到整个链表
7．下面关于线性表的叙述错误的是( )。

(A)线性表采用顺序存储，必须占用一片地址连续的单元；
(B)线性表采用顺序存储，便于进行插入和删除操作；
(C)线性表采用链式存储，不必占用一片地址连续的单元；
(D)线性表采用链式存储，不便于进行插入和删除操作；
8．单链表中，增加一个头结点的目的是为了（）。

(A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置
（C）方便运算的实现 (D) 说明单链表是线性表的链式存储
9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

(A) 单链表 (B) 仅有头指针的单循环链表
(C) 双链表 (D) 仅有尾指针的单循环链表
）个元素的前趋元素，则采用（i个元素和找第i某线性表中最常用的操作是取第若．10．存储方式最节省运算时间（）。

(A) 单链表 (B) 顺序表
(C) 双链表 (D) 单循环链表
11．对一个具有n个元素的线性表，建立其单链表的时间复杂度为（）
A）O(n) （B） O(1) （C）O(n) （D）O(logn)2三填空题
2（
1．带头结点的单链表H为空的条件是_______H->next==null___________。

1．非空单循环链表L中*p是尾结点的条件是_____p->next==L_____________。

3．在一个单链表中p所指结点之后插入一个由指针f所指结点，应执行
f->next=p->next________;和p->next=_f____________的操作。

4．在一个单链表中p所指结点之前插入一个由指针s所指结点，可执行以下操作：
s->next=p->next__;
p->next=s;
t=p->data;
p->data= ____ s->data _______;
s->data= ____ t _______;
5．在顺序表中做插入操作时首先检查___是否满_____________。

6．在一个单链表中删除p结点时，应执行下列操作：
q=p->next;
p->data=p->next->data;
p->next=__q->next__________
delete q;
7．在双向链表中，每个结点含有两个指针域，一个指向_____结点，另一个指向____结点。

四算法设计题
1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。

试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性。

并且分析算法的时间复杂度。

2．已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。

3．编写一个函数，从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较高的效率来实现。

提示：可以先将顺序表中所有值在x~y之间的元素置成一个特殊的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素将其删除掉。

4．线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R中的字符按字母字符、数字字符和其它字符的顺序排列。

要求利用原来的存储空间，元素移动次数最小。

．
5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。

即将线性表
（a, a, … , a, b, b, … , b）改变为：nm2112（b, b, … , b , a, a, … , a）。

mn21216．已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x 的结点插入到表L中，使得L仍然有序。

并且分析算法的时间复杂度。

7．假设有两个已排序的单链表A和B，编写一个函数将他们合并成一个链表C而不改变其排序性。

8．假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写一个函数删除该结点的前趋结点。

9．已知两个单链表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的单链表形式存储。

10．设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度freq 域，在链表被起用之前，该域其值初始化为零。

每当在链表进行一次Locata(L,x)运算后，令值为x的结点中的freq域增1，并调整表中结点的次序，使其按访问频度的递减序列排列，以便
使频繁访问的结点总是靠近表头。

试写一个算法满足上述要求的Locata(L,x)算法。

11．设计算法以判断带头结点的双向循环链表L是否是对称的，即从前往后和从后往前的输出序列是相同的。

若对称，返回1，否则返回0。