教科版（2019）选修一5.1栈结构及其实现同步训练（含解析）
文档属性
| 名称 | 教科版（2019）选修一5.1栈结构及其实现同步训练（含解析） |  | |
| 格式 | docx | ||
| 文件大小 | 24.8KB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 教科版（2019） | ||
| 科目 | 信息科技（信息技术） | ||
| 更新时间 | 2025-10-21 21:56:51 | ||
图片预览
文档简介
教科版（2019）选修一5.1栈结构及其实现同步训练
学校:___________姓名：___________班级：___________考号：___________
一、选择题
1．有如下Python程序段：
import random
a=['A'，'B'，'#'，'#'，'C'，'D'，'#']
stk=[0]*len（a）；top=-l
for i in range（len（a））：
op=random. randint（0，1） # 随机生成0或1
if op= =l and a[i]!='#"：
top+=l；stk[top]=a[i]
a[i]='#'
elif op= =0 and top!=-1 and a[i]= ='#'：
a[i]=stk[top]；top-=l
执行该程序段后，a的值不可能的是（ ）
A．['A'，'B'，'#'，'#'，'C'，'D'，'#'] B．['#'，'#'，'#'，'#'，'#'，'#'，'#']
C．['#'，'B'，'#'，'#'，'C'；'D'，'A'] D．['#'，'#'，'A'，'B'，'C'，'D'，'#']
2．用栈的数据结构编写进制转换中的“除二取余法”的程序段如下：
st=[-1]*100
top=-1
n=int(input("请输入一个十进制数： "))
while n>0:
while top!=-1:
print(st[top],end="")
top-=1
方框处的代码由以下四部分组成：
①n=n//2 ②top+=1 ③x=n%2 ④st[top]=x
下列选项中，代码顺序正确的是（ ）
A．③④②① B．③①②④ C．①②③④ D．①③④②
3．栈s的最大长度为3，初始为空，经过一系列入栈、出栈操作，若元素入栈的顺序是a，b，c，d，e，f，则可能的出栈序列为（ ）
A．f，e，d，c，b，a B．c，b，a，f，e，d C．c，a，b，d，e，f D．c，e，d，b，a，f
4．下列有关栈和队列说法，正确的是( )
A．栈的特点是先进先出，队列的特点是先进后出 B．栈只允在一端进行插入，在另一端进行删除
C．队列限定仅能在一端进行插入和删除操作 D．栈和队列均为操作受限的线性表
5．有如下 Python 程序段：
s = input('请输入一串小写字母')
head = 0; tail = 0; top = -1
s1 = [""]*((len(s)+1)//2)
s2 = [""]*(len(s)//2)
for i in range(len(s)):
if i % 2 == 0:
s1[tail] = s[i]
tail += 1
else:
top += 1
s2[top] = s[i]
x = ""
while head < tail and top > -1:
x = s1[head] + x
head += 1
x = x + s2[top]
top -= 1
print(x)
执行该程序段，输入字符串“abcdefg”，则输出的结果是（ ）
A．acegbdf B．acegfdb C．gecafdb D．ecafdb
6．有如下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']
7．已知一个栈的入栈序列是a，c，e，h，r，t，e，其出栈序列可能的是（ ）
A．c，h，e，a，t，e，r B．h，e，c，t，a，r，e C．t，e，a，c，h，e，r D．r，e，t，e，a，c，h
8．有如下程序：
wz=[0,1,2,3,4,5,6]
start=0
qu=[0]*len(wz)
wm="abcdefg"
h=0;t=0
while len(wz)>0:
for i in range(2):
start=(start+1)%len(wz)
qu[t]=wz[start]
t=t+1
wz.pop(start)
mm=""
while h mm=mm+wm[qu[h]]
h=h+1
print(mm)
程序运行后，显示的结果为（ ）
A．bdfaecg B．bdfaceg C．cfbgead D．cfbeadg
9．栈S从栈底到栈顶的元素依次为1，2，3，队列Q初始为空。约定：U操作是指元素出栈后入队，H操作是指元素出队后再入队。经过UUHU系列操作后，队列中队首到队尾的元素依次为（ ）
A．2,1,3 B．3,1,2 C．1,3,2 D．2,3,1
10．某Python程序如下：
from random import randint
a=[1,8,3,6,7,2,9,0,5,1,3]
s=[-1]*100;top=-1
i=0
x=randint（5,8）
while i while top!=-1 and a[i] < s[top]:
top-=1
top+=1;s[top]=a[i]
i+=1
while top!=-1:
print(s[top],end="")
top-=1
执行该程序段后，输出的结果不可能是（ ）
A．0 B．21 C．631 D．921
11．有如下程序段：
bt=["A","B","C","D",None,"E","F"]
result=[]
stack=[]
i=0
while stack or (i if i < len(bt) and bt[i] is not None:
stack.append(i)
i=2*i+1
else:
i=stack.pop()
result.append(bt[i])
i=2*i+2
print("-".join(result))
则程序运行后输出的结果为（ ）
A．A-B-D-C-E-F B．D-B-E-F-C-A C．D-B-A-E-C-F D．A-B-C-D-E-F
12．设栈S初始状态为空，元素A、B、C、D、E、F依次入栈，出栈的序列为D、F、E、C、B、A，则栈S的容量至少应该是（ ）
A．5 B．4 C．3 D．2
13．若用1表示进栈操作，用0表示出栈操作，若元素的进栈顺序是“q，w，e，r，t”，为了得到出栈序列“ewrtq”，则应进行的操作序列为( )
A．1101010100 B．1110010100 C．1110011000 D．1110100100
14．一个栈的入栈序列为“6、9、5、7、8、3”，其出栈序列不可能是( )
A．3、8、7、5、9、6 B．7、5、9、8、6、3 C．6、5、7、9、3、8 D．5、9、6、3、7、8
15．一个栈的初始状态为空，若它的输入序列为a、b、c、d，则它的输出序列为( )
A．a、b、c、d B．d、c、b、a
C．b、a、c、d D．d、b、a、c
试卷第1页，共3页
试卷第1页，共3页
参考答案：
1．D
【详解】本题考查的是堆栈的操作。堆栈的操作原则先进后出。stk可以看做一个堆栈，阅读程序可知对列表a中的字母进行入栈和出栈操作。选项A没有进行入栈和出栈操作，有可能；选项B把字母全部压入栈，有可能；选项C对字母A进行入栈，最后出栈，有可能；选项D，先把字母A、B进行入栈，然后出栈，出栈顺序应为B、A，故选项D不可能。
2．B
【详解】本题主要考查栈及Python程序调试。根据题意“除二取余法”可知先要执行取余，然后才能整除2更新n的值。top初值为-1标记此时栈中无元素，每递增一个元素，top先递增1，再将x保存到栈中，即st[top]=x，故代码顺序正确的是③①②④，故本题选B选项。
3．B
【详解】本题考查栈的基本操作。栈是先进后出，题干中限定条件栈s的最大长度为3，初始为空。A选项f最先出栈，说明a，b，c，d，e，f需要全部入栈后，f才能出栈，但这种情况下栈长度需要为6，不符合题意，故A选项错误；B选项c最先出栈，此时a，b，c入栈，接着c，b，a依次出栈，此时栈s内为空，接下来f出栈，说明d，e，f需要入栈，接着f，e，d出栈，过程中栈内长度符合题意，故B选项正确；C选项c最先出栈，此时a，b，c入栈，接着c出栈，此时栈内a，b，由于b是栈顶元素，所以接下来出栈元素不可能是a，故C选项错误；D选项c最先出栈，此时a，b，c入栈，接着c出栈，此时栈内a，b，接下来e出栈，需要d，e入栈，此时栈内a，b，d，e，栈长度为4，不符合题意，故D答案错误。本题应选B。
4．D
【详解】本题主要考查栈和队列的描述。栈的特点是先进后出，队列的特点是先进先出；队列只允在一端进行插入，在另一端进行删除； 栈限定仅能在一端进行插入和删除操作； 栈和队列均为操作受限的线性表，故本题选D选项。
5．D
【详解】本题主要考查Python及数据结构的应用。根据题意，s1为队列，s2为栈，每读取s一个字母时，偶数次取出放入s1中，奇数次取出放入s2中，存储后再依次取出，取时必须同时满足 head-1，故只取最少次数。故输入字母串 abcdefg 时，存入队列中的为aceg，存入栈中的为bdf。队列从head指向处顺序取出，反接在x中；栈从top指向处逆序取出，正接在x中，故输出的结果是ecafdb，故本题选D选项。
6．B
【详解】本题考查数据结构栈的相关操作。以下仅取部分随机数序列进行解析：
A选项，若每次使用random．randint（0，1）时，都产生随机数0，即0、0、0、0，则只执行入栈操作（if部分），lst并未发生变化（elif部分未执行），其值仍然为['A'，'B'，'C'，'D'] ，选项A正确；
C选项，当产生随机数依次为：0、1、0、0、0时，第一次值为0，将lst第一个元素'A'入栈，i+1变为1，第二次值为1时，将栈st中元素出栈且赋值给lst[1]，则lst[1]='A'，第三、四、五次值为0时，进行入栈操作，i值由1变为4，结束循环，lst中对应位置元素并未发生变化，lst中元素最终为：['A'，'A'，'C'，'D'] ，选项C正确；
D选项，当产生随机数依次为：0、1、0、0、1、1、0时，第一次值为0，将lst第一个元素'A'入栈，i+1变为1，第二次值为1时，将栈st中元素出栈且赋值给lst[1]，则lst[1]='A'，第三、四次值为0时，进行入栈操作，st=['A'，'C']，第五、六次执行出栈，lst中元素为：['A'，'A'，'C'，'A]，第七次执行出栈，lst不变还是['A'，'A'，'C'，'A]，i值由1变为4，结束循环。选项D正确。
排除ACD，故本题答案是B选项。
7．A
【详解】本题主要考查栈的操作。根据栈的特点“先进后出”的原则，可知入栈序列是a，c，e，h，r，t，e，结合选项，其出栈序列可能的是c，h，e，a，t，e，r，故本题选A选项。
8．C
【详解】本题主要考查Python程序的执行。第一次循环后start=2，qu[0]=wz[start]=2；第二至第七次循环后，qu[1]=5，qu[2]=1，qu[3]=6，qu[4]=4，qu[5]=0，qu[6]=3。h初值为0，执行完最后一个while循环，即根据列表qu的值从wm中取对应的元素拼接到mm中，mm=mm+wm[qu[h]]，程序运行后，显示的结果为mm="cfbgead"，故本题选C选项。
9．D
【详解】本题考查栈、队列相关内容。栈的特点是后进先出，队列的特点是先进先出。初始状态，栈中从栈顶到栈底的元素为3、2、1，队列为空。第一次操作：U，即将栈顶元素3出栈后入队，队列中队首元素为3；第二次操作：U，即将栈顶元素2出栈后入队，队列中队首元素为3，队尾元素为2；第三次操作：H，即将队首元素3出队后再入队，队列中队首元素为2，队尾元素为3；第四次操作：U，即将栈顶元素1出栈后再入队，队列中从队首到队尾各元素依次为2、3、1。故本题答案是D选项。
10．C
【详解】本题主要考查栈数据结构及Python程序实现。分析程序可知，x随机生成5~8之间的整数，即外循环的次数，嵌套while循环中，栈中保存的数从栈底到栈顶成递增趋势，如果出现了不符合的数，则依次出栈直到符合递增趋势。因此x=5时，输出的结果是7631；x=6时，输出的结果是21；x=7时，输出的结果是921；x=8时，输出的结果是0，因此输出的结果不可能是631，故本题选C选项。
11．C
【详解】本题主要考查Python中stack()用法。分析程序可知，前3轮循环，即当i=0、1、3时均满足if判断条件，此时stack=[0,1,3]，接下来i=2*i+1=7不满足if判断条件，执行else部分， i=stack.pop()=3，result.append(bt[i])=["D"]，i=2*i+2=8，继续执行else，i=stack.pop()=1，result.append(bt[i])=["D","B"]，i=2*i+2=4，不满足if判断条件，继续执行else部分，i=stack.pop()=0，result.append(bt[i])=["D","B","A"]，此时结合选项可知程序运行后输出的结果为D-B-A-E-C-F，选C选项。
12．A
【详解】本题考查栈相关内容。栈的特点是先入后出。栈S 的初始状态为空，元素A、B、C、D、E、F依次入栈，出栈顺序为D、F、E、C、B、A。D出栈，说明D要先进栈，此时C、B、A已在栈内，栈的容量至少为4；D出栈后，F出栈，说明F需要先进栈，此时E、C、B、A在栈内，栈的容量至少为5；后续出栈序列为E、C、B、A，期间没有元素再入栈，栈的容量不会再增加，故栈的容量至少为5。本题答案是A选项。
13．B
【详解】本题主要考查栈的操作。为了得到出栈序列“ewrtq”，即e先出栈，按照进栈顺序，则qwe先进栈，对应111，接着是ew出栈，对应00，后面依次类推可得到应进行的操作序列为1110010100，故本题选B选项。
14．D
【详解】本题主要考查栈数据结构。选项D中，先入栈6、9、5，再依次出栈，此时再入栈7、8、3，则出栈顺序只能是3、8、7，故出栈序列不可能是5、9、6、3、7、8，故本题选D选项。
15．B
【详解】本题考查的栈的操作。堆栈是一个后进先出的数据结构，若它的输入序列为a、b、c、d，则它的输出序列为d、c、b、a。故本题应选B。
答案第1页，共2页
答案第1页，共2页
学校:___________姓名：___________班级：___________考号：___________
一、选择题
1．有如下Python程序段：
import random
a=['A'，'B'，'#'，'#'，'C'，'D'，'#']
stk=[0]*len（a）；top=-l
for i in range（len（a））：
op=random. randint（0，1） # 随机生成0或1
if op= =l and a[i]!='#"：
top+=l；stk[top]=a[i]
a[i]='#'
elif op= =0 and top!=-1 and a[i]= ='#'：
a[i]=stk[top]；top-=l
执行该程序段后，a的值不可能的是（ ）
A．['A'，'B'，'#'，'#'，'C'，'D'，'#'] B．['#'，'#'，'#'，'#'，'#'，'#'，'#']
C．['#'，'B'，'#'，'#'，'C'；'D'，'A'] D．['#'，'#'，'A'，'B'，'C'，'D'，'#']
2．用栈的数据结构编写进制转换中的“除二取余法”的程序段如下：
st=[-1]*100
top=-1
n=int(input("请输入一个十进制数： "))
while n>0:
while top!=-1:
print(st[top],end="")
top-=1
方框处的代码由以下四部分组成：
①n=n//2 ②top+=1 ③x=n%2 ④st[top]=x
下列选项中，代码顺序正确的是（ ）
A．③④②① B．③①②④ C．①②③④ D．①③④②
3．栈s的最大长度为3，初始为空，经过一系列入栈、出栈操作，若元素入栈的顺序是a，b，c，d，e，f，则可能的出栈序列为（ ）
A．f，e，d，c，b，a B．c，b，a，f，e，d C．c，a，b，d，e，f D．c，e，d，b，a，f
4．下列有关栈和队列说法，正确的是( )
A．栈的特点是先进先出，队列的特点是先进后出 B．栈只允在一端进行插入，在另一端进行删除
C．队列限定仅能在一端进行插入和删除操作 D．栈和队列均为操作受限的线性表
5．有如下 Python 程序段：
s = input('请输入一串小写字母')
head = 0; tail = 0; top = -1
s1 = [""]*((len(s)+1)//2)
s2 = [""]*(len(s)//2)
for i in range(len(s)):
if i % 2 == 0:
s1[tail] = s[i]
tail += 1
else:
top += 1
s2[top] = s[i]
x = ""
while head < tail and top > -1:
x = s1[head] + x
head += 1
x = x + s2[top]
top -= 1
print(x)
执行该程序段，输入字符串“abcdefg”，则输出的结果是（ ）
A．acegbdf B．acegfdb C．gecafdb D．ecafdb
6．有如下Python程序段：
import random
lst=['A'，'B'，'C'，'D']
st=[0]*len（lst）
i，top=0，-1
while i
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']
7．已知一个栈的入栈序列是a，c，e，h，r，t，e，其出栈序列可能的是（ ）
A．c，h，e，a，t，e，r B．h，e，c，t，a，r，e C．t，e，a，c，h，e，r D．r，e，t，e，a，c，h
8．有如下程序：
wz=[0,1,2,3,4,5,6]
start=0
qu=[0]*len(wz)
wm="abcdefg"
h=0;t=0
while len(wz)>0:
for i in range(2):
start=(start+1)%len(wz)
qu[t]=wz[start]
t=t+1
wz.pop(start)
mm=""
while h
h=h+1
print(mm)
程序运行后，显示的结果为（ ）
A．bdfaecg B．bdfaceg C．cfbgead D．cfbeadg
9．栈S从栈底到栈顶的元素依次为1，2，3，队列Q初始为空。约定：U操作是指元素出栈后入队，H操作是指元素出队后再入队。经过UUHU系列操作后，队列中队首到队尾的元素依次为（ ）
A．2,1,3 B．3,1,2 C．1,3,2 D．2,3,1
10．某Python程序如下：
from random import randint
a=[1,8,3,6,7,2,9,0,5,1,3]
s=[-1]*100;top=-1
i=0
x=randint（5,8）
while i
top-=1
top+=1;s[top]=a[i]
i+=1
while top!=-1:
print(s[top],end="")
top-=1
执行该程序段后，输出的结果不可能是（ ）
A．0 B．21 C．631 D．921
11．有如下程序段：
bt=["A","B","C","D",None,"E","F"]
result=[]
stack=[]
i=0
while stack or (i
stack.append(i)
i=2*i+1
else:
i=stack.pop()
result.append(bt[i])
i=2*i+2
print("-".join(result))
则程序运行后输出的结果为（ ）
A．A-B-D-C-E-F B．D-B-E-F-C-A C．D-B-A-E-C-F D．A-B-C-D-E-F
12．设栈S初始状态为空，元素A、B、C、D、E、F依次入栈，出栈的序列为D、F、E、C、B、A，则栈S的容量至少应该是（ ）
A．5 B．4 C．3 D．2
13．若用1表示进栈操作，用0表示出栈操作，若元素的进栈顺序是“q，w，e，r，t”，为了得到出栈序列“ewrtq”，则应进行的操作序列为( )
A．1101010100 B．1110010100 C．1110011000 D．1110100100
14．一个栈的入栈序列为“6、9、5、7、8、3”，其出栈序列不可能是( )
A．3、8、7、5、9、6 B．7、5、9、8、6、3 C．6、5、7、9、3、8 D．5、9、6、3、7、8
15．一个栈的初始状态为空，若它的输入序列为a、b、c、d，则它的输出序列为( )
A．a、b、c、d B．d、c、b、a
C．b、a、c、d D．d、b、a、c
试卷第1页，共3页
试卷第1页，共3页
参考答案：
1．D
【详解】本题考查的是堆栈的操作。堆栈的操作原则先进后出。stk可以看做一个堆栈，阅读程序可知对列表a中的字母进行入栈和出栈操作。选项A没有进行入栈和出栈操作，有可能；选项B把字母全部压入栈，有可能；选项C对字母A进行入栈，最后出栈，有可能；选项D，先把字母A、B进行入栈，然后出栈，出栈顺序应为B、A，故选项D不可能。
2．B
【详解】本题主要考查栈及Python程序调试。根据题意“除二取余法”可知先要执行取余，然后才能整除2更新n的值。top初值为-1标记此时栈中无元素，每递增一个元素，top先递增1，再将x保存到栈中，即st[top]=x，故代码顺序正确的是③①②④，故本题选B选项。
3．B
【详解】本题考查栈的基本操作。栈是先进后出，题干中限定条件栈s的最大长度为3，初始为空。A选项f最先出栈，说明a，b，c，d，e，f需要全部入栈后，f才能出栈，但这种情况下栈长度需要为6，不符合题意，故A选项错误；B选项c最先出栈，此时a，b，c入栈，接着c，b，a依次出栈，此时栈s内为空，接下来f出栈，说明d，e，f需要入栈，接着f，e，d出栈，过程中栈内长度符合题意，故B选项正确；C选项c最先出栈，此时a，b，c入栈，接着c出栈，此时栈内a，b，由于b是栈顶元素，所以接下来出栈元素不可能是a，故C选项错误；D选项c最先出栈，此时a，b，c入栈，接着c出栈，此时栈内a，b，接下来e出栈，需要d，e入栈，此时栈内a，b，d，e，栈长度为4，不符合题意，故D答案错误。本题应选B。
4．D
【详解】本题主要考查栈和队列的描述。栈的特点是先进后出，队列的特点是先进先出；队列只允在一端进行插入，在另一端进行删除； 栈限定仅能在一端进行插入和删除操作； 栈和队列均为操作受限的线性表，故本题选D选项。
5．D
【详解】本题主要考查Python及数据结构的应用。根据题意，s1为队列，s2为栈，每读取s一个字母时，偶数次取出放入s1中，奇数次取出放入s2中，存储后再依次取出，取时必须同时满足 head
6．B
【详解】本题考查数据结构栈的相关操作。以下仅取部分随机数序列进行解析：
A选项，若每次使用random．randint（0，1）时，都产生随机数0，即0、0、0、0，则只执行入栈操作（if部分），lst并未发生变化（elif部分未执行），其值仍然为['A'，'B'，'C'，'D'] ，选项A正确；
C选项，当产生随机数依次为：0、1、0、0、0时，第一次值为0，将lst第一个元素'A'入栈，i+1变为1，第二次值为1时，将栈st中元素出栈且赋值给lst[1]，则lst[1]='A'，第三、四、五次值为0时，进行入栈操作，i值由1变为4，结束循环，lst中对应位置元素并未发生变化，lst中元素最终为：['A'，'A'，'C'，'D'] ，选项C正确；
D选项，当产生随机数依次为：0、1、0、0、1、1、0时，第一次值为0，将lst第一个元素'A'入栈，i+1变为1，第二次值为1时，将栈st中元素出栈且赋值给lst[1]，则lst[1]='A'，第三、四次值为0时，进行入栈操作，st=['A'，'C']，第五、六次执行出栈，lst中元素为：['A'，'A'，'C'，'A]，第七次执行出栈，lst不变还是['A'，'A'，'C'，'A]，i值由1变为4，结束循环。选项D正确。
排除ACD，故本题答案是B选项。
7．A
【详解】本题主要考查栈的操作。根据栈的特点“先进后出”的原则，可知入栈序列是a，c，e，h，r，t，e，结合选项，其出栈序列可能的是c，h，e，a，t，e，r，故本题选A选项。
8．C
【详解】本题主要考查Python程序的执行。第一次循环后start=2，qu[0]=wz[start]=2；第二至第七次循环后，qu[1]=5，qu[2]=1，qu[3]=6，qu[4]=4，qu[5]=0，qu[6]=3。h初值为0，执行完最后一个while循环，即根据列表qu的值从wm中取对应的元素拼接到mm中，mm=mm+wm[qu[h]]，程序运行后，显示的结果为mm="cfbgead"，故本题选C选项。
9．D
【详解】本题考查栈、队列相关内容。栈的特点是后进先出，队列的特点是先进先出。初始状态，栈中从栈顶到栈底的元素为3、2、1，队列为空。第一次操作：U，即将栈顶元素3出栈后入队，队列中队首元素为3；第二次操作：U，即将栈顶元素2出栈后入队，队列中队首元素为3，队尾元素为2；第三次操作：H，即将队首元素3出队后再入队，队列中队首元素为2，队尾元素为3；第四次操作：U，即将栈顶元素1出栈后再入队，队列中从队首到队尾各元素依次为2、3、1。故本题答案是D选项。
10．C
【详解】本题主要考查栈数据结构及Python程序实现。分析程序可知，x随机生成5~8之间的整数，即外循环的次数，嵌套while循环中，栈中保存的数从栈底到栈顶成递增趋势，如果出现了不符合的数，则依次出栈直到符合递增趋势。因此x=5时，输出的结果是7631；x=6时，输出的结果是21；x=7时，输出的结果是921；x=8时，输出的结果是0，因此输出的结果不可能是631，故本题选C选项。
11．C
【详解】本题主要考查Python中stack()用法。分析程序可知，前3轮循环，即当i=0、1、3时均满足if判断条件，此时stack=[0,1,3]，接下来i=2*i+1=7不满足if判断条件，执行else部分， i=stack.pop()=3，result.append(bt[i])=["D"]，i=2*i+2=8，继续执行else，i=stack.pop()=1，result.append(bt[i])=["D","B"]，i=2*i+2=4，不满足if判断条件，继续执行else部分，i=stack.pop()=0，result.append(bt[i])=["D","B","A"]，此时结合选项可知程序运行后输出的结果为D-B-A-E-C-F，选C选项。
12．A
【详解】本题考查栈相关内容。栈的特点是先入后出。栈S 的初始状态为空，元素A、B、C、D、E、F依次入栈，出栈顺序为D、F、E、C、B、A。D出栈，说明D要先进栈，此时C、B、A已在栈内，栈的容量至少为4；D出栈后，F出栈，说明F需要先进栈，此时E、C、B、A在栈内，栈的容量至少为5；后续出栈序列为E、C、B、A，期间没有元素再入栈，栈的容量不会再增加，故栈的容量至少为5。本题答案是A选项。
13．B
【详解】本题主要考查栈的操作。为了得到出栈序列“ewrtq”，即e先出栈，按照进栈顺序，则qwe先进栈，对应111，接着是ew出栈，对应00，后面依次类推可得到应进行的操作序列为1110010100，故本题选B选项。
14．D
【详解】本题主要考查栈数据结构。选项D中，先入栈6、9、5，再依次出栈，此时再入栈7、8、3，则出栈顺序只能是3、8、7，故出栈序列不可能是5、9、6、3、7、8，故本题选D选项。
15．B
【详解】本题考查的栈的操作。堆栈是一个后进先出的数据结构，若它的输入序列为a、b、c、d，则它的输出序列为d、c、b、a。故本题应选B。
答案第1页，共2页
答案第1页，共2页