数据结构第三次作业答案.doc

一、单项选择题1. 一个栈的入栈序列是a，b，c，d，e，则栈不可能输出的序列是（ C ）。Aedcba Bdecba Cdceab Dabcde2. 一个队列的入队序列是1，2，3，4，则队列的输出序列是（ B ）。A4，3，2，1 B1，2，3，4 C1，4，3，2 D3，2，4，13. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为P1，P2，P3，Pn，若P1=n，则Pi为（ C ）。Ai Bn-i Cn-i+1 D不确定4. 判定一个栈S（最多元素为m0）为空的条件是（ B ）AS.top!=0 BS.top = =0 CS.top!= m0 -1 DS.top = = m0 -15. 判定一个队列Q（最多元素为m0）为空的条件是（ C ）。AQ.rearQ.front= = m0 BQ.rearQ.front1= = m0CQ.front = =Q.rear DQ.front=Q.rear+16. 判定一个循环队列Q（最多元素为m0）为满的条件是（ C ）。AQ.front = =Q.rear BQ.front !=Q.rear CQ.front = =(Q.rear+1)% m0 DQ.front ! =(Q.rear+1)% m07. 栈和队列的共同点是（ C ）。A都是后进先出 B都是先进先出C只允许在端点处插入和删除元素 D没有共同点二、写出下列程序段的输出结果。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); 输出结果：stack栈S栈Scakk出栈，x=k栈Scatkk出栈，x=ks栈Scat栈Scatss出栈，y=s输出y的值s栈Scatt出栈，y=t输出y的值t同理，接着a出栈，y=a，输出y的值a。c出栈，y=c，输出y的值c。最后输出变量x的值k 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); 输出结果：char队列Q队列Qhrch出队，x=h队列Qchr出队，x=rh队列Qrc队列Qchc出队，y=c输出y的值c队列Qh出队，y=h输出y的值h同理，接着a出队，y=a，输出y的值a。最后输出变量x的值raaha三、算法设计1、假设称正读和反读都相同的字符序列为“回文”，例如，abba和abcba是回文，abcde和ababab则不是回文。试运用栈和队列的知识编写算法判别读入的一个以为结束符的字符序列是否是“回文”。算法的基本思想:将依次读入的字符分别插入栈和队列，然后依次比较“栈顶”和“队头”的字符。Status ReturnText ( ) / 若从终端依次输入的字符序列是“回文”，则返回TRUE,否则返回FALSE。 InitStack(S); InitQueue(Q); scanf(“%c”,&ch); while(ch!=) Push(S, ch); EnQueue(Q, ch); scanf(“%c”,&ch); state=TRUE; while(!StackEmpty(S)& s