CSP-J 近15年栈队列链表真题专项｜教师答案解析

一、答案速查

1.B  2.C  3.B  4.D  5.A  6.B  7.B  8.A  9.D  10.B
11.B  12.B  13.C  14.B  15.A  16.B  17.C  18.B  19.D  20.D
21.A  22.A  23.C  24.C  25.D  26.D  27.B  28.A  29.A  30.B

二、逐题解析

第 1 题｜2011 NOIP 普及组｜答案 B

考点： 队列 / BFS

BFS 按“先发现、先扩展”的顺序处理结点，因此通常使用先进先出的队列。

第 2 题｜2011 NOIP 普及组｜答案 C

考点： 链表 / 复杂度

普通链表不支持按下标随机访问，最坏情况下需要从头到尾检查 n 个结点。

第 3 题｜2012 NOIP 普及组｜答案 B

考点： 队列概念

队列是 FIFO（First In First Out）；栈则是 LIFO。

第 4 题｜2012 NOIP 普及组｜答案 D

考点： 栈 / 入栈顺序

若先输入 d 并将其弹出，再依次输入 a、b、c，就能得到栈底到栈顶 a、b、c。其他顺序无法满足栈的后进先出约束。

第 5 题｜2012 NOIP 普及组｜答案 A

考点： 递归 / 栈

函数调用的参数、局部变量和返回信息通常由调用栈维护，递归过深会导致栈空间耗尽。

第 6 题｜2013 NOIP 普及组｜答案 B

考点： 栈概念

只能从同一端进出，且上面的元素先离开，体现了后进先出的栈。

第 7 题｜2014 NOIP 普及组｜答案 B

考点： 链表特点

链表通常需要沿 next 指针逐个访问，不能像数组 a[i] 一样进行 O(1) 随机访问。

第 8 题｜2015 NOIP 普及组｜答案 A

考点： 链表特点

链表的结点通过指针相连，访问第 k 个结点一般要从前向后走。

第 9 题｜2015 NOIP 普及组｜答案 D

考点： 链式存储

链表依靠指针表达逻辑次序，不要求物理地址连续。

第 10 题｜2015 NOIP 普及组｜答案 B

考点： 栈 / 手动模拟

a 入栈，b 入栈，b 出栈；c 入栈，d 入栈，d 出栈。此时栈内为 a、c，栈顶是 c。

第 11 题｜2017 NOIP 普及组｜答案 B

考点： 栈 / 后缀表达式

先得到 b c +，再与 a 相乘得到 a b c + *，最后与 d 相乘。

第 12 题｜2017 NOIP 普及组｜答案 B

考点： 链式栈 / 指针

新结点先指向旧栈顶，再让栈顶指针 hs 改为新结点 s。

第 13 题｜2017 NOIP 普及组｜答案 C

考点： 栈 / 出栈序列

在 C 中，d 出栈后栈顶仍是 c，不能越过 c 先弹出 b，因此该序列不合法。

第 14 题｜2018 NOIP 普及组｜答案 B

考点： 栈概念

这种“同一端进入、同一端离开”的结构就是栈。

第 15 题｜2018 NOIP 普及组｜答案 A

考点： 双向链表完善程序①

数组 a 用来保存“值 → 原位置”的映射，因此应记录 a[x]=i。

第 16 题｜2018 NOIP 普及组｜答案 B

考点： 双向链表完善程序②

初始链表按下标 1,2,...,n 排列，所以 i 的直接后继是 i+1。

第 17 题｜2018 NOIP 普及组｜答案 C

考点： 双向链表完善程序③

被删除结点的右邻居是 R[a[i]]，应修改这个右邻居的 L 指针。

第 18 题｜2018 NOIP 普及组｜答案 B

考点： 双向链表完善程序④

被删结点编号就是 a[i]，它原来的右邻居为 R[a[i]]。

第 19 题｜2018 NOIP 普及组｜答案 D

考点： 双向链表完善程序⑤

双向链表删除较小值后，R[i] 记录当前位置右边第一个仍保留的位置。

第 20 题｜2019 CSP-J 第一轮｜答案 D

考点： 链表特点

链表通常需要顺序访问，随机访问是数组的优势。

第 21 题｜2020 CSP-J 第一轮｜答案 A

考点： 链表特点

链表的第 k 个结点通常要沿指针寻找，不能直接 O(1) 随机访问。

第 22 题｜2020 CSP-J 第一轮｜答案 A

考点： 栈概念

只有一个操作端，体现栈的后进先出。

第 23 题｜2022 CSP-J 第一轮｜答案 C

考点： 栈 / 出栈序列

按栈顶约束模拟即可发现 C 无法实现。该题是典型的出栈序列判断。

第 24 题｜2022 CSP-J 第一轮｜答案 C

考点： 数组与链表

A、B 都不是本质区别；链表能按需动态申请结点，而普通静态数组大小通常预先确定。

第 25 题｜2022 CSP-J 第一轮｜答案 D

考点： 栈与队列

两个栈可以模拟一个队列，所以 D 的“无法实现”是错误的。

第 26 题｜2022 CSP-J 第一轮｜答案 D

考点： 双向循环链表

需要同时维护四条关系：s 的前驱/后继，以及原后继的 prev 和 p 的 next。

第 27 题｜2022 CSP-J 第一轮｜答案 B

考点： 栈 + 队列综合模拟

按目标出队顺序安排各元素出栈可得到最低峰值栈深为 3，因此最小容量为 3。

第 28 题｜2023 CSP-J 第一轮｜答案 A

考点： 链表头插

头插法必须让新结点先指向旧 head，再把 head 更新为新结点。

第 29 题｜2025 CSP-J 第一轮｜答案 A

考点： 栈 + 队列综合模拟

7、5 入栈；8 使 5 出栈入队；3、1 入栈；4 使 1 入队；2 使 3 入队，所以 P 为 5、1、3。

第 30 题｜2024 CSP-S 第一轮（加餐）｜答案 B

考点： 队列概念

FIFO 就是队列的定义。此题来自 CSP-S，但知识点属于 CSP-J 也应掌握的基础概念。