3.3 栈和队列的应用·习题
复习入口
3.3 栈和队列的应用 · 3.3.1 栈在括号匹配中的应用 · 3.3.2 栈在表达式求值中的应用 · 3.3.3 栈在递归中的应用 · 3.3.4 队列在层次遍历中的应用 · 3.3.5 队列在计算机系统中的应用
本节共20题:选择题19题,综合应用题1题。每题答案紧接题目折叠显示。
文字转录进度:20/20题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P94 · 解析P96 · 目视转录
栈的应用不包括( )。
A. 递归
B. 表达式求值
C. 括号匹配
D. 缓冲区
查看答案与解析
答案:D。
缓冲区是用队列实现的,选项 A、B、C 都是栈的典型应用。
单项选择题 02
原书题目P94 · 解析P96 · 目视转录
表达式 a*(b+c)-d 的后缀表达式是( )。
A. abcd*+-
B. abc+*d-
C. abc*+d-
D. -+*abcd
查看答案与解析
答案:B。
后缀表达式中,每个运算符均直接位于其两个操作数的后面,按照这样的方式逐步根据计算的优先级将每个计算式进行变换,即可得到后缀表达式。
【另解】将两个直接操作数用括号括起来,再将操作符提到括号后,最后去掉括号。例如,对于 (a*(b+c))-d,从内到外依次提出操作符并去掉括号后,可得后缀表达式为 abc+*d-。
学完第 5 章后,可将表达式画成二叉树的形式,再用后序遍历即可求得后缀表达式。
单项选择题 03
原书题目P94 · 解析P97 · 目视转录
下面( )用到了队列。
A. 括号匹配
B. 表达式求值
C. 递归
D. FIFO 页面替换算法
查看答案与解析
答案:D。
FIFO 页面替换算法用到了队列。其余的都只用到了栈。
单项选择题 04
原书题目P94 · 解析P97 · 目视转录
利用栈求表达式的值时,设立运算数栈 OPEN。假设 OPEN 只有两个存储单元,则在下列表达式中,不会发生溢出的是( )。
A. A-B*(C-D)
B. (A-B)*C-D
C. (A-B*C)-D
D. (A-B)*(C-D)
查看答案与解析
答案:B。
利用栈求表达式的值时,可以分别设立运算符栈和运算数栈,其原理不变。选项 B 中 A 入栈,B 入栈,计算得 R1,C 入栈,计算得 R2,D 入栈,计算得 R3,由此得栈深为 2。选项 A、C、D 依次计算得栈深为 4、3、3。因此选择选项 B。
技巧:根据运算符优先级,统计已依次入栈但还未参与计算的运算符的个数。以选项 C 为例,当“(”“A”“-”入栈时,“(”和“-”还未参与运算,此时运算符栈大小为 2,“B”和“”入栈时运算符大小为 3,“C”入栈时“BC”运算,运算符栈大小为 2,以此类推。
转录核对:题干限制的是运算数栈 OPEN 的容量。上述技巧段讨论运算符栈,不能直接作为运算数栈深度的依据;计算 OPEN 深度应统计尚未归约的操作数及中间结果。
单项选择题 05
原书题目P94 · 解析P97 · 目视转录
执行完下列语句段后, 的值为( )。
int f(int x){
return ((x>0)? x*f(x-1):2);
}
int i;
i=f(f(1));
A. 2
B. 4
C. 8
D. 无限递归
查看答案与解析
答案:B。
栈与递归有着紧密的联系。递归模型包括递归出口和递归体两个方面。递归出口是递归算法的出口,即终止递归的条件。递归体是一个递推的关系式。根据题意有
单项选择题 06
原书题目P95 · 解析P97 · 目视转录
设有如下递归函数,则计算 F(8) 需要调用该递归函数的次数为( )。
int F(int n){
if(n<=3) return 1;
else return F(n-2)+F(n-4)+1;
}
A. 7
B. 8
C. 9
D. 10
查看答案与解析
答案:C。
计算 F(8) 的递归调用树如下:
F(8)
├─ F(6)
│ ├─ F(4)
│ │ ├─ F(2)
│ │ └─ F(0)
│ └─ F(2)
└─ F(4)
├─ F(2)
└─ F(0)
由图可知,递归函数 F() 调用的次数为 9。
单项选择题 07
原书题目P95 · 解析P97 · 目视转录
设有如下递归函数,在 func(func(5)) 的执行过程中,第 4 个被执行的 func 函数是( )。
int func(int x){
if(x<=3) return 2;
else return func(x-2)+func(x-4);
}
A. func(2)
B. func(3)
C. func(4)
D. func(5)
查看答案与解析
答案:C。
首先,执行内层参数 func(5)=func(3)+func(1)=4,共执行 3 次 func 函数。然后,执行 func(func(5))=func(4)=func(2)+func(0)=4,因此第 4 个被执行的函数是 func(4)。也可以采用画出递归调用树的方式,即某个函数的执行次序等于其在递归调用树先序遍历中的次序。
单项选择题 08
原书题目P95 · 解析P97 · 目视转录
对于一个问题的递归算法求解和其相对应的非递归算法求解,( )。
A. 递归算法通常效率高一些
B. 非递归算法通常效率高一些
C. 两者相同
D. 无法比较
查看答案与解析
答案:B。
通常情况下,递归算法在计算机实际执行的过程中包含很多的重复计算,所以效率会低。
单项选择题 09
原书题目P95 · 解析P97 · 目视转录
执行函数时,其局部变量一般采用( )进行存储。
A. 树形结构
B. 静态链表
C. 栈结构
D. 队列结构
查看答案与解析
答案:C。
调用函数时,系统会为调用者构造一个由参数表和返回地址组成的活动记录,并将记录压入系统提供的栈中,若被调用函数有局部变量,也要压入栈中。
单项选择题 10
原书题目P95 · 解析P97 · 目视转录
执行( )操作时,需要使用队列作为辅助存储空间。
A. 查找散列(哈希)表
B. 广度优先搜索图
C. 前序(根)遍历二叉树
D. 深度优先搜索图
查看答案与解析
答案:B。
本题涉及第 5 章和第 6 章的内容,图的广度优先搜索类似于树的层序遍历,都要借助于队列。
单项选择题 11
原书题目P95 · 解析P97 · 目视转录
下列说法中,正确的是( )。
A. 消除递归不一定需要使用栈
B. 对同一输入序列进行两组不同的合法入栈和出栈组合操作,所得到的输出序列也一定相同
C. 通常使用队列来处理函数或过程调用
D. 队列和栈都是运算受限的线性表,只允许在表的两端进行运算
查看答案与解析
答案:A。
使用栈可以模拟递归的过程,以此来消除递归,但对于简单的递归和尾递归而言,可以用迭代的方式来消除递归,选项 A 正确。不同的入栈和出栈组合操作,会产生许多不同的输出序列,B 错误。通常使用栈来处理函数或过程调用,选项 C 错误。队列和栈都是操作受限的线性表,但只有队列允许在表的两端进行运算,而栈只允许在栈顶方向进行操作,选项 D 错误。
单项选择题 12
原书题目P95 · 解析P98 · 目视转录
【2009 统考真题】为解决计算机主机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。
A. 栈
B. 队列
C. 树
D. 图
查看答案与解析
答案:B。
在提取数据时必须保持原来数据的顺序,所以缓冲区的特性是先进先出。
单项选择题 13
原书题目P95 · 解析P98 · 目视转录
【2012 统考真题】已知操作符包括“+”“-”“*”“/”“(”和“)” 。将中缀表达式 a+b-a*((c+d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+ 时,用栈来存放暂时还不能确定运算次序的操作符。栈初始时为空时,转换过程中同时保存在栈中的操作符的最大个数是( )。
A. 5
B. 7
C. 8
D. 11
查看答案与解析
答案:A。
在中缀表达式转后缀表达式的过程中,扫描到操作数时直接输出,扫描到操作符时根据其优先级进行相应的出入栈操作。有几点需要注意:①若遇到界限符“(”,则直接入栈;②若遇到界限符“)” ,则不入栈,且依次弹出栈顶运算符,直到遇到“(”为止,并删除“(”;③若当前运算符的优先级高于栈顶运算符或遇到栈顶为“(”,则直接入栈;④若当前运算符的优先级低于或等于栈顶运算符,则依次弹出栈中的运算符并加入后缀表达式,直到遇到一个优先级低于它的运算符或遇到“(”或栈空为止。之后将当前运算符入栈。
求栈中操作符的最大个数时,为简单起见,可省略对操作数的处理。
| 步 | 扫描运算符 | 处理后的栈(底→顶) | 动作 |
|---|---|---|---|
| 1 | + | + | + 入栈 |
| 2 | - | - | - 优先级等于栈顶 +,弹出 +,- 入栈 |
| 3 | * | -* | * 优先级高于栈顶 -,* 入栈 |
| 4 | ( | -*( | ( 直接入栈 |
| 5 | ( | -*(( | ( 直接入栈 |
| 6 | + | -*((+ | 栈顶为 (,+ 直接入栈 |
| 7 | ) | -*( | 遇到 ),弹出 +,删除 ( |
| 8 | / | -*(/ | 栈顶为 (,/ 直接入栈 |
| 10 | - | -*(- | - 优先级低于栈顶 /,弹出 /,- 入栈 |
| 11 | ) | -* | 遇到 ),弹出 -,删除 ( |
| 12 | + | + | + 优先级低于栈顶 *,等于 -,依次弹出 * 和 -,+ 入栈 |
| 13 | 结束 | + | 扫描完成,余下 + 待弹出 |
由上述过程可知,栈中操作符的最大个数为 5。(步骤编号沿用原书,未列第 9 步。)
单项选择题 14
原书题目P95 · 解析P98 · 目视转录
【2014 统考真题】假设栈初始为空,将中缀表达式 a/b+(c*d-e*f)/g 转换为等价的后缀表达式的过程中,当扫描到 f 时,栈中的元素依次是( )。
A. +(*-
B. +(-*
C. /+(*-*
D. /+-*
查看答案与解析
答案:B。
中缀表达式 a/b+(c*d-e*f)/g 转换为后缀表达式的过程如下:
| 步 | 扫描项 | 栈(底→顶) | 后缀表达式 | 动作 |
|---|---|---|---|---|
| 1 | a | a | a 加入后缀表达式 | |
| 2 | / | / | a | / 入栈 |
| 3 | b | / | ab | b 加入后缀表达式 |
| 4 | + | + | ab/ | + 优先级低于栈顶 /,弹出 /,+ 入栈 |
| 5 | ( | +( | ab/ | ( 入栈 |
| 6 | c | +( | ab/c | c 加入后缀表达式 |
| 7 | * | +(* | ab/c | 栈顶为 (,* 入栈 |
| 8 | d | +(* | ab/cd | d 加入后缀表达式 |
| 9 | - | +(- | ab/cd* | - 优先级低于栈顶 *,弹出 *,- 入栈 |
| 10 | e | +(- | ab/cd*e | e 加入后缀表达式 |
| 11 | * | +(-* | ab/cd*e | * 优先级高于栈顶 -,入栈 |
| 12 | f | +(-* | ab/cd*ef | f 加入后缀表达式 |
| 13 | ) | + | ab/cd*ef- | 遇到 ),依次弹出 *、- 加入表达式,删除 ( |
| 14 | / | +/ | ab/cd*ef- | / 优先级高于栈顶 +,入栈 |
| 15 | g | +/ | ab/cd*ef-g | g 加入后缀表达式 |
| 16 | 结束 | ab/cd*ef-g | 扫描完毕,运算符依次弹出加入表达式 | |
| 17 | 完成 | ab/cd*ef-g/+ | 完成 |
由此可知,当扫描到 f 时,栈中的元素依次是 +(-*。
【另解】采用手算方法,得出中缀式 a/b+(c*d-e*f)/g 对应的后缀式为 ab/cd*ef*-/g/+。中缀表达式转后缀表达式时,操作数都直接输出,因此操作数的顺序是固定的。扫描到 f 时,在后缀表达式 f 后面的运算符要么还未入栈,要么还在栈中,需要结合中缀式来判断。f 后面依次出栈的运算符为 *-/+,/ 在中缀表达式 f 之后,此时还未入栈,因此栈中的运算符(从栈底到栈顶)为 +-*;此外,已入栈的界限符(此时还未消解,因此也还在栈中),栈中的元素依次是 +(-*。
转录核对:原书过程表从第 13 步起漏写后缀表达式中的乘号
*;上表保留其显示内容,正确完整结果为另解中的ab/cd*ef*-/g/+,不影响本题答案 B。
单项选择题 15
原书题目P95 · 解析P99 · 目视转录
【2015 统考真题】已知程序如下:
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()
查看答案与解析
答案:A。
递归调用函数时,在系统栈中保存的函数信息需满足先进后出的特点,依次调用了 main()、S(1)、S(0),所以栈底到栈顶的信息依次是 main()、S(1)、S(0)。
注意:在递归中,系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来存储。
单项选择题 16
原书题目P96 · 解析P99 · 目视转录
【2016 统考真题】设有如下图所示的火车车轨,入口和出口之间有 条轨道,列车的行进方向均为从左至右,列车可驶入任意一条轨道。现有编号为 1~9 的 9 列列车,驶入的次序依次是 8、4、2、5、3、9、1、6、7。若期望驶出的次序依次为 1~9,则 至少是( )。
┌──→ 轨道1 ──→┐
入口 ───→ 分岔 … 合流 ───→ 出口
└──→ 轨道n ──→┘
各轨道上列车保持进入的先后顺序,均向右行驶。
A. 2
B. 3
C. 4
D. 5
查看答案与解析
答案:C。
根据题意:入队顺序为 8、4、2、5、3、9、1、6、7,出队顺序为 1~9。入口和出口之间有多个队列( 条轨道),且每个队列(轨道)可容纳多个元素(多列列车),为便于区分,队列用字母编号。
分析如下:显然先入队的元素必须小于后入队的元素(否则,若 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
原书题目P96 · 解析P99 · 目视转录
【2017 统考真题】下列关于栈的叙述中,错误的是( )。
Ⅰ. 采用非递归方式重写递归程序时必须使用栈
Ⅱ. 函数调用时,系统要用栈保存必要的信息
Ⅲ. 只要确定了入栈次序,即可确定出栈次序
Ⅳ. 栈是一种受限的线性表,允许在其两端进行操作
A. 仅Ⅰ
B. 仅Ⅰ、Ⅱ、Ⅲ
C. 仅Ⅰ、Ⅲ、Ⅳ
D. 仅Ⅱ、Ⅲ、Ⅳ
查看答案与解析
答案:C。
Ⅰ的反例:计算斐波那契数列迭代实现只需要一个循环即可实现。Ⅲ的反例:入栈序列为 1、2,进行 Push、Push、Pop、Pop 操作,出栈次序为 2、1;进行 Push、Pop、Push、Pop 操作,出栈次序为 1、2。Ⅳ,栈是一种受限的线性表,只允许在一端进行操作。Ⅱ正确。
单项选择题 18
原书题目P96 · 解析P99 · 目视转录
【2018 统考真题】若栈 S1 中保存整数,栈 S2 中保存运算符,函数 F() 依次执行下述各步骤操作:
- 从 S1 中依次弹出两个操作数 a 和 b。
- 从 S2 中弹出一个运算符 op。
- 执行相应的运算 b op a。
- 将运算结果压入 S1 中。
假定 S1 中的操作数依次是 5、8、3、2(2 在栈顶),S2 中的运算符依次是 *、-、+(+ 在栈顶)。调用 3 次 F() 后,S1 栈顶保存的值是( )。
A. -15
B. 15
C. -20
D. 20
查看答案与解析
答案: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 中弹出 ;③执行 53=15;④将 15 压入 S1 中。第三次调用结束后 S1 中仅剩余 15,S2 为空。
单项选择题 19
原书题目P96 · 解析P99 · 目视转录
【2024 统考真题】与表达式 x+y*(z-u)/v 等价的后缀表达式是( )。
A. xyzu-*v/+
B. xyzu-v/*+
C. +x/*y-zuv
D. +x*y/-zuv
查看答案与解析
答案:A。
根据中缀表达式画出对应的二叉树:
+
/ \
x /
/ \
* v
/ \
y -
/ \
z u
对该二叉树进行后序遍历即可得到后缀表达式为 xyzu-*v/+。本题也可采用本节前面描述的手算方法。
综合应用题
综合应用题 01
原书题目P96 · 解析P99 · 目视转录
假设一个算术表达式中包含圆括号、方括号和花括号 3 种类型的括号,编写一个算法来判别表达式中的括号是否配对,以字符 \0 作为算术表达式的结束符。
查看答案与解析
整理注记
实现时,遇到右括号应先检查栈非空,或检查Pop是否成功,再比较弹出的括号。若直接忽略空栈弹出失败,可能使用未赋值的变量。扫描结束还应检查栈为空。
括号匹配是栈的一个典型应用,给出这道题是希望读者好好掌握栈的应用。
算法的基本思想是扫描每个字符,遇到花、方、圆的左括号时入栈;遇到花、方、圆的右括号时检查栈顶元素是否为相应的左括号,若是,出栈,否则配对错误。最后栈若不为空也为错误。
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(!IsEmpty(S)){
printf("括号不匹配\n");
return false;
}
else{
printf("括号匹配\n");
return true;
}
}
转录核对:原书 push/Pop/pop 的大小写不统一,使用时应统一为所定义的栈接口;S、e 的声明亦需按接口补全。右括号出现时还须先判栈空或检查 Pop 成功,避免在失败后读取未定义的 e。