资源简介

专题14　栈
知识点一　栈的性质
1.数字1，2，3依次进栈，则不可能的出栈顺序是(　　)
A.3，2，1 B.3，1，2
C.1，2，3 D.2，1，3
2.有一个空栈，规定用Ⅰ表示一个元素入栈，用O表示一个元素出栈。现经过IIOIOOIO系列操作后，元素的出栈顺序是4，1，3，2，则元素的入栈顺序是(　　)
A.1，3，4，2 B.3，4，1，2
C.2，3，1，4 D.1，4，3，2
3.有1个栈，从栈顶到栈底依次为元素a、b、c，并且已知元素d已入栈并出栈，则这四个元素的入栈顺序可能为(　　)
A.a，b，c，d B.b，d，c，a
C.c，d，b，a D.d，a，b，c
4.某栈初始状态为空，有五个元素的入栈序列为a，b，c，d，e，每个元素都只能进行1次入栈和1次出栈操作，若第1个出栈的元素是c，则以下推测正确的是(　　)
A.第2个出栈的元素肯定是b
B.最后1个出栈的元素肯定是a
C.第2个出栈的元素肯定不是d
D.最后1个出栈的元素肯定不是b
5.下列关于数据结构的说法正确的是(　　)
A.栈结构只允许从栈底入栈，从栈顶出栈
B.链表结构只能使用二维列表存储
C.某完全二叉树有偶数个节点，则一定存在度为1的节点
D.数组是一种适合用于组织、存储涉及频繁插入与删除的数据结构
6.假设有一个栈和一个队列，它们的初始状态均为空。元素ABCDEFGH依次进入栈中，每个元素出栈后就立即进入队列中。如果队列中元素的出队顺序是CGFEHDBA，则栈的容量至少是(　　)
A.4 B.5
C.6 D.7
7.元素p，y，t，h，o，n，s按序入栈，从所有出栈序列中(要求元素全部出栈)，以元素n开头且以元素p结尾的出栈序列的数量有(　　)
A.3 B.4
C.5 D.6
8.若一个序列的入栈顺序为1，2，3，4，5，则其出栈顺序不可能的是(　　)
A.1，2，3，4，5 B.4，5，3，2，1
C.4，3，5，1，2 D.3，2，1，5，4
9.用一个带盖的玻璃筒来放取乒乓球，放、取只能在带盖的一端进行(另一端为封闭状态)，且筒的直径只允许一个乒乓球进出。若放入球的编号序列为1、2、3、4，则取出球的编号序列不可能的是(　　)
A.1、2、3、4 B.2、3、4、1
C.4、2、3、1 D.3、2、1、4
10.某小型列车站有一个单轨车厢调度轨道，最多可容纳3节车厢。初始时调度轨上停有2节车厢：最里面是1号车厢，出口处是2号车厢。之后有三节车厢进入调度轨的顺序是3，4，5，那么所有车厢出调度轨的顺序可能是(　　)
A.4，3，2，1，5 B.2，5，4，3，1
C.2，1，5，3，4 D.2，1，5，4，3
11.已知5个元素的出栈序列为1，2，3，4，5，则入栈序列可能是(　　)
A.2，4，3，1，5 B.2，3，1，5，4
C.3，1，4，2，5 D.3，1，2，5，4
12.栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可能出栈，则5个元素全部出栈后，出栈的序列可能是(　　)
A.ABCED B.DBCEA
C.CDABE D.DCBEA
13.一个序列的出栈顺序为1，2，3，4，5，则该序列的入栈顺序不可能为(　　)
A.3，2，1，5，4 B.5，4，3，2，1
C.4，5，2，1，3 D.2，1，4，3，5
14.设n个元素的进栈序列是1，2，3，…，n，出栈序列是p1，p2，…，pn。若p2＝4，则p1的值(　　)
A.可能是2 B.一定是5
C.可能是6 D.不可能是1
15.某APP采用栈结构处理数据，具体的规则如下：
①输入待加入的元素，并转到②
②若栈为空，则转到⑤，否则转到③
③若当前待加入元素与栈顶元素的值相同，则转到④，否则转到⑤
④将栈顶元素出栈，并转到①
⑤将当前待加入元素入栈，并转到①
将元素“ABBACAAAD”，按以上规则依次入栈，则处理后栈中元素从栈底至栈顶依次是(　　)
A.CD B.CAD
C.AACD D.ABCAD
16.若入栈顺序为1，2，3，4，5，6，7，出栈序列为1，4，3，2，7，6，5，则栈深度至少是(　　)
A.3 B.4
C.5 D.6
知识点二　栈的算法实现
1.有如下程序段：
s＝list(input(″输入一个字符串s：″))　#list函数将s转换为列表
top＝－1
a＝[0]*100
i＝0
while iif s[i]＝＝'('：
top＋＝1
a[top]＝i
elif s[i]＝＝')'：
st＝a[top]
top－＝1
s＝s[：st]＋s[i－1：st：－1]＋s[i＋1：]
i－＝2
i＋＝1
print(''.join(s))　#将s 中元素以字符连接成一个新的字符串
执行该程序段后，输入“(ed(y(oc))p)”，输出结果是(　　)
A.pycode B.codepy
C.pcodey D.copyde
2.有如下Python程序段：
import random
a＝[21，7，35，3，12，24，42，－1，－1，1，17，－1，29，38，57]
stack＝[0]*10
key＝random.randint(5，19)*2＋1
p＝0；top＝－1
while p<15：
top＋＝1；stack[top]＝p
if a[p]＝＝－1 or a[p]＝＝key：
break
elif a[p]p＝p*2＋2
else：
p＝p*2＋1
while top ！＝－1：
print(stack[top]，end＝'，')
top －＝1
执行该程序段后，显示的结果不可能的是(　　)
A.13，6，2，0, B.10，4，1，0，
C.5，2，0, D.0，
3.有如下Python程序代码：
def check(s1，s2)：
st＝[″″]*100
top＝－1；head＝0；tail＝len(s2)
for i in s1：
top＋＝1；st[top]＝i
while top！＝－1 and st[top]＝＝s2[head]：
　　　 　top －＝1；head＋＝1
if top＝＝－1 and head＝＝tail：
flag＝True
else：
flag＝False
return flag
a＝″cebad″
b＝input()
print(check(a，b))
执行该程序段后，若输出结果为True，则下列输入值不可能的是(　　)
A.cbeda B.cdabe
C.bdace D.abdec
4.有如下Python程序段：
lst＝[3，5，6，7，10，11，14，16]
i＝len(lst)－1
stk＝[0]*len(lst)
top＝－1
while i>＝0：
if lst[i]%2＝＝0：
top＋＝1
stk[top]＝lst[i]
else：
lst[i＋top＋1]＝lst[i]
i－＝1
i＝0
while top>－1：
lst[i]＝stk[top]
top－＝1
i＋＝1
执行该程序段后，lst[3]的值是(　　)
A.3 B.6
C.14 D.16
5.有如下Python程序段：
import random
p＝″abcde*″；st＝[]；s＝″″
i＝0
while i<＝5：
m＝random.randint(0，1)
if m＝＝0：
st.append(p[i])
i＋＝1
elif len(st)>0：
s＋＝st.pop()
print(s)
执行上述程序段后，输出结果可能的是(　　)
A.a* B.cdabe
C.abcde* D.cdba
6.有如下Python程序段：
import random
q＝[″A″，″B″，″C″，″D″，″#″]
head，tail＝0，4
s＝[0]*5
top＝－1
for i in range(5)：
t＝random.randint(0，1)　#随机生成 0 或 1
if t＝＝0 and headtop＋＝1；s[top]＝q[head]
head＋＝1
elif t＝＝1 and top！＝－1：
s[top]＝0；top－＝1
执行该程序后，s的值不可能的是(　　)
A.['A'，'B'，'C'，'D'，0] B.['D'，0，0，0，0]
C.[0，0，0，0，0] D.['A'，'C'，'D'，0，0]
7.有如下Python程序段：
def sym(d1，d2)：
s1＝d1.split(″，″)　#以“，”将字符串分割成列表
s2＝d2.split(″，″)
if len(s1) ！＝len(s2)：
return False
stk＝[]
i＝j＝0
while istk.append(s1[i])
i＋＝1
while stk ！＝[] and stk[－1]＝＝s2[j]：
stk.pop()　#删除列表stk中的最后一个元素
j＋＝1
return stk＝＝[] and i＝＝j
L1＝″@，a，b，3，c，d″
L2＝input()
print(sym(L1，L2))
执行该程序段后，若输出结果为True，则L2输入的值可能是(　　)
A.a，b，c，d，3 B.c，d，3，b，@，a
C.b，a，@，3，d，c D.d，c，3，@，a，b
8.已知字符“a”的ASCII码值为97，有如下Python程序段：
que＝[″″]*20
head，tail＝0，0
for i in range(3)：
que[tail]＝chr(97＋i)
tail＋＝1
st＝[″b″，″c″，″d″，″a″]
top＝3
while head－1：
if st[top]＝＝que[head]：
head＋＝1
else：
que[tail]＝st[top]
tail＋＝1
top－＝1
print(que[head：tail])
执行该程序段，则输出的结果是(　　)
A.['c'，'d'，'c'] B.['c'，'c'，'d']
C.['c'，''，'d'] D.['c'，'d']
9.有如下Python程序段：
import random
a＝[″″]*10
a[0]＝″A″；s＝″″；top＝0
while 0<＝top<9：
m＝random.randint(0，10)
if m % 2＝＝0：
top＋＝1
a[top]＝chr(ord(a[top－1])＋1)
else：
s＋＝a[top]
top－＝1
执行完上述程序后，输出结果不可能是(　　)
A.A B.ABC
C.FEDCBA D.BDE
10.执行下列Python程序代码：
from random import randint
st＝['']*10；top＝－1；out＝''
s＝input('s＝')
while len(s)>0：
flag＝randint(0，1)
if flag＝＝1：
top＋＝1；st[top]＝s[0]
s＝s[1：]
elif top ！＝－1：
out＋＝st[top]；top －＝1
while top ！＝－1：
out＋＝st[top]；top －＝1
print(out)
当输入的数据为“ABCDE”，则输出的结果不可能的是(　　)
A.CEDAB B.BDECA
C.ABCED D.DCBEA
11.消消乐游戏。随机产生5排(每排10个)a－e之间的随机字母，相邻两个字母之间互不相同见图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个字母的方式显示栈st中各个元素，代码略。
n＝10　#每排字母的个数
st1＝[″″]*(7*n)
totn＝5*n　#游戏开始时总共的字母个数
①________
top1＝－1
for i in s：
top1＋＝1；st1[top1]＝i
display(st1，top1，n)　#按蛇形走线显示栈中各个元素
st2＝[″″]*(n＋1)　#临时存储栈st1顶部不能被消除的元素
top2＝－1
k＝0；chs＝[″a″，″b″，″c″，″d″，″e″]
while top1！＝－1：
k＋＝1
ch＝input(″输入要消除的字母：″)
if ch not in chs：
continue
t＝0
while ：
t＋＝1；top2＋＝1
st2[top2]＝st1[top1]；top1－＝1
if t②________
while st1[top1]＝＝st2[top2] and top1>－1 and top2>－1：
　　　 　top1－＝1；top2－＝1
while top2！＝－1：
top1＋＝1
③________
top2－＝1
if t＝＝n：
top1＋＝1
st1[top1]＝ch
display(st1，top1，n)
print(″恭喜你，大获全胜，尝试的次数：″，k)
(1)当剩余的字母为“ababdaeababa”时，把全部字母消除完至少还要输入的次数是________。
(2)在划线处填入合适的代码。
(3)加框处代码有误，请改正。
12.十进制整数n从左向右读和从右向左读完全相同时称n为“回文数”。小芳想快速找出100到1000000以内所有的满足n是回文数，且它的二进制或十六进制也是回文数的“超级回文数”。她编写的Python程序如下。请在划线处填入合适代码。
def judgehw(n)：　#判断十进制数 n 是否为回文数
d＝n；p＝0
while n！＝0：
①________
n＝n//10
if p＝＝d：
return True
return False
def DtK(n，k)：　#将十进制数n转换为K进制
s＝″0123456789ABCDEF″
a＝[0]*100
top＝0；s1＝″″
while n！＝0：
a[top]＝n%k
top＝top＋1
n＝②________
while top>0：
s1＝③________
top＝top－1
return s1
c＝0
for i in range(100，1000000)：
h1＝DtK(i，16)
b1＝DtK(i，2)
if ④________：
print(i，h1，b1)
c＋＝1
print(″100到1000000以内的超级回文数有：″，str(c))
专题14　栈
知识点一
1.B　[B选项2较1后入栈，则必须于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，由于t2＝t0－1，代入可得总节点数为2*t0＋t1－1，完全二叉树1度节点数量为0或1，若该数为偶数，则t1必须为1。]
6.C　[本题考查栈的性质。C要栈，栈中为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出栈后，栈中元素是1，接着5要出栈，那么要3、4、5依次入栈，此时栈容量也需4，不符合题意。C选项2、1依次出栈后，5要出栈则同样要需3、4、5依次入栈，那么出栈顺序只能是5、4、3而不能是5、3、4，即C项是错误的，而D项符合要求。]
11.D　[A选项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需先入栈，这三个元素的出栈顺序为2，5，4，与题目要求不符。]
14.A　[本题考查栈操作的理解。若p2＝4，那么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　[本题考查栈的性质和基本操作。遇到'('对应的下标入栈，遇到')'，元素出栈。同时列表元素重新组合，组合原则：二端不动，最内层配对括号内的元素翻转，同时这对括号抛弃。算法过程：(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　[有一个入栈序列a，输入一个出栈序列，检测该出栈序列是否符合栈先进先出特性。]
4.D　[本题考查栈的应用。从后往前遍历列表lst，判断元素的奇偶性，将偶数入栈、奇数元素往后移动top＋1个位置，其中top＋1是表示栈的元素个数，当前偶数元素个数。再进行出栈操作，覆盖列表前面的元素。程序执行后，lst元素依次是[6，10，14，16，3，5，7，11]。]
5.D　[遍历字符串p，若产生的随机数为0，则进行入栈操作。若m不为0且栈不为空，进行出栈操作，并将出栈的元素连接到s中。由于最后一个元素入栈后，i的值为5，结束循环，因此最后一个元素不可能出栈。]
6.B　[本题考查队列和栈的基本操作。A选项t产生全0时，q中队列元素依次出队入栈，最后t＝0且head＝＝tail时，没有任何操作。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″，出队和出栈操作，接着″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中，由于栈的顺序为ABCDE，则A选项中，A必须晚于B出栈。]
11.(1)2　(2)①s＝create(totn)或create(5*n) ②top1－＝1　③st1[top1]＝st2[top2]
(3)t解析　(1)输入e，从ababdaeababa变化到ababdbaba，输入d，消完。(2)①调用函数create初始化s。②t是不相同的字母，如果小于10，说明能被消除，出栈一个字母。③将临时栈st2时元素返回到栈st1中。(3)在前n个字母中查找与输入字母ch不同的字母。
12.①p＝p*10＋n%10　②n//k　③s1＋s[a[top－1]]
④judgehw(i) and (h1＝＝h1[：：－1] or b1＝＝b1[：：－1])
解析　①judgehw判断十进制数n是否为回文数，除10的余数是个位数，若要逆序，可以不断地乘以10。②DtK(n，k)将十进制数n转换为K进制，因此要不断地整除以K。③考查的栈，由于可能是十六进制，找到每个数字对应在字符串s中的文本字符s1＋s[a[top－1]]。④十进制整数n是回文，它的二进制或十六进制也是回文数的“超级回文数”。

展开更多......

收起↑