四、简答题(每小题4分,共20分) 1.说明线性表、栈与队的异同点 2.设有编号为1,2,3,4的四辆列车,顺序进入一个栈式结构的车站,具体写出这四辆列车开出车站 所有可能的顺序。 3.假设正读和反读都相同的字符序列为“回文”,例如,abba’和 abeba’是回文,‘ abcde’和‘ ababab 则不是回文。假设一字符序列已存入计算机,请分析用线性表、堆栈和队列等方式正确输出其回文的可能 性? 4.顺序队的“假溢出”是怎样产生的?如何知道循环队列是空还是满? 5.设循环队列的容量为40(序号从0到39),现经过一系列的入队和出队运算后,有 ① front=1l,rear=19;② front=19,rear=1;问在这两种情况下,循环队列中各有元素多少个? 五、阅读理解(每小题5分,共20分) 1.按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,并仿照教材例32的格式,画出对下 列算术表达式求值时操作数栈和运算符栈的变化过程: A一BXC/D+E↑F 2.写出下列程序段的输出结果(栈的元素类型 SElem Type为char) void main( Stack S: Pop(S, x); Push(s, t); Push(S x) Pop(S, x); Push(S,'s); InitStack (S); while(Stack Empty(S))i Pop(S y): printf(y): 1; X=’e’;y=k’; Printf(x);3 四、简答题（每小题 4 分，共 20 分） 1. 说明线性表、栈与队的异同点。 2. 设有编号为 1，2，3，4 的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的 所有可能的顺序。 3. 假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’ 则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能 性？ 4. 顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？ 5. 设循环队列的容量为 40（序号从 0 到 39），现经过一系列的入队和出队运算后，有 ① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？ 五、阅读理解（每小题 5 分，共 20 分） 1. 按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教材例 3-2 的格式，画出对下 列算术表达式求值时操作数栈和运算符栈的变化过程： A－B×C/D+E↑F 2. 写出下列程序段的输出结果（栈的元素类型 SElem Type 为 char）。 void main( ){ Stack S; Char x,y; InitStack(S); X=’c’;y=’k’; Pop(S,x); Push(S,’t’); Push(S,x); Pop(S,x); Push(S,’s’); while(!StackEmpty(S)){ Pop(S,y);printf(y); }; Printf(x); }