第三章栈和队列
一、单项选择题
参考答案：1A6B11D2B7D12A3C8D13A4A9C14D5B10A15C
二、填空题
参考答案：1先进后出2先进先出3队尾，队头4栈顶指针5栈顶指针6MaxSize17top08空栈9栈顶指针10pli
ktop，topp11toptopli
k12Qfro
tQrear13Qrear1MaxSizeQfro
t14队尾指针15空，只含有一个结点16fro
trearfro
tNULL或者fro
trearrearNULL17两端183x251915203
三、判断题
参考答案：1是6否11否16否2是7否12是3否8是13否4是9否14是5是10否15否
四、运算题
参考答案：1根据以上规则，给出计算中缀表达式abcde时两个栈的变化。步0123456abc操作数操作符操作数操作符操作数操作符扫描项项类型动作OPND栈OPTR栈aaabababcas1
OPTR栈与OPND栈初始化‘’进OPTR栈取第一个符号a进OPND栈取下一符号icp‘’isp‘’进OPTR栈取下一符号b进OPND栈取下一符号icp‘’isp‘’进OPTR栈取下一符号c进OPND栈取下一符号icp‘’isp‘’退OPND栈‘c’退OPND栈‘b’退OPTR栈‘’计算bc→s1结果进OPND栈icp‘’isp‘’退OPND栈‘s1’退OPND栈‘a’退OPTR栈‘’计算as1→s2结果进OPND栈
7
同上
同上
s2

f89101112
同上de
同上操作数操作符操作数操作符
icp‘’isp‘’进OPTR栈取下一符号d进OPND栈取下一符号icp‘’isp‘’进OPTR栈取下一符号e进OPND栈取下一符号icp‘’isp‘’退OPND栈‘e’退OPND栈‘d’退OPTR栈‘’计算de→s5结果进OPND栈icp‘’isp‘’退OPND栈‘s3’退OPND栈‘s2’退OPTR栈‘’计算s2s3→s4结果进OPND栈icp‘’isp‘’退OPND栈‘s4’结束
s2s2ds2ds2des2s3

13
同上
同上
s4

14
同上
同上

2
利用运算符优先数，画出将中缀表达式abcde改为后缀表达式时运算符栈OPTR的变化。扫描项abc同上同上de同上项类型操作数操作符操作数操作符操作数操作符同上同上操作数操作符操作数操作符同上动进栈读下一符号直接输出读下一符号ispicp进栈读下一符号直接输出读下一符号ispicp进栈读下一符号直接输出读下一符号ispicp退栈输出ispicp退栈输出ispicpr