数据结构第三次功课.docVIP

一、单项选择题 一个栈的入栈序列是a，b，c，d，e，则栈不可能输出的序列是（ ）。 A．edcba B．decba C．dceab D．abcde 一个队列的入队序列是1，2，3，4，则队列的输出序列是（ ）。 A．4，3，2，1 B．1，2，3，4 C．1，4，3，2 D．3，2，4，1 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为P1，P2，P3…，Pn，若P1=n，则Pi为（ ）。 A．i B．n-i C．n-i+1 　 D．不确定 判定一个栈S（最多元素为m0）为空的条件是（ ） A．S.top!=0 B．S.top = =0 C．S.top!= m0 -1 D． 判定一个队列Q（最多元素为m0）为空的条件是（ ）。 A．Q.rear－Q.front= = m0 B．Q.rear－Q.front－1= = m0 C．Q.front = =Q.rear　 D．Q.front=Q.rear+1 判定一个循环队列Q（最多元素为m0）为满的条件是（ ）。 A．Q.front = =Q.rear B．Q.front !=Q.rear C．Q.front = =(Q.rear+1)% m0 D．Q.front ! =(Q.rear+1)% m0 栈和队列的共同点是（ ）。 A．都是后进先出 B．都是先进先出 C．只允许在端点处插入和删除元素 D．没有共同点 二、写出下列程序段的输出结果。 1． void main( ) { stack S; char x,y; InitStack(S); x=’c’ ; y=’k’ ; Push(S,x); Push(S,’a’); Push(S,y); 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); } 2．void main( ) { Queue Q; InitQueue(Q); char x=‘e’, y=‘c’; EnQueue(Q,’h’); EnQueue(Q,’r’); EnQueue(Q,y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q,’a’); while(!QueueEmpty(S)) { DeQueue(Q, y); printf(y); } printf(x); } 三、算法设计 1、假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试运用栈和队列的知识编写算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。