判断题
1-1
Run the following operations on a stack S: Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S). The output sequence must be {1, 2, 3}.
T F
1-2
If keys are pushed onto a stack in the order abcde, then it's impossible to obtain the output sequence cdabe.
T F
1-3
序列{1,2,3,4,5}依次入栈，则不可能得到{3,4,1,2,5}的出栈序列。
T F
1-4
栈结构不会出现溢出现象。
T F
1-5
两个栈共享一片连续空间，可以将两个栈的栈底分别设在这片空间的两端。
T F
1-6
Non recursive programs are generally faster than equivalent recursive programs. However, recursive programs are in general much simpler and easier to understand.
T F
1-7
Recursive programs are generally faster than equivalent non recursive programs. However, non recursive programs are in general much simpler and easier to understand.
T F
1-8
In most restaurants, we follow one principle called "First come, first served". This principle can be implemented by a stack.
T F
1-9
When n elements are pushed into a stack, they may be popped in a different order. But if they are inserted into a queue, they will always be deleted in the same order as the insertions.
T F
1-10
栈的特性
栈是后进先出的线性表。
T F
1-11
"Circular Queue" is defined to be a queue implemented by a circularly linked list or a circular array.
T F
1-12
In a circular queue which is implemented by an array, the front value must always be no larger than the rear value.
T F
1-13
In most restaurants, we follow one principle called "First come, first served". This principle can be implemented by a queue.
T F
1-14
循环队列也存在空间溢出的问题。
T F
1-15
队列的特性
队列是后进先出的线性表。
T F
单选题
2-1
若已知一队列用单向链表表示，该单向链表的当前状态（含3个对象）是：1->2->3，其中x->y表示x的下一节点是y。此时，如果将对象4入队，然后队列头的对象出队，则单向链表的状态是：
A.1->2->3
B.2->3->4
C.4->1->2
D.答案不唯一
2-3
若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？
(2分)
A.2和0 B.2和2 C.2和4 D.2和6
2-4
现有队列 Q 与栈 S，初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }（1在队头），S 为空。若允许下列3种操作：（1）出队并输出出队元素；（2）出队并将出队元素入栈；（3）出栈并输出出栈元素，则不能得到的输出序列是：
(2分)
A.1, 2, 5, 6, 4, 3 B.2, 3, 4, 5, 6, 1 C.3, 4, 5, 6, 1, 2 D.6, 5, 4, 3, 2, 1
2-5
循环队列的引入，目的是为了克服( )。
(1分)
A.假溢出问题 B.真溢出问题 C.空间不够用 D.操作不方便
2-6
循环队列的队满条件为 ( )。
(2分)
A.(sq.rear+1) % maxsize ==(sq.front+1) % maxsize
B.(sq.front+1) % maxsize ==sq.rear
C.(sq.rear+1) % maxsize ==sq.front
D.sq.rear ==sq.front
2-7
栈和队列的共同点是（ ）。
(2分)
A.都是先进先出
B.都是先进后出
C.只允许在端点处插入和删除元素
D.没有共同点
2-8
已知初始为空的队列 Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是 1、2、3、4、5，则不能得到的出队序列是：
(2分)
A.5、4、3、1、2
B.5、3、1、2、4
C.4、2、1、3、5
D.4、1、3、2、5
2-9
有六个元素以6、5、4、3、2、1的顺序进栈，问哪个不是合法的出栈序列？
(2分)
A.2 3 4 1 5 6
B.3 4 6 5 2 1
C.5 4 3 6 1 2
D.4 5 3 1 2 6
2-10
若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？
(2分)
A.将链表头设为top
B.将链表尾设为top
C.随便哪端作为top都可以
D.链表头、尾都不适合作为top
2-11
利用大小为n的数组（下标从0到n-1）存储一个栈时，假定栈从数组另一头开始且top==n表示栈空，则向这个栈插入一个元素时，修改top指针应当执行：
(2分)
A.top=0 B.top++ C.top-- D.top不变
2-12
Given the pushing sequence of a stack as {1, 2, 3, 4, 5}. If the first number being popped out is 4, then the last one out must be:
(2分)
A.1 B.3 C.5 D.1 or 5
2-13
To delete a node from a linked stack with ST being its top pointer, and save the key value of the deleted node into X, we must do:
(2分)
A.X= ST->data;
B.X= ST; ST = ST->next;
C.X= ST->data; ST = ST->next;
D.ST = ST->next; X= ST->data;
2-14
下列关于栈的叙述中，错误的是：
- 采用非递归方式重写递归程序时必须使用栈
- 函数调用时，系统要用栈保存必要的信息
- 只要确定了入栈次序，即可确定出栈次序
- 栈是一种受限的线性表，允许在其两端进行操作
(2分)
A.仅 1 B.仅 1、2、3 C.仅 1、3、4 D.仅 2、3、4
2-15
若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：
- （1）从S1中依次弹出两个操作数a和b；
- （2）从S2中弹出一个运算符op；
- （3）执行相应的运算b op a；
- （4）将运算结果压入S1中。
假定S1中的操作数依次是{ 5, 8, 3, 2 }（2在栈顶），S2中的运算符依次是{ *, -, + }（+在栈顶）。调用3次F()后，S1栈顶保存的值是：
(2分)
A.-15 B.15 C.-20 D.20
2-16
对空栈 S 进行 Push 和 Pop 操作，入栈序列为 a, b, c, d, e，经过 Push, Push, Pop, Push, Pop, Push, Push, Pop 操作后，得到的出栈序列是：
(2分)
A.b, a, c B.b, a, e C.b, c, a D.b, c, e
2-17
设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是( )。
(2分)
A.2 B.3 C.5 D.6
2-18
元素A,B,C,D依次入栈，出栈无限制，则以下（ ）是可能的出栈序列。
(2分)
A.C, A, B, D B.B, A, D, C C.B, D, A, C D.A, D, B, C
2-19
用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为( )。
(2分)
A.SXSSSXXX B.SXSXSXSX C.SSSSXXXX D.SXSSXSXX
2-20
Given the popping sequence of a stack as { a, b, c, d, e, f }. Among the following, the impossible pushing sequence is:
(2分)
A.c b a f e d B.d f e a c b C.f e a b c d D.f e d a b c
2-21
Given the popping sequence of a stack as { 1, 2, 3, 4, 5, 6 }. Among the following, the impossible pushing sequence is:
(2分)
A.3 2 1 6 5 4 B.6 5 1 2 3 4 C.6 5 4 1 2 3 D.4 6 5 1 3 2
程序填空题
略.
