资源简介

栈
一 、选择题(每小题列出的四个备选项中只有一个是符合题目要求
的，不选、多选、错选均不得分)
1.下列关于栈的说法，不正确的是 ( )
A.出栈操作时，先将栈顶元素出栈，同时栈顶指针变量值减1
B.入栈或出栈操作时不需要移动其他元素
C.栈不空时，当前只能取出栈顶元素
D.栈为空时，栈顶指针变量值为0
2.用一个带盖的玻璃筒来放取乒乓球，放、取只能在带盖的一端进行
(另一端为封闭状态),且筒的直径只允许一个乒乓球进出。若放
入球的编号序列为1、2、3、4,则取出球的编号序列不可能是( )
A.1 、2 、3 、4
B.2 、3 、4 、1
C.4 、2 、3 、1
D.3 、2 、1 、4
3.有7个羽毛球分别用1～7进行编号，若将7个羽毛球按一定顺序装
入栈结构的球罐中。已知取出羽毛球的顺序用编号表示为2,4,3,
1,6,5,7,则放入羽毛球的编号顺序不可能是 ( )
A.7,5,6,1,3,4,2
B. 1,2,3,4,5,6,7
C.7,6,5,4,3,2,1
D.2,4,3,1,6,5,7
4.设栈S 和队列Q 的初始状态为空，元素el,e2,e3,e4,e5,e6依次通
过 栈S,一个元素出栈后随即进入队列Q, 若6个元素出队的序列是
e2,e4,e3,e6,e5,el,则栈S 的容量至少是 ( )
A.6 B.4
C.3 D.2
5.已知序列8,25,14,87,51,90,6,19,20,将这些元素全部入栈后再全部出
栈，若要使出栈的顺序满足8在51的前面，90在87的后面，20在14的后
面，25在6的前面，19在90的后面，则这些元素的进栈顺序可能是( )
A.20,6,8,51,90,25,14,19,87
B.51,6,19,20,14,8,87,90,25
C. 19,20,90,8,6,25,51,14,87
D.6,25,51,8,20,19,90,87,14
6. 元素x1、x2、x3、x4、x5入栈的顺序为x1、x2、x3、x4、x5。如果第1个 出栈的是x3,则第2个出栈的不可能是 ( )
A.x1 B.x2
C.x4 D.x5
7. 当栈为空时，栈顶top=- 1 。 利用栈计算逆波兰表达式“682-2* 3/+”的过程中，当即将计算“8-2”时，top的值是 ( )
A.0 B.1
C.2 D.3
8. 某Python程序如下：
import random as rd
st=[0]*10
st[0]=2
top=0
for iin range(5):
if top==- 1:
break
num=rd.randint(1,6)
if num>=st[top]:
top+=1
st[top]=num
elif num%2==0:
top-=1
for i in range(top+1):
print(st[i],end="")
程序运行后，输出的结果可能是 ( )
A.2245566 B.255
C.2464 D.2342
9. 用Python列表自带的函数和方法来模拟栈，代码如下：
import random
a=[1,2,3,4,5]
stack=[a[0]]
i=1
res=[]
while iif 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,5,4,3,2]
D.[1,4,2,3,5]
10. 有如下创建栈及进行栈操作的Python 程序：
class Stack():
def def def inil (self): self.my stack=[] push(self,data): self.my stack.append(data) pop(self): return self.my stack.pop()
La=[]
stack=Stack()
stack.push("r1")
La.append(stack.pop()
stack.push("r2")
stack.push("r3")
La.append(stack.pop()
stack.push("r4")
La.append(stack.pop()
stack.push("r5")
print(La)
程序运行后，输出的内容是
A.["r2","r5"]
B.["r5","r2"]
C.["r4","r3","r1"]
D.["r1","r3","r4"]
( )
( )
二、非选择题
11. 利用栈的“先进后出”的特点可以实现数的进制转换。某Python 程序如下，实现的是十进制数转换为二进制数的功能。运行界
面如图所示。请在划线处填入合适的代码。
请输入一个整数：27
11011
s=[0]*100
top=- 1
n=int(input("请输入一个整数：")
while n>0:
top+=1
①
n=n//2
while top>- 1:
print(s[top],end="")
②
12. 单调栈是保证栈中元素具有单调性的数据结构，如已知栈中元素 从栈底到栈顶依次为：2、4、4、8、9,保证了栈中具有单调不下降的 性质，如果此时有新元素4入栈，则为了保证栈的单调性，将会把
8、9出栈，令4入栈，栈中元素更新为2、4、4、4。小王利用Python 编写的程序如下，对于已有的整数单调栈s,将数据new 入栈，同 时保证栈中元素的单调不下降性。请在划线处填入合适的代码。 s=[0]*100
n=int(input("请输入已有单调递增栈中的元素数量：")
i=0
while is[i]=int(input("请依次输入栈中的元素：")
i+=1
top=n- 1
def push(x):
global top #定义全局变量top
while ① :
top-=1
top+=1
②
new=int(input("请输入新入栈的元素：")
push(new)
for i in range(top+1):
print(s[i].end=”")
13. 字符串如"CBAABC" 称为回文字符串，而字符串"ABC"则不是回 文字符串。可以利用栈来检查字符串是否为回文字符串，实现上 述功能的Python程序如下，运行界面如图所示。请在划线处填入
合适的代码
请输入字符串：abcdcba 是回文字符串
st=[“”]]*100
top=- 1
1
s=input("请输入字符串：")
k=len(s)//2
fori in range(k):
top+=1
st[top]=s[i]
if ② **
k=k+1
for i in range(k,len(s)):
ch=st[top]
top-=1
if 3 :
flag=False:break
if flag:
print("是回文字符串")
else:
print("不是回文字符串")
14. 有一个背包，它的最大承载质量为m 公斤(kg),现有n 件物品，并 已知这n 件物品的质量，编写一个Python程序找出所有能将背包 装满的方案。程序运行后，首先输入背包的最大承载质量m, 接 着输入物品的数量n 及n 件物品的质量，输出能装满背包的所有 方案。实现上述功能的Python程序如下，运行界面如图所示。请
在划线处填入合适的代码。
输入背包的最大承载质量：20 输入物品数量：6 输入物品质量(用逗号隔开):12,5.8,9.3.16 装满背包的方案有 [0,1,4] [0,2] [2,3,4]
def cal(t,w):
n=len(w)
stack=[
k=0
while stack or kwhile ①
if t>=int(w[k]):
stack.append(k)
②
k+=1
if t==0:
print(stack)
#若无方案，则将当前物品出栈，退回一步尝试其他物品
k=stack.pop()
t+=int(w[k])
k+=1
m=int(input("输入背包的最大承载质量：")
n=int(input("输入物品数量：")
weight=input("输入物品质量(用逗号隔开):")
wplist=weight.split(",")
print("装满背包的方案有：")
③
参考答案
1.D 2.C 3.C 4.C 5.D 6.A 7.D 8.B 9.D 10.D
① s[top]=n%2
② top-=1
① x=0
② s[top]=x
① flag=true
② len(s)%2==1
③ ch!=s[i]
① t>0 and k②t-=int(w[k]) 或 t=t-int(w[k])
③ cal(m,wplist)

展开更多......

收起↑