资源简介

(共52张PPT)
第二章　数组与链表
验收卷(一)　数组与链表
(考试时间40分钟　满分50分)
一、选择题(本题共12小题，每小题2分，共24分)
B
解析　本题主要考查的是数组和链表的特性。查找特定元素，使用单向链表查找时，只能通过头指针进入链表并通过指针链接依次访问，直到找到特定元素，而使用数组查找时，只要使用数组名和下标就能直接访问特定元素，因此，查找特定元素，使用数组比使用单向链表更方便。
A.对于需要频繁插入和删除元素的情况，使用单向链表比使用数组合适
B.查找特定元素，使用单向链表比使用数组方便
C.数组适用于最大元素个数容易确定的情况
D.存储相同的元素，使用单向链表比使用数组方便
D
2.下列关于数组和链表的存储结构与逻辑结构关系的说法，正确的是(　　)
解析　链表的节点结构包括数据域与指针域，指针表示各节点的连接前后顺序，即链表数据的逻辑结构由指针表示，D选项正确。
A.链表的存储结构与逻辑结构一致
B.数组的存储结构对逻辑结构没有影响
C.存放相同数据的数组存储空间大于链表
D.链表数据的逻辑结构由指针表示
A
3.利用5列6行的二维数组qp来记录某试场中的座位编号1～30，m＝0
qp＝[[0 for i in range(5)] for j in range(6)] #建立二维数组并初始赋值为0
for i in range(5)：
　for j in range(6)：
　 if i %2＝＝0：
　　　 qp[j][i]＝m*6＋j＋1
　else：
　　　qp[j][i]＝m*6＋6－j
　m＝m＋1
运行上述程序段后，编号17所在的数组元素为(　　)
A.qp[4][2] B.qp[2][4] C.qp[5][3] D.qp[6][1]
解析　赋值对象为qp[j][i]，即i表示列，j表示行，意味着是按列遍历矩阵，因此第1列为1－6，第2列为m*6＋6－j，即12－7递减，第3列为13－18。
D
4.下列关于链表的叙述中，正确的是(　　)
解析　单链表存储方式地址不连续，元素顺序是任意的，因此答案为D。
A.线性链表中的各元素在存储空间中的位置必须是连续的
B.线性链表中的表头元素一定存储在其他元素的前面
C.线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面
D.线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的
C
A.节点的数据区域用于存放实际需要处理的数据元素
B.节点的指针区域用于存放该节点相邻节点的存储地址
C.单向链表必须带有数据区域为空的头节点和尾节点
D.单向链表中的各个节点在内存中可以非顺序存储
解析　选项单向链表的头节点和尾节点可以是单独的数据区域为空的节点，也可以将节点序列中的第1个和最后一个节点作为头节点和尾节点。在Python程序设计时我们通常使用第二种方式，即直接使用带数据区域的节点作为头节点或尾节点来标记和使用。
C
6.有如下Python程序段：
解析　本题考查链表的遍历。条件a[p][1]！＝－1表示当前节点的指针区域值为－1，即当前节点为尾节点。当遍历到尾节点时，结束循环。
a＝[[2，2]，[5，3]，[3，1]，[6，－1]，[1，0]，[4，2]]
p＝5
while a[p][1]！＝－1：
　　print(a[p][0]，end＝″→″)
　　p＝a[p][1]
则运行程序后，控制台输出的结果是(　　)
A.4→3→5 B.4→3→2→5→
C.4→3→5→ D.4→3→2→5
7.有下列Python程序段：
a＝[[1，3]，[1，0]，[7，1]，[4，5]，[1，－1]，[6，4]]
x＝1
p＝pre＝head＝2
if x＝＝a[head][0]：
head＝a[head][1]
else：
while p！＝－1 ：
if x＝＝a[p][0]：
　　　　a[pre][1]＝a[p][1]
解析　本题考查链表的基本操作。如果链表头节点值为1，直接删除头节点，否则遍历链表，语句a[pre][1]＝a[p][1]的作用让节点p的前驱指向他的后继，即删除p节点。程序的功能是删除元素值为1的节点。
else：
　　　　pre＝p
p＝a[p][1]
运行该段程序后，a[2][1]的值为(　　)
A.－1 B.0 C.1 D.3
D
8.采用Python二维列表模拟链表，
a＝[['A'，1]，['B'，2]，['C'，3]，['D'，4]，['E'，5]，
['F'，－1]]表示链表为：
A→B→C→D→E→F→None，有以下Python程序：
a＝[['A'，1]，['B'，2]，['C'，3]，['D'，4]，['E'，5]，
['F'，－1]]
head＝0；p＝a[head][1]
a[head][1]＝－1
while p！＝－1：
p＝a[p][1]
if p＝＝－1：
break
解析　本题考查链表的基本操作。p的初值为a[head][1]，即head的后继，进入循环后，语句p＝a[p][1]的功能是向后遍历，让该节点指向头节点，p再向后遍历。A后继的后继是C，当前头节点为C，C指向A；C后继的后继是E，当前头节点为E，E指向C。
t＝a[p][1]
a[p][1]＝head
head＝p
p＝t
执行以上程序后，以head为首的链表结构为(　　)
A.E→C→A B.A→C→E
C.B→D→F D.F→D→B
A
9.有如下 Python 程序：
a＝[43，23，87，67，80]
queinfo＝[]
for item in a：
　k＝0
　 while kif item>＝queinfo[k][－1]：
　　　 　break
k＋＝1
　　if k＝＝len(queinfo)：
queinfo.append([item])
解析　queinfo初值为空，语句queinfo.append([item])是将一个列表添加到queinfo，因此他是一个二维数组。遍历列表a，在queinfo数组从第0个元素开始，与每个元素最后一个数据项进行比较，如果大于等于元素最后一个数据项，结束比较，此时j肯定在0至len(queinfo)－1之间，若j的值为len(queinfo)，说明该元素比queinfo中每个元素的最后一个值均小，则新成一组。Queinfo的值为[[43，87]，[23，67，80]]。
　　　else：
queinfo[k].append(item)
print(len(queinfo))
执行该程序段后，输出的结果是(　　)
A.1 B.2 C.3 D.4
B
10.有如下Python程序段：
n＝6
a＝[[0]*n for i in range(n)]
for i in range(n)：
　for j in range(i＋1)：
　 if j！＝0 and j！＝i：
　　　 a[i][j]＝a[i－1][j－1]＋a[i－1][j]
　else：
　　　a[i][j]＝1
C
程序执行后，a[4]的值是(　　)
A.[1，3，3，1，0，0] B.[1，4，6，6，4，1]
C.[1，4，6，4，1，0] D.[1，5，10，10，5，1]
解析　本题考查二维数组的创建和遍历。先创建一个6行6列的二维数组，遍历二维数组的每一行，内循环从0至i，因此只对二维数组的左下半部分进行赋值。将第1列和主对角线(i和j相等)的数据全部赋值为1，其他数据为上一行的前一个和上一行的当前列之和，因此程序的功能是构建一个杨辉三角。
11.有如下 Python程序段：
a＝[[1，3，6，9]，[2，4，7，5]，[5，2，3，8]]；b＝[1]
n＝len(a)
for i in range(n)：　　
　　　for j in range(n＋1)：
　 if ib.append(a[i][j])#b追加一个元素a[i][j]
A
执行该程序执段后，数组b 中的元素为(　　)
A.[1，3，6，9，7，5，8] B.[3，6 ，9，7 ，5，8]
C.[1，3，6，9，2，4，7，5，8] D.[1，3，6，9，4，7，5，8]
解析　本题考查二维数组的应用.将二维数组a中下标i12.某Python程序如下：
data＝[]
for i in range(len(a))：
　data.append([a[i]，i＋1])
data[－1][1]＝－1
la＝head＝0
t＝data[head][1]
key，c＝2，0
while c<3 and t！＝－1：
　 if data[t][0]－data[la][0]　 c＋＝1
　la＝t
　t＝data[t][1]
B
已知执行上述程序后，t的值为6，则数组a的值可能(　　)
A.[4，3，1，6，3，9，3] B.[2，6，5，1，6，4，0]
C.[7，5，2，3，2，7，5] D.[2，4，0，1，0，8，4]
解析　本题考查链表应用。data是一个链表，t指针从链表的第二个节点开始遍历，1a指针是t节点的前驱，t节点减去前驱节点la的值小于key时，c计数，c的初值为0，计数到3时历结束，也就是整个过程计数3次就结束，执行程序后t的值为6，也就是遍历到最后一个节点时程序才结束。
二、非选择题(本题共4小题，共26分)
13.(6分)大部分社交软件都有好友推荐的功能，当用户A和用户B不为好友，但他们的共同好友数量超过阈值m时，由系统向用户A推荐用户B。
编写Python程序，实现好友推荐功能。生成一个二维数组a记录两者关系，当a[0][2]的值为1时，表示ID1和ID3是好友，值为0则不是好友。运行程序，输入用户ID和共同好友数量超过阈值m，显示每个用户ID的好友及向目标用户推荐的好友列表。程序运行界面如图：
共同好友数量超过阈值m：2
1ID号的好友有：2，3，4，5，6，7，9
2ID号的好友有：1，3，4，5，6，7，10
3ID号的好友有：1，2，5，6，7，8，9
4ID号的好友有：1，2，5，6，7，8，9，10
5ID号的好友有：1，2，3，4，6，8
6ID号的好友有：1，2，3，4，5，7，9，10
7ID号的好友有：1，2，3，4，6，8
8ID号的好友有：3，4，5，7，9，10
9ID号的好友有：1，3，4，6，8
10ID号的好友有：2，4，6，8
向用户ID1推荐的共同好友有：[8，10]
编写的代码如下：
n＝10
#产生一个n*n的二维数组a，存储两人之间的关系。
def Check(a，x，y): #向用户ID为x推荐的阈值为y的好友列表。
n＝10；ans＝0
nothy＝[]
for i in range(n): #查找与x不是好友的朋友编号
　 if ①____________：
　　　 　nothy.append(i)
hy＝[]
for i in nothy：
　 t＝0
　 for j in range(n)：
　 if ②____________：
　　　 　t＋＝1
if t>y：
　 hy.append(i＋1)
return hy　
hm＝int(input(″输入用户ID：″))
m＝int(input(″共同好友数量超过阈值m：″))　
for i in range(n)：
　 s＝str(i＋1)＋″ID号的好友有：″
　 for j in range(n)：
　 if a[i][j]＝＝1：
　　　　s＝s＋str(j＋1)＋″，″
　print(s[：－1])
③____________
print(″向用户ID″，hm，″推荐的共同好友有：″，p)
(1)输入用户ID为7，阈值m为4，则推荐的好友是________。
(2)请在程序划线处填入合适的代码。
答案　(1)5，9　(2)①a[i][x]＝＝0 and x！＝i
②a[x][j]＝＝1 and a[i][j]＝＝1
③p＝Check(a，hm，m)
解析　(1)在不是好友中选择共同好友超过4的ID，ID10与ID7的共同好友只有4个。(2)①查找与x不是好友的朋友编号，在各个编号中遍历，相当在于二维表格的第x行查找0的列号，但列号不能是x自己。②寻找共同好友，即第x第i行中，值均为1的列号数量。③调用自定义函数查找共同好友。
已知
14.(6分)某影平台上架新影片时，需要先确定该影片的类型，如喜剧片、动作片、爱情片。确定某影片的类型，可根据已有的样本数据(如图a所示)进行分类。
图a
电影名称 搞笑镜头 拥抱镜头 打斗镜头 影片类型
宝贝当家 45 2 9 喜剧片
唐人街探案 23 3 17 喜剧片
我的特工 爷爷 6 4 21 动作片
…… …… …… …… ……
泰坦尼克号 9 39 8 爱情片
罗马假日 9 38 2 爱情片
新步步惊心 8 34 17 爱情片
图b
电影名称 搞笑 镜头 拥抱 镜头 打斗 镜头 影片
类型
美人鱼 19 18 5 ？
距离最近的前5部影片为：
唐人街探案19.62，罗马假日22.56，新步步惊心22.83，泰坦尼克号23.45，我的特工爷爷24.92，
图c
请回答下列问题：
(1)与《美人鱼》距离最近的前5部影片如图c所示，则该影片属于________(单选，填字母：A.喜剧片 /B.动作片 /C.爱情片)。
(2)定义如下mvmin(result，flag)函数，参数result列表存储距离，flag列表存储标记。若result＝[43，33，18，25，65]，flag＝[False，False，True，True，False]，则函数的返回值为________。
def mvmin(result，flag)：
mv＝10000　#假定result列表元素值不超过10000
for i in range(len(result))：
　　 　if mv>result[i] and flag[i]＝＝False：
　　　 mv＝result[i]
　　　pos＝i
return pos
(3)实现电影分类的部分Python程序如下，请在划线处填入合适的代码。
读取样本影片的镜头数据，存储在data中，每个元素包含5个数据项，分别对应电影名称、搞笑镜头、打斗镜头、拥抱镜头、影片类型。
如data＝[[″宝贝当家″，45，2，9，″喜剧片″]，……]，代码略。
x＝[″美人鱼″，19，18，5]
dic＝{″喜剧片″：0，″动作片″：0，″爱情片″：0}
k＝5　
result＝[0]*len(data)
for i in range(len(data))：
d＝0
for j in range(1，4)：
　　tmp＝①________
　 　d＋＝tmp**2　
result[i]＝round(d**0.5，2) #结果保留2位小数
flag＝[False]*len(result)
print(″距离最近的前″，k，″部影片为：″)
while k>0：
p＝mvmin(result，flag)
flag[p]＝True
②________
print(data[p][0]，result[p]，end＝″，″)
③________
#统计前k个最近距离的影片中出现频次最多的类型，并输出该影片类型，代码略
答案　(1)C　(2)1　(3)①data[i][j]－x[j] 或 x[j]－data[i][j] 　②dic[data[p][4]]＋＝1　③k－＝1
解析　(1)距离最近的5部影片中，喜剧片1部，爱情片3部分，动作片1部，因此该影片类型为爱情片。(2)在存储标记为False的位置中，查找最小值的索引，43，33，65三个数中最小值索引为1。(3)①遍历所有的样本数据data，计算出“美人鱼”与样本中所有影片的距离。data[i][1]、data[i][2]、data[i][3]分别表示样本数据中搞笑镜头、打斗镜头、拥抱镜头的值，用变量j表示这些下标，计算与x[j]的平方差的和。②调用mvmin函数计算最小距离的索引p，即对应的样本的索引，在数组元素data[p][4]中存储的是该影片的类型，需要对该类型的数量增加1。③处理下一个样本数据。
15.(7分)某学校工会举行飞镖大赛，共有n位老师报名参赛，每位选手共掷5支镖，每镖得分为0至10分，选手总分为 5镖成绩之和，每位选手的比赛数据记录在文本文件中，如图a所示。
处理要求：数据读入数组 data 中，计算出每位选手的总分，在不改变数据在原数组 data 中的位置的条件下，按总分从高到低输出选手的编号和总分。
(1)主程序。采用链表结构处理数据。程序运行结果如图 b所示。请在程序中划线处填入合适的代码。
data＝readdata(″scores.txt″) #读取数据，计算总分
print(″处理前的数据为：\\n″，data)
n＝len(data)
flag＝[True]*n #标记数据被使用情况
head＝findmax() #返回 data 中可使用状态最大数的位置
k＝head
for i in range(1，n):
　 posi＝findmax()
　 data[k].append(posi)
　______________
data[k].append(－1)
print(″处理后的数据为：\\n″，data)
print(″从高分到低分输出为：″)
output(head)
(2)编写readdata函数，功能为从文本文件读取数据，计算出总分，返回列表。代码如下，请在程序中划线处填入合适的代码。
def readdata(filename):
　 f＝open(filename)
　 line＝f.readline()
　　lst＝[]
　　while line: #获取每位选手的编号和总分数据
　　 　line＝line.split(″，″)
　　　s＝0
　 　　for i in range(1，len(line))：
　　 　__________
　　　lst.append([line[0]，s])
　 　　line＝f.readline()
return lst
(3)编写findmax函数，功能为返回 data 中可使用状态最大数的位置pos，并设置该数的使用状态为 False。请在程序中划线处填入合适的代码。
def findmax()：
　maxnum＝0
　 for i in range(n)：
　 if ①____________：
　　　 maxnum＝data[i][1]
　　　 pos＝i
　　　②____________
　　　return pos
答案　(1)k＝posi　(2)s＋＝int(line[i])
(3)①maxnum②flag[pos]＝False　(4)q！＝－1
解析　(1)查找数组中的最大值的位置，利用位置关系串成一个降序链表，最后遍历链表输出。k 是当前元素的位置，posi 是下一个元素的位置，找到的数应该在节点 posi 后面。(2)readdata函数功能是读取“scores.txt”文件，生成一个二维列表。变量s累计的总分。(3)findmax函数找到最大数所在位置，同时将该位置设置为 False。
(4)遍历链表，输出节点相关数据域的内容。
16.(7分)“抢单”是外卖骑手的日常，当外卖平台上一个新的订单出现时，骑手需要在短时间内考虑是否抢单。平台根据骑手的实际信息，给出是否抢单的建议，若建议抢单则给出到达各个取送点的顺序。
平台判断是否抢单的算法设计如下：
1)在不改变已有订单各取送点顺序的前提下，将新订单按先取餐后送餐的顺序分别插入原来的路线中，枚举所有新路线；
2)计算新路线路程，并进行判断：每个取送点都有一个系统指定时间，若骑手到达该位置时，时间晚于系统指定时间，则该方案无效；
3)对新路线进行计算和判断后，删除此次枚举的两个插入位置，还原为初始状态，再继续进行下一次枚举；
4)在所有有效方案中，输出总路程最小的方案，若无有效方案，则输出不接单的建议。
如果骑手目前无订单在派送中，则插入订单A的方案只有1种，骑手→取餐点A→送餐点A；如果骑手订单中已有1个送餐点A和1个送餐点B，则新订单C有6种插入方案，如下所示，
方案1：骑手→取餐点C→送餐点C→送餐点A→送餐点B
方案2：骑手→取餐点C→送餐点A→送餐点C→送餐点B
方案3：骑手→取餐点C→送餐点A→送餐点B→送餐点C
方案4：骑手→送餐点A→取餐点C→送餐点C→送餐点B
方案5：骑手→送餐点A→取餐点C→送餐点B→送餐点C
方案6：骑手→送餐点A→送餐点B→取餐点C→送餐点C
(1)若骑手仅剩3份餐未送(已取餐)，路线为：骑手→送餐点A→送餐点B→送餐点C，新的订单出现后，有________种插入方案。
(2)定义如下con(tim)函数进行时间格式转换，将24小时制的“时：分”转换为分，如02：30转换为150，请在划线处填上合适代码。
def con(tim)：
　t＝__________＋int(tim[3：])
　　return　t
(3)定义totd(riderlist，h)函数，其功能为从头指针h进入链表riderlist，按节点先后顺序计算总路程，并判断能否在系统指定时间内到达各取送点，若到达某一取送点时超时返回－1。若链表riderlist如下，
riderlist＝[[″u1001″，″119.906033″，″31.014597″，″11：30″，2]，
[″s″，″119.921439″，″31.023022″，″11：55″，3]，
[″t″，″119.887850″，″31.022861″，″11：40″，1]，
[″s″，″119.953836″，″31.021122″，″12：10″，－1]]
第1个元素中″u1001″为骑手编号，″119.906033″和″31.014597″，表示骑手实时位置，″11：30″为实时时间，2为下一节点指针，第2个元素开始，第1项若为″t″表示此元素为取餐点信息，若为″s″表示此元素为送餐点信息。调用函数totd(riderlist，h)，risderlist的值如上，h为0，则加框处语句最多被执行______次，若将此条件语句改为riderlist[pre][4]！＝－1，______(选填：影响/不影响)程序执行。
total＋＝d
if total/speed>con(riderlist[cur][3])－con(riderlist[h][3])：
　　　　return －1
else：
　　　　 pre＝cur
　　　　 cur＝riderlist[pre][4]
return round(total，2)
(4)实现是否接单判断的Python部分程序如下，请在划线处填入合适的代码。
def add(oldlist，x，c)：　#在x所指节点后插入新节点c
c[4]＝oldlist[x][4]
oldlist.append(c)
oldlist[x][4]＝len(oldlist)－1
return oldlist
#读取骑手信息，存储在lit中，代码略
tc＝[″t″，″119.936506″，″31.008933″，″12：05″，－1]　#新订单取餐信息　
sc＝[″s″，″119.919839″，″31.020183″，″12：22″，－1]　#新订单送餐信息
ans＝[－1，－1，10000]
head＝0
p＝head
while p！＝－1：
lit＝add(lit，p，tc)
①____________
while q！＝－1：
lit＝add(lit，q，sc)
tot＝totd(lit，head)
if tot！＝－1 and ②____________ ：
　　　ans＝[p，q，tot]
lit[q][4]＝lit[lit[q][4]][4]
q＝lit[q][4]
lit[p][4]＝lit[lit[p][4]][4]
p＝lit[p][4]
if ans[2]＝＝10000：
print(″不建议接单，不能在系统指定时间内送达。″)
else：
print(″可以接单，建议各取送点到达顺序依次为：″)
#按顺序输出各取送点代码略
答案　(1)10 (2)int(tim[0：2])*60 或 int(tim[：2])*60 (3)4　 不影响
(4)①q＝lit[p][4] 或 q＝lit[p][－1]
②tot解析　本题考查链表的遍历和插入等操作。(1)取餐点一定在送餐点的前面，若有3个送餐点，则可以分别在这3个点的4个地方依次插入取送餐点，则分别有4＋3＋2＋1＝10种方案。(2)获取字符串中小时并转换成分钟。(3)4个取送餐点有3段距离，但循环条件需判断4次。cur是当前节点，pre为当前节点的前驱，当前节点为－1时，其前驱的指针区域值也为－1。(4)①节点p遍历链表，在节点p的后面插入取送餐点，因此q的初值为节点p的后继。②变量ans存储了插入点位置及距离，语句ans＝[p，q，tot]表示更新了其值，因此条件是新的距离tot小于最短距离ans。验收卷(二)　字符串、队列和栈
(考试时间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

展开更多......

收起↑