《数据结构》习题汇编03-第三章-栈与队列-试题(答案)

《《数据结构》习题汇编03-第三章-栈与队列-试题(答案)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第三章栈和队列一、单项选择题参考答案：1.A2.B6.B7.D11.D12.A3.C4•A5.B8.D9.c10.A13•A14•D15-C二、填空题参考答案:1.先进后出2.先进先出3•队尾，队头4・栈顶指针5.栈顶指针6.MaxSize-17•top==08.空栈9・栈顶指针10•p->link=top，top=p12.Q.front==Q.rear13.（Q.rear+1）%MaxSize==Q.front16.front==17•两端rear&&front!=NULL或者front==rear&&rear!=NULL18.3x2+*5-19.1520.3三、判断题参考答案：1.是2

2、・是3.否4・是5・是6・否7・否8.是9・否10.否11.否12.是13.否14.是15.否16.否11•top=top->link14・队尾指针15.空，只含有一个结点四.运算题参考答案：d/e时两个栈的变化。1.根据以上规则，给出汁算中缀表达式4+b*步扫描项项类型动作OPND栈OPTR栈0OPTR栈与OPND栈初始化，、#，进OPTR栈，#取第一个符号1a操作数3进OPND栈，取下一符号a#2+操作符icp（'+，）>isp（'#'）,进OPTR栈，取a#+下一符号3b操作数b进OPND栈，取下一符号ab#+4*操作符icp（'★，）>isp（、+，）z进OPTR栈，取ab#+*下

3、一符号5c操作数c进OPND栈，収下一符号abc#+*6—操作符icp（、一）isp('#')下一符号,进OPTR栈，取S2#-9d操作数d进OPND栈，取下一符号S2d#-10/操作符icp(、/，)>isp('-z),进OPTR栈，取S2d#-/下一符号11e操作数e进OPND栈，取下一符号s2de#-/12#操作符icp

4、('#‘)

5、a栈，读下一符号3b操作数直接输出，读下一符号#+ab4★操作符isp(1+1)icp()，退#+abc*栈输出7同上同上isp(1+1)>icp(),退#abc*+栈输出1+*8同上同上isp(*#*)icp(*#!)，退#-

6、abc*+d2栈输出'/*e/1同上同上isp()>icp(■和），退#abc*+d3栈输出e/-1同上同上isp(•#*)==icp(*#*)z结#abc*+d4束e/-3.画出对后缀算术表达式3bc*+de/-求值吋运算对象栈OPND的变化步扫描项项类型动作OPND栈1置空栈空2a操作数进栈a3b操作数进栈ab4c操作数进栈abc5★操作符c、b退栈，计算b*C,结果S1进栈aSi6+操作符Sisa退栈，计算a；+S1，结果s2进栈S27d操作数进栈s2d8e操作数进栈s2de9/操作符ad退栈，计算d/e,结果S3进栈S2S310操作符S3、S2退栈，计算S2-S3，结果s4进S41

7、1#操作符结束，在栈顶得到运算结果4.将二项式(m+4'展开，其系数构成杨辉三角形。画111当n=3的情况下，在打印过程中队列的变化。步nsQ_ts+t—Qt-*s输出s队列Q的变化(0)(1)(2)(3)(4)(5)00[110]1101111【1011211211[012】31010—(121100][121420111101][21512322013)【1621311【0133171010—[1331]0【1331