PTA第三章栈和队列练习题

1-1经过对货仓S操作：Push(S,1),Push(S,2),Pop(S),Push(S,3),Pop(S),Pop(S)。输出的序列为：123。(2分)TF作者:DS课程组单位:浙江大学1-2在用数组表示的循环行列中，front值必定小于等于rear值。(1分)TF作者:DS课程组单位:浙江大学1-3若一个栈的输入序列为{1,2,3,4,5}，则不行能获得{3,4,1,2,5}这样的出栈序列。(2分)TF作者:徐镜春单位:浙江大学1-4Ifkeysarepushedontoastackintheorder{1,2,3,4,5},thenitisimpossibletoobtaintheoutputsequence{3,4,1,2,5}.(2分)TF作者:徐镜春单位:浙江大学1-5所谓“循环行列”是指用单向循环链表或许循环数组表示的行列。(1分)TF作者:DS课程组单位:浙江大学1-6Analgorithmtocheckforbalancingsymbolsinanexpressionusesastacktostorethesymbols.(1分)TF2-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.bcaefd2.cbdaef3.dcebfa4.afedcb作者:DS课程组单位:浙江大学2-3设一个栈的输入序列是1、2、3、4、5，则以下序列中，是栈的合法输出序列的是？(2分)1.321542.512343.451324.43125作者:DS课程组单位:浙江大学2-4令P代表入栈，O代表出栈。则将一个字符串3*a+b/c变为3a*bc/+的货仓操作序列是哪个？（比如将ABC变为BCA的操作序列是PPOPOO。）(2分)1.PPPOOOPPOPPOOO2.POPOPOPPOPPOOO3.POPPOOPPOPOOPO4.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.bacde2.dbace3.ecbad4.dbcae作者:DS课程组单位:浙江大学2-86的数组来实现循环行列，且目前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.==2.!=3.==+1)%MaxSize4.!=+1)%MaxSize作者:严冰单位:浙江大学城市学院2-15(neuDS)在行列中存取数据元素的原则是（）。(2分)1.先进先出2.先进后出3.后进先出4.没有限制作者:徐婉珍单位:浙江大学2-16循环行列用数组A[0，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-21LetPstandsforpushandOforpop.Whenusingastacktoconverttheinfixexpression3*2+8/4intoapostfixexpression,thestackoperationsequenceis:(3分)1.PPPOOO2.POPOPO3.POPPOO4.PPOOPO作者:DS课程组单位:浙江大学2-22Thepostfixexpressionofa*(b+c)-dis:(2分)1.abc+*d-2.3.4.

abcd*+-abc*+d--+*abcd作者: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-24Supposedthata,b,c,d,eandfarepushedontoastackinthegivenorder.Assumethatpushingandpoppingcanbedonealternatively,butnoconsecutivethreepoppingsareallowed.Thenamongthefollowing,theimpossiblepoppingsequenceis:(2分)1.bcaefd2.cbdaef3.dcebfa4.afedcb作者:DS课程组单位:浙江大学2-25GivenanemptystackSandanemptyqueueQ.Pushelements{1,2,3,4,5,6,7}onebyoneontoS.IfeachelementthatispoppedfromSisenqueuedontoQimmediately,andifthedequeuesequenceis{4,5,7,6,3,2,1},thentheminimumsizeofSmustbe:(2分)1.22.33.44.5作者:MartinEster单位:浙江大学2-26Giventhepushingsequenceofastackas{6,5,4,3,2,1}.Amongthefollowing,theimpossiblepoppingsequenceis:(2分)1.2341562.3465213.5436124.4