题目导航

林老师 · 客观题题库 · 专题 S04 栈·队列·递归与递推 · 复习强化

专题 S04 栈·队列·递归与递推 · 复习强化

100 题 · 每题对应一个知识细节 · 全部原创

真题
复刻

试卷编号ORIG-专题S04栈-队列-递归与递推-复习强化

题目总数108 题 · 100 分

试卷类型客观题

考生须知：
① 本卷共 9 大部分，合计 108 题 · 100 分，全部为客观题；
② 试卷右上角设有 「提交答卷」 与 「重置考试」 按钮，提交后系统自动判分并显示答题正确情况，请确认全部作答后再行提交；
③ 试卷不显示答案，提交后方可查看每题作答与正确答案的对照；
④ 答卷进度会保留在本地缓存中，刷新或再次打开仍可继续作答；
⑤ 本卷仅供学生练习使用；请勿用于其他用途；题面有问题请联系：i64coder@163.com。

判分报告

0 / 100 分

答对 · 得 0 分

答错 · 失 0 分

未作答

当前筛选下没有题目

壹

栈深入

12 QUESTIONS · 2 POINTS EACH

第 1 题 A1 未作答

空栈 $S$ ，对序列 a,b,c,d,e,f 依次执行：进栈、进栈、出栈、进栈、进栈、出栈。操作完成后栈底元素为（）。（2020 年 CSP-S 真题）

（1 分）

c

d

a

b

第 2 题 A2 未作答

空栈依次执行 push(1) push(2) pop() push(3) push(4) pop() pop()，此时栈中从栈底到栈顶为（）。

（1 分）

1

空

1 3

1 2

第 3 题 A3 未作答

元素 a,b,c,d,e,f 依次进栈，允许进栈退栈交替进行。下列不可能的出栈序列是（）。（2022 年 CSP-S 真题：不允许连续三次退栈）

（1 分）

dcebfa

cbdaef

bcaefd

afedcb

第 4 题 A4 未作答

出栈序列 fedcba（全逆序）要求进栈 $6$ 个元素后连续退栈 $6$ 次。如果约束"不允许连续三次退栈"，这个序列（）。

（1 分）

不可能实现——最后需要连续 $5$ 次退栈（ $f,e,d,c,b,a$ ），违反约束

只需改变进栈顺序

只需额外进栈一次

可以实现

第 5 题 A5 未作答

元素 e1~e6 依次进栈（允许交替退栈），出栈序列为 e2,e4,e3,e6,e5,e1。栈的容量至少为（）个。

（1 分）

$2$

$4$

$3$

$6$

第 6 题 A6 未作答

递归函数在计算机内部通过（）实现。

（1 分）

栈——每层递归调用压入一个栈帧（局部变量+返回地址），返回时弹出

堆

队列

链表

第 7 题 A7 未作答

main() 调用 f()、f() 调用 g()，此时调用栈从底到顶为（）。

（1 分）

f() g() main()

main() f() g()

只有 g()

g() f() main()

第 8 题 A8 未作答

函数 A 调用 B，B 调用 C，C 返回后 B 也返回，然后 A 调用 D。D 开始执行时栈中有（）个帧。

（1 分）

$3$

$4$

$1$

$2$

第 9 题 A9 未作答

用栈求中缀表达式 3 + 4 * 2 的值时，读到 * 需要先与栈顶 + 比较优先级，因为（）。

（1 分）

不需要比较

栈满了

乘法优先级高于加法，* 直接入栈；但如果栈顶是更高/同级运算符，需要先弹出计算——优先级决定弹不弹

所有运算符都要弹出

第 10 题 A10 未作答

表达式 a*(b+c)-d 的后缀表达式为（）。（2020 年 CSP-S 真题）

（1 分）

abcd*+-

abc*+d-

-*+abcd

abc+*d-

第 11 题 A11 未作答

后缀表达式 23*4+ 的值是（）。

（1 分）

$14$

$10$

$24$

$6$

第 12 题 A12 未作答

关于栈的说法，错误的是（）。

（1 分）

栈是后进先出（LIFO）结构

中缀转后缀需要运算符栈

栈只能在尾部插入，不能查看中间元素

递归调用使用系统栈

贰

队列深入

10 QUESTIONS · 2 POINTS EACH

第 13 题 B1 未作答

广度优先搜索（BFS）一定需要用到的数据结构是（）。（2020 年 CSP-S 真题）

（1 分）

队列

二叉树

哈希表

栈

第 14 题 B2 未作答

下面哪个数据结构最适合实现先进先出（FIFO）功能（）。（2024 年 CSP-S 真题）

（1 分）

栈

队列

二叉搜索树

线性表

第 15 题 B3 未作答

"实现撤销操作（最近做的最先撤销）"应使用（）；"实现排队叫号（先来先服务）"应使用（）。

（1 分）

栈；队列

都用栈

队列；栈

都用队列

第 16 题 B4 未作答

容量为 $5$ 的循环队列，front=3, rear=1，队列中有（）个元素。

（1 分）

$3$

$4$

无法确定

$2$

第 17 题 B5 未作答

容量为 $n$ 的循环队列，判满条件 (rear + 1) % n == front 意味着（）。

（1 分）

队列恰好装满 $n$ 个元素

队列溢出

队列空

队列装了 $n-1$ 个元素——牺牲一个格子来区分满和空

第 18 题 B6 未作答

队列初始为空，依次执行 enqueue(A) enqueue(B) dequeue() enqueue(C) dequeue()，此时队头和队尾分别是（）。

（1 分）

队头 B、队尾 C

队头 A、队尾 C

队头 C、队尾 C

队列为空

第 19 题 B7 未作答

用两个队列 Q1, Q2 模拟栈的 pop 操作（弹出最后入队的元素），正确做法是（）。

（1 分）

两个队列同时出队

直接从 Q1 出队

把 Q1 出队到只剩一个元素（全部转入 Q2），剩下的那个就是"栈顶"——然后交换 Q1 和 Q2 的角色

不可能实现

第 20 题 B8 未作答

优先队列（priority_queue）与普通队列的区别是（）。

（1 分）

普通队列按入队时间出队（FIFO）；优先队列按优先级出队——最高优先级的最先出

优先队列不能插入

没有区别

优先队列就是栈

第 21 题 B9 未作答

BFS 用队列实现的层序遍历，第 $k$ 层的点在队列中的特点是（）。

（1 分）

按编号排序

分散在整个队列

交替排列

连续排列——第 $k$ 层的所有点先入队，然后才轮到第 $k+1$ 层

第 22 题 B10 未作答

关于队列的说法，错误的是（）。

（1 分）

BFS 使用队列

队列是先进先出（FIFO）结构

队列可以在中间任意位置插入删除

循环队列用取模实现环形

叁

双端队列

10 QUESTIONS · 2 POINTS EACH

第 23 题 C1 未作答

双端队列（deque）的特点是（）。

（1 分）

只能存整数

两端都可以插入和删除——兼具栈和队列的能力

只能在一端操作

随机访问比 vector 快

第 24 题 C2 未作答

deque<int> d 依次执行 push_back(1) push_front(2) push_back(3) push_front(4)，从前往后为（）。

（1 分）

4 3 2 1

1 2 3 4

4 2 1 3

2 4 1 3

第 25 题 C3 未作答

deque 的 push_front(x) 等价于（）。

（1 分）

删除开头元素

删除末尾元素

在容器开头插入元素 x

在容器末尾插入

第 26 题 C4 未作答

deque<int> d = {1,2,3,4} 执行 pop_front() 和 pop_back() 后，d 变为（）。

（1 分）

{2,3,4}

{1,2,3}

{}

{2,3}

第 27 题 C5 未作答

deque 与 vector 的主要区别是（）。

（1 分）

deque 内存永远连续

vector 只能在末尾高效插入（push_back）；deque 在两端都可以高效插入删除（push_front 和 push_back）

deque 不能随机访问

没有区别

第 28 题 C6 未作答

queue（队列容器适配器）与 deque（双端队列容器）的关系是（）。

（1 分）

queue 是接口限制——底层可用 deque 实现，但只暴露 push_back（入队）和 pop_front（出队）；deque 是底层容器，两端全开

没有关系

deque 是 queue 的子类

两者完全相同

第 29 题 C7 未作答

"滑动窗口"问题：长度为 $k$ 的窗口从左到右滑动，每步求窗口内的最大值。暴力做法 $O(nk)$ ，用单调队列可优化到（）。

（1 分）

$O(n \log n)$

$O(k \log k)$

$O(n)$ ——每个元素至多入队出队各一次

$O(n^2)$

第 30 题 C8 未作答

下列最适合用 deque 的场景是（）。

（1 分）

需要在两端频繁插入删除（如滑动窗口维护、撤销重做双向操作）

只需在末尾添加元素的列表

需要频繁随机访问中间元素

存储大量浮点数

第 31 题 C9 未作答

01deque<int> d;
02for (int i = 1; i <= 5; ++i) {
03    if (i % 2) d.push_front(i);
04    else d.push_back(i);
05}

执行后 d 从前往后为（）。

（1 分）

5 4 3 2 1

5 3 1 2 4

1 3 5 2 4

1 2 3 4 5

第 32 题 C10 未作答

关于 deque，错误的是（）。

（1 分）

在中间插入比在两端插入更快

两端都可以插入和删除

底层通常由分段连续空间实现

支持随机访问 d[i]

肆

单调栈与单调队列

12 QUESTIONS · 2 POINTS EACH

第 33 题 D1 未作答

单调栈是指栈内元素从底到顶保持（）的栈。

（1 分）

全部相等

随机排列

严格递增

单调递增或单调递减（根据应用场景选择）

第 34 题 D2 未作答

维护一个单调递减栈（栈底到栈顶递减），依次入栈 $3, 1, 4, 1, 5$ 。元素 $4$ 入栈时需要先弹出（）。

（1 分）

只弹出 $1$

弹出全部

$1$ 和 $3$ （都比 $4$ 小，破坏递减性需弹出）

不需要弹出

第 35 题 D3 未作答

数组 $\{3, 1, 4, 1, 5\}$ ，对每个元素找右边第一个比它大的元素。用单调栈（递减栈）求解，元素 $3$ 的下一个更大元素是（）。

（1 分）

$1$

$4$

不存在

$5$

第 36 题 D4 未作答

下列问题最适合用单调栈解决的是（）。

（1 分）

对每个元素找左/右第一个比它大/小的元素位置

排序数组

求最短路

求所有元素的平均值

第 37 题 D5 未作答

单调队列是指队列内元素从 front 到 back 保持（），常用于滑动窗口最值。

（1 分）

单调递增或递减——如求窗口最大值用递减队列（队头始终最大）

随机排列

全部相等

严格递增

第 38 题 D6 未作答

维护单调递减队列（存下标），处理数组 $\{5, 3, 8\}$ 。处理 $8$ 时需要先从队尾弹出（）。

（1 分）

只弹出 $3$

$5$

$3$ 和 $5$ （都比 $8$ 小，从队尾弹出）

不需要弹出

第 39 题 D7 未作答

数组 $\{1, 3, -1, -3, 5, 3, 6, 7\}$ ，窗口大小 $k = 3$ 。窗口 $[0, 2]$ （元素 $1, 3, -1$ ）的最大值和窗口 $[4, 6]$ （元素 $5, 3, 6$ ）的最大值分别是（）。

（1 分）

$1$ 和 $5$

$-1$ 和 $3$

$3$ 和 $6$

$3$ 和 $7$

第 40 题 D8 未作答

单调队列与单调栈的本质区别是（）。

（1 分）

没有区别

单调栈只能从栈顶弹出（一端操作）；单调队列可以从队尾弹出不满足单调性的元素、同时从队头弹出过期的（超出窗口的）——两端操作

单调队列不能存下标

单调栈只能递增、单调队列只能递减

第 41 题 D9 未作答

单调栈找"每个元素右边第一个更大元素"的代码框架，栈存的是（）。

（1 分）

元素值

不需要存东西

元素的下一个更大值

元素下标——弹栈时通过下标计算距离

第 42 题 D10 未作答

单调队列求滑动窗口最大值的代码中，"从队头弹出"的条件是（）。

（1 分）

队头下标超出窗口范围（q.front() <= i - k 时弹出）

队头元素值最大

队头元素值最小

队列长度超过 $k$

第 43 题 D11 未作答

单调栈和单调队列的总时间复杂度都是 $O(n)$ ，原因是（）。

（1 分）

用哈希加速

每次操作恰好 $O(1)$

每个元素至多入栈/入队一次、出栈/出队一次——均摊分析每次操作 $O(1)$

只处理一半元素

第 44 题 D12 未作答

关于单调栈和单调队列，错误的是（）。

（1 分）

单调栈可以替代单调队列解决所有问题

单调队列适合"滑动窗口最值"

两者维护过程都是"新元素到来时从一端弹出破坏单调性的元素"

单调栈适合"找最近更大/更小元素"

伍

递归深入

14 QUESTIONS · 2 POINTS EACH

第 45 题 E1 未作答

在程序运行过程中，如果递归调用的层数过多，可能会由于（）引发错误。（2021 年 CSP-S 真题）

（1 分）

系统分配的堆空间溢出

系统分配的链表空间溢出

系统分配的队列空间溢出

系统分配的栈空间溢出

第 46 题 E2 未作答

递归深度 $10^5$ 的函数（每帧约 $100$ 字节），总栈空间约（）。

（1 分）

$100$ MB

$10$ KB——不会溢出

$1$ KB

$10$ MB——超过默认栈空间（通常 $1\sim8$ MB），会溢出

第 47 题 E3 未作答

在 C++ 中，以下哪个函数调用会造成栈溢出（）。（2024 年 CSP-S 真题）

（1 分）

void qux() { return; }

int bar() { int x = 1; return x; }

void baz() { int a[1000]; baz(); }——无终止条件的递归

int foo() { return 0; }

第 48 题 E4 未作答

递归函数 $f(n) = f(n-1) + n$ （ $f(0)=0$ ）可以改写为循环：for(i=1; i<=n; ++i) s += i;。改写的好处是（）。

（1 分）

消除了递归深度限制——不再消耗栈空间， $n = 10^7$ 也不会溢出

结果更精确

代码更长

时间复杂度降低

第 49 题 E5 未作答

尾递归是指（）。

（1 分）

最后一行是 return 0

递归调用是函数的最后一个操作（返回值直接就是递归结果，无需额外计算）——某些编译器可优化为循环

只递归一层

没有参数的递归

第 50 题 E6 未作答

递归函数 g(n) 调用 g(n-1) 两次（ $g(0)=1$ ）。 $g(3)$ 的总调用次数是（）。

（1 分）

$15$

$10$

$8$

$7$

第 51 题 E7 未作答

01int h(int n) {
02    if (n <= 0) return 0;
03    return h(n / 2) + n;
04}

h(7) 的返回值是（）。

（1 分）

$7$

$13$

$10$

$3$

第 52 题 E8 未作答

01void p(int n) {
02    if (n == 0) { cout << "*"; return; }
03    p(n - 1);
04    cout << n;
05    p(n - 1);
06}

p(2) 输出（）。

（1 分）

12*

*1*2*1*

*1*

*2*1*1*

第 53 题 E9 未作答

01int q(int a, int b) {
02    if (b == 0) return a;
03    return q(b, a % b);
04}

q(12, 8) 的返回值是（）（辗转相除法）。

（1 分）

$12$

$0$

$8$

$4$

第 54 题 E10 未作答

递归与分治的关系是（）。

（1 分）

分治不能用递归

分治通常用递归实现——"分"就是递归调用自身处理子问题；但递归不一定是分治（单路递归没有"分"）

完全等价

递归是分治的一种

第 55 题 E11 未作答

设计递归函数时最重要的安全措施是（）。

（1 分）

使用全局变量

返回值必须为 int

参数越多越好

确保有正确的终止条件（base case），且每层递归都朝终止条件靠近

第 56 题 E12 未作答

调试递归函数最有效的方法是（）。

（1 分）

只看最终结果

删除递归

换编译器

在函数入口打印递归深度和参数值——追踪每层调用与返回过程

第 57 题 E13 未作答

朴素斐波那契递归 fib(30) 需要约 $2^{30} \approx 10^9$ 次调用，但加记忆化后只需（）次。

（1 分）

$59$ （ $fib(0)$ 到 $fib(30)$ 各算一次）

$30$

$30^2$

$2^{30}$

第 58 题 E14 未作答

关于递归，错误的是（）。

（1 分）

所有递归都比循环快

递归使用系统栈

递归可以转循环

递归深度过大可能栈溢出

陆

递推深化

14 QUESTIONS · 2 POINTS EACH

第 59 题 F1 未作答

递推与递归的关系是（）。

（1 分）

递推只能用数组

递推是自底向上（从小到大填表）；递归是自顶向下（从大到小拆分）——本质等价，只是方向不同

递归一定比递推快

完全无关

第 60 题 F2 未作答

递推 $f(n) = f(n-1) + 3$ ， $f(1) = 1$ 。 $f(5) = ?$ （）。

（1 分）

$15$

$10$

$13$

$16$

第 61 题 F3 未作答

斐波那契 $f(1)=1, f(2)=1, f(n)=f(n-1)+f(n-2)$ 。 $f(8) = ?$ （）。

（1 分）

$13$

$21$

$34$

$18$

第 62 题 F4 未作答

递推 $f(1)=1, f(2)=2, f(n) = f(n-1) + f(n-2)$ 。 $f(6) = ?$ （）。

（1 分）

$8$

$16$

$13$

$21$

第 63 题 F5 未作答

汉诺塔递推 $h(n) = 2h(n-1) + 1$ ， $h(1) = 1$ 。 $h(5) = ?$ （）。

（1 分）

$31$

$16$

$15$

$32$

第 64 题 F6 未作答

汉诺塔 $n = 2$ （A→C 借助 B），移动序列是（）。

（1 分）

A→B, A→C

A→B, A→C, B→C

A→C, A→C

A→C, A→B, B→C

第 65 题 F7 未作答

递推 $f(n) = 2f(n-1)$ （ $f(1) = 1$ ）的通项公式是（）。

（1 分）

$f(n) = 2^{n-1}$

$f(n) = n$

$f(n) = n^2$

$f(n) = 2n$

第 66 题 F8 未作答

递推 $f(n) = f(n-1) + f(n-2)$ 的特征方程 $x^2 = x + 1$ 的解中包含黄金比 $\phi = \frac{1+\sqrt{5}}{2}$ 。这说明斐波那契数列的增长速度是（）。

（1 分）

对数增长

常数

线性增长

指数增长（底为 $\phi \approx 1.618$ ）

第 67 题 F9 未作答

递推 $f(n) = f(n-1) + f(n-2)$ ，初始条件 $f(1)=1, f(2)=1$ 得斐波那契数列；改为 $f(1)=1, f(2)=3$ 得到的是（）数列。

（1 分）

仍然是斐波那契

常数列

等差数列

Lucas 数列——递推相同但初始值不同，产生完全不同的数列

第 68 题 F10 未作答

递推编程的标准框架是（）。

（1 分）

初始化 $f[1], f[2]$ → for (i = 3; i <= n; ++i) f[i] = f[i-1] + f[i-2]; → 输出 $f[n]$

不需要初始值

递归函数调用自身

从 $n$ 往回推

第 69 题 F11 未作答

斐波那契数列 $f(50) \approx 1.2 \times 10^{10}$ 。int（上限约 $2.1 \times 10^9$ ）能否存下（）。

（1 分）

能

用 float 可以

取决于编译器

不能—— $f(47) = 2971215073$ 已超 int 上限，应用 long long

第 70 题 F12 未作答

递推 $f(n) = f(n-1) + f(n-2)$ 只需前两项。不开 $f[n]$ 数组、只保留两个变量的做法叫（）。

（1 分）

记忆化

不可能实现

打表

滚动变量——空间从 $O(n)$ 降到 $O(1)$

第 71 题 F13 未作答

递推与动态规划的关系是（）。

（1 分）

递推比 DP 慢

两者无关

线性递推是最简单的 DP——状态转移方程 $f[i] = f[i-1] + f[i-2]$ 就是 DP 的状态转移

DP 不能用递推实现

第 72 题 F14 未作答

关于递推，错误的是（）。

（1 分）

递推需要正确的初始条件

递推自底向上填表

递推可以优化空间（滚动变量）

递推就是递归的另一种叫法

柒

栈队列递归综合

14 QUESTIONS · 2 POINTS EACH

第 73 题 G1 未作答

用双栈法求中缀表达式 2 * (3 + 4) 的值，计算结果是（）。

（1 分）

$14$

$10$

$24$

$7$

第 74 题 G2 未作答

检查括号串 (()()) 是否匹配：用栈扫描，最终栈的状态是（）。

（1 分）

有一个 )

空——所有左括号都被匹配弹出

有两个 (

有一个 (

第 75 题 G3 未作答

main() 调用 f(3)，f(3) 调用 f(2)，f(2) 调用 f(1)，f(1) 返回 $1$ 。此时栈中从底到顶为（）。

（1 分）

空

main() f(3) f(2) f(1)

只有 f(1)

f(1) f(2) f(3) main()

第 76 题 G4 未作答

表达式 (a+b)*c-d 的后缀表达式为（）。

（1 分）

abc+*d-

abcd*+-

abcd+-*

ab+c*d-

第 77 题 G5 未作答

01void f(int n) {
02    if (n > 2) { f(n / 2); cout << n; }
03    else cout << n;
04}

f(12) 的输出是（）。

（1 分）

3

3 6 12

12 6 3

12

第 78 题 G6 未作答

初始空栈和空队列。执行 push(1) push(2) enqueue(pop()) push(3) enqueue(pop())，此时队列从队头到队尾为（）。

（1 分）

1 2

1 3

2 3

3 2

第 79 题 G7 未作答

二叉树根为 $1$ ，左子 $2$ 、右子 $3$ ， $2$ 的左子 $4$ 。BFS 层序遍历序列是（）。

（1 分）

4 2 3 1

1 3 2 4

1 2 4 3

1 2 3 4

第 80 题 G8 未作答

01int s(int arr[], int n) {
02    if (n == 0) return 0;
03    return arr[n-1] + s(arr, n-1);
04}

int a[] = {1, 2, 3}; s(a, 3) 返回（）。

（1 分）

$0$

$1$

$3$

$6$

第 81 题 G9 未作答

递推 $f[0]=0, f[1]=1$ ， $f[i] = f[i-1] + f[i-2]$ 。 $f[6] = ?$ （）。

（1 分）

$13$

$5$

$8$

$21$

第 82 题 G10 未作答

用两个栈 S1（入队栈）和 S2（出队栈）实现队列。dequeue() 时若 S2 为空，应（）。

（1 分）

从 S1 弹出

不需要操作

直接返回错误

把 S1 的全部元素弹出压入 S2——逆序变正序，然后从 S2 弹出

第 83 题 G11 未作答

用两个队列实现栈的 pop()（弹出最后入队的元素），需要的操作次数是（）。

（1 分）

$O(1)$

$O(\log n)$

$O(n^2)$

$O(n)$ ——需把主队列 $n-1$ 个元素转移到辅队列、取出最后一个

第 84 题 G12 未作答

01int f(int n) {
02    return f(n + 1);  // 没有终止条件
03}

调用 f(0) 的结果是（）。

（1 分）

返回 $\infty$

栈溢出——递归无限加深，系统栈耗尽

返回 $0$

编译错误

第 85 题 G13 未作答

空栈依次进栈 a,b,c，允许交替出栈。下列可能的出栈序列是（）。

（1 分）

c a b

cab

b a c

b c a

第 86 题 G14 未作答

以下对数据结构的表述不恰当的是（）。（2023 年 CSP-S 真题）

（1 分）

队列是一种先进先出（FIFO）的线性结构

哈夫曼树的构造过程主要是为了实现图的深度优先搜索

二叉树是一种每个结点最多有两个子结点的树结构

散列表是一种通过散列函数将关键字映射到存储位置的数据结构

捌

综合与易错

14 QUESTIONS · 2 POINTS EACH

第 87 题 H1 未作答

栈、队列、deque 的操作能力从少到多排列是（）。

（1 分）

栈（一端进出）< 队列（一端进一端出）< deque（两端进出）

deque < 队列 < 栈

三者相同

队列 < 栈 < deque

第 88 题 H2 未作答

对同一输入序列 1,2,3，栈和队列的出序分别是（）。

（1 分）

栈 1 2 3；队列 3 2 1

都是 1 2 3

栈（全进全出）3 2 1；队列 1 2 3

都是 3 2 1

第 89 题 H3 未作答

$n = 10^6$ 的递归求和 f(n) = f(n-1) + n 应改用循环，主要原因是（）。

（1 分）

没有原因

递归深度 $10^6$ 超过系统栈空间（约 $1\sim8$ MB），会栈溢出

递归不能处理大数

循环结果更精确

第 90 题 H4 未作答

防范递归栈溢出的方法不包括（）。

（1 分）

改为循环

增大输入规模

限制递归深度

用显式栈模拟递归

第 91 题 H5 未作答

容量 $6$ 的循环队列，rear = 4，enqueue 后 rear 变为（）。

（1 分）

$5$

$0$

$10$

$4$

第 92 题 H6 未作答

递推 $f[i] = f[i-1] + f[i-2]$ 从 $i = ?$ 开始循环（ $f[0]$ 和 $f[1]$ 已初始化）（）。

（1 分）

$i = 1$

$i = 0$

$i = 3$

$i = 2$ ——访问 $f[0]$ 和 $f[1]$ 不越界

第 93 题 H7 未作答

单调栈的核心性质是（）。

（1 分）

只能存整数

栈的大小固定

栈内元素从底到顶保持单调——新元素入栈前先弹出破坏单调性的元素

栈内元素全部相等

第 94 题 H8 未作答

滑动窗口最大值用单调递减队列而不是单调递增队列，原因是（）。

（1 分）

没有区别

递减队列的队头始终是当前窗口的最大值——直接读队头即可

递增队列不能维护

递减队列更短

第 95 题 H9 未作答

递推 $f(n) = 3 \cdot f(n-1)$ （ $f(0)=1$ ）的 $f(5) = ?$ （）。

（1 分）

$243$

$81$

$15$

$125$

第 96 题 H10 未作答

deque 的 insert 在中间位置的时间复杂度是（）。

（1 分）

$O(n^2)$

$O(n)$ ——中间插入仍需移动元素；只有两端操作是 $O(1)$

$O(1)$

$O(\log n)$

第 97 题 H11 未作答

单调队列的"过期弹出"（从队头移出超出窗口的下标）保证了（）。

（1 分）

没有作用

队列长度固定

队头元素始终在当前窗口内——不会输出已经滑出窗口的最大/最小值

队列单调递增

第 98 题 H12 未作答

关于 priority_queue（优先队列），正确的是（）。

（1 分）

插入是 $O(n)$

按优先级出队——默认大根堆（最大元素在堆顶）

只能存字符串

按入队顺序出队

第 99 题 H13 未作答

递推 $f(n) = f(n-1) \cdot 2$ （ $f(0) = 1$ ）， $f(10) = ?$ （）。

（1 分）

$20$

$512$

$100$

$1024$

第 100 题 H14 未作答

关于栈、队列、递归和递推，错误的是（）。

（1 分）

BFS 使用队列

递归调用使用系统栈

单调栈可以在 $O(n \log n)$ 时间内解决"下一个更大元素"问题

递推是自底向上的填表

玖

真题演练

8 QUESTIONS · 真题演练不计分

第 1 题单选未作答

今有一空栈 $S$ ，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行：进栈、进栈、出栈、进栈、进栈、出栈的操作，则此操作完成后，栈底元素为（）。

（0 分）

b

a

d

c

CSP-S 2020 · 单选第4题｜知识点栈、栈的应用

第 2 题单选未作答

广度优先搜索时，一定需要用到的数据结构是（）。

（0 分）

栈

二叉树

队列

哈希表

CSP-S 2020 · 单选第9题｜知识点双端队列、冒泡排序

第 3 题单选未作答

表达式 a*(b+c)-d 的后缀表达形式为（）。

（0 分）

abc*+d-

-*+abcd

abcd*+-

abc+*d-

CSP-S 2020 · 单选第12题｜知识点栈的应用、栈

第 4 题单选未作答

在程序运行过程中，如果递归调用的层数过多，可能会由于（）引发错误。

（0 分）

系统分配的栈空间溢出

系统分配的队列空间溢出

系统分配的链表空间溢出

系统分配的堆空间溢出

CSP-S 2021 · 单选第3题｜知识点归并排序、栈、Unicode与汉字编码

第 5 题单选未作答

若元素 a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈操作，则不可能得到的出栈序列是（）。

（0 分）

dcebfa

cbdaef

bcaefd

afedcb

CSP-S 2022 · 单选第3题｜知识点栈、栈的应用

第 6 题单选未作答

以下对数据结构的表述不恰当的一项是（）。

（0 分）

队列是一种先进先出（FIFO）的线性结构。

哈夫曼树的构造过程主要是为了实现图的深度优先搜索。

散列表是一种通过散列函数将关键字映射到存储位置的数据结构。

二叉树是一种每个结点最多有两个子结点的树结构。

CSP-S 2023 · 单选第5题｜知识点回溯、双端队列

第 7 题单选未作答

在 C++ 中，以下哪个函数调用会造成栈溢出？（）

（0 分）

int foo() { return 0; }

int bar() { int x = 1; return x; }

void baz() { int a[1000]; baz(); }

void qux() { return; }

CSP-S 2024 · 单选第3题｜知识点三目运算、归并排序、栈

第 8 题单选未作答

下面哪个数据结构最适合实现先进先出（FIFO）的功能？

（0 分）

栈

队列

线性表

二叉搜索树

CSP-S 2024 · 单选第5题｜知识点双端队列、栈

重置作答

专题 S04 栈·队列·递归与递推 · 复习强化

判 分 报 告

栈深入

队列深入

双端队列

单调栈与单调队列

递归深入

递推深化

栈队列递归综合

综合与易错

真 题 演 练

打印

导出 HTML 子卷

判分报告

真题演练