第三章栈、队列和数组（不含25_26）

答案速对

1. 2009-02：C
2. 2010-01：D
3. 2010-02：C
4. 2011-02：B
5. 2011-03：B
6. 2013-02：C
7. 2018-01：B
8. 2018-02：C
9. 2020-02：D
10. 2014-03：A
11. 2021-02：D
12. 2022-02：D
13. 2023-03：A
14. 2016-04：B
15. 2017-03：A
16. 2018-03：A
17. 2020-01：C
18. 2021-03：B
19. 2009-01：B
20. 2012-02：A
21. 2014-02：B
22. 2015-01：A
23. 2016-04：C
24. 2017-02：C
25. 2024-02：A

(一) 栈和队列的基本概念

(二) 栈和队列的顺序存储结构

1. 【2009-02】设栈 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

解析

答案：C

队列具有先进先出特性，所以队列的出队顺序与元素进入队列的顺序完全相同。又因为每个元素从栈中弹出后立即入队，因此题目给出的 b、d、c、f、e、a、g 也就是栈的出栈顺序。

按照输入次序构造操作：

1. a、b 入栈，弹出 b。此时栈中剩 a，最大深度为 2。
2. c、d 入栈，栈中为 a、c、d，弹出 d，再弹出 c。最大深度达到 3。
3. e、f 入栈，栈中为 a、e、f，弹出 f，再弹出 e。最大深度仍为 3。
4. 弹出 a。
5. g 入栈后立即弹出。

整个过程中栈内元素最多为 3 个，所以容量至少为 3。

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

A. d, c, e, b, f, a

B. c, b, d, a, e, f

C. b, c, a, e, f, d

D. a, f, e, d, c, b

解析

答案：D

“不允许连续三次出栈”表示每连续进行两次出栈之后，若还要继续产生输出，就必须先进行一次入栈。

A 可以这样实现：先将 a、b、c、d 入栈，连续弹出 d、c；将 e 入栈并弹出 e，再弹出 b；将 f 入栈并弹出 f，最后弹出 a。没有出现连续三次出栈。

B 可以这样实现：a、b、c 入栈，弹出 c、b；d 入栈，弹出 d、a；e 入栈并弹出；f 入栈并弹出。可以实现。

C 可以这样实现：a、b 入栈并弹出 b；c 入栈，弹出 c、a；d、e 入栈并弹出 e；f 入栈，弹出 f、d。可以实现。

D 的第一个输出是 a，因此 a 入栈后必须立即弹出。随后为了输出 f，必须把 b、c、d、e、f 全部压栈。弹出 f 后，栈顶依次是 e、d、c、b，而此时已经没有尚未入栈的元素可以打断出栈操作，因此至少会连续弹出 f、e、d 三个元素，违反限制。

1. 【2010-02】某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，若元素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

解析

答案：C

把允许出队的一端称为“出口端”。新元素若从出口端入队，其出队次序会与入队次序相反；新元素若从另一端入队，其出队次序会保持原来的先后关系。

因此，最终出队序列必然可以分成两段：

• 前一段相对于 a、b、c、d、e 是逆序的；
• 后一段相对于 a、b、c、d、e 是正序的。

逐项检查：

• A 可分为“b、a”和“c、d、e”，前段逆序、后段正序，可以得到。
• B 可分为“d、b、a”和“c、e”，可以得到。
• D 可分为“e、c、b、a”和“d”，可以得到。
• C 为 d、b、c、a、e。若把 d、b 作为逆序段，则剩余 c、a、e 不是正序；若把 c 放入前段，则 d、b、c 又不是逆序。不存在合法分界。

1. 【2011-02】元素a, b, c, d, e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（ ）

A. 3 B. 4 C. 5 D. 6

解析

答案：B

要让 d 第一个出栈，必须先将 a、b、c、d 依次压栈，再立即弹出 d。此时：

• 栈中从底到顶为 a、b、c；
• e 尚未入栈。

接下来有两类选择。

第一类：先弹出 c。此后根据 e 的入栈时机，可以得到：

1. d、c、b、a、e；
2. d、c、b、e、a；
3. d、c、e、b、a。

第二类：在弹出 c 前先将 e 入栈。此时 e 必须先出栈，随后 c、b、a 依次出栈，得到：

4. d、e、c、b、a。

一共 4 种。

1. 【2011-03】已知循环队列存储在一维数组 A[0..n−1] ，且队列非空时， front 和 rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存储在 A[0] 处，则初始时 front 和 rear 的值分别是（ ）。

A. 0,0

B. 0,n−1

C. n−1,0

D. n−1,n−1

解析

答案：B

在这种指针约定下，入队时先将 rear 循环后移一位，再把元素写入 rear 所指位置：

要让第一个元素写入 ，初始 rear 应满足

所以初始 。

第一个元素入队后，front 应直接指向 ，因此 front 的初值设为 0。第一次入队后 front 与 rear 都为 0，共同指向唯一的队列元素。

1. 【2013-02】一个栈的入栈序列为 1,2,3,…,n，其出栈序列是 \(p_1,p_2,p_3,…,p_n\) ，若\(p_2=3\) ，则 \(p_3\)可能取值的个数是（ ）。

A. n−3

B. n−2

C. n−1

D. 无法确定

解析

答案：C

因为第二个出栈元素是 3，第一个出栈元素只可能是 1 或 2。

若 ：

1. 1 入栈并弹出；
2. 2、3 入栈，弹出 3；
3. 此时栈顶为 2，尚未入栈的元素为 。

所以 可以是 2；也可以继续把元素压到某个 ，再弹出 k。因此可取 。

若 ：

1. 1、2 入栈，弹出 2；
2. 3 入栈并弹出；
3. 此时栈顶为 1。

所以 可以是 1，也可以是 中的任意一个。

两种情况合并后， 可以取 ，即除了 3 以外的所有值，共 个。

1. 【2018-01】若栈 S1 中保存整数，栈 S2 中保存运算符，函数 F() 依次执行下述各步操作:
2. 从 S1 中依次弹出两个操作数a和b;
3. 从 S2 中弹出一个运算符op;
4. 执行相应的运算b op a;
5. 将运算结果压入 S1 。

假定 S1 中的操作数依次是5, 8, 3, 2 （2在栈顶），S2 中的运算符依次是 ×,−,+ （ + 在栈顶）。调用3次 F() 后， S1 栈顶保存的值是（ ）。

A. -15

B. 15

C. -20

D. 20

解析

答案：B

第一次调用：

• 弹出 、；
• 弹出运算符 ；
• 计算 ；
• S1 变为 5、8、5。

第二次调用：

• 弹出 、；
• 弹出运算符 ；
• 计算 ；
• S1 变为 5、3。

第三次调用：

• 弹出 、；
• 弹出运算符 ；
• 计算 。

要特别注意运算顺序是 ，不是 。

1. 【2018-02】现有队列Q与栈S，初始时Q中的元素依次是1, 2, 3, 4, 5, 6 （1在队头），S为空。若仅允许下列3种操作：

① 出队并输出出队元素；

② 出队并将出队元素入栈；

③ 出栈并输出出栈元素；

则不能得到的输出序列是（ ）。

A. 1, 2, 5, 6, 4, 3

B. 2, 3, 4, 5, 6, 1

C. 3, 4, 5, 6, 1, 2

D. 6, 5, 4, 3, 2, 1

解析

答案：C

A 可以实现：1、2 直接出队输出；3、4 出队后入栈；5、6 直接输出；最后从栈中弹出 4、3。

B 可以实现：1 先入栈；2、3、4、5、6 直接输出；最后弹出 1。

D 可以实现：1、2、3、4、5 全部入栈；6 直接输出；再依次弹出 5、4、3、2、1。

对于 C，要先输出 3，必须把 1、2 都暂存在栈中。此时栈中从底到顶为 1、2。输出 3、4、5、6 后，栈顶是 2，只能先输出 2 再输出 1，不可能得到题目要求的 1、2。

1. 【2020-02】对空栈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

解析

答案：D

逐步执行：

1. Push：a 入栈；
2. Push：b 入栈；
3. Pop：弹出 b；
4. Push：c 入栈；
5. Pop：弹出 c；
6. Push：d 入栈；
7. Push：e 入栈；
8. Pop：弹出 e。

因此出栈序列为 b、c、e。

1. 【2014-03】循环队列放在一维数组 A[0..M-1] 中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳 M-1 个元素。初始时为空。下列判断队空和队满的条件中，正确的是（ ）。

A. 队空：end1 == end2; 队满：end1 == (end2 + 1) mod M

B. 队空：end1 == end2; 队满：end2 == (end1 + 1) mod (M - 1)

C. 队空：end1 == (end1 + 1) mod M; 队满：end1 == (end2 + 1) mod M

D. 队空：end1 == (end2 + 1) mod M; 队满：end2 == (end1 + 1) mod (M - 1)

解析

end2 指向队尾后一个位置，因此队列为空时，没有任何元素夹在 end1 与 end2 之间，二者重合：

为了区分队空和队满，数组中始终保留一个空位置，所以最多存放 个元素。

当 end2 再循环前进一步就会追上 end1 时，队列已满：

等价地写成

取模的模数必须是数组长度 ，不能写成 。

答案：A

1. 【2021-02】已知初始为空的队列Q的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若Q的入队序列是1, 2, 3, 4, 5，则不能得到的出队序列是（ ）。

A. 5, 4, 3, 1, 2

B. 5, 3, 1, 2, 4

C. 4, 2, 1, 3, 5

D. 4, 1, 3, 2, 5

解析

把可以出队的一端称为出口端。新元素可以从任意一端入队，但所有输出都必须从出口端产生。

A 可以实现：1 从出口端入队，2 从另一端入队，3、4、5 依次从出口端入队。队列从另一端到出口端为 2、1、3、4、5，依次输出 5、4、3、1、2。

B 可以实现：依次把元素放成从另一端到出口端的 4、2、1、3、5，便可输出 5、3、1、2、4。

C 可以实现：输入前四个元素后，将它们放成从另一端到出口端的 3、1、2、4，输出 4、2、1、3；再让 5 入队并输出。

D 的第一个输出是 4，所以在首次出队前，1、2、3、4 至少已经全部入队。为了随后输出 1、3、2，首次出队前从另一端到出口端应出现 2、3、1、4 的相对排列。但从单元素 1 开始，2 和 3 每次只能加在当前序列两端，无法把 3 插入 2 与 1 之间。即使提前让 5 入队，也不能改变 1、2、3 的这种相对限制。

答案：D

1. 【2022-02】给定有限符号集 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可能互为倒序

解析

给定完整的 in 和 out 后，可以模拟栈来判断：

1. 按 in 的顺序不断压栈；
2. 每次栈顶等于 out 当前需要的元素时就弹出；
3. 最后若能按顺序产生整个 out，则 out 合法，否则不合法。

因此 A、B 所说的“不能判断”都错误。

若每个元素入栈后立即出栈，则 out 可以与 in 完全相同，所以 C 错误。

若把 in 中的所有元素全部压栈后再依次弹出，out 就恰好是 in 的倒序，所以 D 正确。

答案：D

(三) 栈和队列的链式存储结构

(四) 多维数组的存储

1. 【2023-03】若采用三元组表存储结构存储系数矩阵 M。则除三元组外，下列数据中还需要保存的是（ ）。

I. M 的行数

II M 中包含非零元素的行数

III. M 的列数

IV. M 中包含非零元素的列数

A. 仅 I 和 III

B. 仅 I 和 IV

C. 仅 II 和 IV

D. I、II、III 和 IV

解析

每个非零元素通常用三元组

表示，其中 i 是行号、j 是列号、v 是元素值。

这些三元组只能说明非零元素出现在哪里，却不能完整确定原矩阵的整体规模。例如，若最后几行或最后几列全为 0，它们不会出现在任何三元组中，仅凭三元组无法知道这些全零行、全零列是否存在。

因此还必须保存：

• 矩阵的总行数，即 I；
• 矩阵的总列数，即 III；
• 通常还会保存非零元素总数，但该项不在题目给出的四项中。

“包含非零元素的行数”和“包含非零元素的列数”既不能代替矩阵总行数、总列数，也可以通过扫描三元组统计出来，不是重建矩阵所必需的规模信息。

答案：A

(五) 特殊矩阵的压缩存储

1. 【2016-04】有一个100阶的三对角矩阵 M ，其元素 m_{i,j}(1≤i≤100,1≤j≤100) 按行优先依次压缩存入下标从0开始的一维数组 N 中。元素 m_{30,30} 在数组 N 中的下标是（ ）。

A. 86

B. 87

C. 88

D. 89

解析

三对角矩阵只存储满足的元素。

各行存储元素个数为：

• 第 1 行有 2 个，即 ；
• 第 2 行至第 99 行各有 3 个；
• 第 100 行有 2 个。

在第 30 行之前：

• 第 1 行存 2 个；
• 第 2 行至第 29 行共有 28 行，每行存 3 个。

所以第 30 行第一个压缩元素 的下标为

第 30 行按 的顺序存储，因此 比该行第一个元素再后移一位：

答案：B

1. 【2017-03】适用于压缩存储稀疏矩阵的两种存储结构是（ ）。

A. 三元组表和十字链表

B. 三元组表和邻接矩阵

C. 十字链表和二叉链表

D. 邻接矩阵和十字链表

解析

稀疏矩阵中绝大多数元素为 0。压缩存储的核心是只保存非零元素及其位置。

三元组表为每个非零元素保存“行号、列号、元素值”，空间复杂度与非零元素个数有关，适合稀疏矩阵。

十字链表为每个非零元素建立结点，同时通过行链和列链组织这些结点，既便于按行访问，也便于按列访问，同样适合稀疏矩阵。

邻接矩阵通常用于表示图，需要为所有行列位置分配空间，本质上仍是完整二维数组，不属于稀疏矩阵的压缩存储。二叉链表也不是稀疏矩阵的标准存储结构。

答案：A

1. 【2018-03】设有一个 12×12 的对称矩阵 M ，将其上三角部分的元素 m_{ij}(1≤i≤j≤12) 按行优先存入C语言的一维数组N中，元素 m_{6,6} 在N中的下标是（ ）。

A. 50

B. 51

C. 55

D. 66

解析

上三角部分按行存储时：

• 第 1 行存 12 个元素；
• 第 2 行存 11 个元素；
• 第 3 行存 10 个元素；
• 第 4 行存 9 个元素；
• 第 5 行存 8 个元素。

因此第 6 行之前已经存储个元素。

第 6 行存储顺序从 开始，所以 是第 6 行的第一个压缩元素。数组下标从 0 开始，前面已有 50 个元素时，当前元素下标正好是 50。

答案：A

1. 【2020-01】将一个 10×10 的对称矩阵 M 的上三角部分的元素 \(m_{i,j}(1≤i≤j≤10)\) 按列优先存入C语言的一维数组 N 中，元素 \(m_{7,2}\)在 N 中的下标是（ ）。

A. 15

B. 16

C. 22

D. 23

解析

位于下三角。因为 M 是对称矩阵，

所以实际要查找上三角中的 。

上三角按列优先存储时，第 j 列保存共 j 个元素。

第 7 列之前的第 1 至第 6 列共存储个元素。

第 7 列中， 的下标是 21， 的下标是

答案：C

1. 【2021-03】已知二维数组A按行优先方式存储，每个元素占用1个存储单元。若元素A0的存储地址是100, A3的存储地址是220 ,则元素A5的存储地址是（ ）。

A. 295

B. 300

C. 301

D. 306

解析

设二维数组每行有 n 个元素。按行优先存储时，

其中每个元素所占空间 。

由 的地址为 220：

解得：

于是

答案：B

(六) 栈、队列和数组的应用

1. 【2009-01】为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。

A. 栈

B. 队列

C. 树

D. 图

解析

打印任务必须按照进入缓冲区的先后顺序处理：

• 先写入缓冲区的数据应先交给打印机；
• 后写入的数据应排在后面等待。

这正是“先进先出”，即 FIFO。队列的入队端用于接收主机写入的数据，出队端用于向打印机提供数据。

栈是后进先出，会让后写入的数据先打印，不符合要求；树和图也不用于表达这种简单的排队次序。

答案：B

1. 【2012-02】已知操作符包括‘ + ’、‘ − ’、‘ ∗ ’、‘ / ’、‘ ( ’ 和 ‘ ) ’。将中缀表达式 a+b−a∗((c+d)/e−f)+g 转换为等价的后缀表达式 ab+acd+e/f−∗−g+ 时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。

A. 5

B. 7

C. 8

D. 11

解析

从左到右扫描表达式，操作数直接输出，操作符按优先级处理。左括号也需要压入操作符栈。

只列出栈深度发生变化的关键位置，以下均按“栈底到栈顶”书写：

1. 扫描第一个 ：栈为 ，深度 1。
2. 扫描 ：先弹出同优先级的 ，再压入 ，深度仍为 1。
3. 扫描乘号：栈为 ，深度 2。
4. 扫描第一个左括号：栈为 ，深度 3。
5. 扫描第二个左括号：栈为 ，深度 4。
6. 扫描 c 后面的 ：栈为 ，深度达到 5。
7. 扫描右括号时，弹出 并删除与之匹配的左括号，深度下降。
8. 后续除号、减号和最后的加号都不会让深度超过 5。

因此最大深度为 5。

答案：A

1. 【2014-02】假设栈初始为空，将中缀表达式 a/b+(c∗d−e∗f)/g 转换为等价的后缀表达式的过程中，当扫描到 f 时，栈中的元素依次是（ ）。

A. +(∗−

B. +(−∗

C. /+(∗−∗

D. /+−∗

解析

逐步处理操作符：

1. 扫描 a 后的除号：除号入栈。
2. 扫描 b 后的加号：加号优先级低于除号，因此先弹出除号，再压入加号。栈为 。
3. 扫描左括号：压栈，栈为 。
4. 扫描 c 后的乘号：压栈，栈为 。
5. 扫描 d 后的减号：乘号优先级高于减号，先弹出乘号，再压入减号。栈为 。
6. 扫描 e 后的乘号：乘号优先级高于栈顶减号，直接压栈。栈为 。
7. f 是操作数，扫描到 f 时直接输出，不改变操作符栈。

所以从栈底到栈顶为 、、、，即 。

答案：B

1. 【2015-01】已知程序如下：

int S(int n) {
    return (n <= 0) ? 0 : S(n - 1) + n;
}
void main() {
    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()

解析

函数调用过程为：

1. 首先执行 main()，main 的活动记录进入调用栈；
2. main 调用 S(1)，S(1) 的活动记录压在 main 之上；
3. 因为 ，S(1) 继续调用 S(0)，S(0) 的活动记录位于栈顶；
4. S(0) 返回后，才依次返回 S(1) 和 main。

因此递归最深时，从栈底到栈顶为

答案：A

1. 【2016-04】设有下图所示的火车车轨，入口到出口之间有 n 条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为1~9的9列列车，驶入的次序依次是8, 4, 2, 5, 3, 9, 1, 6, 7。若期望驶出的次序依次为1~9，则 n 至少是（ ）。

A. 2

B. 3

C. 4

D. 5

解析

同一条轨道中的列车不能互相越过，因此进入同一轨道的编号必须保持递增，才能最终按 驶出。

原序列中存在严格递减子序列

这 4 列火车不能进入同一条轨道中的任意两列：如果较大的编号先进入同一轨道，它会挡住后进入的较小编号。因此至少需要 4 条轨道。

答案：C

1. 【2017-02】下列关于栈的叙述中，错误的是（ ）。

Ⅰ．采用非递归方式重写递归程序时必须使用栈

Ⅱ．函数调用时，系统要用栈保存必要的信息

Ⅲ．只要确定了入栈次序，即可确定出栈次序

Ⅳ．栈是一种受限的线性表，允许在其两端进行操作

A. 仅Ⅰ

B. 仅Ⅰ、Ⅱ、Ⅲ

C. 仅Ⅰ、Ⅲ、Ⅳ

D. 仅Ⅱ、Ⅲ、Ⅳ

解析

I 错误。递归改写为非递归时，经常需要显式栈保存状态，但并非“必须”。某些尾递归或可直接推导迭代关系的递归算法可以用循环和普通变量改写。

II 正确。函数调用时，系统通常利用运行时栈保存返回地址、参数、局部变量和现场信息。

III 错误。给定同一个入栈次序，可以通过不同的入栈、出栈交替方式产生多个合法出栈序列。

IV 错误。栈只允许在同一端进行插入和删除，该端称为栈顶；另一端称为栈底，不能随意操作。

错误的是 I、III、IV。

答案：C

1. 【2024-02】与表达式 x+y∗(z−u)/v 等价的后缀表达式是

A. xyzu−∗v/+

B. xyzu−v/∗+

C. +x/∗y−zuv

D. +x∗y/−zuv

解析

按运算次序逐层转换：

1. 括号中的 转换为 zu-；
2. 转换为 yzu-*；
3. 再除以 v，得到 yzu-*v/；
4. 最后与 x 相加，得到 xyzu-*v/+。

后缀表达式不需要括号，运算符紧跟在对应的两个操作数之后。

答案：A