资源简介

(共55张PPT)
第三章　字符串、队列和栈
验收卷(二)　字符串、队列和栈
(考试时间40分钟　满分50分)
一、选择题(本题共12小题，每小题2分，共24分)
1.有如下Python程序段：
count＝0
st＝list(″Python″)
s＝″″
for i in st：
s＝i＋s
count＋＝1
print(count，s)
程序段执行后，输出的结果是(　　)
A.5 Python B.6 Python
C.6 nohtyP D.6 'nohtyP'
解析　本题主要考查的是字符串操作。本题的功能是统计循环的次数及将列表st中的字符进行反向拼接，列表中共有6个元素，因此循环次数为6，将列表st中的字符进行反向拼接后的结果为'nohtyP'，print输出时字符串内容没有引号，因此，答案为C。
C
2.有如下Python程序段：
s＝input(″输入一个字符串″)
a＝[″″]*6；t＝0
a[0]＝s[0]
for i in range(1，len(s))：
if t>＝0 and s[i]＝＝a[t]：
t＝t－1
else：
t＋＝1
a[t]＝s[i]
print(t)
C
运行程序段，输入以下字符串，运行后变量 t 的值与其它三项不同的是(　　)
A.AABAB B.AAABA C.BAABA D.BBABA
解析　本题考查字符串操作的相关知识。观察代码，t 初值为 0，a[t]为第 1 个字符，从第 2 个字符开始判断： 若与 a(t)相同且 t>＝0，则 t＝t－1；若与 a(t)不同或 t<0，则 t＝t＋1，a(t)跟踪新字符依据算法，ABD选项 t 值变化：－1，0，1，2，而C选项t 值变化：1，0，－1，0，可见 C 选项与其余三项不同，选 C。
3.输入一个数字字符串 s，输出删除其中 k 个数字字符，并且数字的次序不能交换，输出删除后的最大数字字符串。如：输入数字字符串“38726”，若 k＝1，则删除其中 1 个数字字符后的最大数字字符串是“8726”，若k＝3，则删除其中 3 个数字字符后的最大数字字符串是“87”。实现上述功能的Python程序段如下：
s＝input(″请输入数字串″)
k＝int(input(″请输入要删除的数字个数″))
while k>0：
i＝0
while is[i＋1]：
i＋＝1
A
k－＝1
print(s)
上述程序段中加框处可选语句为：①s＝s[i＋1：]　②s＝s[i＋1：len(s)－1]　③s＝s[：i]＋s[i＋1：len(s)－1]　④s＝s[：i]＋s[i＋1：]
则(1)(2)处语句依次是(　　)
A.①④ B.③② C.③④ D.①②
解析　本题考查程序代码的阅读理解能力，以及字符串相关函数的书写。删掉某个位置上的数字，使得剩下的数字构成的数最大。简单的思路就是，从前往后找。发现某个数字比后面的数字小，将这个数字删除即可。如果没有这样的情况，将最后的那个删掉即可。
D
4.队列Q从队首到队尾的元素依次是1，3，5，栈S从栈底到栈顶的元素依次是2，4，6，现约定：A操作是指元素出队后入栈，B操作是指元素出栈后入队。经过BAAB系列操作后，队列中队首到队尾的元素依次为(　　)
A.5，2，1 B.5，2，4 C.5，6，1 D.5，6，3
解析　6出栈后入队，1和3出队后入栈，3出栈后入队，因此队列中有原来的5和入队后的6、3。
5.某Python程序如下：
q＝[″″]*50
head＝tail＝0
s＝″ningbo″
for i in s：
　q[tail]＝i
　tail＋＝1
while head　 print(q[head]，end＝″″)
A
　head＋＝1
　for i in range(3)：
　 q[tail]＝q[head]
　head＋＝1
　tail＋＝1
执行该程序段后，输出结果为(　　)
A.nbgoni B.nbogni C.goninb D.ningbo
解析　操作过程：队首出队，紧接着3个入队尾后出队，直至队列为空。ningbo→boing→goin→oin→ni→i。
6.有如下Python程序：
a＝[4，2，5，1，9]
que＝[0]*7
head，tail＝0，0
que[tail]＝a[0]
tail＋＝1
for i in range(1，len(a)):
　if a[i]>que[tail－1]:
　 que[tail]＝a[i]
　tail＋＝1；head＋＝1
B
　elif a[i]　 que[tail]＝a[i]
　tail＋＝1
print(que[head：tail])
执行以上程序段后，输出结果是(　　)
A.4，7 B.5，1，9
C.2，5，1，9 D.4，7，2，5，1，9
解析　队列中初始1个元素，值为4。遍历列表a中位置1到len(a)－1的元素，若遍历的元素值比队尾元素大，则将队首出队后再将a[i]入队。若遍历的元素值小于队首，直接将a[i]入队。队列中元素变化情况为[4，2]、[2，5]、[2，5，1]、[5，1，9]。
7.有如下Python程序段：
a＝[2，4，5，10，8，13，11，7，2，6]
que＝[0]*len(a)
k＝int(input())
key＝int(input())
msq＝0；sq＝0
head，tail＝0，0
for i in a：
　 que[tail]＝i
　 sq＝sq＋i
　 tail＝tail＋1
　 while sq>key or tail－head>＝k：
　 sq＝sq－que[head]
head＝head＋1
　 if sq>msq：
　msq＝sq
若输入k的值为3、key的值为20，则程序运行后，变量msq的值为(　　)
A.18 B.19 C.20 D.21
A
解析　本题考查队列的操作。语句que[tail]＝i的功能是将数组a中数据依次入队，并将队列的数进行累加到sq中，当条件sq>key or tail－head>＝k时，依次出队，并在sq中减去队首的值，msq是出队后(队列中最多只包含k－1个元素)累加和的最大值。最大值为4＋5＝9、5＋10＝15、10＋8＝18、8＋13－8＝13(累加和大于20，还要出队)。
A
8.用>表示进栈操作，<表示出栈操作，若元素进栈的顺序为“＋/*\”，出栈顺序为“＋\〔%/”，则由>和<表示的操作串是(　　)
A.><>>><<><< B.><>><><<><
C.>>>><<><<< D.><>>>><<<<
解析　本题考查栈的操作。＋入后马上出，/*\\入，\〔出，栈中只有/，%入后马上出，/再出。
D
9.栈底至栈顶依次存放元素 A、B、C、D，在第五个元素E入栈前，栈中元素可能出栈，则 5 个元素全部出栈后，出栈的序列可能是(　　)
A.ABCED B.DBCEA C.CDABE D.DCBEA
解析　本题考查出入栈相关知识点。四个元素的出栈顺序是一定是DCBA。
10.有如下Python程序段：
w＝input()
flag＝True
st＝[″″]；top＝－1
c＝0
for i in w ：
　 if flag and i＝＝″(″：
　top＝top＋1
　 st[top]＝i
　flag＝False
　 elif not flag and i＝＝″)″：
　top＝top－1
　c＝c＋1
　flag＝True
print(c)
若输入w的值为″()()(()()))″，则以上程序运行后，输出结果为(　　)
A.6 B.3 C.4 D.5
C
解析　本题考查栈的操作。当读取到″(″进行入栈操作，并且flag值为False；当栈不为空，且读取到″)″时，进行出栈操作。前面2对括号依次入栈出栈，c为2。连续读取2个左括号，第2个左括号时，flag值为False，只有一个括号入栈。2对括号依次入栈出栈。读取最后两个右括号时，栈中无元素，不能出栈操作。
11.有如下 Python 程序段：
s＝[0]*10；q＝[0]*10
a＝[6，3，2，4，2，1，5]
n，top，head，tail＝len(a)，0，0，0
s[top]＝a[0]
for i in range(1，n)：
　 while top！＝－1 and a[i]>s[top]：
　 q[tail]＝s[top]
　tail＋＝1
　top－＝1
　 top＋＝1
　 s[top]＝a[i]
while top！＝－1：
　 print(s[top]，end＝' ')
　 top－＝1
print() #输出换行
while head！＝tail：
　 print(q[head]，end＝' ')
　 head＋＝1
程序段运行后， 输出的结果第2行第3个数字为(　　)
A.1 B.2 C.3 D.4
A
解析　程序首先建立两个长度为 10 的列表 s 与 q，将a[0]入队。从索引位 1 开始向后遍历列表 a，将s 列表小于a[i]的值出栈，加入到队列 q 中。输出时第一行为 s 中的元素，第二行是队列 q 中的元素，输出2 3 1 2 4。
12.有如下Python程序段：
que＝[1，5，3，2，7]＋[0]*100　　　#构建列表que，形如[1，5，3，2，7，0，0，0，…]
head＝0；tail＝5
st＝[0]*len(que)　　　　　　　　#构建栈st
top＝－1
while head！＝tail：
　 while top！＝－1 and que[head]>st[top]：
　que[tail]＝st[top]
　tail＋＝1
B
　top－＝1
top＋＝1　　
　 st[top]＝que[head]
　 head＋＝1
执行该程序段后，栈st从栈顶到栈底的元素依次为(　　)
A.7，5，3，2，1 B.1，2，3，5，7
C.0，1，2，3，5，7 D.7，5，3，2，1，0
解析　程序功能是利用队列将栈中的元素进行升序排列。若栈不为空，当队首元素大于栈顶元素的值时，将栈中元素入队并出栈，否则将队首元素入栈并将队首进行出队操作。
二、非选择题(本题共4小题，共26分)
13.(6分)甲乙双方进行一场球类比赛，一局计分的规则是：赢1球得1分，用“1”表示；输1球失1分，用“0”表示。当任一方得分大于等于6分，且领先对方2分及以上，领先方赢一局。如甲选手一局比赛数据为“101110101”，表示甲选手得6分失3分，局比分6∶3。
小王用一个字符串记录了甲选手多局比赛数据，其中有一处错误，位于连续多个“0”的最后一个。为了找出错误，小王的处理方法如图a所示，对示例中疑似错误位置6和20分别修改数据，并统计每局比分。他编写了Python程序，功能如下：输入记录数据，输出修改位置以及修改后每局的比分。程序运行界面如图b所示。
图a
图b
输入记录数据：
1000001110101010100101010101101011
分析结果为：
修改位置　修改后每局的比分
6 /18：16
20 /4：6/6：4/8：6
实现上述功能的Python程序如下， 请回答下列问题：
rec＝input(″输入记录数据：″)
s＝list(rec)
①________________
k＝m＝i＝0
pos＝[]
while ik＝i
while s[i]＝＝″0″ and ii＝i＋1
if ②________________：
m＋＝1
pos.append(i－1)
i＝i＋1
print(″分析结果为：″)
print(″修改位置″，″修改后每局的比分″)
for i in range(m)：
f1＝f2＝0
k＝pos[i]
s[k]＝″1″
sp＝sp＋″/″＋str(f1)＋″：″＋str(f2)
print(sp)
③________________
(1)请在划线处填入合适的代码。
划线①处应填入的代码为_____________________________________________；
划线②处应填入的代码为______________________________________________；
划线③处应填入的代码为_____________________________________________。
(2)程序中加框处代码有错，请改正。
答案　(1)①n＝len(rec)或 n＝len(s) ②i－k>＝2　③s[k]＝″0″
(2)(f1>＝6 or f2>＝6) and abs(f1－f2)>＝2
解析　本题主要考查的是字符串的综合应用。(1)本题的算法思想是首先找出01串中连续2个及以上“0”的位置(在列表中的索引位置)，然后根据记录的位置，分别将记录的位置上的“0”修改为“1”，统计比分，记得统计好比分后，应将记录位置上的字符恢复为“0”。划线①处的功能是求01串中字符的个数，因此代码为n＝len(rec)，等价于 n＝len(s)；②处代码的功能是判断连续“0”的个数是否为2个及以上，k为连续“0”字符串中的起始位置，i为连续“0”字符串后的第1个“1”的位置，则连续“0”的个数为i－k，因此②处代码为i－k>＝2；③处代码的功能是恢复s[k]元素的值为“0”，因此代码为s[k]＝″0″。(2)加框处的代码表示一局比赛结束的条件，根据题意可知当任一方得分大于等于6分，且领先对方2分及以上时一局比赛结束，因此加框处语句应修改为(f1>＝6 or f2>＝6) and abs(f1－f2)>＝2。
14.(6分)某APP为增加用户活跃度，采用“签到得积分换奖品”的形式来吸引用户。签到积分的规则与玩法如下：
①第一天签到得1分，第二天签到得2分，第三天签到得3分，……第7天及7天以上签到得7分；一旦中途漏签，签到积分从1分开始重新计算；积分每年最后一天结束时清零。现在用“1”和“0”表示签到和未签到，如某用户下载APP后第一天到第九天的签到记录为“101111011”，则这9天共获得14个积分。
全年签到记录：01100011011001000100111111101101
0101111100110111000011100101111001000000111001
1001101110110011110001011011101111001001010010
1010011000110011011101100110111100111010100001
1000101010100011111100101010011001101000010000
1001000010010111011010001101000000111110100011
0011010101001010111111000111111110111010001011
0110010101010011011111111101100110101111011011
010011100
年积分：426
补签10月25日增加积分最多！可增加22分。
(1)若第1天到第18天的签到记录为“101110111001101111”，则补签第________天可增加积分最多。
(2)请在划线处填入合适的代码。
def tongji(s)：　#统计字符串中的积分
sum，pre＝0，0
　 for i in range(len(s))：
　 if s[i]＝＝″1″：
　　 　if pre<7：
　　　　 　pre＋＝1
　　　sum＋＝pre
　else：
　　　①________________
return sum
def check(ss)：
　 month＝{1：31，2：28，3：31，4：30，5：31，6：30，7：31，8：31，9：30，10：31，11：30，12：31}
　 max，index＝0，0
　 for i in range(len(ss))：
　 if ss[i]＝＝″0″：
　　　 head＝i－1
　　　tail＝i＋1
　　 while head>＝0 and ss[head]＝＝″1″：
　　　　　 head－＝1
　　　while tail<＝len(ss)－1 and ss[tail]＝＝″1″：
　　　　　tail＋＝1
　　　s1＝ss[head＋1：tail]
　　　②________________
　　　jfzj＝tongji(s2)－tongji(s1)
　　　if jfzj>max：
　　　　　max＝jfzj
　　　　　index＝i
　 k＝1
　 day＝index＋1
　 while ③________________：
　day＝day－month[k]
　k＋＝1
　 result＝″补签″＋str(k)＋″月″＋str(day)＋″日增加积分最多！可增加″＋str(max)＋″分。″
　 return result
答案　(1)6　(2)①pre＝0　②s2＝ss[head＋1：i]＋″1″＋ss[i＋1：tail]　
③day>month[k]
解析　本题考查字符串的相关知识。(1)修改第6天的值，连续1的天数最多。(2)①遇到“0”则重新开始计分，pre恢复初值。②check函数用于统计积分改变后的差值最大值。s2为将第i位字符改为“1”后的字符串：故②空建立s2字符串，填：s2＝ss[head＋1：i]＋″1″＋ss[i＋1：tail].③check函数最终返回的是一年中的某一天，接下来要计算出day对应的年月日。方法是通过day＝day－month[k]不断向后计算月份，直到无法减出完整月份，③空填：day>month[k]。
15.(7分)某餐厅餐桌设置如下表：
餐桌型号 2 人 小桌 4 人 方桌 6 人 大方桌 12 人
大圆桌
餐桌数量 8 15 10 4
平均就餐时间(分钟) 25 45 60 80
有客人来就餐时其叫号系统会自动生成一个号码，并根据人数安排餐桌型号；当对应餐桌型号有空桌时，按餐桌编号(由小到大)即时分配餐桌安排客人就餐；当对应餐桌型号没有空桌时， 客人按先后顺序排队。程序部分运行界面如下：
(1)定义如下 gettype函数，功能为输入客人人数，返回对应桌型，请在程序划线处填入合适代码。
def gettype(num):
　type＝－1
　 for i in range(len(size)):
11号客人，给您安排的是4人桌，前面还有0人在等位。
11号客人请用餐→4人桌2号
12号客人，给您安排的是2人桌，前面还有1人在等位。
13号客人，给您安排的是2人桌，前面还有2人在等位。
　 if num<＝size[i]：
　　　type＝i
　 　　__________
　　return type
(2)定义如下 checktable()函数，功能为输入桌型，返回对应桌型空桌的编号，返回值类型为列表，请在程序划线处填入合适代码。
def checktable(n):
　ans＝[]
　for i in range(nums[n])：
　 if ____________：
　　　ans.append(i)
　return ans
(3)解决上述问题的主程序如下，请在程序划线处填入合适代码。
size＝[2，4，6，12] #每种桌型最大就餐人数
nums＝[8，15，10，4] #每种桌型的餐桌数量
times＝[25，45，60，80] #每种桌型平均就餐时间
flags＝[[True]*nums[i] for i in range(4)] #标记每张桌子的初始状态
s_time＝10*60*60 #开始营业时间——10 点整，转化为秒
e_time＝14*60*60 #结束营业时间——14 点整，转化为秒
maxn＝50 #假设队列已经足够深
qc＝[[0]*maxn for i in range(4)] #循环队列
now_time＝s_time
id＝0
head，tail＝[0]*4，[0]*4
while now_time　　number＝getinfo() #调用函数 getinfo()，获取客人人数
if number>0：
　 id＋＝1
　type＝gettype(number) #根据就餐人数确定餐桌类型
　if type！＝－1：
　 　qc[type][tail[type]]＝id
　　 tail[type]＝(tail[type]＋1)%maxn
　　 qc_len＝①____________
　　　print(id，″号客人，给您安排的是″，size[type]，″人桌，前面还有″，qc_len－1，″人在等位″)
　else：
　　　print(id，″号客人，非常抱歉，没有适合您的桌型！″)
　　　for i in range(4)：
　tables＝checktable(i)
　if ②____________：
　　　　　flags[i][tables[0]]＝False #入座第一个空桌
　　　　print(qc[i][head[i]]，″号客人请用餐→″，size[i]，″人桌″，tables[0]，″ 号″)
　　 　　　head[i]＝(head[i]＋1)%maxn
　　　now_time＋＝1
　　　#更新每张餐桌的就餐情况，代码略
答案　(1)break　(2)flags[n][i]＝＝True
(3)①(tail[type]－head[type]＋maxn)%maxn
②len(tables)>0 and head[i]！＝tail[i] 或 tables and head[i]！＝tail[i]
解析　本题考查循环队列的基本应用。(1)gettype 函数功能为输入客人人数，返回对应桌型。size 数组存储每种桌型最大就餐人数，从小桌开始枚举，找到相应的规格就结束查找。
(2)checktable 函数功能找到对应桌型的空桌编号。nums 每种桌型的餐桌数量，flags 二维数组标记每种桌型每张桌子的初始状态，n为桌型编号，nums[n]表示该种桌型中最多就餐桌位，在 flags[n] 列表中从头开始(循环变量 i 从 0 至 nums[n]－1 中枚举)查找值为 True(空桌)的编号，并将这些编号添加到列表 ans 中，因此答案为 flag[n][j]＝＝True。(3)①求队列长度，qc 存储循环列表的信息，type 表示餐桌类型，qc[type]就是存储该类型的循环列表，循环队列长度公式(tail－head＋maxn)% maxn，因此①答案为(tail[type]－head[type]＋maxn) % maxn。②输出安排就餐情况。变量 i 表示每种桌型，安排座位的条件有两个，一是这种桌型有客人来，即qc[i]队列不为空；二是这种桌型有空位，tables 调用checktable(i)函数，获取空位列表。
16.(7分)消消乐游戏。随机产生5排(每排10个)a－e之间的随机字母，相邻两个字母之间互不相同。玩家输入一个字母，在第一排从左至右查找第1个与之相同的字母，消去该字母，左面的字母自动向右靠拢，若重组后相邻两个字母也相同，则消除相同的字母。如第1次输入字母“a”，得到结果所图b所示。若第1排找不到输入的字母，则在前10个位置查找，如第2次输入字母“a”，得到结果所图c所示。前10个位置中找不到输入的字母，则将该字母添加在最左边，如第3次输入字母“b”，得到结果所图d所示。
编制Python程序实现游戏功能，代码如下
def display(st，t，n)：
　 #按蛇形走线每排n个字母的方式显示栈st中各个元素，代码略。
#将产生的字符串入栈st1并显示，代码略。
ecebecaceb dedbabdecd edaeabdbec dabebcaeba cdcdcabceb 　　　 ece dedbabdecd edaeabdbec dabebcaeba cdcdcabceb 　　ecedcd edaeabdbec dabebcaeba cdcdcabceb 　 becedcd
edaeabdbec
dabebcaeba
cdcdcabceb
图a 图b 图c 图d
st2＝[″″]*(n＋1) #临时存储栈st1顶部不能被消除的元素
top2＝－1
k＝0；chs＝[″a″，″b″，″c″，″d″，″e″]
while top1！＝－1：
k＋＝1
ch＝input(″输入要消除的字母：″)
if ch not in chs：
continue
t＝0
while ttop2－＝1
if ③________________：
top1＋＝1
st1[top1]＝ch
display(st1，top1，n)
print(″恭喜你，大获全胜，尝试的次数有：″，k)
(1)当剩余的字母为“ababdaeababa”时，把全部字母消除完至少还要输入的次数是________。
(2)实现查找将移动元素功能的方框处可能的语句有：
①top1－＝1　②top2＋＝1
③st2[top2]＝st1[top1]　④t＋＝1。
按程序执行的先后顺序，可以选择其中的语句和顺序是：________。
答案　(1)2　(2)②③①保持顺序不变，④可以在任何地方。　(3)①top1－＝1
②st1[top1]＝st2[top2]　③t＝＝n　(4)会
(3)根据程序的功能，完善程序划线处①②③的代码。
(4)若输入要消除的字母为“p”，________(填：是 /否)会对程序的运行结果有影响。
解析　本题考查栈的基本操作。(1)第1次消除d，剩余“ababaeababa”，第2次消除e。(2)在栈st1顶部前n个元素中查找ch，若没有找到，移动到栈st2中。指针top指向栈顶第1个元素，出栈时，先取出数据，再向前移动指针。入栈时，先向后移动指针，再存入数据。语句②top2＋＝1必定在语句③st2[top2]＝st1[top1]的后面，存入数据后，再出栈。变量t是统计比较的字符个数，可以
在循环体的任意位置。(3)①当条件t(考试时间40分钟　满分50分)
一、选择题(本题共12小题，每小题2分，共24分)
1.有如下Python程序段：
count＝0
st＝list(″Python″)
s＝″″
for i in st：
s＝i＋s
count＋＝1
print(count，s)
程序段执行后，输出的结果是(　　)
A.5 Python B.6 Python
C.6 nohtyP D.6 'nohtyP'
2.有如下Python程序段：
s＝input(″输入一个字符串″)
a＝[″″]*6；t＝0
a[0]＝s[0]
for i in range(1，len(s))：
if t>＝0 and s[i]＝＝a[t]：
t＝t－1
else：
t＋＝1
a[t]＝s[i]
print(t)
运行程序段，输入以下字符串，运行后变量 t 的值与其它三项不同的是(　　)
A.AABAB B.AAABA C.BAABA D.BBABA
3.输入一个数字字符串 s，输出删除其中 k 个数字字符，并且数字的次序不能交换，输出删除后的最大数字字符串。如：输入数字字符串“38726”，若 k＝1，则删除其中 1 个数字字符后的最大数字字符串是“8726”，若k＝3，则删除其中 3 个数字字符后的最大数字字符串是“87”。实现上述功能的Python程序段如下：
s＝input(″请输入数字串″)
k＝int(input(″请输入要删除的数字个数″))
while k>0：
i＝0
while is[i＋1]：
i＋＝1
if i＝＝0：
　　
else：
　　
k－＝1
print(s)
上述程序段中加框处可选语句为：①s＝s[i＋1：]　②s＝s[i＋1：len(s)－1]　③s＝s[：i]＋s[i＋1：len(s)－1]　④s＝s[：i]＋s[i＋1：]
则(1)(2)处语句依次是(　　)
A.①④ B.③② C.③④ D.①②
4.队列Q从队首到队尾的元素依次是1，3，5，栈S从栈底到栈顶的元素依次是2，4，6，现约定：A操作是指元素出队后入栈，B操作是指元素出栈后入队。经过BAAB系列操作后，队列中队首到队尾的元素依次为(　　)
A.5，2，1 B.5，2，4 C.5，6，1 D.5，6，3
5.某Python程序如下：
q＝[″″]*50
head＝tail＝0
s＝″ningbo″
for i in s：
　q[tail]＝i
　tail＋＝1
while head　 print(q[head]，end＝″″)
　head＋＝1
　for i in range(3)：
　 q[tail]＝q[head]
　head＋＝1
　tail＋＝1
执行该程序段后，输出结果为(　　)
A.nbgoni B.nbogni C.goninb D.ningbo
6. 有如下Python程序：
a＝[4，2，5，1，9]
que＝[0]*7
head，tail＝0，0
que[tail]＝a[0]
tail＋＝1
for i in range(1，len(a)):
　if a[i]>que[tail－1]:
　 que[tail]＝a[i]
　tail＋＝1；head＋＝1
　elif a[i]　 que[tail]＝a[i]
　tail＋＝1
print(que[head：tail])
执行以上程序段后，输出结果是(　　)
A.4，7 B.5，1，9
C.2，5，1，9 D.4，7，2，5，1，9
7.有如下Python程序段：
a＝[2，4，5，10，8，13，11，7，2，6]
que＝[0]*len(a)
k＝int(input())
key＝int(input())
msq＝0；sq＝0
head，tail＝0，0
for i in a：
　 que[tail]＝i
　 sq＝sq＋i
　 tail＝tail＋1
　 while sq>key or tail－head>＝k：
　 sq＝sq－que[head]
head＝head＋1
　 if sq>msq：
　msq＝sq
若输入k的值为3、key的值为20，则程序运行后，变量msq的值为(　　)
A.18 B.19 C.20 D.21
8.用>表示进栈操作，<表示出栈操作，若元素进栈的顺序为“＋/*\”，出栈顺序为“＋\〔%/”，则由>和<表示的操作串是(　　)
A.><>>><<><< B.><>><><<><
C.>>>><<><<< D.><>>>><<<<
9.栈底至栈顶依次存放元素 A、B、C、D，在第五个元素E入栈前，栈中元素可能出栈，则 5 个元素全部出栈后，出栈的序列可能是(　　)
A.ABCED B.DBCEA C.CDABE D.DCBEA
10.有如下Python程序段：
w＝input()
flag＝True
st＝[″″]；top＝－1
c＝0
for i in w ：
　 if flag and i＝＝″(″：
　top＝top＋1
　 st[top]＝i
　flag＝False
　 elif not flag and i＝＝″)″：
　top＝top－1
　c＝c＋1
　flag＝True
print(c)
若输入w的值为″()()(()()))″，则以上程序运行后，输出结果为(　　)
A.6 B.3 C.4 D.5
11.有如下 Python 程序段：
s＝[0]*10；q＝[0]*10
a＝[6，3，2，4，2，1，5]
n，top，head，tail＝len(a)，0，0，0
s[top]＝a[0]
for i in range(1，n)：
　 while top！＝－1 and a[i]>s[top]：
　 q[tail]＝s[top]
　tail＋＝1
　top－＝1
　 top＋＝1
　 s[top]＝a[i]
while top！＝－1：
　 print(s[top]，end＝' ')
　 top－＝1
print() #输出换行
while head！＝tail：
　 print(q[head]，end＝' ')
　 head＋＝1
程序段运行后， 输出的结果第2行第3个数字为(　　)
A.1 B.2 C.3 D.4
12.有如下Python程序段：
que＝[1，5，3，2，7]＋[0]*100　　　#构建列表que，形如[1，5，3，2，7，0，0，0，…]
head＝0；tail＝5
st＝[0]*len(que)　　　　　　　　#构建栈st
top＝－1
while head！＝tail：
　 while top！＝－1 and que[head]>st[top]：
　que[tail]＝st[top]
　tail＋＝1
　top－＝1
top＋＝1　　
　 st[top]＝que[head]
　 head＋＝1
执行该程序段后，栈st从栈顶到栈底的元素依次为(　　)
A.7，5，3，2，1 B.1，2，3，5，7
C.0，1，2，3，5，7 D.7，5，3，2，1，0
二、非选择题(本题共4小题，共26分)
13.(6分)甲乙双方进行一场球类比赛，一局计分的规则是：赢1球得1分，用“1”表示；输1球失1分，用“0”表示。当任一方得分大于等于6分，且领先对方2分及以上，领先方赢一局。如甲选手一局比赛数据为“101110101”，表示甲选手得6分失3分，局比分6∶3。
小王用一个字符串记录了甲选手多局比赛数据，其中有一处错误，位于连续多个“0”的最后一个。为了找出错误，小王的处理方法如图a所示，对示例中疑似错误位置6和20分别修改数据，并统计每局比分。他编写了Python程序，功能如下：输入记录数据，输出修改位置以及修改后每局的比分。程序运行界面如图b所示。
图a
输入记录数据： 1000001110101010100101010101101011 分析结果为： 修改位置　修改后每局的比分 6 /18：16 20 /4：6/6：4/8：6
图b
实现上述功能的Python程序如下， 请回答下列问题：
rec＝input(″输入记录数据：″)
s＝list(rec)
①________________
k＝m＝i＝0
pos＝[]
while ik＝i
while s[i]＝＝″0″ and ii＝i＋1
if ②________________：
m＋＝1
pos.append(i－1)
i＝i＋1
print(″分析结果为：″)
print(″修改位置″，″修改后每局的比分″)
for i in range(m)：
f1＝f2＝0
k＝pos[i]
s[k]＝″1″
sp＝″　 ″＋str(k)＋″　　″
for j in range(n)：
if s[j]＝＝″1″：
　　　f1＋＝1
else：
　　　f2＋＝1
if ：
　　　sp＝sp＋″/″＋str(f1)＋″：″＋str(f2)
　　　f1＝f2＝0
if f1＋f2>0：
sp＝sp＋″/″＋str(f1)＋″：″＋str(f2)
print(sp)
③________________
(1)请在划线处填入合适的代码。
划线①处应填入的代码为_____________________________________________；
划线②处应填入的代码为______________________________________________；
划线③处应填入的代码为________________________________________________。
(2)程序中加框处代码有错，请改正。
14.(6分)某APP为增加用户活跃度，采用“签到得积分换奖品”的形式来吸引用户。签到积分的规则与玩法如下：
①第一天签到得1分，第二天签到得2分，第三天签到得3分，……第7天及7天以上签到得7分；一旦中途漏签，签到积分从1分开始重新计算；积分每年最后一天结束时清零。现在用“1”和“0”表示签到和未签到，如某用户下载APP后第一天到第九天的签到记录为“101111011”，则这9天共获得14个积分。
②APP每年会给用户一次补签一天的机会，补签之后积分的连续性可以持续，例如上面的9天中如果补签第七天增加积分最多，补签后9天的签到记录将变为“101111111”，积分将达到29分。为了找出一年中最佳的补签日，设计如下程序：从文件中读取一年365天(2月以28天计)的签到记录并以字符串形式输出，然后统计出全年的积分，并分析出补签增加积分最多那天的日期及将这一天补签后可增加积分数，程序输出效果如图所示。
全年签到记录：01100011011001000100111111101101 0101111100110111000011100101111001000000111001 1001101110110011110001011011101111001001010010 1010011000110011011101100110111100111010100001 1000101010100011111100101010011001101000010000 1001000010010111011010001101000000111110100011 0011010101001010111111000111111110111010001011 0110010101010011011111111101100110101111011011 010011100 年积分：426 补签10月25日增加积分最多！可增加22分。
(1)若第1天到第18天的签到记录为“101110111001101111”，则补签第________天可增加积分最多。
(2)请在划线处填入合适的代码。
def tongji(s)：　#统计字符串中的积分
sum，pre＝0，0
　 for i in range(len(s))：
　 if s[i]＝＝″1″：
　　 　if pre<7：
　　　　 　pre＋＝1
　　　sum＋＝pre
　else：
　　　①________________
return sum
def check(ss)：
　 month＝{1：31，2：28，3：31，4：30，5：31，6：30，7：31，8：31，9：30，10：31，11：30，12：31}
　 max，index＝0，0
　 for i in range(len(ss))：
　 if ss[i]＝＝″0″：
　　　 head＝i－1
　　　tail＝i＋1
　　 while head>＝0 and ss[head]＝＝″1″：
　　　　　 head－＝1
　　　while tail<＝len(ss)－1 and ss[tail]＝＝″1″：
　　　　　tail＋＝1
　　　s1＝ss[head＋1：tail]
　　　②________________
　　　jfzj＝tongji(s2)－tongji(s1)
　　　if jfzj>max：
　　　　　max＝jfzj
　　　　　index＝i
　 k＝1
　 day＝index＋1
　 while ③________________：
　day＝day－month[k]
　k＋＝1
　 result＝″补签″＋str(k)＋″月″＋str(day)＋″日增加积分最多！可增加″＋str(max)＋″分。″
　 return result
15.(7分)某餐厅餐桌设置如下表：
餐桌型号 2 人 小桌 4 人 方桌 6 人 大方桌 12 人 大圆桌
餐桌数量 8 15 10 4
平均就餐时间(分钟) 25 45 60 80
有客人来就餐时其叫号系统会自动生成一个号码，并根据人数安排餐桌型号；当对应餐桌型号有空桌时，按餐桌编号(由小到大)即时分配餐桌安排客人就餐；当对应餐桌型号没有空桌时， 客人按先后顺序排队。程序部分运行界面如下：
11号客人，给您安排的是4人桌，前面还有0人在等位。 11号客人请用餐→4人桌2号 12号客人，给您安排的是2人桌，前面还有1人在等位。 13号客人，给您安排的是2人桌，前面还有2人在等位。
(1)定义如下 gettype函数，功能为输入客人人数，返回对应桌型，请在程序划线处填入合适代码。
def gettype(num):
　type＝－1
　 for i in range(len(size)):
　 if num<＝size[i]：
　　　type＝i
　 　　__________
　　return type
(2)定义如下 checktable()函数，功能为输入桌型，返回对应桌型空桌的编号，返回值类型为列表，请在程序划线处填入合适代码。
def checktable(n):
　ans＝[]
　for i in range(nums[n])：
　 if ____________：
　　　ans.append(i)
　return ans
(3)解决上述问题的主程序如下，请在程序划线处填入合适代码。
size＝[2，4，6，12] #每种桌型最大就餐人数
nums＝[8，15，10，4] #每种桌型的餐桌数量
times＝[25，45，60，80] #每种桌型平均就餐时间
flags＝[[True]*nums[i] for i in range(4)] #标记每张桌子的初始状态
s_time＝10*60*60 #开始营业时间——10 点整，转化为秒
e_time＝14*60*60 #结束营业时间——14 点整，转化为秒
maxn＝50 #假设队列已经足够深
qc＝[[0]*maxn for i in range(4)] #循环队列
now_time＝s_time
id＝0
head，tail＝[0]*4，[0]*4
while now_time　　number＝getinfo() #调用函数 getinfo()，获取客人人数
if number>0：
　 id＋＝1
　type＝gettype(number) #根据就餐人数确定餐桌类型
　if type！＝－1：
　 　qc[type][tail[type]]＝id
　　 tail[type]＝(tail[type]＋1)%maxn
　　 qc_len＝①____________
　　　print(id，″号客人，给您安排的是″，size[type]，″人桌，前面还有″，qc_len－1，″人在等位″)
　else：
　　　print(id，″号客人，非常抱歉，没有适合您的桌型！″)
　　　for i in range(4)：
　tables＝checktable(i)
　if ②____________：
　　　　　flags[i][tables[0]]＝False #入座第一个空桌
　　　　print(qc[i][head[i]]，″号客人请用餐→″，size[i]，″人桌″，tables[0]，″ 号″)
　　 　　　head[i]＝(head[i]＋1)%maxn
　　　now_time＋＝1
　　　#更新每张餐桌的就餐情况，代码略
16.(7分)消消乐游戏。随机产生5排(每排10个)a－e之间的随机字母，相邻两个字母之间互不相同。玩家输入一个字母，在第一排从左至右查找第1个与之相同的字母，消去该字母，左面的字母自动向右靠拢，若重组后相邻两个字母也相同，则消除相同的字母。如第1次输入字母“a”，得到结果所图b所示。若第1排找不到输入的字母，则在前10个位置查找，如第2次输入字母“a”，得到结果所图c所示。前10个位置中找不到输入的字母，则将该字母添加在最左边，如第3次输入字母“b”，得到结果所图d所示。
ecebecaceb dedbabdecd edaeabdbec dabebcaeba cdcdcabceb 　　　 ece dedbabdecd edaeabdbec dabebcaeba cdcdcabceb 　　ecedcd edaeabdbec dabebcaeba cdcdcabceb 　 becedcd edaeabdbec dabebcaeba cdcdcabceb
图a 图b 图c 图d
编制Python程序实现游戏功能，代码如下
def display(st，t，n)：
　 #按蛇形走线每排n个字母的方式显示栈st中各个元素，代码略。
#将产生的字符串入栈st1并显示，代码略。
st2＝[″″]*(n＋1) #临时存储栈st1顶部不能被消除的元素
top2＝－1
k＝0；chs＝[″a″，″b″，″c″，″d″，″e″]
while top1！＝－1：
k＋＝1
ch＝input(″输入要消除的字母：″)
if ch not in chs：
continue
t＝0
while t#在栈st1顶部前n个元素中查找ch，若没有找到，移动到栈st2中
　　
if t①________________
while st1[top1]＝＝st2[top2] and top1>－1 and top2>－1: #消除相同的字母
　　　　top1－＝1
　　　　top2－＝1
while top2！＝－1：
top1＋＝1
②________________
top2－＝1
if ③________________：
top1＋＝1
st1[top1]＝ch
display(st1，top1，n)
print(″恭喜你，大获全胜，尝试的次数有：″，k)
(1)当剩余的字母为“ababdaeababa”时，把全部字母消除完至少还要输入的次数是________。
(2)实现查找将移动元素功能的方框处可能的语句有：
①top1－＝1　②top2＋＝1
③st2[top2]＝st1[top1]　④t＋＝1。
按程序执行的先后顺序，可以选择其中的语句和顺序是：________。
(3)根据程序的功能，完善程序划线处①②③的代码。
(4)若输入要消除的字母为“p”，________(填：是 /否)会对程序的运行结果有影响。
验收卷(二)　字符串、队列和栈
1.C　[本题主要考查的是字符串操作。本题的功能是统计循环的次数及将列表st中的字符进行反向拼接，列表中共有6个元素，因此循环次数为6，将列表st中的字符进行反向拼接后的结果为'nohtyP'，print输出时字符串内容没有引号，因此，答案为C。]
2.C　[本题考查字符串操作的相关知识。观察代码，t 初值为 0，a[t]为第 1 个字符，从第 2 个字符开始判断： 若与 a(t)相同且 t>＝0，则 t＝t－1；若与 a(t)不同或 t<0，则 t＝t＋1，a(t)跟踪新字符依据算法，ABD选项 t 值变化：－1，0，1，2，而C选项t 值变化：1，0，－1，0，可见 C 选项与其余三项不同，选 C。]
3.A　[本题考查程序代码的阅读理解能力，以及字符串相关函数的书写。删掉某个位置上的数字，使得剩下的数字构成的数最大。简单的思路就是，从前往后找。发现某个数字比后面的数字小，将这个数字删除即可。如果没有这样的情况，将最后的那个删掉即可。]
4.D　[6出栈后入队，1和3出队后入栈，3出栈后入队，因此队列中有原来的5和入队后的6、3。]
5.A　[操作过程：队首出队，紧接着3个入队尾后出队，直至队列为空。ningbo→boing→goin→oin→ni→i。]
6.B　[队列中初始1个元素，值为4。遍历列表a中位置1到len(a)－1的元素，若遍历的元素值比队尾元素大，则将队首出队后再将a[i]入队。若遍历的元素值小于队首，直接将a[i]入队。队列中元素变化情况为[4，2]、[2，5]、[2，5，1]、[5，1，9]。]
7.A　[本题考查队列的操作。语句que[tail]＝i的功能是将数组a中数据依次入队，并将队列的数进行累加到sq中，当条件sq>key or tail－head>＝k时，依次出队，并在sq中减去队首的值，msq是出队后(队列中最多只包含k－1个元素)累加和的最大值。最大值为4＋5＝9、5＋10＝15、10＋8＝18、8＋13－8＝13(累加和大于20，还要出队)。]
8.A　[本题考查栈的操作。＋入后马上出，/*\\入，\〔出，栈中只有/，%入后马上出，/再出。]
9.D　[本题考查出入栈相关知识点。四个元素的出栈顺序是一定是DCBA。]
10.C　[本题考查栈的操作。当读取到″(″进行入栈操作，并且flag值为False；当栈不为空，且读取到″)″时，进行出栈操作。前面2对括号依次入栈出栈，c为2。连续读取2个左括号，第2个左括号时，flag值为False，只有一个括号入栈。2对括号依次入栈出栈。读取最后两个右括号时，栈中无元素，不能出栈操作。]
11.A　[程序首先建立两个长度为 10 的列表 s 与 q，将a[0]入队。从索引位 1 开始向后遍历列表 a，将s 列表小于a[i]的值出栈，加入到队列 q 中。输出时第一行为 s 中的元素，第二行是队列 q 中的元素，输出2 3 1 2 4。]
12.B　[程序功能是利用队列将栈中的元素进行升序排列。若栈不为空，当队首元素大于栈顶元素的值时，将栈中元素入队并出栈，否则将队首元素入栈并将队首进行出队操作。]
13.(1)①n＝len(rec)或 n＝len(s)　②i－k>＝2　③s[k]＝″0″
(2)(f1>＝6 or f2>＝6) and abs(f1－f2)>＝2
解析　本题主要考查的是字符串的综合应用。(1)本题的算法思想是首先找出01串中连续2个及以上“0”的位置(在列表中的索引位置)，然后根据记录的位置，分别将记录的位置上的“0”修改为“1”，统计比分，记得统计好比分后，应将记录位置上的字符恢复为“0”。划线①处的功能是求01串中字符的个数，因此代码为n＝len(rec)，等价于 n＝len(s)；②处代码的功能是判断连续“0”的个数是否为2个及以上，k为连续“0”字符串中的起始位置，i为连续“0”字符串后的第1个“1”的位置，则连续“0”的个数为i－k，因此②处代码为i－k>＝2；③处代码的功能是恢复s[k]元素的值为“0”，因此代码为s[k]＝″0″。(2)加框处的代码表示一局比赛结束的条件，根据题意可知当任一方得分大于等于6分，且领先对方2分及以上时一局比赛结束，因此加框处语句应修改为(f1>＝6 or f2>＝6) and abs(f1－f2)>＝2。
14.(1)6　(2)①pre＝0　②s2＝ss[head＋1：i]＋″1″＋ss[i＋1：tail]　③day>month[k]
解析　本题考查字符串的相关知识。(1)修改第6天的值，连续1的天数最多。(2)①遇到“0”则重新开始计分，pre恢复初值。②check函数用于统计积分改变后的差值最大值。s2为将第i位字符改为“1”后的字符串：故②空建立s2字符串，填：s2＝ss[head＋1：i]＋″1″＋ss[i＋1：tail].③check函数最终返回的是一年中的某一天，接下来要计算出day对应的年月日。方法是通过day＝day－month[k]不断向后计算月份，直到无法减出完整月份，③空填：day>month[k]。
15.(1)break　(2)flags[n][i]＝＝True　(3)①(tail[type]－head[type]＋maxn)%maxn　②len(tables)>0 and head[i]！＝
tail[i] 或 tables and head[i]！＝tail[i]
解析　本题考查循环队列的基本应用。(1)gettype 函数功能为输入客人人数，返回对应桌型。size 数组存储每种桌型最大就餐人数，从小桌开始枚举，找到相应的规格就结束查找。
(2)checktable 函数功能找到对应桌型的空桌编号。nums 每种桌型的餐桌数量，flags 二维数组标记每种桌型每张桌子的初始状态，n为桌型编号，nums[n]表示该种桌型中最多就餐桌位，在 flags[n] 列表中从头开始(循环变量 i 从 0 至 nums[n]－1 中枚举)查找值为 True(空桌)的编号，并将这些编号添加到列表 ans 中，因此答案为 flag[n][j]＝＝True。(3)①求队列长度，qc 存储循环列表的信息，type 表示餐桌类型，qc[type]就是存储该类型的循环列表，循环队列长度公式(tail－head＋maxn)% maxn，因此①答案为(tail[type]－head[type]＋maxn) % maxn。②输出安排就餐情况。变量 i 表示每种桌型，安排座位的条件有两个，一是这种桌型有客人来，即qc[i]队列不为空；二是这种桌型有空位，tables 调用checktable(i)函数，获取空位列表。
16.(1)2　(2)②③①保持顺序不变，④可以在任何地方。
(3)①top1－＝1　②st1[top1]＝st2[top2]　③t＝＝n　(4)会
解析　本题考查栈的基本操作。(1)第1次消除d，剩余“ababaeababa”，第2次消除e。(2)在栈st1顶部前n个元素中查找ch，若没有找到，移动到栈st2中。指针top指向栈顶第1个元素，出栈时，先取出数据，再向前移动指针。入栈时，先向后移动指针，再存入数据。语句②top2＋＝1必定在语句③st2[top2]＝st1[top1]的后面，存入数据后，再出栈。变量t是统计比较的字符个数，可以在循环体的任意位置。(3)①当条件t

展开更多......

收起↑