资源简介

2023-2024学年高二上学期浙教版(2019)选修一3.3栈
一、选择题
1．有1个栈初始为空，其元素入栈顺序依次为a，b，c，d，e，f，g，经若干次入栈和出栈操作后，栈底至栈顶元素分别为b，d，f，则第3个出栈元素为（ ）
A．g B．c C．e D．a
2．有如下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']
3．队列Q和栈S的初始值均为空，数字入栈先后顺序为1、2、3、4、5。P表示入栈，T表示元素出栈以后入队。在进行一系列P、T操作后，队列中从队首到队尾的元素依次为2、1、4、5，则对应的P、T操作是（ ）
A．PPTTPPTPT B．PTPTPPPTT C．PPTTPPPTT D．PPTTPTPPT
4．栈s的最大长度为3，初始为空，经过一系列的入栈、出栈操作，若元素入栈的顺序是a，b，c，d，e，则可能的出栈序列为（ ）
A．a，e，d，c，b B．c，a，b，d，e
C．a，d，c，e，b D．e，d，c，b，a
5．用一带盖的玻璃筒来放取乒乓球，放、取球只能在带盖的一端进行（另一端为封闭状态），且筒的直径只允许一个乒乓球进出。若放入球的编号序列为1、2、3、4，则取出球的编号序列不可能的是（ ）
A．1、2、3、4 B．2、3、4、1 C．4、2、3、1 D．3、2、1、4
6．设初始输入序列为1，2，3，4，5，利用一个栈产生输出序列，下列输出序列不可能通过栈产生的是（ ）
A．1,2,3,4,5 B．5,3,4,1,2 C．4,3,2,1,5 D．3,4,5,2,1
7．已知字符″a″的ASCⅡ码值为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’]
8．栈S1从栈底到栈顶的元素顺序由1，2，3改为3，2，1，可借助初始均为空、长度均为3的栈S2、栈S3出入栈操作来实现，则需要出栈操作的总次数至少是（ ）
A．6 B．7 C．8 D．9
9．有如下程序段：
import random
a=[1.2.3.4.5]
stack=[a[0]]
i=1
res=[]
while i if random.randint（0.1）==0 or len（stack）==0：
stack.append（a[i]）
else：
res.append（stack.pop（））
i-=1
i+=1
while len（stack）>0：
res.append（stack.pop（））
print（res）
程序运行后，输出的结果不可能是（ ）
A．[1.2.3.4.5] B．[2.1.4.3.5] C．[1.4.2.3.5] D．[1.5.4.3.2]
10．由元素1，2，3，4，5，6，7，8依次入栈、出栈，要求每次出栈之前至少有两次连续入栈操作，出栈时可以出栈一个元素，也可以出栈多个元素直至栈空，则数据的出栈序列可能是（ ）
A．3，4，2，5，7，6，1，8 B．2，4，3，1，8，7，6，5
C．5，7，6，4，8，3，2，1 D．4，3，5，2，1，6，8，7
11．栈s的最大长度为3，初始为空，经过一系列入栈、出栈操作，若元素出栈的顺序是e，c，b，a，d，则可能的入栈序列为（ ）
A．a，b，c，d，e B．a，e，c，b，d C．e，b，a，c，d D．d，e，a，b，c
12．一个序列的入栈顺序为9,8,7,6,5,4。若7第一个出栈，则下列出栈序列中不可能的是（ ）
A．7,8,9,6,5,4 B．7,8,9,5,6,4
C．7,9,8,4,5,6 D．7,8,9,6,4,5
13．有如下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
14．数据结构栈的特点是（ ）
A．先进先出 B．先进后出
C．可以在栈的任意位置取出元素 D．可以在栈的任意位置插入元素
15．现有栈S和队列Q，初始状态均为空，令数据元素b1，b2，b3，b4，b5，b6依次通过栈S，规定某元素出栈后立即进入队列Q，若出队的顺序为b2，b5，b4，b6，b3，b1，则栈S的容量至少应该为（ ）
A．2 B．3 C．4 D．5
二、填空题
16．有一维数组1、2、3、4、5，依次按照某一线性存储，请回答以下问题：
（1）如果该线性结构是队列，写出出队序列。
（2）如果该线性结构是栈，输出序列可能是4、3、5、1、2吗？为什么？
（3）在一维数组A中有5个元素：8、12、20、25、33，采用二分查找25，请写出每次查找的过程？
17．数据结构中的栈是一种特殊的列表，它只允许在 进行数据的添加和删除操作。
18．栈是一种 数据结构，遵循 的原则。
19．在数据结构中，栈是一种 的数据结构，遵循后进先出（LIFO）原则。
三、操作题
20．电路板布线问题。电路板的水平直线上，从左向右分布着 n个针脚（1，2，3，…，n），用于连接导线。连线（p，q）表示针脚p和q之间通过一根导线连接，导线只允许从水平直线的下方相连，对于给定的一组连线（p1，q1），（p2，q2），…，（pm，qm）（确保各pi与qi均互不相同，且pi编写程序，对于给定的n个针脚和m条连线，判定这组连线是否可布线。
请回答下列问题：
（1）若有8个针脚，并有一组连线（2，5），（1，6），（3，4），（7，8），则该组连线 （单选，填字母：A．可以/B．不可以）布线。
（2）实现上述功能的部分Python 程序如下，请在划线处填入合适的代码。
#读取针脚数量与这组连线数量，分别存入n、m中，代码略。
#将连线情况存入a，a=[[p1，q1]，[p2，q2]…]，代码略。
for i in range（1，m）：#按连线左端点升序排序
for j in range（m-1，i-1，-1）：
if① ：
a[j]，a[j-1]=a[j-1]，a[j]
st=[0]*m；top=-1
②
for i in range（m）：
while top>=0 and st[top]<=a[i][0]：
top-=1
if top>=0 and③ ：
flag=False
top+=1
st[top]=a[i][1]
if flag：
print（“YES”）
else：
print（“NO”）
21．小陈同学高一结束后需要换寝室，他将全部物品打包成6个箱子并编号叠放在一起（如图1所示）。为了搬运物品方便，他借了一辆手推车，该手推车一次最多能叠放3个箱子（如图2所示）。箱子从上往下依次叠放在小推车上（假定每次只放一个箱子），小推车每次可以叠放1、2或3个箱子，小推车上的箱子也是从上往下依次拿取（假定每次只取一个箱子），搬运后的箱子仍旧叠放在一起。
（1）在搬运中，与手推车上箱子叠放和拿取的过程相似的数据结构是 。
（2）若搬运完毕后箱子的叠放顺序是2、1、3、4、6、5（从下往上），则每趟手推车至多需要搬运的箱子数是 个。
图1 图2
四、简答题
22．请简述什么是堆栈（Stack）数据结构，并说明其特点。
23．解释什么是栈数据结构，并说明其后进先出（LIFO）的特性。
参考答案：
1．C
2．B
3．A
4．C
5．C
6．B
7．A
8．B
9．C
10．B
11．B
12．C
13．C
14．B
15．C
16． 1、2、3、4、5
不可能，因为：4是第一出栈字符，说明1,2已别压入栈内；并且压入栈的次序为12345;由以上得出：12出栈的顺序只能是2、1，而不是1、2。所以，出栈序列4,3,5,1,2是不可能的 第一次查找，找到的元素为20，此时20小于目标数，所以在列表的后半部分查找，第二次查找到的元素为25，此时找到，所以共需要两次找到
17．顶端（或顶部）
18． 后进先出（LIFO） 后进先出
19．线性
20． A a[j][0]21． 栈 2
22．堆栈是一种后进先出（LIFO）的数据结构，其特点是只能在一端（栈顶）进行数据的添加（push）和删除（pop）操作。
23．栈是一种遵循后进先出（LIFO）原则的数据结构，最后添加的元素将是第一个被移除的。这意味着元素只能从栈顶添加或移除。

展开更多......

收起↑