CSP-J/S 历年 STL 容器初赛客观题专项（2009—2025）

共 34 道客观小题，整理自 2009—2025 年 NOIP 普及/提高组与 CSP-J/S 第一轮中与 STL 容器、栈、队列、堆及相关应用直接相关的考点。题面已做适度整理改写，核心考点与年份标记保留。

本题为 一个 HydroOJ 客观题题目，完成全部小题后统一提交。

[2009 J] 栈的合法出栈序列

基于 NOIP 2009 普及组初赛第 12 题整理改写。

元素按 F, E, D, C, B, A 的顺序依次压入同一个栈。压栈过程中允许随时执行出栈操作。下列哪一个序列 不可能 成为完整的出栈序列？

{{ select(1) }}

• E, D, C, F, A, B
• D, E, C, A, B, F
• C, D, F, E, B, A
• B, C, D, A, E, F

[2009 J] 栈与后缀表达式

基于 NOIP 2009 普及组初赛第 13 题整理改写。

中缀表达式 a*(b+c)-d 对应的后缀表达式是（ ）。

{{ select(2) }}

• abcd*+-
• abc+*d-
• abc*+d-
• -+*abcd

[2010 J] 已知首次出栈后的可能性

基于 NOIP 2010 普及组初赛第 15 题整理改写。

R1, R2, R3, R4, R5 按此顺序依次入栈，允许边入栈边出栈。若第一个出栈的元素确定为 R3，那么第五个出栈的元素 不可能 是（ ）。

{{ select(3) }}

• R1
• R2
• R4
• R5

[2011 J] BFS 常用的数据结构

基于 NOIP 2011 普及组初赛相关客观题整理改写。

在经典的广度优先搜索（BFS）实现中，为了按“先发现先处理”的顺序保存待扩展结点，最常使用的数据结构是（ ）。

{{ select(4) }}

• 链表
• 队列
• 栈
• 散列表

[2012 J] 当前栈状态与可能的入栈顺序

基于 NOIP 2012 普及组初赛第 12 题整理改写。

某栈初始为空。当前栈中从栈底到栈顶依次为 a, b, c，另有元素 d 已经出栈。下列哪一种入栈顺序可能产生该状态？

{{ select(5) }}

• a, d, c, b
• b, a, c, d
• a, c, b, d
• d, a, b, c

[2012 S] 根据当前栈状态反推入栈顺序

基于 NOIP 2012 提高组初赛栈相关客观题整理改写。本题为多选题。

某栈当前从栈底到栈顶依次为 a, b, c，并且元素 d 已经在此前出栈。若四个元素最初按某一固定顺序依次入栈，入栈过程中允许随时出栈，则下列哪些入栈顺序有可能产生上述状态？

{{ multiselect(6) }}

• a, b, c, d
• b, a, c, d
• a, c, b, d
• d, a, b, c

[2015 J/S] 连续栈操作后的栈顶

基于 NOIP 2015 普及组与提高组初赛中的同类栈题整理改写。

空栈 S 中的数据按 a, b, c, d, e, f 的顺序等待入栈。现在依次执行：

入栈、入栈、出栈、入栈、入栈、出栈

每次“入栈”都把尚未入栈的最前一个数据压入栈。执行完毕后，栈顶元素是（ ）。

{{ select(7) }}

• f
• c
• a
• b

[2017 J] 中缀表达式转后缀表达式

基于 NOIP 2017 普及组初赛第 12 题整理改写。

中缀表达式 a*(b+c)*d 对应的后缀表达式是（ ）。

{{ select(8) }}

• abcd*+*
• abc+*d*
• a*bc+*d
• b+c*a*d

[2017 J] 链式栈的入栈操作

基于 NOIP 2017 普及组初赛第 13 题整理改写。

设 hs 指向链式栈的栈顶结点，s 指向一个准备压入栈的新结点。若结点的后继指针域名为 next，正确的入栈操作是（ ）。

{{ select(9) }}

• hs->next = s;
• s->next = hs; hs = s;
• s->next = hs->next; hs->next = s;
• s->next = hs; hs = hs->next;

[2017 J] 判断不可能的出栈序列

基于 NOIP 2017 普及组初赛第 16 题整理改写。

元素 a, b, c, d, e, f, g 按此顺序依次入栈，入栈与出栈可以交替进行。下列哪一个序列不可能成为完整的出栈序列？

{{ select(10) }}

• a, b, c, d, e, f, g
• a, d, c, b, e, g, f
• a, d, b, c, g, f, e
• g, f, e, d, c, b, a

[2018 S] Catalan 数与合法出栈序列

基于 NOIP 2018 提高组初赛第 8 题整理改写。

关于第 n 个 Catalan 数 C_n 的常见计数意义，下列说法中 不正确 的是（ ）。

{{ select(11) }}

• C_n 等于含 n+1 个结点的不同二叉树形态数
• C_n 等于 n 对括号组成的合法括号序列数
• C_n 等于 n 个元素按固定顺序入栈时的合法出栈序列数
• C_n 等于凸 n+2 边形的三角剖分数

[2021 J] 入栈顺序固定时的非法出栈序列

基于 CSP-J 2021 第一轮第 5 题整理改写。

元素 a, b, c, d, e 按此顺序依次入栈，允许在过程中随时出栈。下列哪一个完整出栈序列是不合法的？

{{ select(12) }}

• a, b, c, d, e
• e, d, c, b, a
• b, a, c, d, e
• c, d, a, e, b

[2022 J] 固定入栈顺序的出栈判断

基于 CSP-J 2022 第一轮第 2 题整理改写。

把 6, 5, 4, 3, 2, 1 按此顺序依次压入一个初始为空的栈，期间允许随时出栈。下列哪一个序列不可能成为完整的出栈序列？

{{ select(13) }}

• 5, 4, 3, 6, 1, 2
• 4, 5, 3, 1, 2, 6
• 3, 4, 6, 5, 2, 1
• 2, 3, 4, 1, 5, 6

[2022 J] 栈与队列混合操作的最小容量

基于 CSP-J 2022 第一轮第 5 题整理改写。

空栈 S 和空队列 Q 共同处理 e1~e6。所有元素压入栈 S 的顺序固定为 e1,e2,e3,e4,e5,e6；每个元素必须先经过栈，再进入队列；队列最终出队顺序要求为：

e2, e4, e3, e6, e5, e1

在允许合理交错“入栈、出栈、入队、出队”的前提下，为完成该顺序，栈 S 至少需要多大的容量？

{{ select(14) }}

• 2
• 3
• 4
• 6

[2022 J] 栈与队列的基本性质

基于 CSP-J 2022 第一轮第 10 题整理改写。

关于栈、队列及其典型应用，下列说法中 不恰当 的是（ ）。

{{ select(15) }}

• 深度优先搜索常使用栈或递归调用栈
• 栈通常是后进先出，队列通常是先进先出
• 广度优先搜索常使用队列
• 栈与队列机制完全不同，因此不能用若干个栈来实现一个队列

[2022 J] vector 操作与因数枚举

基于 CSP-J 2022 第一轮第 35~39 题中的 vector 使用方式整理改写。

下面的程序希望把 n 的正因数按从小到大输出。small 用于保存不超过 sqrt(n) 的较小因数。

vector<int> small;
small.reserve((int)ceil(sqrt(n)));
int i;
for (i = 1; i * i < n; ++i) {
    if ( /* ① */ ) small.push_back(i);
}
for (int k = 0; k < (int)small.size(); ++k)
    cout << /* ② */ << ' ';
if ( /* ③ */ ) cout << /* ④ */ << ' ';
for (int k = (int)small.size() - 1; k >= 0; --k)
    cout << /* ⑤ */ << ' ';

① 应填（ ）。

{{ select(16) }}

• n % i == 0
• n % i == 1
• n % (i - 1) == 0
• n % (i - 1) == 1

② 应填（ ）。

{{ select(17) }}

• n / small[k]
• small[k]
• small[k] - 1
• n / (small[k] - 1)

③ 应填（ ）。

{{ select(18) }}

• (i - 1) * (i - 1) == n
• (i - 1) * i == n
• i * i == n
• i * (i - 1) == n

④ 应填（ ）。

{{ select(19) }}

• n - i
• n - i + 1
• i - 1
• i

⑤ 应填（ ）。

{{ select(20) }}

• n / small[k]
• small[k]
• small[k] - 1
• n / (small[k] - 1)

[2022 J] queue 与 BFS 染色

基于 CSP-J 2022 第一轮第 40~44 题整理改写。

下面的程序使用 queue<Point> 进行四方向洪水填充。请补全 ①~⑤。

bool valid(char img[8][8], Point p, int oldc, int newc) {
    int r = p.r, c = p.c;
    return 0 <= r && r < 8 && 0 <= c && c < 8
           && /* ① */ && img[r][c] != newc;
}

void fill(char img[8][8], Point cur, int newc) {
    queue<Point> q;
    q.push(cur);
    int oldc = img[cur.r][cur.c];
    /* ② */;

    while (!q.empty()) {
        Point p = q.front(); q.pop();
        Point nxt[4] = { /* ③ */, Point(p.r-1,p.c),
                         Point(p.r,p.c+1), Point(p.r,p.c-1) };
        for (auto x : nxt) {
            if (valid(img, x, oldc, newc)) {
                /* ④ */;
                /* ⑤ */;
            }
        }
    }
}

① 应填（ ）。

{{ select(21) }}

• img[r][c] == oldc
• img[r][c] != oldc
• img[r][c] == newc
• img[r][c] != newc

② 应填（ ）。

{{ select(22) }}

• img[cur.r+1][cur.c] = newc
• img[cur.r][cur.c] = newc
• img[cur.r][cur.c+1] = newc
• img[cur.r][cur.c] = oldc

③ 应填（ ）。

{{ select(23) }}

• Point(p.r, p.c)
• Point(p.r, p.c+1)
• Point(p.r+1, p.c)
• Point(p.r+1, p.c+1)

④ 应填（ ）。

{{ select(24) }}

• oldc = img[x.r][x.c]
• newc = img[x.r][x.c]
• img[x.r][x.c] = oldc
• img[x.r][x.c] = newc

⑤ 应填（ ）。

{{ select(25) }}

• q.push(x)
• q.push(p)
• q.push(cur)
• q.push(Point(8,8))

[2022 S] 带限制条件的出栈序列

基于 CSP-S 2022 第一轮第 3 题整理改写。

元素 a,b,c,d,e,f 按此顺序依次入栈，入栈与出栈允许交错，同时规定 不能连续执行 3 次出栈操作。下列哪一个完整出栈序列不可能出现？

{{ select(26) }}

• d, c, e, b, f, a
• c, b, d, a, e, f
• b, c, a, e, f, d
• a, f, e, d, c, b

[2023 J] 二维 vector 的下标边界

基于 CSP-J 2023 第一轮第 24 题涉及的二维 vector 下标问题整理改写。

程序中有：

vector<vector<int>> v(m + 1, vector<int>(n + 1, 0));
// ... 中间若干处理 ...
cout << v[m][n] << '\n';

若把最后一行的 v[m][n] 改成 v[n][m]，而程序并没有保证 m == n，以下判断最合适的是（ ）。

{{ select(27) }}

• 程序行为一定完全不变
• 程序只会输出另一个合法位置的值，不可能越界
• 程序一定立即异常退出
• 程序可能发生越界访问，从而出现未定义行为或异常

[2023 J] 后缀表达式还原

基于 CSP-J 2023 第一轮第 8 题整理改写。

后缀表达式

6 2 3 + - 3 8 2 / + * 2 ^ 3 +

对应的中缀表达式是（ ）。

{{ select(28) }}

• ((6-(2+3))*(3+8/2))^2+3
• 6-2+3*3+8/2^2+3
• (6-(2+3))*((3+8/2)^2)+3
• 6-((2+3)*(3+8/2))^2+3

[2023 S] 队列与常见数据结构性质

基于 CSP-S 2023 第一轮第 5 题整理改写。

关于常见数据结构与算法，下列说法中 不恰当 的是（ ）。

{{ select(29) }}

• 队列是一种典型的先进先出线性结构
• 构造 Huffman 树的主要目的，是实现图的深度优先搜索
• 哈希表常通过哈希函数把关键字映射到表中位置
• 二叉树中每个结点最多有两个孩子

[2024 J] 栈的出栈序列判断

基于 CSP-J 2024 第一轮第 13 题整理改写。

空栈中按 1,2,3,4,5,6 的顺序依次压入元素，允许边压栈边出栈。下列哪个序列不可能作为完整出栈序列？

{{ select(30) }}

• 6,5,4,3,2,1
• 1,6,5,4,3,2
• 2,4,6,5,3,1
• 1,3,5,2,4,6

[2024 S] FIFO 对应的数据结构

基于 CSP-S 2024 第一轮第 5 题整理改写。

若要求数据严格遵循“先进先出（FIFO）”的访问顺序，最合适的数据结构是（ ）。

{{ select(31) }}

• 栈
• 队列
• 普通顺序表（不附加访问规则）
• 二叉搜索树

[2024 S] priority_queue 的默认顺序

基于 CSP-S 2024 第一轮第 39 题涉及的 priority_queue<pair<int,int>> 用法整理改写。

在 Dijkstra 算法中，若使用默认的：

priority_queue<pair<int,int>> q;

希望 q.top() 优先得到 当前距离 d 更小 的结点 v，可利用默认大根堆对 pair 的字典序比较。下列入队写法最合适的是（ ）。

{{ select(32) }}

• q.push(make_pair(-d, v));
• q.push(make_pair(d, v));
• q.push(make_pair(v, d));
• q.push(make_pair(-v, d));

[2025 J] 栈与队列的联合模拟

基于 CSP-J 2025 第一轮第 15 题整理改写。

初始时整数栈 S 与整数队列 P 都为空。按顺序处理数组：

7, 5, 8, 3, 1, 4, 2

规则如下：

• 遇到奇数：把该数压入 S；
• 遇到偶数且 S 非空：弹出 S 的栈顶元素并把它加入队列 P；
• 遇到偶数且 S 为空：不做操作。

全部处理完成后，从队头到队尾，P 中元素为（ ）。

{{ select(33) }}

• 5, 1, 3
• 7, 5, 3
• 3, 1, 5
• 5, 1, 3, 7

[2025 S] 小根堆删除最小值后的堆顶

基于 CSP-S 2025 第一轮第 12 题整理改写。

向一个初始为空的小根堆中依次插入：

20, 12, 15, 8, 10, 5

随后连续执行两次“删除最小值”。此时堆顶元素是（ ）。

{{ select(34) }}

• 10
• 12
• 15
• 20