第三章 栈和队列 试题
一、单项选择题
1. 栈的插入和删除操作在（      ）进行。
A. 栈顶                B. 栈底                C. 任意位置            D. 指定位置
2. 当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（      ）语句修改top指针。
A. top++;            B. top--;            C. top = 0;        D. top;
3. 若让元素1,2,3依次进栈，则出栈次序不可能出现（      ）种情况。
A. 3, 2, 1        B. 2, 1, 3        C. 3, 1, 2        D. 1, 3, 2
4. 在一个顺序存储的循环队列中，队头指针指向队头元素的（      ）位置。
A. 前一个            B. 后一个            C. 当前            D. 后面
5. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（      ）。
A. n-2            B. n-1                C. n                D. n+1
6. 从一个顺序存储的循环队列中删除一个元素时，需要（      ）。
A. 队头指针加一                        B. 队头指针减一
C. 取出队头指针所指的元素            D. 取出队尾指针所指的元素
7. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（  ）。
A. front+1 == rear                B. rear+1 == front
C. front == 0                        D. front == rear
8. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（      ）。
A. front == rear                    B. front != NULL
C. rear != NULL                    D. front == NULL
9. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行操作（      ）。
A. top->link = s;                B. s->link = top->link;  top->link = s;
C. s->link = top;  top = s;      D. s->link = top;  top = top->link;
10. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行操作（      ）。
A. x = top->data;  top = top->link;    B. top = top->link;  x = top->data;
C. x = top;  top = top->link;            D. x = top->data;
11. 设循环队列的结构是
        #define MaxSize 100
        typedef int ElemType;
    typedef struct {
              ElemType base[MaxSize];
              int front, rear;
        } Queue;
若有一个Queue类型的队列Q，则判断队列满的条件应是语句（      ）。
A. Q.front == Q.rear;                    B. Q.front - Q.rear == MaxSize;
C. Q.front + Q.rear == MaxSize;        D. Q.front == (Q.rear+1) % MaxSize;
12. 设循环队列的结构是
        #define MaxSize 100
        typedef int ElemType;
    typedef struct {
          ElemType base[MaxSize];
          int front, rear;
        } Queue;
若有一个Queue类型的队列Q，则应用语句（      ）计算队列元素个数。
A. (Q.rear - Q.front + MaxSize ) % MaxSize;
B. Q.rear - Q.front +1;
C. Q.rear - Q.front -1;
D. Q.rear - Qfront;
13. 在做进栈运算时,应先判断栈是否（      ）
A. 空                  B. 满                C. 上溢3 d                D. 下溢
14. 为增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时, 应将两栈的（      ）分别设在这片内存空间的两端。
          A. 长度                B. 深度                C. 栈顶                D.  栈底
15. 使用两个栈共享一片内存空间时，当（      ）时，才产生上溢。
        A. 两个栈的栈顶同时到达这片内存空间的中心点
        B. 其中一个栈的栈顶到达这片内存空间的中心点
        C. 两个栈的栈顶在这片内存空间的某一位置相遇
        D. 两个栈均不空, 且一个栈的栈顶到达另一个栈的栈底
二、填空题
1. 栈是一种限定在表的一端插入和删除的线性表，它的特点是________。
2. 队列是一种限定在表的一端插入，在另一端删除的线性表，它的特点是________。
3. 队列的插入操作在________进行，删除操作在________进行。
4. 向一个顺序栈插入一个元素时，首先使_______后移一个位置，然后把待插入元素写入到这个位置上。
5. 从一个顺序栈中删除元素时，需要将________前移一位位置。
6. 若设顺序栈的最大容量为MaxSize，则判断栈满的条件是________。
7. 当用长度为MaxSize的数组顺序存储一个栈时，若用top == MaxSize表示栈空，则表示栈满的条件为________。
8. 在一个链式栈中，若栈顶指针等于NULL则为________。
9. 在向一个链式栈插入一个新结点时，首先把栈顶指针中存放的结点地址赋给新结点的指针域，然后把新结点的存储位置赋给________。
10. 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行________和________操作。
11. 从一个栈顶指针为top的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行________操作。
12. 设循环队列Q的队头和队尾指针分别为front和rear，则判断队空的条件为________。
13. 设循环队列Q的队头和队尾指针分别为front和rear，队列的最大容量为MaxSize，且规定判断队空的条件为Q.front == Q.rear，则判断队满的条件为________。
14. 向一个循环队列中插入元素时，需要首先移动________，然后再向所指位置写入新插入的元素。
15. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为_______或该队列________。
16. 假定front和rear分别为链式队列的队头和队尾指针，则该队列中只有一个结点的条件为______。
17. 双端队列是限定插入和删除操作在表的________进行的线性表。
18. 中缀表达式3*(x+2)-5所对应的后缀表达式为________。
19. 后缀表达式“4 5 * 3 2 + -”的值为________。
20. 设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为________。
三、判断题
1. 每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列。
2. 链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。
3. 在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置。
4. 栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。
5. 在使用后缀表示实现计算器类时使用了一个栈的实例，它起的作用是暂存运算对象和计算结果。
6. 在向顺序栈压入新元素时，要先按栈顶指针指示的位置存入新元素再移动栈顶指针。
7. 在用单链表表示的链式队列中，队头在链表的链尾位置。
8. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
9. 在一个循环队列Q中，判断队满的条件为Q.rear % MaxSize+1 == Q.front。
10. 在一个循环队列Q中，判断队空的条件为Q.rear+1 == Q.front。
11. 若让元素1, 2, 3依次进栈，则出栈次序1, 3, 2是不可能出现的情况。
12. 若让元素1, 2, 3依次进栈，则出栈次序3, 1, 2是不可能出现的情况。
13. 在循环队列中，进队时队尾指针进一，出队时队头指针减一。
14. 在循环队列中，进队时队尾指针进一，出队时队头指针进一。
15. 在用单链表表示的链式队列Q中，队空条件为Q->front == Q->rear。
16. 如果进栈序列是1, 2, 3, 4, 5, 6, 7, 8。则可能的出栈序列有8！种。
四、运算题
1. 试利用运算符优先数法，画出对中缀算术表达式a + b * c - d / e 求值时运算符栈OPTR和运算对象栈OPND的变化。运算符优先数如下表所示：
       
运算符
#
(
*, /, %
+, -
)
isp（栈顶运算符优先级）
0
1
5
3
7
icp（栈外运算符优先级）
0
7
4
2
1
2. 试利用运算符优先数法，画出将中缀算术表达式a + b * c - d / e 改为后缀表达式时运算符栈OPTR的变化。运算符优先数如下表所示：
       
运算符
#
(
*, /, %
+, -
)
isp（栈顶运算符优先级）
0
1
5
3
7
icp（栈外运算符优先级）
0
7
4
2
1
3. 试画出对后缀算术表达式a b c * + d e / - 求值时运算对象栈OPND的变化。
4. 将二项式 (a + b) i 展开, 其系数构成杨辉三角形。若想按行将展开式系数的前n行打印出来，需要用到一个队列，存放各行展开式的系数。试画出当n = 3的情况下，在打印过程中队列的变化。
#include "03b.h" //在03b.h里定义了链栈的抽象数据类型
        void YANGVI ( int n ) {
SqQueue q; InitQueue(&q);
            q.EnQueue (1);  q.EnQueue (1);
            int i, j, t, s = 0;   
            for ( i = 1; i <= n; i++ ) {
                cout << endl;   
                q.EnQueue (0);
                for ( j = 1; j <= i+2; j++ ) {
                    q.DeQueue (t);