1. 栈的应用不包罗( D F )。
A. 递归 B. 进制转换 C. 迷宫求解
D. 缓冲区队列 E. 括号匹配 F.页面更换算法
解：缓冲区和页面更换算法中的 FIFO 都用队列实现。
2. 【2009统考真题】为解决计算机主机与打印机之间速率不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( B )。
A. 栈 B. 队列 C. 树 D. 图
3. 表达式 a*(b+c)-d 的后缀表达式是( B )。
A. abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd
解： 画出运算式对应的表达式树，用后序遍历该树得出后缀表达式。选B，如下图：
4. 使用栈求表达式的值时，设立运算数栈 OPEN，假设 OPEN 只有两个存储单元，则在下列表达式中，不会发生溢出的是( B )。
A. A-B*(C-D) B. (A-B)*C-D C. (A-B*C)-D D. (A-B)*(C-D)
解： 使用栈求表达式的值时，可分别设立运算符栈和运算数栈，其原理稳固。 对选项B：
A入栈，B入栈，计算 A - B 得 R1；
C入栈，计算 R1* C 得 R2；
D入栈，计算 R2 - D 得 R3，由此栈深为 2 。符合题意，不会发生溢出。 对选项A：
A入栈，B入栈，C入栈，D入栈，计算 C - D 得 R1；可知栈深为4。溢出。 对选项C：
A入栈，B入栈，C入栈，计算 B * C，得 R1；可知栈深为3。溢出。 对选项D：
A入栈，B入栈，计算 A - B 得 R1；
C入栈，D入栈，此时栈中有 R1 C D，可知栈深为3。溢出。
5. 下列说法中，精确的是（ A ）
A. 消除递归不肯定需要使用栈
B. 对同一输入序列举行两组差别的正当入栈和出栈组合操纵，所得的输出序列也肯定相同
C. 通常使用队列来处置惩罚函数或过程调用
D. 队列和栈都是运算受限的线性表，只允许在表的两头举行运算
解：使用栈可以模仿递归的过程，以此来消除递归，但对于单向递归和尾递归而言，可以用选代方式来消除递归，A对；
差别的进栈和出栈组合操纵，会产生许多差别的输出序列，B错；
通使用栈来处置惩罚函数或过程调用，C错；
队列和栈都是操纵受限的线性表， 但只有队列允许在表两头举行运算。 而栈只允许在栈顶方向举行操纵，D错。
6. 【2012 统考真题】已知操纵符包罗+、一、*、 /、(和)。将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式 ab+acd+e/f-*-g+ 时，用栈来存放临时还不可以或许定运算序次的操纵符。若栈初始时为空，则转换过程中同时保存在栈中的操纵符的最大个数是( A )。
A. 5 B. 7 C. 8 D. 9
解：将中缀表达式转换为等价的后缀表达式：（算法头脑可参考第7题）
可知在转换过程中同时保存在栈中的操纵符的最大个数是 5 个，此时栈中元素为 -*((+
待处置惩罚序列
栈
后缀表达式
当前扫描
动作
a+b-a*((c+d)/e-f)+g
a
a 加入后缀表达式
+b-a*((c+d)/e-f)+g
a
+
+入栈
b-a*((c+d)/e-f)+g
+
a
b
b 加入后缀表达式
-a*((c+d)/e-f)+g
+
ab
-
-优先级低于栈顶的+，弹出+
-a*((c+d)/e-f)+g
ab+
-
-入栈
a*((c+d)/e-f)+g
-
ab+
a
a 加入后缀表达式
*((c+d)/e-f)+g
-
ab+a
*
*优先级高于栈顶的-，*入栈
((c+d)/e-f)+g
-*
ab+a
(
(入栈
(c+d)/e-f)+g
-*(
ab+a
(
(入栈
c+d)/e-f)+g
-*((
ab+a
c
c 加入后缀表达式
+d)/e-f)+g
-*((
ab+ac
+
栈顶 ( 的优先级低于+，+入栈
d)/e-f)+g
-*((+
ab+ac
d
d 加入后缀表达式
)/e-f)+g
-*((+
ab+acd
)
把栈中第二个 ( 之前符号加入表达式
/e-f)+g
-*((
ab+acd+
/
栈顶 ( 的优先级低于/，/入栈
e-f)+g
-*(/
ab+acd+
e
e 加入后缀表达式
-f)+g
-*(/
ab+acd+e
-
栈顶 / 的优先级高于-，弹出/
-f)+g
-*(
ab+acd+e/
-
栈顶 ( 的优先级低于-，-入栈
f)+g
-*(-
ab+acd+e/
f
f 加入后缀表达式
)+g
-*(-
ab+acd+e/f
)
把栈中 ( 之前的符号加入表达式
+g
-*
ab+acd+e/f-
+
栈顶 * 的优先级高于+，弹出*
+g
-
ab+acd+e/f-*
+
栈顶 - 的优先级高于+，弹出-
+g
ab+acd+e/f-*-
+
+入栈
g
+
ab+acd+e/f-*-
g
g 加入后缀表达式
+
ab+acd+e/f-*-g
扫描完毕，运算符依次退栈加入表达式
ab+acd+e/f-*-g+
完成
7. 【2014统考真题】假设栈初始为空，将中缀表达式 a/b+(c*d-e*f)/g 转换为等价的后缀表达式的过程中，当扫描到 f 时，栈中的元素依次是( B ).
A. + ( * - B. + ( - * C. / + ( * - * D. / + - *
解：将中缀表达式转换为后缀表达式的算法头脑如下:
（1）从左向右开始扫描中缀表达式;
（2）遇到数字时，加入后缀表达式;
（3）遇到运算符时:
a. 若为 '('，入栈；
b. 若为 ')'，则依次把栈中的运算符加入后缀表达式，直到出现 '('，从栈中删除 '('；
c. 若为除括号外的其他运算符，当其优先级高于除 '(' 外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处置惩罚的运算符优先级高和优先级相称的运算符，直到一个比它优先级低的或遇到了一个左括号为止。
（4）当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。
