A）3，2，1，4 B）2，1，4，3 C）4，3，2，1 D）1，4，2，3 14.下列关于队列的叙述中正确的是（ ）。
A）在队列中只能插入数据 B）在队列中只能删除数据 C）对列是先进先出的线性表 D）队列是先进后出的线性表 15.在一个顺序循环队列中，队头指针指向队头元素的（ ）位置。 A）前一个 B）后一个 C）当前 D）最后
16. 在一个顺序循环队列中，队尾指针指向队尾元素的（ ）位置。 A）前一个 B）后一个 C）当前 D）最后
17.从一个顺序循环队列中删除元素时，首先需要( )。
A）前移队头指针 B）取出队尾指针所指位置上的元素 C）后移队头指针 D）取出队头指针所指位置上的元素
18.假设一个顺序循环队列的队头指针和队尾指针分别用front和rear表示，则判别队空的条件为（ ）。
A）front+1==rear B）rear+1==front C）front==0 D）front==rear 19.假设一个顺序循环队列存储于数组a[N]中，其队头指针和队尾指针分别用front和rear表示，则判断队列满的条件为（ ）。
A）(rear-1)%N=front B）(rear+1)%N=front C）(front-1)%N=rear D）(front+1)%N=rear
20. 假设一个顺序循环队列存储于数组a[N]中，其队头指针和队尾指针分别用front和rear表示，已知队列未满，当元素x入队时所执行的操作为（ ）。
A）a[++rear%N]=x; B）a[r++%N]=x; C）a[--rear%N]=x; D）a[rear--%N]=x;
21. 假设一个顺序循环队列存储于数组a[N]中，其队头指针和队尾指针分别用front和rear表示，已知队列未满，当出队并返回队头元素时所执行的操作为（ ）。
A）return a[++rear%N]; B）return a[--rear%N]; C）return a[++front%N]; D）return a[front++%N];
22.假设一个链接队列的队头指针和队尾指针分别为front和rear，则判别队列空的条件为（ ）。
A）front==rear B）front!=NULL C）rear!=NULL D）front==NULL
23. 假设一个链接队列的队头指针和队尾指针分别为front和rear，每个结点由一个数值域data和一个指针域next构成，当出队时，所进行的指针操作为（ ）。
A）front=front->next; B）front->next=rear;rear=rear->next; C）rear=rear->next; D）front=front->next;front->next=rear; 24.以下哪一个不是队列的基本运算（ ）。
A）从队尾插入一个新元素 B）从队列中删除第i个元素 C）判断一个队列是否为空 D）读取队头元素的值 25.栈和队列的共同特点是（ ）。
A）都是先进先出 B）都是先进后出 C）都只允许在端点处插入和删除元素 D）没有共同点
16
26.一个队列的入队序列是1，2，3，4，在队列的出队序列是（ ）。 A）4，3，2，1 B）1，2，3，4 C）1，4，3，2 D）3，2，4，1
27.下列叙述中，（ ）与在循环顺序队列中插入下一个元素有关。 A）与队头指针和队尾指针的值有关
B）只与队尾指针的值有关，与队头指针的值无关 C）只与队头指针的值有关，与队尾指针的值无关 D）与曾经进行过多少次插入操作有关
二、填空题
1. 在栈中，允许插入与删除的一端称为 ，而不允许插入与删除的另一端称为 。
2. 往栈中插入一个元素称为 运算。从栈中删除一个元素（即删除栈顶元素）称为 运算。
3.栈又称为 表，队列又称为 表。
4.在一个用一维数组a[Max]表示的顺序栈中，该栈所含元素的个数最少为 个，最多为 个。
5.向一个顺序栈插入一个元素时，首先使 后移一个位置，然后把新元素 到这个位置上。
6.从一个顺序栈删除元素时，首先取出 ，然后再使 减1。 7.队列的插入操作在 进行，删除操作在 进行。
8.一个顺序循环队列存于一维数组a[Max]中，假设队头指针和队尾指针分别为front和rear，则判断队空的条件为 ，判断队满的条件为 。
9. 一个顺序循环队列存于一维数组a[Max]中，假设队头指针和队尾指针分别为front和rear，则求出队头指针和队尾指针的下一个位置的计算公式分别为 和 。
10. 一个顺序栈存储于一维数组a[ 0..N-1 ] 中，栈顶指针用top表示，当栈顶指针等于 时，则为空栈，栈顶指针等于 时，则为满栈。
11.在一个链栈中，若栈顶指针等于NULL，则为 ；在一个链队列中，若队头指针与队尾指针的值相同，则表示该队列为 或该队 。
12.假设一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当p所指向的结点入栈时，则首先执行 操作，然后执行 操作。
13. 假设一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当进行出栈运算时（栈非空），则要把栈顶指针top修改为 的值。
14.向一个顺序循环队列中插入元素时，需要首先移动 ，然后再向它所指的位置 新元素。
15.在一个空链队列中，假定队头指针和队尾指针分别为front和rear，当向其插入一个新结点*p时，则首先执行 操作，然后执行 操作。
16.假设front和rear分别为一个链队列的队头指针和队尾指针，则该链队列中只有一个结点的条件为 。
17.在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有 个元素。
三、简答题
1. 什么是栈？栈组织数据的原则是什么？
17
2. 什么是顺序栈和链式栈？
3. 简述在顺序栈的栈顶插入一个元素的操作过程。 4. 简述在链栈中插入一个元素的操作过程。
5. 在循环队列中，仅依据头尾指针相等，无法判断队列是“空”还是“满”。要解决这个问题，常用的两种方法是什么？
6. 一个栈的输入序列为A、B、C，若输出序列由A、B、C所构成，试给出全部可能的输出序列。
四、应用题（写出下面算法的结果）
1. void exem1(SeqStack &s)
{
int i,a[4]={15,24,38,44};
InitStack(s); //初始化s栈 Push(s,20); //向s栈压入20 Push(s,36); //向s栈压入36 for(i=0;i<4;i++)
Push(s,a[i]); //a数组各元素入栈 cout<
Cout<
该算法的输出结果为：
2. void exam2(LinStack &s) {
InitStack(s); //初始化s栈 Push(s,30); //向s栈压入30 Push(s,40); Push(s,50);
int x=Pop(s)+2*Pop(s); Push(s,x);
int i,a[4]={5,8,12,15}; for(i=0;i<4;i++)
18
Push(s,a[i]); //将数组a各元素入栈 while(!StackEmpty(s))
cout<
该算法的输出结果为：
3. void exam3(SeqQueue &q) {
InitQueue(q); //初始化队列q int i,a[4]={5,8,12,15}; for(i=0;i<4;i++)
EnQueue(q,a[i]); //a数组各元素入队 EnQueue(q,DeQueue(q)); //入队元素是出队元素 EnQueue(q,30); //30入队 EnQueue(q,DeQueue(q)+10); While(!QueueEmpty(q))
cout<
}
该算法的输出结果为：
4. void exam4(LinQueue &Lq)
{
InitQueue(Lq); //初始化队列Lq EnQueue(Lq,25); //25入队 int i,a[5]={34,23,78,56,19}; for(i=0;i<5;i++)
EnQueue(Lq,a[i]); //数组a各元素入队 DeQueue(Lq); //进行一次出队运算 EnQueue(Lq,DeQueue(Lq)); //入队元素是出队元素 While(!QueueEmpty(Lq))
Cout<
19
Cout<
该算法的输出结果为：
参考答案
一、单选题
1.A 2.D 3.A 4.B 5.B 6.A 7.C 8.B 9.C 10.D 11.C 12.C 13.D 14.C 15.C 16.B 17.D 18.D 19.B 20.B 21.D 22.D 23.A 24.B 25.C 26.B 27.A
二、填空题
1. 栈项，栈底 2. 进栈（或入栈），退栈（或出栈） 3. 后进先出，先进先出 4. 0，Max
5. 栈顶指针，插入（或写入） 6. 栈顶元素， 栈顶指针
7. 队尾，队头 8. front==rear，(rear+1)%Max==front 9.(front+1)%Max，(rear+1)%Max 10.-1，N-1
11.空栈，空，只含有一个结点 12.p->next=top，top=p
13. top->next 14.应该：先插入（或写入）新元素，然后移动队尾指针
15. p->next=NULL，front=rear=p
16.（front==rear&&front!=NULL或 front==rear&&rear!=NULL） 17. 3 三、简答题
1. 答案：栈(stack ) 是限定在一端进行插入与删除的线性表。 栈是按照“先进后出”（FILO，First in Last Out） 或“后进先出”（LIFO，Last in First Out）的原则组织数据的。
2. 答案：栈是一种线性表，采用顺序存储方式存储的栈，称为顺序栈；而采用链式存储方式存储的栈，称为链式栈。
3. 答案：在顺序栈的栈顶插入一个元素时，首先将栈顶指针s->top 加１，以指示新的栈顶位置，然后将新元素插入到栈顶指针指向的位置。
4. 答案：当向链栈的栈顶插入一个元素时，可使该元素结点的指针域指向原来的栈顶结点，而栈顶指针则修改为指向该元素的结点，这样，该结点就成为新的栈顶结点。
5. 答案：在循环队列中，仅依据头尾指针相等，无法判断队列是“空”还是“满”。要解决这个问题，常用两种方法：一是少用一个元素空间，约定入队前，若尾指针加1后等于头指针，则认为队列满（rear所指单元始终为空）；二是使用一个计数器，记录队列中元素的总数（实际上是队列的长度）。
20