资源简介

第三章　字符串、队列和栈
课时1　字符串
一、基础巩固
1.已知x＝″2.0＋3＝5.0″，下列表达式成立的是(　　)
A.len(x)＝＝8 B.x[0]>x[2]
C.x[：2]＝＝″2.0″ D.x[6：：]＝＝″5″
2.字符串变量s＝″2022jiaxing″，则表达式s[1：len(s)∥2]＋s[2]*2的值是(　　)
A.″20224″ B.″2026″ C.″022j22″ D.″022j4″
3.通过键盘输入一串字符串，程序输出该字符串的所有子串。例如，下面程序段当输入“the”时，将输出['t'，'th'，'the'，'h'，'he'，'e']。
s＝input(″请输入一个字符串：″)
a＝[]
for i in range(len(s))：
　 for j in range((1)________________)：
a.append((2)________________)
　print(a)
为实现上述功能，上述程序段(1)(2)处的语句分别是(　　)
A.①i，len(s)　　　 ②s[i：j＋1]
B.①i，len(s)－i＋1 ②s[i：j＋i]
C.①i，len(s)－i＋1 ②s[i：j＋1]
D.①i，len(s) ②s[j：j＋i]
4.某RGB色彩模式图像信息存储在文本文件中，文件的一行存储图像的一个像素，现对图像中连续的0或1进行压缩，某个像素的压缩算法如下：
def change(s): #对连续多个0或1进行压缩，字符串s中不含换行符
　 i＝1；j＝0；result＝″″
　 sd＝″0123456789ABCDEF″
　 while i　 while i　　　 　i＋＝1
　 d＝i－j
　 s1＝s[j]＋sd[d%16]
　 if d>16：
　　　　s1＝s[j]＋sd[0]＋s1
　 result＋＝s1
　 j＝i
return result
若某个像素点的信息为“111100000000000000000001”，则压缩后的信息为(　　)
A.41003011 B.140003 C.14000311 D.140F0411
5.有如下程序段：
s1＝″232″
s2＝″abcdef″
for i in s1：
　 m＝int(i)
　 c＝s2[m：m＋1]
　 s2＝s2[1：m＋1]＋c＋s2[m＋1：]
print(s2)
执行该程序段后，变量s2的值是(　　)
A.″eef″ B.″cdddef″ C.″dcdcdcdef″ D.″abccccdef ″
6.有如下程序段：
s＝″aabbbcc″
i＝3
while ij＝i－2
if s[i－1]＝＝s[i] and s[j]＝＝s[j－1]：
　 s＝s[：i]＋s[i＋1：]
else：
　 i＋＝1
print(s)
执行该程序段后，变量 s 的值是(　　)
A.″abc″ B.″aabbc″ C.″aabc″ D.″aabcc″
7.有如下 Python 程序段：
s＝″5A9C3B0E7D″
ans＝″″； i＝0
while s[i]！＝″0″：
　 t＝int(s[i])
　　ans＋＝s[t]
　　i＝t－1
print(ans)
运行该程序段后，变量 ans 的值是(　　)
A.″BCDEA″ B.″BCD″ C.″ABCD″ D.″BCDE″
二、能力提升
8.下列 Python 程序段功能为：输入由英文字母组成的字符串，若字符串中有连续升序段(相邻字符 ASCII 码值增量为 1)，则把该升序段缩写为“首字符－尾字符”构成的新字符串。例如：字符串为“abcbxy”，则缩写成“a－cbx－y”。
s＝input(″请输入字符串：″)
k＝len(s)；flag＝False；result＝″″
for i in range(0，k－1)：
　 if ①________________ :
　 result＝result＋s[i]＋″－″
　 flag＝True
　 elif ord(s[i])！＝ord(s[i＋1])－1:
　 result＝result＋s[i]
　 flag＝False
②________________
print(″缩写后的字符串为″，result)
则划线处应填入的代码为(　　)
A.①ord(s[i])＝＝ord(s[i＋1])－1 and flag 　　　②result＝result＋s[i]
B.① ord(s[i])＝＝ord(s[i＋1])－1 and not flag 　②result＝result＋s[i]
C.① ord(s[i])＝＝ord(s[i＋1])－1 and flag 　　　②result＝result＋s[i＋1]
D.① ord(s[i])＝＝ord(s[i＋1])－1 and not flag 　②result＝result＋s[i＋1]
9.某字符串s是由一个原始字符串反复重叠形成的。例如字符串″abcababcababcab″的是由原始字符串″abcab″重叠而成。检测的算法：将该字符串划分成若干段，若字符串每一段与第一段相同，则认为该字符串是由这段字符重叠而成。为查找字符串s的原始字符串，有如下程序段：
s＝″abcababcababcababcababcab″
n＝len(s)；ans＝″″
for i in range(1，n∥2＋1)：
　 if ①________________
　for j in range(i，n，i)：
　 　 if ②________________
　　 　　　break
　　 else：
　　　　ans＝s[：i]
print(″原始串是：″，ans)
将划线处填写完整。
10.有Python程序段如下：
s＝'I Love You HangZhou！'
s1＝''
for i in range(0，len(s)，3)：
　 c＝s[i]
　 if ord(c)>＝ord('a')：
　 c＝chr(ord(c)－ord('a')＋ord('A'))
　 s1＝c＋s1
print(s1)
程序运行后，输出的值是(　　)
A.OUAZU B.OUAU C.UZAUO D.UAUO
11.有如下Python程序段：
s＝″abbaddcab″
k＝0；r＝″″
b＝[″″]*6
for i in s：
　 if i＝＝b[k]：
　k－＝1
　 else：
　 k＋＝1
　b[k]＝i
for i in range(1，k＋1)：
　 print(b[i]，end＝″″)
执行该程序段后，输出的内容是(　　)
A.abdc B.aacab C.c D.cab
12.判断两个字符串是否相等：规定字符“？”为万能字符，即可与任意一个字符相等，在忽略字符串中空格以及不区分大小写的前提下，判断两个字符串是否相同。Python程序运行界面如图所示。
请输入一个字符串：？？ a d ？？dad wd 请输入另一个字符串：a a c？d？d w 两个字符串相同
(1)根据以上规则字符串’？？ad？？dad wd’和字符串’a？？？c？d？d？d’是否相等____(填：是/否)。
(2)实现上述功能的Python程序如下，请在划线处填入适当的代码。
s1＝input(″请输入一个字符串：″)
s2＝input(″请输入另一个字符串：″)
s1＝s1.upper()
s2＝s2.upper()
s＝″″
#将字符串s1中的空格去掉
for i in s1：
if i ！＝″″：
①________________
s1＝s
#同上，将字符串s2中的空格去掉，代码略
i＝0
if len(s1)！＝len(s2)：
print(″两个字符串不相同″)
else：
while i　　c1＝s1[i]；c2＝s2[i]
　 　if c1＝＝c2：
　　 　 ②________________
　　else：
　　　 if ③________________：
　　　　 　 i＋＝1
　　　 else：
　　　 　　break
if i＝＝len(s1)：
print(″两个字符串相同″)
else：
print(″两个字符串不相同″)
13.小张参加学校举行的密码破解攻防比赛，他需要在规定时间破解对手密码。比赛时，小张发现对方密文可能采用凯撒加密，这是一种简单且广为人知的加密技术，方法是将明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文，非字母保持原状。例如，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，Z变成C，以此类推。
小张为了增加破解难度，决定在凯撒加密基础上，引入密钥字符串，密钥字符及对应的偏移量如下表所示，密钥字符串长度不够时，可循环使用。
密钥 A B C D E F G H I J K L M
偏移量 0 1 2 3 4 5 6 7 8 9 10 11 12
密钥 N O P Q R S T U V W X Y Z
偏移量 13 14 15 16 17 18 19 20 21 22 23 24 25
例如：若输入明文为：Hello，输入密钥为：ABC，则得到密文为：Hfnlp
(1)若明文：ZhouShan密钥为：LOVE，则密文为：________
(2)引入密钥后的加密算法的Python程序代码如下：
def change(x)：
ek＝[]
for c in x：
　　if ' a'<＝c<＝'z'：
　　　　①________
　 　elif ' A'<＝c<＝'Z'：
　　 　　#与小写字母相似处理，代码略
return ek
s＝input(″输入原文：″)
key＝input(″输入秘钥：″)
keyn＝change(key)
ch＝″″
for i in range(len(s))：
k＝keyn[②________]
if ' a'<＝s[i]<＝'z'：
　ch＝③________
　result＝result＋ch
elif 'A'<＝s[i]<＝'Z'：
　#与小写字母相似处理，代码略
else：
　result＝result＋s[i]
print(result)
(2)在划线处填写合适代码，完善程序。
(3)程序调试过程中，出现如下错误提示“NameError：name' result' is not defined”，产生此错误的原因是___________________________________________________。
14.查找包含26个小写字母的最短字符串：输入任意一串包含小写字母的字符串(长度n>＝26)，要求找到长度最小的一段区间，能够包含全部26个小写英文字母。小王设计了Python程序用于搜索最短字符串，若无解，则输出“无解！”，反之输出该最小区间的长度以及字符的开始位置，并输出相应的最短字符串，程序界面如图所示：
请输入字符串内容：wurfabcdefghijklmnopqrstuvwxyzzsdf 包含26个字母的字符串为：abcdefghijklmnopqrstuvw 最短长度：26　开始位置：4
本题的算法思想是：
①确定初始右边界：从第1个字符开始，向右搜索到包含全部26个字母的子串，并因此而确定右边界，同时记录每个字母在子串中出现过的次数。
②调整子串左边界：若左边界有重复的字母则表明该子串可缩短，故左边可右移1位，……直到找到一个符合条件的子串并记录，然后子串左边界再右移1位。
③调整子串右边界：子串右边界继续右移，在新子串符合条件后，记录并进行比较。
重复②各调整步骤，直至遍历完整个字符串，获得并输出满足条件的最小长度字符串。
实现上述功能的Python程序如下，请回答下列问题。
text＝input(″请输入字符串内容：″)
n＝len(text)
s＝[0 for i in range(n)]
for i in range(n)：
①________________
res＝″″
k＝left＝pos＝0
length＝n
f＝[0]*26
for i in range(n)：
if f[s[i]]＝＝0：
　　　　k＝k＋1
f[s[i]]＝f[s[i]]＋1
while ②________________：
f[s[pos]]＝f[s[pos]]－1
if ③________________：
　　　　k－＝1
　　　　if i－pos＋1　　　　　　length＝i－pos＋1
　　　　　　res＝text[pos：pos＋length]
　　　　　　left＝pos
pos＋＝1
if res ！＝″″：
print(″包含26个字母的字符串为：″，res)
print(″最短长度：″，length，″开始位置：″，left)
else：
print(″无解！″)
(1)对于字符串“abfabcfdeefed”，包含字母“abcdef”的最短字符串长度为________(填数字)。
(2)请在划线处填入合适的代码。
课时1　字符串
1.B　[本题主要考查的是字符串的函数及基本运算。len(x)的值为9，因此A选项错误；x[：2]的值为″2.″，因此C选项错误；x[6：：]的值为″5.0″，因此D选项错误；x[0]的值为″2″，x[2]的值为″0″，因为″2″>″0″，因此x[0]>x[2]，故答案为B。]
2.C　[本题主要考查的是字符串切片和运算。s[1：len(s)∥2]表示从第2个字符位置取到中间位置的前一个字符，结果为“022j”，s[2]*2表示索引第3个字符“2”重复2次，结果为“22”，最后连接两个字符串，因此，答案为C。]
3.A　[本题考查双重循环和字符串的切片。i表示切片的开始位置，j表示切片的结束位置。]
4.C　[本题考查字符串处理。变量j表示出现相同字符的起点位置，变量i表示结束位置后面第1个位置，s[i]＝＝s[i－1]表示有多个重复，s[j]＝＝s[i]表示单个，不重复。d表示重复的长度，由于一个点的像素，长度为24个二进制位，当d>16条件成立时，d∥16－1的值为0。字符串中包含4个1，19个0和1个1。]
5.B　[本题考查字符串的切片。s2的值从″bccdef″、″ccddef″变化到″cdddef″。]
6.D　[本题主要考查字符串的处理，即字符的比较和字符的删除操作。变量s从″aabbcc″变化到″aabcc″。]
7.D　[变量t的值依次为5，3，9，7，对应s[t]的值依次为B、C、D、E。当i的值为6时，s[i]的值为0，结束循环。]
8.D　[本题考查字符串操作。①语句result＝result＋s[i]＋″－″是连接首字母，接着flag为True，因此flag表示是否找到起点，该空表示的是连续升序且为起点。②循环的条件for i in range(0，k－1)，只处理前k－1个字符，最后一个字符没有处理。]
9.①n %i＝＝0　②s[j：j＋i]！＝s[：i]
解析　本题考查双重遍历的算法思想。一个原始字符串反复重叠，该原始字符串长度必定能被n整除，条件n %i＝＝0成立表示该长度i是n的因子，可能是原始字符串s[：i＋1]的长度，字符串s从第0个位置开始，到i－1位置是原始字符串，从i开始，每i个长度的字符串s[j：j＋i]是否是原始字符串，如果不是说明这段中不符合原始字符串。
10.D　[本题考查range函数的使用以及程序基本代码的阅读能力。根据range函数的参数，是从字符串s中从索引0开始，依次取出下标为0、3、6……位置的字符，如果字符是小写，将它转为大写，并按逆序依次拼接。答案为D。]
11.D　[本题考查程序结构的灵活应用。程序算法为：依次从左向右提取s中每一个字符，如果与b[k]中字符不一致，则将该字符存储到b[k＋1]中，如果一致，则k＝k－1。]
12.(1)是　(2)①s＝s＋i　②i＋＝1　③c1＝＝″？″ or c2＝＝″？″
解析　本题主要考查字符串的综合应用。(1)依照题意，‘？’作为万能字符与任意字符相等，问题中的两个字符串依次比较是相等的。
(2)填空①处实现去掉字符串s1的空格，所以遍历字符串时为非空格的时候，进行字符的连接，因此①处答案是s＝s＋i；填空②处当遍历至相同位置的字符相等时，则进行下一个位置的字符比较，因此②处答案是i＋＝1；填空③处当两个相同位置的字符不相等时，则考虑“？”作为万能字符情况，因此③处答案是c1＝＝″？″ or c2＝＝″？″。
13.(1)KvjyDvvr　(2)①ek.append(ord(c)－ord(″a″))　②i%len(keyn)　③chr(ord(s[i])－ord(″a″)＋k)%26＋ord(″a″))　(3)变量result没有赋初始值
解析　本题主要考查字符串的综合应用。(1)根据表中提供数据，密钥LOVE对应的偏移量分别是11，14，21，17，可得ZhouShan的密文是KvjyDvvr；
(2)①自定义函数change(x)将密钥字符转成对应的偏移量，结果存放在数组ek中，根据表中字母对应的偏移量，所以此处应填ek.append(ord(c)－ord(″a″))；
②遍历明文字符应取密钥列表中的每一个偏移量，由于密钥长度可能小于明文长度，需循环使用，所以此处应填i%len(keyn)；③将原字符的字母按照密钥的偏移值进行位移，由于需在字母范围内进行循环位移，因此此处答案为chr(ord(s[i]－ord(″a″)＋k)%26＋ord(″a″))；
(3)在python中变量没有赋初始值，表示没有定义。
14.(1)6　 (2)①s[i]＝ord(text[i])－97或s[i]＝ord(text[i])－ord(″a″)　② k>＝26　或 k＝＝26　③f[s[pos]]＝＝0
解析　本题主要考查字符串的综合应用。(1)包括字母“abcdef”的最短字符串为“abcfde”，长度为6。(2)①处代码表示求每个输入的小写字母在字母表中的位置，其中字母“a”的位置为0，其他字母依次类推，因此①处代码为s[i]＝ord(text[i])－ord(″a″)，小写字母a的ASCII为97，故也可以写为s[i]＝ord(text[i])－97；②处代码表示当前字符串已包含26个字母时的处理， 变量k表示字母的种类数，如果字符串中已包含26个字母，则进行优化处理，看能否调整字符串的左边界，因此②处代码为k>＝26或 k＝＝26；③处代码表示条件左边界不能再调整的情况，表示该子串不可再缩短，因此③处代码为f[s[pos]]＝＝0。课时2　队　列
一、基础巩固
1.下列有关队列的说法正确的是(　　)
A.队列是一种先进先出的线性表，插入一端为队首，删除一端称队尾
B.队列的存储结构，可用数组实现，也可用链表实现
C.一队列队头指针head，队尾指针tail，则tail－1－head表示队列中元素个数
D.学生排队就餐与软件连续撤消操作都是数据结构“队列”的应用实例
2.有1个队列，现有元素依次为1，2，3，4。约定：P操作是指1个入队，T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过PPTQTPQ系列操作后，队列中队首到队尾的元素依次为(　　)
A.1 B.1，3 C.3，4 D.3
3.创建一个容量为 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
4.某种特殊的队列 Q，支持以下3个操作：操作Q1，若队列非空，队首元素出队，并输出；操作Q2，若队列非空，队首元素出队；操作Q3，一个元素入队；以上任意一种操作后，若队列非空，新的队首元素仍为队列中所有元素的最小值。若队列 Q 初始状态为空，依次进行 Q3、Q2、Q1、Q2、Q3、Q1、Q3 七次操作后，下列说法正确的是(　　)
A.当前队列中的元素个数为 2
B.输出的元素个数为 2
C.第一个输出的元素肯定比当前队首元素大
D.队列初始状态是否为空对输出结果有影响
5.假设队列空间足够，队列中的元素个数为 5。约定：T 为入队操作，Q 为出队操作，则经过 TTQQTQTQQ一系列操作之后，队首指针 head，队尾指针 tail 的值可能为(　　)
A.head＝11，tail＝7 B.head＝7，tail＝11
C.head＝9，tail＝12 D.head＝12，tail＝9
6.列表q长度为20，q[0]到q[7]的值依次为'a'，'b'，'c'，'a'，'c'，'d'，'d'，'e'，执行如下程序段后，输出的结果为(　　)
head＝tail＝0
for i in range(8)：
if q[i]＝＝q[head] and head！＝tail:
　 tail＋＝1
　 head＝tail
else：
　　tail＋＝1
print(q[head：tail])
A.cdde B.acdde C.eddc D.e
7.有如下程序段：
m＝3；n＝7
head＝tail＝0；ans＝0
vis＝[0]*10；q＝[0]*10
for i in range(n)：
　x＝int(input())
　 if (vis[x]＝＝0):
　 ans＋＝1
　if (tail－head>＝m):
　　　vis[q[head]]＝0
　 　　head＋＝1
　 q[tail]＝x
　 tail＋＝1
　vis[x]＝1
print(ans)
运行该程序段，依次输入x的值：1，2，1，5，4，4，1。则程序运行完成后ans的值是(　　)
A.3 B.4 C.5 D.6
8.执行如下程序段后，输出的结果是(　　)
q＝[6，8，9，7，4，5，2，3]
pre＝10
head，tail＝0，len(q)
while head！＝tail：
　if pre>q[head]:
pre＝q[head]
print(q[head]，end＝' ')
head＋＝1
A.6 8 9 B.6 4 2 C.6 5 3 D.6
9.有如下Python程序段：
a＝[3，6，10，5，9，4]
q＝[0]*len(a)
k＝int(input(″输入k的值：″))
head＝tail＝0
s＝ans＝0
for i in a：
　 q[tail]＝i
　 tail＝tail＋1
　s＋＝i
　if ansans＝s
　while ik：
s－＝q[head]
head＝head＋1
执行该程序段后，输入k的值为2，变量ans的值是(　　)
A.18 B.19 C.21 D.22
二、能力提升
10.有如下Python程序段：
Q＝[0]*10
cnt，head，tail＝0，0，0
S＝input()
for i in range(0，9，2)：
　 t＝S[i]
　n＝int(S[i＋1])
　if t＝＝'A'：
　 for j in range(n)：
　　　 Q[tail]＝cnt
　 　　tail＋＝1
　　 　cnt＋＝1
elif t＝＝″D″：
　while head！＝tail and n>0：
　　 head＋＝1
　　 n－＝1
print(Q[head : tail])
若输入S的值为″A2D1A1D3A2″，则程序的输出结果是 (　　)
A.[3，4，5] B.[3，4] C.[4，5] D.[4]
11.有如下程序段：
s＝input()
head＝0; tail＝0; ans＝0; tmp＝″
q＝[″]*100
flag＝True
for i in range(len(s))：
　　　if s[i]＝＝'，':
while head！＝tail：
　　　tmp＋＝q[head]
　　　head＋＝1
　　　if flag and head　　　　　　head＋＝1
　　　flag＝not flag
　ans＋＝int(tmp)
　tmp＝″； flag＝True
　elif '0'<＝s[i]<＝'9'：
　q[tail]＝s[i]
　tail＋＝1
若输入s为“1－500，2023900－，”，执行该程序段，变量ans的值为(　　)
A.100 B.22300 C.22351 D.22400
12.某市举办科技嘉年华活动，为了激发学生的参与积极性，举办方推出了玩游戏得积分，积分兑换礼物的活动。活动中游戏分为简单和困难两种，参与游戏就可以获得相应的积分，当完成困难游戏时，除了获得相应积分外，还可获得一张“积分翻倍卡”，一张“积分翻倍卡”可用于一个简单游戏，使简单游戏的积分翻倍。
“积分翻倍卡”使用规则如下：
1)当简单游戏开始时，如果有“积分翻倍卡”可用，则一定会使用。
2)“积分翻倍卡”需在15分钟内使用。比如困难游戏完成时间是9：15分，则获得的“积分翻倍卡”将在9：15分激活，且超过9：30分将失效。
3)如果有多张“积分翻倍卡”，则优先使用最早的“积分翻倍卡”。
某同学的游戏记录如图a所示(类型0表示困难游戏，类型1表示简单游戏)，小明读取游戏记录，编写Python程序计算出该同学游戏的最终得分。程序运行结果如图b 所示，请回答下列问题：
序号 类型 积分 开始时间 完成时间
1 0 10 9：10 9：15
2 1 3 9：15 9：28
3 1 5 9：38 9：42
4 0 12 9：58 10：05
5 1 3 10：20 10：36
6 0 15 10：48 10：55
7 1 3 11：25 11：29
图a
(1)若某同学参加游戏的记录如图c所示，则他获得的积分是________分。
(2)定义如下函数 change(t)，参数t为游戏时间，函数功能是将时间t转换为分钟并返回。如：t＝″9：20″时，转换为整数(分钟)值是560，函数返回值为560。
函数代码如下，请在划线处填入合适的语句。
def change(t): #参数t的时间格式为：″小时：分钟″
m＝t.split(″：″)　　
s＝____________
return s
(3)计算游戏积分的部分Python程序如下，请在划线处填入合适的代码。
从Excel文件中读取游戏过程记录，存储在列表s 中，如s＝[[1，0，10，550，565]，[2，1，3，565，568]，...]，s[i]表示第i个游戏记录，s[i][0]，s[i][1]，s[i][2]，s[i][3]，s[i][4]依次存储游戏的序号、类型、积分、开始时间，完成时间；当游戏类型s[i][1]值为日时表示困难游戏，为1则表示简单游戏；
将困难游戏取出存入列表a中，列表 a按游戏完成时间升序排序；
将简单游戏取出存入列表b中，列表b按游戏开始时间升序排序，代码略
que＝[－1]*(len(a)＋len(b)＋1)
head＝tail＝0
total＝0
for i in range(len(a)): #累加游戏积分，将“积分翻倍卡”激活时间加入队列
total＋＝a[i][2]
①____________
tail＋＝1
for i in range(len(b)) ：
　 while head　 print(que[head]∥60，″： ″，que[head] % 60，″时刻生效的″＋″积分翻倍卡过期；″)
　 head＋＝1
　　if head　 print(b[i][3]∥60，″：″，b[i][3]%60，″时刻使用了积分翻倍卡；″)
　③____________
　head＋＝1
　　else：
　total＋＝b[i][2]
print(″总共获得积分为： ″，total，″分，″，″剩余积分卡有： ″，tail－head，″张。″)
13.某文本编辑软件可以把所做的文本编辑操作记录下来，并通过撤销和恢复命令来撤销一步操作或恢复一步撤销的操作，也可以通过数字命令一次性撤销最近的多步文本编辑操作，如图所示。
设计算法模拟该功能。约定：①操作记录只存储文本编辑指令；②存储步数最多为 5步，存满后早期的操作记录将被覆盖；③程序只显示操作记录的可“撤销”记录，可 “恢复”记录不显示；④一旦有新的文本编辑操作，则清空所有可“恢复”记录。
人机交互的指令如下(所有操作示例都基于上一个示例结果继续操作)：
类型 指令 示例 程序输出结果
文本 编辑 “T1”、“T2”、“T3”、“T4”表示四种文本编辑操作 对文本依次做“ T1 ” 、 “T2”、“T3”、“T4” 操作后，再输入指令“T2” 请输入操作指令：T2 指令B可用：指令F不可用 可撤销记录：T1/T2/T3/T4/T2/
撤销 “B”表示撤销 1 步操作 输入“B” 结果：撤销最近一步操作 “T2” 请输入操作指令：B 指令B可用：指令F可用 可撤销记录：T1/T2/T3/T4/
数字“1”～“5”表示撤销多步操作 输入“3” 结果：撤销最近 3 步操作 “T4”、“T3”和“T2” 请输入操作指令：3 指令B可用：指令F可用 可撤销记录：T1/
恢复 “F”表示恢复 1 步撤销的文本编辑操作 输入“F” 结果：恢复最近的 1 步文本编辑操作“T2” 请输入操作指令：F 指令B可用；指令F可用 可撤销记录：T1/T2/
文本 编辑 在撤销或恢复操作之后继续新的文本编辑操作 输入“T1” 结果： 可“ 恢复” 记录 “T3”、“T4”、“T2” 被清空 请输入操作指令：T1 指令B可用；指令F不可用 可撤销记录：T1/T2/T1/
所有指令均可使用多次。每次输入一个指令后都输出“F”指令和“B”指令是否可用以及当前可撤销记录。所有无效操作指令输入后均提示“Input Error！”。输入“#”则结束程序。请回答下列问题：
(1)由题意可知，当依次执行指令“T2”、“T2”、“T1”、“T3”、“T1”、“T4”，则最终可撤销记录共有__________个。
(2)模拟实现该功能的 Python 代码如下，请在划线处填入合适的代码。
def printh(head，cur)：
　print(f[flag[0]*2＋flag[1]])
　 s＝″可撤销记录：″
　 while head！＝cur＋1:
　s＝s＋hist[head]＋″/″
　①____________
　print(s)
opera＝[″T1″，″T2″，″T3″，″T4″]
f＝{0：″指令 B 不可用；指令 F 不可用″，1：″指令 B 不可用；指令 F 可用″，2：″指令 B 可用；指令 F 不可用″，3：″指令 B 可用；指令 F 可用″}
maxn＝5 #历史记录最多存储的步数
maxsize＝100 #设定最多输入文本编辑指令 100 次
hist＝[″″]*maxsize
cur＝－1；tail＝0；head＝0
flag＝[0，0] #记录指令 B 与指令 F 的状态
while True：
　d＝input(″请输入操作指令：″)
　if d＝＝″#″： break
　if d in opera：
　if ②____________：
　　　head＝head＋1
　cur＝cur＋1；hist[cur]＝d
　tail＝cur＋1
　flag＝[1，0]
　printh(head，cur)
　　elif ″1″<＝d<＝str((cur－head＋1)):
　 cur＝③____________
　if cur＝＝head－1:
　　　flag[0]＝0
　flag[1]＝1
printh(head，cur)
　　elif d＝＝″F ″and tail！＝cur＋1:
　#恢复功能代码略
　　elif
　if cur＝＝head：
　　　flag[0]＝0
　flag[1]＝1
cur＝cur－1
　printh(head，cur)
　else：
　print(″Input Error! ″)
(3)若加框处代码误写为“d＝＝″B″”，会导致某些情况下无法得到符合判断功能的结果。下列 4 组数据中能测试出这一问题的是__________(多选，填字母)
选项 依次输入下列操作指令
A “B”
B “T1”、“B”、“B”
C “T1”、“1”、“B”
D “T1”、“T2”、“B”
课时2　队　列
1.B　[本题考查队列的性质。A选项队列在队尾插入，在队首删除；C选项队尾指针tail指向队尾元素的下一个位置，所以tail－head表示队列中元素个数；D选项软件连续撤销操作是撤销前一步操作，是栈的应用实例。]
2.D　[元素1，2入队，1出队后入队，队列为2，1。2出队，1出队后入队，3入队，1出队，因此队列中只有元素3。]
3.D　[本题考查队列性质。2，3，5入队，队满。2出队，1入队，队列为3，5，1；3和5在队列中，跳过该元素。3出队，才能让2入队，队列中元素为5，1，2。]
4.D　[操作Q3、Q2之后，队列为空。Q3、Q1，队列为空。因此队列中元素个数为1，Q1操作出队并输出元素，输出的元素个数为1。C选项没有可比性。D选项若队列不为空，则Q3、Q2、Q1、Q2输出的结果不一样。]
5.B　[本题考查队列基本操作。经过4次入队，5次出队，因此队列中共有4个元素。由于队列空间足够，因此队尾指针大于队首指针。A选项队尾应大于队首。B选项队列中元素个数为11－7＝4，符合题目要求。C选项队尾应大于队首。D选项队列中元素个数为12－9＝3，不符合题目要求。]
6.A　[分析程序段可知，该程序段实现的是一种消消乐游戏，即若新遍历到的元素和队首的元素不同或者队列为空，则将新元素入队。若新遍历到的元素和队首的元素相同，则将所有队列中的元素清空。因此队列中最后剩余的元素为 c，d，d，e。]
7.C　[本题考查队列的算法实现。vis是一个标志数组，当其元素值为0时，可以入队，保证队列中数据是唯一的。当队列中元素个数大于等于3时，将进行出队操作。ans统计入队次数。输入x的值1，2入队，接着1不能入队，5入队，当输入4时，让1出队，4入队。第2个4不能入队，最后一个1入队。]
8.B　[本题考查队列的基本操作。程序的功能是查找队列中最小值，pre初值为10，每次出队一个元素，出队元素与pre比较，记录其最小值的过程。]
9.C　[遍历数组a并累加数组元素值，求队列的最大值；当遍历到的当前值小于队首或是长度大于k，将队首元素出队。s的值依次为[3，6，10]＝19，[6，10，5]＝21，[5，9]＝14，[5，9，4]＝18。]
10.B　[本题考查队列的入队与出队操作。字符串S中两个字符为一组，第1个元素t代表入队或出队，第2个元素代表n入队或出队的次数。A是入队，D是出队，若出队过程中队空，则中止出队。]
11.D　[本题考查队列的程序实现。在for循环中，当s[i]的值为数字字符时，将s[i]放入队列中；当s[i]为’，’时，将队列中的字符出队并连接。当flag为True时，字符出队但不连接到tmp中；其余字符忽略不处理。因此当输入的字符串为“1－500，2023900－，”时，遇到第一个’，’字符，则ans加上100，然后再对于进入队列中的字符串“2023900”进行计算，故最后的结果为22400。]
12.(1)40　(2)int(m[0])*60＋int(m[1])　(3)①que[tail]＝a[i][4]　②que[head]＋15解析　本题考查队列的基本操作。(1)完成困难游戏获得积分翻倍卡，一张积分翻倍卡使简单游戏的积分翻倍，但积分卡在15分钟内有效，14：47激活卡，15：10已经过期。积分为10＋5*2＋15＋5。(2)将时间按冒号分隔，得到一个列表，列表中有两个值，分别为m[0]和m[1]。(3)①将积分卡激活时间加入队列，困难游戏完成时间就是卡激活时间。②遍历列表b，简单游戏一开始就可以使用翻倍卡，因此计算翻倍卡的激活时间与当前简单游戏开始时间的时间差，该时间差大于15分钟时，卡失效。③使用翻倍卡，积分将翻倍。
13.(1)5　(2)① head＋＝1　②cur－head＋1＝＝maxn或tail＝＝cur＋l and tail－head＝＝maxn　③cur－int(d)　(3)ABC
解析　本题考查队列的基本操作。(1)存储步数最多为 5步，存满后早期的操作记录将被覆盖。(2)①head表示队首，cur表示最后一个元素指针，每输出一个元素，就要出队。②当d是文本编辑指令时，存储步数最多为 5步，超出队首元素将不能撤消。cur初值为－1，一个元素入队后，值为0，因此cur表示列队中最后一个元素，因此队列总共元素个数为cur＋1－head。③当d为撤消步数时，cur表示撤消后的元素位置，因此cur将减去int(d)的值。(3)A选项cur小于head无法输出。B选项撤消一步后，效果同A。C选项1表示撤消一步，效果同B。D选项有两个元素，可以输出。课时3　栈
一、基础巩固
1.栈s的最大长度为4，初始已有两个元素在栈内，栈底为a，栈顶为b，经过一系列入栈、出栈操作，若元素入栈的顺序是c，d，e，f，则可能的出栈序列为(　　)
A.c，a，b，e，f，d B.b，d，f，e，c，a
C.a，b，d，c，e，f D.b，e，f，c，d，a
2.有一个队列和一个栈，其中队列中队首到队尾的元素依次为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
3.用“除二取余”法将十进制转换为二进制数，用栈的方法操作，需要把得到的余数依次入栈，除尽后再把余数出栈即可。若要将十进制数n(0≤n<64)转换为二进制数，则设置栈的长度至少为(　　)
A.3 B.4 C.5 D.6
4.已知栈k的入栈顺序为2，7，3，1，6，9，第2个出栈的是6，第5个出栈的是2，则最后出栈的元素是(　　)
A.7 B.3 C.1 D.9
5.已知字符“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']
6.用栈的思想编写进制转换中的“除二取余法”的Python程序如下：
st＝[－1]*100
top＝－1
n＝int(input(″请输入一个十进制数″))
while n>0：
n∥＝2
while top！＝－1：
　　print(st[top]，end＝″″)
　　top－＝1
方框处的代码由以下三条语句组成：①st[top]＝x　②x＝n%2　③top＋＝1下列语句顺序正确的是(　　)
A.①②③ B.①③② C.②①③ D.②③①
7.有如下Python程序段：
s＝input(″请输入一个仅由小写英文字母组成的字符串：″)
st＝[″″]*len(s)
top＝－1
t＝[－1]*26
for i in range(len(s)):
　id＝ord(s[i])－97
　 if t[id]＝＝－1：
　top＋＝1
　st[top]＝s[i]
　t[id]＝top
　else：
　 first＝t[id]
　while top>＝first and top！＝－1:
　　num＝ord(st[top])－97
　　t[num]＝－1; top－＝1
print(st[：top＋1])
若从键盘输入的值为″hellopython″，则输出的值为(　　)
A.['o'，'n']
B.['h'，'e'，'n']
C.['h'，'e'，'l'，'o'，'p'，'y'，'t'，'n']
D.['h'，'e'，'o'，'p'，'y'，'t'，'h'，'o'，'n']
8.有如下Python程序段：
import random
s＝[3，2，7，6，9]
st＝[0]*len(s)
top＝－1；i＝0
while i　op＝random.randint(0，1)
　if top＝＝－1 or op＝＝0 and s[i]>st[top]：
　top＋＝1
　st[top]＝s[i]
　elif top>＝1 and op＝＝1 and s[i]>st[top－1]：
　st[top]＝s[i]
　i＋＝1
while top！＝－1：
　　　print(st[top]，end＝″ ″)
　　　top－＝1
执行该程序段后，输出的结果不可能是(　　)
A.3 B.9 6 2　 C.9 6 3 D.9 7 3
9.如下Python 程序段的功能是判断一个表达式中的括号(只有小括号)是否匹配，
exp＝input(″请输入表达式：″)
top＝－1；n＝len(exp)∥2；flag＝True
stack＝[″″]*n
for ch in exp:
　if ch＝＝″(″：
　 if ①____________：
　　　flag＝False；break
top＋＝1；stack[top]＝″(″
　　elif ch＝＝″)″：
　if top<0：
　　　　flag＝False；break
top－＝1
if ②____________：
　print(″括号匹配″)
else：
　　print(″括号不匹配″)
则划线处应填入的代码是(　　)
A.① top>＝n ② flag and top＝＝0
B.① top＝＝n－1 ② flag and top＝＝0
C.① top>＝n ② flag and top＝＝－1
D.① top＝＝n－1 ② flag and top＝＝－1
二、能力提升
10.某栈入栈序列为“A、B、C、D、E”，若第一个出栈的元素为“C”，最后一个出栈的元素为“E”，则可能的出栈序列有(　　)
A.3种 B.4种 C.5种 D.6种
11.有如下 Python 程序：
s1＝[0]*5; s2＝[0]*5; top1＝－1；top2＝－1
a＝[9，2，5，6，1]
for i in range (len(a))：
　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
print (s1[top1])
执行程序后的输出结果是(　　)
A.1 B.5 C.6 D.9
12.有如下 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']
13.有如下 Python 程序段：
a＝{'<'：0，'('：1，'['：2，'{'：3，'>'：4，')'：5，']'：6，
'}'：7}
s1＝input()
s＝[8，0，0，0，0，0，0，0，0]
top＝0；flag＝True
for x in s1：
　 k＝a[x]
　if k<4：
if s[top]　　 flag＝False
　　　break
top＋＝1
s[top]＝k
else：
if s[top]！＝k－4:
　　　flag＝False
　　　break
top－＝1
if flag and top＝＝0:
　print(″YES″)
else：
　　　print(″NO″)
若输出结果为“NO”，则 s1 输入的值是(　　)
A.{}[]()<> B.[()]{<>} C.{[<()>]} D.{()[<>]}
14.有如下Python程序段：
import random
s＝″Happy″
stk＝[″″]*len(s)；top＝－1
i＝0；res＝″″
while i　 if random.randint(0，1)＝＝0 or top＝＝－1：
　top＋＝1；stk[top]＝s[i]
　elif s[i]>stk[top]：
　res＋＝stk[top]；top－＝1
　i－＝1
　i＋＝1
while top>＝0：
　res＋＝stk[top]；top－＝1
print(res)
执行该程序段后，res的值不可能是(　　)
A.″Hpapy″ B.″Happy″ C.″yppaH″ D.″Hpay″
15.判断某序列b是否是入栈序列a＝[1，2，3，4，5]的出栈序列，程序如下：
a＝[1，2，3，4，5]
b＝list(map(int，input().split()))
stack＝[]
i＝j＝0
while i　 stack.append(①____________)
　 i＋＝1
　 while len(stack)>0 and ②____________：
　stack.pop()
　j＋＝1
if len(stack)＝＝0 and j＝＝len(a):
　print(b，'是'，a，'的出栈序列')
else：
　　print(b，'不是'，a，'的出栈序列')
划线处应填写的语句是(　　)
A.①a[i]　②stack[－1]＝＝a[j]
B.①a[i]　②stack[－1]＝＝b[j]
C.①b[i]　②stack[－1]＝＝b[i]
D.①b[i]　②stack[－1]＝＝a[j]
16.自从学习了不同进制之后，小明设计了一个计算不同进制数的加法器，并用Python编程实现。输入一个加法算式，加数可以是十进制数、二进制数或者十六进制数，程序的功能是输出它们的和。例如输入形如“1010B＋1DH＋109D＝”的加法算式后，执行程序输出“和是148”的结果。Python程序如下：
s＝input('输入一个混合进制的加法算式：')
dic＝{'B'：2，'D'：10，'H'：16}
st＝[″]*100
top，i，x，m＝－1，0，0，0
while i　　　if s[i]＝＝'＋' or s[i]＝＝'＝'：
　　　 m＝①____________
　　　top＝top－1
　　　t＝0
　　　while top！＝－1：
　　　if st[top]>＝'A' and st[top]<＝'F'：
　　　　　　　st[top]＝ord(st[top])－ord('A')＋10
　　　else：
　　　　　　st[top]＝int(st[top])
　　　②____________
　　　t＝t＋1
　　　top＝top－1
　else：
　　　③____________
　　　st[top]＝s[i]
　i＝i＋1
print('和是'，x)
(1)将划线处代码补充完整。
(2)若输入”101B＋DH＋100D”，输出的结果是________。
17.某种密码设计方法如下：给定两个数组，数组元素由数字 1～9 组成，从中选出 k(k 小于等于两个数组长度之和)个数字拼接成一个新的数，同一数组中取出的数字保持其在原数组中的相对顺序，每个数组中至少有 1 个数被选中，满足该条件的最大数即为密码，程序运行界面如图所示。
请输入数组1：3　4　6　5　7　8 请输入数组2：9　1　2　5　8　3　4 请输入k：6 密码为：987834
请回答下列问题：
(1)程序部分代码如下，请在划线处填入正确的代码。
def select_num(nums，k):
　stack＝[0]*len(nums)；top＝－1；cnt＝len(nums)－k
　for num in nums:
　 while cnt>0 and top！＝－1 and stack[top]　　　top－＝1；cnt－＝1
　top＋＝1
　①____________
　while cnt>0：
　 top－＝1；cnt－＝1
　return stack[0：top＋1]
def merge(a，b)：
　　c＝″；i＝0；j＝0
　　while ：
if j＝＝len(b) or i＝b[j]:
　　　　 c＋＝str(a[i])；i＋＝1
elif i＝＝len(a) or j　　　　　c＋＝str(b[j])；j＋＝1
　　return int(c)
num1＝input(″请输入数组 1：″)
num2＝input(″请输入数组 2：″)
num1＝list(map(int，num1.split(″ ″)))
num2＝list(map(int，num2.split(″ ″)))
k＝int(input(″请输入 k：″))
②____________
for i in range(1，k):
　a＝select_num(num1，i)
　③____________
　c＝merge(a，b)
　if c>m：
m＝c
print(″密码为：″＋str(m))
(2)加框处的程序代码有误，请改正。
课时3　栈
1.B　[A选项和C选项都出现了 a 在 b 前面出栈的情况，因此选项错误；D选项f 出栈时栈内的元素为(栈底)c，d(栈顶)，因此不可能 c 出栈，选项错误。]
2.A　[队列特征为先进先出，有4次出队，因此队列中3，15，8，7全部出队。Q出栈入队，因此6先入队，15和3在栈中，接着15入队，8出队入栈，因此后面是8和3。]
3.D　[十进制数n(0≤n＜64)转换为二进制数，得到最大的是6位二进制数。]
4.D　[2是第1个入栈，当2出栈时，栈为空，只有9入栈再出栈。]
5. A　[第1个循环让abc依次入队。当队列和栈不为空时，如果栈顶元素和队首元素相同，则进行出队和出栈操作，否则将栈顶元素出栈并入队。栈顶和队首均为″a″，出队和出栈操作，接着″d″入队，″d″出栈，接着″c″入队，″c″出栈，队列中元素为″bcdc″，接着″b″出队和出栈。]
6.D　[入栈必先移动top指针，入栈元素为x，先对x进行除2的余数赋值。]
7.A　[遍历字符串s，将每个字母转换成0～25之间对应的数字。t列表是每个字母出现在栈中位置的桶。若字母不在栈中，将该字母入栈，同时记录该字母为当前栈顶位置。若该字母已经存在于栈中，将后入栈的字母进行出栈操作，并在桶中作－1的标记。最后一个h让前面所有字母出栈，因此栈中只有o和n。]
8.B　[本题考查栈的应用。当栈空入栈，因此3肯定在栈中。当op为0且s[i]>st[top]时，s[i]入栈，若产生op的值一直为1，则栈中只有3；入栈的元素比栈中元素大，2小于3，因此2不可能入栈，若7没有入栈，则6可能入栈。]
9.D　[本题考查栈的基本操作。n值为len(exp)∥2，如果是″(″，进行入栈操作，如果栈顶指针为n，若再入栈，则左括号超出总字符串长度的一半，说明左括号的数量大于右括号。否则进行出栈操作，一个右括号匹配一个左括号，若在出栈前，栈为空，说明左括号少了。遍历完后，用右括号对左括号进行出栈操作，如果栈为空，说明两者数量相等。]
10.A　[C要出栈，栈中有A和B，E最后一个出栈，因此E最后入栈并马上出栈，那么D可能在A前面，AB之间和B之后三个位置出栈。]
11.D　[本题考查栈的相关知识。若 a[i]12.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先出栈。]
13.C　[本题考查栈的操作。遍历字符串s1并取出在字典中的值k，如果是符号的左半部分，并且栈顶元素大于等于k，将k值入栈。若k大于等于4，且栈顶元素等于k－4，出栈一个元素。当flag为True且栈中只剩下一个元素，输出YES，否则输出NO。A选项{在字典中键值为3，入栈，}在字典中键值为7，满足条件栈顶元素等于k－4，让栈顶元素出栈，其他符号均成对，相同方法处理。B选项[和(对应的键值分别为2和1，2入栈后，1小于栈顶2，1也入栈，接着)和]让1和2依次出栈。{键值大于<键值，相同方法处理。C选项<和(对应的键值分别为0和1，当遍历到(时s[top]14.A　[分为产生随机数为0、随机数为1且s[i]>stk[top]和随机数为1且s[i]<＝stk[top]三种情况，在第2种情况中，让较小的元素先出栈，同时i减1。第3种情况既不入栈，也不出栈，因此s中可能有部分元素未入栈。B选项H入栈，a让H先出栈，a入栈，p让a入栈，p和p均入栈，y分两种让两个p出栈，最后在while结构中y出栈。C选项产生的随机数均为0。D选项a让H出栈，a入栈，随机数为0，p入栈，第2个p随机数为1，不入栈。y让p和a出栈。A选项a不可能让p出栈。]
15.B　[本题考查栈的操作与程序实现。由第6行的添加操作和第9行的删除操作可以判断stack用于存储栈元素。可以通过将a元素不断入栈，看能否形成和b一样的出栈序列。第①空应该让a中的元素入栈，填写a[i]。而出栈时，需要判定栈顶元素是否和b序列中当前元素是否一致，一致才能出栈，尽可能形成与b一样的序列。]
16.(1)①dic[st[top]]　 ②x＝x＋st[top]*m**t　 ③ top＝top＋1　(2)118
解析　程序可知st列表中保存着当前加数的每一位。如对于式子“1010B＋1DH＋109D＝”，当读到第一个加号时，st列表的值为[‘1’，‘0’，’1’，’0’，’B’]，读到第二加号时，st的值是[‘1’，‘D’，‘H’]，读到最后’＝’号时，st的值是[‘1’，‘0’，‘9’，‘D’]。①st列表的最后一位是进制编号，读取st最后一位，通过字典dic得到进制值。②使用权值法把st列表中保存的进制数转化为十进制数。③读取到加数的每一位数字，都保存在st列表中的相应位置。(2)由于式子中的最后一位不是’＋’或者’＝’， 所以st列表中的最后一个数字没有加上。
17.(1)①stack[top]＝num　②m＝0　③b＝select_num(num2，k－i)　(2)i解析　本题考查栈和数据的归并。(1)①函数select_num的功能是在数字串nums取出的数字位置不变的k个长度子串。cnt初值为len(nums)－k，即需要去除的数字个数，遍历数字串nums并将数字入栈，若当前的数字比栈顶数字大，则需将栈中数字出栈，让栈中形成一个递减的系列，每出栈一个cnt减1，当cnt值为0时，则不再出栈。②对m赋初值0。③主程序外循环i的值从1循环到k，采用枚举的思想，分别从一个数组num1中选出1到k－1个数字，则从另一个数组2中选出k－1到1个数字，所以第③空应填入b＝select_num(num2，k－i)。(2)自定义函数merge(a，b)用于将a、b两个数组的值合并按顺序合并成最大数，变量 i、j分别指向ab两个数组中待合并区间的初始位置，根据if j＝＝len(b) or i＝b[j]可知当只剩下a列表中的数据未处理或者a数组的值大于b数组的值则c＋＝a[i]，否则当 i＝＝len(a) or j

展开更多......

收起↑