第四章 栈和队列习题
一 判断题(y/n)nyynnynnn
1做进栈运算时应先判别,栈是否为空。
2,做退栈运算时应先判别,栈是否为空。
3,当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为n.
4,为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存 空间时，应将两栈的栈顶分别设在着片内存空间的两端。
5, 只有当两个基本栈的栈底在栈空间的某一位置相遇时，才产生上溢。
6, 栈是一种线性表，它的特点是后进先出。
7, 设一数列的顺序为1,2,3,4,5,6, 通过栈结构可以排成的顺序必须是3,2,5,6,4,1.
8, 设有一个空栈，栈顶指针为1000H(十六进制，下同），现有输入序列1,2,3,4,5,经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列是2,1.
9, 设有一个空栈，栈顶指针为1000H(十六进制，下同），现有输入序列1,2,3,4,5,经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后,栈顶指针是不是1005H.
二 单选题 (请从下列A，B，C，D选项中选择一项） 1,栈的特点是：
先进先出 后进先出 进优于出 出优于进
2，队列的特点是：
先进先出 后进先出 进优于出 出优于进
3,栈与队列都是： 顺序存储的线性结构 链式存储的线性结构 限制存取点的线性结构 限制存取点的非线性结构
4,若进栈序列为1，2，3，4，则（）不可能是一个出栈序列。 3，2，1，4 3，2，4，1 4，2，3，1 4，3，2，1 1，2，3，4
1，3，2，4
5,若进栈队列的序列为1，2，3，4，则（）是一个出队列序列。 3，2，1，4 3，2，4，1 4，2，3，1 4，3，2，1 1，2，3，4 1，3，2，4
6,若一个栈的输入序列是：1，2，3，...,n，输出序列的第一个元素是n，则第i个输出元素是： 不确定 n-i
n-i+1 i n-i-1
三 编程题
1，以flag为标志位，写出循环队列中插入算法 2，以flag为标志位，写出循环队列中删除算法
4-2 改写顺序栈的进栈成员函数Push (x )，要求当栈满时执行一个stackFull ( )操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置。
【解答】template
template
Type * temp = new Type [ 2 * maxSize ]; //创建体积大一倍的数组
for ( int i = 0; i <= top; i++ ) //传送原数组的数据 temp[i] = elements[i];
delete [ ] elements; //删去原数组
maxSize *= 2; //数组最大体积增长一倍
elements = temp; //新数组成为栈的数组空间 }
4-3 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：
(1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?
(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出\进栈\或\出栈\的序列)。
【解答】
(1) 可能的不同出栈序列有 种。
(2) 不能得到435612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。
154623也是这种情况。出栈序列325641和135426可以得到。 3 2 1
2 1
1
5 4 1
4 1
6 4 1
4 1
1
3 32 32 325 325 3256 32564 325641 1
1 1 13 135 1354 13542 13542 135426
3 2
5 4 2
4 2
2
6
4-4 试证明：若借助栈可由输入序列1, 2, 3, …, n得到一个输出序列p1, p2, p3, …, pn (它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i < j < k，使得pj < pk < pi。(提示：用反证法) 【解答】
因为借助栈由输入序列1, 2, 3, …, n，可得到输出序列p1, p2, p3, …, pn ，如果存在下标i, j, k，满足i < j < k，那么在输出序列中，可能出现如下5种情况： ? i进栈，i出栈，j进栈，j出栈，k进栈，k出栈。此时具有最小值的排在最前面pi位置，具有中间值的排在其后pj位置，具有最大值的排在pk位置，有pi < pj < pk, 不可能出现pj < pk < pi的情形； i进栈，i出栈，j进栈，k进栈，k出栈，j出栈。此时具有最小值的排在最前面pi位置，具有最大值的排在pj位置，具有中间值的排在最后pk位置，有pi < pk < pi , 不可能出现pj, pk < pi的情形；
? i进栈，j进栈，j出栈，i出栈，k进栈，k出栈。此时具有中间值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj < pi < pk, 不可能出现pj < pk < pi的情形； ˉ i进栈，j进栈，j出栈，k进栈，k出栈，i出栈。此时具有中间值的排在最前面pi 位置，具有最大值的排在其后pj位置，具有最小值的排在pk位置，有pk < pi < pj, 也不可能出现pj < pk < pi的情形；
° i进栈，j进栈，k进栈，k出栈，j出栈，i出栈。此时具有最大值的排在最前面pi 位置，具有中间值的排在其后pj位置，具有最小值的排在pk位置，有pk < pj < pi, 也不可能出现pj < pk < pi的情形；
4-5 写出下列中缀表达式的后缀形式： (1) A * B * C
(2) - A + B - C + D (3) A* - B + C
(4) (A + B) * D + E / (F + A * D) + C
(5) A && B|| ! (E > F) {注：按C++的优先级) (6) !(A && !( (B < C)||(C > D) ) )||(C < E) 【解答】 (1) A B * C *
(2) A - B + C - D + (3) A B - * C +
(4) A B + D * E F A D * + / C + (5) A B && E F > ! ||
(6) A B C < C D > || ! && ! C E < ||
4-7 设表达式的中缀表示为a * x - b / x↑2，试利用栈将它改为后缀表示ax * bx2↑/ -。写出转换过程中栈的变化。 【解答】
步序 0 1 2
扫描项 项类型 动 作
栈的变化 # # # *
输 出
a *
? '#' 进栈, 读下一符号 a a
操作数 ? 直接输出, 读下一符号
操作符 ? isp ( ' # ' ) < icp ( ' * ' ), 进栈, 读下
一符号 操作数 ? 直接输出, 读下一符号
操作符 ? isp ( ' * ' ) > icp ( ' - ' ), 退栈输出
? isp ( ' # ' ) < icp ( ' - ' ), 进栈, 读下一符号
3 4
x -
# * # # -
a x a x * a x *
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第三章 栈和队列习题与解析good在线全文阅读。
相关推荐：