第二章 线性表练习题（1）

一、单项选择题

1、链式存储结构的最大优点是（D ）。

A.便于随机存取 C.无需预分配空间

B.存储密度高

D.便于进行插入和删除操作

2、假设在顺序表{a0,a1,……,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（D ）。

A. 106 B. 107 C.124 D.128

3、 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（A）存储方式。

A.顺序表

C.不带头结点的单链表

B. 带头结点的单链表 D. 循环单链表

4、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：C （A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构 5、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 B （A）110 （B）108 （C）100 （D）120

6、 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：A

（A） 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B） 在第i个结点后插入一个新结点（1≤i≤n） （C） 删除第i个结点（1≤i≤n） （D） 将n个结点从小到大排序

7、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 B 个元素

（A）8 （B）63.5 （C）63 （D）7 8、下述哪一条是顺序存储结构的优点？（ ）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

9、下面关于线性表的叙述中，错误的是哪一个？ C A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。

10、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 二、填空

1、在顺序表中插入或删除一个元素，需要平均移动__一半______元素，具体移动的元素个数与 表长和该元素在表中的位置 有关。

2、 线性表中结点的集合是 有限 的，结点间的关系是 一对一 的。

3、 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n -i+1 个元素。

4、 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。

5、 在顺序表中访问任意一结点的时间复杂度均为 0(1) ，因此，顺序表也称为 随机存取 的数据结构。

6、.顺序表中逻辑上相邻的元素的物理位置 必定 相邻。单链表中逻辑上相邻的元素的物理位置 不一定 相邻。线性表是由n（n≥0）个数据元素所构成的 有限序列 ，其中n为数据元素的个数，称为线性表的 长度 ，n=0的线性表称为 空表 。

7、 线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点之外，其它每一个数据元

素有且仅有一个 前驱 ，有且仅有一个 后继 。

8、 线性表通常采用 顺序存储 和 链式存储 两种存储结构。若线性表的长度确

定或变化不大，则适合采用 顺序存储 存储结构进行存储。

9、 在顺序表{a0,a1,……,an-1}中的第i(0≤i≤n-1)个位置之前插入一个新的数据元素，会引起

n-i个数据元素的移动操作。