第三章栈和队列练习题
一、单项选择题
1．一个顺序栈一旦被声明，其占用空间的大小（）。
A．已固定B．可以改变C．不能固定D．动态变化
2．链栈和顺序栈相比，有一个比较明显的缺点，即（）。
A．插入操作更加方便B．通常不会出现栈满的情况
C．不会出现栈空的情况D．删除操作更加方便
3．用单链表表示的链式队列的队头在链表的（）位置。
A．链头B．链尾C．链中D．任意位置
4．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。
A．堆栈B．队列C．数组D．先性表
5．若已知一个栈的入栈序列是1，2，3，…，30，其输出序列是p1,p2,p3,…p n，若p1=30，则p10为（）。
A．11 B．20 C．19 D．21
6．循环队列A[m] 存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是（）。
A．（rear+1)%m=front B．rear =front+1
C．rear=front D．（rear+1)%m-1=front
7．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。
A．top->next=p; B．p->next=top->next; top->next=p;
C．p->next=top; top=p; D．p->next=top->next; top=top->next;
8．在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。
A．x=top;top=top->next; B．x=top->data;
C．top=top->next; x=top->data; D．x=top->data; top=top->next;
9．表达式a*(b+c)-d的后缀表达式是（）。
A．abcd*+- B．abc+*d-
C．abc*++d- D．-+*abcd
10．在一个链队中，设front和rear分别为队首和队尾指针，则插入p所指结点时，应执行（）。
A．front->next=p;front=p; B．rear->next=p;rear=p;
C．p->next=rear;rear=p; D．p->next=front;front=p;
11．栈的插入和删除操作在（）进行。
A．栈底B．栈顶C．任意位置D．指定位置
12．利用数组a[N]顺序存储一个栈时，用top标识栈顶指针，用top== -1表示栈空，并已知栈未满，当元素x进行进栈时执行的操作是（）。
A．a[--top]=x; B．a[top --]=x; C．a[++top]=x; D．a[top++]=x;
13．若让元素1，2，3依次进栈，则出栈次序不可能出现（）的情况。
A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，2
14．一个递归算法必须包括（）。
A．递归部分B．终止条件和递归部分
C．迭代部分D．迭代部分和递归部分
15．在一个顺序循环队列中，队尾指针指向队尾元素的（）位置。
A．前一个B．后一个C．当前D．最后
二、填空题
1．向顺序栈插入新元素分为三步：第一步进行判断，判断条件
是；第二步是修改；第三步是把新元素赋给。同样从顺序栈删除元素分为三步：第一步进行判断，判断条件是。第二步是把；第三步。
2．假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到的输出序列为。
3．循环队列的引入，目的是为了克服。
4．判断一个循环队列LU（最多元素为m0）为空的条件是。
5．在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的，而对于后者，进入栈的元素为，中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是。
6．一个顺序循环队列存于一维数组a[Max]中，假设队头指针和队尾指针分别为front和rear，则判断队空的条件为，判断队满的条件为。
7．一个顺序栈存储于一维数组a[0…N-1]中，栈顶指针用top表示，当栈顶指针等
于时，则为空栈，当栈顶指针等于时，则为满栈。
8．一个容量为15的循环队列中，若头指针front=5，尾指针rear=9，则该循环队列中共
有个元素。
9．栈又称为表，队列又称为表。
10．在一个链栈中，若栈顶指针等于NULL则为；在一个链队中，若队首指针与队尾指针的值相同，则表示该队为或该队。
11．后缀表达式“45*32+-”的值为。
三、问答题
1．假定有四个元素A、B、C、D，按所列次序进栈，试写出所有可能的出栈列，注意，每一个元素进栈后都允许出栈，如ACDB就是一种出栈序列。
2．简述在栈的栈顶插入一个元素的操作过程。
3．简述链栈中插入一个元素的操作过程。
四、算法设计题
1．编写把十进制正整数转换为十六进制数输出的算法。
2．裴波那契（Fibonacci）数列的定义为：它的第一项和第二项均为1，以后各项为其前两项之和。若裴波那契数列中的第n项用Fid(n)表示，则计算公式为：
Fib(n)=1 (n=1或n=2)
Fib(n)= Fib(n-1)+Fib(n-2) (n>=2)
试编写计算Fib(n)的递归算法。
3．在栈顶指针为HS的链栈中，写出计算该链栈中结点个数的函数。4．在HQ的链队中，编写算法求链队中结点个数。
