资源简介

中小学教育资源及组卷应用平台
2025新教材技术高考第一轮
专题八　数据结构与算法
考点过关练
考点一　数据结构与算法效率
1.(2024届发展共同体联考,12)以下两个程序段的功能相同,实现的功能是:删除列表a(元素个数为n)中的重复元素(只保留一个),并将剩下的元素降序输出。
#程序段① #对列表a进行降序排序,代码略 i=1 while i#程序段② max_num=max(a)#求出列表a中的最大值max_num b=[0]*(max_num+1) for i in range(0,n): 　 b[a[i]]+=1 for i in range(max_num,0,-1): 　 if b[i]>0: 　　　print(i,end=" ")
关于上述两个程序段及功能的描述,正确的是(　　)
A.同样的数据规模,两个程序段的时间效率一样
B.程序段①加框处语句是否执行不受列表a原数据的影响
C.程序段②加框处语句修改为“for i in range(1,max_num+1)”,输出结果不变
D.在实现该功能的过程中,程序段②比程序段①需要更多的存储空间
2.常见算法时间复杂度函数的增长率如图所示。
则当问题规模n=100时,下列时间复杂度中效率最高的是(　　)
A.O(nlog2n)　　　　B.O(log2n)
C.O(n)　　　　D.O(n3)
3.有如下Python程序代码:
n=int(input("n="))
ans1=ans2=0
for i in range(0,n,2):
　　　for j in range(n):
　　　ans1=ans1+1
　　　ans2=ans2+ans1
print("ans1=",ans1,"ans2=",ans2)
则该算法的时间复杂度为(　　)
A.O(1)　　　B.O(n)　　　C.O(n2)　　　D.O(2n)
4.有以下Python程序段:
def jishu(n):
s=0
while n>0:
　s+=n%2
　n//=2
return s
n=int(input("输入一个正整数:"))
ans=jishu(n)
print(ans)
阅读上述代码,回答以下问题。
(1)该程序运行后,输入整数23,输出结果为　　　　。
(2)若输入整数23,则程序中自定义函数jishu()中语句“s+=n%2”执行的次数是　　　。
(3)函数jishu()的时间复杂度为　　　　(单选:A.O(n)　B.O(log2n))。
考点二　迭代与递归
1.(2023浙江1月选考,11,2分)定义如下函数:
def rf(n):
if n<3:
return n
return rf(n-1)+rf(n-3)
执行语句v=rf(5),函数rf被调用的次数是(　　)
A.1　　　B.5　　　C.7　　　D.15
2.(2023浙江6月选考,10,2分)定义如下函数:
def f(a,s):
　　if a>=s:
　　　　return a
　　else:
　　　　return f(a+1,s-a)
执行语句k=f(6,21)后,k的值为(　　)
A.6　　　B.7　　　C.8　　　D.9
3.(2024届发展共同体联考,10)定义如下函数:
def f(x,y):
　　if x<=2 or y>20:
　　　　return x+y
　　return f(x-1,y+1)
执行语句k=f(5,1)后,k的值为(　　)
A.6　　　B.7　　　C.8　　　D.9
4.(2022绍兴诸暨期中,10)某Python程序段如下:
import random
fibo=[1]*11
for i in range(2,11):
　 fibo[i]=fibo[i-1]+fibo[i-2]
n=random.randint(1,10)
print(fibo[n])
运行该程序段,输出结果不可能是(　　)
A.1　　　B.21　　　C.35　　　D.89
5.(2022绍兴诸暨期中,12)下列Python程序的功能是使用迭代算法求s的值。
n=int(input("please input n:"))
s=0
for i in range(1,n):
　　if i%3==0:
　　　　 s=s+i
print("s=",s)
程序执行时,输入n的值为25,则输出的结果为(　　)
A.s=84　　　B.s=118　　　C.s=108　　　D.s=105
6.(2022衢州期末,11)某Python程序段如下:
def doit(x):
　　if x>=6:
　　　　ans=1
　　else:
　　　　ans=3*doit(x+1)+2*doit(x+2)
　　return ans
print(doit(3))
程序运行后,输出的结果为(　　)
A.17　　　B.21　　　C.61　　　D.62
考点三　数据排序
1.(2023浙江1月选考,10,2分)列表s包含8个互不相等的元素,即s[0],s[1],s[2],…,s[7],有如下 Python程序段:
n=8
for i in range(1,n-1):
　for j in range(1,n-i-1):
if s[j]>s[j-1]:
　　s[j],s[j-1]=s[j-1],s[j]
该程序段实现的是(　　)
A.s[0]到s[5]的降序排列
B.s[1]到s[6]的降序排列
C.s[1]到s[7]的升序排列
D.s[2]到s[6]的升序排列
2.(2024届名校协作体联考,10)有如下Python程序:
a=[12,45,45,63,0,0,63]
cnt=0
for i in range(1,len(a)):
　　j=i-1
　　t=a[i]
　　while j>=0 and t>a[j]:
　　　　 a[j+1]=a[j]
　　　　 j=j-1
　　　　 cnt=cnt+1
　　a[j+1]=t
print(cnt)
运行该程序后,输出的结果是(　　)
A.8　　　B.10　　　C.11　　　D.13
3.(2024届浙南名校联考,12)有如下Python程序段:
from random import randint
x=randint(2,4)*2
a=[9,2,5,1,3,4,8,7]
n=len(a)
for i in range(0,n-1):
　　k=i
　　for j in range(i+1,x):
　　　 　if a[k]>a[j]:
　　　　　　k=j
　　if i!=k:
　　　 　a[k],a[i]=a[i],a[k]
print(a)
执行后,输出结果不可能是(　　)
A. [1,2,3,4,5,7,8,9]
B. [1,2,3,4,5,9,8,7]
C. [1,2,5,9,3,4,8,7]
D. [1,2,3,4,5,9,7,8]
4.(2024届天域全国名校协作体联考,11)列表s存有4个整数,有如下Python程序段:
n=len(s)
f=[1]*n
for i in range(n-1):
　 　for j in range(i+1,n):
if s[j]>=s[i]:
　　f[j]+=1
else:
　　f[i]+=1
print(f)
该程序段实现的功能是标记列表中每个数值的名次值,名次排序的规则是(　　)
A.数值越大名次值越大,同数值先出现的名次值小
B.数值越大名次值越大,同数值先出现的名次值大
C.数值越大名次值越小,同数值先出现的名次值小
D.数值越大名次值越小,同数值先出现的名次值大
5.(2022绍兴诸暨期中,11)有如下Python程序段:
b=[56,80,10,31,24,52,66,49]
n=len(b)
for i in range(1,3):
　for j in range(0,n-i):
　　　if b[j]>b[j+1]:
　　　　b[j],b[j+1]=b[j+1],b[j]
经过该程序段“加工”后,列表b中的元素为(　　)
A.[10,24,31,49,52,56,66,80]
B.[10,31,24,52,56,49,66,80]
C.[56,10,31,24,52,66,49,80]
D.[10,24,31,52,49,56,66,80]
6.(2022绍兴柯桥期末,11)对一组数据采用冒泡排序算法进行排序,若第一趟排序完成后的数据序列为31,24,23,15,20,10,则该数据序列的原始顺序不可能是(　　)
A.24,23,15,31,10,20
B.24,23,15,20,31,10
C.24,31,23,15,10,20
D.23,24,15,20,31,10
考点四　数据查找
1.(2022 Z20名校联盟联考,9)某Python程序如下:
import random
key=random.randint(35,45)*2
i=0;j=len(a)-1;s=[]
while i<=j:
　　m=(i+j+1)//2
　　s.append(a[m])
　　if key　　　j=m-1
　　else:
　　　i=m+1
数组a中的元素为“58,69,78,80,83,84,90,90,95”,则执行该程序段后,数组s 中的元素不可能为(　　)
A.83,90,95　　　　B.83,78,80
C.83,90,90,84　　　　D.83,78,69,58
2.(2022百校联考,12)某程序段如下:
a=[9,15,19,20,23,36,78,87,96,100]
ans=[];i=0;j=9
key=int(input("请输入待查数据:"))
flag=False
while i<=j and not flag:
　　m=(i+j)//2
　　ans.append(a[m])
　　if a[m]==key:
　　　flag=True
　　elif a[m]>key:
　　　j=m-1
　　else:
　　　i=m+1
print(ans)
执行该程序后,当输入的key值为15时,输出的结果是(　　)
A.[23,15]　　　　B.[23,19,15]
C.[20,15]　　　　D.[20,19,15]
3.(2022名校协作体联考,12)某算法的Python程序段如下:
key=randint(0,3)*2+13
i,j,c=0,len(a)-1,0
while i<=j:
　m=(i+j+1)//2
　if a[m]>=key:
　　i=m+1
　else:
　　j=m-1
　c+=1
列表a=[23,21,19,18,16,15,14,11],该程序段执行后,下列说法不正确的是(　　)
A.i的值为j+1　　　　B.i的值可能是8
C.j的值可能是5　　　　D.c的值一定是3
4.(2022诸暨海亮月考,12)下列程序实现了输入k,找出大于k的数据的起始索引位置并显示。
a=[1,3,3,5,5,7,10,11,12,15]
n=10
k=int(input())
i=-1
j=　　　
while i < j:
　　m=(i+j+1)//2
　　if k < a[m]:
　　　　j=　　
　　else:
　　　　i=m
L=　　
print(">",k,"的数据索引起始位置为",L)
上述程序段横线处语句依次为(　　)
A.n　m-1　i　　　　B.n-1　m-1　i+1
C.n　m+1　i　　　　D.n-1　m+1　i+1
5.(2022诸暨期末,12)有如下二分查找程序段:
　#列表a存放整数升序数据,代码略
　key=int(input())
　f=[0]*9
　i=0;j=8
　while i<=j:
　　　m=(i+j)//2
　　　f[m]=1
　　　if a[m]>key:
　　　　　 j=m-1
　　　else:
　　　　　i=m+1
　print(f)
输入待查找数据,执行该程序段后,下列选项中,列表f的值不可能是(　　)
A.[0,0,0,0,1,1,1,0,0]
B.[1,1,0,0,1,0,0,0,0]
C.[0,1,0,0,1,0,1,0,0]
D.[0,0,0,0,1,0,1,1,0]
6.(2022绍兴诸暨期中,19)小明学了排序和查找算法后,编写了一个处理成绩的程序,功能如下:程序运行时,首先从Excel文件中读取n个学生的技术成绩存储在列表a中,并对列表中的数据按升序进行排序;输入成绩 key,统计并输出共有多少位同学的成绩大于该成绩。
实现上述功能的Python程序如下,请在程序划线处填入合适的代码。
#从Excel文件中读取n个学生的技术成绩存储在列表a中,代码略
#对列表a中的元素进行升序排序
n=len(a)
for i in range(n-1):
　　for j in range(0,n-i-1):
　　　　if　　①　　:
　　　　　　a[j],a[j+1]=a[j+1],a[j]
print (a)
#输入成绩 key,统计并输出共有多少位同学的成绩大于该成绩
key=int(input("please input key:"))
i,j=0,n-1
while i<=j:
　　m=(i+j)//2
　　if　　②　　 :
　　　　j=m-1
　　else:
　　　　i=m+1
print("共有"　　③　　+ "位同学大于等于该成绩。")
专题综合练
题组一
1.(2024届A9协作体返校考,11)有如下Python程序段:
import random
a=[1,3,4,6,6,6,9,9,11,12]
key=random.randint(2,5)*2
i,j=0,9
while i<=j:
m=(i+j)//2
if key　　j=m-1
else:
　　i=m+1
print(j)
执行该程序段后,输出的结果不可能是(　　)
A.2　　　B.3　　　C.5　　　D.7
2.(2024届Z20联盟联考,10)有如下Python函数:
def trans(num,n):
s="0123456789ABCDEF"
if num　　return s[num]
else:
　　return trans(num//n,n)+s[num%n]
执行语句a=trans(394,16)后,a的值为(　　)
A.19A　　　B.1810　　　C.180　　　D.18A
3.(2024届七彩联盟联考,10)有如下程序段:
def cal(n):
if n<=1:
　　return 1
if n % 2==0:
　　return 2*cal(n-1)
return 1+cal(n-1)
执行语句k=cal(5),则k的值为(　　)
A.6　　　B.7　　　C.10　　　D.11
4.(2024届强基联盟统测,10)有如下程序段:
def fun(k):
if k==1:
　　return "1"
elif k%2==0:
　　return fun(k-1)+str(k%2)
else:
　　return str(k%2)+fun(k-1)
执行语句s=fun(5),则s 的值为(　　)
A."00111"　　　　B."11010"
C."11100"　　　　 D."10110"
5.(2024届新阵地联盟联考,10)有如下Python程序:
import random
def func(n):
if n==1:
　　return 1
elif n==2:
　　return 2
elif n%2==1:
　　return 2*func(n-2)+func(n-1)
else:
　　return func(n-2)+2*func(n-1)
p=random.randint(3,6)
print(func(p))
执行程序后,输出结果不可能为(　　)
A.4　　　B. 10　　　C. 12　　　D. 18
6.(2024届天域全国名校协作体联考,10)某递归函数如下所示:
def hs(m):
if m<=1:
　　f=1
else:
　　f=hs(m-1)+hs(m-2)
return f
ans=0
for i in range(5):
if hs(i)%2==1:
　　ans+=1
print(ans)
程序运行后,输出的结果是(　　)
A.2　　　B.3　　　C.4　　　D.5
7.(2023十校联盟联考,12)某二分查找算法的Python程序段如下:
import random
key=random.randint(0,4)*2+5
n=10;ans=0
a=[4,5,5,8,9,11,11,13,15,17]
i=0;j=n-1
while i<=j:
m=(i+j)//2
if a[m]<=key:
i=m+1
else:
j=m-1
ans+=a[m]
print(ans)
执行该程序段后,ans的值不可能是(　　)
A.19　　　B.27　　　C.37　　　D.44
8.(2024届七彩联盟联考,15)某工厂每天会收到多个订单,有n台机器对零件进行加工。为减少机器的损耗,需要在满足所有订单加工的情况下(订单即到即加工),机器开启数量尽量少。若开启n台机器不能满足订单即到即加工,则计算所有订单最少的平均等待时间。若给定某天内所有的订单信息,请计算需要开启的机器数量以及订单平均等待时间,代码运行效果图如图所示(注意:若上一个订单结束时间为9:00,下一个订单开启时间最早为9:00)。
订单信息如下:(批次,到达时间,加工时间min)
(A1,9:00,30)(A2,11:30,50) (A3,10:40,50)(A4,10:00,60)(A5,9:20,40)(A6,11:00,20)(A7,10:20,40)(A8,9:30,20)
机器数量:2
2台机器全部开启,订单平均等待2.5min
第1台机器:
A1:09:00~09:30,A8:09:30~09:50,A4:10:00~11:00,A3:11:00~11:50
第2台机器:
A5:09:20~10:00,A7:10:20~11:00,A6:11:00~11:20,A2:11:30~12:20
请回答下列问题:
(1)上图所示的例子中,若机器有10台,则只需要开启　　　　台机器。
(2)定义如下data_sort(a)函数,参数a为列表,列表中每个元素包含三个数据项,依次分别对应订单批次、到达时间、加工时间(时间均转为分钟)。该函数实现将列表a按照订单到达时间升序排序。
def data_sort(a):
for i in range(len(a)):
　　for j in range(len(a)-i-1):
　　　　if　　　　:
　　　　　a[j],a[j+1]=a[j+1], a[j]
①划线处填入的语句为　　　　　　　,可实现上述功能。
②若将加框处语句写错为range(i,len(a)-1),则下列4组数据中,列表a的值为　　　(单选,填字母)时不能测试出问题。
A.[['A1',100,30],['A2',120,30],['A3',110,30],['A4',140,30],['A5',130,30]]
B.[['A1',120,30],['A2',110,30],['A3',100,30],['A4',130,30],['A5',140,30]]
C. [['A1',110,30],['A2' ,140,30],['A3',130,30],['A4',100,30],['A5',120,30]]
D.[['A1',110,30],['A2',120,30],['A3',130,30],['A4',140,30],['A5',100,30]]
(3)实现计算开启机器数量的部分Python程序如下,请在划线处填入合适的代码。
def huan(n):
#将分钟转换为时间AA:BB格式,返回值为字符串,代码略
#读取文件中的信息,并存储在列表order中,代码略
data_sort(order)
n=int(input("机器数量:"))
for i in range(len(order)):
order[i].append(-1)
#order[i]追加一个元素-1
mach=[-1]* n
num, wait=0,0
for i in range(len(order)):
k=-1
time=-1
for j in 　　①　　:
　　t1=mach[j]
　　if k==-1:
　　　　k=j
　　　　time=order[t1][1]+order
[t1][2]
　　else:
　　　　t2=mach[k]
　　　　if order[t1][1]+order[t1][2]　　　　　　k=j
　　　　　　time=order[t1][1]+order
[t1][2]
if k==-1 or num　 mach[num]=i
　 num+=1
　　else:
　 order[i][3]=mach[k]
　 mach[k]=i
　 if time>order[i][1]:
　　　　wait +=time-order[i][1]
　　　　order[i][1]=time
if numprint("只需开启"+str(num)+"台机器")
else:
print(str(n)+"台机器全部开启,订单平均等待"+str(round(wait/len(order),2))+"min")
for i in range(num):
print('第'+str(i+1)+'台机器: ')
p=mach[i]
ans=' '
while p!=-1:
　　ans=order[p][0]+':'+huan(order[p][1])+'~'+huan(order[p][1]+order[p][2])+','+ ans
　　p=　　③　　
　　print(ans[:-1])
9.(2024届名校协作体联考,15)有一款益智游戏,规则如下:轨道上有不同颜色的珠子连成珠串,玩家可以通过炮台发射若干珠子,每次发射一颗珠子到珠串中的某位置,形成新的珠串。当新珠串中出现3颗及以上颜色相同的连续珠子时,这些连续的同色珠子会被消除,并获得相应积分,若消除后仍有符合条件的同色珠子,会继续被消除。记分规则为:在被消除的连续珠子中,前面3颗直接记3分,其余的珠子每颗记2分,例如有5颗相同颜色的连续珠子被消除,可获得7分。程序运行过程如图所示。
现轨道的珠串为:
-1->3->1->5->4->2->2->1->2->2
当前珠子的颜色为:1
请输入当前发射位置:7
当前珠子的颜色为:1
请输入当前发射位置:7
当前珠子的颜色为:4
请输入当前发射位置:5
当前珠子的颜色为:4
请输入当前发射位置:5
最终得分为11
轨道中剩余的珠串为:
-1->3->1->5
编写程序模拟游戏的实现过程,珠子的颜色用数字表示,为方便处理,在珠串最前面加入一颗不可消除的珠子,颜色值为-1。请回答下列问题:
(1)若珠串为-1,2,2,3,3,2,2,将颜色为3的珠子发射到颜色为2和3的珠子之间,可获得积分为　　　　。
(2)定义如下insert(t,pos)函数,函数功能是将颜色为t的珠子,插入到当前珠串中的第pos颗珠子后面(列表link存储珠串的相关数据,例如link中某元素的值为[3,2],3表示某颗珠子的颜色,2表示与该珠子相邻的下一颗珠子的存储地址,变量 head保存珠串第一个珠子的存储地址),请在划线处填入合适的代码。
def insert(t,pos): #将颜色为t的珠子,插入到当前珠串第pos颗珠子的后面
p=head
while pos>1:
　　pos-=1
　　p=link[p][1]
link.append(　　　　)
link[p][1]=len(link)-1
(3)定义如下fun()函数,函数功能是:查找珠串里最早出现的可消除珠串,函数返回ret,ret由该珠串起始珠子的前一颗珠子位置和该珠串的连续长度组成。
def fun():
p=head;st=head
pre=p
num=0
lastcolor=-1
ret=[-1,0]
while p!=-1:
　　t=link[p][0]
　　if t!=lastcolor:
　　　　if num>=3:
　　　　　　ret=[st,num]
　　　　　　break
　　　　lastcolor=t
　　　　st=pre
　　　　num=1
　　else:
　　　　num+=1
　　pre=p
　　p=link[p][1]
if num>=3:
ret=[st,num]
return ret
若将函数中加框处代码删除,会导致某些情况下无法得到符合函数功能的结果。调用fun()函数,下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.head=4
link=[[2,3],[1,0],[1,1],[2,-1],[-1,2]]
B.head=0
link=[[-1,1],[2,3],[2,4],[2,2],[1,-1]]
C. head=1
link=[[2,-1],[-1,3],[2,0],[1,4],[2,2]]
D.head=4
link=[[2,-1],[1,0],[1,1],[1,2],[-1,3]]
(4)实现模拟游戏过程的部分Python程序如下,请在划线处填入合适的代码。
def clear(g):#根据fun函数的返回值对珠串进行消除,并统计获得本次消除的积分
p=g[0]
q=p
length=g[1]
ret=　　①　　
while length>=0:
　　q=link[q][1]
　　length-=1
link[p][1]=q
return ret
def traverl():
　　#将轨道中珠串按序输出,代码略
head=7
link=[[1,3],[1,8],[2,1],[5,5],[2,2],[4,4],[3,0],[-1,6],[2,9],[2,-1]]
print("现轨道的珠串为: ")
traverl()
points=0
que=[1,1,4,4]#保存炮台中待发射珠子的颜色
qhead=0
qtail=4
while qhead!=qtail:
　　print("当前珠子的颜色为: ",que[ghead])
　　s=int(input("请输入当前发射位置:"))
　　insert(que[qhead],s)
　　qhead+=1
　　g=fun()
　　while g!=[-1,0]:
　　　　points+=clear(g)
　　　　　　②　　
print("最终得分为",points)
print("轨道中剩余的珠串为: ")
traverl()
10.(2024届发展共同体联考,15)某业务服务大厅共有m个服务窗口(编号为0~m-1),服务大厅根据服务对象的优先等级(等级分为1~10,数字越大优先级越高)从高到低依次分配窗口并提供服务。某个时间段内(该时间段起始时刻各窗口都空闲着),服务对象按服务优先等级从高到低排队后依次到空闲的窗口享受服务,服务优先等级相同时,先到达的先享受服务。由于办理的业务不同,每个服务对象的服务时长(单位:分钟)可能是不相同的。按照上述服务规则,问所有服务对象完成业务办理需要多少时间。一个服务对象业务办理结束,另一个服务对象马上到该窗口接受服务,中间浪费的时间忽略不计。
图a描述了5个服务对象的信息,按照服务规则确定的服务次序如图b所示。
到达序号 服务优先等级 服务时长
1 7 10
2 6 12
3 4 32
4 5 24
5 6 8
图a
到达序号 服务优先等级 服务时长 服务次序
1 7 10 1
2 6 12 2
3 4 32 5
4 5 24 4
5 6 8 3
图b
若服务大厅提供2个服务窗口(m=2),则所有服务对象完成业务办理需要50分钟。具体方案可以是:0号窗口依次服务到达序号为1、5、3的对象,1号窗口依次服务到达序号为2、4的对象。请回答下列问题:
(1)若有6个服务对象的信息如图c所示,根据上述服务规则,在提供3个服务窗口的情况下,所有服务对象完成业务办理需要　　　　分钟。
到达序号 服务优先等级 服务时长
1 3 2
2 5 7
3 4 13
4 1 5
5 8 12
6 4 11
图c
(2)定义如下sort_lst(lst)函数,参数 lst是所有服务对象信息构成的列表。函数的功能是将列表lst 按照服务对象的优先等级降序排列并构成链表,返回排序后的链表及其头指针。
def sort_lst(lst):
for i in range(len(lst)):
　　lst[i].append(-1)
head=0
for i in range(1,len(lst)):
　　p=head
　　while p!=-1:
　　　　if lst[p][1]>=lst[i][1]:
　　　　　　q=p
　　　　　　p=lst[p][3]
　　　　else:
　　　　　　break
　　if p==head:
　　　　lst[i][3]=head
　　　　head=i
　　else:
　　　　lst[q][3]=i
　　　　lst[i][3]=p
return lst,head
若lst列表依次存储图c所示的服务对象信息,如lst[0]为[1,3,2],各数据项依次表示服务对象的到达序号,服务优先等级及服务时长。调用sort_lst(lst)时,程序中加框处的语句“q=p”总共执行　　　　次。
(3)计算时间段内服务对象完成业务办理所需时间的部分Python程序如下,请在划线处填入合适的代码。
def proc(lst,p,n,m):
s=[0]*m
for i in range(m):　　#前m个人直接开始服务,等待时间为0
　　if p==-1:
　　　　break
　　s[i]=lst[p][2]
　　　　①　　
ans=0
while p!=-1 :
　　k=s[0]　　#找出正在被服务的对象中最早结束的一个
　　for j in range(1,m):
　　　　if s[j]　　　　　　k=s[j]
　　ans+=k
　　for j in range(m):
　　　　s[j]-=k
　　　　if　　②　　:
　　　　　　s[i]=lst[p][2]
　　　　　　p=lst[p][3]
k=s[0]
for i in range(m):
　　if s[i]>k:
　　　　k=s[i]
　　③　　
print("所有服务对象完成业务办理需要" ,str(ans),"分钟")
'''
读入服务对象总数n和窗口数m
按到达序号读入n个服务对象的信息到列表lst中,如图c为:lst=[[1,3,2],[2,5,7],[3,4,13],[4,1,5],[5,8,12],[6,4,11]]
代码略
'''
lst,head=sort_lst(lst)#对lst按照服务对象优先等级降序排序
proc(lst,head,n,m)
11.(2024浙江1月选考,15,9分)某项活动有n个单位(编号1到n)参加,需将员工分成若干个小组,每个小组的人数上限为m,小组编号按新建次序从1开始编号。分组时,首先按单位编号次序依次在各单位内部分组,每m人分配到一个新建小组中,不足m人的剩余员工暂不分配;然后按剩余员工人数由大到小的顺序,依次为各单位剩余员工分配小组。
若某单位剩余员工人数为k,则分配方法为:在已建的小组中查找空位数(该小组还可容纳的人数)大于或等于k的小组,如果找到的小组有多个,则选择空位数最少的小组,将此k人分配到该小组中; 如果没有找到,则新建一个小组,将此k人分配到该小组中。
设n为5,m为20,各单位员工人数及单位内部的分组过程如图a所示,各单位剩余员工的分组过程如图b所示。
编写程序:给定各单位编号及员工人数,根据上述方法进行分组处理,按单位编号次序输出各单位所分配的分组编号。请回答下列问题:
(1)由题意可知,若仅将图a中1号单位的员工人数修改为25,然后对图中5个单位重新分组,则1号单位所分配的分组编号为　　　　。
(2)定义如下bubble_sort(lst)函数,参数lst的每个元素由单位编号和剩余员工人数2个数据项组成。函数的功能是根据每个单位的剩余员工人数,对lst进行降序排序。
def bubble_sort(lst):
　　n=len(lst)
　　for i in range(0,n-1):
for j in range(n-1,i,-1):
　　if lst[j-1][1]　　　　tmp=lst[j]
lst[j]=lst[j-1]
lst[j-1]=tmp
if lst[i][1]==0:
　　break
　　return
调用该函数,若lst为[[1,0],[2,0],[3,18],[4,0],[5,19],[6,17]],请回答①和②两个问题。
①框中的程序段第1次执行后,关于lst中的剩余员工人数,下列说法正确的是　　　 (单选,填字母)。
A.lst[0][1]数值最小
B.lst[0][1]数值最大
C.lst[5][1]数值最小
D.lst[5][1]数值最大
②框中的程序段执行的次数为　　　　。
(3)实现分组功能的部分Python程序如下,程序中用到的列表函数与方法如图c所示,请在程序中划线处填入合适的代码。
函数与方法 功能
w.append(x) 在列表w末尾添加元素x
x.w.pop() 将列表w末尾元素赋值给x,并将其从w中删除
图c
def group(data,m):
n=len(data)
a=[]
for i in range(n+1):
a.append([])　　　#a[i]初始化为空列表,存放编号为i的单位所分配的分组编号
gnum=0
for i in range(n):　　#各单位内部分组
　　while data[i][1]>=m:
　　　　gnum+=1
k=data[i][0]
a[k].append(gnum)
　　　①　　　
bubble_sort(data)　　#根据每个单位的剩余员工人数,对data 进行降序排序
b=[]
for i in range(m):
b.append([])
i=0　　　#对剩余员工分组
while i　　　　　②　　　
while j　　j+=1
if j　　v=b[j].pop()
else:
　　gnum+=1
　　v=gnum
a[data[i][0]].append(v)
　　　③　　　
i+=1
#输出各单位的分组编号,代码略
'''
读取小组人数上限存入m;读取1至n号单位的数据,依次存入列表data的data[0]至data[n-1]中。
data[i]包含2个数据项,data[i][0],data[i][1]分别存放单位编号及员工人数,代码略
'''
group(data,m)
12.(2024届浙南名校联盟联考,15)某工厂将送达的各批次物品按品种打包。小李将各批次物品信息按送达时间顺序合并,得到如图a-2所示数据 data。同一个包裹只能装入同一品种任意批次的物品,当某一个品种物品A送达使得已送达的该品种物品总质量超过m时,则将在该物品之前送达的物品按质量由大到小依次装入包裹,其余质量不足m的品种,按各品种依次装入包裹。编写程序,读取物品合并更新后的信息,按送达时间顺序打包,输出各包裹中的物品序号,运行结果如图b所示。
序号 品种 送达时间 批次 质量(千克)
1 2 8:35 1 6
2 1 8:50 1 8
3 0 9:10 1 2
4 0 9:15 1 4
序号 品种 送达时间 批次 质量(千克)
1 0 8:30 2 3
序号 品种 送达时间 批次 质量(千克)
1 0 8:40 3 4
图a-1
序号 品种 送达时间 批次 质量(千克)
1 0 8:30 2 3
2 2 8:35 1 6
3 0 8:40 3 4
4 1 8:50 1 8
5 0 9:10 1 2
6 0 9:15 1 4
图a-2
m=10
data=[[1,0,'8:30',2,3],[2,2,'8:35',1,6],[3,0,'8:40',3,4],[4,1,'8:50',1,8],[5,0,'9:10',1,2],[6,0,'9:15',1,4]]
第1个包裹中品种为0,各物品的序号依次是:3,1,5,
第2个包裹中品种为0,各物品的序号依次是:6,
第3个包裹中品种为1,各物品的序号依次是:4,
第4个包裹中品种为2,各物品的序号依次是:2,
图b
请回答下列问题:
(1)送达物品信息合并后如图a-2所示,若包裹装入物品质量不能超过8千克,则首先打包完成的包裹中装入品种为0,各物品的序号依次是　　　　。
(2)定义data_sort(lst)函数。先将数据(见图a-1)合并得到 lst列表(见图a-2),函数data_sort(lst)的功能是对lst列表按送达时间升序排列,并对序号进行更新。
def data_sort(lst):
for i in range(n-1):#n为数据个数
　　for j in range(n-1,i,-1):
　　　　if lst[j][2]< lst[j-1][2]:
　　　　　　lst[j],lst[j-1]=lst[j-1],lst[j]
　　lst[i][0]=i+1
return lst
执行上述代码后,　　　　(填写:能/不能)正确得到图a-2中的数据。
(3)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
def pack(k):　#对品种k已送达待打包的物品按质量由大到小输出
#部分代码略
p=b[k][1]
num+=1
print("第"+str(num)+"个包裹中品种为"+str(k)+",各物品的序号依次是: ",end=" ")
while p!=-1:
　　print(data[p][0],end=",")
　　p=x[p]
print()
#合并后排序得到n件物品的数据存储在数组data中并输出,包裹最大承受质量为m千克。物品品种的数量是sn,代码略
b=[[0,-1] for i in range(sn)]
x=[-1 for i in range(n)]
num=0
for i in range(n):
k=data[i][1]
if b[k][0]+data[i][4]>m:
　　pack(k)
　　b[k]=[0,-1]
p=　　①　　
if p==-1:
　　b[k][1]=i
else:
　　if data[i][4]>data[p][4]:
　　　　b[k][1]=i
　　　　　　②　　
　　else:
　　　　q=-1
　　　　while　　③　　:
　　　　　　q=p
　　　　　　p=x[p]
　　　　x[q]=i
　　　　x[i]=p
b[k][0]+=data[i][4]
#质量不足m的品种,按品种依次装入包裹
for i in range(sn):
if b[i][1]!=-1:
　　pack(i)
13.(2024届新阵地联盟联考,15)进入新学期第一天,班主任老师将班上N个同学(学号为1~N)排成一排,分配座位。从排队到分配座位步骤如下:
步骤一:先将1号同学安排进队;
步骤二:2~N号同学由老师依次指定入队位置,如学号为i的同学由老师指定站在队中某位同学的左侧或右侧;
步骤三:所有同学按照上述方法入队完毕后,以2人一组的方式依次分配到四个组别中;
步骤四:输出每组学生的名单。
请回答下列问题。
(1)若某班有4位同学,学号为1~4,完成步骤一后,执行步骤二的指令3次,每次指令包含两个整数k和p(p为0或1)。若p为0,则表示插在k号同学的左侧,p为1则表示插在k号同学的右侧。若三条指令分别为1 0、2 1、1 0,则执行指令后队伍从左到右学号分别为　　　　。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
#insert(k,x)函数的功能是在k号的右侧插入x号同学
#L和R列表分别用于记录每位同学的左侧和右侧的同学学号
def insert(k,x):
R[x]=R[k]
L[x]=k
　　①　　
R[k]=x
L=[0]*100;R=[0]*100;vis=[0]*100
insert(0,1)　　#0的右边插入1号同学
#info列表存储各学生姓名和学号,格式如[["张三",1],["李四",2]…],代码略
n=int(input("请输入同学人数:"))
for i in range(2,n+1):
k=int(input("请问插入在几号同学旁边 "))
p=int(input("请输入该同学的左侧还是右侧"))
if p==0:
　　　　②　　
else:
　　insert(k, i)
q=[[] for i in range(4)]
i=m=0
　　③　　
while x!=0:
q[i].append(x)
m=m+1
if m%2==0:
　　　　④　　
x=R[x]
for i in range(4):
for j in q[i]:
　　print(info[j-1][0], end="　")
print()
14. (2023学军中学月考,15)学校为了使本校毕业生能以更好的状态参加高考,都会创造条件向上级申请在本校设立标准化考点,让学生能在本校参加考试。标准化考点要求很多,其中之一就是各考场内的座位安排必须是蛇形排列,保证使用A、B卷的同学能完全错开,如图a所示。小明用Python编写了一个模拟考场座位编排程序,程序运行结果如图b所示,每个座位号占4位宽度右对齐。输出程序如下,请在划线处填入合适的代码。
def px(lst):
for i in range(len(lst)-1):
k=i
for j in range(　①　):
if lst[j]>lst[k]:
k=j
if k!=i:
lst[i],lst[k]=lst[k],lst[i]
def gssc(t,n):　　　　#将字符t按n个字符宽度输出
t="　"* (n-len(t))+t
return t
n=int(input('请输入行数:'))
m=int(input('请输入列数:'))
a=[]
for j in range(m):
a.append([])
for i in range(n):
a[j].append(　②　)
for i in range(m):
if　③　:
px(a[i])
for i in range(n):
st=" "
for j in range(m):
tmp='A'
if a[j][i]%2==1:
tmp='B'
st+=　④　　　#每个座位号按4位输出
print(st)
题组二
1.(2024届名校协作体联考,11)定义如下函数:
def f(k):
if k<=3:
　　print(k)
　　return
for i in range(1,4):
　　f(k-i)
return
执行语句f(6),则f(3)被调用的次数为(　　)
A.1次　　　B.2次　　　C.3次　　　D.4次
2.(2024届强基联盟联考,10)执行下列Python代码,输出结果为(　　)
def f(s):
m=len(s)
if m==1:
　　return int(s)
else:
　　return f(s[:m-1])+f(s[m-1])
print(f("101"))
A.11　　　　B.2　　　
C.5　　　　D.101
3.(2024届百校起点调研测试,10)定义如下递归函数:
def f(a,n):
n=n-1
if n==0:
　　return a
else:
　　return f(a-1,n)+f(a+1,n)
print(f(5,3))
程序运行后,输出的结果是(　　)
A.10　　　B.20　　　C.30　　　D.40
4.(2022宁波九校联考期末,12)某二分查找算法的 Python程序段如下,运行该段代码后,输出的结果不可能是(　　)
import random
a=[10,20,30,40,50,60,70,80]
key=random.choice(a);i,j=0,len(a)-1
s=" "
while i<=j:
　　m=(i+j)//2
　　if key==a[m]:
　　　　s=s+"M";break
　　elif key　　　　j=m-1;s=s+"L"
　　else:
i=m+1;s=s+"R"
print(s)
A.LLM　　　　B.LRM
C.RRRM　　　　D.RRLM
5.(2023浙江开学考,12)峰值元素指数组中其值大于左右相邻值的元素,如序列3、8、4、1中8为峰值元素。一个数组r包含多个峰值元素,现需要找出其中一个峰值元素所在的位置(默认第一个数的左侧和最后一个数的右侧为0,即序列1、2、3中3也为峰值元素)。现有实现该功能的Python程序如下:
i=0;j=6
while i　　m=(i+j)//2
　　if a[m+1]>a[m]:
　　　　i=m+1
　　else:
　　　　j=m
print("峰值位置是",i)
数组a=[10,2,25,17,20,21,9],执行该程序后,输出的值为(　　)
A.0　　　B.2　　　C.5　　　D.8
6.(2023十校联盟联考,9)有如下Python程序段:
def trans(m,n):
if m!=0:
　　r=m%n
　　return trans(m//n,n)+str(r)
else:
　　return "0"
a=int(input("a="))
b=int(input("b="))
print(trans(a,b))
执行该程序段,依次输入11和2,则输出的结果是(　　)
A.1011　　　　B.1101
C.01011　　　　D.11010
7.(2023浙南名校联盟联考,8)小王走楼梯,每次走1个台阶或2个台阶,问小王走n个台阶时,有多少种不同的走法 现编写代码如下:
def upstairs(n):
if n==0 or n==1:
return 1
else:
return upstairs(n-1)+upstairs(n-2)
n=int(input('请输入楼梯有几个台阶:'))
way=upstairs(n)
print(way)
当输入的楼梯有10个台阶时,请问有多少种走楼梯的方法(　　)
A.88　　　B.89　　　C.90　　　D.91
8.(2024届天域全国名校协作体联考,15)计算机运行多个任务(又称进程)时,需要进行调度。有的进程需要优先响应,例如用户的交互操作,此时就需要暂停当前运行的进程,让CPU先执行需要优先响应的进程,这称为抢占。操作系统需要设计调度算法,来决定CPU运行进程的顺序。
优先级抢占式调度算法是一种简单的调度算法,规则如下:
1)将进程分为m个优先级,设置m个等待队列,分别对应每一级优先级。
2)每个进程具有三个要素:到达时间,运行所需时长,优先级数(数越大优先级越高)。
3)相同优先级的进程,按照先到先服务的原则依次执行。
4)同一时刻中,先将到达的进程都加入队列,再按照优先级进行分配。
5)只有当k级队列为空的时候,才会为k-1级队列队首的进程分配时间。
6)进程Pi运行时,如果有优先级更高的进程Pj到达,则立即发生抢占,先执行Pj,并将进程Pi未执行完的部分,重新加入Pi优先级对应的队列末尾,等待继续执行。
编写程序模拟CPU分配计算资源的过程,已知按照到达时间升序排序的进程数据(包含到达时间、运行时长、优先级),计算并输出每个进程最终处理完成的时间。(时间单位均为毫秒)
请回答下列问题:
(1)有4个进程A、B、C、D如图所示。
进程 到达时间 运行时长 优先级
A 0 7 1
B 2 4 2
C 4 1 3
D 5 4 2
由优先级抢占式调度算法的规则可知,0毫秒时进程A到达并执行;2毫秒时进程B到达,B的优先级高于A,发生抢占,A剩余的5毫秒回到队列1,B开始执行;4毫秒时进程C到达,C的优先级高于B,发生抢占,B剩余的2毫秒回到队列2,C开始执行;则进程D执行完的时刻为　　　　。
(2)模拟实现优先级抢占式调度算法Python程序如下,请在划线处填入合适的代码。
def insert(p,remain):
data[p][2]=remain　#更新进程剩余的运行时间
lvl=data[p][3]
if queinfo[lvl][0]==-1:
　　queinfo[lvl][0]=p
if queinfo[lvl][1]!=-1:
　　data[queinfo[lvl][1]][-1]=p
data[p][-1]=-1
queinfo[lvl][1]=p
m=int(input('设置优先级的数量m:'))
#输入列表data存储进程,data中的节点包含信息有[名称,到达时间,运行时长,优先级],代码略
#进程已经按到达时间升序排序
#例如: data=[['A',0,7,1],['B',2,4,2],['C',4,1,3],['D',5,4,2]]
for i in range(len(data)):
data[i].append(-1)
queinfo=[[-1,-1] for i in range(m+1)]
insert(0,data[0][2])#将第1个进程加入队列
time=data[0][1]
cnt=1　#所有队列内等待的进程总数
idx=1
lvl=m
while cnt > 0:
if queinfo[lvl][0]!= -1:
　　cur=queinfo[lvl][0]
　　queinfo[lvl][0]= data[queinfo[lvl][0]][-1]
　　cnt -=1
　　　　①　　
　　while idx=data[idx][1]:
　　　　if lvl>=data[idx][3] or time+data[cur][2]==data[idx][1]:
　　　　　　insert(idx, data[idx][2])
　　　　　　cnt+= 1
　　　　　　idx+= 1
　　　　elif time+data[cur][2]> data[idx][1]:
　　　　　　insert(idx, data[idx][2])#抢占的进程也先入队
　　　　　　cnt+=1
　　　　　　insert(cur,　　②　　)
　　　　　　cnt+=1
　　　　　　time=data[idx][1]
　　　　　　lvl=data[idx][3]
　　　　　　idx+=1
　　　　　　flag=True
　　　　　　break
　　if flag==False:
　　　　time=time+data[cur][2]
　　　　print("时刻", time,":进程", data[cur][0],"完成")
　　lvl=m
　　if　　　③　　:　#仍然有未到达的进程等待入队
　　　　insert(idx, data[idx][2])
　　　　cnt+=1
　　　　time=data[idx][1]
　　　　idx+=1
else:
　　lvl-=1
　　if lvl==0:
　　　　lvl=m
(3)若将以上程序中insert 函数内的加框处代码删除,会导致某些情况下无法得到符合程序功能的结果,下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.m=3
data=[['A',0,1,1],['B',1,1,2],['C',3,1,3]]
B.m=3
data=[['A',0,2,2],['B',1,2,3],['C',3,1,3]]
C.m=3
data=[['A',0,2,1],['B',1,2,3],['C',2,1,2]]
D.m=3
data=[['A',0,2,2],['B',1,2,3],['C',2,1,1]]
9.(2024届A9协作体联考,15)张三是一名计算机专业的大学生,为了帮助同学们学习专业相关的英语词汇,编写了一个简易字典程序。该程序中存放词汇数据库,在学习中输入英文单词,可以获得中文翻译结果。程序中的词汇数据库采用链表方式存储,首字母相同时按升序排序。查找单词时,首先根据首字母找到同首字母最小单词所在链表,再按照链表顺序查找该单词。
(1)根据题意,部分的单词库数据逻辑结构如图所示,查找单词"byte"的过程是"binary"→"bit"→"byte",补充图中空白单元格的值为　　　　。
列表索引 数据区域 指针区域
0 audio 音频 -1
1 binary 二进制数 6
2 byte 字节 -1
3 cursor 光标 -1
4 access 存取 1
5 cache 高速缓存 3
6 bit 比特 　　　
(2)wordlist(data,info)函数实现将词汇数据库data以链表的方式按字母序升序排列。info表示词汇数据库中各字母开头的最小单词位置,如info[0]表示字母a开头的最小单词在词汇数据库data中的位置。实现该功能的程序如下,请在划线处填入合适的代码。
def wordlist(data,info):
n=len(data)
for i in range(n):
　　data[i].append(-1)　#data[i]追加一个元素-1
for i in range(n):
　　d=data[i][0]
　　　　①　　
　　if info[k]==-1:
　　　　info[k]=i
　　else:
　　　　head=info[k]
　　　　q=head
　　　　while　　②　　:
　　　　　　p=q
　　　　　　q=data[q][2]
　　　　if q !=head:
　　　　　　data[p][2]=i
　　　　　　data[i][2]=q
　　　　else:
　　　　　　data[i][2]=head
　　　　　　　　③　　
return data,info
(3)searchword(data,info,key)函数实现单词的查找。程序如下,请在划线处填入合适的代码。
def searchword(data,info,key):
k=ord(key[0])-ord("a")
head=info[k]
p=head
while p != -1:
　　if data[p][0]==key:
　　　　return 　　　
　　p=data[p][2]
return "没有找到该单词"
#读取词汇数据库,存入列表data中,列表的每个元素包含2个数据项,分别为英文单词和中文翻译,如data = [['audio','音频'],['binary','二进制数']…],数据读取存入的代码略
info=[-1]* 26
data,info=wordlist(data,info)
key=input("请输入查找单词:").lower()　#转化为小写字母
res=searchword(data,info,key)
print(key,"查找结果是:",res)
10.(2024届强基联盟联考,15)某校针对高三高考成绩进行分析时,其中有两个主要指标:班级各科平均成绩和班级总分平均成绩。高考成绩保存在“kscj.csv”文件中,格式如图a所示,每行有四个项目,分别是“学号”“姓名”“学科”和“得分”,其中“学号”的前两位表示班级编号,后两位表示该学生班内编号,两种编号均从“01”递增编排。
设计如下Python程序,执行后输出上述两个主要指标,如图b所示。请回答下列问题。
(1)通读下列程序代码后,可知程序中各班级队列采用的数据结构为　　　　(选填,数组/链表)。
(2)函数dataToClassQue功能:根据班级编号,将数据分配到各个班级队列。请在划线处填入合适的代码。
def dataToClassQue(data):
num=len(data)
for i in range(num):
　　classId=data[i][0]
　　if queInfo[classId-1][0]==-1:
　　　　queInfo[classId-1][0]=i
　　else:
　　　　　　　
　　queInfo[classId-1][1]=i
return
(3)函数dataProcessing 功能:统计各班各科平均分和班总分平均分。请在划线处填入合适的代码。
def dataProcessing(data):
for classId in range(1,classNumber+1):
　　　　①　　
　　score=[[0,0] for i in range(10)]#班级各科平均分和人数初始化
　　p=queInfo[classId-1][0]
　　while p !=-1:
　　　　subjectId=data[p][3]
　　　　total+=data[p][4]
　　　　　　②　　
　　　　score[subjectId][1]+=1
　　　　p=data[p][-1]
　　for subjectId in range(10):
　　　　if score[subjectId][1]!=0:
　　　　　　t=　　③　　
　　　　　　averageScore[classId-1][subjectId]=round(t,1)
　　averageScore[classId-1][10]=round(total/score[0][1],1)
return
def readFile(data):
#读入原始学生数据,预处理后,存储到data中,代码略
#data数据格式:[[6,10,'白凯修',0,117,-1],[6,10,'白凯修',1,109,-1],……]
#每条记录包括班级编号,班内编号,姓名,学科编号,得分和预留值-1
return maxClassId#返回最大班级编号
def fmtPrint():
#格式化输出,如图b所示,代码略
return
#主程序
course={'语文':0,'数学':1,'英语':2,'物理':3,'化学':4,'生物':5,'政治':6,'历史':7,'地理':8,'技术':9}
data=[]　#存储读入的数据
classNumber=readFile(data)
queInfo=[[-1,-1] for i in range(classNumber)]　#初始化队列,用于存储各班级信息
averageScore=[[0 for k in range(11)] for i in range(classNumber)]
dataToClassQue(data)
dataProcessing(data)
fmtPrint()
11.(2024届百校起点调研测试,15)某医院的团体体检流程如下:
编号登记:为n位体检者设置体检编号1~n。
体检呼叫:体检项目处空闲时呼叫下一个体检者(编号小的优先),若多个项目同时呼叫,体检者到优先级小的项目处体检。仅考虑常规体检项目,各个项目的优先级及体检时间如图所示。
项目 名称 B 超 心 电 图 抽 血 尿 常 规 C14 检测 胸 透 一般 常规
优先级 0 1 2 3 4 5 6
时间 (min) 12 5 2 2 2 2 1
前去体检:各个体检项目之间相互独立,互不影响;病人排队体检和体检完毕到下一科室之间没有时间延迟。
(1)某个团队4人(分别用编号1,2,3,4表示)参加体检,开始体检后第5分钟,4号在检查　　　　(填写项目名称)项目。
(2)定义如下lst(n)函数,生成n人体检队列。若体检人数为4,则que生成结果如图所示。
队列索引号 体检编号 已检测项目
0 1 []
1 2 []
2 3 []
3 4 []
def lst(n):
que=[]
for i in range(n):
temp=[i+1,[]]
　　que.append(temp)
return que
若加框处语句改为:for i in range(1,n+1):
temp=[i,[]]
则执行语句lst(4),que的生成结果　　　(选填:相同/不同)。
(3)用Python程序模拟一个10人团队参加体检的流程。程序运行后,体检完成顺序如图所示。
体检完成顺序:
编号2:心电图→一般常规→抽血→尿常规→C14检测→胸透→B超
编号1:B超→抽血→尿常规→C14检测→胸透→一般常规→心电图
编号5:C14检测→胸透→一般常规→抽血→尿常规→B超→心电图
编号3:抽血→尿常规→C14检测→胸透→一般常规→心电图→B超
编号4:尿常规→C14检测→胸透→一般常规→抽血→心电图→B超
编号6:胸透→一般常规→抽血→尿常规→C14检测→心电图→B超
编号7:一般常规→抽血→尿常规→C14检测→胸透→心电图→B超
编号8:一般常规→心电图→C14检测→胸透→抽血→尿常规→B超
编号9:一般常规→胸透→抽血→尿常规→C14检测→心电图→B超
编号10:一般常规→尿常规→C14检测→胸透→抽血→心电图→B超
Python部分程序如下,请在划线处填入合适的代码。
n=10
head=0
que=lst(n)
tail=10
dis=[['B超',12],['心电图',5],['抽血',2],['尿常规',2],['C14检测',2],['胸透',2],['一般常规',1]]
t=[-1]*7#t记录各个项目当前体检的开始时间
f=[-1]* 7#f记录各个项目当前体检人员编号
def jh(num):
global tail #global能够实现在自定义函数中改变公共变量tail
p=head
while p　　if que[p][0]not in f and num not in que[p][1]:#p体检者等待中且未体检num项目
　　　　que[p][1].append(num)
　　　　　　①　　
　　　　t[num]=time
　　　　if len(que[p][1])==7:
　　　　　　temp=que[p]
　　　　　　for i in range(p,tail-1):
　　　　　　　　que[i]=que[i+1]
　　　　　　que[tail-1]=temp
　　　　　　tail-=1
　　　　break
　　p=p+1
time=0
while tail!=head:
i=0
while i<7:
　　if t[i]==-1:
　　　　jh(i)
　　elif　　②　　:
　　　　t[i]=-1
　　　　f[i]=-1
　　　　i-=1
　　i+=1
time+=1
print('体检完成顺序:')
for i in range(　　③　　):　#按体检完成顺序输出体检者及其体检项目顺序
item=que[i][1]
s=' '
for j in item:
　　s+=dis[j][0]+'→'
print('编号%d: %s'%(que[i][0],s[:-1]))
12.(2022名校协作体联考,16)某会务组根据参会者到达指定上车点的时间和每位参会者可以等待的时间信息,安排车辆接送参会者去宾馆(不考虑车子座位数量)。参会者到达上车点的时间和可以等待的时间用长度为7的字符串表示,例如“08:15 2”表示参会者当天8点15分到达上车点,最多等待2分钟(每个人的等待时间都小于10),那么该参会者最晚8点17分出发去宾馆(若有8点17分刚到的参会者也一同出发)。编写Python程序,统计接送n个参会者所需的最少车辆数。运行程序,显示所有参会者提交的信息,按到达时间先后排列,再显示所需的最少车辆数,程序运行结果如图所示。
(1)若将图中第4行“08:15 4”数据改为“08:15 1”,程序输出的结果是否会发生改变　　(A.会改变　B.不会改变)。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
a=['08:15 4','08:14 3','08:23 4','08:15 2','08:12 2','08:17 1','08:17 3','08:19 4','08:21 4','08:17 1']
def tran(str1):
　　ss=int(str1[:2])*60+int(str1[3:6])
　　return ss
for i in range(len(a)-1):
　　for j in range(len(a)-1,i,-1):
　　　if a [j]　　　　a[j],a[j-1]=a[j-1],a[j]
n=len(a)
b=[]
c=[]
for i in range(n):
　　b.append(tran(a[i][:5]))
　　c.append(b[-1]+int(a[i][6:]))
　　for j in range(i,0,-1):
　　　　　　①　　
　　　　if c[k]>c[j]:
　　　　　　b[k],b[j]=b[j],b[k]
　　　　　　c[k],c[j]=c[j],c[k]
　　　　else:
　　　　　　break
sum=0
flag=[False for i in range(n)]
for i in range(n):
　　if flag[i]==False:
　　　　for j in range(i,n):
　　　　　　if　　②　　:
　　　　　　　　flag[j]=True
　　　　　　③　　
print('接送所有参会者最少需要%d辆车'%sum)
13.(2023强基联盟统测,15)银行技术部编写风险控制算法,根据申请贷款公司的收益率和信用度,从多个申请公司中挑选前n名公司发放贷款,发放对象必须同时满足以下两个条件:
条件1:公司的收益率大于rate%;
条件2:公司的信用度在rank等级及以上。(A等高于B等,B等高于C等……)
将满足条件1和条件2的公司信息按收益率降序输出。
如所有公司信息为:[[1,20.0,'C'],[2,32.0,'A'],[3,46.0,'B'],[4,44.0,'A']]
满足A等级,且收益率大于20的输出情况为:
[4,44.0,'A'],[2,32.0,'A']]
(1)实现上述功能的Python程序如下,请在划线处填入合适的代码。
(2)加框处代码有错,请改正。
#info=[[1,30.0,'C'],[2,44.0,'B'],……]其中[1,30.0,'C']分别表示公司编号、收益率及信用度等级,代码略
m=len(info)
rate=float(input('输入收益率要求:'))
rank=input('输入等级要求:')
for i in range(m-1):
for j in range(m-1,　①　):
if info[j][2]<=rank:
if info[j][1]>info[j-1][1]and info[j-1][2]<=rank or　②　:
info[j], info[j-1]=info[j-1], info[j]
if info[i][1]m=i
break
if i>0:
print('符合要求的公司为:',　③　)
else:
print('当前无符合要求的公司!')
专题八　数据结构与算法
考点过关练
考点一　数据结构与算法效率
1.(2024届发展共同体联考,12)以下两个程序段的功能相同,实现的功能是:删除列表a(元素个数为n)中的重复元素(只保留一个),并将剩下的元素降序输出。
#程序段① #对列表a进行降序排序,代码略 i=1 while i#程序段② max_num=max(a)#求出列表a中的最大值max_num b=[0]*(max_num+1) for i in range(0,n): 　 b[a[i]]+=1 for i in range(max_num,0,-1): 　 if b[i]>0: 　　　print(i,end=" ")
关于上述两个程序段及功能的描述,正确的是(　　)
A.同样的数据规模,两个程序段的时间效率一样
B.程序段①加框处语句是否执行不受列表a原数据的影响
C.程序段②加框处语句修改为“for i in range(1,max_num+1)”,输出结果不变
D.在实现该功能的过程中,程序段②比程序段①需要更多的存储空间
答案　D　
2.常见算法时间复杂度函数的增长率如图所示。
则当问题规模n=100时,下列时间复杂度中效率最高的是(　　)
A.O(nlog2n)　　　　B.O(log2n)
C.O(n)　　　　D.O(n3)
答案　B　
3.有如下Python程序代码:
n=int(input("n="))
ans1=ans2=0
for i in range(0,n,2):
　　　for j in range(n):
　　　ans1=ans1+1
　　　ans2=ans2+ans1
print("ans1=",ans1,"ans2=",ans2)
则该算法的时间复杂度为(　　)
A.O(1)　　　B.O(n)　　　C.O(n2)　　　D.O(2n)
答案　C　
4.有以下Python程序段:
def jishu(n):
s=0
while n>0:
　s+=n%2
　n//=2
return s
n=int(input("输入一个正整数:"))
ans=jishu(n)
print(ans)
阅读上述代码,回答以下问题。
(1)该程序运行后,输入整数23,输出结果为　　　　。
(2)若输入整数23,则程序中自定义函数jishu()中语句“s+=n%2”执行的次数是　　　。
(3)函数jishu()的时间复杂度为　　　　(单选:A.O(n)　B.O(log2n))。
答案　(1)4　(2)5　(3)B
考点二　迭代与递归
1.(2023浙江1月选考,11,2分)定义如下函数:
def rf(n):
if n<3:
return n
return rf(n-1)+rf(n-3)
执行语句v=rf(5),函数rf被调用的次数是(　　)
A.1　　　B.5　　　C.7　　　D.15
答案　C　
2.(2023浙江6月选考,10,2分)定义如下函数:
def f(a,s):
　　if a>=s:
　　　　return a
　　else:
　　　　return f(a+1,s-a)
执行语句k=f(6,21)后,k的值为(　　)
A.6　　　B.7　　　C.8　　　D.9
答案　C　
3.(2024届发展共同体联考,10)定义如下函数:
def f(x,y):
　　if x<=2 or y>20:
　　　　return x+y
　　return f(x-1,y+1)
执行语句k=f(5,1)后,k的值为(　　)
A.6　　　B.7　　　C.8　　　D.9
答案　A　
4.(2022绍兴诸暨期中,10)某Python程序段如下:
import random
fibo=[1]*11
for i in range(2,11):
　 fibo[i]=fibo[i-1]+fibo[i-2]
n=random.randint(1,10)
print(fibo[n])
运行该程序段,输出结果不可能是(　　)
A.1　　　B.21　　　C.35　　　D.89
答案　C　
5.(2022绍兴诸暨期中,12)下列Python程序的功能是使用迭代算法求s的值。
n=int(input("please input n:"))
s=0
for i in range(1,n):
　　if i%3==0:
　　　　 s=s+i
print("s=",s)
程序执行时,输入n的值为25,则输出的结果为(　　)
A.s=84　　　B.s=118　　　C.s=108　　　D.s=105
答案　C　
6.(2022衢州期末,11)某Python程序段如下:
def doit(x):
　　if x>=6:
　　　　ans=1
　　else:
　　　　ans=3*doit(x+1)+2*doit(x+2)
　　return ans
print(doit(3))
程序运行后,输出的结果为(　　)
A.17　　　B.21　　　C.61　　　D.62
答案　C　
考点三　数据排序
1.(2023浙江1月选考,10,2分)列表s包含8个互不相等的元素,即s[0],s[1],s[2],…,s[7],有如下 Python程序段:
n=8
for i in range(1,n-1):
　for j in range(1,n-i-1):
if s[j]>s[j-1]:
　　s[j],s[j-1]=s[j-1],s[j]
该程序段实现的是(　　)
A.s[0]到s[5]的降序排列
B.s[1]到s[6]的降序排列
C.s[1]到s[7]的升序排列
D.s[2]到s[6]的升序排列
答案　A　
2.(2024届名校协作体联考,10)有如下Python程序:
a=[12,45,45,63,0,0,63]
cnt=0
for i in range(1,len(a)):
　　j=i-1
　　t=a[i]
　　while j>=0 and t>a[j]:
　　　　 a[j+1]=a[j]
　　　　 j=j-1
　　　　 cnt=cnt+1
　　a[j+1]=t
print(cnt)
运行该程序后,输出的结果是(　　)
A.8　　　B.10　　　C.11　　　D.13
答案　B　
3.(2024届浙南名校联考,12)有如下Python程序段:
from random import randint
x=randint(2,4)*2
a=[9,2,5,1,3,4,8,7]
n=len(a)
for i in range(0,n-1):
　　k=i
　　for j in range(i+1,x):
　　　 　if a[k]>a[j]:
　　　　　　k=j
　　if i!=k:
　　　 　a[k],a[i]=a[i],a[k]
print(a)
执行后,输出结果不可能是(　　)
A. [1,2,3,4,5,7,8,9]
B. [1,2,3,4,5,9,8,7]
C. [1,2,5,9,3,4,8,7]
D. [1,2,3,4,5,9,7,8]
答案　D　
4.(2024届天域全国名校协作体联考,11)列表s存有4个整数,有如下Python程序段:
n=len(s)
f=[1]*n
for i in range(n-1):
　 　for j in range(i+1,n):
if s[j]>=s[i]:
　　f[j]+=1
else:
　　f[i]+=1
print(f)
该程序段实现的功能是标记列表中每个数值的名次值,名次排序的规则是(　　)
A.数值越大名次值越大,同数值先出现的名次值小
B.数值越大名次值越大,同数值先出现的名次值大
C.数值越大名次值越小,同数值先出现的名次值小
D.数值越大名次值越小,同数值先出现的名次值大
答案　A　
5.(2022绍兴诸暨期中,11)有如下Python程序段:
b=[56,80,10,31,24,52,66,49]
n=len(b)
for i in range(1,3):
　for j in range(0,n-i):
　　　if b[j]>b[j+1]:
　　　　b[j],b[j+1]=b[j+1],b[j]
经过该程序段“加工”后,列表b中的元素为(　　)
A.[10,24,31,49,52,56,66,80]
B.[10,31,24,52,56,49,66,80]
C.[56,10,31,24,52,66,49,80]
D.[10,24,31,52,49,56,66,80]
答案　B　
6.(2022绍兴柯桥期末,11)对一组数据采用冒泡排序算法进行排序,若第一趟排序完成后的数据序列为31,24,23,15,20,10,则该数据序列的原始顺序不可能是(　　)
A.24,23,15,31,10,20
B.24,23,15,20,31,10
C.24,31,23,15,10,20
D.23,24,15,20,31,10
答案　D　
考点四　数据查找
1.(2022 Z20名校联盟联考,9)某Python程序如下:
import random
key=random.randint(35,45)*2
i=0;j=len(a)-1;s=[]
while i<=j:
　　m=(i+j+1)//2
　　s.append(a[m])
　　if key　　　j=m-1
　　else:
　　　i=m+1
数组a中的元素为“58,69,78,80,83,84,90,90,95”,则执行该程序段后,数组s 中的元素不可能为(　　)
A.83,90,95　　　　B.83,78,80
C.83,90,90,84　　　　D.83,78,69,58
答案　D　
2.(2022百校联考,12)某程序段如下:
a=[9,15,19,20,23,36,78,87,96,100]
ans=[];i=0;j=9
key=int(input("请输入待查数据:"))
flag=False
while i<=j and not flag:
　　m=(i+j)//2
　　ans.append(a[m])
　　if a[m]==key:
　　　flag=True
　　elif a[m]>key:
　　　j=m-1
　　else:
　　　i=m+1
print(ans)
执行该程序后,当输入的key值为15时,输出的结果是(　　)
A.[23,15]　　　　B.[23,19,15]
C.[20,15]　　　　D.[20,19,15]
答案　A　
3.(2022名校协作体联考,12)某算法的Python程序段如下:
key=randint(0,3)*2+13
i,j,c=0,len(a)-1,0
while i<=j:
　m=(i+j+1)//2
　if a[m]>=key:
　　i=m+1
　else:
　　j=m-1
　c+=1
列表a=[23,21,19,18,16,15,14,11],该程序段执行后,下列说法不正确的是(　　)
A.i的值为j+1　　　　B.i的值可能是8
C.j的值可能是5　　　　D.c的值一定是3
答案　B　
4.(2022诸暨海亮月考,12)下列程序实现了输入k,找出大于k的数据的起始索引位置并显示。
a=[1,3,3,5,5,7,10,11,12,15]
n=10
k=int(input())
i=-1
j=　　　
while i < j:
　　m=(i+j+1)//2
　　if k < a[m]:
　　　　j=　　
　　else:
　　　　i=m
L=　　
print(">",k,"的数据索引起始位置为",L)
上述程序段横线处语句依次为(　　)
A.n　m-1　i　　　　B.n-1　m-1　i+1
C.n　m+1　i　　　　D.n-1　m+1　i+1
答案　B　
5.(2022诸暨期末,12)有如下二分查找程序段:
　#列表a存放整数升序数据,代码略
　key=int(input())
　f=[0]*9
　i=0;j=8
　while i<=j:
　　　m=(i+j)//2
　　　f[m]=1
　　　if a[m]>key:
　　　　　 j=m-1
　　　else:
　　　　　i=m+1
　print(f)
输入待查找数据,执行该程序段后,下列选项中,列表f的值不可能是(　　)
A.[0,0,0,0,1,1,1,0,0]
B.[1,1,0,0,1,0,0,0,0]
C.[0,1,0,0,1,0,1,0,0]
D.[0,0,0,0,1,0,1,1,0]
答案　C　
6.(2022绍兴诸暨期中,19)小明学了排序和查找算法后,编写了一个处理成绩的程序,功能如下:程序运行时,首先从Excel文件中读取n个学生的技术成绩存储在列表a中,并对列表中的数据按升序进行排序;输入成绩 key,统计并输出共有多少位同学的成绩大于该成绩。
实现上述功能的Python程序如下,请在程序划线处填入合适的代码。
#从Excel文件中读取n个学生的技术成绩存储在列表a中,代码略
#对列表a中的元素进行升序排序
n=len(a)
for i in range(n-1):
　　for j in range(0,n-i-1):
　　　　if　　①　　:
　　　　　　a[j],a[j+1]=a[j+1],a[j]
print (a)
#输入成绩 key,统计并输出共有多少位同学的成绩大于该成绩
key=int(input("please input key:"))
i,j=0,n-1
while i<=j:
　　m=(i+j)//2
　　if　　②　　 :
　　　　j=m-1
　　else:
　　　　i=m+1
print("共有"　　③　　+ "位同学大于等于该成绩。")
答案　①a[j]>a[j+1]　②key专题综合练
题组一
1.(2024届A9协作体返校考,11)有如下Python程序段:
import random
a=[1,3,4,6,6,6,9,9,11,12]
key=random.randint(2,5)*2
i,j=0,9
while i<=j:
m=(i+j)//2
if key　　j=m-1
else:
　　i=m+1
print(j)
执行该程序段后,输出的结果不可能是(　　)
A.2　　　B.3　　　C.5　　　D.7
答案　B　
2.(2024届Z20联盟联考,10)有如下Python函数:
def trans(num,n):
s="0123456789ABCDEF"
if num　　return s[num]
else:
　　return trans(num//n,n)+s[num%n]
执行语句a=trans(394,16)后,a的值为(　　)
A.19A　　　B.1810　　　C.180　　　D.18A
答案　D　
3.(2024届七彩联盟联考,10)有如下程序段:
def cal(n):
if n<=1:
　　return 1
if n % 2==0:
　　return 2*cal(n-1)
return 1+cal(n-1)
执行语句k=cal(5),则k的值为(　　)
A.6　　　B.7　　　C.10　　　D.11
答案　B　
4.(2024届强基联盟统测,10)有如下程序段:
def fun(k):
if k==1:
　　return "1"
elif k%2==0:
　　return fun(k-1)+str(k%2)
else:
　　return str(k%2)+fun(k-1)
执行语句s=fun(5),则s 的值为(　　)
A."00111"　　　　B."11010"
C."11100"　　　　 D."10110"
答案　C　
5.(2024届新阵地联盟联考,10)有如下Python程序:
import random
def func(n):
if n==1:
　　return 1
elif n==2:
　　return 2
elif n%2==1:
　　return 2*func(n-2)+func(n-1)
else:
　　return func(n-2)+2*func(n-1)
p=random.randint(3,6)
print(func(p))
执行程序后,输出结果不可能为(　　)
A.4　　　B. 10　　　C. 12　　　D. 18
答案　C　
6.(2024届天域全国名校协作体联考,10)某递归函数如下所示:
def hs(m):
if m<=1:
　　f=1
else:
　　f=hs(m-1)+hs(m-2)
return f
ans=0
for i in range(5):
if hs(i)%2==1:
　　ans+=1
print(ans)
程序运行后,输出的结果是(　　)
A.2　　　B.3　　　C.4　　　D.5
答案　C　
7.(2023十校联盟联考,12)某二分查找算法的Python程序段如下:
import random
key=random.randint(0,4)*2+5
n=10;ans=0
a=[4,5,5,8,9,11,11,13,15,17]
i=0;j=n-1
while i<=j:
m=(i+j)//2
if a[m]<=key:
i=m+1
else:
j=m-1
ans+=a[m]
print(ans)
执行该程序段后,ans的值不可能是(　　)
A.19　　　B.27　　　C.37　　　D.44
答案　A　
8.(2024届七彩联盟联考,15)某工厂每天会收到多个订单,有n台机器对零件进行加工。为减少机器的损耗,需要在满足所有订单加工的情况下(订单即到即加工),机器开启数量尽量少。若开启n台机器不能满足订单即到即加工,则计算所有订单最少的平均等待时间。若给定某天内所有的订单信息,请计算需要开启的机器数量以及订单平均等待时间,代码运行效果图如图所示(注意:若上一个订单结束时间为9:00,下一个订单开启时间最早为9:00)。
订单信息如下:(批次,到达时间,加工时间min)
(A1,9:00,30)(A2,11:30,50) (A3,10:40,50)(A4,10:00,60)(A5,9:20,40)(A6,11:00,20)(A7,10:20,40)(A8,9:30,20)
机器数量:2
2台机器全部开启,订单平均等待2.5min
第1台机器:
A1:09:00~09:30,A8:09:30~09:50,A4:10:00~11:00,A3:11:00~11:50
第2台机器:
A5:09:20~10:00,A7:10:20~11:00,A6:11:00~11:20,A2:11:30~12:20
请回答下列问题:
(1)上图所示的例子中,若机器有10台,则只需要开启　　　　台机器。
(2)定义如下data_sort(a)函数,参数a为列表,列表中每个元素包含三个数据项,依次分别对应订单批次、到达时间、加工时间(时间均转为分钟)。该函数实现将列表a按照订单到达时间升序排序。
def data_sort(a):
for i in range(len(a)):
　　for j in range(len(a)-i-1):
　　　　if　　　　:
　　　　　a[j],a[j+1]=a[j+1], a[j]
①划线处填入的语句为　　　　　　　,可实现上述功能。
②若将加框处语句写错为range(i,len(a)-1),则下列4组数据中,列表a的值为　　　(单选,填字母)时不能测试出问题。
A.[['A1',100,30],['A2',120,30],['A3',110,30],['A4',140,30],['A5',130,30]]
B.[['A1',120,30],['A2',110,30],['A3',100,30],['A4',130,30],['A5',140,30]]
C. [['A1',110,30],['A2' ,140,30],['A3',130,30],['A4',100,30],['A5',120,30]]
D.[['A1',110,30],['A2',120,30],['A3',130,30],['A4',140,30],['A5',100,30]]
(3)实现计算开启机器数量的部分Python程序如下,请在划线处填入合适的代码。
def huan(n):
#将分钟转换为时间AA:BB格式,返回值为字符串,代码略
#读取文件中的信息,并存储在列表order中,代码略
data_sort(order)
n=int(input("机器数量:"))
for i in range(len(order)):
order[i].append(-1)
#order[i]追加一个元素-1
mach=[-1]* n
num, wait=0,0
for i in range(len(order)):
k=-1
time=-1
for j in 　　①　　:
　　t1=mach[j]
　　if k==-1:
　　　　k=j
　　　　time=order[t1][1]+order
[t1][2]
　　else:
　　　　t2=mach[k]
　　　　if order[t1][1]+order[t1][2]　　　　　　k=j
　　　　　　time=order[t1][1]+order
[t1][2]
if k==-1 or num　 mach[num]=i
　 num+=1
　　else:
　 order[i][3]=mach[k]
　 mach[k]=i
　 if time>order[i][1]:
　　　　wait +=time-order[i][1]
　　　　order[i][1]=time
if numprint("只需开启"+str(num)+"台机器")
else:
print(str(n)+"台机器全部开启,订单平均等待"+str(round(wait/len(order),2))+"min")
for i in range(num):
print('第'+str(i+1)+'台机器: ')
p=mach[i]
ans=' '
while p!=-1:
　　ans=order[p][0]+':'+huan(order[p][1])+'~'+huan(order[p][1]+order[p][2])+','+ ans
　　p=　　③　　
　　print(ans[:-1])
答案　　(1)3 　(2)①a[j][1]> a[j+1][1]
②A　(3)①range(num)　②time>order[i][1]　③order[p][3]
9.(2024届名校协作体联考,15)有一款益智游戏,规则如下:轨道上有不同颜色的珠子连成珠串,玩家可以通过炮台发射若干珠子,每次发射一颗珠子到珠串中的某位置,形成新的珠串。当新珠串中出现3颗及以上颜色相同的连续珠子时,这些连续的同色珠子会被消除,并获得相应积分,若消除后仍有符合条件的同色珠子,会继续被消除。记分规则为:在被消除的连续珠子中,前面3颗直接记3分,其余的珠子每颗记2分,例如有5颗相同颜色的连续珠子被消除,可获得7分。程序运行过程如图所示。
现轨道的珠串为:
-1->3->1->5->4->2->2->1->2->2
当前珠子的颜色为:1
请输入当前发射位置:7
当前珠子的颜色为:1
请输入当前发射位置:7
当前珠子的颜色为:4
请输入当前发射位置:5
当前珠子的颜色为:4
请输入当前发射位置:5
最终得分为11
轨道中剩余的珠串为:
-1->3->1->5
编写程序模拟游戏的实现过程,珠子的颜色用数字表示,为方便处理,在珠串最前面加入一颗不可消除的珠子,颜色值为-1。请回答下列问题:
(1)若珠串为-1,2,2,3,3,2,2,将颜色为3的珠子发射到颜色为2和3的珠子之间,可获得积分为　　　　。
(2)定义如下insert(t,pos)函数,函数功能是将颜色为t的珠子,插入到当前珠串中的第pos颗珠子后面(列表link存储珠串的相关数据,例如link中某元素的值为[3,2],3表示某颗珠子的颜色,2表示与该珠子相邻的下一颗珠子的存储地址,变量 head保存珠串第一个珠子的存储地址),请在划线处填入合适的代码。
def insert(t,pos): #将颜色为t的珠子,插入到当前珠串第pos颗珠子的后面
p=head
while pos>1:
　　pos-=1
　　p=link[p][1]
link.append(　　　　)
link[p][1]=len(link)-1
(3)定义如下fun()函数,函数功能是:查找珠串里最早出现的可消除珠串,函数返回ret,ret由该珠串起始珠子的前一颗珠子位置和该珠串的连续长度组成。
def fun():
p=head;st=head
pre=p
num=0
lastcolor=-1
ret=[-1,0]
while p!=-1:
　　t=link[p][0]
　　if t!=lastcolor:
　　　　if num>=3:
　　　　　　ret=[st,num]
　　　　　　break
　　　　lastcolor=t
　　　　st=pre
　　　　num=1
　　else:
　　　　num+=1
　　pre=p
　　p=link[p][1]
if num>=3:
ret=[st,num]
return ret
若将函数中加框处代码删除,会导致某些情况下无法得到符合函数功能的结果。调用fun()函数,下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.head=4
link=[[2,3],[1,0],[1,1],[2,-1],[-1,2]]
B.head=0
link=[[-1,1],[2,3],[2,4],[2,2],[1,-1]]
C. head=1
link=[[2,-1],[-1,3],[2,0],[1,4],[2,2]]
D.head=4
link=[[2,-1],[1,0],[1,1],[1,2],[-1,3]]
(4)实现模拟游戏过程的部分Python程序如下,请在划线处填入合适的代码。
def clear(g):#根据fun函数的返回值对珠串进行消除,并统计获得本次消除的积分
p=g[0]
q=p
length=g[1]
ret=　　①　　
while length>=0:
　　q=link[q][1]
　　length-=1
link[p][1]=q
return ret
def traverl():
　　#将轨道中珠串按序输出,代码略
head=7
link=[[1,3],[1,8],[2,1],[5,5],[2,2],[4,4],[3,0],[-1,6],[2,9],[2,-1]]
print("现轨道的珠串为: ")
traverl()
points=0
que=[1,1,4,4]#保存炮台中待发射珠子的颜色
qhead=0
qtail=4
while qhead!=qtail:
　　print("当前珠子的颜色为: ",que[ghead])
　　s=int(input("请输入当前发射位置:"))
　　insert(que[qhead],s)
　　qhead+=1
　　g=fun()
　　while g!=[-1,0]:
　　　　points+=clear(g)
　　　　　　②　　
print("最终得分为",points)
print("轨道中剩余的珠串为: ")
traverl()
答案　(1)8　(2)[t ,link[p][1]]　(3)C　(4)①3+(length -3)*2　②g=fun()
10.(2024届发展共同体联考,15)某业务服务大厅共有m个服务窗口(编号为0~m-1),服务大厅根据服务对象的优先等级(等级分为1~10,数字越大优先级越高)从高到低依次分配窗口并提供服务。某个时间段内(该时间段起始时刻各窗口都空闲着),服务对象按服务优先等级从高到低排队后依次到空闲的窗口享受服务,服务优先等级相同时,先到达的先享受服务。由于办理的业务不同,每个服务对象的服务时长(单位:分钟)可能是不相同的。按照上述服务规则,问所有服务对象完成业务办理需要多少时间。一个服务对象业务办理结束,另一个服务对象马上到该窗口接受服务,中间浪费的时间忽略不计。
图a描述了5个服务对象的信息,按照服务规则确定的服务次序如图b所示。
到达序号 服务优先等级 服务时长
1 7 10
2 6 12
3 4 32
4 5 24
5 6 8
图a
到达序号 服务优先等级 服务时长 服务次序
1 7 10 1
2 6 12 2
3 4 32 5
4 5 24 4
5 6 8 3
图b
若服务大厅提供2个服务窗口(m=2),则所有服务对象完成业务办理需要50分钟。具体方案可以是:0号窗口依次服务到达序号为1、5、3的对象,1号窗口依次服务到达序号为2、4的对象。请回答下列问题:
(1)若有6个服务对象的信息如图c所示,根据上述服务规则,在提供3个服务窗口的情况下,所有服务对象完成业务办理需要　　　　分钟。
到达序号 服务优先等级 服务时长
1 3 2
2 5 7
3 4 13
4 1 5
5 8 12
6 4 11
图c
(2)定义如下sort_lst(lst)函数,参数 lst是所有服务对象信息构成的列表。函数的功能是将列表lst 按照服务对象的优先等级降序排列并构成链表,返回排序后的链表及其头指针。
def sort_lst(lst):
for i in range(len(lst)):
　　lst[i].append(-1)
head=0
for i in range(1,len(lst)):
　　p=head
　　while p!=-1:
　　　　if lst[p][1]>=lst[i][1]:
　　　　　　q=p
　　　　　　p=lst[p][3]
　　　　else:
　　　　　　break
　　if p==head:
　　　　lst[i][3]=head
　　　　head=i
　　else:
　　　　lst[q][3]=i
　　　　lst[i][3]=p
return lst,head
若lst列表依次存储图c所示的服务对象信息,如lst[0]为[1,3,2],各数据项依次表示服务对象的到达序号,服务优先等级及服务时长。调用sort_lst(lst)时,程序中加框处的语句“q=p”总共执行　　　　次。
(3)计算时间段内服务对象完成业务办理所需时间的部分Python程序如下,请在划线处填入合适的代码。
def proc(lst,p,n,m):
s=[0]*m
for i in range(m):　　#前m个人直接开始服务,等待时间为0
　　if p==-1:
　　　　break
　　s[i]=lst[p][2]
　　　　①　　
ans=0
while p!=-1 :
　　k=s[0]　　#找出正在被服务的对象中最早结束的一个
　　for j in range(1,m):
　　　　if s[j]　　　　　　k=s[j]
　　ans+=k
　　for j in range(m):
　　　　s[j]-=k
　　　　if　　②　　:
　　　　　　s[i]=lst[p][2]
　　　　　　p=lst[p][3]
k=s[0]
for i in range(m):
　　if s[i]>k:
　　　　k=s[i]
　　③　　
print("所有服务对象完成业务办理需要" ,str(ans),"分钟")
'''
读入服务对象总数n和窗口数m
按到达序号读入n个服务对象的信息到列表lst中,如图c为:lst=[[1,3,2],[2,5,7],[3,4,13],[4,1,5],[5,8,12],[6,4,11]]
代码略
'''
lst,head=sort_lst(lst)#对lst按照服务对象优先等级降序排序
proc(lst,head,n,m)
答案　(1)18　(2)7　(3)①p=lst [p][3]或其他等价答案　②s[j]==0 and p !=-1或其他等价答案　③ans=ans+k 或其他等价答案
11.(2024浙江1月选考,15,9分)某项活动有n个单位(编号1到n)参加,需将员工分成若干个小组,每个小组的人数上限为m,小组编号按新建次序从1开始编号。分组时,首先按单位编号次序依次在各单位内部分组,每m人分配到一个新建小组中,不足m人的剩余员工暂不分配;然后按剩余员工人数由大到小的顺序,依次为各单位剩余员工分配小组。
若某单位剩余员工人数为k,则分配方法为:在已建的小组中查找空位数(该小组还可容纳的人数)大于或等于k的小组,如果找到的小组有多个,则选择空位数最少的小组,将此k人分配到该小组中; 如果没有找到,则新建一个小组,将此k人分配到该小组中。
设n为5,m为20,各单位员工人数及单位内部的分组过程如图a所示,各单位剩余员工的分组过程如图b所示。
编写程序:给定各单位编号及员工人数,根据上述方法进行分组处理,按单位编号次序输出各单位所分配的分组编号。请回答下列问题:
(1)由题意可知,若仅将图a中1号单位的员工人数修改为25,然后对图中5个单位重新分组,则1号单位所分配的分组编号为　　　　。
(2)定义如下bubble_sort(lst)函数,参数lst的每个元素由单位编号和剩余员工人数2个数据项组成。函数的功能是根据每个单位的剩余员工人数,对lst进行降序排序。
def bubble_sort(lst):
　　n=len(lst)
　　for i in range(0,n-1):
for j in range(n-1,i,-1):
　　if lst[j-1][1]　　　　tmp=lst[j]
lst[j]=lst[j-1]
lst[j-1]=tmp
if lst[i][1]==0:
　　break
　　return
调用该函数,若lst为[[1,0],[2,0],[3,18],[4,0],[5,19],[6,17]],请回答①和②两个问题。
①框中的程序段第1次执行后,关于lst中的剩余员工人数,下列说法正确的是　　　 (单选,填字母)。
A.lst[0][1]数值最小
B.lst[0][1]数值最大
C.lst[5][1]数值最小
D.lst[5][1]数值最大
②框中的程序段执行的次数为　　　　。
(3)实现分组功能的部分Python程序如下,程序中用到的列表函数与方法如图c所示,请在程序中划线处填入合适的代码。
函数与方法 功能
w.append(x) 在列表w末尾添加元素x
x.w.pop() 将列表w末尾元素赋值给x,并将其从w中删除
图c
def group(data,m):
n=len(data)
a=[]
for i in range(n+1):
a.append([])　　　#a[i]初始化为空列表,存放编号为i的单位所分配的分组编号
gnum=0
for i in range(n):　　#各单位内部分组
　　while data[i][1]>=m:
　　　　gnum+=1
k=data[i][0]
a[k].append(gnum)
　　　①　　　
bubble_sort(data)　　#根据每个单位的剩余员工人数,对data 进行降序排序
b=[]
for i in range(m):
b.append([])
i=0　　　#对剩余员工分组
while i　　　　　②　　　
while j　　j+=1
if j　　v=b[j].pop()
else:
　　gnum+=1
　　v=gnum
a[data[i][0]].append(v)
　　　③　　　
i+=1
#输出各单位的分组编号,代码略
'''
读取小组人数上限存入m;读取1至n号单位的数据,依次存入列表data的data[0]至data[n-1]中。
data[i]包含2个数据项,data[i][0],data[i][1]分别存放单位编号及员工人数,代码略
'''
group(data,m)
答案　(1)1,8　(2)①B　②4　(3)①data[i][1]-=m　②j=data[i][1]　③b[j-data[i][1]].append(v)
12.(2024届浙南名校联盟联考,15)某工厂将送达的各批次物品按品种打包。小李将各批次物品信息按送达时间顺序合并,得到如图a-2所示数据 data。同一个包裹只能装入同一品种任意批次的物品,当某一个品种物品A送达使得已送达的该品种物品总质量超过m时,则将在该物品之前送达的物品按质量由大到小依次装入包裹,其余质量不足m的品种,按各品种依次装入包裹。编写程序,读取物品合并更新后的信息,按送达时间顺序打包,输出各包裹中的物品序号,运行结果如图b所示。
序号 品种 送达时间 批次 质量(千克)
1 2 8:35 1 6
2 1 8:50 1 8
3 0 9:10 1 2
4 0 9:15 1 4
序号 品种 送达时间 批次 质量(千克)
1 0 8:30 2 3
序号 品种 送达时间 批次 质量(千克)
1 0 8:40 3 4
图a-1
序号 品种 送达时间 批次 质量(千克)
1 0 8:30 2 3
2 2 8:35 1 6
3 0 8:40 3 4
4 1 8:50 1 8
5 0 9:10 1 2
6 0 9:15 1 4
图a-2
m=10
data=[[1,0,'8:30',2,3],[2,2,'8:35',1,6],[3,0,'8:40',3,4],[4,1,'8:50',1,8],[5,0,'9:10',1,2],[6,0,'9:15',1,4]]
第1个包裹中品种为0,各物品的序号依次是:3,1,5,
第2个包裹中品种为0,各物品的序号依次是:6,
第3个包裹中品种为1,各物品的序号依次是:4,
第4个包裹中品种为2,各物品的序号依次是:2,
图b
请回答下列问题:
(1)送达物品信息合并后如图a-2所示,若包裹装入物品质量不能超过8千克,则首先打包完成的包裹中装入品种为0,各物品的序号依次是　　　　。
(2)定义data_sort(lst)函数。先将数据(见图a-1)合并得到 lst列表(见图a-2),函数data_sort(lst)的功能是对lst列表按送达时间升序排列,并对序号进行更新。
def data_sort(lst):
for i in range(n-1):#n为数据个数
　　for j in range(n-1,i,-1):
　　　　if lst[j][2]< lst[j-1][2]:
　　　　　　lst[j],lst[j-1]=lst[j-1],lst[j]
　　lst[i][0]=i+1
return lst
执行上述代码后,　　　　(填写:能/不能)正确得到图a-2中的数据。
(3)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
def pack(k):　#对品种k已送达待打包的物品按质量由大到小输出
#部分代码略
p=b[k][1]
num+=1
print("第"+str(num)+"个包裹中品种为"+str(k)+",各物品的序号依次是: ",end=" ")
while p!=-1:
　　print(data[p][0],end=",")
　　p=x[p]
print()
#合并后排序得到n件物品的数据存储在数组data中并输出,包裹最大承受质量为m千克。物品品种的数量是sn,代码略
b=[[0,-1] for i in range(sn)]
x=[-1 for i in range(n)]
num=0
for i in range(n):
k=data[i][1]
if b[k][0]+data[i][4]>m:
　　pack(k)
　　b[k]=[0,-1]
p=　　①　　
if p==-1:
　　b[k][1]=i
else:
　　if data[i][4]>data[p][4]:
　　　　b[k][1]=i
　　　　　　②　　
　　else:
　　　　q=-1
　　　　while　　③　　:
　　　　　　q=p
　　　　　　p=x[p]
　　　　x[q]=i
　　　　x[i]=p
b[k][0]+=data[i][4]
#质量不足m的品种,按品种依次装入包裹
for i in range(sn):
if b[i][1]!=-1:
　　pack(i)
答案　(1)3,1　(2)不能　 (3)①b [k][1]　②x [i]=p
③p !=-1 and data [i][4]<=data[p][4]或 p >- 1 and data [i][4]<=data [p][4]或 p >=0 and data [i][4]<=data [p][4]
13.(2024届新阵地联盟联考,15)进入新学期第一天,班主任老师将班上N个同学(学号为1~N)排成一排,分配座位。从排队到分配座位步骤如下:
步骤一:先将1号同学安排进队;
步骤二:2~N号同学由老师依次指定入队位置,如学号为i的同学由老师指定站在队中某位同学的左侧或右侧;
步骤三:所有同学按照上述方法入队完毕后,以2人一组的方式依次分配到四个组别中;
步骤四:输出每组学生的名单。
请回答下列问题。
(1)若某班有4位同学,学号为1~4,完成步骤一后,执行步骤二的指令3次,每次指令包含两个整数k和p(p为0或1)。若p为0,则表示插在k号同学的左侧,p为1则表示插在k号同学的右侧。若三条指令分别为1 0、2 1、1 0,则执行指令后队伍从左到右学号分别为　　　　。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
#insert(k,x)函数的功能是在k号的右侧插入x号同学
#L和R列表分别用于记录每位同学的左侧和右侧的同学学号
def insert(k,x):
R[x]=R[k]
L[x]=k
　　①　　
R[k]=x
L=[0]*100;R=[0]*100;vis=[0]*100
insert(0,1)　　#0的右边插入1号同学
#info列表存储各学生姓名和学号,格式如[["张三",1],["李四",2]…],代码略
n=int(input("请输入同学人数:"))
for i in range(2,n+1):
k=int(input("请问插入在几号同学旁边 "))
p=int(input("请输入该同学的左侧还是右侧"))
if p==0:
　　　　②　　
else:
　　insert(k, i)
q=[[] for i in range(4)]
i=m=0
　　③　　
while x!=0:
q[i].append(x)
m=m+1
if m%2==0:
　　　　④　　
x=R[x]
for i in range(4):
for j in q[i]:
　　print(info[j-1][0], end="　")
print()
答案　(1)2341　(2)①L[R[k]]=x　②insert(L[k], i)
③x=R[0]　④i=(i+1)%4
14. (2023学军中学月考,15)学校为了使本校毕业生能以更好的状态参加高考,都会创造条件向上级申请在本校设立标准化考点,让学生能在本校参加考试。标准化考点要求很多,其中之一就是各考场内的座位安排必须是蛇形排列,保证使用A、B卷的同学能完全错开,如图a所示。小明用Python编写了一个模拟考场座位编排程序,程序运行结果如图b所示,每个座位号占4位宽度右对齐。输出程序如下,请在划线处填入合适的代码。
def px(lst):
for i in range(len(lst)-1):
k=i
for j in range(　①　):
if lst[j]>lst[k]:
k=j
if k!=i:
lst[i],lst[k]=lst[k],lst[i]
def gssc(t,n):　　　　#将字符t按n个字符宽度输出
t="　"* (n-len(t))+t
return t
n=int(input('请输入行数:'))
m=int(input('请输入列数:'))
a=[]
for j in range(m):
a.append([])
for i in range(n):
a[j].append(　②　)
for i in range(m):
if　③　:
px(a[i])
for i in range(n):
st=" "
for j in range(m):
tmp='A'
if a[j][i]%2==1:
tmp='B'
st+=　④　　　#每个座位号按4位输出
print(st)
答案　①i+1,len(lst)　②i+j*n　③i%2==1
④gssc(str(a[j][i])+tmp,4)
题组二
1.(2024届名校协作体联考,11)定义如下函数:
def f(k):
if k<=3:
　　print(k)
　　return
for i in range(1,4):
　　f(k-i)
return
执行语句f(6),则f(3)被调用的次数为(　　)
A.1次　　　B.2次　　　C.3次　　　D.4次
答案　D　
2.(2024届强基联盟联考,10)执行下列Python代码,输出结果为(　　)
def f(s):
m=len(s)
if m==1:
　　return int(s)
else:
　　return f(s[:m-1])+f(s[m-1])
print(f("101"))
A.11　　　　B.2　　　
C.5　　　　D.101
答案　B　
3.(2024届百校起点调研测试,10)定义如下递归函数:
def f(a,n):
n=n-1
if n==0:
　　return a
else:
　　return f(a-1,n)+f(a+1,n)
print(f(5,3))
程序运行后,输出的结果是(　　)
A.10　　　B.20　　　C.30　　　D.40
答案　B　
4.(2022宁波九校联考期末,12)某二分查找算法的 Python程序段如下,运行该段代码后,输出的结果不可能是(　　)
import random
a=[10,20,30,40,50,60,70,80]
key=random.choice(a);i,j=0,len(a)-1
s=" "
while i<=j:
　　m=(i+j)//2
　　if key==a[m]:
　　　　s=s+"M";break
　　elif key　　　　j=m-1;s=s+"L"
　　else:
i=m+1;s=s+"R"
print(s)
A.LLM　　　　B.LRM
C.RRRM　　　　D.RRLM
答案　D　
5.(2023浙江开学考,12)峰值元素指数组中其值大于左右相邻值的元素,如序列3、8、4、1中8为峰值元素。一个数组r包含多个峰值元素,现需要找出其中一个峰值元素所在的位置(默认第一个数的左侧

展开更多......

收起↑