二、综合应用题
## 二、综合应用题
01. 假设一个算术表达式中包含圆括号，方括号和花括号 3 种类型的括号，编写一个算法来判别表达式中的括号是否配对，以字符 “\0” 作为算术表达式的结束符。
## 3.3.7 答案与解析
### 一、单项选择题
01. D
缓冲区是用队列实现的，选项 A、B、C 都是线的典型应用。
<!-- page: 109 -->
第3章 栈、队列和数组
02. B
后缀表达式中，每个运算符均直接位于其两个操作数的后面，按照这样的方式逐步根据计算的优先级将每个计算式进行变换，即可得到后缀表达式。
【另解】将两个直接操作数用括号括起来，再将操作符提到括号后，最后去掉括号。例如，对于 $(\mathbb{Q} = \mathbb{Q}\mathbf{a}^{*}(\mathbb{Q}\mathbf{b} + \mathbf{c})) - \mathbf{d})$ ，提出操作符并去掉括号后，可得后缀表达式为 $\mathrm{abc} + *\mathrm{d}-$ 。
学完第5章后，可将表达式画成二叉树的形式，再用后序遍历即可求得后缀表达式。
03. D
FIFO页面替换算法用到了队列。其余的都只用到了栈。
04. B
利用栈求表达式的值时，可以分别设立运算符栈和运算数栈，其原理不变。选项B中A入栈，B入栈，计算得R1，C入栈，计算得R2，D入栈，计算得R3，由此得栈深为2。选项A、C、D依次计算得栈深为4、3、3。因此选择选项B。
## 技巧
根据运算符优先级，统计已依次入栈但还未参与计算的运算符数。以选项C为例，当“（”“A”“-”入栈时，“（”和“-”还未参与运算，此时运算符栈大小为2，“B”和“*”入栈时运算符大小为3，“C”入栈时“B*C”运算，运算符栈大小为2，以此类推。
05. B
栈与递归有着紧密的联系。递归模型包括递归出口和递归体两个方面。递归出口是递归算法的出口，即终止递归的条件。递归体是一个递推的关系式。根据题意有
$$
f (0) = 2;
$$
$$
f (1) = 1 * f (0) = 2;
$$
$$
f (f (1)) = f (2) = 2 * f (1) = 4。
$$
06. C
计算F(8)的递归调用树如右图所示：
由图可知，递归函数F()调用的次数为9。
07. C
首先，执行内层参数 func(5)=func(3)+
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
func(1)=4，共执行3次func函数。然后，执行func(func(5))=func(4)=func(2)+
func(0)=4，因此第4个被执行的func函数是func(4)。也可以采用画出递归调用树的方式，即某个函数的执行次序等于其在递归调用树的先序遍历中的次序。
08. B
通常情况下，递归算法在计算机实际执行的过程中包含很多的重复计算，所以效率会低。
09. C
调用函数时，系统会为调用者构造一个由参数表和返回地址组成的活动记录，并将记录压入系统提供的栈中，若被调用函数有局部变量，也要压入栈中。
10. B
本题涉及第5章和第6章的内容，图的广度优先搜索类似于树的层序遍历，都要借助于队列。
11. A
使用栈可以模拟递归的过程，以此来消除递归，但对于单向递归和尾递归而言，可以用迭代的方式来消除递归，选项A正确。不同的入栈和出栈组合操作，会产生许多不同的输出序列，B
<!-- page: 110 -->
2027年数据结构考研复习指导
错误。通常使用栈来处理函数或过程调用，选项C错误。队列和栈都是操作受限的线性表，但只有队列允许在表的两端进行运算，而栈只允许在栈顶方向进行操作，选项D错误。
## 12. B
在提取数据时必须保持原来数据的顺序，所以缓冲区的特性是先进先出。
## 13. A
在中缀表达式转后缀表达式的过程中，扫描到操作数时直接输出，扫描到操作符时根据其优先级进行相应的出入栈操作。有几点需要注意：①若遇到界限符“（”，则直接入栈；②若遇到界限符“）”，则不入栈，且依次弹出栈顶运算符，直到遇到“（”为止，并删除“（”；③若当前运算符的优先级高于栈顶运算符或遇到栈顶为“（”，则直接入栈；④若当前运算符的优先级低于或等于栈顶运算符，则依次弹出栈中的运算符并加入后缀表达式，直到遇到一个优先级低于它的运算符或遇到“（”或栈空为止，之后将当前运算符入栈。
求栈中操作符的最大个数时，为简单起见，可省略对操作数的处理。
| 步 | 待处理运算符 | 栈 | 扫描运算符 | 动 作 |
| --- | --- | --- | --- | --- |
| 1 | +b-a*((c+d)/e-f)+g | | + | +入栈 |
| 2 | -a*((c+d)/e-f)+g | + | - | -优先级等于栈顶+，弹出+，-入栈 |
| 3 | *((c+d)/e-f)+g | - | * | *优先级高于栈顶-，*入栈 |
| 4 | ((c+d)/e-f)+g | -* | ( | (直接入栈 |
| 5 | (c+d)/e-f)+g | -* | ( | (直接入栈 |
| 6 | +d)/e-f)+g | -* | + | 栈顶为(，+直接入栈 |
| 7 | )/e-f)+g | -* | + | 遇到)，弹出+，删除( |
| 8 | /e-f)+g | -* | / | 栈顶为(，/直接入栈 |
| 9 | -f)+g | -* | - | -优先级低于栈顶/，弹出/，-入栈 |
| 10 | )+g | -* | ) | 遇到)，弹出-，删除( |
| 11 | +g | -* | + | +优先级低于栈顶*，等于-，依次弹出*和-；+入栈 |
| 12 | | + | | |
由上述过程可知，栈中操作符的最大个数为5。
## 14. B
中缀表达式 $a / b + (c * d - e * f) / g$ 转换为后缀表达式的过程如下：
| 步 | 待处理序列 | 栈 | 后缀表达式 | 扫描项 | 动 作 |
| --- | --- | --- | --- | --- | --- |
| 1 | a/b+(c*d-e*f)/g | | | a | a加入后缀表达式 |
| 2 | /b+(c*d-e*f)/g | | a | / | /入栈 |
| 3 | b+(c*d-e*f)/g | / | a | b | b加入后缀表达式 |
| 4 | +(c*d-e*f)/g | / | ab | + | +优先级低于栈顶的/，弹出/，+入栈 |
| 5 | (c*d-e*f)/g | + | ab/ | ( | (入栈 |
| 6 | c*d-e*f)/g | +( | ab/ | c | c加入后缀表达式 |
| 7 | *d-e*f)/g | +( | ab/c | * | 栈顶为(，*入栈 |
| 8 | d-e*f)/g | +(* | ab/c | d | d加入后缀表达式 |
| 9 | -e*f)/g | +(* | ab/cd | - | -优先级低于栈顶的*，弹出*。-入栈 |
| 10 | e*f)/g | +(- | ab/cd* | e | e加入后缀表达式 |
| 11 | *f)/g | +(- | ab/cd*e | * | *优先级高于栈顶的-，*入栈 |
| 12 | f)/g | +(-* | ab/cd*e | f | f加入后缀表达式 |
| 13 | )/g | +(-* | ab/cd*ef | ) | 遇到)，依次弹出*、 -加入表达式，删除( |
| 14 | /g | + | ab/cd*ef*- | / | /优先级高于栈顶的+，/入栈 |
| 15 | g | +/ | ab/cd*ef*- | g | g加入后缀表达式 |
| 16 | | +/ | ab/cd*ef*-g | | 扫描完毕，运算符依次弹出加入表达式 |
| 17 | | | ab/cd*ef*-g/+ | | 完成 |
<!-- page: 111 -->
第3章 栈、队列和数组
99
由此可知，当扫描到 $f$ 时，栈中的元素依次是 $+(-*)$。
【另解】采用手算方法，得出中缀式 $a / b + (c * d - e * f) / g$ 对应的后缀式为 $ab / cd * ef * -g / +$。中缀表达式转后缀表达式时，操作数都直接输出，因此操作数的顺序是固定的。扫描到 $f$ 时，在后缀表达式 $f$ 后面的运算符要么还未入栈，要么还在栈中，需要结合中缀式来判断，$f$ 后面依次出栈的运算符为 $+/-/+$，/在中缀表达式 $f$ 之后，此时还未入栈，因此栈中的运算符（从栈底到栈顶）为 $+-*$；此外，已入栈的界限符（此时还未消解，因此（也还在栈中，栈中的元素依次是 $+(-*)$。
## 15. A
递归调用函数时，在系统栈中保存的函数信息需满足先进后出的特点，依次调用了 main(), S(1), S(0)，所以栈底到栈顶的信息依次是 main(), S(1), S(0)。
## 注意
在递归中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来存储。
## 16. C
根据题意：入队顺序为8, 4, 2, 5, 3, 9, 1, 6, 7，出队顺序为 $1 \sim 9$。入口和出口之间有多个队列（$n$ 条轨道），且每个队列（轨道）可容纳多个元素（多列列车），为便于区分，队列用字母编号。分析如下：显然先入队的元素必须小于后入队的元素（否则，若8和4入同一个队列，8在4前面，则出队时也只能8在4前面），这样8入队列A，4入队列B，2入队列C，5入队列B（按照前述原则“大的元素在小的元素后面”也可将5入队列C，但这时剩下的元素3就必须放入一个新的队列中，无法确保“至少”），3入队列C，9入队列A，这时共占了3个队列，后面还有元素1，直接再用一个新的队列D，1从队列D出队后，剩下的元素6和7或入队列B，或入队列C。综上，共占用了4个队列。当然还有其他的入队、出队情况，请读者自己推演，但要确保满足：①队列中后面的元素大于前面的元素；②确保占用最少（满足题意中“至少”）的队列。
## 17. C
说法I的反例：计算斐波那契数列迭代实现只需要一个循环即可实现。说法III的反例：入栈序列为1,2，进行Push, Push, Pop, Pop操作，出栈次序为2、1；进行Push, Pop, Push, Pop操作，出栈次序为1,2。说法IV，栈是一种受限的线性表，只允许在一端进行操作。说法II正确。
## 18. B
第一次调用：① 从 S1 中弹出 2 和 3；② 从 S2 中弹出 +；③ 执行 $3 + 2 = 5$；④ 将 5 压入 S1 中，第一次调用结束后 S1 中剩余 5、8、5（5 在栈顶），S2 中剩余 *、-（-在栈顶）。第二次调用：① 从 S1 中弹出 5 和 8；② 从 S2 中弹出 -；③ 执行 $8 - 5 = 3$；④ 将 3 压入 S1 中，第二次调用结束后 S1 中剩余 5、3（3 在栈顶），S2 中剩余 *。第三次调用：① 从 S1 中弹出 3 和 5；② 从 S2 中弹出 *；③ 执行 $5 * 3 = 15$；④ 将 15 压入 S1 中，第三次调用结束后 S1 中仅剩余 15，S2 为空。
## 19. A
根据中缀表达式画出对应的二叉树如右图所示，对该二叉树进行后序遍历即可得到后缀表达式为 $xyzu^{-*v/+}}$。本题也可采用本书前面描述的手算方法。
## 20. D
该算法利用栈来检查括号匹配：遇到左括号时入栈，遇到右括号时出栈并与之匹配。由于栈的容量为3，因此最多只能容纳3个未匹配的左括号，即最多支持3层嵌套的括号结构。逐项分析各选项的括号嵌套深度：对于选项A，括号序列为 $([()])$，最大嵌套深度为3，依次入栈 $([(),
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 112 --> 2027年数据结构考研复习指导 未超过栈容量。对于选项B，括号序列为[（（）]，最大深度为3，依次入栈[（，栈容量足够。对于选项C，括号序列为[（（）]，同样最大深度为3，栈容量足够。对于选项D，括号序列为[（[（）]]，最大嵌套深度达到4。扫描至*后的(时，栈中已存有[（三个左括号，此时，需要将第四个左括号(入栈，但栈容量仅为3，无法继续入栈，因此该表达式无法被正确处理。 ## 二、综合应用题 ### 01. 【解答】 括号匹配是栈的一个典型应用，给出这道题是希望读者好好掌握栈的应用。算法的基本思想是扫描每个字符，遇到花、方、圆的左括号时入栈，遇到花、方、圆的右括号时检查栈顶元素是否为相应的左括号，若是，出栈，否则配对错误。最后栈若不为空也为错误。### 3.4 数组和特殊矩阵 矩阵在图形学、工程计算等领域占有重要地位。在数据结构中，关注的重点并非矩阵本身的数学性质及其运算，而是如何以最小的内存空间高效存储矩阵，并支持对元素的便捷访问。 #### 3.4.1 数组的定义 数组是由 $n \ (n \geqslant 1)$ 个相同类型的数据元素组成的有限序列。每个元素称为数组元素，其在线性序列中的位置由下标标识，下标的取值范围称为维界。 <!-- page: 113 --> 第3章 栈、队列和数组 101 数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表；二维数组可视为其元素为定长一维数组的线性表；更高维数组以此类推。数组一旦定义，其维数与维界即固定不变。因此，除初始化和销毁外，数组仅支持存取元素和修改元素两种基本操作。 ## 3.4.2 数组的存储结构 大多数编程语言提供数组类型，逻辑上的数组通常映射为内存中一段连续的存储空间。 以一维数组 $\mathrm{A}[0\dots n - 1]$ 为例，设每个元素占 $L$ 个存储单元，则元素 $\mathrm{A}[i]$ 的地址为 $$ \mathrm{LOC}(a_i) = \mathrm{LOC}(a_0) + iL \quad (0 \leqslant i < n) $$ **导航图2** ▶ 二维数组按行优先存储的下标对应关系（2021） 多维数组在内存中需按某种顺序展开为一维。常见方式有按行优先和按列优先。 **按行优先**：先行后列，先存储行号较小的元素；同一行内，先存储列号较小的元素。 设二维数组行下标与列下标范围分别为 $[0, h_1]$ 与 $[0, h_2]$，则元素 $\mathrm{A}[i][j]$ 的地址为 $$ \mathrm{LOC}(a_{i,j}) = \mathrm{LOC}(a_{0,0}) + [i(h_2 + 1) + j]L $$ 例如，数组 $\mathrm{A}_{[2][3]}$ 按行优先存储的形式如图 3.18 所示。 $$ \mathrm{A}_{[2][3]} = \begin{bmatrix} a_{[0][0]} & a_{[0][1]} & a_{[0][2]} \\ a_{[1][0]} & a_{[1][1]} & a_{[1][2]} \\ \end{bmatrix} \begin{bmatrix} a_{[0][0]} & a_{[0][1]} & a_{[0][2]} & a_{[1][0]} & a_{[1][1]} & a_{[1][2]} \\ \hline \text{第1行} & & \text{第2行} \\ \end{bmatrix} $$ 图 3.18 二维数组按行优先顺序存放 **按列优先**：先列后行，先存储列号较小的元素；同一列内，先存储行号较小的元素。 其对应的地址公式为 $$ \mathrm{LOC}(a_{i,j}) = \mathrm{LOC}(a_{0,0}) + [j(h_1 + 1) + i]L $$ 例如，数组 $\mathrm{A}_{[2][3]}$ 按列优先存储的形式如图 3.19 所示。 $$ \mathrm{A}_{[2][3]} = \begin{bmatrix} a_{[0][0]} & a_{[0][1]} & a_{[0][2]} \\ a_{[1][0]} & a_{[1][1]} & a_{[1][2]} \\ \end{bmatrix} \begin{bmatrix} a_{[0][0]} & a_{[1][0]} & a_{[0][1]} & a_{[1][1]} & a_{[0][2]} & a_{[1][2]} \\ \hline \text{第1列} & & \text{第2列} & & \text{第3列} \\ \end{bmatrix} $$ 图 3.19 二维数组按列优先顺序存放 ## 3.4.3 特殊矩阵的压缩存储 **压缩存储**：为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。 **特殊矩阵**：指具有大量相同元素或零元素，且这些元素分布具有规律性的矩阵。常见的特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵等。 **特殊矩阵的压缩存储方法**：通过分析矩阵中相同元素的分布规律，仅存储一份实际数据，其余的可通过下标映射访问，从而将原本冗余的数据压缩到一个共享的空间中，显著节省内存。 ### 1. 对称矩阵 **导航图3** ▶ 对称矩阵压缩存储的下标对应关系（2018、2020） 若 $n$ 阶矩阵 $A$ 中任意元素 $a_{i,j}$ 均满足 $a_{i,j} = a_{j,i}$ $(1 \leqslant i,j \leqslant n)$，则称其为对称矩阵。其元素可分为三部分：上三角区、主对角线和下三角区，如图 3.20 所示。 由于上三角区与下三角区完全对称，若仍用二维数组存储，将近一半空间被浪费。为此可将 $n$ 阶对称矩阵 $A$ 压缩存储于一维数组 $\mathrm{B}[n(n + 1)/2]$ 中，通常仅存放下三角部分（含主对角线）。 <!-- page: 114 --> 2027年数据结构考研复习指导bool BracketsCheck(char *str) { InitStack(S); //初始化栈 int i = 0; while (str[i] != '\0') { switch (str[i]) { //左括号入栈 case '(': Push(S, '('); break; case '[': Push(S, '['); break; case '[': Push(S, '('); break; //遇到右括号，检测栈顶 case '): Pop(S, e); if (e != '(') return false; break; case '[': Pop(S, e); if (e != '(') return false; break; case '[': Pop(S, e); if (e != '(') return false; break; default: break; //switch i++; } //while if (!StackEmpty(S)) { printf("括号不匹配\n"); return false; } else { printf("括号匹配\n"); return true; } }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.20 $n$ 阶矩阵的划分
对于元素 $a_{i,j}$ $(i\geq j)$ ，其在数组B中的位置由其前方的元素个数决定
第1行：1个元素（ $a_{1,1}$ ）。
第2行：2个元素（ $a_{2,1}, a_{2,2}$ ）。
……
第 $i - 1$ 行： $i - 1$ 个元素 $(a_{i - 1,1},a_{i - 1,2},\dots ,a_{i - 1,i - 1})$ 。
第 $i$ 行： $j - 1$ 个元素 $(a_{i,1},a_{i,2},\dots ,a_{i,j - 1})$
因此，元素 $a_{i,j}$ 在数组B中的下标 $k = 1 + 2 + \dots + (i - 1) + j - 1 = i(i - 1) / 2 + j - 1$ （数组下标从0开始）。元素下标之间的对应关系如下：
$$
k = \left\{ \begin{array}{l l} \frac {i (i - 1)}{2} + j - 1, & i \geq j \text {(下三角区和主对角线元素)} \\ \frac {j (j - 1)}{2} + i - 1, & i < j \text {(上三角区元素} a _ {i, j} = a _ {j, i}) \end{array} \right.
$$
若数组下标从1开始，则可采用类似的推导方法，请读者自行思考。