408选择题数据结构

第一章 绪论 - 1.1 数据结构的基本概念

第1题：可以用( )定义一个完整的数据结构。 A. 数据元素 B. 数据对象 C. 数据关系 D. 抽象数据类型

【一】题目考察什么知识点 本题考察数据结构的核心定义，特别是“抽象数据类型（ADT）”的概念模型。

【二】解题思路分析（不要直接给答案） 一个完整的数据结构不仅仅包含数据本身，还必须包含这些数据之间的关系，以及可以在这些数据上执行的操作。我们需要在选项中寻找一个能够**同时囊括“数据对象”、“数据关系”和“基本操作”**的综合性概念。

【三】逐步推导过程

  1. 数据元素和数据对象只是数据的集合，没有体现数据之间的结构（关系）和操作，所以A、B都不完整。
  2. 数据关系只是定义了元素之间的逻辑联系，依然缺失了“操作”这一块。
  3. 抽象数据类型（ADT）的完整定义是一个三元组：ADT = (D, S, P)，其中 D 是数据对象，S 是 D 上的关系集，P 是对 D 的基本操作集。因此它能完整地定义一个数据结构。

【四】正确答案 D

【五】错误选项为什么错 A、B、C 都是构成数据结构的“零部件”，单拿出来任何一个都不足以描述整体（盲人摸象）。

【六】本题属于哪类题型 纯概念辨析题（送分题）。

【七】如何举一反三 记住口诀：“数据结构三要素 = 逻辑结构 + 存储结构 + 数据运算”。而在理论设计层面，“抽象数据类型（ADT）”就是这三要素的完美数学模型。以后看到“完整定义数据结构”，直接找 ADT。

第2题：以下数据结构中，( )是非线性数据结构。 A. 树 B. 字符串 C. 队列 D. 栈

【一】题目考察什么知识点 考察对数据逻辑结构的分类（线性结构 vs 非线性结构）。

【二】解题思路分析 线性结构的核心特征是“一对一”，也就是排成一条线，除了头尾，每个元素只有一个前驱和一个后继。非线性结构则是“一对多”或“多对多”。我们只需要看选项中哪个存在分叉或网状连接。

【三】逐步推导过程

  • 字符串：字符排成一排，一对一，是线性结构。
  • 队列和栈：虽然操作受限，但本质上依然是元素排成一排，是线性结构。
  • 树：一个父节点可以有多个子节点，典型的“一对多”关系，属于非线性结构。

【四】正确答案 A

【五】错误选项为什么错 B、C、D 在逻辑上都是严格的一条线（一对一），没有出现层次或网状的复杂关联。

【六】本题属于哪类题型 逻辑结构分类题。

【七】如何举一反三 408常考的数据结构分类要刻在DNA里：

  • 线性结构：线性表、栈、队列、字符串、数组（一维）。
  • 非线性结构：集合（平起平坐）、树（一对多）、图（多对多）。

第3题：以下属于逻辑结构的是( ) A. 顺序表 B. 哈希表 C. 有序表 D. 单链表

【一】题目考察什么知识点 这是408第一章最高频的易错点：死磕区分“逻辑结构”和“存储结构（物理结构）”。

【二】解题思路分析 判别技巧：“逻辑结构”只存在于大脑中，跟计算机底层的内存分配完全无关。如果在它的名字里，你能看出它是怎么在内存里放的（比如连续放、用指针连起来、算哈希地址），那它就是存储结构。如果名字只代表一种抽象的排列特征，那就是逻辑结构。

【三】逐步推导过程

  • A. 顺序表：强调“顺序连续存储”，暴露了内存排布，属于存储结构。
  • B. 哈希表：强调“根据函数算地址”，暴露了内存查找方式，属于存储结构。
  • D. 单链表：强调“用指针链式存储”，暴露了内存连接方式，属于存储结构。
  • C. 有序表：只强调“数据元素是按大小排好序的”，至于它是用顺序表存，还是用单链表存，你根本不知道。因此它是抽象的，属于逻辑结构。

【四】正确答案 C

【五】错误选项为什么错 A、B、D 都有具体的计算机内存实现方案，属于存储结构（或称物理结构）。

【六】本题属于哪类题型 逻辑/存储结构辨析题（易错陷阱）。

【七】如何举一反三 凡是带了“顺序、链式、哈希/散列、索引”这几个字眼的，100%是存储结构！比如：循环队列（逻辑）、循环链表（存储）；栈（逻辑）、顺序栈（存储）。

第4题：以下关于数据结构的说法中，正确的是( ) A. 数据的逻辑结构独立于其存储结构 B. 数据的存储结构独立于其逻辑结构 C. 数据的逻辑结构唯一决定其存储结构 D. 数据结构仅由其逻辑结构和存储结构决定

【一】题目考察什么知识点 考察数据结构三要素（逻辑结构、存储结构、数据运算）之间的辩证关系。

【二】解题思路分析 这题在考“谁决定谁，谁独立于谁”。我们要理清概念：逻辑结构是我们构思出来的，不依赖于计算机；而存储结构是逻辑结构在计算机里的落地实现，必须依附于逻辑结构。

【三】逐步推导过程

  • A项：逻辑结构是数学模型，你设计一个“树”的概念时，根本不需要考虑电脑怎么存它，所以逻辑结构独立于存储结构。正确。
  • B项：存储结构是为了在内存中实现逻辑结构而存在的，比如你不可能在不知道逻辑关系的前提下凭空建一个存储结构，所以存储结构不独立于逻辑结构。错误。
  • C项：一种逻辑结构可以有多种存储结构（比如线性表可以用顺序存，也可以用链式存），并不唯一。错误。
  • D项：数据结构还包括“数据运算”（三要素缺一不可），所以“仅由”表述错误。

【四】正确答案 A

【五】错误选项为什么错 见逐步推导过程。核心错因是弄反了抽象与具象的依附关系，以及漏掉了“数据运算”这个要素。

【六】本题属于哪类题型 综合概念辨析题。

【七】如何举一反三 用造房子类比：

  • 逻辑结构 = 图纸（独立存在，不管用什么砖都能画）。
  • 存储结构 = 用红砖还是用水泥（必须根据图纸来建，不独立；且同一个图纸可以用不同的材料，不唯一）。
  • 数据结构 = 完整的建筑（图纸 + 实体材料 + 水电运作）。

第5题：在存储数据时，通常不仅要存储各数据元素的值，而且要存储( ) A. 数据的操作方法 B. 数据元素的类型 C. 数据元素之间的关系 D. 数据的存取方法

【一】题目考察什么知识点 考察存储结构（物理结构）的本质内涵。

【二】解题思路分析 存储结构要把逻辑结构“搬进”内存。逻辑结构里有两样东西：数据本身，以及数据之间的关系（比如谁是谁的前驱，谁是谁的父节点）。所以在内存里，你也得把这两样东西都存下来，否则以后读出来就是一盘散沙。

【三】逐步推导过程 计算机内存是一维线性的。要把复杂的（比如树形的、网状的）数据放进去，光存值是不够的。比如树，存了节点 A 和节点 B，你必须再用某种方式（如指针、数组下标）把“A是B的父节点”这个关系存下来。因此必须存储“数据元素之间的关系”。操作方法和存取方法属于算法层面，通常体现在代码指令中，而不是直接存储在数据元素的结构里。

【四】正确答案 C

【五】错误选项为什么错 A和D是代码（函数/方法）干的事，不需要跟着数据一块分配内存单元。B项的类型信息在静态编译型语言中是由编译器管理的，虽然面向对象里有类型指针，但从数据结构最基础的定义来看，核心任务是保存“关系”。

【六】本题属于哪类题型 存储结构概念题。

【七】如何举一反三 在顺序存储中，关系是靠“物理位置的相邻”来隐式存储的；在链式存储中，关系是靠“指针”来显式存储的。无论哪种方式，目的都是为了保存“关系”！

第一章 绪论 - 1.2 算法和算法评价 (Part 1: 基础篇)

第1题：一个算法应该具有( )等重要特性。 A. 可维护性、可读性和可行性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和可靠性 D. 可读性、正确性和可行性

【一】题目考察什么知识点 考察算法的五个基本特性定义。

【二】解题思路分析（不要直接给答案） 计算机科学中对“算法”的定义是有严格规定的，有五大铁律缺一不可：有穷性、确定性、可行性、输入、输出。我们要在这个范围里找。

【三】逐步推导过程

  • A项中，“可维护性、可读性”是我们在软件工程中追求的“好算法/好代码”的标准，但不是算法本身的定义。即使一段代码写得像天书（毫无可读性），只要它能执行出结果，它依然是个算法。
  • C项中，“可靠性”不是算法的定义术语。
  • D项中，“可读性、正确性”同样属于对“好算法”的评估标准，而不是定义特征（哪怕一个算法算出的结果是错的，它本身依然是个算法，只不过是错误的算法）。
  • B项完美踩中了三大铁律：可行性、确定性、有穷性。

【四】正确答案 B

【五】错误选项为什么错 混淆了“算法的定义”和“好算法的标准”。

【六】本题属于哪类题型 纯概念记忆题（送分题）。

【七】如何举一反三 408选择题非常喜欢把这俩概念混在一起考。牢记：

  • 算法5特性（定性标准）：有穷、确定、可行、输入、输出。
  • 好算法4特质（评价标准）：正确、可读、健壮、高效率与低存储量。

第2题：下列关于算法的说法中，正确的是( ) A. 算法的时间效率取决于算法执行所花的CPU时间 B. 在算法设计中不允许用牺牲空间效率的方式来换取好的时间效率 C. 算法必须具备有穷性、确定性等五个特性 D. 通常用时间效率和空间效率来衡量算法的优劣

【一】题目考察什么知识点 考察算法效率的度量以及算法基本特性的综合理解。

【二】解题思路分析 逐个分析选项，辨析时间/空间复杂度的本质，以及算法定义的铁律。

【三】逐步推导过程

  • A项：算法的时间复杂度是指算法执行“基本运算语句”的次数（指令条数）与问题规模的关系，属于一种事前渐进分析。而“所花的CPU时间”属于事后统计，它受计算机硬件、编译器、当时系统负载影响极大，不能用来客观评价算法本身。
  • B项：在实际工程和考研题中，我们极其喜欢用“空间换时间”（比如哈希表、各类的辅助数组），这是绝对允许的策略。
  • C项：非常严谨，算法必须具备有穷性、确定性、可行性、输入和输出五个特性。
  • D项：衡量算法优劣的标准不仅仅是时间和空间，还必须包括正确性、可读性、健壮性。仅仅靠时空效率去衡量是不全面的。相对而言，C项是无懈可击的真理。

【四】正确答案 C

【五】错误选项为什么错 见逐步推导过程。最容易错选的是D，D败在不够全面严谨。

【六】本题属于哪类题型 概念综合辨析题。

第3题：某算法的时间复杂度为 O(n2)，表明该算法的( ) A. 问题规模是 n2 B. 执行时间等于 n2 C. 执行时间与 n2 成正比 D. 问题规模与 n2 成正比

【一】题目考察什么知识点 考察大O渐进时间复杂度的数学含义。

【二】解题思路分析 O(f(n)) 的严谨数学定义是：存在正常数 C 和 n0​，当 n≥n0​ 时，算法的执行时间 T(n)≤C⋅f(n)。我们提取它的本质：在大规模数据下，执行时间和 f(n) 是处于同一量级的。

【三】逐步推导过程 时间复杂度 O(n2) 说明算法的执行时间 T(n) 随着问题规模 n 的增大，其增长率与 n2 的增长率相同。忽略掉低阶项和常数系数后，即意味着执行时间与 n2 呈正比例关系。

【四】正确答案 C

【五】错误选项为什么错

  • A和D混淆了“问题规模”（n）和“执行时间”（T(n)）的关系。n 就是问题规模本身，不用与 n2 成正比。
  • B错在“等于”。大O表示的是“渐进上界”（成正比），它忽略了常数系数和低阶项（比如真实的执行次数可能是 3n2+5n+2），绝不能用等于来描述。

【六】本题属于哪类题型 时间复杂度概念理解题。

第4题：若某算法的空间复杂度为 O(1)，则表示该算法() A. 不需要任何辅助空间 B. 所需辅助空间大小与问题规模无关 C. 不需要任何空间 D. 所需空间大小与问题规模无关

【一】题目考察什么知识点 考察“原地工作”（In-place）及空间复杂度的概念。

【二】解题思路分析 空间复杂度到底看的是什么空间？是所有内存吗？不是，只看辅助空间（即为了实现算法而额外申请的空间，不包括输入数据本身占用的空间）。

【三】逐步推导过程 算法运行所需的总空间 = 程序代码空间 + 输入数据占用的空间 + 额外申请的辅助变量空间。 空间复杂度只评估辅助变量空间随问题规模 n 的变化趋势。如果辅助空间是一个常数（比如仅仅申请了几个用于循环控制的变量 i, j，或者一个交换变量 temp），无论处理 10个元素还是 10万个元素，这部分空间都不变，这就叫作与问题规模无关，记为 O(1)。

【四】正确答案 B

【五】错误选项为什么错

  • A和C非常极端：任何程序的运行都不可避免地需要栈空间、局部变量等，不可能“不需要任何空间”。
  • D错在“所需空间大小”。所需空间大小包含了输入数据本身的大小，如果你要对长度为 n 的数组排序，输入数据本身就占了 O(n)，它显然与规模有关。必须精确到“辅助空间”。

【六】本题属于哪类题型 空间复杂度概念辨析题（极其容易掉陷阱）。

【七】如何举一反三 遇到“原地工作”、“就地排序”等词汇，立刻条件反射：辅助空间复杂度为 O(1)。

第5题：下列关于时间复杂度的函数中，时间复杂度最小的是( ) A. T1​(n)=nlog2​n+5000n B. T2​(n)=n2−8000n C. T3​(n)=nlog2​n−6000n D. T4​(n)=20000log2​n

【一】题目考察什么知识点 考察不同渐进时间复杂度函数的增长率量级比较。

【二】解题思路分析 比较复杂度大小的秘诀：先去低阶项，再扔掉常数系数，最后比最高阶。

【三】逐步推导过程

  • A：去低阶项 5000n，最高阶为 nlog2​n，量级为 O(nlog2​n)。
  • B：去低阶项 8000n，最高阶为 n2，量级为 O(n2)。
  • C：同A，量级为 O(nlog2​n)。
  • D：扔掉系数 20000，最高阶就是 log2​n，量级为 O(log2​n)。 根据经典不等式：O(1)<O(log2​n)<O(n)<O(nlog2​n)<O(n2)<O(n3)<O(2n)，显然D的时间复杂度最小。

【四】正确答案 D

【五】错误选项为什么错 很多初学者会被D选项前面巨大的常数“20000”吓到。要记住，在渐进分析（大O表示法）中，当 n 趋近于无穷大时，任何对数阶 logn 的增长速度都会远远慢于线性阶 n 及其乘积，常数系数在无穷大面前毫无意义。

【六】本题属于哪类题型 复杂度量级比较题。

第6题：以下算法的时间复杂度为( )

C

1
2
3
4
5
void fun (int n) {
    int i=1;
    while (i<=n)
        i=i*2;
}

A. O(n) B. O(n2) C. O(nlog2​n) D. O(log2​n)

【一】题目考察什么知识点 考察最基础的单层循环时间复杂度计算（步长倍增型）。

【二】解题思路分析 找最深层循环的“基本语句”（这里是 i = i * 2），设其总共执行了 t 次。我们需要推导出 i 与 t 的数学函数关系，然后利用循环结束条件解出 t。

【三】逐步推导过程

  1. 初始时刻：i=1。
  2. 第 1 次执行：i=1×2=21。
  3. 第 2 次执行：i=2×2=22。
  4. 第 t 次执行：i=2t。
  5. 循环结束的边界条件是 i>n，即 2t>n。
  6. 两边取对数解得：t>log2​n。 因此，基本语句的执行次数 t 与 log2​n 处于同一量级。

【四】正确答案 D

【五】错误选项为什么错 如果只看 while (i<=n) 这个条件，非常容易凭直觉选 A O(n)。但决定循环次数的不仅是终点 n，还有你走向终点的步伐大小。步伐每次翻倍，所以是呈指数级狂奔向终点，花费的时间就是对数阶。

【七】如何举一反三 套路总结：凡是循环变量 i 每次乘以（或除以）一个常数 k(k>1)，时间复杂度必定是 O(logk​n)。 （底数通常忽略，统称对数阶）。

第7题：有以下算法，其时间复杂度为()

C

1
2
3
4
5
void fun (int n) {
    int i=0;
    while (i*i*i<=n)
        i++; // 原卷印刷有误写为i=i++; 这里按正常i++解析
}

A. O(n) B. O(nlog2​n) C. O(3n![](data:image/svg+xml;utf8,)​) D. O(n![](data:image/svg+xml;utf8,)​)

【一】题目考察什么知识点 考察非常规结束条件的单层循环复杂度计算。

【二】解题思路分析 套用上一题的方法：设基本语句执行了 t 次，找 i 和 t 的关系，再带入循环结束条件。

【三】逐步推导过程

  1. 初始时刻：i=0。
  2. 基本运算：i++。说明步伐是每次加1的匀速运动。
  3. 假设执行了 t 次后，i=t。
  4. 循环继续的条件是：i×i×i≤n。
  5. 把 i=t 代入条件：t3≤n。
  6. 解得：t≤3n![](data:image/svg+xml;utf8,)​。即最高执行次数为 n1/3 级别。

【四】正确答案 C

【五】错误选项为什么错 见推导过程。只要老老实实写出关于 t 的方程，就不会做错。

第8题：程序段如下，其中n为正整数，则最后一行语句的频度在最坏情况下是( )

C

1
2
3
4
for (i=n-1; i>1; i--)
    for (j=1; j<i; j++)
        if (A[j]>A[j+1])
            A[j] 与 A[j+1] 对换;

A. O(n) B. O(nlog2​n) C. O(n3) D. O(n2)

【一】题目考察什么知识点 考察双重循环（其实就是冒泡排序的思想）的语句频度计算。

【二】解题思路分析 题目问的是“最坏情况”。最坏情况就是 if 条件每次都成立，每次都执行对换语句。此时对换语句的执行次数就完全等于内层循环体的进入次数。我们需要把内外层循环的次数用求和公式累加起来。

【三】逐步推导过程

  1. 外层循环：i 从 n-1 递减到 2（因为条件是 i>1，并且 i 是整数）。
  2. 内层循环：j 从 1 递增到 i-1（因为条件是 j<i）。所以在特定的外层 i 下，内层循环会执行 i−1 次。
  3. 将所有情况累加求和： S=∑i=2n−1​(i−1)=(2−1)+(3−1)+⋯+(n−1−1) S=1+2+⋯+(n−2)=2(n−2)(n−1)​
  4. 将求和结果展开，其最高阶项为 21​n2，忽略常数系数后，渐进时间复杂度为 O(n2)。

【四】正确答案 D

【五】错误选项为什么错 不要看到双层嵌套 for 循环就凭感觉猜 O(n2)，一定要像这样写出 Sigma (Σ) 求和公式。如果内层循环是 j*=2，那就是 O(nlogn) 了。

第9题：下列程序段的时间复杂度为( )

C

1
2
3
4
5
6
7
8
if (n>=0) {
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            printf("输入数据大于或等于零\n");
} else {
    for(int j=0; j<n; j++)
        printf("输入数据小于零\n");
}

A. O(n2) B. O(n) C. O(1) D. O(nlog2​n)

【一】题目考察什么知识点 考察分支结构（if-else）下的最坏时间复杂度评估。

【二】解题思路分析 在计算时间复杂度时，如果存在分支结构，按照算法分析的原则，我们应当采用**“悲观原则”**（即最坏情况分析），取所有分支中复杂度最高的那一个作为整个算法的复杂度。

【三】逐步推导过程

  1. 如果走 if (n>=0) 分支，里面是一个双重循环，外层跑 n 次，内层跑 n 次，频度为 n×n=n2，复杂度为 O(n2)。
  2. 如果走 else 分支，里面只有一个单层循环，跑 n 次，复杂度为 O(n)。
  3. 根据大O表示法的最坏情况分析原则，取最大值：max(O(n2),O(n))=O(n2)。

【四】正确答案 A

【七】如何举一反三 如果有并列的代码块（比如一段代码先跑 O(n) 的循环，接着跑一个 O(n2) 的循环），总复杂度遵循**“加法法则”**：O(f(n))+O(g(n))=O(max(f(n),g(n)))。谁阶数高听谁的。

第10题：以下算法中加下画线的语句的执行次数为( )

C

1
2
3
4
int m=0,i,j;
for (i=1; i<=n; i++)
    for (j=1; j<=2*i; j++)
        m++; // 加下画线语句

A. n(n+1) B. n C. n+1 D. n2

【一】题目考察什么知识点 考察双重循环嵌套时的绝对频度精确计算（注意：这题问的是精确的“执行次数”，而不是用大O表示的复杂度）。

【二】解题思路分析 绝对不能用 O(n2) 来糊弄，必须老老实实写 Sigma (Σ) 求和公式。

【三】逐步推导过程

  1. 外层循环 i 从 1 取到 n。
  2. 对于给定的 i，内层循环 j 从 1 取到 2*i。因此内层循环的执行次数是 2i。
  3. 将所有外层循环下的内层执行次数累加： S=∑i=1n​(2i)=2×∑i=1n​i 利用等差数列求和公式：S=2×2n(n+1)​ 化简得：S=n(n+1)

【四】正确答案 A

【五】错误选项为什么错 D选项 n2 虽然在数量级上是正确的（大O表示法确实是 O(n2)），但此题问的是具体的频度表达式，缺少了低阶项，因此不能选D。

第一章 绪论 - 1.2 算法和算法评价 (Part 2: 进阶篇)

第11题：下列函数代码的时间复杂度是( )

C

1
2
3
4
int Func(int n) {
    if (n==1) return 1;
    else return 2*Func(n/2)+n;
}

A. O(n) B. O(nlog2​n) C. O(log2​n) D. O(n2)

【一】题目考察什么知识点 考察递归算法的时间复杂度分析，以及代码阅读时的“视觉陷阱”。

【二】如何通俗理解（生活化类比） 想象你要切一个大蛋糕（问题规模 n）。代码里的 Func(n/2) 就代表你把蛋糕切了一半，然后只拿其中一半去继续切。至于前面的 2* 和后面的 +n，那只是你在切完这一半之后，顺手把结果翻个倍、再加点点缀（常数级别的基本运算）。因为你每次都只处理一半的蛋糕，所以切的次数就是 log2​n。

【三】解题思路分析（不要直接给答案） 很多同学看到 2*Func(n/2) 会下意识地联想到归并排序的复杂度递推式 T(n)=2T(n/2)+O(n)，从而错选 B。但请仔细看代码！2* 是一个乘法运算符，它表示把 Func(n/2) 的返回值乘以 2，而不是调用了两次 Func 函数！

【四】逐步推导过程

  1. 递归方程的建立：设 Func(n) 的执行时间为 T(n)。
  2. 代码中只有一个递归调用 Func(n/2)，执行这个调用需要 T(n/2) 的时间。
  3. 除此之外，判断 if、乘法 2*、加法 +n 都是基本运算，时间为 O(1)。
  4. 因此真正的递归时间复杂度方程是：T(n)=T(n/2)+O(1)。
  5. 根据主定理或展开法解这个方程：T(n)=T(n/2)+O(1)=T(n/4)+2O(1)=⋯=T(1)+log2​n⋅O(1)，最终复杂度为 O(log2​n)。

【五】正确答案 C

【六】错误选项为什么错 错选 B 的同学是中了命题人的障眼法，把“返回值乘2”看成了“执行了2次递归”。如果代码写成 Func(n/2) + Func(n/2) + n，那复杂度才是 O(n)。

【七】本题属于哪类题型 递归复杂度计算的“坑题”。

【八】如何举一反三 做递归分析题时，千万不要看系数，要看函数调用的个数！ 比如 return 100 * Func(n/2); 依然只调用了 1 次，复杂度是 O(log2​n)。

第12题：【2011统考真题】设 n 是描述问题规模的非负整数，下面的程序片段的时间复杂度是( )

C

1
2
3
x=2;
while (x<n/2)
    x=2*x;

A. O(log2​n) B. O(n) C. O(nlog2​n) D. O(n2)

【一】题目考察什么知识点 考察单层循环（步长倍增型）的渐进时间复杂度计算。

【二】如何通俗理解（生活化类比） 你要跑一场距离为 n/2 的马拉松。但你的速度不是匀速的，而是“跨步跳”：第1步跨2米，第2步跨4米，第3步跨8米……因为步子按指数级翻倍，所以你到达终点所需的步数会被大幅压缩，是“对数”级别的。

【三】解题思路分析 依然是找最深层循环的基本语句 x = 2 * x，设其执行次数为 t。推导出 x 随 t 变化的表达式，代入循环结束条件求解。

【四】逐步推导过程

  1. 初始时刻：x=2。
  2. 第 1 次循环：x=2×2=22。
  3. 第 2 次循环：x=22×2=23。
  4. 第 t 次循环：x=2t+1。
  5. 循环继续的条件是 x<n/2，即 2t+1<n/2。
  6. 两边取对数得到 t+1<log2​(n/2)=log2​n−1。
  7. 解得 t<log2​n−2。忽略常数项后，渐进复杂度为 O(log2​n)。

【五】正确答案 A

【六】错误选项为什么错 B 错在误以为终点是 n/2，复杂度就是线性的。记住：决定时间的是步长，每次乘 2 必定是对数阶。

【七】本题属于哪类题型 基础循环复杂度分析（408真题）。

第13题：【2012统考真题】求整数 n(n≥0) 的阶乘的算法如下，其时间复杂度是( )

C

1
2
3
4
int fact (int n) {
    if (n<=1) return 1;
    return n*fact(n-1);
}

A. O(log2​n) B. O(n) C. O(nlog2​n) D. O(n2)

【一】题目考察什么知识点 考察单分支递归算法的时间复杂度分析。

【二】如何通俗理解（生活化类比） 这就像俄罗斯套娃。你要打开一个有 n 层的套娃，每次只能剥开最外面的一层（n−1），剥开一层花 1 秒钟。剥到最里面那一层总共需要剥 n 次，所以时间就是 O(n)。

【三】解题思路分析 找到递归式，分析问题规模 n 每次递归缩小的幅度。

【四】逐步推导过程

  1. 设计算 n 的阶乘耗时为 T(n)。
  2. 每次递归调用 fact(n-1)，问题规模减 1。
  3. 递归方程：T(n)=T(n−1)+O(1)（这里的 O(1) 是判断和乘法操作）。
  4. 展开：T(n)=T(n−1)+1=T(n−2)+1+1=⋯=T(1)+(n−1)×1。
  5. 显然共执行了 n 次，时间复杂度为 O(n)。

【五】正确答案 B

【六】错误选项为什么错 不要看到递归就觉得是 O(log2​n)！递归每次规模是“折半（除以2）”还是“减1”，决定了它是对数阶还是线性阶。这里是减1，所以是线性阶。

第14题：【2014统考真题】下列程序段的时间复杂度是( )

C

1
2
3
4
count=0;
for (k=1; k<=n; k*=2)
    for (j=1; j<=n; j++)
        count++;

A. O(log2​n) B. O(n) C. O(nlog2​n) D. O(n2)

【一】题目考察什么知识点 考察双重循环嵌套的时间复杂度计算（外层倍增，内层线性）。

【二】如何通俗理解（生活化类比） 你要在一个体育场跑圈。外层循环是“教练吹哨”，教练吹哨的时间间隔是翻倍的（1秒、2秒、4秒…），所以教练总共只会吹 log2​n 次哨。内层循环是你自己跑步，教练每吹一次哨，你就雷打不动地跑满 n 圈。最终你跑的总圈数 = 教练吹哨次数 × n 圈。

【三】解题思路分析 内外层循环变量不相互依赖（j 的范围与 k 无关），所以可以直接把内外层循环的复杂度相乘。

【四】逐步推导过程

  1. 分析外层循环：k 的初始值为1，每次执行 k *= 2，直到 k > n 结束。设外层循环执行了 t 次，则 2t≤n⇒t=⌊log2​n⌋。即外层循环跑了 O(log2​n) 次。
  2. 分析内层循环：对于外层循环的每一步，内层变量 j 都从 1 老老实实遍历到 n，步长为1。因此内层循环固定跑 n 次。
  3. 总执行次数 = 外层次数 × 内层次数 = log2​n×n。
  4. 时间复杂度为 O(nlog2​n)。

【五】正确答案 C

【六】本题属于哪类题型 独立嵌套双重循环的复杂度计算。

第15题：下列函数的时间复杂度是( )

C

1
2
3
4
int i=0, sum=0;
while(sum<n)
    sum += ++i;
return i;

A. O(log2​n) B. O(n![](data:image/svg+xml;utf8,)​) C. O(n) D. O(nlog2​n)

【一】题目考察什么知识点 考察基于等差数列求和的循环结束条件的复杂度推导。

【二】如何通俗理解（生活化类比） 你要往一个容积为 n 的水缸里加水。第1次加1勺，第2次加2勺，第3次加3勺……这叫加速加水。因为你越加越快，所以加满水缸所需的次数，绝对不是 n 次，而是比 n 小得多。数学告诉我们，这种等差数列的累加，其增长速度是平方级别的，反推回去，次数就是开根号。

【三】解题思路分析 关键在于分析变量 sum 的值随执行次数变化的规律。

【四】逐步推导过程

  1. 设循环执行了 t 次。
  2. 每次循环，i 的值依次变为 1, 2, 3, …, t。
  3. sum 的值是 i 的累加和：sum=1+2+3+⋯+t=2t(t+1)​。
  4. 循环结束的边界条件是 sum≥n。
  5. 此时 2t(t+1)​≥n，即 t2+t≥2n。
  6. 解这个不等式，得出最高阶项 t≈2n![](data:image/svg+xml;utf8,)​。
  7. 忽略常数系数后，时间复杂度为 O(n![](data:image/svg+xml;utf8,)​)。

【五】正确答案 B

【六】如何举一反三 记住这个极其经典的结论：只要循环体内是对循环变量进行等差累加（如 sum = sum + i 且 i++），其时间复杂度必然是根号阶 O(n![](data:image/svg+xml;utf8,)​)。

第16题：【2019统考真题】设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是( )

C

1
2
3
x=0;
while (n>=(x+1)*(x+1))
    x=x+1;

A. O(log2​n) B. O(n![](data:image/svg+xml;utf8,)​) C. O(n) D. O(n2)

【一】题目考察什么知识点 考察不等式约束下的时间复杂度计算。

【二】解题思路分析 这道题属于“送分题”，命题人已经把不等式写在脸上了。我们只需要直接根据条件解方程即可。

【三】逐步推导过程

  1. 基本操作是 x = x + 1，也就是说每次循环 x 匀速增加 1。
  2. 设循环执行了 t 次，因为 x 初始为 0，所以执行 t 次后，x=t。
  3. 循环继续的条件是 (x+1)2≤n。
  4. 将 x=t 代入：(t+1)2≤n。
  5. 两边同时开平方：t+1≤n![](data:image/svg+xml;utf8,)​。
  6. 整理得 t≤n![](data:image/svg+xml;utf8,)​−1。
  7. 取大O渐进表示法，得时间复杂度为 O(n![](data:image/svg+xml;utf8,)​)。

【四】正确答案 B

第17题：【2022统考真题】下列程序段的时间复杂度是()

C

1
2
3
4
int sum=0;
for(int i=1; i<n; i*=2)
    for(int j=0; j<i; j++)
        sum++;

A. O(log2​n) B. O(n) C. O(nlog2​n) D. O(n2)

【一】题目考察什么知识点 考察内外层循环变量相互依赖时的语句频度求和（等比数列求和）。

【二】如何通俗理解（生活化类比） 这是一场特殊的接力赛。第一天你要跑1圈，第二天跑2圈，第三天跑4圈……直到有一天你要跑的数量接近 n 圈时比赛结束。看起来你跑了很多天（log2​n 天），但实际上，根据数学规律，你之前所有天数跑的圈数总和，都不如最后一天跑得多！ 你最后一天跑了大约 n 圈，总圈数大约是 2n 圈。所以总工作量其实是 O(n)。

【三】解题思路分析 绝对不能简单地把外层 O(log2​n) 和内层 O(n) 相乘，因为内层的运行次数 j < i 是依赖于 i 的当前值的。必须写出 Σ（Sigma）求和公式。

【四】逐步推导过程

  1. 外层循环：i 的取值依次为 1,2,4,8,…,2k。设外层一共跑了 m 次，则最后的 i=2m<n。
  2. 内层循环：对于特定的 i，内层循环会执行 i 次（执行 sum++）。
  3. 总执行次数 S 是所有内层循环次数的累加： S=1+2+4+8+⋯+2m
  4. 这是一个首项为1、公比为2的等比数列求和： S=1−21×(1−2m+1)​=2m+1−1
  5. 因为 2m≈n，所以 2m+1=2×2m≈2n。
  6. 代入得 S≈2n−1。
  7. 取大O表示法，时间复杂度为 O(n)。

【五】正确答案 B

【六】错误选项为什么错 极其容易错选 C！如果你不仔细看内层条件，把 j < i 当成了 j < n，那才是 O(nlog2​n)。核心陷阱就在这里：内外层变量是否关联。

第2章 线性表 - 2.1 线性表的定义和基本操作

第1题：线性表是具有n个()的有限序列。 A. 数据表 B. 字符 C. 数据元素 D. 数据项

【一】题目考察什么知识点 考察线性表的严格基本定义。

【二】如何通俗理解（生活化类比） 线性表就像是一列正在排队买票的队伍。队伍里的每一个人就是一个完整的“数据元素”。而这个人的衣服颜色、身高（数据项）只是他的属性。队伍是由“人”组成的，而不是由“衣服颜色”组成的。

【三】解题思路分析 只要认准408官方教材中的那句原话：“线性表是具有相同数据类型的n个数据元素的有限序列”。

【四】逐步推导过程 线性表作为一种逻辑结构，其构成的基本单位必须是“数据元素”。数据项是数据元素的不可分割的最小单位，而数据表通常指数据库中的表，字符只是数据元素的一种具体类型（不够一般化）。

【五】正确答案 C

【六】错误选项为什么错 B错在太狭隘，线性表里也可以存整数、存结构体。D错在层级不对，数据项是构成数据元素的内部成分。

【七】本题属于哪类题型 纯概念记忆题。

第2题：下列几种描述中,()是一个线性表。 A. 由n个实数组成的集合 B. 由100个字符组成的序列 C. 所有整数组成的序列 D. 邻接表

【一】题目考察什么知识点 考察线性表的两个核心特征：“有限”和“序列（有序性）”。

【二】解题思路分析 对照线性表的定义：一要有顺序（不是一盘散沙），二要长度有限（不能无穷无尽）。

【三】逐步推导过程

  • A项：集合是无序的（集合的三大特性：无序性、互异性、确定性），而线性表必须有先后顺序。
  • C项：整数有无数个，违反了线性表的“有限”原则。
  • D项：邻接表是图的一种存储结构，本质上是数组和链表的结合，属于存储结构的具体实现，不能直接拿来等同于逻辑概念“线性表”。
  • B项：100个（有限）字符组成的序列（有先后顺序），完美符合定义。

【四】正确答案 B

【五】错误选项为什么错 见逐步推导过程。408极其爱在“集合”、“序列”、“有限”这几个词上挖坑。

【六】本题属于哪类题型 逻辑结构辨析题。

第3题：在线性表中,除开始元素外,每个元素() A. 只有唯一的前驱元素 B. 只有唯一的后继元素 C. 有多个前驱元素 D. 有多个后继元素

【一】题目考察什么知识点 考察线性结构的逻辑拓扑特征（一对一关系）。

【二】解题思路分析 线性表就是一条线，像一条珠串。除了两头的珠子比较特殊，中间的珠子前后都只连着一颗珠子。

【三】逐步推导过程 题目特别限定了“除开始元素外”。开始元素没有前驱，有唯一后继。那么剩下的所有元素（不管是不是尾元素），它们肯定都“排在某个元素后面”，所以必然只有唯一的前驱元素。 （注意：尾元素没有后继，所以不能说除开始元素外每个元素都有唯一后继）。

【四】正确答案 A

【五】错误选项为什么错 B项错在没有排除尾元素（尾元素没有后继）。C和D是树形结构（一对多）或图状结构（多对多）的特征。

【七】如何举一反三 如果题目问：“在线性表中，除表尾元素外，每个元素……”，答案就是“只有唯一的后继元素”。

第4题：若非空线性表中的元素既没有直接前驱,又没有直接后继,则该表中有( )个元素。 A. 1 B. 2 C. 3 D. n

【一】题目考察什么知识点 考察线性表的边界情况（单节点线性表）。

【二】解题思路分析 没有直接前驱，说明它是头节点；没有直接后继，说明它也是尾节点。一个人既是排头又是排尾，说明队伍里有几个人？

【三】逐步推导过程 在线性表中，只有第一个元素无前驱，最后一个元素无后继。如果某个元素兼具这两个特征，说明表头就是表尾，整个表只有一个元素。

【四】正确答案 A

第2章 线性表 - 2.2 线性表的顺序表示 (顺序表)

第1题：下列叙述中,( )是顺序存储结构的优点。 A. 存储密度大 B. 插入运算方便 C. 删除运算方便 D. 方便地运用于各种逻辑结构的存储表示

【一】题目考察什么知识点 考察顺序表（数组）和链表在宏观上的优缺点对比。

【二】如何通俗理解（生活化类比）

  • 顺序存储（数组）：就像高铁上的连座，座位挨在一起，不浪费一点空间（存储密度大），找人很方便。但是如果想在中间加塞一个人，后面的人全得往后挪（插入/删除麻烦）。
  • 链式存储（链表）：就像大家手里拿着指引下一位同志在哪里的纸条，散落在广场各处。加塞人很容易（改下纸条就行），但每人都得多拿一张纸条，浪费了空间（存储密度小）。

【三】逐步推导过程

  • 顺序存储结构在物理内存中是连续分配的，不需要额外存储指针等结构关系信息，因此数据本身占用的空间 / 分配的总空间 = 1，存储密度极大。
  • 插入和删除需要移动大量元素，是它的缺点。
  • 树和图这种复杂的逻辑结构，如果硬用顺序存储会产生大量空节点（比如极度不平衡的二叉树），并不方便。

【四】正确答案 A

第2题：下列关于顺序表的叙述中,正确的是( ) A. 顺序表可以利用一维数组表示,因此顺序表与一维数组在逻辑结构上是相同的 B. 在顺序表中,逻辑上相邻的元素物理位置上不一定相邻 C. 顺序表和一维数组一样,都可以进行随机存取 D. 在顺序表中,每个元素的类型不必相同

【一】题目考察什么知识点 顺序表的核心特征：连续内存与随机存取。

【二】逐步推导过程

  • A项：顺序表是线性表的一种“存储结构”，而一维数组属于编程语言层面的数据类型。概念层次不同。
  • B项：错。顺序表的绝对铁律就是：逻辑上相邻，物理上也必须绝对相邻。
  • C项：正确。因为物理地址连续且元素大小相同，只要知道头地址，就能用公式 Loc(i) = Loc(1) + (i-1)*sizeof(ElemType) 直接算出任何一个元素的地址，这叫随机存取。
  • D项：错。顺序表中的元素数据类型必须完全相同（否则算不出首地址的偏移量）。

【四】正确答案 C

第3题：线性表的顺序存储结构是一种() A. 随机存取的存储结构 B. 顺序存取的存储结构 C. 索引存取的存储结构 D. 散列存取的存储结构

【一】题目考察什么知识点 考察存取方式的分类（极易混淆名词）。

【二】解题思路分析 不要被“顺序存储”里的“顺序”两个字骗了！顺序表在内存中是顺序放的，但在拿数据的时候，是“指哪打哪”的随机存取。

【四】正确答案 A

【六】错误选项为什么错 B是链表的特征（找第i个必须从头顺藤摸瓜）。

【七】如何举一反三 记住这个反差：“顺序表是随机存取，单链表是顺序存取”。408极其喜欢拿这个文字游戏考人。

第4题：通常说顺序表具有随机存取的特性,指的是( ) A. 查找值为x的元素的时间与顺序表中元素个数无关 B. 查找值为x的元素的时间与顺序表中元素个数有关 C. 查找序号为i的元素的时间与顺序表中元素个数无关 D. 查找序号为i的元素的时间与顺序表中元素个数有关

【一】题目考察什么知识点 考察“随机存取”的真正含义。

【二】解题思路分析 随机存取（Random Access）是指读取（获取）内存中指定位置（序号）的数据，耗时是常数 O(1)。

【三】逐步推导过程

  • A和B说的是“按值查找”。按值查找你需要从头到尾遍历比对，平均要找 n/2 次，显然与元素个数（n）有关。
  • C和D说的是“按序号存取”。得益于连续存储和固定大小，找第i个元素的地址计算公式是恒定的运算，只需 O(1) 的时间。因此与总元素个数无关。

【四】正确答案 C

第5题：一个顺序表所占用的存储空间大小与()无关。 A. 表的长度 B. 元素的存放顺序 C. 元素的类型 D. 元素中各字段的类型

【一】题目考察什么知识点 顺序表空间的计算公式。

【三】逐步推导过程 顺序表总空间 = 表长(n) × 单个元素占用的空间(sizeof(ElemType))。

  • A决定了 n。
  • C和D决定了单个元素占用的空间。
  • 至于这n个元素是怎么排列的（比如从小到大排，还是乱序排），完全不影响总大小。

【四】正确答案 B

第6题：若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值,为了提高效率,应采用()的存储方式。 A. 单链表 B. 双向链表 C. 循环单链表 D. 顺序表

【一】题目考察什么知识点 结构选型：根据高频操作选择合适的数据结构。

【三】逐步推导过程 题目说最常用的操作是“存取第i个元素”。注意“存取”不仅是找，还要精准定位。

  • 顺序表可以通过下标直接 A[i-1], A[i-2], A[i] 拿到本身及其前驱后继，全部都是 O(1) 操作！效率无敌。
  • 链表类结构，找第i个元素全都需要从头遍历，时间复杂度 O(n)。

【四】正确答案 D

第7题：一个线性表最常用的操作是存取任意一个指定序号的元素并在最后进行插入、删除操作,则利用()存储方式可以节省时间。 A. 顺序表 B. 双链表 C. 带头结点的循环双链表 D. 循环单链表

【一】题目考察什么知识点 综合结构选型：结合“按位存取”和“尾部操作”。

【三】逐步推导过程

  • “存取任意指定序号元素”：顺序表 O(1)，各类链表都是 O(n)。这里顺序表已经拿下了决定性优势。
  • “在最后进行插入、删除”：顺序表在尾部（长度范围允许内）插入和删除，不需要移动任何元素，时间复杂度也是 O(1)。 两项叠加，顺序表完胜。

【四】正确答案 A

第8题：在n个元素的线性表的数组表示中,时间复杂度为O(1)的操作是( ) I. 访问第i个结点和求第i个结点的直接前驱 II. 在最后一个结点后插入一个新的结点 III. 删除第1个结点 IV. 在第i个结点后插入一个结点 A. I B. II、III C. I、II D. I、II、III

【一】题目考察什么知识点 顺序表各项基本操作的时间复杂度。

【二】解题思路分析 逐个评估每个操作在顺序表（数组）中需要挪动多少元素。

【三】逐步推导过程

  • I：访问靠下标直接取值，O(1)。正确。
  • II：在尾部插入，如果没有满，直接 A[length++] = new_val，不移动任何元素，O(1)。正确。
  • III：删除第1个，后面 n-1 个元素全部都要往前挪一位，O(n)。错误。
  • IV：在中间插入，平均要挪动一半的元素，O(n)。错误。

【四】正确答案 C (对应选项中的 I、II)

第9题：设线性表有n个元素,严格说来,以下操作中,()在顺序表上实现要比在链表上实现的效率高。 I. 输出第i个元素值 II. 交换第3个元素与第4个元素的值 III. 顺序输出这n个元素的值 A. I B. I、III C. I、II D. II、III

【一】题目考察什么知识点 顺序表与链表的底层微观效率对比。

【三】逐步推导过程

  • I：输出第i个元素。顺序表 O(1) 直接拿到；链表 O(n) 遍历才能拿到。顺序表高！
  • II：交换第3和第4个元素。顺序表 swap(A[2], A[3])，完全直接地址定位，毫无多余废动作。单链表你要从头走2步走到节点3，再修改值或指针，指针的跳转在底层指令里是要多花时间的。严格来说顺序表依然更高！
  • III：顺序输出全表。两者都要从头到尾走一遍，时间复杂度都是 O(n)。但顺序表因为内存连续，有CPU Cache极大的加持（空间局部性极好），实际上确实比链表快。但从考研理论复杂度层面，这俩都是O(n)，被认为是一样的。 （这题的408命题逻辑中，通常倾向于把 O(1) 和 O(n) 的区别作为“效率高”的判定标准。由于前两个明显是 O(1) vs O(n)（链表找第3个严格来说也是要走的，只不过常数较小），所以选 I 和 II）。

【四】正确答案 C (对应 I、II)

第10题：在一个长度为n的顺序表中删除第i(1≤i≤n)个元素时,需向前移动()个元素。 A. n B. i-1 C. n-i D. n-i+1

【一】题目考察什么知识点 顺序表删除操作的具体推导公式。

【二】解题思路分析 不要死记硬背！直接用代入法（特例法）秒杀。

【三】逐步推导过程 假设数组总长 n=5。 你要删除最后 1 个元素（即 i=5）。你不需要移动任何元素，移动次数为 0。 把 n=5,i=5 代入选项： A: 5 B: 4 C: 5-5 = 0 <– 命中！ D: 5-5+1 = 1 唯一符合逻辑的就是 C。

【四】正确答案 C

【七】如何举一反三 遇到所有“算移动次数”、“算比较次数”的带字母公式题，一律用 n=3 或 n=5 的具体特例带进去验证。这是防脑子短路的最好方法。

第11题：对于顺序表,访问第i个位置的元素和在第i个位置插入一个元素的时间复杂度为( ) A. O(n),O(n) B. O(n),O(1) C. O(1),O(n) D. O(1),O(1)

【一】题目考察什么知识点 顺序表基本操作的大O表示法。

【三】逐步推导过程

  • 访问第i个位置：数组下标直接寻址 A[i-1]，一步到位，O(1)。
  • 在第i个位置插入：不仅要找到位置，还需要把原来第i个及以后的所有元素全部往后挪一位腾出坑来。平均挪动 n/2 次，复杂度 O(n)。

【四】正确答案 C

第12题：对于顺序存储的线性表,其算法时间复杂度为O(1)的运算应该是( ) A. 将n个元素从小到大排序 B. 删除第i个元素 C. 改变第i个元素的值 D. 在第i个元素后插入一个新元素

【一】题目考察什么知识点 基础复杂度分析。

【三】逐步推导过程

  • A项排序最快也要 O(n log n)。
  • B和D因为涉及到后续元素的牵连移动，平均复杂度都是 O(n)。
  • C项：改变第i个元素的值，即 A[i-1] = new_value，典型的随机存取写操作，O(1) 搞定。

【四】正确答案 C

第13题：若长度为n的非空线性表采用顺序存储结构,在表的第i个位置插入一个数据元素,则i的合法值应该是() A. 1≤i<n B. 1≤i≤n+1 C. 1≤i≤n-1 D. 0≤i<n

【一】题目考察什么知识点 顺序表插入操作的边界条件判定（408代码题最容易扣分的地方）。

【二】解题思路分析 题目说的是“第 i 个位置”，这指的是我们日常语境中的逻辑位序（从1开始数），而不是C语言的数组下标（从0开始数）。

【三】逐步推导过程 表里现在有 n 个元素。

  • 你可以插在最前面，变成新的第1个，所以 i 最小是 1。
  • 你也可以插在最后面，也就是第 n 个元素的屁股后面。插进去之后，它就变成了第 n+1 个元素。所以 i 最大可以是 n+1。 因此插入的合法范围是 1≤i≤n+1。

【四】正确答案 B

【七】如何举一反三 对比记忆：

  • 插入的合法范围：1≤i≤n+1。（因为可以在尾巴后面加一个）。
  • 删除的合法范围：1≤i≤n。（只能删已有的，不能删第 n+1 个不存在的）。

第14题：顺序表的插入算法中,当几个空间已满时,可再申请增加分配m个空间,若申请失败,则说明系统没有( )可分配的存储空间。 A. m个 B. m个连续 C. n+m个 D. n+m个连续

【一】题目考察什么知识点 顺序表（动态数组）扩容的底层原理（malloc / realloc 的机制）。

【二】解题思路分析 C语言中实现动态顺序表的扩容，本质上是申请一块全新且更大的连续内存，然后把老数据搬过去，释放老内存。

【三】逐步推导过程 顺序表最大的规矩就是“连续”。原来有 n 个空间满了，你想扩容到 n+m 个空间。系统绝不是在原来的内存后面硬给你接上 m 个连续块（因为原来内存的后面可能已经被别的程序占用了）。 系统的做法是：在庞大的内存大海中，寻找一块能够一口气容纳 n+m 个元素的连续空地。如果失败了，说明系统连一块长达 n+m 的连续空间都找不出了（尽管零碎的内存加起来可能远超这个数）。

【四】正确答案 D

第15题：【2023统考真题】在下列对顺序存储的有序表(长度为n)实现给定操作的算法中,平均时间复杂度为O(1)的是( ) A. 查找包含指定值元素的算法 B. 插入包含指定值元素的算法 C. 删除第i(1≤i≤n)个元素的算法 D. 获取第i(1≤i≤n)个元素的算法

【一】题目考察什么知识点 综合考察顺序表（注意题干加了“有序表”的定语）的时间复杂度。这是离我们最近的统考真题之一。

【二】解题思路分析 仔细审题，题目说的是“顺序存储的有序表”。

【三】逐步推导过程

  • A项：有序表的按值查找可以采用二分查找（折半查找），复杂度为 O(log n)。如果选顺序查找是 O(n)。不管怎样都不可能是 O(1)。
  • B项：要在有序表中插入元素，为了保持有序，你必须先找位置，再移元素。移动大量元素决定了它是 O(n)。
  • C项：按位置删除，同样需要移动后面的元素来填补空缺，O(n)。
  • D项：获取第 i 个元素，直接通过数组下标存取，完全不需要管它是不是有序的，一步到位，O(1)！

【四】正确答案 D

【六】本题属于哪类题型 概念与复杂度综合判断（属于典型的408“白给分”题，只要别粗心看错字）。

第2章 线性表 - 2.3 线性表的链式表示 (Part 1)

第1题：下列关于线性表的存储结构的描述中,正确的是( ) I. 线性表的顺序存储结构优于其链式存储结构 II. 链式存储结构比顺序存储结构能更方便地表示各种逻辑结构 III.若频繁使用插入和删除结点操作,则顺序存储结构更优于链式存储结构 IV.顺序存储结构和链式存储结构都可以进行顺序存取 A. I、II、III B. II、IV C. II、III D. III、IV

【一】题目考察什么知识点 考察顺序表与链表的宏观特性对比。

【二】解题思路分析 逐个判断表述的正确性。注意不存在“谁绝对优于谁”的说法，只有“谁在什么场景下更合适”。

【三】逐步推导过程

  • I：错。没有绝对的优劣，只看应用场景。
  • II：对。链式存储的指针可以非常灵活地指向任何地方，不仅能表示线性的单链表，还能方便地表示树（左孩子右兄弟）、图（邻接表）等各种复杂的逻辑结构。顺序存储由于内存物理连续的限制，表示复杂结构会有很多局限。
  • III：错。频繁插入和删除时，顺序表需要移动大量元素 O(n)，而链表只要修改指针 O(1)（假设已经找到了位置），所以应该是链式存储更优。
  • IV：对。顺序存取就是“从头到尾按顺序挨个访问”。顺序表可以用下标 0, 1, 2... 挨个访问，链表可以用 p=p->next 挨个访问，它们都能做到。

【四】正确答案 B

【五】错误选项为什么错 错选的同学大多是对 IV 有疑问。注意区分“顺序存取”和“随机存取”。顺序表既能顺序存取，也能随机存取；而链表只能顺序存取。

第2题：对于一个线性表,既要求能够进行较快速地插入和删除,又要求存储结构能反映数据之间的逻辑关系,则应该用() A. 顺序存储方式 B. 链式存储方式 C. 散列存储方式 D. 以上均可以

【一】题目考察什么知识点 考察存储结构选型。

【三】逐步推导过程

  • “较快速地插入和删除”：直接排除了顺序表，指向链式存储或散列表。
  • “能反映数据之间的逻辑关系”：散列（哈希）存储是把数据根据哈希函数散列到不同地址，元素之间完全是一盘散沙，丢失了原本的逻辑先后关系。而链式存储通过指针完美保留了前驱后继的逻辑关系。

【四】正确答案 B

第3题：链式存储设计时,结点内的存储单元地址() A. 一定连续 B. 一定不连续 C. 不一定连续 D. 部分连续,部分不连续

【一】题目考察什么知识点 考察链表结点的底层物理结构本质。

【二】如何通俗理解（生活化类比） 链表的各个结点就像是分布在不同城市的快递驿站，它们之间的物理位置是不连续的。但是，在一个驿站内部（一个结点内），“包裹（数据区）”和“下一站地址单（指针区）”必须是装在一个屋子里的。

【三】逐步推导过程 虽然链表的各个结点之间在内存中是随机分配、不连续的。但对于同一个结点内部（如C语言中的一个 struct Node { int data; struct Node *next; }），一旦被 malloc 分配出来，它内部的 data 和 next 在内存物理地址上是绝对连续的。否则系统怎么可能把它们当成一个整体去读取呢？

【四】正确答案 A

【五】易错点总结 极其容易看错题！看清楚题目问的是**“结点之间”还是“结点内”**。

第4题：下列关于线性表说法中,正确的是( ) I.顺序存储方式只能用于存储线性结构 II. 在一个设有头指针和尾指针的单链表中,删除表尾元素的时间复杂度与表长无关 III.带头结点的循环单链表中不存在空指针 IV.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n) V.若用单链表来表示队列,则应该选用带尾指针的循环链表 A. I. II B. I、III、IV、V C. IV、V D. III、IV、V

【一】题目考察什么知识点 链表的各类变形及其操作时间复杂度综合。

【三】逐步推导过程

  • I：错。顺序存储也能存非线性结构，比如完全二叉树完全可以放进一个一维数组里。
  • II：错。单链表删除尾结点，必须找到尾结点的前驱（倒数第二个结点）才能修改它的 next 指针。哪怕你有尾指针，因为是“单”链表不能往回指，你依然得从头开始顺藤摸瓜找 n−1 步，复杂度是 O(n)。
  • III：对。循环单链表的最后一个结点的指针指向头结点，永远是一个闭环，没有任何一个结点的 next 为 NULL。
  • IV：对。即使是有序单链表，也无法用二分查找。你必须从头遍历寻找插入位置，平均要找 n/2 次，时间复杂度 O(n)。
  • V：对。队列需要在表头删（出队），在表尾插（入队）。如果用带尾指针的循环单链表，找尾结点是 O(1)，找头结点（即尾指针的下一个）也是 O(1)，极其高效！

【四】正确答案 D (包含 III、IV、V)

第5题：设线性表中有2n个元素,()在单链表上实现要比在顺序表上实现效率更高。 A. 删除所有值为x的元素 B. 在最后一个元素的后面插入一个新元素 C. 顺序输出前k个元素 D. 交换第i个元素和第 2n−i−1 个元素的值

【一】题目考察什么知识点 顺序表和单链表的微观操作效率对比。

【三】逐步推导过程

  • A项：单链表删除所有值为 x 的元素，只需遍历一遍，遇到就跨过，时间复杂度 O(n)，不需要大量移动。而顺序表如果删掉中间的 x，后续元素全得往前挪，如果有多个 x，可能就是 O(n2)（如果优化算法也能做到 O(n)，但在没有额外空间的情况下常数时间极大）。总体来说链表更高效。
  • B项：在末尾插入，顺序表是 O(1)，单链表要走到尾巴是 O(n)。顺序表更优。
  • C项：顺序输出前k个，大家都要走一遍，效率差不多。
  • D项：按位置交换，顺序表 O(1) 瞬间定位；单链表还得跑遍历，极慢。

【四】正确答案 A

第6题：在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入结点s,则执行() A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p C. q->next=s; s->next=p; D. p->next=s; s->next=q;

【一】题目考察什么知识点 单链表中间位置的标准插入代码。

【二】解题思路分析 现在的状态是 q -> p。我们想把它变成 q -> s -> p。 画图！把指针连线断开重连。

【三】逐步推导过程

  1. s 的 next 必须要指向 p，即 s->next = p;。
  2. q 的 next 必须要指向 s，即 q->next = s;。 这两个动作的顺序在有明确的前驱和后继指针的情况下都可以，只要完成了这两步就行。看选项，C 完美符合。

【四】正确答案 C

第7题：给定有n个元素的一维数组,建立一个有序单链表的最低时间复杂度是( ) A. O(1) B. O(n) C. O(n2) D. O(nlog2​n)

【一】题目考察什么知识点 将数组转化为有序链表的时间复杂度（底层实为排序算法）。

【二】解题思路分析 题目说的是一个“普通的”一维数组（意味着无序），要建立一个“有序”的单链表。这本质上就是一个排序过程！

【三】逐步推导过程 不管你是先把数组排好序再建链表，还是每次取一个元素在链表中找位置插入（直接插入排序 O(n2)），你绕不开的核心是排序。目前基于比较的最快的排序算法（如快速排序、归并排序）时间复杂度下限就是 O(nlog2​n)。所以建有序链表的最低代价就是 O(nlog2​n)。

【四】正确答案 D

第8题：将长度为n的单链表链接在长度为m的单链表后面,其算法的时间复杂度采用大O形式表示应该是() A. O(1) B. O(n) C. O(m) D. O(n+m)

【一】题目考察什么知识点 单链表尾部拼接操作的时间复杂度。

【二】解题思路分析 把链表 B 拼到链表 A 后面，你需要做的是：找到链表 A 的尾巴，然后把 A 尾巴的 next 指向链表 B 的头。

【三】逐步推导过程 链表 A 长度为 m，链表 B 长度为 n。

  1. 为了找到链表 A 的尾巴，你必须从 A 的头指针开始，顺藤摸瓜走 m 步，耗时 O(m)。
  2. 找到尾巴后，执行一句赋值操作 A_tail->next = B_head;，耗时 O(1)。
  3. 后面的 B 根本不需要去遍历，直接接上就完事了。 总耗时只与前一个链表的长度 m 有关。

【四】正确答案 C

第9题：单链表中,增加一个头结点的目的是( ) A. 使单链表至少有一个结点 B. 标识表结点中首结点的位置 C. 方便运算的实现 D. 说明单链表是线性表的链式存储

【一】题目考察什么知识点 “头结点”引入的意义（408大题手写代码时的关键）。

【二】如何通俗理解 想象你在穿一串珍珠项链。如果在第一个珍珠前面没有一个固定的“金属卡扣”（头结点），那你想拿掉第一颗珍珠，或者在最前面新加一颗珍珠，你的线头（头指针）就得改来改去，非常麻烦。有了这个不存实际数据的金属卡扣，不管怎么删改，线头永远捏在卡扣上，代码逻辑就统一了。

【三】逐步推导过程 引入头结点的根本原因有两点：

  1. 统一插入和删除操作：在第一个位置插入或删除时，不需要专门写 if(p == head) 的特殊判断分支，所有位置的操作逻辑全部一致。
  2. 统一空表和非空表：带头结点时，无论表空表非空，头指针始终指向这个实体头结点，处理起来更方便。 综上所述，目的就是为了“方便运算的实现”。

【四】正确答案 C

第10题：在一个长度为n的带头结点的单链表h上,设有尾指针,则执行()操作与链表的表长有关。 A. 删除单链表中的第一个元素 B. 删除单链表中的最后一个元素 C. 在单链表第一个元素前插入一个新元素 D. 在单链表最后一个元素后插入一个新元素

【一】题目考察什么知识点 单链表（含尾指针）在头尾两端操作的时间复杂度。

【二】解题思路分析 “与表长有关”的同义词就是：时间复杂度为 O(n)（需要遍历）。如果能在 O(1) 时间内干完，就是与表长无关。

【三】逐步推导过程

  • A项：删第一个元素，直接 head->next = head->next->next，瞬间完成，O(1)。
  • C项：插在第一个前面（也就是头结点之后），同样只需修改头结点指针，O(1)。
  • D项：在最后一个元素后面插，因为有尾指针 rear，直接 rear->next = new_node; rear = new_node;，O(1)。
  • B项：删除最后一个元素！这是最致命的陷阱！你虽然知道尾巴在哪，但单链表无法回头，你拿不到尾巴前面的那个结点！所以你只能老老实实从头开始遍历，走 n−1 步找到倒数第二个结点，把它变成新的尾巴。耗时 O(n)，与表长有关！

【四】正确答案 B

【七】如何举一反三 切记：单向链表的尾部删除操作永远是 O(n)（除非是双向链表），哪怕给你一万个尾指针都没用！

第2章 线性表 - 2.3 线性表的链式表示 (Part 2)

第11题：对于一个头指针为head的带头结点的单链表,判定该表为空表的条件是()；对于不带头结点的单链表,判定空表的条件为( ) A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL (注：本题为两空填空题，对应选项为 B 和 A)

【一】题目考察什么知识点 考察“带头结点”与“不带头结点”单链表的本质区别及判空条件。

【二】如何通俗理解（生活化类比）

  • 带头结点的链表就像一列火车有个专门的“车头”（哪怕没拉货，车头这个壳子永远在）。如果车头后面一节货厢都没有，那就是空车（head->next == NULL）。
  • 不带头结点的链表就像你直接去车间提“第一节货厢”。如果没有货厢，那就是啥都没有，彻彻底底的一场空（head == NULL）。

【三】解题思路分析 区分 head（头指针）是指向真正的第一个数据结点，还是指向一个“傀儡”头结点。

【四】逐步推导过程

  1. 带头结点的单链表：初始化时就已经 malloc 了一个头结点，head 永远指向这个头结点（所以 head 不可能为 NULL）。如果表为空，说明头结点后面没有挂接任何实际数据结点，因此判定条件是 head->next == NULL。第一空选 B。
  2. 不带头结点的单链表：head 直接指向真正的第一个数据结点。如果表为空，连第一个结点都不存在，head 自然是指向空，判定条件是 head == NULL。第二空选 A。

【五】正确答案 第一空：B；第二空：A

【六】如何举一反三 408代码大题中，99%都是要求使用“带头结点的单链表”，因为这样能把所有结点的插入/删除操作逻辑统一起来，不用专门写 if (head == NULL) 的特判代码。

第12题：在线性表中 a0​,a1​,⋅⋅⋅,a100​,删除元素 a50​ 需要移动()个元素。 A. 0 B. 50 C. 51 D. 0或50

【一】题目考察什么知识点 考察对“线性表”这个宏观逻辑概念与底层存储结构关系的理解。

【二】如何通俗理解（生活化类比） 题目只说“线性表”（大家排成一队），但没说大家是“肩并肩坐连排椅”（顺序表）还是“松散地手拉手”（链表）。 如果是坐连排椅，中间走了一个人，后面所有人必须整体往前挪；如果是手拉手，中间的人松手走人，前后两个人重新牵上手就行了，不需要大规模挪位置。

【三】解题思路分析 这是408极其爱玩的文字游戏。看到“线性表”三个字，脑子里必须同时浮现出“顺序表”和“链表”两种可能。

【四】逐步推导过程

  1. 若该线性表采用顺序存储（顺序表）：表中共有101个元素（下标从0到100）。删除了 a50​ 后，需要将其后的 a51​ 到 a100​ 这50个元素全部向前移动一位。移动次数为 50。
  2. 若该线性表采用链式存储（链表）：删除 a50​ 只需要修改 a49​ 的指针指向 a51​，然后释放 a50​ 的内存即可，移动元素的个数为 0。
  3. 综合来看，都有可能。

【五】正确答案 D

第13题：通过含有 n(n>1) 个元素的数组a,采用头插法建立单链表L,则L中的元素次序() A. 与数组的元素次序相同 B. 与数组的元素次序相反 C. 与数组a的元素次序无关 D. 以上都错误

【一】题目考察什么知识点 考察链表“头插法”建表的本质特性（逆序特性）。

【二】如何通俗理解（生活化类比） 头插法就像是“往枪膛里压子弹”或者“把书塞进拥挤的书包”。你按数组顺序拿来《语文》《数学》《英语》，用头插法放进去：先放《语文》，再把《数学》硬塞到最前面（压在语文上面），最后把《英语》硬塞到最前面。最后建好的链表（从头到尾看）顺序变成了《英语》《数学》《语文》——正好完全逆序了。

【三】逐步推导过程 头插法每次都将新结点插入到头结点之后（即当前链表实际第一个元素的最前面）。因此，数组中第1个被读取的元素最终会被挤到链表的最后面，而最后一个被读取的元素被插在表头。

【四】正确答案 B

【五】如何举一反三 记住结论：“头插法建表 = 逆序（可用于实现单链表逆置）；尾插法建表 = 顺序保持不变”。如果考研大题让你就地逆置一个单链表，最经典的解法就是把原链表拆了，用头插法重新插入回去！

第14题：下面关于线性表的一些说法中,正确的是() A. 对一个设有头指针和尾指针的单链表执行删除最后一个元素的操作与链表长度无关 B. 线性表中每个元素都有一个直接前驱和一个直接后继 C. 为了方便插入和删除数据,可以使用双链表存放数据 D. 取线性表第i个元素的时间与i的大小有关

【一】题目考察什么知识点 综合考察线性表各类存储结构（单链表、双链表、顺序表）的优缺点和操作代价。

【二】解题思路分析 逐个选项进行严格的逻辑“排雷”。

【三】逐步推导过程

  • A项：错。单链表是单行道！你要删除尾结点，必须修改倒数第二个结点的 next 指针为 NULL。虽然你有尾指针能瞬间找到最后一个结点，但你无法回头找到倒数第二个结点！只能从头指针开始遍历 n−1 步。因此耗时仍为 O(n)，与表长有关。
  • B项：错。表头元素没有前驱，表尾元素没有后继。
  • D项：错。题干只说了“线性表”，如果线性表是用一维数组（顺序表）实现的，取第 i 个元素靠下标直接访问 A[i]，时间复杂度是 O(1)，与 i 的大小毫无关系。
  • C项：对。在双向链表中，每个结点既有 next 也有 prior。如果我们已经有了一个结点的指针，要在它前面插入或删除它，因为能靠 prior O(1) 找到前驱，不用像单链表那样从头遍历找前驱，极大地方便了插入和删除。

【四】正确答案 C

第15题：在双链表中向p所指的结点之前插入一个结点q的操作为() A. p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior; B. p->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next; C. q->next=p; p->next=q; q->prior->next=q; q->next=p; D. p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q;

【一】题目考察什么知识点 408极其爱考的：双向链表结点插入的代码执行顺序铁律（防断链）。

【二】如何通俗理解（生活化类比） 你（p）和你前面的人（原 p->prior）手拉手站着。现在新来一个人（q）要插到你前面。 你的死穴是：千万不能先把你牵前面人的手（p->prior）弄断！ 因为一旦你把这只手直接去牵了新来的q（即先执行了 p->prior=q），你就彻底迷失了原先站在你前面的那个人是谁，q也就再也无法和原来的队伍连上了。

【三】逐步推导过程 插入 q 到 p 之前，一共要改 4 根线。

  • 第一步（自我武装）：先让 q 伸出手去牵两边。q->next = p; 以及 q->prior = p->prior;。此时 q 已经通过 p 找到了原来的前驱。
  • 第二步（切断原前驱的后继）：让原来的前驱结点不再牵 p，改去牵 q。即 p->prior->next = q;。（注意：必须在修改 p->prior 之前做这一步）。
  • 第三步（最后切断自己的前驱）：让 p 的前驱指向 q。即 p->prior = q;。 观察 D 选项： p->prior->next = q; （前驱牵q） q->next = p; （q牵p） q->prior = p->prior; （q牵前驱，这里稍微有点瑕疵，如果前一步 p->prior 没变，这步是对的。但等等，看选项D的原话！） 注意：仔细看选项 D 的顺序！ D: p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q; 在第1句 p->prior->next=q 后，p->prior 这个指针本身并没有被覆盖，它依然指向原来的前驱结点！所以第3句 q->prior=p->prior 依然能成功获取原前驱结点的地址！最后一句 p->prior=q 完成交接。完全合法！

【四】正确答案 D

【五】错误选项为什么错 A选项第一句就是致命的 p->prior=q，把寻址线索直接覆盖，后面再写 p->prior->next=q 就变成了让 q 自己指向自己，发生严重断链错误！

第16题：在双向链表存储结构中,删除p所指的结点时必须修改指针() A. p->prior->next = p->next; p->next->prior = p->prior; B. p->prior = p->prior->prior; p->prior->next = p; C. p->next->prior = p; p->next = p->next->next; D. p->next = p->prior->prior; p->prior = p->next->next;

【一】题目考察什么知识点 双向链表的结点删除操作。

【二】解题思路分析 要让 p 结点滚蛋，不需要修改 p 自己的指针，只需要让 p 的“前驱”和 p 的“后继”手牵手，直接跨过 p 即可。

【三】逐步推导过程

  1. 让 p 的前驱结点（p->prior）的后继指针（->next），越过 p，直接指向 p 的后继（p->next）。即：p->prior->next = p->next;
  2. 让 p 的后继结点（p->next）的前驱指针（->prior），越过 p，直接指向 p 的前驱（p->prior）。即：p->next->prior = p->prior; 这两句话修改的是 p 左右两个邻居内部的指针域，对 p 自己用来寻路的两根线没有任何破坏，所以这两句先后顺序颠倒也无所谓。完美匹配选项 A。

【四】正确答案 A

第17题：在如下图所示的双链表中,已知指针p指向结点A,若要在结点A和C之间插入指针q所指的结点B, 则依次执行的语句序列可以是() ... <-> A(p) <-> C <-> ... ① q->next=p->next; ② q->prior=p; ③ p->next=q; ④ p->next->prior=q; A. 1243 B. 4321 C. 3412 D. 1342

【一】题目考察什么知识点 “向后插入”时的双链表指针语句排序。

【二】解题思路分析 p 指向 A 结点。A 的原后继是 C（即 p->next 就是 C 结点）。我们想把 B(q) 插在 A(p) 后面。 死穴：一旦执行了 p->next = q（第③句），p 和 C 的联系就彻底切断了！所以所有需要依赖 p->next 来找到 C 结点的操作（比如①和④），都必须在第③句之前执行！

【三】逐步推导过程 我们验证 A 选项 (1-2-4-3)：

  1. q->next = p->next; （B 的 next 指向了 C。合法）
  2. q->prior = p; （B 的 prior 指向了 A。合法，此时 B 两只手牵好了）
  3. p->next->prior = q; （p->next 此时还是 C，所以这句相当于 C 的 prior 指向了 B。合法！）
  4. p->next = q; （最后安全地让 A 的 next 指向 B，大功告成）。 逻辑严丝合缝，不会断链。

【四】正确答案 A

【五】错误选项为什么错 拿 D 选项 (1-3-4-2) 开刀：它在第 2 步执行了第 ③ 句 p->next = q。这时候 p 已经抛弃了 C 去指向 B 了。接着第 3 步执行 ④ p->next->prior = q，这相当于 q->prior = q，让 B 结点去指自己了！而真正的 C 结点由于没被接上，就此迷失在内存的黑洞中，发生断链。

第18题：在双链表的两个结点之间插入一个新结点,需要修改()个指针域。 A. 1 B. 3 C. 4 D. 2

【一】题目考察什么知识点 双向链表插入操作的基础常识。

【二】解题思路分析 插入操作本质是把一根原有的“双黄线”剪断，并在中间连入一个新枢纽。

【三】逐步推导过程

  1. 新结点自己有左手（prior）和右手（next），伸向两边邻居 → 修改 2 个指针。
  2. 原来的左邻居要伸出右手（next）牵新结点，原来的右邻居要伸出左手（prior）牵新结点 → 又修改 2 个指针。 算上刚才分析的 4 条必不可少的赋值语句，总共需要修改 4 个指针域。

【四】正确答案 C

第19题：在长度为n的有序单链表中插入一个新结点,并仍然保持有序的时间复杂度是() A. O(1) B. O(n) C. O(n2) D. O(nlog2​n)

【一】题目考察什么知识点 单链表按值查找的时间复杂度。

【二】解题思路分析 这个动作分为两步：第一步找插入位置，第二步执行修改指针插入。

【三】逐步推导过程

  • 插入位置的寻找：因为是“单链表”，无论是否有序，它都不支持像数组那样的二分查找（折半查找），因为它无法在 O(1) 时间内找到中间结点。你只能像排查地雷一样，从头结点一个一个往后比对大小，平均要走 n/2 步。耗时 O(n)。
  • 插入操作：一旦找到位置，只需修改两根指针（s->next = p->next; p->next = s;），耗时 O(1)。 取大头，整体时间复杂度为 O(n)。

【四】正确答案 B

第20题：与单链表相比,双链表的优点之一是( ) A. 插入、删除操作更方便 B. 可以进行随机访问 C. 可以省略表头指针或表尾指针 D. 访问前后相邻结点更灵活

【一】题目考察什么知识点 双链表引入的核心意义。

【二】如何通俗理解（生活化类比） 单链表就像单行道，你走过了就不能回头；要是想找站在你前面的人，只能从队伍的最前面重新往后数一遍。而双链表是双向车道，你不仅知道谁跟在你后面，一回头还能知道谁在你前面，灵活性拉满。

【三】逐步推导过程

  • A项：双链表的插入和删除需要修改 4 根指针，代码更繁琐易错；单链表只要修改 2 根。虽然双链表找前驱快，但单纯评价“操作更方便”不严谨。
  • B项：只要是链表（非连续分配），就绝对不可能像数组那样靠下标 A[i] 瞬间随机访问。必须顺藤摸瓜。
  • C项：任何链表都必须有头指针才能作为一个数据结构被抓住，不能省略。
  • D项：双链表的结点包含 prior 和 next，既可以找后继（O(1)），也可以找前驱（O(1)），完全对应“访问前后相邻结点更灵活”。

【四】正确答案 D

第2章 线性表 - 2.3 线性表的链式表示 (Part 3: 循环与静态链表)

第21题：对于一个带头结点的循环单链表L,判断该表为空表的条件是( ) A. 头结点的指针域为空 B. L的值为NULL C. 头结点的指针域与L的值相等 D. 头结点的指针域与L的地址相等

【一】题目考察什么知识点 带头结点的循环单链表判空条件。

【二】解题思路分析 循环链表的精髓就是“咬尾巴”。最后一个结点的指针不再指向 NULL，而是指回表头结点。

【三】逐步推导过程 因为有头结点，L 永远不可能为 NULL。 当表为空时，也就是只有头结点一个光杆司令。按照循环的规矩，它的指针域（L->next）必须指回它自己（头结点的地址，也就是 L）。即 L->next == L。

【四】正确答案 C

第22题：对于一个带头结点的循环双链表L,判断该表为空表的条件是( ) A. L->prior==L && L->next==NULL B. L->prior==NULL && L->next==NULL C. L->prior==NULL && L->next==L D. L->prior==L && L->next==L

【一】题目考察什么知识点 带头结点的循环双链表判空条件。

【二】解题思路分析 循环双链表不仅往后“咬尾巴”，往前也“咬尾巴”。

【三】逐步推导过程 空表时，只有头结点 L。

  • L 的后继指回自己：L->next == L
  • L 的前驱也指回自己：L->prior == L 两者同时成立。并且循环链表中永远不可能出现 NULL 指针！

【四】正确答案 D

第23题：一个链表最常用的操作是在末尾插入结点和删除结点,则选用()最节省时间。 A. 带头结点的循环双链表 B. 循环单链表 C. 带尾指针的循环单链表 D. 单链表

【一】题目考察什么知识点 基于高频操作（尾部增删）的链表选型。

【二】解题思路分析 这题是个极高频的经典陷阱！很多人看到“末尾操作”就秒选带尾指针的单链表，这会直接掉坑。

【三】逐步推导过程

  • 末尾插入：只要有尾指针，单链表和双链表都能在 O(1) 搞定。

  • 末尾删除（致命点）：要删除尾结点，必须修改倒数第二个结点的指针！

    • 单链表（哪怕是循环单链表带尾指针），你只能从头遍历找到倒数第二个，耗时 O(n)。
    • 循环双链表：你可以通过头结点的 prior 瞬间找到尾结点，再通过尾结点的 prior 瞬间找到倒数第二个结点！全程 O(1)！极其丝滑。

【四】正确答案 A

【七】如何举一反三 牢记口诀：“凡是涉及到【尾部删除】的操作，单链表全家（含循环、含尾指针）一律 O(n) 被拉黑，必须上双链表！”

第24题：设对n(n>1)个元素的线性表的运算只有4种:删除第一个元素;删除最后一个元素;在第一个元素之前插入新元素;在最后一个元素之后插入新元素,则最好使用() A. 只有尾结点指针没有头结点指针的循环单链表 B. 只有尾结点指针没有头结点指针的非循环双链表 C. 只有头结点指针没有尾结点指针的循环双链表 D. 既有头结点指针又有尾结点指针的循环单链表

【一】题目考察什么知识点 两端频繁增删操作的极致数据结构选型。

【三】逐步推导过程 题目要求的其实就是双端队列的操作。 根据上题的结论，只要有**“删除最后一个元素”**，必须淘汰所有单链表（淘汰 A、D）。 剩下 B 和 C 都是双链表。

  • B 选项：非循环双链表只有尾指针。你能 O(1) 在尾部操作，但你找不到头在哪，怎么删除/插入第一个元素？不行。
  • C 选项：带头指针的循环双链表。头指针能瞬间找到第一个元素（O(1)）；因为是循环的，头指针的 prior 就是尾结点，也能瞬间找到最后一个元素及它的前驱（O(1)）。四种操作全O(1)！完美！

【四】正确答案 C

第25题：设有两个长度为n的循环单链表,若要求两个循环单链表的头尾相接的时间复杂度为O(1),则对应两个循环单链表各设置一个指针,分别指向() A. 各自的头结点 B. 各自的尾结点 C. 各自的首结点 D. 一个表的头结点,另一个表的尾结点

【一】题目考察什么知识点 循环单链表的拼接操作。

【二】解题思路分析 拼接要把表 A 的尾巴指向表 B 的头，把表 B 的尾巴指向表 A 的头。如果只有头指针，找尾巴得 O(n)。

【三】逐步推导过程 如果只有尾指针 rear：

  1. 表的头结点瞬间拿到：head = rear->next。
  2. 表的尾巴本来就捏在手里：rear。 头尾都能在 O(1) 时间内获取，拼接操作自然也就是两三句赋值代码的事，O(1) 搞定。 如果指向头结点，找尾结点只能死磕遍历。

【四】正确答案 B

第26题：设有一个长度为n的循环单链表,若从表中删除首元结点的时间复杂度达到O(n),则此时采用的循环单链表的结构可能是( ) A. 只有表头指针,没有头结点 B. 只有表尾指针,没有头结点 C. 只有表尾指针,带头结点 D. 只有表头指针,带头结点

【一】题目考察什么知识点 循环单链表结构微调对复杂度（牵一发而动全身）的影响。

【二】解题思路分析 正常的带头结点循环单链表删第一个数据（首元结点），只要 head->next = head->next->next 就完了，O(1)。为什么会变成 O(n)？

【三】逐步推导过程 结合选项分析，如果不带头结点，且只有表头指针（选项A）： 头指针直接指向了第一个实际数据结点。你要删除它，不仅头指针要后移，更致命的是——循环链表的尾巴是咬在这个结点上的！ 你把第一个结点删了，尾巴必须改咬新的第一个结点。 但是你只有头指针，你怎么找尾巴？只能顺藤摸瓜绕一整圈找到尾结点，把它指向新的头。因此耗时 O(n)。

【四】正确答案 A

第27题：某线性表用带头结点的循环单链表存储,头指针为head,当 head->next->next==head 成立时,线性表的长度可能是( ) A. 0 B. 1 C. 2 D. 可能为0或1

【一】题目考察什么知识点 循环单链表的边界情况推演（极易错）。

【三】逐步推导过程 让我们分别代入长度 0 和 1 进行测试：

  • 长度为 0 时（只有头结点）：head->next = head。代入表达式：head->next->next 就等于 head->next，又等于 head。式子成立！
  • 长度为 1 时（头结点 -> A -> 头结点）：head->next = A，且 A->next = head。代入表达式：head->next->next 就是 A->next，正好等于 head。式子也成立！
  • 长度为 2 时：head->next->next 指向的是第二个数据元素，绝不是 head。

【四】正确答案 D

第28题：有两个长度都为n的双链表,若以h1为头指针的双链表是非循环的,以h2为头指针的双链表是循环的,则下列叙述中正确的是( ) A. 对于双链表h1,删除首结点的时间复杂度是O(n) B. 对于双链表h2,删除首结点的时间复杂度是O(n) C. 对于双链表h1,删除尾结点的时间复杂度是O(1) D. 对于双链表h2,删除尾结点的时间复杂度是O(1)

【一】题目考察什么知识点 循环与非循环双向链表的尾部操作对比。

【三】逐步推导过程

  • 删除首结点：无论循不循环，有头指针都在 O(1) 解决。A、B错。

  • 删除尾结点：

    • h1（非循环）：从头指针出发，没有捷径，必须遍历到尾巴，O(n)。C错。
    • h2（循环）：由于循环，h2->prior 就是尾结点。瞬间找到尾结点及其前驱，执行删除操作，O(1)！D对。

【四】正确答案 D

第29题：一个链表最常用的操作是在最后一个元素后插入一个元素和删除第一个元素,则选用()最节省时间。 A. 不带头结点的循环单链表 B. 双链表 C. 单链表 D. 不带头结点且有尾指针的循环单链表

【一】题目考察什么知识点 特殊场景（头删、尾插，其实就是队列操作）的最佳链表选型。

【三】逐步推导过程

  • 需求1：尾部插入。如果有尾指针，瞬间完成。

  • 需求2：头部删除。如果有头指针，瞬间完成。

  • 结合选项 D 来看：带尾指针的循环单链表。

    • 尾插：new->next = rear->next; rear->next = new; rear = new; (O(1))
    • 头删：rear->next 就是首元结点（不带头结点的情况）。p = rear->next; rear->next = p->next; free(p); (O(1))
    • 两端全 O(1) 且单链表省去了 prior 指针的空间，极致高效！

【四】正确答案 D

第30题：需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构为( ) A. 单链表 B. 静态链表 C. 顺序表 D. 双链表

【一】题目考察什么知识点 静态链表的本质特征。

【二】如何通俗理解（生活化类比） 静态链表就像是一个有固定格子的药盒（底层是数组，需要分配较大的一整块连续空间），但是你不按格子的顺序吃药。每个格子里放了张纸条写着“下次吃第3格的药”。你想把某格的药扔掉，不需要把后面的药全挪格子，只要改一下纸条上的数字就行了。

【三】逐步推导过程

  • “分配较大空间”暗指它在物理内存上是连续分配的一大块（类似于数组，排除 A、D 纯指针链表）。
  • “插入删除不移动元素”暗指它逻辑上是用指针（游标下标）连起来的（排除 C 顺序表）。 兼具“底层数组”和“逻辑链表”双重特性的，就是静态链表。

【四】正确答案 B

第31题：下列关于静态链表的说法中,正确的是( ) I. 静态链表兼具顺序表和单链表的优点,因此存取表中第i个元素的时间与i无关 II. 静态链表能容纳的最大元素个数在表定义时就确定了,以后不能增加 III. 静态链表与动态链表在元素的插入、删除上类似,不需要移动元素 IV. 相比动态链表,静态链表可能浪费较多的存储空间 A. I、II、III B. II、III、IV C. I、III、IV D. I、II、IV

【一】题目考察什么知识点 考察静态链表的本质特征与时空代价。

【二】解题思路分析 静态链表就是“用数组来模拟链表”，数组的下标作为“游标（指针）”。

【三】逐步推导过程

  • I：错！静态链表虽然底层是数组，但它在逻辑上依然是“链表”，各个元素在物理上并不一定是按顺序紧挨着的。要找第 i 个元素，必须从头游标开始顺藤摸瓜找 i 次，时间复杂度是 O(n)，与 i 有关。
  • II：对。底层是静态数组，一旦声明 struct Node a[MaxSize]，容量就写死了，不能像 malloc 那样无限动态扩展。
  • III：对。插入和删除只需要修改对应下标里的“游标”值，不需要大面积移动数组元素。
  • IV：对。为了防止溢出，静态链表通常一开始就要开辟一个很大的数组，如果实际没装满，多出来的空间就浪费了。而动态链表是用多少 malloc 多少，不浪费。

【四】正确答案 B

第32题：【2016统考真题】已知一个带有表头结点的循环双链表L,结点结构为: prev data next。其中 prev 和 next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点,正确的语句序列是( ) A. p->next->prev=p->prev; p->prev->next=p->prev; free(p); B. p->next->prev=p->next; p->prev->next=p->next; free(p); C. p->next->prev=p->next; p->prev->next=p->prev; free(p); D. p->next->prev=p->prev; p->prev->next=p->next; free(p);

【一】题目考察什么知识点 考察双向链表的删除操作代码实现。

【二】如何通俗理解 p 站在中间，要把它踢出队伍。你只需要让它右边的人的左手（p->next->prev）去牵它左边的人（p->prev）；让它左边的人的右手（p->prev->next）去牵它右边的人（p->next）。这俩动作互不干扰，顺序随便。

【三】逐步推导过程

  • 选项 A 第二句 p->prev->next = p->prev; 让左边的人右手牵自己，错。
  • 选项 B 第一句 p->next->prev = p->next; 让右边的人左手牵自己，错。
  • 选项 C 两句全是让别人牵自己，大错特错。
  • 选项 D：p->next->prev = p->prev;（右邻居的左手牵左邻居），p->prev->next = p->next;（左邻居的右手牵右邻居），完美闭环！

【四】正确答案 D

第33题：【2016统考真题】已知表头元素为c的单链表在内存中的存储状态如下表所示: 地址 1000H 放 a，链接 1010H 地址 1004H 放 b，链接 100CH 地址 1008H 放 c，链接 1000H 地址 100CH 放 d，链接 NULL 地址 1010H 放 e，链接 1004H 现将f存放于1014H处并插入单链表,若f在逻辑上位于a和e之间,则a,e,f的“链接地址”依次是() A. 1010H, 1014H, 1004H B. 1010H, 1004H, 1014H C. 1014H, 1010H, 1004H D. 1014H, 1004H, 1010H

【一】题目考察什么知识点 考察单链表指针（链接地址）的物理本质与修改逻辑。

【二】解题思路分析 这道题看起来眼花缭乱，我们要做的第一步是**“还原现场”**，理清插入前单链表的真实逻辑顺序。

【三】逐步推导过程

  1. 表头是 c (位于 1008H)。
  2. c 的链接指向 1000H (即 a)。当前链表: c → a
  3. a 的链接指向 1010H (即 e)。当前链表: c → a → e
  4. e 的链接指向 1004H (即 b)。当前链表: c → a → e → b
  5. b 的链接指向 100CH (即 d)。当前链表: c → a → e → b → d
  6. d 的链接是 NULL，链表结束。

现在要把 f(位于 1014H) 插入到 a 和 e 之间。即链表变成：c → a → f → e → b → d。 我们来看要怎么改地址：

  • a 必须要指向 f，所以 a 的链接地址变为 f 的地址：1014H。
  • f 必须要指向 e，所以 f 的链接地址变为 e 的地址：1010H。
  • e 依然指向 b，所以 e 的链接地址不变，依然是：1004H。 题目问 a, e, f 的链接地址依次是：1014H, 1004H, 1010H。

【四】正确答案 D

第34题：【2021统考真题】已知头指针h指向一个带头结点的非空循环单链表…其中 p是尾指针,q是临时指针。现要删除该链表的第一个元素,正确的语句序列是() A. h->next=h->next->next; q=h->next; free(q); B. q=h->next; h->next=h->next->next; free(q); C. q=h->next; h->next=q->next; if(p != q) p = h; free(q); D. q=h->next; h->next = q->next; if(p == q) p = h; free(q);

【一】题目考察什么知识点 带尾指针的循环单链表的删除操作，以及极易被忽略的临界条件（只剩一个结点时的出表处理）。

【二】解题思路分析 正常的头删法我们都会写：q = h->next; h->next = q->next; free(q); 但命题人特意给了你一个尾指针 p。你想想，在什么情况下，删除第一个数据元素会影响到“尾巴”？ 只有一种情况：这个队伍里原本只有这1个数据元素！

【三】逐步推导过程

  1. 用 q 暂存要删除的第一个元素：q = h->next;
  2. 将头结点的 next 越过 q 指向下一个元素：h->next = q->next;
  3. 致命判定：如果被删除的 q 就是尾结点 p（即 p == q，说明删除前链表只有这1个数据结点），那么删除后链表就只剩一个空壳头结点了。此时尾指针 p 不能变成野指针，必须让它重新指向头结点 h。即 if(p == q) p = h;。
  4. 最后释放 q 的内存：free(q);。

【四】正确答案 D

【五】错误选项为什么错 A和B根本没有对尾指针进行任何保护，一旦删空，尾指针 p 就会指向被 free 掉的内存，变成悬空指针（野指针）。

第35题：【2023统考真题】现有非空双链表L…若要在L中指针p所指向的结点(非尾结点)之后插入指针s指向的新结点,则在执行语句序列 “s->next = p->next; p->next=s;” 后,下列语句序列中还需要执行的是() A. s->next->prev=p; s->prev=p; B. p->next->prev=s; s->prev=p; C. s->prev=s->next->prev; s->next->prev=s; D. p->next->prev=s->prev; s->next->prev=p;

【一】题目考察什么知识点 双向链表插入时的代码“时序”与指针覆盖问题。

【二】解题思路分析 这道题非常恶心，因为题目提前执行了两句代码，把常规的插入顺序打乱了。我们必须在这个“半成品”的状态下收拾残局。

【三】逐步推导过程 初始状态：p → 原后继。 已执行的语句：

  1. s->next = p->next; (s的右手牵住了原后继)
  2. p->next = s; (p的右手松开了原后继，改牵了s。注意：此时通过 p 已经找不到原后继了！)

此时还剩下两个动作没做：① 让 s 的左手牵 p；② 让原后继的左手牵 s。 我们来看看此时各指针指向谁：

  • p 就是 p。
  • s 就是 s。
  • 原后继是谁？因为 p->next 已经被改了，原后继现在只能通过 s->next 来找到！
  • 原后继的 prev 指针目前还指向着 p。所以 s->next->prev 其实就是 p！

代入选项验证：

  • 选项 B 中：p->next->prev = s; 因为 p->next 已经是 s 了，这句话等于 s->prev = s，完全乱套。
  • 选项 C 中：s->prev = s->next->prev; 翻译过来就是：让 s 的左手，牵住“原后继的左手目前牵着的人(也就是p)”。这完美实现了 s 牵 p！ 接着 s->next->prev = s; 翻译过来就是：让“原后继”的左手，改牵 s。这也完美实现了交接！

【四】正确答案 C

第36题：【2024统考真题】已知带头结点的非空单链表L的头指针为h… 现有指针p和q,若p指向L中非首且非尾的任意一个结点,则执行语句序列 “q=p->next; p->next=q->next; q->next=h->next; h->next=q;” 的结果是() A. 在p所指结点后插入所指结点 B. 在q所指结点后插入p所指结点 C. 将p所指结点移至L的头结点之后 D. 将q所指结点移动到L的头结点之后

【一】题目考察什么知识点 单链表结点的“摘除”与“头插”。

【二】如何通俗理解 这四句代码就像是一个魔术： 第一句锁定目标（q 是 p 后面的小弟）； 第二句过河拆桥（p 跳过 q，把 q 从队伍里踢了出来）； 第三、四句就是经典的“头插法”（把刚刚踢出来的 q，硬塞到队伍的最前面，也就是头结点的屁股后面）。

【三】逐步推导过程

  1. q = p->next;：让 q 指向 p 的下一个结点（锁定嫌疑人 q）。
  2. p->next = q->next;：让 p 越过 q，直接指向 q 的下一个结点。此时 q 已经从原来的位置脱离了。
  3. q->next = h->next; 和 h->next = q;：这两句是标准的在头结点 h 之后插入 q 结点的逻辑。 综合起来，就是把原本在 p 后面的结点（即现在的 q），拔出来，插到了链表的最前面。

【四】正确答案 D

第3章 栈、队列和数组 - 3.1 栈 (Part 1: 基础概念与操作)

第1题：栈和队列具有相同的( ) A. 抽象数据类型 B. 逻辑结构 C. 存储结构 D. 运算

【一】题目考察什么知识点 考察栈和队列的宏观逻辑归属。

【二】如何通俗理解（生活化类比） 栈是“死胡同”，先进后出；队列是“单向行车道”，先进先出。虽然它们进出的规矩不一样（运算不同），但在宏观上看，大家都是排成一条线的队伍，也就是“线性结构”。

【三】解题思路分析 栈和队列本质上都是受限的线性表。

【四】逐步推导过程

  • A项：抽象数据类型不仅包含数据，还包含操作。栈和队列的操作（LIFO vs FIFO）截然不同，所以ADT不同。
  • C项：它们既可以用顺序表存，也可以用链表存，没有固定的相同存储结构。
  • D项：运算不同（栈是在一端增删，队列是在两端）。
  • B项：它们在逻辑上都是一条线，元素之间是一对一的关系，所以具有相同的逻辑结构（线性结构）。

【五】正确答案 B

第2题：栈是一种() A. 顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存储点的非线性结构

【一】题目考察什么知识点 栈的严格定义。

【三】逐步推导过程 栈是只允许在一端进行插入或删除操作的线性表。

  • 首先它必须是“线性结构”，排除了 B 和 D。
  • 其次，它是一种逻辑结构，可以用顺序存也可以用链式存，A 说死了是顺序存储，错误。
  • C 完美描述了它的特性：限制了存取点（只能在栈顶操作）的线性结构。

【四】正确答案 C

第3题：下列选项中,( )不是栈的基本操作。 A. 删除栈顶元素 B. 删除栈底元素 C. 判断栈是否为空 D. 将栈置为空栈

【一】题目考察什么知识点 栈的操作铁律（LIFO）。

【三】逐步推导过程 栈的唯一操作出入口就是“栈顶”。删除栈顶元素（Pop）是标准操作。绝对不允许操作栈底元素，否则它就失去了栈的独有特性（那就变成双端队列或普通线性表了）。

【四】正确答案 B

第4题：假定利用数组a[n]存储一个栈,初始栈顶指针 top==-1,则元素x进栈的操作为( ) A. a[–top]=x B. a[top–]=x C. a[++top]=x D. a[top++]=x

【一】题目考察什么知识点 顺序栈入栈的代码实现与指针先后的顺序（高频代码填空点）。

【二】解题思路分析 核心看 top 的初始值。如果初始值指向的格子不能直接存数据，那就要先移动指针，再存数据。

【三】逐步推导过程 top == -1 时，数组的下标 -1 是越界的，不能存东西。 所以要存入第一个元素 x 时，必须先把 top 往上挪一格变成 0，然后再存进 a[0]。 对应的代码逻辑就是：先加加（++top），后赋值（a[top] = x），合并起来就是 a[++top] = x。

【四】正确答案 C

第5题：假定用数组 a[1…n] 存储一个栈,初始栈顶指针 top=1,则元素x进栈的操作是( ) A. data[top–]=x B. data[top++]=x C. data[–top]=x D. data[++top]=x

【一】题目考察什么知识点 初始栈顶指针位置不同导致的入栈逻辑变化。

【三】逐步推导过程 注意这里的数组是从 1 开始的。top 初始值为 1。 这意味着 top 当前指向的格子（data[1]）正好是空着的、可以直接存数据的首个合法位置。 所以第一步：直接把数据存进去 data[top] = x。 第二步：存完之后，top 必须往上走一格，准备迎接下一个人，即 top++。 合并起来就是先用后加：data[top++] = x。

【四】正确答案 B

第6题：假定用数组 a[1…n] 存储一个栈,初始栈顶指针 top=n+1,则元素x进栈的操作是( ) A. data[–top]=x B. data[top++]=x C. data[top–]=x D. data[++top]=x

【一】题目考察什么知识点 倒生栈（栈底在高地址，往低地址生长）的入栈逻辑。

【三】逐步推导过程 数组范围是 1...n，初始 top 却是 n+1，越界了！ 这说明栈是从后往前倒着长的。因为 n+1 这个位置不能存数据，所以你要存入第一个数据时，必须先把 top 减去 1 变成 n，然后再存入 data[n]。 逻辑：先减减（--top），后赋值。即 data[--top] = x。

【四】正确答案 A

第7题：设有一个空栈,栈顶指针为1000H,每个元素需要一个存储单元,执行Push、Push、Pop、Push、Pop、Push、Pop、Push操作后,栈顶指针为( ) A. 1002H B. 1003H C. 1004H D. 1005H

【一】题目考察什么知识点 栈中元素数量的动态计算与内存地址偏移。

【三】逐步推导过程 我们不去管中间过程多复杂，只算总账： 一共执行了 5 次 Push（加5个元素），3 次 Pop（减3个元素）。 所以最终栈里比原来多了 5−3=2 个元素。 每个元素占 1 个存储单元，空栈是 1000H，多出 2 个元素，栈顶指针自然向上移动 2 个单元，变为 1002H。（默认栈顶指针随元素增加而增大）。

【四】正确答案 A

第8题：和顺序栈相比,链栈有一个比较明显的优势,即() A. 通常不会出现栈满的情况 B. 通常不会出现栈空的情况 C. 插入操作更容易实现 D. 删除操作更容易实现

【一】题目考察什么知识点 链式存储在容量分配上的绝对优势。

【三】逐步推导过程

  • 顺序栈底层是数组，初始化时大小就固定了（或者动态扩容代价大），如果数据量难以估算，很容易发生“上溢（栈满）”。
  • 链栈底层是离散的内存通过指针连接，用一个结点就 malloc 一个，只要计算机可用内存没耗尽，它就永远不会满。

【四】正确答案 A

第9题：设链表不带头结点且所有操作均在表头进行,则下列最不适合作为链栈的是( ) A. 只有表头结点指针,没有表尾指针的双向循环链表 B. 只有表尾结点指针,没有表头指针的双向循环链表 C. 只有表头结点指针,没有表尾指针的单向循环链表 D. 只有表尾结点指针,没有表头指针的单向循环链表

【一】题目考察什么知识点 各类循环链表在特定操作（表头增删）下的时间代价比较。

【二】解题思路分析 题目要求“所有操作均在表头进行”。对于循环链表来说，在表头插入或删除一个结点，必须要修改表尾结点的指针（让它重新咬住新的表头）！ 所以，谁找“表尾结点”最困难（复杂度高达 O(n)），谁就最不适合。

【三】逐步推导过程

  • A（只有头指针，双向循环）：通过 head->prior 瞬间（O(1)）就能找到尾结点。适合。
  • B（只有尾指针，双向循环）：通过 rear->next 瞬间找到头结点。适合。
  • D（只有尾指针，单向循环）：通过 rear->next 就是头结点。插在头结点后，再让 rear 咬住新头即可，O(1)。适合。
  • C（只有头指针，单向循环）：你要修改尾巴，但你只有头指针，并且它是“单向”的！你无法通过 head->prior 往回找，只能顺藤摸瓜绕一整圈跑 n−1 步找到尾结点。入栈操作的时间复杂度变成了惊人的 O(n)。极其不适合作为要求效率的栈！

【四】正确答案 C

第10题：向一个栈顶指针为top的链栈(不带头结点)中插入一个x结点,则执行() A. top->next=x B. x->next=top->next; top->next=x C. x->next=top; top=x D. x->next=top; top=top->next

【一】题目考察什么知识点 无头结点链栈的入栈（本质是头插法）代码逻辑。

【三】逐步推导过程 top 指针直接指着最顶上的数据结点（没有带虚假的头结点）。

  1. 新来的 x 要压在最上面，所以 x 的下面应该是原来的栈顶 top，即 x->next = top;
  2. x 成功登顶后，栈顶的标志 top 必须移交给 x 结点本身，即 top = x;

【四】正确答案 C

第3章 栈、队列和数组 - 3.1 栈 (Part 2: 出栈序列与进阶操作)

第11题：链栈(不带头结点)执行Pop操作,并将出栈的元素存在x中,应该执行() A. x=top; top=top->next B. x=top->data C. top=top->next; x=top->data D. x=top->data; top=top->next

【一】题目考察什么知识点 考察不带头结点的链栈的出栈（Pop）代码基本逻辑。

【二】解题思路分析 出栈分为两步：第一步，把当前栈顶结点里的数据拿出来存好；第二步，把栈顶指针（top）往下移一个结点，抛弃原来的栈顶。

【三】逐步推导过程

  • A项：把结点指针直接赋给数据变量x，类型不匹配，且丢了数据。
  • B项：只拿了数据，忘了移动栈顶指针（这叫GetTop，不叫Pop）。
  • C项：先移动了指针，再去拿数据。这样拿到的是原栈顶下面的那个元素，原栈顶的数据彻底丢失了！
  • D项：先 x = top->data; 稳稳把数据放进口袋，再 top = top->next; 让栈顶下移。完美符合逻辑。

【四】正确答案 D

第12题：经过以下栈的操作后,变量x的值为( ) InitStack(st); Push(st, a); Push(st, b); Pop(st, x); GetTop(st, x); A. a B. b C. NULL D. false

【一】题目考察什么知识点 考察对栈的基本操作序列的追踪能力。

【三】逐步推导过程 我们一步步画出栈内的状态（左底右顶）：

  1. InitStack(st); → 栈空 []
  2. Push(st, a); → 栈内容 [a]
  3. Push(st, b); → 栈内容 [a, b] (此时栈顶是 b)
  4. Pop(st, x); → 弹出栈顶的 b 赋给 x。此时 x = b，栈内容变回 [a]。
  5. GetTop(st, x); → 读取当前栈顶的值赋给 x，注意 GetTop 不删除元素。当前栈顶是 a，所以 x = a，栈内容依然是 [a]。 最终 x 的值被最后一步覆盖为了 a。

【四】正确答案 A

第13题：三个不同元素依次进栈,能得到()种不同的出栈序列。 A. 4 B. 5 C. 6 D. 7

【一】题目考察什么知识点 408必考数学公式：卡特兰数（Catalan Number）。

【二】如何通俗理解 n 个元素按顺序进栈，到底能有多少种合法的出栈排列？数学家卡特兰早就推导出了一个万能公式：Cn​=n+11​C2nn​ （组合数）。

【三】逐步推导过程 题目中 n=3。直接代入卡特兰数公式： C3​=3+11​×C63​=41​×3×2×16×5×4​=41​×20=5。

【四】正确答案 B

【七】如何举一反三 考研中经常考 n=3,4,5 的情况，建议直接背下这前几个卡特兰数：

  • n=1: 1种
  • n=2: 2种
  • n=3: 5种
  • n=4: 14种
  • n=5: 42种 （口诀：“一二五，一四四二”）。看到题目问“n个节点能构成多少种不同形态的二叉树”，答案也是卡特兰数！

第14题：设a,b,c,d,e,f以所给的次序进栈,若在进栈操作时,允许出栈操作,则下面得不到的序列为( ) A. fedcba B. bcafed C. dcefba D. cabdef

【一】题目考察什么知识点 栈的 LIFO (后进先出) 规则在具体序列中的合法性判定。这是选择题的超高频题型！

【二】解题思路分析（独家“防错秒杀法”） 判定一个出栈序列是否合法，只需盯住一个铁律：“对于序列中的任何一个出栈元素，排在它后面的、且比它先入栈的元素，必须是逆序出栈的。” （因为比它先入栈的元素全都被压在它下面，如果它们要出栈，必须按从上到下的顺序出。）

【三】逐步推导过程 我们直接扫描选项（以 a,b,c,d,e,f 顺序入栈为例）：

  • A项 fedcba：完全逆序。说明是一口气全进栈，再一口气全出栈。合法。

  • B项 bcafed：看 b，它后面的 a 先于它入栈，且就这一个，合法；看 c，后面的 a 已经出了，合法。推演一遍：进a,进b,出b,进c,出c,出a,进d,e,f,出f,e,d。合法。

  • D项 cabdef（重点排雷）：

    • 第一个出的是 c，这意味着什么？意味着 a 和 b 目前死死地被压在栈底（此时栈从底到顶是 a, b）。
    • 既然 a 被压在 b 的底下，那么在后续的出栈中，b 必须在 a 之前出栈！
    • 但是你看 D 选项，在 c 后面紧跟着出栈的竟然是 a（c → a → b）！这就相当于你想把压在最底下的 a 隔着 b 抽出来，严重违反栈的规则。不合法！

【四】正确答案 D

第15题：4个元素依次进栈的次序为a,b,c,d,则以c,d开头的出栈序列的个数为( ) A. 1 B. 2 C. 3 D. 4

【一】题目考察什么知识点 在给定部分前缀情况下的出栈序列推演。

【三】逐步推导过程

  1. 要想让 c 第一个出栈，唯一的操作途径是：进 a，进 b，进 c，然后出 c。此时栈内残底为：[a, b]（b在顶）。
  2. 要想让 d 第二个出栈，唯一的操作途径是：进 d，然后出 d。此时栈内残底依然为：[a, b]。
  3. 现在所有元素都进过栈了，栈里还剩 b（在顶）和 a（在底）。
  4. 它们出栈的顺序只能是先出 b，再出 a。 所以，以 c,d 开头的序列只有一种可能：c, d, b, a。

【四】正确答案 A

第16题：用S表示进栈操作,用X表示出栈操作,若元素的进栈顺序是1234,为了得到1342的出栈顺序,相应的S和X的操作序列为( ) A. SXSXSSXX B. SSSXXSXX C. SXSSXXSX D. SXSSXSXX

【一】题目考察什么知识点 逆向推导进出栈的操作步骤。

【三】逐步推导过程 目标出栈序列：1, 3, 4, 2。

  1. 要想出 1，必须先进 1：S (进1)，接着马上出 1：X (出1)。【目前序列：SX，栈空】
  2. 要想出 3，必须让 2、3 进栈：S (进2)，S (进3)，接着出 3：X (出3)。【目前序列加了 SSX，变成 SXSSX。此时栈内留有 2】
  3. 要想出 4，必须进 4：S (进4)，接着出 4：X (出4)。【目前序列加了 SX，变成 SXSSXSX。栈内留有 2】
  4. 最后出 2，直接从栈顶弹出：X (出2)。【完整序列为：SXSSXSXX】

【四】正确答案 D

第17题：若一个栈的输入序列是 1,2,3,⋅⋅⋅,n, 输出序列的第一个元素是n,则第i个输出元素是( ) A. ≤n−i−1 B. n−i C. n−i+1 D. 不确定

【一】题目考察什么知识点 栈的极端出栈情况（完全逆序）。

【三】逐步推导过程 题干给出“输出序列的第一个元素是 n”。n 是最后一个输入元素，它既然第一个出来了，说明什么？ 说明在前 n−1 个元素进栈的时候，全都没有出栈！ 直到第 n 个元素进去后，才开始一股脑儿全退出来。 因此，输出序列必定是完全的逆序：n,n−1,n−2,…,2,1。 找规律： 第 1 个输出是 n （即 n−1+1）； 第 2 个输出是 n−1 （即 n−2+1）； 所以，第 i 个输出的元素就是 n−i+1。

【四】正确答案 C (注意：此题你的题本扫描版选项错乱，C和D的描述混了。正确公式为 n−i+1。根据常见的选项排布，通常是C。对照选项我已将正确推导写出，如果选项中 D 是 n−i+1，则选 D)。 (更正：看你的题本原文，D 选项是 n−i+1。所以选 D)

第18题：一个栈的输入序列为 1,2,3,⋅⋅⋅,n,输出序列的第一个元素是i,则第j个输出元素是( ) A. i−j−1 B. i−j C. j−i+1 D. 不确定

【一】题目考察什么知识点 出栈序列的非唯一性分析。

【三】逐步推导过程 第一个出栈的是 i，这只说明了 1∼i−1 已经被压在栈底了（当前栈从顶到底依次是 i−1,i−2,…,1），而 i+1∼n 还没有进栈。 那么第二个出栈的（即 j=2 时）会是谁？

  • 可以直接弹出栈顶的 i−1。
  • 也可以接着让 i+1 进栈然后再弹出，此时输出就是 i+1。 既然有多种选择，所以第 j 个输出元素是无法给出唯一确定的公式的。

【四】正确答案 D

第19题：某栈的输入序列为a,b,c,d,下面的4个序列中,不可能为其输出序列的是( ) A. a,b,c,d B. c,b,d,a C. d,c,a,b D. a,c,b,d

【一】题目考察什么知识点 再次考察出栈序列的合法性（参考第14题绝招）。

【三】逐步推导过程 寻找“排在后面、且先入栈的元素，有没有违反逆序规律”。 看 C 选项 d,c,a,b： d 第一个出栈，此时栈里面必定压着 [a, b, c]（c 在栈顶）。 接下来 c 出栈，没问题。 此时栈里面只剩 [a, b] 了（b 在栈顶）。按理说下一个必须是弹 b！ 但 C 选项第三个出栈的是 a，这就是想隔着 b 把底下的 a 抽走，这在栈里是绝对不可能发生的。

【四】正确答案 C

第20题：若一个栈的输入序列是 P1​,P2​,⋅⋅⋅,Pn​, 输出序列是 1,2,3,⋅⋅⋅,n, 若 P3​=1,则 P1​ 的值() A. 可能是2 B. 一定是2 C. 不可能是2 D. 不可能是3

【一】题目考察什么知识点 逆向思维：已知输出序列和某个位置的入栈元素，推断入栈序列。这是408历年真题改编的最强陷阱。

【二】解题思路分析 题干说输出序列是 1, 2, 3, ..., n，这意味着 1 是第一个出栈的，2 是第二个出栈的。 题干又说 P3​=1（第3个入栈的是元素’1’）。

【三】逐步推导过程

  1. 前三个入栈的元素依次是：P1​,P2​,P3​(即元素′1′)。
  2. 因为 ‘1’ 是第一个出栈的，说明在这个时刻，P1​ 和 P2​ 都稳稳地压在栈里，且 P2​ 压在 P1​ 上面。
  3. 现在 ‘1’ 已经走了。根据输出序列的要求，下一个出栈的必须是元素 ‘2’。
  4. 假设 P1​=2。 因为 P2​ 压在 P1​ (即2) 上面，要想让 2 出栈，必须先让 P2​ 出栈！ 也就是说，输出序列会变成：1 → $P_2$ → 2。 而 P2​ 显然不可能是 1（1已经出了），所以这就产生了一个大于 1 的元素排在了 2 的前面，打破了 1, 2, 3... 的输出规律！ （除非 P2​=2，但这又不可能，因为每个数只出现一次，既然 P1​=2，那 P2​ 就不能是 2）。
  5. 因此，得出绝杀结论：P1​ 绝对不可能是 2！ （注：如果 P1​=3,P2​=2，那么 1 走后，正好弹 P2​(2)，再弹 P1​(3)，输出刚好是 1,2,3。这就成立）。

【四】正确答案 C

第3章 栈、队列和数组 - 3.1 栈 (Part 3: 序列推导与统考真题)

第21题：若一个栈的输入序列是 P1​,P2​,…,Pn​，输出序列是 1,2,3,…,n。若 P3​=3，则 P1​ 的值( ) A. 可能是2 B. 不可能是1 C. 一定是1 D. 一定是2

【一】题目考察什么知识点 考察已知部分入栈和出栈序列，逆推入栈元素的可能性。

【二】解题思路分析 题目说输出序列是按顺序的 1, 2, 3...。并且第三个进栈的元素是 3（即 P3​=3）。我们需要推演前两个进栈的元素 P1​ 和 P2​ 可以是什么。

【三】逐步推导过程

  • 假设 P1​=1,P2​=2： 进 1，出 1；进 2，出 2；接着 P3​(3) 进栈，出 3。输出序列是 1, 2, 3，符合条件！所以 P1​ 可能是 1。
  • 假设 P1​=2,P2​=1： 进 2，进 1；此时栈顶是 1，出 1；接着出 2；接着 P3​(3) 进栈，出 3。输出序列依然是 1, 2, 3，完全符合条件！所以 P1​ 也可能是 2。 综上所述，P1​ 既可能是 1 也可能是 2。对照选项，只有 A 正确。

【四】正确答案 A

第22题：已知一个栈的入栈序列是1,2,3,4, 其出栈序列为 P1​,P2​,P3​,P4​，则 P2​,P4​ 不可能是( ) A. 2, 4 B. 2, 1 C. 4, 3 D. 3, 4

【一】题目考察什么知识点 指定位置的出栈元素合法性判定。

【三】逐步推导过程 让我们直接排雷，看选项 C (即 P2​=4,P4​=3) 为什么不可能：

  1. 如果 P2​=4，说明第 2 个出栈的是 4。

  2. 因为 4 是最后一个入栈的，要让它第 2 个出栈，只能是：前 3 个数里有 1 个提前出栈了（充当了 P1​），剩下的 2 个数被压在栈底。

  3. 当 4 出栈后，栈里剩下的那两个数（比如 1 和 2，或者 2 和 3）必须按逆序出栈。

  4. 重点来了：既然 4 已经出栈了，那么 3 一定早就进栈了（要么是 P1​ 已经出了，要么被压在栈里）。

    • 如果 3 是 P1​ 已经出了，那么 P4​ 绝对不可能是 3。
    • 如果 3 被压在栈里，那它一定压在 1 和 2 的最上面！所以 4 出栈后，下一个出栈的（即 P3​）必须是 3！

  5. 因此，如果 P2​=4，3 要么是 P1​，要么是 P3​，绝对轮不到最后才出栈变成 P4​！

【四】正确答案 C

第23题：设栈的初始状态为空, 当字符序列“n1_”作为栈的输入时, 输出长度为3, 且可用做C语言标识符的序列有()个。 A. 4 B. 5 C. 3 D. 6

【一】题目考察什么知识点 卡特兰数结合C语言标识符命名规则。

【二】解题思路分析

  1. 3个字符进栈，总共可能的出栈序列有 C3​=5 种（卡特兰数）。
  2. C语言标识符的铁律：只能由字母、数字和下划线组成，且不能以数字开头！ 这里的输入是字母 n、数字 1、下划线 _。
  3. 找出那5种序列中，不以 1 开头的序列即可。

【三】逐步推导过程 全部的 5 种出栈序列分别是：

  • n, 1, _ （合法）
  • n, _, 1 （合法）
  • 1, n, _ （非法，数字1开头）
  • 1, _, n （非法，数字1开头）
  • _, 1, n （合法，下划线开头是可以的） 剔除掉2个以 1 开头的，剩下 3 个合法的。

【四】正确答案 C

第24题：采用共享栈的好处是( ) A. 减少存取时间，降低发生上溢的可能 B. 节省存储空间，降低发生上溢的可能 C. 减少存取时间，降低发生下溢的可能 D. 节省存储空间，降低发生下溢的可能

【一】题目考察什么知识点 共享栈（两个栈底在数组两端，向中间生长）的设计目的。

【二】如何通俗理解 就像两个合租的室友用一个大衣柜。一个人衣服多，一个人衣服少，中间不设固定隔板，谁需要就多占点空间。这样能最大化节省存储空间，并且只有当两人衣服加起来真正塞满整个柜子时才装不下（降低上溢可能）。这跟存取速度无关，也防不了下溢（栈空）。

【四】正确答案 B

第25题：设有一个顺序共享栈Share[0: n-1]，其中第一个栈顶指针 top1 的初值为 -1，第二个栈顶指针 top2 的初值为 n，则判断共享栈满的条件是( ) A. top2 - top1 == 1 B. top1 - top2 == 1 C. top1 == top2 D. 以上都不对

【一】题目考察什么知识点 共享栈满的临界条件。

【三】逐步推导过程

  • 栈 1 从左往右长，top1 指向栈 1 当前的栈顶元素。
  • 栈 2 从右往左长，top2 指向栈 2 当前的栈顶元素。
  • 当两个栈顶指针“撞车”也就是紧挨着的时候，说明中间已经没有空位了。因为 top2 在右边，top1 在左边，紧挨着意味着 top2 刚好比 top1 大 1。

【四】正确答案 A

第26题：【2009统考真题】设栈S和队列Q的初始状态均为空，元素 a,b,c,d,e,f,g 依次进入栈S。若每个元素出栈后，立即进入队列Q，且7个元素出队的顺序是 b,d,c,f,e,a,g，则栈S的容量至少是() A. 1 B. 2 C. 3 D. 4

【一】题目考察什么知识点 栈的动态深度模拟。

【二】解题思路分析 队列是先进先出的！所以“出队的顺序”其实就是“进入队列的顺序”，也就是栈的出栈顺序！ 我们只要对着出栈顺序 b, d, c, f, e, a, g，一步步模拟进出栈操作，记录下栈里元素最多的时候有几个即可。

【三】逐步推导过程 入栈序列只能是 a, b, c, d, e, f, g。

  1. 要出 b → 进 a，进 b。栈内：[a, b] (深度2)。出 b。
  2. 要出 d → 进 c，进 d。栈内：[a, c, d] (深度3)。出 d。
  3. 要出 c → 直接出 c。栈内：[a] (深度1)。
  4. 要出 f → 进 e，进 f。栈内：[a, e, f] (深度3)。出 f。
  5. 要出 e → 直接出 e。栈内：[a] (深度1)。
  6. 要出 a → 直接出 a。栈内空。
  7. 要出 g → 进 g，出 g。 整个过程中，栈里最多同时存在 3 个元素，所以容量至少是 3。

【四】正确答案 C

第27题：【2010统考真题】若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续3次进行退栈操作，不可能得到的出栈序列是( ) A. dcebfa B. cbdaef C. bcaefd D. afedcb

【一】题目考察什么知识点 出栈序列模拟与限制条件。

【三】逐步推导过程 这题有一个特殊的附加条件：不允许连续 3 次 Pop。 我们看 D 选项：a, f, e, d, c, b。 要得到这个序列，过程必须是：

  1. 进 a，出 a (此时栈空)。
  2. 依次进 b, c, d, e, f (此时栈从底到顶是 b, c, d, e, f)。
  3. 然后开始疯狂退栈：出 f，出 e，出 d，出 c，出 b。 你看最后一步，一口气连续执行了 5 次退栈操作！这严重违反了题干“不允许连续3次退栈”的规矩，所以绝对不可能得到。

【四】正确答案 D

第28题：【2011统考真题】元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是() A. 3 B. 4 C. 5 D. 6

【一】题目考察什么知识点 指定前缀的出栈序列组合数计算。

【三】逐步推导过程

  1. 第一个出栈的是 d。为了让 d 出栈，前面的 a, b, c 必须全被压在栈底（栈内状态：顶 c, b, a 底）。

  2. d 出栈后，手里还剩下一个尚未进栈的元素 e。

  3. 此时栈里的 c, b, a 只能按这个死顺序依次出栈。而元素 e 可以随时插队进去然后马上出栈。

  4. e 可以在哪个时机出栈呢？

    • 出栈 e，然后出 c, b, a → 序列为 d, e, c, b, a
    • 出 c，然后出栈 e，接着出 b, a → 序列为 d, c, e, b, a
    • 出 c, b，然后出栈 e，接着出 a → 序列为 d, c, b, e, a
    • 出 c, b, a，最后出栈 e → 序列为 d, c, b, a, e 显然，e 有 4 个“插空”的位置，因此共有 4 种可能的序列。

【四】正确答案 B

第29题：【2013统考真题】一个栈的入栈序列为 1,2,3…n，出栈序列是 P1​,P2​,P3​…Pn​。若 P2​=3，则 P3​ 可能取值的个数是() A. n−3 B. n−2 C. n−1 D. 无法确定

【一】题目考察什么知识点 极高难度的出栈序列可能性推演。

【二】解题思路分析 题干说第 2 个出栈的是 3。问第 3 个出栈的（P3​）有多少种可能。 既然 3 是第二个出栈的，它前面一定有一个数字 P1​ 已经出栈了。P1​ 只能是 1, 2, 或 4。

【三】逐步推导过程 我们来看看 P3​ 到底能不能“随心所欲”：

  1. P3​ 能不能是 1？ 如果 P1​=2,P2​=3。说明 1 被压在栈底。3走后，此时栈顶就是 1，直接弹出 1。所以 P3​ 可能是 1。
  2. P3​ 能不能是 2？ 如果 P1​=1,P2​=3。说明 2 被压在栈底。3走后，弹出 2。所以 P3​ 可能是 2。
  3. P3​ 能不能是 4？ 如果 P1​=1,P2​=3。3走后，接着让 4 进栈并弹出。所以 P3​ 可能是 4。
  4. P3​ 能不能是 5 甚至更大的数？ 如果 P1​=1,P2​=3。3走后，让 4 和 5 进栈，弹出 5。所以 P3​ 可能是 5 乃至后面的任何数。

结论：除了数字 3 已经被用掉了之外，剩下的 1,2,4,5,…,n 都有可能成为 P3​！ 因此，P3​ 可能的取值个数就是除了 3 以外的所有数，共 n−1 个。

【四】正确答案 C

第30题：【2020统考真题】对空栈S进行Push和Pop操作，入栈序列为 a,b,c,d,e，经过 Push、Push、Pop、Push、Pop、Push、Push、Pop 操作后得到的出栈序列是( ) A. b, a, c B. b, a, e C. b, c, a D. b, c, e

【一】题目考察什么知识点 最基础的栈操作跟踪（白送分题）。

【三】逐步推导过程

  1. Push, Push → 进 a, b。栈内：[a, b]
  2. Pop → 出栈顶。输出 b。栈内：[a]
  3. Push → 进 c。栈内：[a, c]
  4. Pop → 出栈顶。输出 c。栈内：[a]
  5. Push, Push → 进 d, e。栈内：[a, d, e]
  6. Pop → 出栈顶。输出 e。栈内：[a, d] 拼接出栈的结果：b, c, e。

【四】正确答案 D

第31题：【2022统考真题】给定有限符号集S，in 和 out 均为 S 中所有元素的任意排列。对于初始为空的栈 ST，下列叙述中，正确的是( ) A. 若 in 是ST的入栈序列，则不能判断 out 是否为其可能的出栈序列 B. 若 out 是ST的出栈序列，则不能判断 in 是否为其可能的入栈序列 C. 若 in 是ST的入栈序列，out 是对应 in 的出栈序列，则 in 与 out 一定不同 D. 若 in 是ST的入栈序列，out 是对应 in 的出栈序列，则 in 与 out 可能互为倒序

【一】题目考察什么知识点 栈的宏观序列特征。

【三】逐步推导过程

  • A项：错。给定入栈和出栈序列，我们完全可以通过模拟法来判断它是否合法。
  • B项：错。同样的，给定出栈序列，结合所有元素的集合，也是可以验证入栈序列合法性的。
  • C项：错。如果进一个就出一个（Push, Pop, Push, Pop…），那么入栈序列和出栈序列是完全相同的！
  • D项：对。如果把所有元素一口气全部压入栈中，然后再一口气全部弹出来，那么出栈序列 out 就是入栈序列 in 的完美倒序（逆序）。

【四】正确答案 D

第3章 栈、队列和数组 - 3.2 队列 (Part 1: 队列基础与循环队列计算)

第1题：栈和队列的主要区别在于( ) A. 它们的逻辑结构不一样 B. 它们的存储结构不一样 C. 所包含的元素不一样 D. 插入、删除操作的限定不一样

【一】题目考察什么知识点 考察栈和队列的本质区别。

【二】如何通俗理解（生活化类比） 栈就像是往一个窄口桶里塞书，后塞进去的必须先拿出来；队列就像是在食堂打饭排队，先排队的人先打到饭。它们排队的阵型都是一条线，唯一的区别就是**“哪边进、哪边出”的规矩不同**。

【三】逐步推导过程 栈和队列在逻辑上都是“线性结构”（排成一条线），在物理上都可以用“顺序表”或“链表”来存储。它们最核心的区别就是操作法则：栈是 LIFO（后进先出，只允许在栈顶操作），队列是 FIFO（先进先出，只允许在队尾进、队头出）。

【四】正确答案 D

第2题：队列的“先进先出”特性是指( ) I. 最后插入队列中的元素总是最后被删除 II. 当同时进行插入、删除操作时,总是插入操作优先 III. 每当有删除操作时,总要先做一次插入操作 IV. 每次从队列中删除的总是最早插入的元素 A. I B. I和IV C. II和III D. IV

【一】题目考察什么知识点 FIFO (First In First Out) 特性的多角度理解。

【三】逐步推导过程

  • I：最后插入的元素排在队伍的最末尾，前面的人没走完，它绝对不能走。所以最后进必然最后出，完全正确。
  • II 和 III：队列的插入和删除是完全独立的两个操作，想进就进，想出就出，没有任何“必须谁优先”或者“捆绑操作”的规矩，错。
  • IV：“先进”就是最早插入的，“先出”就是最先被删除的。原汁原味的 FIFO 定义，正确。

【四】正确答案 B (即 I 和 IV)

第3题：允许对队列进行的操作有( ) A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队列元素之间插入元素 D. 删除队首元素

【一】题目考察什么知识点 队列的“受限”特性。

【三】逐步推导过程 队列是受限的线性表，它的绝对铁律是：只能在队尾插入（入队），只能在队头删除（出队）。

  • A、C：在中间排序或插队，这是普通数组/链表才能干的事，队列严禁插队。
  • B：“最近进队的元素”就是队尾元素。队尾只能进不能出，取出它违反了队列规则（那是栈干的事）。
  • D：删除队首元素，也就是正常的出队操作，合法。

【四】正确答案 D

第4题：一个队列的入队顺序是1,2,3,4,则出队的输出顺序是( ) A. 4, 3, 2, 1 B. 1, 2, 3, 4 C. 1, 4, 3, 2 D. 3, 2, 4, 1

【一】题目考察什么知识点 队列的最基础输出规律。

【二】解题思路分析 这道题和“栈”的出栈序列题形成了鲜明对比。栈的出栈序列花样百出，但队列的输出序列永远只有一种：怎么进去的，就原封不动地怎么出来。

【四】正确答案 B

第5题：循环队列存储在数组 A[0…n] 中,入队时的操作为( ) A. rear=rear+1 B. rear=(rear+1) mod (n−1) C. rear=(rear+1) mod n D. rear=(rear+1) mod (n+1)

【一】题目考察什么知识点 循环队列利用求余（模运算 % 或 mod）实现“环状”移动的公式。

【二】如何通俗理解 想象数组是一个钟表的表盘。指针从 0 走到一圈的最大值后，下一步必须归零重新开始。这就需要用到数学里的“除法取余数（mod）”操作。余数的除数，必须是表盘上的总刻度数（也就是数组的总容量）。

【三】逐步推导过程 题目给出数组范围是 A[0…n]。请注意！从 0 到 n，总共有 n+1 个位置！ 因此，该队列的最大容量 MaxSize 就是 n+1。 循环队列的通用后移公式是：指针 = (指针 + 1) % MaxSize。 代入本题容量，即为：rear = (rear + 1) mod (n + 1)。

【四】正确答案 D

【五】易错点总结 千万不要看到数组定义里有个 n，就毫不犹豫地选模 n。必须数清楚数组到底有几个格子！

第6题：已知循环队列的存储空间为数组A [21], front 指向队头元素的前一个位置,rear指向队尾元素,假设当前 front 和 rear 的值分别为8和3,则该队列的长度为( ) A. 5 B. 6 C. 16 D. 17

【一】题目考察什么知识点 408必背公式：循环队列的元素个数（长度）计算公式。

【二】解题思路分析 只要是循环队列算长度，立刻默写万能公式：Length=(rear−front+MaxSize)%MaxSize。这个公式不管 rear 是在 front 后面（没拐弯）还是在 front 前面（拐弯了），都能完美算出正确结果。

【三】逐步推导过程

  • 数组 A[21] 说明最大容量 MaxSize=21。
  • 当前 front=8,rear=3。
  • 代入万能公式：Length=(3−8+21)%21=16%21=16。

【四】正确答案 C

第7题：若用数组 A[0…5] 来实现循环队列,且当前 rear 和 front 的值分别为1和5,当从队列中删除一个元素,再加入两个元素后, rear和front 的值分别为( ) A. 3和4 B. 3和0 C. 5和0 D. 5和1

【一】题目考察什么知识点 循环队列头尾指针的具体步进模拟。

【三】逐步推导过程

  1. 确定容量：数组 A[0…5]，共 6 个位置，MaxSize=6。
  2. 初始状态：rear=1,front=5。
  3. 删除一个元素（出队）：修改头指针。front=(front+1)%6=(5+1)%6=0。
  4. 加入两个元素（入队两次）：修改尾指针。rear=(rear+2)%6=(1+2)%6=3。
  5. 最终结果：rear=3,front=0。

【四】正确答案 B

第8题：假设用数组 Q[Maxsize]实现循环队列,队首指针 front 指向队首元素的前一位置,队尾指针 rear 指向队尾元素,则判断该队列为空的条件是( ) A. Q.rear==(Q.front+1)%MaxSize B. (Q.rear+1)%MaxSize==Q.front+1 C. (Q.rear+1)%MaxSize==Q.front D. Q.rear==Q.front

【一】题目考察什么知识点 循环队列判空的终极标准。

【二】解题思路分析 我们让 front 和 rear 就像操场上的两个跑步者。front 指向排头的前一个位置，rear 指向排尾。如果队伍里一个人都没有，说明排头和排尾根本没拉开差距，两人必定重合。

【三】逐步推导过程 只要是不采用“额外变量法（比如用 size 记录个数）”的普通循环队列，无论是何种指针设定法则，判断队列为空的条件永远是：头尾指针相遇，即 front==rear。

【四】正确答案 D

第9题：假设循环队列Q[MaxSize]的队头指针为front, 队尾指针为rear,队列的最大容量为MaxSize,此外,该队列再没有其他数据成员,则判断该队的列满条件是( ) A. Q.front==Q.rear B. Q.front+Q.rear>=MaxSize C. Q.front==(Q.rear+1)%MaxSize D. Q.rear=(Q.front+1)%MaxSize

【一】题目考察什么知识点 牺牲一个存储单元以区分队空与队满的判断公式。

【二】如何通俗理解 既然 front==rear 已经被“队空”征用了。那如果队列全塞满了，尾指针追上了头指针，再次发生 front==rear 怎么办？这不就分不清是空还是满了吗？ 为了解决这个矛盾，我们采用“留一个空座”的策略。也就是说，当尾巴 rear 再往前走一步就要撞上头 front 的时候，我们就强行认为队列已经满了。

【三】逐步推导过程 “尾巴往前走一步撞上头” 的数学翻译就是：尾巴指针 + 1（并取模），等于头指针。 写成公式即：(Q.rear+1)%MaxSize==Q.front。

【四】正确答案 C

第10题：假设用 A[0…n] 实现循环队列,front、rear分别指向队首元素的前一个位置和队尾元素。若用 (rear+1)%(n+1)==front 作为队满标志,则( ) A. 可用 front==rear 作为队空标志 B. 队列中最多可有 n+1 个元素 C. 可用 front>rear 作为队空标志 D. 可用 (front+1)%(n+1)==rear 作为队空标志

【一】题目考察什么知识点 牺牲一个单元法循环队列的综合特征。

【三】逐步推导过程 题干给出的队满条件 (rear+1)%(n+1)==front，正是标准的“牺牲一个存储单元”的做法（注意数组大小是 n+1）。

  • 既然它使用了标准的队满判定法，那么它的队空判定法必然是毫无争议的 front==rear。所以 A 正确。
  • B 为什么错？数组总容量是 n+1，既然牺牲了一个单元不用来存数据，那么队列中最多只能放 n 个元素。
  • C 错，由于是循环的，front 完全可能大于 rear，但这并不代表队空。

【四】正确答案 A

第11题：与顺序队列相比,链式队列() A. 优点是队列的长度不受限制 B. 优点是进队和出队时间效率更高 C. 缺点是不能进行顺序访问 D. 缺点是不能根据队首指针和队尾指针计算队列的长度

【一】题目考察什么知识点 考察顺序队列与链式队列的宏观特性对比。

【三】逐步推导过程

  • A项：这是链表相对于数组的通用优点，不受初始分配大小限制。是正确的优点描述，但往往不是选择“与…相比”时的唯一核心。不过看D项更加“一针见血”。
  • B项：不论是顺序循环队列还是链队列，进出队都是 O(1)，时间效率并无高下之分。
  • C项：链队列本来就是顺藤摸瓜，完全可以顺序访问。
  • D项：顺序队列的长度可以瞬间通过公式 (rear - front + MaxSize) % MaxSize 算出，时间复杂度 O(1)。而链式队列如果没有额外维护一个 size 变量，光凭 front 和 rear 指针是根本算不出长度的，必须从头遍历一遍（O(n)），这是它极其明显的缺点。

【四】正确答案 D

第12题：下列描述的几种链表中,最适合用作队列的是( ) A. 带队首指针和队尾指针的循环单链表 B. 带队首指针和队尾指针的非循环单链表 C. 只带队首指针的非循环单链表 D. 只带队首指针的循环单链表

【一】题目考察什么知识点 基于操作特性的数据结构选型。

【二】解题思路分析 队列的特性是：一头出（队头出），一头进（队尾进）。所以我们要求能在 O(1) 的时间内找到队头和队尾。

【三】逐步推导过程 最朴素、最合适的结构就是带队首指针和队尾指针的非循环单链表。 front 指针负责出队操作，rear 指针负责入队操作，互不干扰，逻辑最简单清晰。没必要引入循环（循环链表的尾插法还要额外修改尾巴的 next 指针指回头结点，徒增麻烦）。

【四】正确答案 B

第13题：下列描述的几种链表中,最不适合用作链式队列的是( ) A. 只带队首指针的非循环双链表 B. 只带队首指针的循环双链表 C. 只带队尾指针的循环双链表 D. 只带队尾指针的循环单链表

【一】题目考察什么知识点 反向排除：寻找操作代价最大的链表结构。

【三】逐步推导过程 队列必须在队尾入队。 如果是选项 A（只带队首指针，而且是非循环的），当你想要在队尾插入新元素时，你不仅没有尾指针，而且因为“非循环”，你无法通过 front->prior 瞬间回退到尾巴。你只能苦哈哈地从队首一直遍历 n-1 步走到队尾，耗时 O(n)！这对于需要频繁入队的队列来说是灾难性的。 (B可以通过 front->prior 找尾巴，C和D都能 O(1) 找头尾)。

【四】正确答案 A

第14题：在用单链表实现队列时,队头设在链表的( )位置。 A. 链头 B. 链尾 C. 链中 D. 以上都可以

【一】题目考察什么知识点 单链表操作的非对称性。

【二】解题思路分析 单链表是个“单行道”，找后继容易（O(1)），找前驱难（O(n)）。 队列的两个操作：删除、插入。

  • 如果把队头（发生删除操作的地方）设在链尾：你要删除链尾节点，就必须找到它的前驱（倒数第二个节点），这需要从头遍历 O(n)。绝对不行！
  • 如果把队头设在链头：删除只需 front = front->next，O(1) 搞定。 所以，队头必须设在链头！

【四】正确答案 A

第15题：用链式存储方式的队列进行删除操作时需要() A. 仅修改头指针 B. 仅修改尾指针 C. 头尾指针都要修改 D. 头尾指针可能都要修改

【一】题目考察什么知识点 链式队列出队操作的边界条件（408代码题极易丢分点）。

【二】解题思路分析 很多人以为出队就是 front = front->next，只改头指针就行。但命题人最喜欢考的就是“临界状态”——当队列被删空的时候。

【三】逐步推导过程

  • 一般情况：队列有多个元素，出队只需修改 front，不影响 rear。
  • 特殊情况（临界点）：队列中只剩下最后一个元素。此时 front 和 rear 指向同一个结点。把这个结点 free 掉后，不仅 front 要变成 NULL，rear 也绝对不能继续指着那块被释放的废弃内存（变成野指针），必须同时执行 rear = NULL。 因此，头尾指针可能都要修改。

【四】正确答案 D

第16题：在一个链队列中,假设队头指针为front,队尾指针为rear, x所指向的元素需要入队,则需要执行的操作为() A. front=x, front=front->next B. x->next=front->next, front=x C. rear->next=x, rear=x D. rear->next=x, x->next=NULL, rear=x

【一】题目考察什么知识点 链队列的入队（尾插法）标准指针修改序列。

【三】逐步推导过程 队列入队发生在队尾 rear。

  1. 先把新结点 x 挂在当前的尾巴后面，让队伍接长：rear->next = x;
  2. 因为 x 变成了新的队伍末尾，它的后面没有任何人了，保险起见应该彻底切断悬念：x->next = NULL;
  3. 最后，将尾指针的“名号”正式移交给 x 结点：rear = x; D 选项的逻辑最为严谨完整。C 选项缺少了置空操作，如果 x 原本带有脏数据，会导致不可预知的错误。

【四】正确答案 D

第17题：假设循环单链表表示的队列长度为n,队头固定在链表尾,若只设头指针,则进队操作的时间复杂度为() A. O(n) B. O(1) C. O(n2) D. O(nlog2​n)

【一】题目考察什么知识点 循环单链表的“名实不副”陷阱及时间复杂度评估。

【二】解题思路分析 这道题是个文字游戏。先搞清楚两个概念：

  1. 队列的队头/队尾：出队的地方叫队头，进队的地方叫队尾。
  2. 链表的表头/表尾：头指针指向的地方叫表头。 题目说：“队头固定在链表尾”。也就是说，出队在链表尾，那么进队只能在链表头！

【三】逐步推导过程 现在我们要进行“进队操作”，也就是要在链表头插入一个新结点。 虽然有头指针可以直接找到表头，但别忘了，这是循环单链表！ 循环单链表在表头插入新节点后，必须修改链表尾结点的 next 指针，让它重新咬住这个新的头结点！ 但是题目说“只设头指针”，你手里没有尾指针。你怎么找链表尾？你只能顺藤摸瓜绕整整一圈跑 n−1 步才能找到它！ 所以进队的时间复杂度是 O(n)。

【四】正确答案 A

【五】易错点总结 很多人看到“进队在链表头”，又有“头指针”，就秒选 O(1)。殊不知循环单链表的头插法必须牵动尾巴，没有尾指针就必死无疑。

第18题：假设输入序列为1,2,3,4,5,利用两个队列进行出入队操作,不可能输出的序列是( ) A. 1, 2, 3, 4, 5 B. 5, 2, 3, 4, 1 C. 1, 3, 2, 4, 5 D. 4, 1, 5, 2, 3

【一】题目考察什么知识点 队列FIFO特性的组合数学推导（多个队列排序原理）。

【二】如何通俗理解（生活化类比） 队列没有后门可以走。把一个长队伍分成两个小队伍，最后汇合出的总队伍，必然是由两个依然按原有先后顺序排列的子序列拼接起来的。

【三】逐步推导过程 这是一个有意思的进阶结论：一个序列能用 k 个队列排出来，当且仅当这个序列中最长递减子序列的长度不超过 k。 我们要在选项中找“最长递减子序列长度达到 3”的那个。

  • A项：全递增，递减子序列长 1。
  • C项：1, 3, 2, 4, 5。递减的是 3 → 2。长度为 2。（可用 2 个队列实现：队列A出1、3、4、5，队列B出2）。
  • D项：4, 1, 5, 2, 3。最长递减为 4 → 2 或 5 → 3 等。长度均为 2。
  • B项：5, 2, 3, 4, 1。最长递减子序列为 5 → 4 → 1 或 5 → 2 → 1。长度居然达到了 3！ 也就是说，要想吐出 5, 4, 1 这个倒序，意味着 4 必须比 5 晚出，1 必须比 4 晚出，而它们在进队时是 1先进、4次之、5最后进的。这三个互相矛盾的元素必须分在 3 个独立的队列里！区区两个队列根本做不到。

【四】正确答案 B

第19题：若以1,2,3,4作为双端队列的输入序列,则既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列是( ) A. 1, 2, 3, 4 B. 4, 1, 3, 2 C. 4, 2, 3, 1 D. 4, 2, 1, 3

【一】题目考察什么知识点 双端队列（Deque）输入受限与输出受限的合法序列判定。

【二】解题思路分析 此类题目如果靠现场脑补，极容易崩溃。我们用判错法则：

  1. 输出受限的双端队列（两端进，一头出）：既然只能从一头出，那它弹出的必定是从一端向另一端的扫荡。这意味着：先进入的元素必定被后进入的元素“包夹”，不可能出现中间插队。
  2. 输入受限的双端队列（一头进，两头出）：只能从一端塞进去，它本质上就像是在两边生长的竹子。

【三】逐步推导过程 重点审视 C 选项：4, 2, 3, 1。

  • 先看输出受限（两头进，一头出）：1 最先进入，2 第二个进入。所以在最终排好的队列里，1 和 2 必须是死死挨着的（2 要么糊在 1 左边，要么在 1 右边）。但在 C 选项的出队序列中，1 和 2 中间硬生生隔了一个 3！3 是后进来的，怎么可能塞到 1 和 2 的里面去？所以输出受限做不到！
  • 再看输入受限（一头进，两头出）：若要最先出 4，必须把 1、2、3、4 全部塞进去压实（此时内部为 [1, 2, 3, 4]）。从两端挑，出 4 后剩 [1, 2, 3]。此时两端暴露的是 1 和 3，你根本无法第二个抽出被死死夹在中间的 2！所以输入受限也做不到！

【四】正确答案 C

【七】如何举一反三 记住这个经典结论：在四个元素（1,2,3,4）的双端队列考题中，4, 2, 3, 1 永远是做不到的“绝缘体”。碰到这种题，先抓 1, 2 是否被隔离来秒杀！

第20题：【2010统考真题】某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。若元素a,b,c,d,e依次入此队列后再进行出队操作,则不可能得到的出队序列是( ) A. b, a, c, d, e B. d, b, a, c, e C. d, b, c, a, e D. e, c, b, a, d

【一】题目考察什么知识点 输出受限的双端队列特性（真题实战）。

【二】如何通俗理解（生活化类比） 这就是我们刚才讲的**“奥利奥饼干法则”**（夹心是从里往外一层层糊上去的）。 a 最先进去，就是最里面的夹心。b 第二个进去，它只能糊在 a 的左边或右边，所以 a 和 b 必定挨着！ 同理，c 糊上去的时候，只能糊在 a 和 b 这个整体的外侧，绝不可能插入到 a 和 b 的中间去！

【三】逐步推导过程 顺着“后进来的只能包裹在外面，不能插在中间”的逻辑，我们看选项里的奥利奥序列：

  • A项：b, a 挨着；c 在外侧；d 在更外侧；e 在最外侧。完全没问题！
  • B项：b, a 挨着；c 在右；d 在左；e 在最右。没问题！
  • D项：c, b, a 连着；d 在右，e 在左。没问题！
  • C项：d, b, c, a, e。寻找 a 和 b，在序列中，b 和 a 的中间居然隔了一个 c！按照奥利奥法则，c 晚于 a,b 进来，必须糊在外面，怎么可能钻进 a 和 b 的中间？绝对不可能。

【四】正确答案 C

第3章 栈、队列和数组 - 3.3 栈与队列的应用 (Part 1)

第1题：栈的应用不包括() A. 递归 B. 表达式求值 C. 括号匹配 D. FIFO 页面替换算法

【一】题目考察什么知识点 考察栈和队列的经典应用场景区分。

【二】如何通俗理解（生活化类比） 栈是“死胡同”，适合处理“嵌套”、“回溯”或“就近消除”的问题（比如你穿衣服，最后穿的外套必须最先脱下来）。队列是“单行道”，适合处理“排队”、“先来后到”的问题。

【三】逐步推导过程

  • 递归调用需要保存上下文，层层深入再层层返回，符合 LIFO（栈）。
  • 表达式求值和括号匹配都需要将未处理的符号暂存，遇到匹配或高优先级时就近计算消除，符合 LIFO（栈）。
  • 选项 D 中的 FIFO 意思是 First In First Out（先进先出），这四个字母直接把“队列”的名字写在脸上了！操作系统中的 FIFO 页面置换算法显然使用的是队列结构。

【四】正确答案 D

_第2题：表达式 $a(b+c)-d$ 的后缀表达式是( )_* A. abcd *+- B. abc+d- C. abc+d- D. -+*abcd

【一】题目考察什么知识点 必考考点：中缀表达式转后缀表达式（逆波兰表达式）。

【二】如何通俗理解 后缀表达式就是把运算符放到它要计算的两个数字的“屁股后面”，而且完全不需要括号！人类看中缀，计算机看后缀。

【三】逐步推导过程 严格按照人类计算算术题的先后顺序进行转换：

  1. 先算括号里的加法 (b+c)，将加号移到后面，后缀变成：bc+。
  2. 再算乘法 a∗(bc+)，将乘号移到这一整块的后面，后缀变成：a(bc+)*，也就是 abc+*。
  3. 最后算减法 (abc+∗)−d，将减号移到最后，后缀变成：abc+*d-。

【四】正确答案 B

第3题：下面()用到了队列。 A. 括号匹配 B. 表达式求值 C. 递归 D. 缓冲区

【一】题目考察什么知识点 队列的实际应用场景。

【三】逐步推导过程 A、B、C 是数据结构里著名的“栈的三大经典应用”。 D选项的“缓冲区”（如键盘输入缓冲区、打印机数据缓冲区），目的是为了缓解高速设备和低速设备之间的速度不匹配。为了保证数据不乱序，必须遵守“先到达的数据先被处理”的原则，因此必须用队列。

【四】正确答案 D

第4题：利用栈求表达式的值时,设立运算数栈OPEN。假设OPEN只有两个存储单元,则在下列表达式中,不会发生溢出的是() A. A−B∗(C−D) B. (A−B)∗C−D C. (A−B∗C)−D D. (A−B)∗(C−D)

【一】题目考察什么知识点 后缀表达式计算机求值时的“操作数栈”深度计算。这是极其硬核的模拟题。

【二】解题思路分析 计算机在计算时：遇到操作数就压栈；遇到运算符，就从栈顶弹出两个数，算完结果再把这个结果压回栈中。我们需要找出哪个表达式在计算过程中，栈里同时积压的操作数不超过2个。

【三】逐步推导过程 我们先把它们转化为后缀表达式，再模拟压栈：

  • A项后缀：A B C D - * -。连续压入A、B、C、D四个数，栈深达到4！溢出。

  • B项后缀：A B - C * D -。

    1. 压A、压B（深2）。
    2. 遇-，弹B弹A，结果R1压栈（深1）。
    3. 压C（深2）。
    4. 遇*，弹C弹R1，结果R2压栈（深1）。
    5. 压D（深2）。
    6. 遇-，弹D弹R2，算出最终结果。 全程最大深度只有2，不溢出！

  • C项后缀：A B C * - D -。连续压A、B、C（深3）！溢出。

  • D项后缀：A B - C D - *。压A、B（深2），遇-算结果R1（深1）；接着压C、压D（深3）！溢出。

【四】正确答案 B

【七】如何举一反三 栈的深度取决于“连续不被计算的操作数”的个数。算式中的括号越靠前、越早进行归约计算，积累在栈里的未处理数字就越少，需要的栈空间也就越小。

第5题：执行完下列语句段后,i的值为( )

C

1
2
3
4
5
int f(int x) {
    return ((x>0) ? x*f(x-1) : 2);
}
int i;
i = f(f(1));

A. 2 B. 4 C. 8 D. 无限递归 (假定D项)

【一】题目考察什么知识点 递归函数的代码追踪计算。

【三】逐步推导过程 遇到函数嵌套，必须从里向外“剥洋葱”：

  1. 先算最内层的 f(1)： 传入 x=1。条件 1>0 成立，执行 1 * f(1-1)，即 1 * f(0)。 接着算 f(0)：条件 0>0 不成立，执行冒号后面的分支，返回 2。 所以，f(1) = 1 * 2 = 2。
  2. 再算外层 f( f(1) )，即 f(2)： 传入 x=2。条件 2>0 成立，执行 2 * f(2-1)，即 2 * f(1)。 因为刚才已经算出 f(1) = 2。 所以，f(2) = 2 * 2 = 4。 最终 i 的值为 4。

【四】正确答案 B

第6题：设有如下递归函数,则计算F(8)需要调用该递归函数的次数为( )

C

1
2
3
4
int F(int n){
    if (n<=3) return 1;
    else return F(n-2) + F(n-4) + 1;
}

A. 7 B. 8 C. 9 D. 10

【一】题目考察什么知识点 递归调用树（Call Tree）的结点总数计算。

【三】逐步推导过程 我们在草稿纸上画出一棵“调用树”，每个分支代表一次函数调用（别忘了把最初的 F(8) 也算上一次）：

  1. 第一层：调用 F(8) （共 1 次）。

  2. 第二层：F(8) 内部调用了 F(6) 和 F(4) （共 2 次）。

  3. 第三层：

    • 左边的 F(6) 调用了 F(4) 和 F(2)。
    • 右边的 F(4) 调用了 F(2) 和 F(0)。 （共 4 次）。

  4. 第四层：

    • 第三层左边产生的那个 F(4)，会继续调用 F(2) 和 F(0)。（共 2 次）。
    • 注意：所有传入参数 n≤3 的调用（如 F(2) 和 F(0)），都会直接触发 return 1，不再向下产生新的调用分支。

盘点所有调用的框框：1（第一层）+ 2（第二层）+ 4（第三层）+ 2（第四层）= 9 次。

【四】正确答案 C

第7题：设有如下递归函数,在func(func(5))的执行过程中,第4个被执行的func函数是( )

C

1
2
3
4
int func(int x) {
    if (x<=3) return 2;
    else return func(x-2) + func(x-4);
}

A. func(2) B. func(3) C. func(4) D. func(5)

【一】题目考察什么知识点 递归执行的先后时序流（本质是树的先序遍历顺序）。

【二】解题思路分析 函数调用必须彻底算完里面的，才能算外面的。在计算一个长算式 func(A) + func(B) 时，程序一定会先死磕算完左边的 func(A)，再回头去算右边的 func(B)。

【三】逐步推导过程 整个执行流如下：

  • 第1个执行：程序启动，先进入内层函数 func(5) 本身。
  • func(5) 走到 return 处，要求计算 func(5-2) 和 func(5-4)。它会优先进入左边的分支。
  • 第2个执行：进入 func(3)。它满足 x≤3，直接返回 2 退出。
  • 左边算完了，func(5) 接着进入右边的分支。
  • 第3个执行：进入 func(1)。它满足 x≤3，直接返回 2 退出。
  • 此时，内层的 func(5) 彻底执行完毕，返回了 2+2=4。
  • 程序将这算出来的 4，丢进最外层的函数 func( ... ) 里。
  • 第4个执行：外层的 func(4) 被唤醒并开始执行。

【四】正确答案 C

第8题：对于一个问题的递归算法求解和其相对应的非递归算法求解,() A. 递归算法通常效率高一些 B. 非递归算法通常效率高一些 C. 两者相同 D. 无法比较

【一】题目考察什么知识点 递归算法与非递归算法（迭代算法）的时空效率宏观对比。

【二】如何通俗理解 递归就像是公司里层层向下派发任务，做完了再层层向上汇报，中间有很多“沟通成本”（不断地压栈、出栈、保存现场）。而非递归（迭代）就像是老板自己拿个小本本一口气从头干到尾，省去了中间层层汇报的繁文缛节。

【三】逐步推导过程 递归算法在底层运行中，需要极其频繁地分配栈帧、保存寄存器状态、恢复现场，其空间复杂度和时间常数开销都比较大。而非递归算法通常直接使用循环结构，避免了函数调用的开销，因此在计算机实际执行时，非递归算法的效率通常更高。

【四】正确答案 B

第9题：执行函数时,其局部变量一般采用()进行存储。 A. 树形结构 B. 静态链表 C. 栈结构 D. 队列结构

【一】题目考察什么知识点 计算机底层的内存布局与函数调用模型（Call Stack）。

【三】逐步推导过程 函数调用具有“后调用、先返回”的特性。当函数A调用函数B时，A的局部变量必须先冻结并保存起来；等B执行完返回后，A再恢复执行。这种嵌套的、后进先出的逻辑，完美契合栈结构的特性。在操作系统中，这块专门用于保存函数局部变量、参数和返回地址的内存区域，就被称为“栈区（Stack）”。

【四】正确答案 C

第10题：执行()操作时,需要使用队列作为辅助存储空间。 A. 查找散列(哈希)表 B. 广度优先搜索图 C. 前序(根)遍历二叉树 D. 深度优先搜索图

【一】题目考察什么知识点 栈与队列在经典算法中的固定搭配结构。

【三】逐步推导过程

  • 广度优先搜索（BFS）：需要像水波纹一样一层层向外扩展，“先发现的顶点，它的邻居也要先被访问”。这属于典型的“先进先出”逻辑，必须依赖队列。
  • 深度优先搜索（DFS）和二叉树的前序遍历：需要“一条路走到黑，走不通再退回来”，这属于“后进先出”的回溯思想，依赖的是栈（不管是系统调用栈还是自己写的辅助栈）。
  • 查找散列表：辅助空间一般是数组或链表。

【四】正确答案 B

第3章 栈、队列和数组 - 3.3 栈与队列的应用 (Part 2: 表达式与真题)

第11题：下列说法中,正确的是( ) A. 消除递归不一定需要使用栈 B. 对同一输入序列进行两组不同的合法入栈和出栈组合操作,所得的输出序列也一定相同 C. 通常使用队列来处理函数或过程调用 D. 队列和栈都是运算受限的线性表,只允许在表的两端进行运算

+4

【一】题目考察什么知识点 综合考察栈和队列的特性及应用场景。

【二】解题思路分析 逐个排雷。关键在于理解递归底层的本质，以及线性表受限的具体含义。

【三】逐步推导过程

  • B项：错。比如输入 1, 2, 3，如果是全进全出，序列是 3, 2, 1；如果是进一个出一个，序列是 1, 2, 3。显然不同。
  • C项：错。函数调用是典型的后进先出（LIFO）结构，必须用栈来保存上下文帧，而不是队列。
  • D项：错。“只允许在表的两端进行运算”是对队列和双端队列的描述。栈只能在表的一端（栈顶）进行运算，另一端（栈底）是封闭的。
  • A项：对。消除递归（把递归转为非递归迭代）虽然通常会借用辅助栈，但并不是绝对的！比如尾递归，就可以直接优化为简单的 while 循环变量更新，完全不需要使用栈。

【四】正确答案 A

第12题：【2009统考真题】为解决计算机主机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区, 主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( ) A. 栈 B. 队列 C. 树 D. 图

+4

【一】题目考察什么知识点 队列的实际应用（缓冲区管理）。

【二】如何通俗理解（生活化类比） 主机像是一个打字极快的高手（不断产生任务），打印机像是一个慢吞吞的老爷爷（慢慢处理任务）。为了不让高手干等，我们需要一个“排队等候区”。既然是排队，那肯定要遵守“先交上来的文件先打印”的规矩，这就是妥妥的先进先出（FIFO）。

【三】逐步推导过程 凡是涉及到资源竞争、速度不匹配、需要“先来后到”排队处理的，在计算机底层（如 CPU 任务调度、键盘输入缓冲区、打印机缓冲区）一律采用队列结构。

【四】正确答案 B

第13题：【2012统考真题】已知操作符包括“+”“-”“”“/”“(”和“)”。将中缀表达式 $a+b-a((c+d)/e-f)+g$ 转换为等价的后缀表达式ab+acd+e/f-*-g+时,用栈来存放暂时还不能确定运算次序的操作符。栈初始时为空时,转换过程中同时保存在栈中的操作符的最大个数是( ) A. 5 B. 7 C. 8 D. 11

+4

【一】题目考察什么知识点 极度硬核：中缀转后缀表达式的计算机底层算法（操作符栈深度模拟）。

【二】解题思路分析 这题不需要管操作数（a, b, c），我们只盯着操作符栈。 进出栈铁律：

  1. 遇到 ( 直接压栈。
  2. 遇到 ) 持续出栈直到弹出 (。
  3. 遇到普通符号，一直弹出栈里优先级“大于或等于”它的符号，直到栈顶符号优先级“小于”它（或者遇到 (），然后再把自己压栈。

【三】逐步推导过程（请在草稿纸上跟我一起画） 扫描表达式：a + b - a * ( ( c + d ) / e - f ) + g

  1. +：进栈。栈内：[+] （深度 1）
  2. -：遇到减号，栈顶是 +，平级，弹出 +，压入 -。栈内：[-] （深度 1）
  3. *：乘号优先级高于减号，直接压栈。栈内：[-, *] （深度 2）
  4. (：无脑压栈。栈内：[-, *, (] （深度 3）
  5. (：无脑压栈。栈内：[-, *, (, (] （深度 4）
  6. +：直接压入 ( 上方。栈内：[-, *, (, (, +] （深度 5！）
  7. )：消除上一层的括号，弹出 + 和 (。栈内退回：[-, *, (] （深度 3）
  8. /：压入 ( 上方。栈内：[-, *, (, /] （深度 4）
  9. -：减号优先级低于除号，弹出 /，压入 -。栈内：[-, *, (, -] （深度 4）
  10. )：消除括号，弹出 - 和 (。栈内退回：[-, *] （深度 2）
  11. +：加号优先级低，把 * 弹走，把栈底的 - 弹走，自己压栈。栈内：[+] （深度 1）

纵观全局，在扫描到 c+d 的加号时，栈内容纳了 -, *, (, (, +，达到历史最高深度：5！

【四】正确答案 A

【七】如何举一反三 如果怕做错，就找表达式里嵌套括号最深、且前面累积了乘除法的地方。在这个地方，被暂存在栈里的操作符肯定是最多的。

第14题：【2014统考真题】假设栈初始为空,将中缀表达式: a/b+(c∗d−e∗f)/g 转换为等价的后缀表达式的过程中,当扫描到f时,栈中的元素依次是( ) A. +(- B. +(- C. /+(- D. /+-*

+4

【一】题目考察什么知识点 中缀转后缀操作符栈的过程定格“快照”。

【三】逐步推导过程 我们同样用上面的铁律，一步步推导，直到遇到字母 f 为止： 表达式：a / b + ( c * d - e * f ) / g

  1. /：进栈。栈：[/]
  2. +：加号优先级小于除号，弹出 /，压入 +。栈：[+]
  3. (：无脑压栈。栈：[+, (]
  4. *：压栈。栈：[+, (, *]
  5. -：减号优先级低于乘号，弹出 *，压入 -。栈：[+, (, -]
  6. *：乘号优先级高于减号，压栈。栈：[+, (, -, *] 接下来扫描到操作数 f！此时快照定格，栈内从底到顶的元素依次是：+、(、-、*。

【四】正确答案 B

第15题：【2015统考真题】已知程序如下: 1 int S(int n) 2 { return (n<=0)? 0: s(n-1)+n;} 3 void main() 4 { cout<<S(1);} 程序运行时使用栈来保存调用过程的信息,自栈底到栈顶保存的信息依次对应的是() A. main()→S(1)→S(0) B. S(0)→S(1)→main() C. main()→S(0)→S(1) D. S(1)→S(0)→main()

+2

【一】题目考察什么知识点 计算机底层原理：函数调用栈（Call Stack）的压栈顺序。

【二】如何通俗理解 调用函数就像是“请人帮忙”。 main() 是大老板，他干活干到一半，遇到了 S(1)，于是大老板的活儿停下来（压入栈底），去等 S(1) 算结果。 S(1) 算到一半，需要用到 S(0) 的结果，于是 S(1) 的活儿也停下来（压在老板上面），去等 S(0) 算结果。 此时此刻，在这个等候队伍（栈）里，最底下垫着的是最早被挂起的 main()，中间是 S(1)，最上面正在火热执行的是 S(0)。

【三】逐步推导过程

  1. 操作系统首先分配空间并执行主函数 main()。main() 入栈，位于栈底。
  2. main() 中调用了 S(1)。现场被保护，S(1) 及其局部变量入栈。
  3. S(1) 在执行 S(1-1) + 1 的时候，发起了对 S(0) 的调用。S(1) 现场保护，S(0) 入栈。
  4. 此时达到最深调用，自栈底到栈顶依次是：main() -> S(1) -> S(0)。

【四】正确答案 A

第16题：【2016统考真题】设有如下图所示的火车车轨，入口到出口之间有 n 条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为 1∼9 的9列列车，驶入的次序依次是8, 4, 2, 5, 3, 9, 1, 6, 7。若期望驶出的次序依次为 1∼9，则n至少是( ) A. 2 B. 3 C. 4 D. 5

【一】题目考察什么知识点 考察队列（先进先出 FIFO）在实际调度问题中的应用，以及贪心算法思想。

【二】如何通俗理解（生活化类比） 火车道是单向行车的（从左到右），这意味着如果一辆火车停在轨道上，后面跟进来的火车只能排在它左边（它的屁股后面）。出口在最右边，所以最右边的火车必须最先出去。 既然我们希望出去的顺序是按 1,2,3…9 递增的，那就意味着：同一条轨道上，停在右边的（先进去的）火车，编号必须小于停在左边的（后进去的）火车。否则，大号的火车就会挡住小号火车的路，导致小号火车出不来！

【三】解题思路分析 这其实是求解“队列划分”问题。 规则：新来的火车 x 驶入某条轨道时，该轨道的队尾（最左端）火车编号必须小于 x。如果所有现存轨道的队尾都大于 x，那就只能为 x 开辟一条新的空轨道。 贪心策略：为了尽可能节省轨道，新来的火车应该排在**“队尾编号小于它，且最大”**的那条轨道后面。

【四】逐步推导过程 列车驶入序列：8, 4, 2, 5, 3, 9, 1, 6, 7

  • 8 来了：无轨道，开新轨 → 轨道①：[8]
  • 4 来了：比8小，不能排在8后面（否则8先出），开新轨 → 轨道②：[4]
  • 2 来了：比8和4都小，开新轨 → 轨道③：[2]
  • 5 来了：比4大，可以排在4后面 → 轨道②变为：[4, 5]
  • 3 来了：比2大，可以排在2后面 → 轨道③变为：[2, 3]
  • 9 来了：比8大，可以排在8后面 → 轨道①变为：[8, 9]
  • 1 来了：比 9, 5, 3 都小，只能开新轨 → 轨道④：[1]
  • 6 来了：比 5 大，排在 5 后面 → 轨道②变为：[4, 5, 6]
  • 7 来了：比 6 大，排在 6 后面 → 轨道②变为：[4, 5, 6, 7]

最终排布结果： 轨道①：[8, 9] 轨道②：[4, 5, 6, 7] 轨道③：[2, 3] 轨道④：[1] 综上所述，最少需要 4 条轨道。

【五】正确答案 C

【六】错误选项为什么错 很多人会把这道题当成“栈”来做（以为是火车进站调度），从而算出错误的递减子序列长度。一定要死死盯住题干中的**“行进方向均为从左至右”**，这是妥妥的队列！

第17题：【2017统考真题】下列关于栈的叙述中,错误的是( ) I. 采用非递归方式重写递归程序时必须使用栈 II. 函数调用时，系统要用栈保存必要的信息 III. 只要确定了入栈次序，即可确定出栈次序 IV. 栈是一种受限的线性表，允许在其两端进行操作 A. 仅I B. 仅I、II、III C. 仅I、III、IV D. 仅II、III、IV

+4

【一】题目考察什么知识点 栈的综合概念与底层应用判定。

【二】逐步推导过程

  • I. 错。 绝大多数递归（如树的先中后序遍历）转非递归确实需要辅助栈，但并非所有！例如“尾递归”（像求阶乘、斐波那契数列的迭代写法），直接用几个变量写个 while 循环就搞定了，根本不需要栈。含有“必须”二字的选项通常有坑。

  • II. 对。 计算机底层的 Call Stack（调用栈）就是专门干这个的，用来保存局部变量和返回地址。

  • III. 错。 前面咱们做过那么多卡特兰数的题， n 个元素确定的入栈次序，有 n+11​C2nn​ 种合法的出栈次序！因为你可以“边进边出”，随时打断。

  • IV. 错。 栈只能在**一端（栈顶）**进行操作！可以在两端操作的叫“双端队列”。 综上，错误的叙述是 I、III、IV。

【三】正确答案 C

第18题：【2018统考真题】若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作: 1) 从S1中依次弹出两个操作数a和b 2) 从S2中弹出一个运算符 op 3) 执行相应的运算 b op a 4) 将运算结果压入S1中 假定S1中的操作数依次是5, 8, 3, 2 (2在栈顶)，S2中的运算符依次是 *, -, + (+在栈顶)。调用3次 F()后，S1 栈顶保存的值是( ) A. -15 B. 15 C. -20 D. 20

+4

【一】题目考察什么知识点 表达式求值底层算法的纯手工模拟。

【二】解题思路分析 这是408大题手写代码的核心逻辑！一定要注意操作数的先后顺序！ 题干说“依次弹出两个操作数a和b”，意味着 a 是最先弹出来的（原栈顶），b 是第二个弹出来的（原次栈顶）。 执行的运算是 b op a（次栈顶 op 栈顶）。这一点对于减法和除法来说是致命的，一旦搞反，结果天差地别。

+1

【三】逐步推导过程 初始状态（从底到顶）： S1: [5, 8, 3, 2] S2: [*, -, +]

第1次调用 F()： * 弹出 a = 2，弹出 b = 3。 * 弹出 op = +。 * 计算 b op a → 3 + 2 = 5。 * 结果 5 压入 S1。

+4

  • 当前栈状态：S1: [5, 8, 5]，S2: [*, -]。

第2次调用 F()： * 弹出 a = 5，弹出 b = 8。 * 弹出 op = -。 * 计算 b op a → 8 - 5 = 3。（如果你不小心算成了 5 - 8，这题就废了！） * 结果 3 压入 S1。

+3

  • 当前栈状态：S1: [5, 3]，S2: [*]。

第3次调用 F()： * 弹出 a = 3，弹出 b = 5。 * 弹出 op = *。 * 计算 b op a → 5 * 3 = 15。 * 结果 15 压入 S1。 * 当前栈状态：S1: [15]，S2 空。 最终 S1 栈顶保存的值是 15。

+4

【四】正确答案 B

_第19题：【2024统考真题】与表达式 $x+y(z-u)/v$ 等价的后缀表达式是( )_* A. xyzu−∗v/+ B. xyzu−v/∗+ C. +x/∗y−zuv D. +x∗y/−zuv

【一】题目考察什么知识点 中缀表达式向后缀表达式的等价转换（这也是最近的一道 2024 年统考真题，证明了这个考点的经久不衰）。

【二】解题思路分析（独家“画树法”或“加括号法”） 我们可以完全按照人类的算术运算优先级，一层一层地把运算符“往后挪”。

【三】逐步推导过程 原表达式：x+y∗(z−u)/v

第一步：算优先级最高的括号里面 (z−u)。 将减号移到后面，变成了子表达式：zu−。 原式相当于变成了：x+y∗[zu−]/v

第二步：乘除同级，从左往右算。先算乘法 y∗[zu−]。 将乘号移到这一整块的后面，变成了：yzu−∗。 原式相当于变成了：x+[yzu−∗]/v

第三步：算除法 [yzu−∗]/v。 将除号移到屁股后面，变成了：yzu−∗v/。 原式相当于变成了：x+[yzu−∗v/]

第四步：最后算加法 x+[yzu−∗v/]。 将加号移到这所有东西的最后面，大功告成：xyzu−∗v/+。

对照选项，完美匹配 A。

【四】正确答案 A

408选择题数据结构
http://cathylove47.github.io/2026/03/19/408选择题数据结构/
作者
cathy
发布于
2026年3月19日
许可协议