PTA第三章栈与队列练习题.doc

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-4If 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-6An algorithm to check for balancing symbols in an expression uses a stack to store the symbols、 (1分)T F2-1设栈S与队列Q得初始状态均为空,元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队得顺序就是b、d、c、f、e、a、g,则栈S得容量至少就是: (2分)1. 12. 23. 34. 4作者: DS课程组单位: 浙江大学2-2若元素a、b、c、d、e、f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈工作,则不可能得到得出栈序列就是？ (2分)1. b c a e f d2. c b d a e f3. d c e b f a4. a f e d c b作者: DS课程组单位: 浙江大学2-3设一个栈得输入序列就是1、2、3、4、5,则下列序列中,就是栈得合法输出序列得就是？ (2分)1. 3 2 1 5 42. 5 1 2 3 43. 4 5 1 3 24. 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. 12. 33. 54. 1或者5作者: DS课程组单位: 浙江大学2-6为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出得数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区得逻辑结构应该就是？ (1分)1. 堆栈2. 队列3. 树4. 图作者: DS课程组单位: 浙江大学2-7某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作,则不可能得到得出队序列就是: (2分)1. b a c d e2. d b a c e3. e c b a d4. d b c a e作者: DS课程组单位: 浙江大学2-8若用大小为6得数组来实现循环队列,且当前front与rear得值分别为0与4。当从队列中删除两个元素,再加入两个元素后,front与rear得值分别为多少？ (2分)1. 2与02. 2与23. 2与44. 2与6作者: DS课程组单位: 浙江大学2-10以下不就是栈得基本运算得就是( )。 (2分)1. 删除栈顶元素 2. 删除栈底元素3. 判断栈就是否为空4. 将栈置为空栈作者: 严冰单位: 浙江大学城市学院2-11在一个链队列中,front与rear分别为头指针与尾指针,则插入一个结点s得操作为( )。 (2分)1. front=front-next2. s-next=rear;rear=s3. rear-next=s;rear=s;4. s-next=front;front=s;作者: 杨斌单位: 枣庄学院2-12依次在初始为空得队列中插入元素a,b,c,d以后,紧接着做了两次删除操作,此时得队头元素就是( )。 (2分)1. a2. b3. c4. d作者: 杨斌单位: 枣庄学院2-13当用大小为N得数组存储顺序循环队列时,该队列得最大长度为( )。 (2分)1. N2. N-13. N+14. N+2作者: 杨斌单位: 枣庄学院2-14判断一个循环队列QU(最多元素为MaxSize)为空得条件就是()。 (2分)1. QU、front = QU、rear2. QU、front != QU、rear3. QU、front = (QU、rear + 1) % MaxSize4. QU、front != (QU、rear + 1) % MaxSize作者: 严冰单位: 浙江大学城市学院2-15(neuDS)在队列中存取数据元素得原则就是( )。(2分)1. 先进先出 2. 先进后出3. 后进先出4. 没有限制作者: 徐婉珍单位: 浙江大学2-16循环队列用数组A0,m-1存放其元素值,已知其头尾指针分别就是front与rear,则当前队列中得元素个数就是( )。 (2分)1. (rear-front+m)%m2. rear-front3. rear-front-14. rear-front作者: 杨斌单位: 枣庄学院2-17若以1234作为双端队列得输入序列,则既不能由输入受限得双端队列得到,也不能由输出受限得双端队列得到得就是( )。 (2分)1. 12342. 41323. 42314. 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-21Let 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. PPPOOO2. POPOPO3. POPPOO4. PPOOPO作者: DS课程组单位: 浙江大学2-22The 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, 32. 2, 3, 4, 5, 6, 13. 3, 4, 5, 6, 1, 24. 6, 5, 4, 3, 2, 1作者: 考研真题单位: 浙江大学2-24Supposed 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 d2. c b d a e f3. d c e b f a4. a f e d c b作者: DS课程组单位: 浙江大学2-25Given 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. 22. 33. 44. 5作者: Martin Ester单位: 浙江大学2-26Given 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 62. 3 4 6 5 2 13. 5 4 3 6 1 24. 4 5 3 1 2 6作者: DS课程组单位: 浙江大学2-27下列关于栈得叙述中,错误得就是:(2分)1. 采用非递归方式重写递归程序时必须使用栈2. 函数调用时,系统要用栈保存必要得信息3. 只要确定了入栈次序,即可确定出栈次序4. 栈就是一种受限得线性表,允许在其两端进行操作1. 仅 12. 仅 1、2、33. 仅 1、3、44. 仅 2、3、42李文超61、0F(2、0)F(1、0)T(2、0)T(2、0)F(1、0)T(1、0)C(2、0)D(2、0)A(2、0)D(2、0)D(2、0)B(1、0)D(2、0)A(2、0)B(2、0)C(2、0)C(2、0)B(2、0)A(2、0)A(2、0)A(2、0)C(2、0)B(2、0)B(2、0)B(2、0)B(2、0)C(3、0)A(2、0)CD(2、0)D(2、0)B(2、0)C(2、0)