出序列。（2）如果输入序列由A，B，C，D组成，试给出全部可能的输出序列和不可能的输出序列。答：（1）栈的操作特点是后进先出，因此输出序列有：A入，A出，B入，B出，C入C出，输出序列为ABC。A入，A出，B入，C入，C出，B出，输出序列为ACB。A入，B入，B出，A出，C入，C出，输出序列为BAC。A入，B入，B出，C入，C出，A出，输出序列为BCA。A入，B入，C入，C出，B出，A出，输出序列为CBA。由A，B，C组成的数据项，除上述五个不同的组合外，还有一个C，A，B组合。但不可能先把C出栈，再把A出栈，不在栈顶位置）（A，最后把B出栈，所以序列CAB不可能由输入序列A，B，C通过栈得到。（2）按照上述方法，可能的输出序列有：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。不可能的输出序列有：DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD5．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S和X操作串是什么？答：应是SXSSXSXX。各操作结果如下：S1入栈X1出栈输出序列：1S2入栈S3入栈X3出栈输出序列：13S4入栈X4出栈输出序列：134X2出栈输出序列：13426．有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先的次序有哪几个？答：从题中可知，要使C第一个且D第二个出栈，应是A入栈，B入栈，C入栈，C出栈，D入栈。之后可以有以下几种情况：（1）B出栈，A出栈，E入栈，E出栈，输出序列为：CDBAE。（2）B出栈，E入栈，E出栈，A出栈，输出序列为CDBEA。（3）E入栈，E出栈，B出栈，A出栈，输出序列为CDEBA所以可能的次序有：CDBAE，CDBEA，CDEBA7．写出以下运算式的后缀算术运算式⑴3x2x1x5⑵ABCDEFG答；对应的后缀算术运算式⑴3x2x1x5
4
f⑵ABCDEFG8．简述广义表和线性表的区别和联系。答：广义表是线性表的的推广，它也是
0个元素a1a2…ai…a
的有限序列，其中ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。四、程序填空题1．（1）qfro
t
extp
ext（2）freep（3）qrearqfro
t五、综合题1．答：出队序列是e2e4e3e6e5e1的过程：⑴e1入栈（栈底到栈顶元素是e1）⑵e2入栈（栈底到栈顶元素是e1e2）⑶e2出栈（栈底到栈顶元素是e1）⑷e3入栈（栈底到栈顶元素是e1e3）⑸e4入栈（栈底r