资源简介

4.3　栈
学习目标　
1.画出栈的示意图,理解入栈和出栈的操作。
2.通过出栈顺序,推算入栈顺序,理解栈的后进先出的基本特性。
3.根据栈的性质,实现栈的算法实现。
　　　　　　 　　　　　 　　　　　
(2024年6月浙江选考)栈初始为空,经过一系列入栈、出栈操作后,栈又为空。若元素入栈的顺序为“生”“旦”“净”“末”“丑”,则所有可能的出栈序列中,以“旦”结尾的序列个数为(　　)
A.3 B.4
C.5 D.6
　　栈主要用于计算过程中保存的临时数据,是一种只能在数组一端进行存取的数据结构,最大特点是数据在存取时,无需查询,时间复杂度为O(1),后存的数据先被取出。栈中元素必须满足先进后出原则。由于栈顶指针top指向栈中最后一个元素的索引位置,因此栈中元素的个数为top+1,出栈时往往先要读取栈顶元素,再向下移动指针,入栈时,需先向上移动指针,再存入数据。
例1 有后缀表达式“1 3+2*3+2 *”,现利用栈计算该表达式:从左向右扫描,遇到数字时,数字入栈;遇到运算符时,两个元素出栈,用运算符计算,所得结果入栈,如此反复操作,直到扫描结束,栈顶元素是(　　)
A.21 B.22
C.23 D.24
变式1 有后缀表达式“346*+52*+”,现利用栈计算该表达式:从左向右扫描,遇到数字时,数字入栈;遇到运算符时,两个元素出栈,用运算符计算,所得结果入栈,如此反复操作,直到扫描结束,栈的深度至少是(　　)
A.2 B.3
C.4 D.5
例2 有如下Python程序段:
import random
a=['A','B','#','#','C','D','#']
stk=[0]*len(a);top=-1
for i in range(len(a)):
　　op=random.randint(0,1) #随机生成0或1
　　if op==1 and a[i]!='#':
　　　　top+=1;stk[top]=a[i]
　　　　a[i]='#'
　　elif op==0 and top!=-1 and a[i]=='#':
　　　　a[i]=stk[top];top-=1
执行该程序段后,a的值不可能的是(　　)
A.['A','B','#','#','C','D','#']
B.['#','#','#','#','#','#','#']
C.['#','B','#','#','C','D','A']
D.['#','#','A','B','C','D','#']
变式2 列表c长度为100,如图所示,其中c[10]~c[89]各元素的值均为1-99的随机正整数。执行如下程序段,输出的最后一行是(　　)
i 0 1 2 3 4 5 6 7 8 9 … 90 91 92 93 94 95 96 97 98 99
c[i] 4 10 15 8 12 13 15 7 5 10 … 4 55 1 12 39 15 40 21 25 18
top=-1
for i in range(len(c)):
　　t=0
　　while top>=0 and c[top]>=c[i]:
　　　　t+=1
　　　　top-=1
　　top+=1
　　c[top]=c[i]
　　print(top,t)
A.5 4　　　　　　　　B.3 2　　　　　　　　C.4 3　　　　　　　　D.2 3
1.元素30,97,32,75,99入栈的顺序为30,97,32,75,99,如果最先出栈的是32,那么最后出栈的不可能的是(　　)
A.30 B.97
C.75 D.99
2.栈S最大长度为3,若元素a,b,c,d依次入栈,则可能的出栈序列为(　　)
A.d,c,b,a B.b,a,d,c
C.c,a,b,d D.c,d,a,b
3.有一个空栈,若元素入栈的顺序是a,b,c,d,e,第1个出栈的元素是d,则当所有元素都出栈后,下列说法正确的是(　　)
A.c一定比a,b先出栈
B.最后一个出栈的元素一定是e
C.最后一个出栈的元素一定是a
D.a,b,c出栈的先后顺序不确定
4.已知栈st中从栈底到栈顶的元素依次为a、b、c,元素 d 正等待入栈,以下出栈序列不可能的是(　　)
A.c,b,d,a B.c,d,a,b
C.c,d,b,a D.c,b,a,d
5.有1个栈初始为空,其元素入栈顺序依次为s,t,r,w,u,y,m,若经过入栈和出栈操作后,栈底至栈顶元素分别为t,w,y,则第3个出栈元素为(　　)
A.m B.w
C.u D.s
6.栈初始为空,经过一系列的入栈、出栈操作后,栈为空,若元素入栈顺序为ABCD,则所有可能的出栈序列中,C比A先出栈的个数为(　　)
A.5 B.6
C.7 D.8
7.栈S从栈底到栈顶的元素依次为5,8,3,9,7,队列Q初始为空。约定:栈中元素依次出栈后入队,当队尾元素小于队首元素时,队列元素会出队后入栈,直到队尾元素不小于队首元素。当栈为空时,队列中队首到队尾的元素依次为(　　)
A.3,7,9,8,5 B.3,9,7,8,5
C.5,9,7,8,3 D.5,7,9,8,3
8.有一个队列和一个栈,其中队列中队首到队尾的元素依次为3,15,8,7,栈中栈顶到栈底的元素依次为6,9,12,10。现在有两种操作,操作S是指队列中1个元素出队后入栈,操作Q是栈中1个元素出栈后入队。则经过QSSQSQQS操作后,队列中队首到队尾的元素依次是(　　)
A.6,15,8,3 B.10,15,8,3
C.3,6,15,7 D.3,10,15,7
9.有如下程序段:
s=["A","B","C","D","E"]
m=[1,3,2,1,2]
st=[""]*4;top=-1
j=0
for i in range(len(s)):
　　top+=1
　　st[top]=s[i]
　　while top!=-1 and ord(st[top])-ord("A")==m[j]:
　　　　top-=1
　　　　j+=1
print(st[:top+1])
执行该程序段后,输出内容是(　　)
A.[]
B.['A','C']
C.['A','E']
D.['A','C','E']
10.有如下Python程序段:
s=input("请输入:")
stack=[""]*10;top=-1
for i in range(len(s)):
　　if top==-1 or stack[top]!=s[i]:
　　　　top+=1
　　　　stack[top]=s[i]
　　else:
　　　　top-=1
print(top+1)
执行该程序段后,输入变量s的值,程序的输出结果与其他选项不同的是(　　)
A."aabbc" B."aaabbac"
C."bbcaa" D."aabcb"
11.有如下Python程序段:
stk=[5,2,6,3,7];q,s=0,0
lst=[0]*10;top=len(stk)-1
while top>-1:
　　s+=stk[top]
　　if s % a==0:
　　　　break
　　else:
　　　　lst[q]=stk[top]
　　　　q+=1
　　top-=1
for i in range (q):
　　top+=1;stk[top]=lst[i]
若a为[2,4]区间的随机整数,执行该程序段后,stk的值不可能是(　　)
A.[5,2,6,7,3] B.[5,2,6,3,7]
C.[5,2,7,6,3] D.[5,2,7,3,6]
12.有如下Python程序段:
import random
p="abcde*";s=""
st=[""]*1000;top=-1
i=0
while i<=5:
　　m=random.randint(0,1)
　　if m==0:
　　　　top+=1
　　　　st[top]=p[i]
　　　　i+=1
　　elif len(st)>0:
　　　　s+=st[top]
　　　　top-=1
print(s)
执行上述程序段后,输出结果可能的是(　　)
A.a* B.cdabe
C.abcde* D.cdba
13.给定长度为n的数组ts,需为每个元素ts[i]在其后寻找首个更大元素ts[j]。若找到,将两者位置距离存入ans[i],否则ans[i]的值为0。例如数组ts为[33,34,35,31,29,32,36,33],则数组ans为[1,1,4,2,1,1,0,0]。实现该功能的程序段如下,方框处应填入的代码是(　　)
ans=[0]*n;s=[0]*n
top=-1
for i in range(n):
　　t=ts[i]
　　while top>=0 and t>ts[s[top]]:
　　　　j=s[top]
　　　　top-=1
　　　　　　　　　　　　　　
　　top+=1
　　s[top]=i
A.ans[i]=j-i B.ans[i]+=1
C.ans[j]=i-j D.ans[i-j]+=1
1.有五个元素的出栈顺序依次为1,2,3,4,5。则这五个元素的入栈顺序可能是(　　)
A.1,4,5,3,2 B.2,4,3,1,5
C.3,5,4,1,2 D.5,4,1,3,2
2.元素A,B,C,D,E,F按序入栈,在所有出栈序列中(元素需全部出栈),以元素E开头且以元素A结尾的出栈序列的数量有(　　)
A.3 B.4
C.5 D.6
3.已知某栈结构初始状态为空,将“岸南江春绿风又”中各个汉字依次入栈,若要求出栈次序为“春风又绿江南岸”,则栈的容量至少为(　　)
A.6 B.5
C.4 D.3
4.栈初始为空,经过一系列入栈、出栈操作后,栈又为空。若元素入栈顺序为“红”、“橙”、“黄”、“绿”、“蓝”,在所有可能的出栈序列中,“红”比“蓝”晚三步出栈的序列个数是(若出栈顺序为“蓝红某某某”,则表示“红”比“蓝”出栈晚一步)(　　)
A.3 B.4
C.5 D.6
5.S从栈底到栈顶元素依次为1,2,4,5,现有新元素3。经过如下操作:若栈非空且新元素小于或等于栈顶元素,栈顶元素出栈,直到栈空或新元素大于栈顶元素,再将新元素入栈。则S中剩余元素个数为(　　)
A.1 B.2
C.3 D.4
6.利用栈求逆波兰表达式(表达式由操作数和运算符组成)的方法是:从左往右扫描该表达式,遇到操作数时入栈;遇到运算符时,把处于栈上方的两个元素依次出栈,用运算符计算,并把计算结果压入栈中。如此反复操作,直至表达式扫描结束。当用该算法求逆波兰表达式abcd-*e/+f-的值时(abcdef表示不同的操作数),所使用栈的深度至少为(　　)
A.3 B.4
C.5 D.6
7.栈S从栈底到栈顶的元素依次为2、4,队列Q从队首到队尾的元素依次为1、3。约定:A操作是取出栈顶元素x和队首元素y,将x和y相加后入队;M操作是取出栈顶元素x和队首元素y,将x和y相乘后入栈。则经过MAM系列操作后,栈顶元素为(　　)
A.14 B.20
C.26 D.28
8.栈S从栈底到栈顶的元素依次为1,2,3,队列Q初始为空。约定:U操作是指元素出栈后入队,H操作是指元素出队后再入队。经过UUHU系列操作后,队列中队首到队尾的元素依次为(　　)
A.2,1,3 B.3,1,2
C.1,3,2 D.2,3,1
9.有如下Python程序段:
st=[0]*10
a=[4,6,1,7,2,8,6]
top=0;st[top]=a[0]
for i in range(1,len(a)):
　　while top!=-1 and a[i]　　　　top-=1
　　top+=1
　　st[top]=a[i]
执行该程序段后,变量top的值为(　　)
A.-1 B.1
C.2 D.3
10.已知字符“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']
11.有如下Python程序段:
s=[0]*10;q=[0]*10
a=[6,3,2,4,2,1,5]
n,top,head,tail=len(a),0,0,0
s[top]=a[0]
for i in range(1,n):
　　while top!=-1 and a[i]>s[top]:
　　　　q[tail]=s[top];tail+=1
　　　　top-=1
　　top+=1;s[top]=a[i]
while head!=tail:
　　print(q[head],end=' ')
　　head+=1
程序段运行后,输出第3个数字为(　　)
A.1 B.2
C.3 D.4
12.有如下Python程序:
stackA=[0]*6
stackB=[0]*6
topA=topB=-1
d=[5,9,4,8,7,2]
for i in range(len(d)):
　　while topA!=-1 and d[i]　　　　topB+=1
　　　　stackB[topB]=stackA[topA]
　　　　topA-=1
　　topA+=1;stackA[topA]=d[i]
程序执行过程中,变量topB的最大值为(　　)
A.2 B.3
C.4 D.5
13.有如下Python程序段:
import random
lst=['A','B','C','D']
st=[0]*len(lst)
i,top=0,-1
while i　　k=random.randint(0,1)
　　if k==0:
　　　　top+=1
　　　　st[top]=lst[i]
　　　　i+=1
　　elif top!=-1:
　　　　lst[i]=st[top]
　　　　top-=1
执行该程序段后,lst的值不可能是(　　)
A.['A','B','C','D']
B.['A','B','A','C']
C.['A','A','C','D']
D.['A','A','C','A']
14.有如下Python程序段:
a=[2,1,5,7,3];n=len(a)
s1=[-1]*n;top1=-1
s2=[-1]*n;top2=-1
for i in range(n):
　　while top1!=-1 and a[i]　　　　top2+=1;s2[top2]=s1[top1];top1-=1
　　top1+=1;s1[top1]=a[i]
while top2!=-1:
　　top1+=1;s1[top1]=s2[top2];top2-=1
运行该程序段后,下列表达式不成立的是(　　)
A.top1==5 B.top2==-1
C.s1[0]==1 D.s1[3]==7
15.将列表a中的n个整型元素按一定规则压入栈stack中,现要求在出栈时可以获得原压入栈的值以及仍在栈中的最小值。实现该功能的程序段如下,方框处应填入的代码是(　　)
stack=[0]*len(a);top=-1;min=0
for x in a:
　　if top==-1:
　　　　min=x
　　top+=1
　　stack[top]=x-min
　　if x　　　　min=x
while top!=-1:
　　print("当前栈中最小元素为:",min)
　　x=stack[top]
　　top-=1
　　
　　print("当前出栈元素为:",v)
A.if x>0:
　　v=min
　　min-=x
else:
　　v=x+min
B.if x<0:
　　v=x+min
else:
　　v=min
　　min-=x
C.if x>0:
　　v=x+min
　　min-=x
else:
　　v=min
D.if x>0:
　　v=x+min
else:
　　v=min
　　min-=x
16.有如下Python程序段:
from random import randint
st=[""]*4;ys="ABCD";cz=[1,1,1,1]
x=randint(0,3)　#随机生成0、1、2、3
cz[x]=0
top=-1;pos=0
for i in range(len(cz)):
　　if cz[i]==0 and top>-1:
　　　　top=top-1
　　elif cz[i]==1:
　　　　top=top+1;st[top]=ys[pos]
　　　　pos=pos+1
print(st[:top+1])
执行该程序段后,输出结果不可能的是(　　)
A.['A','B']
B.['B','D']
C.['B','C']
D.['A','B','C']4.3　栈
学习目标　
1.画出栈的示意图,理解入栈和出栈的操作。
2.通过出栈顺序,推算入栈顺序,理解栈的后进先出的基本特性。
3.根据栈的性质,实现栈的算法实现。
　　　　　　 　　　　　 　　　　　
(2024年6月浙江选考)栈初始为空,经过一系列入栈、出栈操作后,栈又为空。若元素入栈的顺序为“生”“旦”“净”“末”“丑”,则所有可能的出栈序列中,以“旦”结尾的序列个数为(　　)
A.3 B.4
C.5 D.6
答案　C
解析　本题考查栈的性质。“旦”要结尾,“生”必定是入栈后马上出栈。剩下“净末丑”3个元素按先进后出的顺序进行组合,“净”先出栈,有“净末丑、净丑末”2种组合。“末”先出栈,有“末净丑、末丑净”2种组合。“丑”先出栈,“净末”在栈中,只有“丑末净”一种组合,因此共有5种组合。
　　栈主要用于计算过程中保存的临时数据,是一种只能在数组一端进行存取的数据结构,最大特点是数据在存取时,无需查询,时间复杂度为O(1),后存的数据先被取出。栈中元素必须满足先进后出原则。由于栈顶指针top指向栈中最后一个元素的索引位置,因此栈中元素的个数为top+1,出栈时往往先要读取栈顶元素,再向下移动指针,入栈时,需先向上移动指针,再存入数据。
例1 有后缀表达式“1 3+2*3+2 *”,现利用栈计算该表达式:从左向右扫描,遇到数字时,数字入栈;遇到运算符时,两个元素出栈,用运算符计算,所得结果入栈,如此反复操作,直到扫描结束,栈顶元素是(　　)
A.21 B.22
C.23 D.24
思维点拨
明考向 本题考查栈和后缀表达式应用
精点拨 将后缀表达式“1 3+2*3+2 *”转换为中缀表达式后为“((1+3)*2+3)*2”,计算结果为22
答案　B
变式1 有后缀表达式“346*+52*+”,现利用栈计算该表达式:从左向右扫描,遇到数字时,数字入栈;遇到运算符时,两个元素出栈,用运算符计算,所得结果入栈,如此反复操作,直到扫描结束,栈的深度至少是(　　)
A.2 B.3
C.4 D.5
答案　B
解析　元素346入栈,长度至少为3,4和6出栈,24入栈,遇+号,栈中只有元素27,元素5和2入栈,因此栈深度至少是3。
例2 有如下Python程序段:
import random
a=['A','B','#','#','C','D','#']
stk=[0]*len(a);top=-1
for i in range(len(a)):
　　op=random.randint(0,1) #随机生成0或1
　　if op==1 and a[i]!='#':
　　　　top+=1;stk[top]=a[i]
　　　　a[i]='#'
　　elif op==0 and top!=-1 and a[i]=='#':
　　　　a[i]=stk[top];top-=1
执行该程序段后,a的值不可能的是(　　)
A.['A','B','#','#','C','D','#']
B.['#','#','#','#','#','#','#']
C.['#','B','#','#','C','D','A']
D.['#','#','A','B','C','D','#']
思维点拨
明考向 本题考查栈的应用。若op=1,且'#'时要入栈,是字母时,if语句与elif语句都不执行。若op=0,栈不空且a[i]值为'#',把栈顶值代替当前元素,且进行出栈操作
精点拨 A 当op的值每次都是0时即可实现
B 当op的值每次都是1时即可实现
C 当op的值依次是1、0、1、1、0、0、0时即可实现
D a[0]、a[1]值是'#',表明A、B均已入栈,选项不符合出栈顺序
答案　D
变式2 列表c长度为100,如图所示,其中c[10]~c[89]各元素的值均为1-99的随机正整数。执行如下程序段,输出的最后一行是(　　)
i 0 1 2 3 4 5 6 7 8 9 … 90 91 92 93 94 95 96 97 98 99
c[i] 4 10 15 8 12 13 15 7 5 10 … 4 55 1 12 39 15 40 21 25 18
top=-1
for i in range(len(c)):
　　t=0
　　while top>=0 and c[top]>=c[i]:
　　　　t+=1
　　　　top-=1
　　top+=1
　　c[top]=c[i]
　　print(top,t)
A.5 4　　　　　　　　B.3 2　　　　　　　　C.4 3　　　　　　　　D.2 3
答案　B
解析　遍历列表c,每次弹出栈中所有大于等于当前元素的元素,并记录弹出次数t。当变量i遍历92时,c[i]的值均小于等于栈中的值,元素1入栈,因此程序实现的将一段从小到大的元素依次入栈,直到下一个比栈底元素还小的元素为止。当i的值为98时,栈中元素依次为1,12,15,21,25,元素18让21和25出栈,最后剩下4个元素,top的值为3。
1.元素30,97,32,75,99入栈的顺序为30,97,32,75,99,如果最先出栈的是32,那么最后出栈的不可能的是(　　)
A.30 B.97
C.75 D.99
答案　B
解析　元素32已出栈,则30,97必定在栈中,因此97肯定比30先出栈。
2.栈S最大长度为3,若元素a,b,c,d依次入栈,则可能的出栈序列为(　　)
A.d,c,b,a B.b,a,d,c
C.c,a,b,d D.c,d,a,b
答案　B
解析　A选项d要入栈,至少需要4个长度。B选项a,b入栈,b,a出栈。c,d入栈,d,c出栈。C和D选项a,b入栈,则b先于a出栈。
3.有一个空栈,若元素入栈的顺序是a,b,c,d,e,第1个出栈的元素是d,则当所有元素都出栈后,下列说法正确的是(　　)
A.c一定比a,b先出栈
B.最后一个出栈的元素一定是e
C.最后一个出栈的元素一定是a
D.a,b,c出栈的先后顺序不确定
答案　A
解析　d出栈,则栈中有元素a,b,c。因此c一定比a,b先出栈,且a,b,c出栈的先后顺序是确定的。e可能是第2个出栈的,也可能是最后一个出栈的。
4.已知栈st中从栈底到栈顶的元素依次为a、b、c,元素 d 正等待入栈,以下出栈序列不可能的是(　　)
A.c,b,d,a B.c,d,a,b
C.c,d,b,a D.c,b,a,d
答案　B
解析　栈中有元素a、b、c,则出栈的顺序必定是c、b、a。
5.有1个栈初始为空,其元素入栈顺序依次为s,t,r,w,u,y,m,若经过入栈和出栈操作后,栈底至栈顶元素分别为t,w,y,则第3个出栈元素为(　　)
A.m B.w
C.u D.s
答案　C
解析　根据栈的特性,在栈中元素后进先出,因此第1个入栈和出栈的元素是s,第3个入栈第2个出栈的元素是r,第5个入栈第3个出栈的元素是u。
6.栈初始为空,经过一系列的入栈、出栈操作后,栈为空,若元素入栈顺序为ABCD,则所有可能的出栈序列中,C比A先出栈的个数为(　　)
A.5 B.6
C.7 D.8
答案　C
解析　在元素ABC中,C比A先出栈有CBA或BCA两种可能。在序列CBA中,元素D可能的位置有4个,而在序列BCA中,不可能出现DBCA的序列,可能的位置只有3个。
7.栈S从栈底到栈顶的元素依次为5,8,3,9,7,队列Q初始为空。约定:栈中元素依次出栈后入队,当队尾元素小于队首元素时,队列元素会出队后入栈,直到队尾元素不小于队首元素。当栈为空时,队列中队首到队尾的元素依次为(　　)
A.3,7,9,8,5 B.3,9,7,8,5
C.5,9,7,8,3 D.5,7,9,8,3
答案　B
解析　元素7出栈入队,队中只有一个元素。队尾元素9大于队首元素7;元素3出队入栈,让7和9依次出队并入栈,元素3是最小的,不可能再出队,因此依次出栈的顺序是9,7,8,5。
8.有一个队列和一个栈,其中队列中队首到队尾的元素依次为3,15,8,7,栈中栈顶到栈底的元素依次为6,9,12,10。现在有两种操作,操作S是指队列中1个元素出队后入栈,操作Q是栈中1个元素出栈后入队。则经过QSSQSQQS操作后,队列中队首到队尾的元素依次是(　　)
A.6,15,8,3 B.10,15,8,3
C.3,6,15,7 D.3,10,15,7
答案　A
解析　队列特征为先进先出,有4次出队,因此队列中3,15,8,7全部出队。Q出栈入队,因此6先入队,15和3在栈中,接着15入队,8出队入栈,因此后面是8和3。
9.有如下程序段:
s=["A","B","C","D","E"]
m=[1,3,2,1,2]
st=[""]*4;top=-1
j=0
for i in range(len(s)):
　　top+=1
　　st[top]=s[i]
　　while top!=-1 and ord(st[top])-ord("A")==m[j]:
　　　　top-=1
　　　　j+=1
print(st[:top+1])
执行该程序段后,输出内容是(　　)
A.[]
B.['A','C']
C.['A','E']
D.['A','C','E']
答案　C
解析　遍历列表s,将每个元素入栈,若当前栈顶元素与ord("A")差值为m[j],则将栈顶元素出栈处理。元素"A"和"B"入栈,"B"与ord("A")差值为m[j]为1,"B"出栈,j加1,m[j]值为3,元素"C"和"D"入栈,"D"与ord("A")差值为m[j]为3,"D"出栈;j加1,m[j]值为2,栈顶为元素为"C","C"出栈,最后"E"入栈。
10.有如下Python程序段:
s=input("请输入:")
stack=[""]*10;top=-1
for i in range(len(s)):
　　if top==-1 or stack[top]!=s[i]:
　　　　top+=1
　　　　stack[top]=s[i]
　　else:
　　　　top-=1
print(top+1)
执行该程序段后,输入变量s的值,程序的输出结果与其他选项不同的是(　　)
A."aabbc" B."aaabbac"
C."bbcaa" D."aabcb"
答案　D
解析　遍历字符串s,若栈空或当前字符s[i]不等于栈顶元素,则该元素入栈,否则栈顶元素出栈。A选项剩余元素c,B选项第1个元素a入栈后,第2个a让栈内元素a出栈,第3个元素a入栈,元素b入栈后出栈,第4个a让栈内元素a出栈,栈内只剩下元素c。同理C选项只有元素c。D选项栈内有元素bcb。
11.有如下Python程序段:
stk=[5,2,6,3,7];q,s=0,0
lst=[0]*10;top=len(stk)-1
while top>-1:
　　s+=stk[top]
　　if s % a==0:
　　　　break
　　else:
　　　　lst[q]=stk[top]
　　　　q+=1
　　top-=1
for i in range (q):
　　top+=1;stk[top]=lst[i]
若a为[2,4]区间的随机整数,执行该程序段后,stk的值不可能是(　　)
A.[5,2,6,7,3] B.[5,2,6,3,7]
C.[5,2,7,6,3] D.[5,2,7,3,6]
答案　C
解析　栈中已经有5个元素,将栈顶元素值累加到s中,如果s是a的倍数,结束循环,否则将栈顶元素添加到lst中(入队),并出栈,最后把列表lst中元素返回到栈中。当a的值为2时,7和3累加值为10,栈中值为B选项。当a的值为3时,7+3+6+2=18,列表lst中依次为7,3,6,栈中值为D选项。当a的值为4时,7+3+6=16,列表lst中依次为7,3,栈中值为A选项。C选项3较6先出栈,因此3必定先出队。
12.有如下Python程序段:
import random
p="abcde*";s=""
st=[""]*1000;top=-1
i=0
while i<=5:
　　m=random.randint(0,1)
　　if m==0:
　　　　top+=1
　　　　st[top]=p[i]
　　　　i+=1
　　elif len(st)>0:
　　　　s+=st[top]
　　　　top-=1
print(s)
执行上述程序段后,输出结果可能的是(　　)
A.a* B.cdabe
C.abcde* D.cdba
答案　D
解析　若产生的随机数m值为0,进行入栈操作。否则出栈后并连接到字符串s中。则于最后一个字符*一旦入栈后,i的值为5,结束循环,就不可能出栈。B选项a比b先入栈,出栈顺序应相反。D选项abc先入栈,c出栈,d入栈后出栈,最后a出栈。
13.给定长度为n的数组ts,需为每个元素ts[i]在其后寻找首个更大元素ts[j]。若找到,将两者位置距离存入ans[i],否则ans[i]的值为0。例如数组ts为[33,34,35,31,29,32,36,33],则数组ans为[1,1,4,2,1,1,0,0]。实现该功能的程序段如下,方框处应填入的代码是(　　)
ans=[0]*n;s=[0]*n
top=-1
for i in range(n):
　　t=ts[i]
　　while top>=0 and t>ts[s[top]]:
　　　　j=s[top]
　　　　top-=1
　　　　　　　　　　　　　　
　　top+=1
　　s[top]=i
A.ans[i]=j-i B.ans[i]+=1
C.ans[j]=i-j D.ans[i-j]+=1
答案　C
解析　栈初始为空,将数组ts第1个元素的下标0入栈。后续遍历ts的过程中,若栈不为空,且当前元素值ts[i]大于栈顶元素,则将栈顶元素依次出栈。即栈中元素从栈顶到栈底必须是升序的。元素34让33出栈可以计算得出ans[0]的值为1。当元素35入栈后,元素31、29依次入栈,元素32让29和31出栈,计算出相应ans[4],ans[3]中的值依次为1和2,因此可以得知,当栈顶元素值j出栈时,可以计算ans[j]的值为i-j。
1.有五个元素的出栈顺序依次为1,2,3,4,5。则这五个元素的入栈顺序可能是(　　)
A.1,4,5,3,2 B.2,4,3,1,5
C.3,5,4,1,2 D.5,4,1,3,2
答案　D
解析　A选项4比5先入栈,则5应先出栈。B选项1要出栈,栈中有元素2,4,3,则4必须先于3出栈。C选项1要出栈,栈中有元素3,5,4,则4必须先于3出栈。D选项5,4,1入栈,接着1出栈,3和2入栈,再依次出栈。
2.元素A,B,C,D,E,F按序入栈,在所有出栈序列中(元素需全部出栈),以元素E开头且以元素A结尾的出栈序列的数量有(　　)
A.3 B.4
C.5 D.6
答案　B
解析　E出栈时,栈内有元素A、B、C、D。元素A必须最后出栈,出栈序列可能为:EFDCBA、EDFCBA、EDCFBA、EDCBFA。
3.已知某栈结构初始状态为空,将“岸南江春绿风又”中各个汉字依次入栈,若要求出栈次序为“春风又绿江南岸”,则栈的容量至少为(　　)
A.6 B.5
C.4 D.3
答案　B
解析　将“岸南江春绿风又”中各个汉字依次入栈,当风出栈时,栈中还有元素“岸南江绿”,因此栈的容量至少为5。
4.栈初始为空,经过一系列入栈、出栈操作后,栈又为空。若元素入栈顺序为“红”、“橙”、“黄”、“绿”、“蓝”,在所有可能的出栈序列中,“红”比“蓝”晚三步出栈的序列个数是(若出栈顺序为“蓝红某某某”,则表示“红”比“蓝”出栈晚一步)(　　)
A.3 B.4
C.5 D.6
答案　A
解析　红比蓝晚三步出栈的有3种可能:①橙、蓝、绿、黄、红;②黄、蓝、绿、橙、红;③绿、蓝、黄、橙、红。
5.S从栈底到栈顶元素依次为1,2,4,5,现有新元素3。经过如下操作:若栈非空且新元素小于或等于栈顶元素,栈顶元素出栈,直到栈空或新元素大于栈顶元素,再将新元素入栈。则S中剩余元素个数为(　　)
A.1 B.2
C.3 D.4
答案　C
解析　元素5和4小于3,由这两个元素出栈,栈中剩余元素为1,2,3。
6.利用栈求逆波兰表达式(表达式由操作数和运算符组成)的方法是:从左往右扫描该表达式,遇到操作数时入栈;遇到运算符时,把处于栈上方的两个元素依次出栈,用运算符计算,并把计算结果压入栈中。如此反复操作,直至表达式扫描结束。当用该算法求逆波兰表达式abcd-*e/+f-的值时(abcdef表示不同的操作数),所使用栈的深度至少为(　　)
A.3 B.4
C.5 D.6
答案　B
解析　abcd依次入栈,栈深度为4,遇到“-”,进行c-d操作后,计算结果重新入栈(栈深度为3),遇到“*”,进行b*(c-d)操作后重新入栈(深度为2),接着“e”入栈(栈深度为3)最大深度为4。
7.栈S从栈底到栈顶的元素依次为2、4,队列Q从队首到队尾的元素依次为1、3。约定:A操作是取出栈顶元素x和队首元素y,将x和y相加后入队;M操作是取出栈顶元素x和队首元素y,将x和y相乘后入栈。则经过MAM系列操作后,栈顶元素为(　　)
A.14 B.20
C.26 D.28
答案　A
解析　x的值为4,y的值为1,x*y值为4,重新入栈;再进行 A操作,x值4,y值3,x+y值为7,重新入队;最后进行 M操作,x的值为2,y的值为7,x*y值为14重新入栈,故栈顶元素是14。
8.栈S从栈底到栈顶的元素依次为1,2,3,队列Q初始为空。约定:U操作是指元素出栈后入队,H操作是指元素出队后再入队。经过UUHU系列操作后,队列中队首到队尾的元素依次为(　　)
A.2,1,3 B.3,1,2
C.1,3,2 D.2,3,1
答案　D
解析　本题考查栈的基本性质。两次出栈后入队,队列的结果为3,2。队首元素出队后再入队,队列为2,3,最后1入队。
9.有如下Python程序段:
st=[0]*10
a=[4,6,1,7,2,8,6]
top=0;st[top]=a[0]
for i in range(1,len(a)):
　　while top!=-1 and a[i]　　　　top-=1
　　top+=1
　　st[top]=a[i]
执行该程序段后,变量top的值为(　　)
A.-1 B.1
C.2 D.3
答案　C
解析　栈中初始有一个值,从索引位置1开始遍历,当遍历到的数比栈顶小时,将栈顶元素出栈,自身入栈。遍历到1时,让4和6出栈。7入栈,2使得7出栈,8入栈,6使得8出栈,因此栈中有1、2和6共3个元素,top值为2。
10.已知字符“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']
答案　A
解析　第1个循环让abc依次入队。当队列和栈不为空时,如果栈顶元素和队首元素相同,则进行出队和出栈操作,否则将栈顶元素出栈并入队。栈顶和队首均为"a",出队和出栈操作,接着"d"入队,"d"出栈,接着"c"入队,"c"出栈,队列中元素为"bcdc",接着"b"出队和出栈。
11.有如下Python程序段:
s=[0]*10;q=[0]*10
a=[6,3,2,4,2,1,5]
n,top,head,tail=len(a),0,0,0
s[top]=a[0]
for i in range(1,n):
　　while top!=-1 and a[i]>s[top]:
　　　　q[tail]=s[top];tail+=1
　　　　top-=1
　　top+=1;s[top]=a[i]
while head!=tail:
　　print(q[head],end=' ')
　　head+=1
程序段运行后,输出第3个数字为(　　)
A.1 B.2
C.3 D.4
答案　A
解析　程序首先建立两个长度为10的列表s与q,将a[0]入队。从索引位1开始向后遍历列表a,将s列表小于a[i]的值出栈,加入队列q中。输出队列q中的元素,输出23124。
12.有如下Python程序:
stackA=[0]*6
stackB=[0]*6
topA=topB=-1
d=[5,9,4,8,7,2]
for i in range(len(d)):
　　while topA!=-1 and d[i]　　　　topB+=1
　　　　stackB[topB]=stackA[topA]
　　　　topA-=1
　　topA+=1;stackA[topA]=d[i]
程序执行过程中,变量topB的最大值为(　　)
A.2 B.3
C.4 D.5
答案　C
解析　遍历数组d,若栈stackA不空,且d[i]小于stackA[topA],则让stackA[topA]出栈并入栈stackB。5和9入栈stackA,4让5和9出栈并入栈stackB,8入栈stackA,7让8出栈并入栈stackB,2让7,4出栈并入栈stackB,栈stackB中共有5个元素,因此topB的最大值为4。
13.有如下Python程序段:
import random
lst=['A','B','C','D']
st=[0]*len(lst)
i,top=0,-1
while i　　k=random.randint(0,1)
　　if k==0:
　　　　top+=1
　　　　st[top]=lst[i]
　　　　i+=1
　　elif top!=-1:
　　　　lst[i]=st[top]
　　　　top-=1
执行该程序段后,lst的值不可能是(　　)
A.['A','B','C','D']
B.['A','B','A','C']
C.['A','A','C','D']
D.['A','A','C','A']
答案　B
解析　当k的值为0时,进行入栈操作;当k的值为1且栈不为空,进行出栈并替换lst[i]操作。由于i+=1操作发生在入栈过程中,因此必须有4个元素出栈,但栈中可能有元素未出栈。A选项当随机数4次均为0,全部元素均在栈中。C选项随机数依次为0,1,0,0,有两个元素在栈中。D选项随机数依次为0,1,0,1,A先入栈,出栈后替换B,原B位置上的A再次入栈,最后替换D。B选项当i的值为2时,AB在栈中,应该B先出栈。
14.有如下Python程序段:
a=[2,1,5,7,3];n=len(a)
s1=[-1]*n;top1=-1
s2=[-1]*n;top2=-1
for i in range(n):
　　while top1!=-1 and a[i]　　　　top2+=1;s2[top2]=s1[top1];top1-=1
　　top1+=1;s1[top1]=a[i]
while top2!=-1:
　　top1+=1;s1[top1]=s2[top2];top2-=1
运行该程序段后,下列表达式不成立的是(　　)
A.top1==5 B.top2==-1
C.s1[0]==1 D.s1[3]==7
答案　A
解析　本题考查栈的基本应用。遍历列表a中数据,若栈s1不空,且s1栈顶元素大于等于a[i]时,不断地将s1中元素出栈,并入栈s2中,将a[i]入栈s1。因此栈s1中元素有1,3,栈s2中有元素[2,7,5],最后将栈s2中元素出栈并加入栈s1中,因此栈s1中最终结果为[1,3,5,7,2]。
15.将列表a中的n个整型元素按一定规则压入栈stack中,现要求在出栈时可以获得原压入栈的值以及仍在栈中的最小值。实现该功能的程序段如下,方框处应填入的代码是(　　)
stack=[0]*len(a);top=-1;min=0
for x in a:
　　if top==-1:
　　　　min=x
　　top+=1
　　stack[top]=x-min
　　if x　　　　min=x
while top!=-1:
　　print("当前栈中最小元素为:",min)
　　x=stack[top]
　　top-=1
　　
　　print("当前出栈元素为:",v)
A.if x>0:
　　v=min
　　min-=x
else:
　　v=x+min
B.if x<0:
　　v=x+min
else:
　　v=min
　　min-=x
C.if x>0:
　　v=x+min
　　min-=x
else:
　　v=min
D.if x>0:
　　v=x+min
else:
　　v=min
　　min-=x
答案　D
解析　在入栈过程中,若当前数x是最小值,则将x-min入栈,因此若栈中的数为0或负数,则当前的数为最小值。在出栈过程中,若出栈的元素大于0,则真实的值应为x+min。否则出栈的是最小值,要更新当前在栈中的最小值min为min-x。以列表a为[4,3,5,1,4]为例,入栈的值依次为[0,-1,2,-2,3],栈中最小值为1,第1个出栈的元素为3+1=4。第2个出栈的元素是最小值,同时更新当前栈中最小值为1-(-2)=3。
16.有如下Python程序段:
from random import randint
st=[""]*4;ys="ABCD";cz=[1,1,1,1]
x=randint(0,3)　#随机生成0、1、2、3
cz[x]=0
top=-1;pos=0
for i in range(len(cz)):
　　if cz[i]==0 and top>-1:
　　　　top=top-1
　　elif cz[i]==1:
　　　　top=top+1;st[top]=ys[pos]
　　　　pos=pos+1
print(st[:top+1])
执行该程序段后,输出结果不可能的是(　　)
A.['A','B']
B.['B','D']
C.['B','C']
D.['A','B','C']
答案　B
解析　若产生x的值为0,没有出栈,入栈'A','B','C'共3个元素。产生x值为1,'A'入栈再出栈,接着入栈'B'和'C'共['B','C']2个元素。产生x值为2,'A'和'B'入栈,'B'出栈,'C'入栈,共['A','C']2个元素。产生x值为3,'A','B','C'入栈,'C'出栈,共['A','B']2个元素。

展开更多......

收起↑