基本概念

线性表

线性表（Linear List）是具有相同数据类型的 n 个数据元素的有限序列，记作 $L=(a_1, a_2, \ldots, a_n)$ 。

顺序表：元素地址连续，支持随机访问

存储结构对比

存储方式	地址连续	支持随机访问	插入/删除效率	空间利用率
顺序表	是	是	低	低
链表	否	否	高	高

线性表的特点是（）

A. 元素个数固定不变 B. 除首尾外每个元素有且仅有一个前驱和一个后继 C. 存储地址必须连续 D. 所有元素类型可以不同

答案与解析

答案：B

解析：线性表是 n 个相同类型元素的有限序列，除首尾外每个元素有且仅有一个直接前驱和直接后继。C 是顺序表的特征而非线性表的必要特征；D 错误，线性表要求元素类型相同。

简述线性表的定义和主要特点。

答案与解析

线性表是 n（n≥0）个相同类型数据元素的有序序列，有唯一首尾，除首尾外每个元素有且仅有一个前驱和一个后继，元素间是一对一的线性关系。

顺序表和链表各自的优缺点是什么？

答案与解析

顺序表：优点——支持随机访问、查找快（ $O(1)$ ）、存储密度高；缺点——插入/删除需移动大量元素（ $O(n)$ ）、空间利用率低（需要预分配）。

链表：优点——插入/删除快（ $O(1)$ ，定位后）、空间按需分配、利用率高；缺点——不支持随机访问、查找慢（ $O(n)$ ）、每个结点需额外存储指针、存储密度低。