线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

线性表，全名为线性存储结构。使用线性表存储数据的方式可以这样理解，即“把所有数据用一根线儿串起来，再存储到物理空间中”。

如图 1 所示，这是一组具有“一对一”关系的数据，我们接下来采用线性表将其储存到物理空间中。

首先，用“一根线儿”把它们按照顺序“串”起来，如图 2 所示：

图 2 中，左侧是“串”起来的数据，右侧是空闲的物理空间。把这“一串儿”数据放置到物理空间，我们可以选择以下两种方式，如图 3 所示。

图 3a) 是多数人想到的存储方式，而图 3b) 却少有人想到。我们知道，数据存储的成功与否，取决于是否能将数据完整地复原成它本来的样子。如果把图 3a) 和图 3b) 线的一头扯起，你会发现数据的位置依旧没有发生改变（和图 1 一样）。因此可以认定，这两种存储方式都是正确的。

将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表）。

具有“一对一”逻辑关系的数据，最佳的存储方式是使用线性表。

使用线性表存储的数据，如同向数组中存储数据那样，要求数据类型必须一致，也就是说，线性表存储的数据，要么全部都是整形，要么全部都是字符串。一半是整形，另一半是字符串的一组数据无法使用线性表存储。

图 3 中我们可以看出，线性表存储数据可细分为以下 2 种：

如图 3a) 所示，将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构（简称顺序表）

如图 3b) 所示，数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构（简称链表）

也就是说，线性表存储结构可细分为顺序存储结构和链式存储结构。

数据结构中，一组数据中的每个个体被称为“数据元素”（简称“元素”）。例如，图 1 显示的这组数据，其中 1、2、3、4 和 5 都是这组数据中的一个元素。

另外，对于具有“一对一”逻辑关系的数据，我们一直在用“某一元素的左侧（前边）或右侧（后边）”这样不专业的词，其实线性表中有更准确的术语：

以图 1 数据中的元素 3 来说，它的直接前驱是 2 ，此元素的前驱元素有 2 个，分别是 1 和 2；同理，此元素的直接后继是 4 ，后继元素也有 2 个，分别是 4 和 5。如图 4 所示：

广义表(Lists，又称列表)是一种非线性的数据结构，是线性表的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。（书上规定了列表的表头可以是原子或者子表，但是表尾必须是子表）

原子和子表：

通常，广义表中存储的单个元素称为 “原子”，而存储的广义表称为 “子表”。

例如创建一个广义表 LS = {1,{1,2,3}}，我们可以这样解释此广义表的构成：广义表 LS 存储了一个原子 1 和子表 {1,2,3}。

当广义表不是空表时，称第一个数据（原子或子表）为"表头"，剩下的数据构成的新广义表为"表尾"。 强调一下，除非广义表为空表，否则广义表一定具有表头和表尾，且广义表的表尾一定是一个广义表。

例如在广义表中 LS={1,{1,2,3},5} 中，表头为原子 1，表尾为子表 {1,2,3} 和原子 5 构成的广义表，即 {{1,2,3},5}。

再比如，在广义表 LS = {1} 中，表头为原子 1 ，但由于广义表中无表尾元素，因此该表的表尾是一个空表，用 {} 表示。

关于广义表的三个重要结论：

A. 寻找最大项 B. 堆排序 C. 快速排序 D. 顺序查找法

正确答案: A

答案解析：

A. 初等结构、构造型结构 B. 线性结构、非线性结构 C. 动态结构、静态结构 D. 顺序结构、链式结构

正确答案： B

答案解析：

数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。

A. 线性表可以是空表 B. 线性表的所有节点有且仅有一个前件和后件 C. 线性表是由N个元素组成的有限序列 D. 线性表是一种线性结构

正确答案：

答案解析：

线性表是一种线性结构，由n(n≥O)个元素组成，所以线性表可以是空表（线性表中没有元素时,就是一个空表）。但是在线性表中，第一个结点没有前件，最后一个结点没有后件，其他结点有且只有一个前件和后件，

A. 二叉排序树的平均查找长度和二叉排序树的形态无关 B. 顺序查找法要求代查找表应采用顺序存储结构且按关键字大小有序排列 C. 折半查找法要求代查找表应采用顺序存储结构且按关键字大小有序排列 D. 二叉排序树可以通过逐个插入节点算法来创建

正确答案： CD

答案解析：

在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关，最差的情况是二叉排序树为 单支树 的时候。

顺序查找法不需要关键字有序排列

A. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。 B. 栈和队列都是线性表，只是在插入和删除时收到了一些限制。 C. 所谓取广义表的表尾就是返回广义表中最后一个元素 D. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。

正确答案： C

答案解析：

n为表的长度，当n = 0时，LS为空表；n >0时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表称为广义表的表尾(tail)。即当a1为表头元素时，(a2,a3 ……an)为表尾元素。