栈和队列习题

第三章 栈和队列

1. 栈的特点是(),队列的特点是(). A.先进先出 B.先进后出 2.栈和队列的共同点是().

A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点

3.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是().

A.edcba B.decba C.dceab D.abcde 4.若已知一个栈的进栈序列是1,2,3,……,n,其输出序列为p1,p2,p3,……,pn。若p1=n,则pi(1≤i

5.若已知一个栈的进栈序列是1,2,3,……,n,其输出序列为p1,p2,p3,……,pn。若pn=n,则pi(1≤i

6.若已知一个栈的进栈序列是1,2,3,……,n,其输出序列为p1,p2,p3,……,pn。若p1=3,则p2为(). A.可能是2 B.不可能是2 C.可能是1 D.一定是1

7. 若已知一个栈的进栈序列是p1,p2,p3,……,pn,其输出序列为1,2,3,……,n。若p3=1,则p1为().

A.可能是2 B.一定是2 C.不可能是2 D.不可能是3

8.若已知一个栈的进栈序列是p1,p2,p3,……,pn,其输出序列为1,2,3,……,n。若pn=1,则pi(1≤i

9.一个队列的入队序列是1,2,3,4,则队列的输出序列是().

A.4,3,2,1 B.1,2,3,4 C.1,4,3,2 D.3,2,4,1 10.判定一个队列Q为空的条件为(). A.Q->rear-Q->front==MaxSize B.Q->rear-Q->front-1==MaxSize C.Q->front== Q->rear D.Q->front== Q->rear+1

11. 判定一个队列Q为满的条件为(). A.Q->rear-Q->front==MaxSize B.Q->rear-Q->front-1==MaxSize C.Q->front== Q->rear D.Q->front== Q->rear+1

12.循环队列中是否可以插入下一个元素,(). A.与队头指针和队尾指针的值有关 B.只与队尾指针的值有关

C.只与数组的大小有关,与队尾和队头指针的值无

关

D.与曾经进行过多少次插入操作有关 13.判定一个循环队列Q为空的条件(). A.Q->front==Q->rear B. Q->front!=Q->rear

C. Q->front==(Q->rear+1)%MaxSize D. Q->front!=(Q->rear+1)%MaxSize 14. 判定一个循环队列Q为满的条件(). A.Q->front==Q->rear B. Q->front!=Q->rear

C. Q->front==(Q->rear+1)%MaxSize D. Q->front!=(Q->rear+1)%MaxSize

15.在一个链表中,假设f和r分别为队头和队尾指针,则插入s所指结点的运算时(). A.f->next=s;f=s; B.r->next=s;r=s; C.s->next=r;r=s; D.s->next=f;f=s;

16. 在一个链表中,假设f和r分别为队头和队尾指针,则删除一个结点的运算时(). A. r=f->next; B. r=r->next;

C. f=f->next; D. f= r->next;

17.跟踪以下代码，显示每次调用后栈中的内容。 InitStack(s); Push(s,’A’); Push(s,’B’); Push(s,’C’); Pop(s,x); Pop(s,x); Push(s,’D’); Push(s,’E’); Push(s,’F’); Pop(s,x); Push(s,’G’); Pop(s,x); Pop(s,x); Pop(s,x);

18.对于一个栈，给出输入项A,B,C.如果输入项序列由A,B,C所组成。试给出全部可能的输出序列。 19.假设Q[0……10]是一个线性顺序队列，初始状态为front=rear=0，画出做完以下操作后队列的头指针和尾指针的状态变化情况，若不能入队，请指出其元

素，并说明理由。 d,e,b,g,h入队 d,e出队 i,j,k,l,m入队 b出队 n,o,p入队

20.假设Q[0……10]是一个循环队列，初始状态为front=rear=0，画出做完以下操作后队列的头指针和尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。 d,e,b,g,h入队 d,e出队 i,j,k,l,m入队 b出队 n,o,p入队

21.编写一算法，利用栈的基本运算将指定栈中的内容进行逆转。

22.编写一算法，利用栈的基本运算返回指定栈中的栈底元素。

23.编写一个算法，利用队列和栈的基本运算将指定队列中的内容进行逆转。