第三章、第四章习题1.填空[1]栈通常采用的两种存储结构是；其判定栈空的条件分别是，判定栈满的条件分别是。[2]可作为实现递归函数调用的一种数据结构。[3]表达式a*(b+c)-d的后缀表达式是。[4]栈和队列是两种特殊的线性表，栈的操作特性是，队列的操作特性是，栈和队列的主要区别在于。[5]循环队列的引入是为了克服。[6]数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为。[7]用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是和。[8]串是一种特殊的线性表，其特殊性体现在。[9]两个串相等的充分必要条件是。2.选择题⑴若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（）。A不确定Bn-iCn-i-1Dn-i+1⑵设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（
）。A6
B4
C3
D2⑶一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（）。ABCD⑷设计一个判别表达式中左右括号是否配对的算法，采用（）数据结构最佳A顺序表B栈C队列D链表⑸在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（）结构。A栈B队列C数组D线性表⑹一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（）。ABCD⑺栈和队列的主要区别在于（）。A它们的逻辑结构不一样B它们的存储结构不一样C所包含的运算不一样D插入、删除运算的限定不一样⑻设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（）。AS1的栈底位置为0，S2的栈底位置为n-1BS1的栈底位置为0，S2的栈底位置为n/2CS1的栈底位置为0，S2的栈底位置为nDS1的栈底位置为0，S2的栈底位置为1解答题3.设有一个栈，元素进栈的次序为A，B，C，D，E，能否得到如下出栈序列，若能，请写出操作序列，若不能，请说明原因。4.举例说明顺序队列的“假溢出”现象。