练习题3
1．单项选择题
（1）栈的“先进后出”特性是指（ ）。
A．最后进栈的元素总是最先出栈
B．当同时进行进栈和出栈操作时，总是进栈优先
C．每当有出栈操作时，总要先进行一次进栈操作
D．每次出栈的元素总是最先进栈的元素
（2）设一个栈的进栈序列是a、b、c、d（即元素a～d依次通过该栈），则借助该栈所得到的输出序列不可能是（ ）。
A．abcd
B．dcba
C．acdb
D．dabc
（3）一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（ ）。
A．edcba
B．decba
C．dceab
D．abcde
（4）已知一个栈的进栈序列是1，2，3，…，n，其输出序列的第一个元素是i（1≤i≤n），则第j（1≤j≤n）个出栈元素是（ ）。
A．i
B．n—i
C．j—i+1
D．不确定
（5）设顺序栈st的栈顶指针top的初始值为—1，栈空间大小为MaxSize，则判定st栈为栈空的条件为（ ）。
A．st.top==—1
B．st.top!=—1
C．st.top!=MaxSize
D．st.top==MaxSize
（6）设顺序栈st的栈顶指针top的初始值为—1，栈空间大小为MaxSize，则判定st栈为栈满的条件是（ ）。
A．st.top!=—1
B．st.top==—1
C．st.top!=MaxSize—1
D．st.top==MaxSize—1
（7）当用一个数组data[0..n—1]存放栈中元素时，栈底最好（ ）。
A．设置在data[0]处
B．设置在data[n—1]处
C．设置在data[0]或data[n—1]处
D．设置在data数组的任何位置
（8）若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进栈的正确操作是（ ）。
A．top++；data[top]=x；
B．data[top]=x；top++；
C．top——；data[top]=x；
D．data[top]=x；top——；
（9）若一个栈用数组data[1..n]存储，初始栈顶指针top为n，则以下元素x进栈的正确操作是（ ）。
A．top++；data[top]=x；
B．data[top]=x；top++；
C．top——；data[top]=x；
D．data[top]=x；top——；
（10）队列中元素的进出原则是（ ）。
A．先进先出
B．后进先出
C．栈空则进
D．栈满则出
（11）栈和队列的不同点是（ ）。
A．都是线性表
B．都不是线性表
C．栈只能在一端进行插入删除操作，而队列在不同端进行插入删除操作
D．没有不同点
（12）元素a、b、c、d依次连续进入队列qu后，队头元素是（ ① ），队尾元素是（ ② ）。
A．a
B．b
C．c
D．d
（13）一个队列的进列序列为1234，则队列可能的输出序列是（ ）。
A．4321
B．1234
C．1432
D．3241
（14）在循环队列中，元素的排列顺序（ ）。
A．由元素进队的先后顺序确定
B．与元素值的大小有关
C．与队头和队尾指针的取值有关
D．与队中数组大小有关
（15）循环队列qu（队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置）的队满条件是（ ）。
A．（qu.rear+1）%MaxSize==（qu.front+1）%MaxSize
B．（qu.rear+1）%MaxSize==qu.front+1
C．（qu.rear+1）%MaxSize==qu.front
A．qu.rear==qu.front
（16）循环队列qu（队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置）的队空条件是（ ）。
A．（qu.rear+1）%MaxSize==（qu.front+1）%MaxSize
B．（qu.rear+1）%MaxSize==qu.front+1
C．（qu.rear+1）%MaxSize==qu.front
D．qu.rear==qu.front
（17）设循环队列中数组的下标是0～N—1，其头尾指针分别为f和r（队头指针f指向队首元素的前一位置，队尾指针r指向队尾元素的位置），则其元素个数为（ ）。
A．r—f
B．r—f—1
C．（r—f）%N+1
D．（r—f+N）%N
（18）一个循环队列中用data[0..n—1]数组保存队中元素，另设置一个队尾指针rear和一个记录队中实际元素个数的变量count，则该队中最多可以存放的元素个数是（ ）。
A．n—1
B．n
C．（rear+n）%n
D．（n—rear）%n
（19）设栈S和队列Q的初始状态为空，元素e1～e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。
A．5
B．4
C．3
D．2
（20）与顺序队相比，链队的（ ）。
A．优点是可以实现无限长队列
B．优点是进队和出队时间性能更好
C．缺点是不能进行顺序访问
D．缺点是不能根据队首和队尾指针计算队的长度
2．填空题
（1）栈是一种特殊的线性表，允许插入和删除运算的一端称为（ ① ）。不允许插入和删除运算的一端称为（ ② ）。
（2）若栈空间大小为n，则最多的连续进栈操作的次数为（ ）。
（3）一个栈的输入序列是12345，输出序列为12345，其进栈出栈的操作为（ ）。
（4）有5个元素，其进栈次序为a、b、c、d、e，在各种可能的出栈次序中，以元素c、d最先出栈（即c第一个且d第二个出栈）的次序有（ ）。
（5）顺序栈用data[0..n—1]存储数据，栈顶指针为top，其初始值为0，则元素x进栈的操作是（ ）。
（6）顺序栈用data[0..n—1]存储数据，栈顶指针为top，其初始值为0，则出栈元素x的操作是（ ）。
（7）（ ）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
（8）设有数组A[0..m]作为循环队列的存储空间，front为队头指针（它指向队首元素的前一位置），rear为队尾指针（它指向队尾元素的位置），则元素x执行进队的操作是（ ）。
（9）设有数组A[0..m]作为循环队列的存储空间，front为队头指针（它指向队首元素的前一位置），rear为队尾指针（它指向队尾元素的位置），则元素出队并保存到x中的操作是（ ）。
（10）设循环队列的大小为70，队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素位置。现经过一系列进队和出队操作后，有front=20，rear=11，则队列中的元素个数是（ ）。
3．简答题
（1）简要说明线性表、栈与队的异同点。
（2）当用一维数组实现顺序栈时，为什么一般将栈底设置在数组的一端，而不是设置在中间？
（3）在以下几种存储结构中，哪个最适合用作链栈？
①带头结点的单链表；
②不带头结点的循环单链表；
③带头结点的双链表；
（4）在循环队列中插入和删除元素时，是否需要移动队中元素？
（5）顺序队的“假溢出”是怎样产生的？如何判断循环队列是空还是满？
4．算法设计题
（1）设计一个算法，利用一个顺序栈将字符数组a[0..n—1]的所有元素逆置。
（2）设计一个算法，将一个十进制正整数d转换为相应的八进制数。
（3）设计一个算法，利用栈的基本运算返回给定栈中的栈底元素，要求仍保持栈中元素次序不变。这里只能使用栈st的基本运算来完成，不能直接用st.data[0]来得到栈底元素。
（4）设计一个算法，利用循环队列的基本运算和例3.13求循环队列元素个数的算法，求指定循环队列中的队尾元素，要求队列中元素次序不改变，算法的空间复杂度为O（1）。
（5）对于循环队列，假设队中所有元素为数字字符，利用循环队列的基本运算和例3.13求循环队列元素个数的算法，删除其中所有奇数字符元素。