一、选择题。
1. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ ）
a. i-j-1b. i-jc. j-i+1 d. 不确定的。
2. 用s表示进栈操作，用x表示出栈操作。当输入序列为1234，输出序列为1342时，经过的栈操作为（ ）
a. sxsxssxxb. sssxxsxx
c. sxssxxsxd. sxssxsxx
3. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为， ,若是n，则是( )
a. ib. n-ic. n-i+1 d. 不确定。
4. 表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和运算符栈为（ ）其中^为乘幂 。
a. 3,2,4,1,1b. 3,2,8；(*
c. 3,2,4,2,2d. 3,2,8；(*
5. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少。
a. 1和 5 b. 2和4 c. 4和2 d. 5和1 6.
6. 设循环队列的下标范围是0~n-1，其头、尾指针分别为f和r,则其元素个数为（ ）
a．r-fb．r-f-1
c．(r-f)%n+1d．(r-f+n)%n
7. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )
a. 1234b. 4132c. 4231 d. 4213
8. 表达式a*(b+c)-d的后缀表达式是( )
a． abc+*d- b. abcdc. abc*+d- d. -abcd
二、判断题。
1. 消除递归不一定需要使用栈，此说法（ ）
2. 队列逻辑上是一个下端和上端既能增加又能减少的线性表。（
3. 栈与队列是一种特殊操作的线性表。（
4. 循环队列也存在空间溢出问题。（
三、填空题。
1. 用下标0开始的n元数组实现循环队列时，为实现下标变量m加1后在数组有效下标范围内循环，可采用的表达式是m
2. 在实现顺序栈的操作时，在进栈之前应该先判断在出栈之前先判断。
3. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是。
4. 中缀表达式(a&&b)||e>f))的后缀形式为。
5. 在作进栈运算时，应先判别栈是否在作退栈运算时，应先判别栈是否当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为。
二、应用题。
1. 试证明：若借助栈由输入序列1,2,…,n得到输出序列为， ,它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：
存在着i2. 铁路进行列车调度时， 常把站台设计成栈式结构的站台，试问：
(1) 设有编号为 1,2,3,4,5,6 的六辆列车， 顺序开入栈式结构的站台， 则可能的出栈序列有多少种？
2) 若进站的六辆列车顺序如上所述， 那么是否能够得到 435612, 325641, 154623 和 135426 的出站序列， 如果不能， 说明为什么不能； 如果能， 说明如何得到(即写出"进栈"或"出栈"的序列)。
3. 编写一个递归算法，找出从自然数1，2，3，4，5，6···n中任取r个数的所有组合。例如n=5，r=3时所有组合为543,542,541,532,531,521,432,421,321。
4. 假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，编写一个判断表达式中括弧是否正确配对的函数correct(exp,tag)；其中：exp为字符串类型的变量，表示被判别的表达式，tag为布尔型变量。
5. 求两个正整数m和n的最大公约数，可以使用如下gcd(m,n)公式表示：
1）编写一个计算gcd(m,n)的递归过程；
2）将上述过程转换成非递归过程。
6. 以下是队列和栈的主要操作：
queue（设定每个队列元素的数据类型为type）：
int isqueueempty(queue &q判断队列是否空，1为空，0为不空。
int getfront(queue &q, type &x); 通过x返回队头元素的值。
void enqueue(queue &q, type x将新元素x插入到队列的队尾。
void dequeue(queue &q从队列中退出队头元素。
stack（设定每个栈元素的数据类型与队列相同，为type）:
void initstack(stack &s对新创建的栈初始化，置成空栈。
int isstackempty(stack &s判断栈空否，1为栈空，0为不空。
void push(stack &s, type x将新元素x进栈。
void pop(stack &s栈顶元素出栈。
int gettop(stack &s, type &x通过x返回栈顶元素的值。
利用以上栈和队列的操作，编写以下针对队列的函数实现**（要求非递归实现）：
1） 逆转函数：void reverse(queue &q);
将队中所有元素的排列顺序逆置。
2） 判等函数：void equal(queue &q1,queue &q2);
当两个队列都为非空时，按队列中的顺序依次做对应元素的比较，一旦发现不等立即可以断定两个队列不等且退出比较，否则继续比较且将元素从队列中退出。当两个队列经过这样的逐个元素比较后都变空且每一个对应元素都相等，那么这两个队列相等。
3） 清空函数：void clear(queue &q);
当队列非空时，将队列中的元素清空。
第3章栈与队列答案
一 填空题。1.线性任何栈顶 2.栈顶栈底 3.移动栈顶指针存入元素。二 选择题。三 判断题。四 简答题。1 至少有14种。全进之后再出情况，只有1种 4，3，2，1 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4 进2个之后再出的情况，有5种，2,4,3,1 2,3,...
第3章栈与队列答案
return ok allbrackets test 2 int palindrome test while stackempty s return ok palindrome test 一 填空题。1.队尾队首 2.队列 4.队列的假溢出 5.先进先出。二 选择题。1.b 2.d 5.1,2,2 ...
第3章作业
第3章栈和队列作业。1 若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3时，从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？复旦大学98年 2和42 设栈s和队列q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过栈s,一个元素出...