PTA第三章栈与队列练习题

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-4Ifkeysarepushedontoastackintheorder{1,2,3,4,5},thenitisimpossibletoobtaintheoutputsequence{3,4,1,2,5}、(2分)T

F作者:徐镜春单位:浙江大学1-5所谓“循环队列”就是指用单向循环链表或者循环数组表示得队列。(1分)T

F作者:DS课程组单位:浙江大学1-6Analgorithmtocheckforbalancingsymbolsinanexpressionusesastacktostorethesymbols、(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分)1234作者:DS课程组单位:浙江大学2-2若元素a、b、c、d、e、f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈工作,则不可能得到得出栈序列就是？(2分)bcaefdcbdaefdcebfaafedcb作者:DS课程组单位:浙江大学2-3设一个栈得输入序列就是1、2、3、4、5,则下列序列中,就是栈得合法输出序列得就是？(2分)32154512344513243125作者:DS课程组单位:浙江大学2-4令P代表入栈,O代表出栈。则将一个字符串3*a+b/c变为3a*bc/+得堆栈操作序列就是哪个？(例如将ABC变成BCA得操作序列就是PPOPOO。)(2分)PPPOOOPPOPPOOOPOPOPOPPOPPOOOPOPPOOPPOPOOPOPOPPOOPPOPPOOO作者:DS课程组单位:浙江大学2-5设一个堆栈得入栈顺序就是1、2、3、4、5。若第一个出栈得元素就是4,则最后一个出栈得元素必定就是:(2分)1351或者5作者:DS课程组单位:浙江大学2-6为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出得数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区得逻辑结构应该就是？(1分)堆栈队列树图作者:DS课程组单位:浙江大学2-7某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作,则不可能得到得出队序列就是:(2分)bacdedbaceecbaddbcae作者:DS课程组单位:浙江大学2-8若用大小为6得数组来实现循环队列,且当前front与rear得值分别为0与4。当从队列中删除两个元素,再加入两个元素后,front与rear得值分别为多少？(2分)2与02与22与42与6作者:DS课程组单位:浙江大学2-10以下不就是栈得基本运算得就是()。(2分)删除栈顶元素删除栈底元素判断栈就是否为空将栈置为空栈作者:严冰单位:浙江大学城市学院2-11在一个链队列中,front与rear分别为头指针与尾指针,则插入一个结点s得操作为()。(2分)front=front->nexts->next=rear;rear=srear->next=s;rear=s;s->next=front;front=s;作者:杨斌单位:枣庄学院2-12依次在初始为空得队列中插入元素a,b,c,d以后,紧接着做了两次删除操作,此时得队头元素就是()。(2分)abcd作者:杨斌单位:枣庄学院2-13当用大小为N得数组存储顺序循环队列时,该队列得最大长度为()。(2分)NN-1N+1N+2作者:杨斌单位:枣庄学院2-14判断一个循环队列QU(最多元素为MaxSize)为空得条件就是()。(2分)QU、front==QU、rearQU、front!=QU、rearQU、front==(QU、rear+1)%MaxSizeQU、front!=(QU、rear+1)%MaxSize作者:严冰单位:浙江大学城市学院2-15(neuDS)在队列中存取数据元素得原则就是()。(2分)先进先出先进后出后进先出没有限制作者:徐婉珍单位:浙江大学2-16循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别就是front与rear,则当前队列中得元素个数就是()。(2分)(rear-front+m)%mrear-frontrear-front-1rear-front作者:杨斌单位:枣庄学院2-17若以1234作为双端队列得输入序列,则既不能由输入受限得双端队列得到,也不能由输出受限得双端队列得到得就是()。(2分)1234413242314213作者:杨斌单位:枣庄学院2-18(neuDS)在链栈中,进行出栈操作时()。(2分)需要判断栈就是否满需要判断栈就是否为空需要判断栈元素得类型无需对栈作任何操作作者:徐婉珍单位:广东东软学院2-19(neuDS)在栈中存取数据得原则就是()。(2分)先进先出先进后出后进后出没有限制作者:徐婉珍单位:广东东软学院2-20链式栈与顺序栈相比,一个比较明显得优点就是()。(2分)插入操作更加方便通常不会出现栈满得情况不会出现栈空得情况删除操作更加方便作者:严冰单位:浙江大学城市学院2-21若(a-b)*(c+d)就是中序表达式,则其后序表达式就是()。(2分)abcd+*-ab-cd+*ab-*cd+a-bcd+*作者:严冰单位:浙江大学城市学院2-21LetPstandsforpushandOforpop、Whenusingastacktoconverttheinfixexpression3*2+8/4intoapostfixexpression,thestackoperationsequenceis:(3分)PPPOOOPOPOPOPOPPOOPPOOPO作者:DS课程组单位:浙江大学2-22Thepostfixexpressionofa*(b+c)-dis:(2分)abc+*d-abcd*+-abc*+d--+*abcd作者:DS课程组单位:浙江大学2-23现有队列Q与栈S,初始时Q中得元素依次就是{1,2,3,4,5,6}(1在队头),S为空。若允许下列3种操作:(1)出队并输出出队元素;(2)出队并将出队元素入栈;(3)出栈并输出出栈元素,则不能得到得输出序列就是:(2分)1,2,5,6,4,32,3,4,5,6,13,4,5,6,1,26,5,4,3,2,1作者:考研真题单位:浙江大学2-24Supposedthata,b,c,d,eandfarepushedontoastackinthegivenorder、Assumethatpushingandpoppingcanbedonealternatively,butnoconsecutivethreepoppingsareallowed、Thenamongthefollowing,theimpossiblepoppingsequenceis:(2分)bcaefdcbdaefdcebfaafedcb作者:DS课程组单位:浙江大学2-25GivenanemptystackSandanemptyqueueQ、Pushelements{1,2,3,4,5,6,7}onebyoneontoS、IfeachelementthatispoppedfromSisenqueuedontoQimmediately,andifthedequeuesequenceis{4,5,7,6,3,2,1},thentheminimumsizeofSmustbe:(2分)2345作者:MartinEster单位:浙江大学2-26Giventhepushingsequenceofastackas{6,5,4,3,2,1}、Amongthefollowing,theimpossiblepoppingsequenceis:(2分)234156346521543612453126作者:DS课程组单位:浙江大学2-27下列关于栈得叙述中,错误得就是:(2分)采用非递归方式重写递归程序时必须使用栈函数调用时,系统要用栈保存必要得信息只要确定了入栈次序,即可确定出栈次序栈就是一种受限得线性表,允许在其两端进行操作仅1仅1、2、3仅1、3、4仅2、3、42 李文超 61、0 F(2、0