3.1 线性结构（线性表、栈、队列）

2026-11-03 11:43:00上一篇 / 下一篇

本篇定位：数据结构与算法是计算机专业知识的基础理论区（单选 21–40 段前中段），9 年题量 0–4 题、均值约 1.5 题——权重低位但 2024/2025 连续两年回升（各 3 题），且考点集中在线性结构判定、栈/队列特性与应用、单链表查找、排序每趟定位、折半查找、复杂度六类，命题"小而稳"。本章是数据结构第一篇：线性表、栈、队列、串——先把"一对一"逻辑结构讲透。数据依据：01-真题/真题文本/ 9 份真题原文 + 01-真题/考点汇总/ 9 份汇总；答案以专业判断为准。阅读提示：与 2.4 程序设计（数组/指针实现线性表）衔接；队列在 2.2 操作系统（就绪队列）与 5.x 网络（报文队列）中反复出现，此处打基础。

一、考点定位（本章真题统计）

考点	真题锚点	频次	考法
线性结构判定	2019 单38	1 年	哪个是线性结构（串 vs 广义表/二叉树/稀疏矩阵）
栈与队列特性	2019 多84、2022 单24	2 年	栈底元素入栈次序、"栈与队列操作特性相同"判断、队列是先进先出的线性表
队列应用	2025 单21	1 年	打印缓冲区选队列（先进先出）
单链表查找	2025 单49	1 年	N 节点单链表查找成功平均比较 (N+1)/2 次

命题规律：9 年纯线性结构题共 5 题，全部落在"概念判定 + 简单计算"层——不考链表指针操作细节、不考复杂表达式求值。2027 预测 1–2 题：栈/队列应用场景判定（先进先出 vs 后进先出）、线性/非线性结构分类。核心能力：看到"先进先出/后进先出"场景能立刻选队列/栈。

二、知识框架（先搭骨架）

数据结构 = 逻辑结构（数据的组织方式）+ 存储结构（计算机中的存放方式）+ 运算

逻辑结构按"元素间关系"分两大类：
├── 线性结构：元素一对一（每个元素最多一个直接前驱、一个直接后继）
│   ├── 线性表（顺序表 / 链表）
│   ├── 栈（后进先出 LIFO）
│   ├── 队列（先进先出 FIFO）
│   └── 串（字符串，线性结构！）
└── 非线性结构：一对多 / 多对多
    ├── 树（二叉树等）：一对多
    ├── 图：多对多
    └── 广义表、多维数组、稀疏矩阵：非线性

线性表两种存储结构：
├── 顺序存储（顺序表）：连续内存、随机存取 O(1)、插入/删除 O(n)
└── 链式存储（链表）：节点 + 指针、动态分配、插入/删除 O(1)（已知位置）、
    查找 O(n)；单向/双向/循环链表

栈（LIFO）：
├── 只在一端（栈顶）插入删除；栈底最先入栈、最后出栈
└── 应用：函数调用、括号匹配、表达式求值、撤销操作、浏览器后退

队列（FIFO）：
├── 队尾插入、队首删除
├── 循环队列（顺序实现，解决假溢出）
└── 应用：打印缓冲区、进程调度、消息队列、银行叫号

一句话记忆：逻辑结构分线性（一对一：线性表/栈/队列/串）与非线性（树/图/广义表/多维数组）；线性表两种存法（顺序表随机存取、链表灵活插入）；栈后进先出、队列先进先出——"栈底最先入栈，队列队尾入队首出队"。

三、考点详解

3.1 线性结构的定义与分类（2019 单38，必考）

精确定义：线性结构 = 数据元素之间存在一对一线性关系（除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继）。

线性结构清单：线性表、栈、队列、串（字符串）、数组（一维）。 非线性结构清单：树（二叉树）、图、广义表、稀疏矩阵、多维数组。

2019 单38 直接考"哪个是线性结构"——答案是"串"。这是本章最容易错的一题：串（字符串）是线性结构（字符按顺序排列、一对一），而广义表（元素可以是子表，层次嵌套）、二叉树（一对多）、稀疏矩阵（多为二维结构）都是非线性。

3.2 线性表：顺序表 vs 链表

精确定义：线性表 = 由 n（n≥0）个同类型数据元素组成的有限序列。

特性	顺序表（顺序存储）	链表（链式存储）
存储方式	连续内存单元	节点分散，指针链接
随机存取	✅ O(1)（按下标直接算地址）	❌ O(n)（须从头遍历）
插入/删除	O(n)（移动大量元素）	O(1)（已知位置改指针）
空间	需预分配（可能浪费/溢出）	动态分配（不浪费，但指针占额外空间）
适用	查找多、改动少	插入删除频繁、长度不定

为什么链表插入是 O(1)（这张表最容易读错的一格）：O(1) 的前提是"位置已知"——表里"（已知位置改指针）"那半句不是修饰，是限定条件。

顺序表（连续）：[A][B][C][D]   在 B 后插 X → C、D 全体后移（移动 n−i 次 → O(n)）
链表（分散）  ：A→B→C→D       在 B 后插 X → 只改两条指针（2 次赋值 → O(1)）

代码只有两行，顺序不能反：s->next = p->next; 在前、p->next = s; 在后。先写第二行会把 B 原来指向 C 的信息丢掉、断链。
复杂度要拆开看："在第 i 个位置插入"整体是 O(n)——单链表只能从头走 i−1 步找前驱（定位 O(n)），插进去本身才是 O(1)；只有"在结点 p 之后插入"与"头插法"是真 O(1)。
对照：顺序表恰好相反——定位 O(1)（地址＝首地址＋i×元素大小）、插入 O(n)（挪元素）。⇒ 口诀：顺序表算地址快、挪元素慢；链表找位置慢、改指针快。
延伸：头插法建表每步 O(1)（n 个元素建表 O(n)）；双向链表删除给定结点 O(1)（前驱后继都在手上），单链表删给定结点要 O(n)（得先找前驱）。
⚠️ 考法：见到"链表插入/删除 O(1)"先问"位置给了没"——给了才对；只说"第 i 个"，就是 O(n)。

单链表查找（2025 单49）：N 个节点的单链表查找关键字为 K 的节点，查找成功时：

最好 1 次（第一个就是）、最坏 N 次（最后一个才找到）；
平均 (1+2+…+N)/N = (N+1)/2 次（每个位置等概率）。

2025 单49 答案 C（N+1）/2。注意对比顺序表的折半查找（见 3.3 章）——链表不能折半（无法随机存取），只能顺序找，平均比较 (N+1)/2。

3.3 栈（Stack）：后进先出

精确定义：栈 = 只允许在栈顶进行插入（入栈/push）和删除（出栈/pop）操作的线性表，操作特性后进先出（LIFO）。

关键性质（2019 多84 考点）：

栈底元素一定是最先入栈的元素（栈底不参与操作，最后才能出栈）；
出栈次序与入栈次序相反（后进先出）；
"栈底元素一定是最后入栈的元素"是错误说法（2019 多84 的 A 项，选它）。

栈的应用场景（考法：给场景选结构）：

函数调用与递归（调用栈，后调用的先返回）；
括号匹配、表达式求值（中缀→后缀）；
撤销操作（Ctrl+Z）、浏览器后退、Word 撤销；
迷宫求解（回溯）。

3.4 队列（Queue）：先进先出

精确定义：队列 = 只允许在队尾插入（入队）、在队首删除（出队）的线性表，操作特性先进先出（FIFO）。

2022 单24 直接考：队列是先进先出的线性表（C 项正确；"先进后出"是栈的特性，D 错；"只能插入/只能删除"片面，A/B 错）。

队列的应用场景（2025 单21 考点）：

打印缓冲区（2025 单21）：柜面终端与票据打印机速度不匹配，逐条依次传递打印需求 → 先来的需求先打印 → 队列；
操作系统进程调度就绪队列、消息队列；
银行/医院叫号、排队系统、消息中间件（FIFO 消息）。

场景判定口诀：先来先服务、先进先出 → 队列；后来先服务、后进先出 → 栈。 打印缓冲区是"逐条依次"——先进先出，选队列。

循环队列：顺序存储的队列用数组实现，头尾指针循环使用空间（解决"假溢出"——数组未满但队尾已到末尾）。判空/判满常用牺牲一个存储单元：(rear+1) % maxsize == front 判满、front == rear 判空。

四、易错坑汇总（命题人惯用陷阱）

串是线性结构（2019 单38）——字符串按字符顺序一对一排列，属线性；广义表、二叉树、稀疏矩阵、多维数组是非线性。这是本章第一坑。
栈底元素最先入栈（2019 多84）——"栈底元素一定是最后入栈"是错误说法（栈底最先入栈、最后出栈）。同理"栈顶元素最先入栈"也不对（栈顶随时在变）。
"栈与队列操作特性相同"是错误说法（2019 多84 的 D 项）——栈后进先出、队列先进先出，特性不同。
队列=先进先出、栈=后进先出（2022 单24）——"先进后出"指栈，别张冠李戴。
场景题选结构（2025 单21）——"逐条依次传递、先来先打印"是队列；若题干说"后提交的优先处理"才是栈（如递归、撤销）。看"先来先服务"还是"后来先服务"。
链表不能折半查找——单链表无随机存取，只能顺序查找 O(n)；折半查找要求顺序存储 + 有序（见 3.3 章）。
顺序表插入删除 O(n)——不是 O(1)；O(1) 的是随机存取（按下标访问）。链表反之：插入删除 O(1)（已知位置）、查找 O(n)。
循环队列：判空 front==rear、判满 (rear+1)%maxsize==front——两个条件别混（牺牲一格空间是常用做法）。

五、横向扩展（防漏网：本章边界内、真题尚未考但可能补考的点）

说明：横向扩展覆盖"大纲范围内但 9 年真题未考过"的知识，标注【新增概率】供取舍。

栈的表达式求值（中缀→后缀、后缀求值）【高】：运算符优先级 + 栈实现；经典场景题（"表达式 a+bc 的后缀形式"= abc+）。金管局考过"流程/逻辑"题（2021 单40），表达式求值是高概率补考点。
括号匹配用栈【高】：遇到左括号入栈、右括号出栈匹配——"栈的典型应用"选择题常客。
循环队列判空判满公式【中】：(rear+1)%maxsize==front 判满——计算题可能考。
双向链表 / 循环链表【低】：循环链表尾节点指向头节点；双向链表可双向遍历——概念判断题可能涉及。
双端队列（deque）【低】：两端都可插入删除——"既能当栈又能当队列"。
优先队列（堆）【中】：按优先级出队（堆实现），不是严格 FIFO——与 3.2 章堆衔接，操作系统"优先调度"场景常出现（见 2.2 进程调度）。
串的模式匹配（朴素/KMP）【低】：KMP 时间复杂度 O(n+m)——名词辨析题可能只考"KMP 是串匹配算法"。
顺序表 vs 链表适用场景【中】："频繁插入删除选链表、频繁查找选顺序表"——场景判断题。

六、真题演练（代表性真题 + 解析）

例 1（2019 单38） 以下数据结构中，哪一个是线性结构？（口径已核） A. 广义表　B. 二叉树　C. 稀疏矩阵　D. 串

答案：D。串（字符串）是线性结构——字符一对一顺序排列。广义表（元素可为子表）、二叉树（一对多）、稀疏矩阵（二维）均为非线性。口诀：线性结构=线性表、栈、队列、串、一维数组。

例 2（2022 单24） 下列关于队列的叙述中正确的是（口径已核）。 A. 在队列中只能插入数据　B. 在队列中只能删除数据 C. 队列是先进先出的线性表　D. 队列是先进后出的线性表

答案：C。队列在队尾插入、队首删除，操作特性先进先出（FIFO）。A/B 片面（插入删除都有）；D 是栈的特性。口诀：队列先进先出、栈后进先出。

例 3（2025 单21） 为了解决银行柜面终端与票据打印机之间速度不匹配的问题，需要设置一个打印缓冲区。逐条、依次将柜面终端的打印需求传递至打印机。该缓冲区的结构应该选择（口径已核）。 A. 栈　B. 队列　C. 二叉树　D. 图

答案：B。打印需求逐条依次传递、先来先打印——先进先出 → 队列。栈是后进先出（若"后提交的先打印"才选栈）；二叉树/图是树形/网状结构，不适合线性缓冲。场景题口诀：先来先服务→队列。

例 4（2025 单49） 在一个具有 N 个节点的单链表中查找关键字为 K 的节点时，查找成功的情况下，需平均比较（口径已核）次。 A. N　B. N/2　C. (N+1)/2　D. (N−1)/2

答案：C。单链表不能随机存取，只能从首节点顺序比较。查找成功时，第 i 个位置比较 i 次，平均 (1+2+…+N)/N = (N+1)/2。口诀：链表顺序找，平均 (N+1)/2。

例 5（2019 多84） 关于栈与队列，下面错误的说法是（口径已核）。 A. 栈底元素一定是最后入栈的元素　B. 栈操作遵循后进先出原则 C. 栈底元素一定是最先入栈的元素　D. 栈与队列操作特性相同

答案：AD。A 错误——栈底元素最先入栈（最后才能出栈）；B 正确（后进先出）；C 正确；D 错误——栈后进先出、队列先进先出，特性不同。题干问"错误的说法"，故选 AD。口诀：栈底最先入、栈与队列特性不同。

七、本章小结

一条主线：逻辑结构分类（线性：一对一 vs 非线性：树/图/广义表）→ 线性表两种存法（顺序表随机存取、链表动态插入）→ 栈（后进先出，栈底最先入栈）→ 队列（先进先出，队尾入队首出队）→ 串（线性！）。
必背判定：串是线性结构；广义表/二叉树/稀疏矩阵/多维数组是非线性；栈底元素最先入栈；栈与队列操作特性不同。
必背计算：单链表查找成功平均比较 (N+1)/2 次；顺序表随机存取 O(1)、插入删除 O(n)。
必背场景：打印缓冲区/进程调度/叫号 → 队列；函数调用/递归/括号匹配/撤销/后退 → 栈。
衔接预告：队列→2.2 操作系统（就绪队列、消息队列）；栈→2.4 程序设计（递归、调用栈）；树/图→3.2 章；查找排序→3.3 章；复杂度→3.4 章。