第三章 栈与队列（答案）
一、选择题
1．栈的特点是（ B ），队列的特点是（ A ）。 A、先进先出 B、 后进先出
2.一个栈的队列顺序是a,b,c,d,e，则栈的不可能的输出序列是（ ）。 A 、edcba B、 decba C、 dceab D 、abcde 3. 判断一个队列QU（最多元素为MAXSIZE）为空的条件是（ ） A 、QU->rear-QU->front== MAXSIZE B、 QU->rear-QU->front-1==MAXSIZE C、 QU->front==QU->rear D、 QU->front==QU->rear+1
4.若已知一个栈的进栈序列是1，2，3,……..,n，其输出序列为p1,p2,p3,…..,pn,若p1=n,则pi(1<=i A、 i B 、n=i C、 n-i+1 D、不确定 5.循环顺序队列中是否可以插入下一个元素，（ ） A、 与队首指针和队尾指针的值有关 B、 只与队尾指针的值有关，与队首指针的值无关 C、 只与数组大小有关，与队首指针和队尾指针的值无关 D、 与曾经进行过多少次插入操作有关 二、填空题 1. 设有编号为1，2，3，4的四辆车，顺序进入一个栈式结构的站台（栈的大小为4），试写出这四辆车开出站的所有可能的顺序（每辆车入站后出站的时间未知）：1234，1243，1324，1342，1432，2134，2143，2314，2341，2431，3214，3241，3421，4321 2.将下列各中缀表达式转换成后缀表达式。 （A*（B+C）+D）*E-F*G ABC+*D+E*FG*- ; A*(B-D)+H/(D+E)-S/N*T ABD-*HDE+/+SN/T*- ; (A-C)*(B+D)+(E-F)/(G+H) AC-BD+*EF-GH+/+ 3.顺序栈的入栈操作 Sqstack *push_seqstack(Sqstack *s,elementtype x) { if(s->top= =MAXLEN-1) { printf(“上溢\\n”); return 0; } 1 else { s->top++; s->element[s->top] =x; return s; } } 4.链栈的出栈操作 int *pop_linkstack(linkstack *s,elementtype y) {linkstack *p; if(s==NULL ) { printf(“下溢\\n”); return 0; } else { p=s; y=s->data; s= s->next ;(或者s=p->next) free(p); return 1; } } 5.循环队列的出队操作 elementtype delete_cyqueue(Cqueue *cp,elementtype y) { if( cp->front= =cp->rear ) { printf(“下溢\\n”); return NULL; } else { cp->front= (cp->font+1)%MAXLEN ; y=cp->element[cp->front]; return y;} } 2