PTA第三章栈和队列练习题.pdf
1-1 通过对堆栈 S 操作：Push(S,1),Push(S,2),Pop(S),Push(S,3),Pop(S),Pop(S)。输出的序列为：123。(2 分)T?F 作者:DS 课程组 单位:浙江大学 1-2 在用数组表示的循环队列中，front 值一定小于等于 rear 值。(1 分)T?F 作者:DS 课程组 单位:浙江大学 1-3 若一个栈的输入序列为1,2,3,4,5，则不可能得到3,4,1,2,5这样的出栈序列。(2 分)T?F 作者:徐镜春 单位:浙江大学 1-4 If keys are pushed onto a stack in the order 1,2,3,4,5,then it is impossible to obtain the output sequence 3,4,1,2,5.(2 分)T?F 作者:徐镜春 单位:浙江大学 1-5 所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。(1 分)T?F 作者:DS 课程组 单位:浙江大学 1-6 An algorithm to check for balancing symbols in an expression uses a stack to store the symbols.(1 分)T?F 2-1 设栈 S 和队列 Q 的初始状态均为空，元素 a、b、c、d、e、f、g 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b、d、c、f、e、a、g，则栈 S 的容量至少是：(2 分)1.1 2.2 3.3 4.4 作者:DS 课程组 单位:浙江大学 2-2 若元素 a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是(2 分)1.b c a e f d 2.c b d a e f 3.d c e b f a 4.a f e d c b 作者:DS 课程组 单位:浙江大学 2-3 设一个栈的输入序列是 1、2、3、4、5，则下列序列中，是栈的合法输出序列的是(2 分)1.3 2 1 5 4 2.5 1 2 3 4 3.4 5 1 3 2 4.4 3 1 2 5 作者:DS 课程组 单位:浙江大学 2-4 令 P 代表入栈，O 代表出栈。则将一个字符串3*a+b/c变为3 a*b c/+的堆栈操作序列是哪个（例如将ABC变成BCA的操作序列是 PPOPOO。）(2 分)1.PPPOOOPPOPPOOO 2.POPOPOPPOPPOOO 3.POPPOOPPOPOOPO 4.POPPOOPPOPPOOO 作者:DS 课程组 单位:浙江大学 2-5 设一个堆栈的入栈顺序是 1、2、3、4、5。若第一个出栈的元素是 4，则最后一个出栈的元素必定是：(2 分)1.1 2.3 3.5 4.1 或者 5 作者:DS 课程组 单位:浙江大学 2-6 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是(1 分)1.堆栈 2.队列 3.树 4.图 作者:DS 课程组 单位:浙江大学 2-7 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素 a、b、c、d、e 依次入此队列后再进行出队操作，则不可能得到的出队序列是：(2分)1.b a c d e 2.d b a c e 3.e c b a d 4.d b c a e 作者:DS 课程组 单位:浙江大学 2-8 若用大小为 6 的数组来实现循环队列，且当前front和rear的值分别为 0 和 4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少(2分)1.2 和 0 2.2 和 2 3.2 和 4 4.2 和 6 作者:DS 课程组 单位:浙江大学 2-10 以下不是栈的基本运算的是()。(2 分)1.删除栈顶元素 2.删除栈底元素 3.判断栈是否为空 4.将栈置为空栈 作者:严冰 单位:浙江大学城市学院 2-11 在一个链队列中，front 和 rear 分别为头指针和尾指针，则插入一个结点 s 的操作为（）。(2 分)1.front=front-next 2.s-next=rear;rear=s 3.rear-next=s;rear=s;4.s-next=front;front=s;作者:杨斌 单位:枣庄学院 2-12 依次在初始为空的队列中插入元素 a,b,c,d 以后，紧接着做了两次删除操作，此时的队头元素是（）。(2 分)1.a 2.b 3.c 4.d 作者:杨斌 单位:枣庄学院 2-13 当用大小为 N 的数组存储顺序循环队列时，该队列的最大长度为（）。(2 分)1.N 2.N-1 3.N+1 4.N+2 作者:杨斌 单位:枣庄学院 2-14 判断一个循环队列 QU（最多元素为 MaxSize）为空的条件是（）。(2 分)1.=2.!=3.=+1)%MaxSize 4.!=+1)%MaxSize 作者:严冰 单位:浙江大学城市学院 2-15(neuDS)在队列中存取数据元素的原则是（）。(2 分)1.先进先出 2.先进后出 3.后进先出 4.没有限制 作者:徐婉珍 单位:浙江大学 2-16 循环队列用数组 A0，m-1存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列中的元素个数是（）。(2 分)1.(rear-front+m)%m 2.rear-front 3.rear-front-1 4.rear-front 作者:杨斌 单位:枣庄学院 2-17 若以 1234 作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的是（）。(2 分)1.1234 2.4132 3.4231 4.4213 作者:杨斌 单位:枣庄学院 2-18(neuDS)在链栈中，进行出栈操作时()。(2 分)1.需要判断栈是否满 2.需要判断栈是否为空 3.需要判断栈元素的类型 4.无需对栈作任何操作 作者:徐婉珍 单位:广东东软学院 2-19(neuDS)在栈中存取数据的原则是（）。(2 分)1.先进先出 2.先进后出 3.后进后出 4.没有限制 作者:徐婉珍 单位:广东东软学院 2-20 链式栈与顺序栈相比，一个比较明显的优点是（）。(2 分)1.插入操作更加方便 2.通常不会出现栈满的情况 3.不会出现栈空的情况 4.删除操作更加方便 作者:严冰 单位:浙江大学城市学院 2-21 若(a-b)*(c+d)是中序表达式，则其后序表达式是（）。(2 分)1.abcd+*-2.ab-cd+*3.ab-*cd+4.a-bcd+*作者:严冰 单位:浙江大学城市学院 2-21 Let P stands for push and O for pop.When using a stack to convert the infix expression 3*2+8/4 into a postfix expression,the stack operation sequence is:(3 分)1.PPPOOO 2.POPOPO 3.POPPOO 4.PPOOPO 作者:DS 课程组 单位:浙江大学 2-22 The postfix expression of a*(b+c)-d is:(2 分)1.a b c+*d-2.a b c d*+-3.a b c*+d-4.-+*a b c d 作者:DS 课程组 单位:浙江大学 2-23 现有队列 Q 与栈 S，初始时 Q 中的元素依次是 1,2,3,4,5,6（1 在队头），S 为空。若允许下列 3 种操作：（1）出队并输出出队元素；（2）出队并将出队元素入栈；（3）出栈并输出出栈元素，则不能得到的输出序列是：(2 分)1.1,2,5,6,4,3 2.2,3,4,5,6,1 3.3,4,5,6,1,2 4.6,5,4,3,2,1 作者:考研真题 单位:浙江大学 2-24 Supposed that a,b,c,d,e and f are pushed onto a stack in the given order.Assume that pushing and popping can be done alternatively,but no consecutive three poppings are allowed.Then among the following,the impossible popping sequence is:(2分)1.b c a e f d 2.c b d a e f 3.d c e b f a 4.a f e d c b 作者:DS 课程组 单位:浙江大学 2-25 Given an empty stack S and an empty queue Q.Push elements 1,2,3,4,5,6,7 one by one onto S.If each element that is popped from S is enqueued onto Q immediately,and if the dequeue sequence is 4,5,7,6,3,2,1,then the minimum size of S must be:(2分)1.2 2.3 3.4 4.5 作者:Martin Ester 单位:浙江大学 2-26 Given the pushing sequence of a stack as 6,5,4,3,2,1.Among the following,the impossible popping sequence is:(2 分)1.2 3 4 1 5 6 2.3 4 6 5 2 1 3.5 4 3 6 1 2 4.4 5 3 1 2 6 作者:DS 课程组 单位:浙江大学 2-27 下列关于栈的叙述中，错误的是：(2 分)1.采用非递归方式重写递归程序时必须使用栈 2.函数调用时，系统要用栈保存必要的信息 3.只要确定了入栈次序，即可确定出栈次序 4.栈是一种受限的线性表，允许在其两端进行操作 1.仅 1 2.仅 1、2、3 3.仅 1、3、4 4.仅 2、3、4 0218 李文超 F F T T F T C D A D D B D A B C C B A A A C B B B B C A C D D B C
