PTA第三章栈和队列练习题.pdf

吾日三省乎吾身。为人谋而不忠乎？与朋友交而不信乎？传不习乎？——《论语》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—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