文档介绍：: .
静态分配的，而链
表的存储空间是动态分配的。
B、顺序表占的存储空间必须是连续的，而
链表占的存储空间可以是连续的 ，也可是不
连续的
C、顺序表存储密度为 1，而链表中的每个结
点，除了数据域外，还要额外的设置指针域 ，
存储密度小于 1
2、基于时间的考虑：
A、在链表中的任何位置上进行插入和删除 ，
只需要修改指针，而顺序表中平均将要移动
近一半的结点。
B、顺序表是随机存取结构，它的存取时间
为 O(1)，而链表需从头结点顺着链扫描链
表。
总之，当线性表的长度变化不大，易于
事先确定其大小时，为了节约存储空间 ，宜
第 5 页，共 36 页全国计算机等级考试二级公共基础知识
采用顺序表作为存储结构 ；当线性表的长度
变化较大，难以估计其存储规模时 ，以采用
链表作为存储结构为好 。若线性表的操作主
要是进行查找，很少做插入和删除操作时 ，
采用顺序表做存储结构为宜 ；对于频繁进行
插入和删除的线性表，宜采用链表做存储结
构。
例：关于线性表的描述中，错误的是（ ）
A、线性表是线性结构 B、线性表的顺序
存储结构，必须占用一片连续的存储单元
C、线性表是单链表 D、线性表的链式
存储结构，不必占用一片连续的存储单元
用数组表示线性表的优点是（ ）
A、便于插入和删除操作 B、便
于随机存取
C、可以动态地分配存储空间 D、不
需要占用一片连续的存储空间
三、栈：
�栈(Stack)：是限制仅在表的一端进行插
入和删除运算的线性表，通常称插入 、删
第 6 页，共 36 页全国计算机等级考试二级公共基础知识
除的这一端为栈顶 (Top)，另一端称为栈
底 (Bottom) 。当表中没有元素时称为空
栈。是一种后进先出的线性表，又称 为
LIFO 表。
�栈的基本运算有：
栈的初始化、判栈空、判栈满、进栈 、出
栈等
�栈的存储：
顺序存储、链式存储
例：若进栈的输入序列是 A、B、C、D、E，
并且在它们进栈的过程中可以进行出栈操
作，则不可能出现的出栈序列是（ ）
A、EDCBA B、DECBA C、
DCEAB D、ABCDE
四、队列：
�队列 (Queue)：也是一种运算受限的线性
表，它只允许在表的一端进行插入 ，而在
另一端进行删除。允许删除的一段称为队
头 (Front) ，允许插入的一段称为队尾
(Rear)。（类似于生活中的购物排队 ）。是
第 7 页，共 36 页全国计算机等级考试二级公共基础知识
一种先进先出的线性表，又称为 FIFO 表。
�队列的基本运算：
队列的初始化、判队空、判队满、入队 、
出队
�队列的存储实现：
顺序存储、链式存储
例：一个队列的入队序列是 1，2，3，4，
则队列的输出序列是 （ ）
A、4，3，2，1 B、1，2，3，4 C、
1，4，3，2 D、3，2，4，1
五、串：
�串(String)：是零个或多个字符组成的有
限序列。
串中所包含的字符个数称为该串的长度 。
串中任意个连续字符组成的子序列称为
该串的子串，包含子串的串相应地称为主串
注：空串是任意串的子串，任意串是其自
身的子串
�串有串常量、串变量之分：
1、串常量在程序中只能被引用但不能改