1、专题14栈知识点一栈的性质1.数字1，2，3依次进栈，则不可能的出栈顺序是()A.3，2，1 B.3，1，2 C.1，2，3 D.2，1，32.有一个空栈，规定用表示一个元素入栈，用O表示一个元素出栈。现经过IIOIOOIO系列操作后，元素的出栈顺序是4，1，3，2，则元素的入栈顺序是()A.1，3，4，2 B.3，4，1，2C.2，3，1，4 D.1，4，3，23.有1个栈，从栈顶到栈底依次为元素a、b、c，并且已知元素d已入栈并出栈，则这四个元素的入栈顺序可能为()A.a，b，c，d B.b，d，c，aC.c，d，b，a D.d，a，b，c4.某栈初始状态为空，有五个元素的入栈序列为a，b
2、，c，d，e，每个元素都只能进行1次入栈和1次出栈操作，若第1个出栈的元素是c，则以下推测正确的是()A.第2个出栈的元素肯定是bB.最后1个出栈的元素肯定是aC.第2个出栈的元素肯定不是dD.最后1个出栈的元素肯定不是b5.下列关于数据结构的说法正确的是()A.栈结构只允许从栈底入栈，从栈顶出栈B.链表结构只能使用二维列表存储C.某完全二叉树有偶数个节点，则一定存在度为1的节点D.数组是一种适合用于组织、存储涉及频繁插入与删除的数据结构6.假设有一个栈和一个队列，它们的初始状态均为空。元素ABCDEFGH依次进入栈中，每个元素出栈后就立即进入队列中。如果队列中元素的出队顺序是CGFEHDBA
3、，则栈的容量至少是()A.4 B.5 C.6 D.77.元素p，y，t，h，o，n，s按序入栈，从所有出栈序列中(要求元素全部出栈)，以元素n开头且以元素p结尾的出栈序列的数量有()A.3 B.4 C.5 D.68.若一个序列的入栈顺序为1，2，3，4，5，则其出栈顺序不可能的是()A.1，2，3，4，5 B.4，5，3，2，1C.4，3，5，1，2 D.3，2，1，5，49.用一个带盖的玻璃筒来放取乒乓球，放、取只能在带盖的一端进行(另一端为封闭状态)，且筒的直径只允许一个乒乓球进出。若放入球的编号序列为1、2、3、4，则取出球的编号序列不可能的是()A.1、2、3、4 B.2、3、4、1C
4、.4、2、3、1 D.3、2、1、410.某小型列车站有一个单轨车厢调度轨道，最多可容纳3节车厢。初始时调度轨上停有2节车厢：最里面是1号车厢，出口处是2号车厢。之后有三节车厢进入调度轨的顺序是3，4，5，那么所有车厢出调度轨的顺序可能是()A.4，3，2，1，5 B.2，5，4，3，1C.2，1，5，3，4 D.2，1，5，4，311.已知5个元素的出栈序列为1，2，3，4，5，则入栈序列可能是()A.2，4，3，1，5 B.2，3，1，5，4C.3，1，4，2，5 D.3，1，2，5，412.栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可能出栈，则5个元素全部出栈后
5、，出栈的序列可能是()A.ABCED B.DBCEAC.CDABE D.DCBEA13.一个序列的出栈顺序为1，2，3，4，5，则该序列的入栈顺序不可能为()A.3，2，1，5，4 B.5，4，3，2，1C.4，5，2，1，3 D.2，1，4，3，514.设n个元素的进栈序列是1，2，3，n，出栈序列是p1，p2，pn。若p24，则p1的值()A.可能是2 B.一定是5C.可能是6 D.不可能是115.某APP采用栈结构处理数据，具体的规则如下：输入待加入的元素，并转到若栈为空，则转到，否则转到若当前待加入元素与栈顶元素的值相同，则转到，否则转到将栈顶元素出栈，并转到将当前待加入元素入栈，并转
6、到将元素“ABBACAAAD”，按以上规则依次入栈，则处理后栈中元素从栈底至栈顶依次是()A.CD B.CAD C.AACD D.ABCAD16.若入栈顺序为1，2，3，4，5，6，7，出栈序列为1，4，3，2，7，6，5，则栈深度至少是()A.3 B.4 C.5 D.6知识点二栈的算法实现1.有如下程序段：slist(input(输入一个字符串s：)#list函数将s转换为列表top1a0*100i0while ilen(s)：if si(：top1atopielif si)：statoptop1ss：stsi1：st：1si1：i2i1print(.join(s)#将s 中元素以字符连接成
7、一个新的字符串执行该程序段后，输入“(ed(y(oc)p)”，输出结果是()A.pycode B.codepy C.pcodey D.copyde2.有如下Python程序段：import randoma21，7，35，3，12，24，42，1，1，1，17，1，29，38，57stack0*10keyrandom.randint(5，19)*21p0；top1while p15：top1；stacktoppif ap1 or apkey：breakelif ap0：if lsti%20：top1stktoplstielse：lstitop1lstii1i0while top1：lstistk
8、toptop1i1执行该程序段后，lst3的值是()A.3 B.6 C.14 D.165.有如下Python程序段：import randompabcde*；st；si0while i0：sst.pop()print(s)执行上述程序段后，输出结果可能的是()A.a* B.cdabe C.abcde* D.cdba6.有如下Python程序段：import randomqA，B，C，D，#head，tail0，4s0*5top1for i in range(5)：trandom.randint(0，1)#随机生成 0 或 1if t0 and headtail：top1；stopqheadhe
9、ad1elif t1 and top！1：stop0；top1执行该程序后，s的值不可能的是()A.A，B，C，D，0 B.D，0，0，0，0C.0，0，0，0，0 D.A，C，D，0，07.有如下Python程序段：def sym(d1，d2)：s1d1.split(，)#以“，”将字符串分割成列表s2d2.split(，)if len(s1) ！len(s2)：return Falsestkij0while ilen(s1)：stk.append(s1i)i1while stk ！ and stk1s2j：stk.pop()#删除列表stk中的最后一个元素j1return stk and
10、ijL1，a，b，3，c，dL2input()print(sym(L1，L2)执行该程序段后，若输出结果为True，则L2输入的值可能是()A.a，b，c，d，3 B.c，d，3，b，aC.b，a，3，d，c D.d，c，3，a，b8.已知字符“a”的ASCII码值为97，有如下Python程序段：que*20head，tail0，0for i in range(3)：quetailchr(97i)tail1stb，c，d，atop3while head1：if sttopquehead：head1else：quetailsttoptail1top1print(quehead：tail)执行该
11、程序段，则输出的结果是()A.c，d，c B.c，c，dC.c，d D.c，d9.有如下Python程序段：import randoma*10a0A；s；top0while 0top0：flagrandint(0，1)if flag1：top1；sttops0ss1：elif top ！1：outsttop；top 1while top ！1：outsttop；top 1print(out)当输入的数据为“ABCDE”，则输出的结果不可能的是()A.CEDAB B.BDECAC.ABCED D.DCBEA11.消消乐游戏。随机产生5排(每排10个)ae之间的随机字母，相邻两个字母之间互不相同见
12、图a。玩家输入一个字母，在第一排从左至右查找第1个与之相同的字母，消去该字母，左面的字母自动向右靠拢，若重组后相邻两个字母也相同，则消除相同的字母。如第1次输入字母“a”，得到结果如图b所示。若第1排找不到输入的字母，则在前10个位置查找，如第2次输入字母“a”，得到结果如图c所示。前10个位置中找不到输入的字母，则将该字母添加在最左边，如第3次输入字母“b”，得到结果如图d所示。编制Python程序实现游戏功能，代码如下def create(n)：#产生一个长度为n的包含“a，b，c，d，e”的随机字母，且相邻两个字母不相同，代码略。def display(st，t，n)：#按蛇形走线每排n
13、个字母的方式显示栈st中各个元素，代码略。n10#每排字母的个数st1*(7*n)totn5*n#游戏开始时总共的字母个数_top11for i in s：top11；st1top1idisplay(st1，top1，n)#按蛇形走线显示栈中各个元素st2*(n1)#临时存储栈st1顶部不能被消除的元素top21k0；chsa，b，c，d，ewhile top1！1：k1chinput(输入要消除的字母：)if ch not in chs：continuet0while ：t1；top21st2top2st1top1；top11if t1 and top21： top11；top21while
14、 top2！1：top11_top21if tn：top11st1top1chdisplay(st1，top1，n)print(恭喜你，大获全胜，尝试的次数：，k)(1)当剩余的字母为“ababdaeababa”时，把全部字母消除完至少还要输入的次数是_。(2)在划线处填入合适的代码。(3)加框处代码有误，请改正。12.十进制整数n从左向右读和从右向左读完全相同时称n为“回文数”。小芳想快速找出100到1000000以内所有的满足n是回文数，且它的二进制或十六进制也是回文数的“超级回文数”。她编写的Python程序如下。请在划线处填入合适代码。def judgehw(n)：#判断十进制数 n
15、是否为回文数dn；p0while n！0：_nn/10if pd：return Truereturn Falsedef DtK(n，k)：#将十进制数n转换为K进制s0123456789ABCDEFa0*100top0；s1while n！0：atopn%ktoptop1n_while top0：s1_toptop1return s1c0for i in range(100，1000000)：h1DtK(i，16)b1DtK(i，2)if _：print(i，h1，b1)c1print(100到1000000以内的超级回文数有：，str(c)专题14栈知识点一1.BB选项2较1后入栈，则必须于
16、1先出栈。2.B本题考查栈的性质。2次入栈后再出栈，第1个出栈的是第2个入栈的元素，元素4是第2个入栈的，再入栈1个元素，然后出栈，因此第3个入栈的是元素1，此时栈内只有1个元素，再次执行出栈，即为第1个入栈元素3，最后元素2入栈出栈。3.C本题考查栈的操作。d要第1个出栈，则栈中必须有a、b、c，出栈必须是bca的顺序。4.D第1个出栈的元素是c，则a，b在栈中，b必须于a先出栈，因此b不可以最后出栈。5.C设0度、1度和2度节点数分别为t0、t1、t2，由于t2t01，代入可得总节点数为2*t0t11，完全二叉树1度节点数量为0或1，若该数为偶数，则t1必须为1。6.C本题考查栈的性质。C
17、要栈，栈中为ABC，G要出栈，栈中为ABDEFG，因此至少要6个空间。7.C本题考查栈的性质。元素n开头表示n第1个出栈，p最后一个出栈，则n前面数据出栈的顺序肯定是nohtyp，则s的位置可能在n到p之间的位置出现。8.C本题考查栈的基本性质。当4出栈时，栈中有元素1，2，3，则出栈的顺序必须相反。9.C本题考查栈的性质。C选项当4要出栈时，1、2、3已经在栈中，必须逆序输出。10.D本题考查栈的基本操作与应用。题意所述，1、2号车厢已在栈中，后三节车厢入栈顺序是3、4、5，且栈有3个容量的限制。对于选项A而言，4要想首个出栈，那么3、4要依次入栈，此时栈容量已经超过3。B选项中2出栈后，栈
18、中元素是1，接着5要出栈，那么要3、4、5依次入栈，此时栈容量也需4，不符合题意。C选项2、1依次出栈后，5要出栈则同样要需3、4、5依次入栈，那么出栈顺序只能是5、4、3而不能是5、3、4，即C项是错误的，而D项符合要求。11.DA选项1要先出，栈中有2，4，3，此3个数出栈顺序不对。B选项1要先出，栈中有2，3，出栈一定为3，2。C选项1，2出，栈中有3，4，但必须4先于3先出。D选项1，2出，栈中3，3出，5，4入栈，再出栈。12.D本题考查出入栈相关知识点。四个元素的出栈顺序是一定是DCBA。13.C本题考查栈。如果入栈顺序为4，5，2，1，3，若1最先出栈，则4，5，2需先入栈，这三
19、个元素的出栈顺序为2，5，4，与题目要求不符。14.A本题考查栈操作的理解。若p24，那么p1可以是1、2、3、5中的任意一个，但不能是6。如果是6，那么栈内元素从栈底到栈顶必然是12，3，4，5，此时第二个出栈的只能是5，与题意不符。15.B程序的功能是消除相同字符。AB先入栈，B与栈顶元素相同，B出栈，A也栈顶元素相同，A出栈，CA入栈，A与栈顶元素相同，A出栈，AD入栈。16.A本题考查栈结构的基本操作。操作过程：1入栈1出栈，2、3、4入栈，栈中有3个元素，4、3、2出栈，栈空；5、6、7入栈，栈中有3个元素，7、6、5出栈栈中数据最多时有3个数据。知识点二1.A本题考查栈的性质和基本
20、操作。遇到(对应的下标入栈，遇到)，元素出栈。同时列表元素重新组合，组合原则：二端不动，最内层配对括号内的元素翻转，同时这对括号抛弃。算法过程：(ed(y(oc)p)(ed(yco)p)(edocyp)pycode，选A。2.C本题考查栈的基本操作。A选项p的值依次是0，2，6，13，表示没有找到key，p的值大于15的时候循环结束，输出栈内元素13，6，2，0。B选项p的值是0，1，4，10，选项B可能。C选项p的值为0，2，5，在访问到索引为5的时候，还可以继续访问并没有结束，C选项不可能；D选项p的值为0表示第一次访问的时候遇到了key，key有可能是21，29或35。3.C有一个入栈序
21、列a，输入一个出栈序列，检测该出栈序列是否符合栈先进先出特性。4.D本题考查栈的应用。从后往前遍历列表lst，判断元素的奇偶性，将偶数入栈、奇数元素往后移动top1个位置，其中top1是表示栈的元素个数，当前偶数元素个数。再进行出栈操作，覆盖列表前面的元素。程序执行后，lst元素依次是6，10，14，16，3，5，7，11。5.D遍历字符串p，若产生的随机数为0，则进行入栈操作。若m不为0且栈不为空，进行出栈操作，并将出栈的元素连接到s中。由于最后一个元素入栈后，i的值为5，结束循环，因此最后一个元素不可能出栈。6.B本题考查队列和栈的基本操作。A选项t产生全0时，q中队列元素依次出队入栈，最
22、后t0且headtail时，没有任何操作。B选项D要出栈，ABC都入栈且出栈，执行的次数超过5次。C选项t依次产生1，1，1，1，1时q中队列元素不出队也不入栈。D选项t依次产生0，0，1，0，0时AB先后入栈，然后B出栈，最后CD依次入栈。7.C本题考查栈的综合应用，L1代表入栈次序，L2代表出栈次序，用程序模拟判断出栈次序正确的选项。A选项L1与L2的长度不相等。B选项c要出栈，元素，a，b，3已入栈，必须逆序出栈。同理D选项也是错误的。8.A第1个循环让abc依次入队。当队列和栈不为空时，如果栈顶元素和队首元素相同，则进行出队和出栈操作，否则将栈顶元素出栈并入队。栈顶和队首均为a，出队和
23、出栈操作，接着d入队，d出栈，接着c入队，c出栈，队列中元素为bcdc，接着b出队和出栈。9.B本题考查栈的应用。栈中开始时只有一个元素A，当产生m为偶数时，入栈，且入栈的字母比栈顶元素的ASCII值大1，m为奇数时，出栈。题目问的是出栈序列。A选项，产生m的值为奇数，出栈，栈空结束循环。B选项若A第一个出栈，则栈为空结束，所以不可能。C选项连续产生5个偶数m，再连续产生5个奇数m。D选项产生m的值依次为偶、奇、偶、偶、奇、偶、奇。10.A遍历字符串s，当产生的flag值为1时，将字符串s第1个字符入栈并去除该字符。若flag值为0且栈不空，则进行出栈操作，将出栈的字符连接到out中，由于栈的
24、顺序为ABCDE，则A选项中，A必须晚于B出栈。11.(1)2(2)screate(totn)或create(5*n) top11st1top1st2top2(3)tn and st1top1！ch解析(1)输入e，从ababdaeababa变化到ababdbaba，输入d，消完。(2)调用函数create初始化s。t是不相同的字母，如果小于10，说明能被消除，出栈一个字母。将临时栈st2时元素返回到栈st1中。(3)在前n个字母中查找与输入字母ch不同的字母。12.pp*10n%10n/ks1satop1judgehw(i) and (h1h1：1 or b1b1：1)解析judgehw判断十进制数n是否为回文数，除10的余数是个位数，若要逆序，可以不断地乘以10。DtK(n，k)将十进制数n转换为K进制，因此要不断地整除以K。考查的栈，由于可能是十六进制，找到每个数字对应在字符串s中的文本字符s1satop1。十进制整数n是回文，它的二进制或十六进制也是回文数的“超级回文数”。
