第三章 字符串、队列和栈 同步练习（Word版，含答案）2022—2023学年浙教版（2019）高中信息技术选修1
文档属性
| 名称 | 第三章 字符串、队列和栈 同步练习（Word版，含答案）2022—2023学年浙教版（2019）高中信息技术选修1 |  | |
| 格式 | docx | ||
| 文件大小 | 260.5KB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 浙教版（2019） | ||
| 科目 | 信息技术（信息科技） | ||
| 更新时间 | 2023-04-23 08:21:29 | ||
图片预览
文档简介
一．选择题（共27小题）
1．有如下 python 程序段：
from random import*
s＝''
for i in range（1，4）：
k＝int（random（ ）*3+1）
c＝chr（96+k）
if i%2＝＝k%2：
s＝s+c
else：
s＝c+s
print（s）
若该段程序执行以后，s 的值不可能的是（ ）
A．'abc' B．'bbc' C．'aab' D．'caa'
2．有如下python程序段：（注：字母ASCII码＞数字ASCII码，小写字母ASCII码＞大写字母ASCII码）
import random
s＝“olympicGames2021“；ans＝““；i＝0
while i＜len（s）﹣2：
t＝int（random.random（ ）*2）+1
x＝s[i]；y＝s[i+t]
if x＞y：
ans+＝x
else：
ans+＝y
i＝i+t+1
print（ans）
执行程序后，输出结果可能为（ ）
A．oyies B．ymcms2 C．oypcms2 D．ypces1
3．有如下Python程序段：
s＝“ABCDEF“
ch＝““
for i in range（0，len（s））：
a＝int（input（ ））；b＝（a+2）%6
ch＝ch+chr（ord（s[b]）+32）
print（ch）
运行程序后，依次输入3、1、4、5、2、6，输出ch的值是（ ）
A．cadebf B．fdabec C．aabbab D．ecfadb
4．有如下Python程序段：
s＝input（“请输入一串字符串：”）
m＝cnt＝1
for i in range（1，len（s））：
if s[i]＞s[i﹣1]：
cnt+＝1
if cnt＞m：
m＝cnt
else：
cnt＝1
print（m）
该程序段的功能是（ ）
A．输出字符串s中最大的字符的索引
B．输出字符串s中最大的字符
C．输出字符串s中最长的递增序列
D．输出字符串s中最长的递增序列长度
5．有如下Python程序段：
s＝input（“请输入一串字符串：”）
f＝True
for i in range（0，len（s）//2）：
if s[i]!＝s[len（s）﹣i﹣1]：
f＝False
break
print（f）
若执行该程序后，输出的结果是“True”，那么输入的值可能是（ ）
A．onion B．hello C．278 D．111
6．一个栈的入栈序列为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
7．一个栈的输入序列为“12345“，输出的第一个元素为“4“，则输出的第3个元素不可能的是（ ）
A．1 B．2 C．3 D．5
8．某Python程序如下：
s＝“xyAB#Fk”；k＝x＝“”；flag＝True
for i in range（len（s））：
If“a”＜＝s[i]＜＝“z”and flag：
x＝chr（（（ord（s[i]）﹣95））%26+97）#字符“a”的ASCⅡ码值为97
elif“A”＜＝s[i]＜＝“Z”and flag：
x＝chr＞（（（Cord（s[i]）﹣41））%26+65）#字符“A”的 ASCⅡ码值为65
flag＝False
else：
x＝s[i]；flag＝True
k＝k+x
print（k）
执行该程序后，输出值为（ ）
A．ZAyb#dK B．yzYZ#Dm C．zaYB#Dk D．zaYZ#Dm
9．创建一个容量为3的队列，元素2，3，5，1，3，5，2依次等待入队。入队规则为：
①若当前待入队元素已经在队列中，则跳过该元素，否则转②
②若当前队列已满，将队首元素出队列，否则转③
③将当前待入队元素入队列
操作完成后，队列中的元素为（ ）
A．2，3，5，1 B．1，2，3，5 C．2，3，5 D．5，1，2
10．已知一个栈的入栈序列是a，c，e，h，r，t，e，其出栈序列可能的是（ ）
A．c，h，c，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
11．一个栈的入栈序列为“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
12．一个栈的入栈序列为1，2，3，4，5，其出栈序列为sl，s2，s3，s4，s5。若s2是3，则s1不可能是（ ）
A．1 B．2 C．4 D．5
13．在某餐厅点餐系统中，利用队列来储存当前正在排队顾客的编号，head指向队首元素，tail指向队尾元素的下一个位置，若tail＝head+3，则现在排队的顾客数量为（ ）
A．2 B．3 C．4 D．5
14．依次在初始为空的队列中插入元素 a，b，c，d 以后，紧接着做了两次删除操作，此时的队首元素是（ ）
A．a B．b C．c D．d
15．用栈的数据结构编写进制转换中的“除二取余法”的程序段如下：
方框处的代码由以下四部分组成：
①n＝n//2
②top+＝1
③x＝n%2
④st[top]＝x
下列选项中，代码顺序正确的是（ ）
A．③④②① B．③①②④ C．①②③④ D．①③④②
16．某队列的数据结构如图所示，head 和 tail 分别为队列的头、尾指针。现对该队列进行以下操作：①队首元素出队输出②队首元素出队再入队，重复①②操作直到队列为空。
若队列数据元素为“LUCKY”，则输出顺序是（ ）
A．LYUKC B．LCYUK C．LCYKU D．LUCKY
17．若用1表示进栈操作，用0表示出栈操作，若元素的进栈顺序是“q，w，e，r，t”，为了得到出栈序列“ewrtq”，则应进行的操作序列为（ ）
A．1101010100 B．1110010100 C．1110011000 D．1110010100
18．下列有关栈和队列说法，正确的是（ ）
A．栈的特点是先进先出，队列的特点是先进后出
B．栈只允在一端进行插入，在另一端进行删除
C．队列限定仅能在一端进行插入和删除操作
D．栈和队列均为操作受限的线性表
19．已知变量s＝“2029106“，则下列Python表达式计算结果中最大的是（ ）
A．len（s） B．int（s[4]）
C．int（s）%100 D．int（s）//10**6
20．有一入栈序列为“ABCD”，以下以“C”开头的出栈序列中不正确的是（ ）
A．CABD B．CBAD C．CBDA D．CDBA
21．以下有关栈和队列的说法正确的是（ ）
A．栈和队列都是先进后出
B．栈和队列都是先进先出
C．队列元素前面只有一个，后面有多个
D．栈和队列只允许在端点插入和删除数据
22．一个序列的入栈顺序为 a，b，c，d，e，则该序列的出栈顺序不可能为（ ）
A．b，a，d，c，e B．d，c，b，a，e C．d，c，e，a，b D．c，b，a，e，d
23．一个序列的入栈顺序为1，2，3，4，5，6，若4第一个出栈，则下列出栈序列中不可能的是（ ）
A．4，2，3，1，5，6 B．4，6，5，3，2，1
C．4，3，5，2，6，1 D．4，5，3，6，2，1
24．check函数的功能是检查字符串s是否符合相应要求。如果符合返回True，否则返回False。要求。包括大写字母、小写字母、数字以及其它字符。请找出下面代码的两处错误（ ）
A．①② B．②③ C．③④ D．①④
25．一个栈的初始状态为空，若它的输入序列为a、b、c、d，则它的输出序列为（ ）
A．a、b、c、d B．d、c、b、a C．b、a、c、d D．d、b、a、c
26．设计一个判别表达式中括号是否配对的算法，采用（ ）数据结构最佳。
A．顺序表 B．链表 C．队列 D．栈
27．五节车厢以编号1，2，3，4，5顺序进入铁路调度站（栈），可以得到（ ）的编组。
A．3，4，5，1，2 B．2，4，1，3，5 C．3，5，4，2，1 D．1，3，5，2，4
二．简答题（共3小题）
28．字符串分段。输入一串仅由小写字母组成的字符串s，将这个字符串划分为尽可能多的小片段，要求同一个字母只出现在其中的一个片段中，并按照分段顺序逐行输出分段结果。程序运行界面如图所示。
（1）实现上述功能的Python程序如下，请在横线处填入合适的代码。
s＝input（“请输入一串仅包含小写字母的字符串：”）
c＝0
p＝[﹣1]*52#数组p用来记录各个小写字母出现的起始位置和结束位置
#a[0]记录a出现的起始位置，a[1]记录a出现的结束位置，依次类推
for i in range（0，len（s））：#记录各字符第一次和最后一次出现的位置
a＝①
if p[2*a]＝＝﹣1：
p[2*a]＝i
else：
p[2*a+1]＝i
for i in range（0，26）：
if p[2*i]＞p[2*i+1]：
p[2*i+1]＝p[2*i]#只出现一次的字符，起始位置就是结束位置
if p[2*i]!＝﹣1：
c+＝1
for i in range（o，c）：将字符位置按照出现的起始位置升序排序
for j in range（25，i，﹣1）：
if p[2*j]＞﹣1：
if p[2*（j﹣1]＞p[2*j]or② ：
p[2*（j﹣1）]，p[2*j]＝p[2*j]，p[2*（j﹣1）]
p[2*（j﹣1）+1]，p[2*j+1]＝p[2*j+1]，p[2*（j﹣1）+1]
t1，t2＝p[0]，p[1]#字符串分段
for i in range（1，c）：
if p[2*i]＜t2 and p[2*i+1]＞t2：
③
elif p[2*i]＞t2：
print（s[t1：t2+1]）
tl，t2＝p[2*i]，p[2*i+1]
print（s[t1：t2+1]）
（2）运行程序后，若输入的字符串s为“hshjhqueeqabaa”，输出的结果一共有 行，其中，第二行显示结果为 。
29．为四则运算式“6+（8﹣2）*2÷3”转逆波兰表达“682﹣2*3÷+”设计算法，编程实现。
分析：在数学运算表达式中，运算符总是置于与之相关的两个运算对象之间，在计算结果时，要考虑括号、运算符号的优先性。为了程序实现的方便，波兰逻辑学家J.Lukasiewicz提出了另一种表示法，将运算符置于其运算对象之后，没有括号，不用考虑运算符号的优先性。这种表达式称为后缀表达式，又叫逆波兰表达式。
如表达式“682﹣2*3÷+”是四则运算式“6+（8﹣2）*2÷3”的逆波兰表达式。为了处理方便，规定表达式中的数均为小于10的正整数，运算符为+、﹣、*、÷。
（1）抽象建模
设计两个栈bds、fh，栈bds用来存放表达式，栈fh用来暂时存放运算符。从左往右扫描四则运算式，遇到数字时，入栈bds；遇到运算符号时，根据运算符号的优先级设计进栈与出栈。
四则运算式“6+（8﹣2）*2÷3”转换规则的模拟过程如表所示：
结合表格的操作过程，用栈bds和栈fh记录每个操作后的栈内情况（见图），那么在操作2中栈fh里有内容为 （请从栈底到栈顶顺序书写）。
（2）设计算法
基于问题的抽象与建模，解决该问题的主要算法描述如下：
从左往右遍历四则运算式s（设中间变量为ch）：
1）当ch是数字，直接入栈bds；
2）当ch是运算符：
a.若ch为左括号时，直接入栈fh；
b.若ch为右括号时，则将栈fh元素弹出，压入栈bds，直到遇到左括号（左括号只
弹出，不压入栈bds）；
c.若ch为其它运算符时，如果运算符ch优先级大于栈fh中栈顶元素的优先级（或栈fh为空），直接入栈fh；否则，将栈fh元素依次弹出，并压入栈bds，直到运算符ch优先级大于栈fh中栈顶元素的优先级（或栈fh为空）；
3）将栈bds中元素依次出栈，即为该四则运算s的后缀表达式。
（3）编写程序
实现上述功能的Python代码如下，请在横线处填入合适代码。
30．【加试题】要求将某一字符串中指定的字符改写成小写或大写（如果原先是大写就改成小写，反之改成大写），并将处理后的字符重新输出．
程序界面如下图所示，在Text1中输入原始字符串，在Text2中输入需要改变的字符，单击“改变”按钮后，在Text3中输出处理后的结果．
程序代码如下：
Private Sub Command1_Click （ ）
Dim s As String，result As String，k As String
Dim zs As String，n As Integer
result＝“”
s＝Text1．Text
k＝Text2．Text
For n＝1To Len（s）
If zs＝k Then
If Asc（zs）＞＝65And Asc（zs）＜＝90Then
zs＝Chr（Asc（zs）+32）
Else lf Asc（zs）＞＝97And Asc（zs）＜＝122Then
zs＝Chr（Asc（zs）﹣32）
End If
End If
Next n
End Sub
在程序①、②、③横线处填入适当的语句或表达式，把程序补充完整．
（1）程序中①横线处应填入 ．
（2）程序中②横线处应填入 ．
（3）程序中③横线处应填入 ．
参考答案与试题解析
一．选择题（共27小题）
1．【解答】阅读程序可知，i的取值范围是[1，3]，k的取值范围为[1，3]，当k与i奇偶性相同时实行s＝s+c否则执行s＝c+s，选项A，当k依次取1，2，3可得，选项B，当k依次取2，2，3可得，选项D，当k依次取1，3，1可得。
故选：C。
2．【解答】程序中变量t的值只能是1或者2，因此每次是位置i与i+1或i与i+2的字符进行判断。
故选：B。
3．【解答】根据ASCII码值表可知，大小写字母之间的差值为32，阅读程序可知，根据依次输入的数字进行加2，然后除以6取余数转化在转化为小写字母，所以依次输入3、1、4、5、2、6，输出ch的值是f、d、a、b、e、c，所以选项B符合题意。
故选：B。
4．【解答】阅读程序可知用变量i历遍字符串，如果满足字符串中的元素是递增的，那么变量cnt增自动加1，将变量cnt的值赋值给m，否则不满足递增时，cnt＝1，最后输出的m是字符串中元素递增的长度。
故选：D。
5．【解答】如果输入为onion，len（s）＝5，i的取值范围为[0，2]，当I＝0时不满足s[i]!＝s[len（s）﹣i﹣1]，f＝Flase，输出为Flase，同理分析选项B和C均不符合题意。
故选：D。
6．【解答】选项A，进一个出一个可是实现1，2，3，4，5的出栈顺序；
选项B，先进栈1，2，3，4，然后出4，再进5，然后依次出5，3，2，1，可以实现；
选项C，先进1，2，3，4，然后出4，3，然后再进5，最后依次出栈5，2，1，所以该项错误；
选项D，先进栈1，2，3然后依次出栈为3，2，1，然后进栈4，5此时再依次出栈5，4，故该顺序可以实现。
故选：C。
7．【解答】一个栈的输入序列为“12345“，输出的第一个元素为“4“，那么此时可以继续进栈5，然后执行出栈，顺序为5，3，2，1；还可以出栈3，然后再进栈5，此时出栈顺序为5，2，1；还可以出栈3，2，在进栈5，此时出栈顺序为5，1；依次类推，无论如何1的出栈顺序要么为4，要么为5，不可能是3.
故选：A。
8．【解答】通过阅读程序可知，当提取到的字母为小写字母时，那么得到的x则向后移动两位得到对应的小写字母，如果提取到的为大写字母时，flag为交替变化的，当为True时，则向后移动24位得到的大写字母，同时flag的取值发生变化，当提取到其他字符时，直接累加到字符串k上即可，由此得到的结果为zaYB#Dk。
故选：C。
9．【解答】由于容量为3的队列，所以最初栈里的元素为2，3，5，当1进入栈时，若当前队列已满，将队首元素出队列，变为3，5，1，当入栈为3和5时，由于栈中 有该元素，跳过。当入栈为2时，当前队列已满，将队首元素出队列，变为5，1，2.故选：D。
10．【解答】根据栈的特点“先进后出”的原则，可知入栈序列是a，c，e，h，r，t，e，其出栈序列可能的是c，h，c，a，t，e，r。
故选：A。
11．【解答】根据先进后出的原则，可知入栈序列为“6、9、5、7、8、3”，7、8、3的出栈顺序有783，387，783但不可能出现378的顺序。
故选：D。
12．【解答】根据“先进后出”的原则，如果s2是3的话，那么相邻的s1不可能是5，因为中间有间隔，所以出栈的时候也必须间隔一个。故选：D。
13．【解答】有题意可知tail＝head+3，指向队尾元素的下一个位置所以 实际的顾客数为head+3﹣1，故为三个人。
故选：B。
14．【解答】队列数据结构的特点是先进先出。进入的顺序是abcd，删除就是出数据，删除两次分别出数据a和b。剩下cd，并且开头是c。故选C。
15．【解答】根据题意“除二取余法”可知先要执行取余，然后才能整除2。top默认值是﹣1，st[﹣1]表示列表最后一个元素。下一次循环top为0，就成列表第一个元素。余数就不连贯存储在列表了。因此先top+＝1，然后st[top]＝x。按以上规则选B。故选B。
16．【解答】根据题意先执行①输出L。接着执行②，U为队首出队加入队尾。字符串为CKYU。再次执行①输出C。接着执行②，K为队首出队加入队尾。字符串为YUK。第三次执行①输出Y。接着执行②，U为队首出队加入队尾。字符串为KU。
第四次执行①输出K。接着执行②，U为队首出队加入队尾。字符串为U。
第五次执行①输出U。
因此输出字符串为LCYKU。故选C。
17．【解答】若元素的进栈顺序是“q，w，e，r，t”，为了得到出栈序列“ewrtq”则顺序应该为q进，w进，e进，e出，w出，r进r出，t进t出，最后q出，故表示为1110010100。故选：B。
18．【解答】栈的特点是先进先出，队列的特点是先进先出；栈和队列是操作位置受限的线性表，即对插入和删除的位置加以限制。栈是仅允许在表的一端进行插入和删除的线性表，因而是后进先出表。队列是只允许在表的一端进行插入，另一端进行删除操作的线性表，因而是后进先出表。故选：D。
19．【解答】已知变量s＝“2029106“则len（s）＝7，int（s[4]）＝1，int（s）%100＝6，int（s）//10**6＝2。故选：A。
20．【解答】以“C”开头的出栈可以 为CBAD，CDBA，CBDA。故选：A。
21．【解答】栈和队列都是先进后出，队头只允许删除元素，队尾只允许插入元素，而栈只允许在栈顶插入和删除数据。故选：A。
22．【解答】根据进出栈的规则，可知进栈两个字母以上的，出栈时，后进的字母一定先出，根据这一原则，选项C中，不可能先出a再出b。故选：C。
23．【解答】一个序列的入栈顺序为1，2，3，4，5，6，若4第一个出栈，可以出3，可以进5出5，可以进56出65，由于进栈是1234，所以出栈必须是4321中间可以夹进出56，但无法先出2再出3.故选：A。
24．【解答】flag是列表，取列表中的数据用下标索引的方式。②处应该是c＝c+flag[j]。python判断是否相等用＝＝赋值用＝。③处应该是if c＝＝4：故选B。
25．【解答】根据栈的规律先入后出，后入先出，输入序列为a、b、c、d，则它的输出序列为d、c、b、a故选：B。
26．【解答】设计一个判别表达式中左、右括号是否配对出现的算法，采用栈数据结构最佳。原因：栈是一种具有记忆能力的线性表，存取规则是先进后出。故选：D。
27．【解答】栈按后进先出 123入栈，3出栈，45入栈，5出栈，4出栈，2出栈，1出栈。故选：C。
二．简答题（共3小题）
28．【解答】（1）在ASC表中，小写字母a的值为97，ord（ ） 函数以一个字符（长度为1的字符串）作为参数，返回对应的 ASCII 数值，所以①处填写为ord（s[i]）﹣97；p[2*（j﹣1]＞p[2*j]的同等条件为p[2*（j﹣1）]＝﹣1，在字符串分段中，如果p[2*i]＜t2 and p[2*i+1]＞t2条件乘以，则执行t2＝p[2*i+1]，在后面的输出语句中可以找到；
（2）运行程序后，若输入的字符串s为“hshjhqueeqabaa”，输出的结果一共有3行，第二行显示为queeq。
故答案为：（1）①ord（s[i]）﹣97 ②p[2*（j﹣1）]＝﹣1 ③t2＝p[2*i+1]
（2）3 queeq
29．【解答】①由表1中的操作2可知，栈fh里有内容为+（﹣。 ②若ch为右括号时，则将栈fh元素弹出，压入栈bds，直到遇到左括号（左括号只弹出，不压入栈bds），即退出循环，故此处填break。 ③如果topfh不等于﹣l或者fh[topfh]不等于“（“，说明fh栈中有其他运算符，则此处需要判断ch的优先级与fh[topfh]的优先级大小，由代码“fh[opfh]﹣ch”可知此处填yxij[ch]＞yxj[h[opf]。④此处循环结束后，已经将fh栈中比ch优先级高的运算符移到了bds栈中，此处将ch放到fh栈中，故此处填fh[topfh]﹣＝ch。
30．【解答】（1）根据题意，此处要求将从文本框输入的字符串s一个一个地取出，所以需要使用Mid 函数结合for语句中的循环变量n，每次取一个字符，然后将结果赋值给变量zs，因此答案是zs＝Mid（s，n，1）．
（2）将s中的值进行逐个比较和处理后，还必须按照顺序再组合回去，结果放在变量result中．所以此处填result＝result&zs（注意不能写成result＝zs&result）．
（3）本题的要求是在Text3中输出处理后的结果result，需要将result的值赋给Text3的Text，因而此处填写Text3．Text＝result．
故答案为：（1）zs＝Mid（s，n，1）；（2）result＝result+zs或result＝result&zs；（3）Text3．Text＝result
1．有如下 python 程序段：
from random import*
s＝''
for i in range（1，4）：
k＝int（random（ ）*3+1）
c＝chr（96+k）
if i%2＝＝k%2：
s＝s+c
else：
s＝c+s
print（s）
若该段程序执行以后，s 的值不可能的是（ ）
A．'abc' B．'bbc' C．'aab' D．'caa'
2．有如下python程序段：（注：字母ASCII码＞数字ASCII码，小写字母ASCII码＞大写字母ASCII码）
import random
s＝“olympicGames2021“；ans＝““；i＝0
while i＜len（s）﹣2：
t＝int（random.random（ ）*2）+1
x＝s[i]；y＝s[i+t]
if x＞y：
ans+＝x
else：
ans+＝y
i＝i+t+1
print（ans）
执行程序后，输出结果可能为（ ）
A．oyies B．ymcms2 C．oypcms2 D．ypces1
3．有如下Python程序段：
s＝“ABCDEF“
ch＝““
for i in range（0，len（s））：
a＝int（input（ ））；b＝（a+2）%6
ch＝ch+chr（ord（s[b]）+32）
print（ch）
运行程序后，依次输入3、1、4、5、2、6，输出ch的值是（ ）
A．cadebf B．fdabec C．aabbab D．ecfadb
4．有如下Python程序段：
s＝input（“请输入一串字符串：”）
m＝cnt＝1
for i in range（1，len（s））：
if s[i]＞s[i﹣1]：
cnt+＝1
if cnt＞m：
m＝cnt
else：
cnt＝1
print（m）
该程序段的功能是（ ）
A．输出字符串s中最大的字符的索引
B．输出字符串s中最大的字符
C．输出字符串s中最长的递增序列
D．输出字符串s中最长的递增序列长度
5．有如下Python程序段：
s＝input（“请输入一串字符串：”）
f＝True
for i in range（0，len（s）//2）：
if s[i]!＝s[len（s）﹣i﹣1]：
f＝False
break
print（f）
若执行该程序后，输出的结果是“True”，那么输入的值可能是（ ）
A．onion B．hello C．278 D．111
6．一个栈的入栈序列为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
7．一个栈的输入序列为“12345“，输出的第一个元素为“4“，则输出的第3个元素不可能的是（ ）
A．1 B．2 C．3 D．5
8．某Python程序如下：
s＝“xyAB#Fk”；k＝x＝“”；flag＝True
for i in range（len（s））：
If“a”＜＝s[i]＜＝“z”and flag：
x＝chr（（（ord（s[i]）﹣95））%26+97）#字符“a”的ASCⅡ码值为97
elif“A”＜＝s[i]＜＝“Z”and flag：
x＝chr＞（（（Cord（s[i]）﹣41））%26+65）#字符“A”的 ASCⅡ码值为65
flag＝False
else：
x＝s[i]；flag＝True
k＝k+x
print（k）
执行该程序后，输出值为（ ）
A．ZAyb#dK B．yzYZ#Dm C．zaYB#Dk D．zaYZ#Dm
9．创建一个容量为3的队列，元素2，3，5，1，3，5，2依次等待入队。入队规则为：
①若当前待入队元素已经在队列中，则跳过该元素，否则转②
②若当前队列已满，将队首元素出队列，否则转③
③将当前待入队元素入队列
操作完成后，队列中的元素为（ ）
A．2，3，5，1 B．1，2，3，5 C．2，3，5 D．5，1，2
10．已知一个栈的入栈序列是a，c，e，h，r，t，e，其出栈序列可能的是（ ）
A．c，h，c，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
11．一个栈的入栈序列为“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
12．一个栈的入栈序列为1，2，3，4，5，其出栈序列为sl，s2，s3，s4，s5。若s2是3，则s1不可能是（ ）
A．1 B．2 C．4 D．5
13．在某餐厅点餐系统中，利用队列来储存当前正在排队顾客的编号，head指向队首元素，tail指向队尾元素的下一个位置，若tail＝head+3，则现在排队的顾客数量为（ ）
A．2 B．3 C．4 D．5
14．依次在初始为空的队列中插入元素 a，b，c，d 以后，紧接着做了两次删除操作，此时的队首元素是（ ）
A．a B．b C．c D．d
15．用栈的数据结构编写进制转换中的“除二取余法”的程序段如下：
方框处的代码由以下四部分组成：
①n＝n//2
②top+＝1
③x＝n%2
④st[top]＝x
下列选项中，代码顺序正确的是（ ）
A．③④②① B．③①②④ C．①②③④ D．①③④②
16．某队列的数据结构如图所示，head 和 tail 分别为队列的头、尾指针。现对该队列进行以下操作：①队首元素出队输出②队首元素出队再入队，重复①②操作直到队列为空。
若队列数据元素为“LUCKY”，则输出顺序是（ ）
A．LYUKC B．LCYUK C．LCYKU D．LUCKY
17．若用1表示进栈操作，用0表示出栈操作，若元素的进栈顺序是“q，w，e，r，t”，为了得到出栈序列“ewrtq”，则应进行的操作序列为（ ）
A．1101010100 B．1110010100 C．1110011000 D．1110010100
18．下列有关栈和队列说法，正确的是（ ）
A．栈的特点是先进先出，队列的特点是先进后出
B．栈只允在一端进行插入，在另一端进行删除
C．队列限定仅能在一端进行插入和删除操作
D．栈和队列均为操作受限的线性表
19．已知变量s＝“2029106“，则下列Python表达式计算结果中最大的是（ ）
A．len（s） B．int（s[4]）
C．int（s）%100 D．int（s）//10**6
20．有一入栈序列为“ABCD”，以下以“C”开头的出栈序列中不正确的是（ ）
A．CABD B．CBAD C．CBDA D．CDBA
21．以下有关栈和队列的说法正确的是（ ）
A．栈和队列都是先进后出
B．栈和队列都是先进先出
C．队列元素前面只有一个，后面有多个
D．栈和队列只允许在端点插入和删除数据
22．一个序列的入栈顺序为 a，b，c，d，e，则该序列的出栈顺序不可能为（ ）
A．b，a，d，c，e B．d，c，b，a，e C．d，c，e，a，b D．c，b，a，e，d
23．一个序列的入栈顺序为1，2，3，4，5，6，若4第一个出栈，则下列出栈序列中不可能的是（ ）
A．4，2，3，1，5，6 B．4，6，5，3，2，1
C．4，3，5，2，6，1 D．4，5，3，6，2，1
24．check函数的功能是检查字符串s是否符合相应要求。如果符合返回True，否则返回False。要求。包括大写字母、小写字母、数字以及其它字符。请找出下面代码的两处错误（ ）
A．①② B．②③ C．③④ D．①④
25．一个栈的初始状态为空，若它的输入序列为a、b、c、d，则它的输出序列为（ ）
A．a、b、c、d B．d、c、b、a C．b、a、c、d D．d、b、a、c
26．设计一个判别表达式中括号是否配对的算法，采用（ ）数据结构最佳。
A．顺序表 B．链表 C．队列 D．栈
27．五节车厢以编号1，2，3，4，5顺序进入铁路调度站（栈），可以得到（ ）的编组。
A．3，4，5，1，2 B．2，4，1，3，5 C．3，5，4，2，1 D．1，3，5，2，4
二．简答题（共3小题）
28．字符串分段。输入一串仅由小写字母组成的字符串s，将这个字符串划分为尽可能多的小片段，要求同一个字母只出现在其中的一个片段中，并按照分段顺序逐行输出分段结果。程序运行界面如图所示。
（1）实现上述功能的Python程序如下，请在横线处填入合适的代码。
s＝input（“请输入一串仅包含小写字母的字符串：”）
c＝0
p＝[﹣1]*52#数组p用来记录各个小写字母出现的起始位置和结束位置
#a[0]记录a出现的起始位置，a[1]记录a出现的结束位置，依次类推
for i in range（0，len（s））：#记录各字符第一次和最后一次出现的位置
a＝①
if p[2*a]＝＝﹣1：
p[2*a]＝i
else：
p[2*a+1]＝i
for i in range（0，26）：
if p[2*i]＞p[2*i+1]：
p[2*i+1]＝p[2*i]#只出现一次的字符，起始位置就是结束位置
if p[2*i]!＝﹣1：
c+＝1
for i in range（o，c）：将字符位置按照出现的起始位置升序排序
for j in range（25，i，﹣1）：
if p[2*j]＞﹣1：
if p[2*（j﹣1]＞p[2*j]or② ：
p[2*（j﹣1）]，p[2*j]＝p[2*j]，p[2*（j﹣1）]
p[2*（j﹣1）+1]，p[2*j+1]＝p[2*j+1]，p[2*（j﹣1）+1]
t1，t2＝p[0]，p[1]#字符串分段
for i in range（1，c）：
if p[2*i]＜t2 and p[2*i+1]＞t2：
③
elif p[2*i]＞t2：
print（s[t1：t2+1]）
tl，t2＝p[2*i]，p[2*i+1]
print（s[t1：t2+1]）
（2）运行程序后，若输入的字符串s为“hshjhqueeqabaa”，输出的结果一共有 行，其中，第二行显示结果为 。
29．为四则运算式“6+（8﹣2）*2÷3”转逆波兰表达“682﹣2*3÷+”设计算法，编程实现。
分析：在数学运算表达式中，运算符总是置于与之相关的两个运算对象之间，在计算结果时，要考虑括号、运算符号的优先性。为了程序实现的方便，波兰逻辑学家J.Lukasiewicz提出了另一种表示法，将运算符置于其运算对象之后，没有括号，不用考虑运算符号的优先性。这种表达式称为后缀表达式，又叫逆波兰表达式。
如表达式“682﹣2*3÷+”是四则运算式“6+（8﹣2）*2÷3”的逆波兰表达式。为了处理方便，规定表达式中的数均为小于10的正整数，运算符为+、﹣、*、÷。
（1）抽象建模
设计两个栈bds、fh，栈bds用来存放表达式，栈fh用来暂时存放运算符。从左往右扫描四则运算式，遇到数字时，入栈bds；遇到运算符号时，根据运算符号的优先级设计进栈与出栈。
四则运算式“6+（8﹣2）*2÷3”转换规则的模拟过程如表所示：
结合表格的操作过程，用栈bds和栈fh记录每个操作后的栈内情况（见图），那么在操作2中栈fh里有内容为 （请从栈底到栈顶顺序书写）。
（2）设计算法
基于问题的抽象与建模，解决该问题的主要算法描述如下：
从左往右遍历四则运算式s（设中间变量为ch）：
1）当ch是数字，直接入栈bds；
2）当ch是运算符：
a.若ch为左括号时，直接入栈fh；
b.若ch为右括号时，则将栈fh元素弹出，压入栈bds，直到遇到左括号（左括号只
弹出，不压入栈bds）；
c.若ch为其它运算符时，如果运算符ch优先级大于栈fh中栈顶元素的优先级（或栈fh为空），直接入栈fh；否则，将栈fh元素依次弹出，并压入栈bds，直到运算符ch优先级大于栈fh中栈顶元素的优先级（或栈fh为空）；
3）将栈bds中元素依次出栈，即为该四则运算s的后缀表达式。
（3）编写程序
实现上述功能的Python代码如下，请在横线处填入合适代码。
30．【加试题】要求将某一字符串中指定的字符改写成小写或大写（如果原先是大写就改成小写，反之改成大写），并将处理后的字符重新输出．
程序界面如下图所示，在Text1中输入原始字符串，在Text2中输入需要改变的字符，单击“改变”按钮后，在Text3中输出处理后的结果．
程序代码如下：
Private Sub Command1_Click （ ）
Dim s As String，result As String，k As String
Dim zs As String，n As Integer
result＝“”
s＝Text1．Text
k＝Text2．Text
For n＝1To Len（s）
If zs＝k Then
If Asc（zs）＞＝65And Asc（zs）＜＝90Then
zs＝Chr（Asc（zs）+32）
Else lf Asc（zs）＞＝97And Asc（zs）＜＝122Then
zs＝Chr（Asc（zs）﹣32）
End If
End If
Next n
End Sub
在程序①、②、③横线处填入适当的语句或表达式，把程序补充完整．
（1）程序中①横线处应填入 ．
（2）程序中②横线处应填入 ．
（3）程序中③横线处应填入 ．
参考答案与试题解析
一．选择题（共27小题）
1．【解答】阅读程序可知，i的取值范围是[1，3]，k的取值范围为[1，3]，当k与i奇偶性相同时实行s＝s+c否则执行s＝c+s，选项A，当k依次取1，2，3可得，选项B，当k依次取2，2，3可得，选项D，当k依次取1，3，1可得。
故选：C。
2．【解答】程序中变量t的值只能是1或者2，因此每次是位置i与i+1或i与i+2的字符进行判断。
故选：B。
3．【解答】根据ASCII码值表可知，大小写字母之间的差值为32，阅读程序可知，根据依次输入的数字进行加2，然后除以6取余数转化在转化为小写字母，所以依次输入3、1、4、5、2、6，输出ch的值是f、d、a、b、e、c，所以选项B符合题意。
故选：B。
4．【解答】阅读程序可知用变量i历遍字符串，如果满足字符串中的元素是递增的，那么变量cnt增自动加1，将变量cnt的值赋值给m，否则不满足递增时，cnt＝1，最后输出的m是字符串中元素递增的长度。
故选：D。
5．【解答】如果输入为onion，len（s）＝5，i的取值范围为[0，2]，当I＝0时不满足s[i]!＝s[len（s）﹣i﹣1]，f＝Flase，输出为Flase，同理分析选项B和C均不符合题意。
故选：D。
6．【解答】选项A，进一个出一个可是实现1，2，3，4，5的出栈顺序；
选项B，先进栈1，2，3，4，然后出4，再进5，然后依次出5，3，2，1，可以实现；
选项C，先进1，2，3，4，然后出4，3，然后再进5，最后依次出栈5，2，1，所以该项错误；
选项D，先进栈1，2，3然后依次出栈为3，2，1，然后进栈4，5此时再依次出栈5，4，故该顺序可以实现。
故选：C。
7．【解答】一个栈的输入序列为“12345“，输出的第一个元素为“4“，那么此时可以继续进栈5，然后执行出栈，顺序为5，3，2，1；还可以出栈3，然后再进栈5，此时出栈顺序为5，2，1；还可以出栈3，2，在进栈5，此时出栈顺序为5，1；依次类推，无论如何1的出栈顺序要么为4，要么为5，不可能是3.
故选：A。
8．【解答】通过阅读程序可知，当提取到的字母为小写字母时，那么得到的x则向后移动两位得到对应的小写字母，如果提取到的为大写字母时，flag为交替变化的，当为True时，则向后移动24位得到的大写字母，同时flag的取值发生变化，当提取到其他字符时，直接累加到字符串k上即可，由此得到的结果为zaYB#Dk。
故选：C。
9．【解答】由于容量为3的队列，所以最初栈里的元素为2，3，5，当1进入栈时，若当前队列已满，将队首元素出队列，变为3，5，1，当入栈为3和5时，由于栈中 有该元素，跳过。当入栈为2时，当前队列已满，将队首元素出队列，变为5，1，2.故选：D。
10．【解答】根据栈的特点“先进后出”的原则，可知入栈序列是a，c，e，h，r，t，e，其出栈序列可能的是c，h，c，a，t，e，r。
故选：A。
11．【解答】根据先进后出的原则，可知入栈序列为“6、9、5、7、8、3”，7、8、3的出栈顺序有783，387，783但不可能出现378的顺序。
故选：D。
12．【解答】根据“先进后出”的原则，如果s2是3的话，那么相邻的s1不可能是5，因为中间有间隔，所以出栈的时候也必须间隔一个。故选：D。
13．【解答】有题意可知tail＝head+3，指向队尾元素的下一个位置所以 实际的顾客数为head+3﹣1，故为三个人。
故选：B。
14．【解答】队列数据结构的特点是先进先出。进入的顺序是abcd，删除就是出数据，删除两次分别出数据a和b。剩下cd，并且开头是c。故选C。
15．【解答】根据题意“除二取余法”可知先要执行取余，然后才能整除2。top默认值是﹣1，st[﹣1]表示列表最后一个元素。下一次循环top为0，就成列表第一个元素。余数就不连贯存储在列表了。因此先top+＝1，然后st[top]＝x。按以上规则选B。故选B。
16．【解答】根据题意先执行①输出L。接着执行②，U为队首出队加入队尾。字符串为CKYU。再次执行①输出C。接着执行②，K为队首出队加入队尾。字符串为YUK。第三次执行①输出Y。接着执行②，U为队首出队加入队尾。字符串为KU。
第四次执行①输出K。接着执行②，U为队首出队加入队尾。字符串为U。
第五次执行①输出U。
因此输出字符串为LCYKU。故选C。
17．【解答】若元素的进栈顺序是“q，w，e，r，t”，为了得到出栈序列“ewrtq”则顺序应该为q进，w进，e进，e出，w出，r进r出，t进t出，最后q出，故表示为1110010100。故选：B。
18．【解答】栈的特点是先进先出，队列的特点是先进先出；栈和队列是操作位置受限的线性表，即对插入和删除的位置加以限制。栈是仅允许在表的一端进行插入和删除的线性表，因而是后进先出表。队列是只允许在表的一端进行插入，另一端进行删除操作的线性表，因而是后进先出表。故选：D。
19．【解答】已知变量s＝“2029106“则len（s）＝7，int（s[4]）＝1，int（s）%100＝6，int（s）//10**6＝2。故选：A。
20．【解答】以“C”开头的出栈可以 为CBAD，CDBA，CBDA。故选：A。
21．【解答】栈和队列都是先进后出，队头只允许删除元素，队尾只允许插入元素，而栈只允许在栈顶插入和删除数据。故选：A。
22．【解答】根据进出栈的规则，可知进栈两个字母以上的，出栈时，后进的字母一定先出，根据这一原则，选项C中，不可能先出a再出b。故选：C。
23．【解答】一个序列的入栈顺序为1，2，3，4，5，6，若4第一个出栈，可以出3，可以进5出5，可以进56出65，由于进栈是1234，所以出栈必须是4321中间可以夹进出56，但无法先出2再出3.故选：A。
24．【解答】flag是列表，取列表中的数据用下标索引的方式。②处应该是c＝c+flag[j]。python判断是否相等用＝＝赋值用＝。③处应该是if c＝＝4：故选B。
25．【解答】根据栈的规律先入后出，后入先出，输入序列为a、b、c、d，则它的输出序列为d、c、b、a故选：B。
26．【解答】设计一个判别表达式中左、右括号是否配对出现的算法，采用栈数据结构最佳。原因：栈是一种具有记忆能力的线性表，存取规则是先进后出。故选：D。
27．【解答】栈按后进先出 123入栈，3出栈，45入栈，5出栈，4出栈，2出栈，1出栈。故选：C。
二．简答题（共3小题）
28．【解答】（1）在ASC表中，小写字母a的值为97，ord（ ） 函数以一个字符（长度为1的字符串）作为参数，返回对应的 ASCII 数值，所以①处填写为ord（s[i]）﹣97；p[2*（j﹣1]＞p[2*j]的同等条件为p[2*（j﹣1）]＝﹣1，在字符串分段中，如果p[2*i]＜t2 and p[2*i+1]＞t2条件乘以，则执行t2＝p[2*i+1]，在后面的输出语句中可以找到；
（2）运行程序后，若输入的字符串s为“hshjhqueeqabaa”，输出的结果一共有3行，第二行显示为queeq。
故答案为：（1）①ord（s[i]）﹣97 ②p[2*（j﹣1）]＝﹣1 ③t2＝p[2*i+1]
（2）3 queeq
29．【解答】①由表1中的操作2可知，栈fh里有内容为+（﹣。 ②若ch为右括号时，则将栈fh元素弹出，压入栈bds，直到遇到左括号（左括号只弹出，不压入栈bds），即退出循环，故此处填break。 ③如果topfh不等于﹣l或者fh[topfh]不等于“（“，说明fh栈中有其他运算符，则此处需要判断ch的优先级与fh[topfh]的优先级大小，由代码“fh[opfh]﹣ch”可知此处填yxij[ch]＞yxj[h[opf]。④此处循环结束后，已经将fh栈中比ch优先级高的运算符移到了bds栈中，此处将ch放到fh栈中，故此处填fh[topfh]﹣＝ch。
30．【解答】（1）根据题意，此处要求将从文本框输入的字符串s一个一个地取出，所以需要使用Mid 函数结合for语句中的循环变量n，每次取一个字符，然后将结果赋值给变量zs，因此答案是zs＝Mid（s，n，1）．
（2）将s中的值进行逐个比较和处理后，还必须按照顺序再组合回去，结果放在变量result中．所以此处填result＝result&zs（注意不能写成result＝zs&result）．
（3）本题的要求是在Text3中输出处理后的结果result，需要将result的值赋给Text3的Text，因而此处填写Text3．Text＝result．
故答案为：（1）zs＝Mid（s，n，1）；（2）result＝result+zs或result＝result&zs；（3）Text3．Text＝result