线性表
1.线性表的定义：
- 存在唯一一个"第一个"元素
- 存在唯一一个“最后一个”元素
- 除第一个元素外，每一个元素都有且只有一个前驱
- 除最后一个元素外，每个元素都有且只有一个后继
2.优点：
- 存储密度大（结点本身所占存储量/结点结构所占存储量）
- 可以随机存取表中任一元素
3.缺点：
- 在插入、删除某一元素时，需要移动大量元素
- 浪费存储空间
- 属于静态存储形式，数据元素的个数不能自由扩充
单链表链式存储结构（链表）
1.链表的基本概念
各结点由两个域组成：
数据域：存储元素数值数据
指针域：存储直接后继结点的存储位置
2.单链表、双链表、循环链表：
- 结点只有一个指针域的链表，称为单链表或线性链表
- 有两个指针域的链表，称为双链表
- 首尾相接的链表称为循环链表
3.头指针、头结点、首元结点
- 头指针是指向链表中第一个结点的指针
- 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息
- 首元结点是指链表中存储第一个数据元素a1的结点
顺序表和链表的比较
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
（1）在数据结构中，从逻辑上可以把数据结构分成（ C ）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构
C．线性结构和非线性结构 D．内部结构和外部结构
（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ C ）。
A．存储结构 B．存储实现
C．逻辑结构 D．运算实现
（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ B ）。
A．数据具有同一特点
B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C．每个数据元素都一样
D．数据元素所包含的数据项的个数要相等
（4）以下说法正确的是（ D ）。
A．数据元素是数据的最小单位
B．数据项是数据的基本单位
C．数据结构是带有结构的各数据项的集合
D．一些表面上很不相同的数据可以有相同的逻辑结构
解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。
（5）算法的时间复杂度取决于（ D ）。
A．问题的规模 B．待处理数据的初态
C．计算机的配置 D．A和B
解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。
（6）以下数据结构中，（ A ）是非线性数据结构
A．树 B．字符串 C．队列 D．栈