数据项除上述五个不同的组合外还有一个CAB组合但不可能先把C出栈再把A出栈A不在栈顶位置最后把B出栈所以序列CAB不可能由输入序列ABC通过栈得到2按照上述方法可能的输出序列有ABCDABDCACBDACDBADCBBACDBADCBCADBCDABDCACBADCBDACDBADCBA不可能的输出序列有DABCADBCDACBDBACBDACDBCADCABCDABCADBCABD
5用S表示入栈操作X表示出栈操作若元素入栈顺序为1234为了得到1342出栈顺序相应的S和X操作串是什么答应是SXSSXSXX各操作结果如下SX1入栈1出栈输出序列1
fSSXSXX
2入栈3入栈3出栈输出序列134入栈4出栈输出序列1342出栈输出序列1342
6有5个元素其入栈次序为ABCDE在各种可能的出栈次序中以元素CD最先的次序有哪几个答从题中可知要使C第一个且D第二个出栈应是A入栈B入栈C入栈C出栈D入栈之后可以有以下几种情况1B出栈A出栈E入栈E出栈输出序列为CDBAE2B出栈E入栈E出栈A出栈输出序列为CDBEA3E入栈E出栈B出栈A出栈输出序列为CDEBA所以可能的次序有CDBAECDBEACDEBA
7写出以下运算式的后缀算术运算式⑴3x2x1x5⑵ABCDEFG答对应的后缀算术运算式⑴3x2x1x5⑵ABCDEFG
f8简述广义表和线性表的区别和联系答广义表是线性表的的推广它也是
0个元素a1a2…ai…a
的有限序列其中ai或者是原子或者是一个广义表所以广义表是一种递归数据结构而线性表没有这种特性线性表可以看成广义表的特殊情况当ai都是原子时广义表退化成线性表
四程序填空题11qfro
t
extp
ext2freep3qrearqfro
t
五综合题1答出队序列是e2e4e3e6e5e1的过程⑴e1入栈栈底到栈顶元素是e1⑵e2入栈栈底到栈顶元素是e1e2⑶e2出栈栈底到栈顶元素是e1⑷e3入栈栈底到栈顶元素是e1e3⑸e4入栈栈底到栈顶元素是e1e3e4⑹e4出栈栈底到栈顶元素是e1e3⑺e3出栈栈底到栈顶元素是e1⑻e5入栈栈底到栈顶元素是e1e5⑼e6入栈栈底到栈顶元素是e1e5e6
f⑽e6出栈栈底到栈顶元素是e1e5⑾e5出栈栈底到栈顶元素是e1⑿e1出栈栈底到栈顶元素是空栈中最多时有3个元素所以栈S的容量至少是3
2算法设计如下只有一个指针rear的链式队的基本操作i
cludestdiohtypedefcharelemtypestruct
ode定义链队列结点elemtypedatastruct
ode
exttypedefstructqueue定义链队列数据类型struct
oderearLi
kQueue
voidi
itqueueLi
kQueueQ初始化队列
fQstructqueuemallocsizeofstructqueueQrearNULL
voide
queueLi
kQueueQer