浙江版高中信息技术复习专题八数据结构与算法练习含答案

专题八数据结构与算法考点过关练考点一数据结构与算法效率1.(2024届发展共同体联考,12)以下两个程序段的功能相同,实现的功能是:删除列表a(元素个数为n)中的重复元素(只保留一个),并将剩下的元素降序输出。#程序段①#对列表a进行降序排序,代码略i=1whilei<n:ifa[i]==a[i-1]:forjinrange(i+1,n):a[j-l]=a[j]i-=1;n-=1i+=1#输出列表元素a[0]到a[n-1],代码略#程序段②max_num=max(a)#求出列表a中的最大值max_numb=[0]*(max_num+1)foriinrange(0,n):b[a[i]]+=1foriinrange(max_num,0,-1):ifb[i]>0:print(i,end="")关于上述两个程序段及功能的描述,正确的是()A.同样的数据规模,两个程序段的时间效率一样B.程序段①加框处语句是否执行不受列表a原数据的影响C.程序段②加框处语句修改为“foriinrange(1,max_num+1)”,输出结果不变D.在实现该功能的过程中,程序段②比程序段①需要更多的存储空间答案D2.常见算法时间复杂度函数的增长率如图所示。则当问题规模n=100时,下列时间复杂度中效率最高的是()A.O(nlog2n)B.O(log2n)C.O(n)D.O(n3)答案B3.有如下Python程序代码:n=int(input("n="))ans1=ans2=0foriinrange(0,n,2):forjinrange(n):ans1=ans1+1ans2=ans2+ans1print("ans1=",ans1,"ans2=",ans2)则该算法的时间复杂度为()A.O(1)B.O(n)C.O(n2)D.O(2n)答案C4.有以下Python程序段:defjishu(n):s=0whilen>0:s+=n%2n//=2returnsn=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分)定义如下函数:defrf(n):ifn<3:returnnreturnrf(n-1)+rf(n-3)执行语句v=rf(5),函数rf被调用的次数是()A.1B.5C.7D.15答案C2.(2023浙江6月选考,10,2分)定义如下函数:deff(a,s):ifa>=s:returnaelse:returnf(a+1,s-a)执行语句k=f(6,21)后,k的值为()A.6B.7C.8D.9答案C3.(2024届发展共同体联考,10)定义如下函数:deff(x,y):ifx<=2ory>20:returnx+yreturnf(x-1,y+1)执行语句k=f(5,1)后,k的值为()A.6B.7C.8D.9答案A4.(2022绍兴诸暨期中,10)某Python程序段如下:importrandomfibo=[1]*11foriinrange(2,11):fibo[i]=fibo[i-1]+fibo[i-2]n=random.randint(1,10)print(fibo[n])运行该程序段,输出结果不可能是()A.1B.21C.35D.89答案C5.(2022绍兴诸暨期中,12)下列Python程序的功能是使用迭代算法求s的值。n=int(input("pleaseinputn:"))s=0foriinrange(1,n):ifi%3==0:s=s+iprint("s=",s)程序执行时,输入n的值为25,则输出的结果为()A.s=84B.s=118C.s=108D.s=105答案C6.(2022衢州期末,11)某Python程序段如下:defdoit(x):ifx>=6:ans=1else:ans=3*doit(x+1)+2*doit(x+2)returnansprint(doit(3))程序运行后,输出的结果为()A.17B.21C.61D.62答案C考点三数据排序1.(2023浙江1月选考,10,2分)列表s包含8个互不相等的元素,即s[0],s[1],s[2],…,s[7],有如下Python程序段:n=8foriinrange(1,n-1):forjinrange(1,n-i-1):ifs[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]的升序排列答案A2.(2024届名校协作体联考,10)有如下Python程序:a=[12,45,45,63,0,0,63]cnt=0foriinrange(1,len(a)):j=i-1t=a[i]whilej>=0andt>a[j]:a[j+1]=a[j]j=j-1cnt=cnt+1a[j+1]=tprint(cnt)运行该程序后,输出的结果是()A.8B.10C.11D.13答案B3.(2024届浙南名校联考,12)有如下Python程序段:fromrandomimportrandintx=randint(2,4)*2a=[9,2,5,1,3,4,8,7]n=len(a)foriinrange(0,n-1):k=iforjinrange(i+1,x):ifa[k]>a[j]:k=jifi!=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]答案D4.(2024届天域全国名校协作体联考,11)列表s存有4个整数,有如下Python程序段:n=len(s)f=[1]*nforiinrange(n-1):forjinrange(i+1,n):ifs[j]>=s[i]:f[j]+=1else:f[i]+=1print(f)该程序段实现的功能是标记列表中每个数值的名次值,名次排序的规则是()A.数值越大名次值越大,同数值先出现的名次值小B.数值越大名次值越大,同数值先出现的名次值大C.数值越大名次值越小,同数值先出现的名次值小D.数值越大名次值越小,同数值先出现的名次值大答案A5.(2022绍兴诸暨期中,11)有如下Python程序段:b=[56,80,10,31,24,52,66,49]n=len(b)foriinrange(1,3):forjinrange(0,n-i):ifb[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]答案B6.(2022绍兴柯桥期末,11)对一组数据采用冒泡排序算法进行排序,若第一趟排序完成后的数据序列为31,24,23,15,20,10,则该数据序列的原始顺序不可能是()A.24,23,15,31,10,20B.24,23,15,20,31,10C.24,31,23,15,10,20D.23,24,15,20,31,10答案D考点四数据查找1.(2022Z20名校联盟联考,9)某Python程序如下:importrandomkey=random.randint(35,45)*2i=0;j=len(a)-1;s=[]whilei<=j:m=(i+j+1)//2s.append(a[m])ifkey<a[m]:j=m-1else:i=m+1数组a中的元素为“58,69,78,80,83,84,90,90,95”,则执行该程序段后,数组s中的元素不可能为()A.83,90,95B.83,78,80C.83,90,90,84D.83,78,69,58答案D2.(2022百校联考,12)某程序段如下:a=[9,15,19,20,23,36,78,87,96,100]ans=[];i=0;j=9key=int(input("请输入待查数据:"))flag=Falsewhilei<=jandnotflag:m=(i+j)//2ans.append(a[m])ifa[m]==key:flag=Trueelifa[m]>key:j=m-1else:i=m+1print(ans)执行该程序后,当输入的key值为15时,输出的结果是()A.[23,15]B.[23,19,15]C.[20,15]D.[20,19,15]答案A3.(2022名校协作体联考,12)某算法的Python程序段如下:key=randint(0,3)*2+13i,j,c=0,len(a)-1,0whilei<=j:m=(i+j+1)//2ifa[m]>=key:i=m+1else:j=m-1c+=1列表a=[23,21,19,18,16,15,14,11],该程序段执行后,下列说法不正确的是()A.i的值为j+1B.i的值可能是8C.j的值可能是5D.c的值一定是3答案B4.(2022诸暨海亮月考,12)下列程序实现了输入k,找出大于k的数据的起始索引位置并显示。a=[1,3,3,5,5,7,10,11,12,15]n=10k=int(input())i=-1j=

whilei<j:m=(i+j+1)//2ifk<a[m]:j=

else:i=mL=

print(">",k,"的数据索引起始位置为",L)上述程序段横线处语句依次为()A.nm-1iB.n-1m-1i+1C.nm+1iD.n-1m+1i+1答案B5.(2022诸暨期末,12)有如下二分查找程序段:#列表a存放整数升序数据,代码略key=int(input())f=[0]*9i=0;j=8whilei<=j:m=(i+j)//2f[m]=1ifa[m]>key:j=m-1else:i=m+1print(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]答案C6.(2022绍兴诸暨期中,19)小明学了排序和查找算法后,编写了一个处理成绩的程序,功能如下:程序运行时,首先从Excel文件中读取n个学生的技术成绩存储在列表a中,并对列表中的数据按升序进行排序;输入成绩key,统计并输出共有多少位同学的成绩大于该成绩。实现上述功能的Python程序如下,请在程序划线处填入合适的代码。#从Excel文件中读取n个学生的技术成绩存储在列表a中,代码略#对列表a中的元素进行升序排序n=len(a)foriinrange(n-1):forjinrange(0,n-i-1):if①:

a[j],a[j+1]=a[j+1],a[j]print(a)#输入成绩key,统计并输出共有多少位同学的成绩大于该成绩key=int(input("pleaseinputkey:"))i,j=0,n-1whilei<=j:m=(i+j)//2if②:

j=m-1else:i=m+1print("共有"③+"位同学大于等于该成绩。")

答案①a[j]>a[j+1]②key<a[m]③str(n-i)专题综合练题组一1.(2024届A9协作体返校考,11)有如下Python程序段:importrandoma=[1,3,4,6,6,6,9,9,11,12]key=random.randint(2,5)*2i,j=0,9whilei<=j:m=(i+j)//2ifkey<a[m]:j=m-1else:i=m+1print(j)执行该程序段后,输出的结果不可能是()A.2B.3C.5D.7答案B2.(2024届Z20联盟联考,10)有如下Python函数:deftrans(num,n):s="0123456789ABCDEF"ifnum<n:returns[num]else:returntrans(num//n,n)+s[num%n]执行语句a=trans(394,16)后,a的值为()A.19AB.1810C.180D.18A答案D3.(2024届七彩联盟联考,10)有如下程序段:defcal(n):ifn<=1:return1ifn%2==0:return2*cal(n-1)return1+cal(n-1)执行语句k=cal(5),则k的值为()A.6B.7C.10D.11答案B4.(2024届强基联盟统测,10)有如下程序段:deffun(k):ifk==1:return"1"elifk%2==0:returnfun(k-1)+str(k%2)else:returnstr(k%2)+fun(k-1)执行语句s=fun(5),则s的值为()A."00111"B."11010"C."11100"D."10110"答案C5.(2024届新阵地联盟联考,10)有如下Python程序:importrandomdeffunc(n):ifn==1:return1elifn==2:return2elifn%2==1:return2*func(n-2)+func(n-1)else:returnfunc(n-2)+2*func(n-1)p=random.randint(3,6)print(func(p))执行程序后,输出结果不可能为()A.4B.10C.12D.18答案C6.(2024届天域全国名校协作体联考,10)某递归函数如下所示:defhs(m):ifm<=1:f=1else:f=hs(m-1)+hs(m-2)returnfans=0foriinrange(5):ifhs(i)%2==1:ans+=1print(ans)程序运行后,输出的结果是()A.2B.3C.4D.5答案C7.(2023十校联盟联考,12)某二分查找算法的Python程序段如下:importrandomkey=random.randint(0,4)*2+5n=10;ans=0a=[4,5,5,8,9,11,11,13,15,17]i=0;j=n-1whilei<=j:m=(i+j)//2ifa[m]<=key:i=m+1else:j=m-1ans+=a[m]print(ans)执行该程序段后,ans的值不可能是()A.19B.27C.37D.44答案A8.(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)机器数量:22台机器全部开启,订单平均等待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按照订单到达时间升序排序。defdata_sort(a):foriinrange(len(a)):forjinrange(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程序如下,请在划线处填入合适的代码。defhuan(n):#将分钟转换为时间AA:BB格式,返回值为字符串,代码略#读取文件中的信息,并存储在列表order中,代码略data_sort(order)n=int(input("机器数量:"))foriinrange(len(order)):order[i].append(-1)#order[i]追加一个元素-1mach=[-1]*nnum,wait=0,0foriinrange(len(order)):k=-1time=-1forjin①:

t1=mach[j]ifk==-1:k=jtime=order[t1][1]+order[t1][2]else:t2=mach[k]iforder[t1][1]+order[t1][2]<order[t2][1]+order[t2][2]:k=jtime=order[t1][1]+order[t1][2]ifk==-1ornum<nand②:

mach[num]=inum+=1else:order[i][3]=mach[k]mach[k]=iiftime>order[i][1]:wait+=time-order[i][1]order[i][1]=timeifnum<n:print("只需开启"+str(num)+"台机器")else:print(str(n)+"台机器全部开启,订单平均等待"+str(round(wait/len(order),2))+"min")foriinrange(num):print('第'+str(i+1)+'台机器:')p=mach[i]ans=''whilep!=-1:ans=order[p][0]+':'+huan(order[p][1])+'~'+huan(order[p][1]+order[p][2])+','+ansp=③

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保存珠串第一个珠子的存储地址),请在划线处填入合适的代码。definsert(t,pos):#将颜色为t的珠子,插入到当前珠串第pos颗珠子的后面p=headwhilepos>1:pos-=1p=link[p][1]link.append()

link[p][1]=len(link)-1(3)定义如下fun()函数,函数功能是:查找珠串里最早出现的可消除珠串,函数返回ret,ret由该珠串起始珠子的前一颗珠子位置和该珠串的连续长度组成。deffun():p=head;st=headpre=pnum=0lastcolor=-1ret=[-1,0]whilep!=-1:t=link[p][0]ift!=lastcolor:ifnum>=3:ret=[st,num]breaklastcolor=tst=prenum=1else:num+=1pre=pp=link[p][1]ifnum>=3:ret=[st,num]returnret若将函数中加框处代码删除,会导致某些情况下无法得到符合函数功能的结果。调用fun()函数,下列4组数据中能测试出这一问题的是(单选,填字母)。

A.head=4link=[[2,3],[1,0],[1,1],[2,-1],[-1,2]]B.head=0link=[[-1,1],[2,3],[2,4],[2,2],[1,-1]]C.head=1link=[[2,-1],[-1,3],[2,0],[1,4],[2,2]]D.head=4link=[[2,-1],[1,0],[1,1],[1,2],[-1,3]](4)实现模拟游戏过程的部分Python程序如下,请在划线处填入合适的代码。defclear(g):#根据fun函数的返回值对珠串进行消除,并统计获得本次消除的积分p=g[0]q=plength=g[1]ret=①

whilelength>=0:q=link[q][1]length-=1link[p][1]=qreturnretdeftraverl():#将轨道中珠串按序输出,代码略head=7link=[[1,3],[1,8],[2,1],[5,5],[2,2],[4,4],[3,0],[-1,6],[2,9],[2,-1]]print("现轨道的珠串为:")traverl()points=0que=[1,1,4,4]#保存炮台中待发射珠子的颜色qhead=0qtail=4whileqhead!=qtail:print("当前珠子的颜色为:",que[ghead])s=int(input("请输入当前发射位置:"))insert(que[qhead],s)qhead+=1g=fun()whileg!=[-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所示。到达序号服务优先等级服务时长1710261234324524568图a到达序号服务优先等级服务时长服务次序171012612234325452445683图b若服务大厅提供2个服务窗口(m=2),则所有服务对象完成业务办理需要50分钟。具体方案可以是:0号窗口依次服务到达序号为1、5、3的对象,1号窗口依次服务到达序号为2、4的对象。请回答下列问题:(1)若有6个服务对象的信息如图c所示,根据上述服务规则,在提供3个服务窗口的情况下,所有服务对象完成业务办理需要分钟。

到达序号服务优先等级服务时长132257341341558126411图c(2)定义如下sort_lst(lst)函数,参数lst是所有服务对象信息构成的列表。函数的功能是将列表lst按照服务对象的优先等级降序排列并构成链表,返回排序后的链表及其头指针。defsort_lst(lst):foriinrange(len(lst)):lst[i].append(-1)head=0foriinrange(1,len(lst)):p=headwhilep!=-1:iflst[p][1]>=lst[i][1]:q=pp=lst[p][3]else:breakifp==head:lst[i][3]=headhead=ielse:lst[q][3]=ilst[i][3]=preturnlst,head若lst列表依次存储图c所示的服务对象信息,如lst[0]为[1,3,2],各数据项依次表示服务对象的到达序号,服务优先等级及服务时长。调用sort_lst(lst)时,程序中加框处的语句“q=p”总共执行次。

(3)计算时间段内服务对象完成业务办理所需时间的部分Python程序如下,请在划线处填入合适的代码。defproc(lst,p,n,m):s=[0]*mforiinrange(m):#前m个人直接开始服务,等待时间为0ifp==-1:breaks[i]=lst[p][2]①

ans=0whilep!=-1:k=s[0]#找出正在被服务的对象中最早结束的一个forjinrange(1,m):ifs[j]<k:k=s[j]ans+=kforjinrange(m):s[j]-=kif②:

s[i]=lst[p][2]p=lst[p][3]k=s[0]foriinrange(m):ifs[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]==0andp!=-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进行降序排序。defbubble_sort(lst):n=len(lst)foriinrange(0,n-1):forjinrange(n-1,i,-1):iflst[j-1][1]<lst[j][1]:tmp=lst[j]lst[j]=lst[j-1]lst[j-1]=tmpiflst[i][1]==0:breakreturn调用该函数,若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末尾添加元素xx.w.pop()将列表w末尾元素赋值给x,并将其从w中删除图cdefgroup(data,m):n=len(data)a=[]foriinrange(n+1):a.append([])#a[i]初始化为空列表,存放编号为i的单位所分配的分组编号gnum=0foriinrange(n):#各单位内部分组whiledata[i][1]>=m:gnum+=1k=data[i][0]a[k].append(gnum)①

bubble_sort(data)#根据每个单位的剩余员工人数,对data进行降序排序b=[]foriinrange(m):b.append([])i=0#对剩余员工分组whilei<nanddata[i][1]!=0:②

whilej<mandlen(b[j])==0:j+=1ifj<m:v=b[j].pop()else:gnum+=1v=gnuma[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所示。序号品种送达时间批次质量(千克)128:3516218:5018309:1012409:1514序号品种送达时间批次质量(千克)108:3023序号品种送达时间批次质量(千克)108:4034图a-1序号品种送达时间批次质量(千克)108:3023228:3516308:4034418:5018509:1012609:1514图a-2m=10data=[[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列表按送达时间升序排列,并对序号进行更新。defdata_sort(lst):foriinrange(n-1):#n为数据个数forjinrange(n-1,i,-1):iflst[j][2]<lst[j-1][2]:lst[j],lst[j-1]=lst[j-1],lst[j]lst[i][0]=i+1returnlst执行上述代码后,(填写:能/不能)正确得到图a-2中的数据。

(3)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。defpack(k):#对品种k已送达待打包的物品按质量由大到小输出#部分代码略p=b[k][1]num+=1print("第"+str(num)+"个包裹中品种为"+str(k)+",各物品的序号依次是:",end="")whilep!=-1:print(data[p][0],end=",")p=x[p]print()#合并后排序得到n件物品的数据存储在数组data中并输出,包裹最大承受质量为m千克。物品品种的数量是sn,代码略b=[[0,-1]foriinrange(sn)]x=[-1foriinrange(n)]num=0foriinrange(n):k=data[i][1]ifb[k][0]+data[i][4]>m:pack(k)b[k]=[0,-1]p=①

ifp==-1:b[k][1]=ielse:ifdata[i][4]>data[p][4]:b[k][1]=i②

else:q=-1while③:

q=pp=x[p]x[q]=ix[i]=pb[k][0]+=data[i][4]#质量不足m的品种,按品种依次装入包裹foriinrange(sn):ifb[i][1]!=-1:pack(i)答案(1)3,1(2)不能(3)①b[k][1]②x[i]=p③p!=-1anddata[i][4]<=data[p][4]或p>-1anddata[i][4]<=data[p][4]或p>=0anddata[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号同学的右侧。若三条指令分别为10、21、10,则执行指令后队伍从左到右学号分别为。

(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。#insert(k,x)函数的功能是在k号的右侧插入x号同学#L和R列表分别用于记录每位同学的左侧和右侧的同学学号definsert(k,x):R[x]=R[k]L[x]=k①

R[k]=xL=[0]*100;R=[0]*100;vis=[0]*100insert(0,1)#0的右边插入1号同学#info列表存储各学生姓名和学号,格式如[["张三",1],["李四",2]…],代码略n=int(input("请输入同学人数:"))foriinrange(2,n+1):k=int(input("请问插入在几号同学旁边?"))p=int(input("请输入该同学的左侧还是右侧"))ifp==0:②

else:insert(k,i)q=[[]foriinrange(4)]i=m=0③

whilex!=0:q[i].append(x)m=m+1ifm%2==0:④

x=R[x]foriinrange(4):forjinq[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)%414.(2023学军中学月考,15)学校为了使本校毕业生能以更好的状态参加高考,都会创造条件向上级申请在本校设立标准化考点,让学生能在本校参加考试。标准化考点要求很多,其中之一就是各考场内的座位安排必须是蛇形排列,保证使用A、B卷的同学能完全错开,如图a所示。小明用Python编写了一个模拟考场座位编排程序,程序运行结果如图b所示,每个座位号占4位宽度右对齐。输出程序如下,请在划线处填入合适的代码。defpx(lst):foriinrange(len(lst)-1):k=iforjinrange(①):

iflst[j]>lst[k]:k=jifk!=i:lst[i],lst[k]=lst[k],lst[i]defgssc(t,n):#将字符t按n个字符宽度输出t=""*(n-len(t))+treturntn=int(input('请输入行数:'))m=int(input('请输入列数:'))a=[]forjinrange(m):a.append([])foriinrange(n):a[j].append(②)

foriinrange(m):if③:

px(a[i])foriinrange(n):st=""forjinrange(m):tmp='A'ifa[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)定义如下函数:deff(k):ifk<=3:print(k)returnforiinrange(1,4):f(k-i)return执行语句f(6),则f(3)被调用的次数为()A.1次B.2次C.3次D.4次答案D2.(2024届强基联盟联考,10)执行下列Python代码,输出结果为()deff(s):m=len(s)ifm==1:returnint(s)else:returnf(s[:m-1])+f(s[m-1])print(f("101"))A.11B.2C.5D.101答案B3.(2024届百校起点调研测试,10)定义如下递归函数:deff(a,n):n=n-1ifn==0:returnaelse:returnf(a-1,n)+f(a+1,n)print(f(5,3))程序运行后,输出的结果是()A.10B.20C.30D.40答案B4.(2022宁波九校联考期末,12)某二分查找算法的Python程序段如下,运行该段代码后,输出的结果不可能是()importrandoma=[10,20,30,40,50,60,70,80]key=random.choice(a);i,j=0,len(a)-1s=""whilei<=j:m=(i+j)//2ifkey==a[m]:s=s+"M";breakelifkey<a[m]:j=m-1;s=s+"L"else:i=m+1;s=s+"R"print(s)A.LLMB.LRMC.RRRMD.RRLM答案D5.(2023浙江开学考,12)峰值元素指数组中其值大于左右相邻值的元素,如序列3、8、4、1中8为峰值元素。一个数组r包含多个峰值元素,现需要找出其中一个峰值元素所在的位置(默认第一个数的左侧和最后一个数的右侧为0,即序列1、2、3中3也为峰值元素)。现有实现该功能的Python程序如下:i=0;j=6whilei<j:m=(i+j)//2ifa[m+1]>a[m]:i=m+1else:j=mprint("峰值位置是",i)数组a=[10,2,25,17,20,21,9],执行该程序后,输出的值为()A.0B.2C.5D.8答案C6.(2023十校联盟联考,9)有如下Python程序段:deftrans(m,n):ifm!=0:r=m%nreturntrans(m//n,n)+str(r)else:return"0"a=int(input("a="))b=int(input("b="))print(trans(a,b))执行该程序段,依次输入11和2,则输出的结果是()A.1011B.1101C.01011D.11010答案C7.(2023浙南名校联盟联考,8)小王走楼梯,每次走1个台阶或2个台阶,问小王走n个台阶时,有多少种不同的走法?现编写代码如下:defupstairs(n):ifn==0orn==1:return1else:returnupstairs(n-1)+upstairs(n-2)n=int(input('请输入楼梯有几个台阶:'))way=upstairs(n)print(way)当输入的楼梯有10个台阶时,请问有多少种走楼梯的方法()A.88B.89C.90D.91答案B8.(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如图所示。进程到达时间运行时长优先级A071B242C413D542由优先级抢占式调度算法的规则可知,0毫秒时进程A到达并执行;2毫秒时进程B到达,B的优先级高于A,发生抢占,A剩余的5毫秒回到队列1,B开始执行;4毫秒时进程C到达,C的优先级高于B,发生抢占,B剩余的2毫秒回到队列2,C开始执行;则进程D执行完的时刻为。

(2)模拟实现优先级抢占式调度算法Python程序如下,请在划线处填入合适的代码。definsert(p,remain):data[p][2]=remain#更新进程剩余的运行时间lvl=data[p][3]ifqueinfo[lvl][0]==-1:queinfo[lvl][0]=pifqueinfo[lvl][1]!=-1:data[queinfo[lvl][1]][-1]=pdata[p][-1]=-1queinfo[lvl][1]=pm=int(input('设置优先级的数量m:'))#输入列表data存储进程,data中的节点包含信息有[名称,到达时间,运行时长,优先级],代码略#进程已经按到达时间升序排序#例如:data=[['A',0,7,1],['B',2,4,2],['C',4,1,3],['D',5,4,2]]foriinrange(len(data)):data[i].append(-1)queinfo=[[-1,-1]foriinrange(m+1)]insert(0,data[0][2])#将第1个进程加入队列time=data[0][1]cnt=1#所有队列内等待的进程总数idx=1lvl=mwhilecnt>0:ifqueinfo[lvl][0]!=-1:cur=queinfo[lvl][0]queinfo[lvl][0]=data[queinfo[lvl][0]][-1]cnt-=1①

whileidx<len(data)andtime+data[cur][2]>=data[idx][1]:iflvl>=data[idx][3]ortime+data[cur][2]==data[idx][1]:insert(idx,data[idx][2])cnt+=1idx+=1eliftime+data[cur][2]>data[idx][1]:insert(idx,data[idx][2])#抢占的进程也先入队cnt+=1insert(cur,②)

cnt+=1time=data[idx][1]lvl=data[idx][3]idx+=1flag=Truebreakifflag==False:time=time+data[cur][2]print("时刻",time,":进程",data[cur][0],"完成")lvl=mif③:#仍然有未到达的进程等待入队

insert(idx,data[idx][2])cnt+=1time=data[idx][1]idx+=1else:lvl-=1iflvl==0:lvl=m(3)若将以上程序中insert函数内的加框处代码删除,会导致某些情况下无法得到符合程序功能的结果,下列4组数据中能测试出这一问题的是(单选,填字母)。

A.m=3data=[['A',0,1,1],['B',1,1,2],['C',3,1,3]]B.m=3data=[['A',0,2,2],['B',1,2,3],['C',3,1,3]]C.m=3data=[['A',0,2,1],['B',1,2,3],['C',2,1,2]]D.m=3data=[['A',0,2,2],['B',1,2,3],['C',2,1,1]]答案(1)11(2)①flag=True②data[cur][2]-(data[idx][1]-time)③idx<len(data)andcnt==0(3)D9.(2024届A9协作体联考,15)张三是一名计算机专业的大学生,为了帮助同学们学习专业相关的英语词汇,编写了一个简易字典程序。该程序中存放词汇数据库,在学习中输入英文单词,可以获得中文翻译结果。程序中的词汇数据库采用链表方式存储,首字母相同时按升序排序。查找单词时,首先根据首字母找到同首字母最小单词所在链表,再按照链表顺序查找该单词。(1)根据题意,部分的单词库数据逻辑结构如图所示,查找单词"byte"的过程是"binary"→"bit"→"byte",补充图中空白单元格的值为。

列表索引数据区域指针区域0audio音频-11binary二进制数62byte字节-13cursor光标-14access存取15cache高速缓存36bit比特

(2)wordlist(data,info)函数实现将词汇数据库data以链表的方式按字母序升序排列。info表示词汇数据库中各字母开头的最小单词位置,如info[0]表示字母a开头的最小单词在词汇数据库data中的位置。实现该功能的程序如下,请在划线处填入合适的代码。defwordlist(data,info):n=len(data)foriinrange(n):data[i].append(-1)#data[i]追加一个元素-1foriinrange(n):d=data[i][0]①

ifinfo[k]==-1:info[k]=ielse:head=info[k]q=headwhile②:

p=qq=data[q][2]ifq!=head:data[p][2]=idata[i][2]=qelse:data[i][2]=head③

returndata,info(3)searchword(data,info,key)函数实现单词的查找。程序如下,请在划线处填入合适的代码。defsearchword(data,info,key):k=ord(key[0])-ord("a")head=info[k]p=headwhilep!=-1:ifdata[p][0]==key:return

p=data[p][2]return"没有找到该单词"#读取词汇数据库,存入列表data中,列表的每个元素包含2个数据项,分别为英文单词和中文翻译,如data=[['audio','音频'],['binary','二进制数']…],数据读取存入的代码略info=[-1]*26data,info=wordlist(data,info)key=input("请输入查找单词:").lower()#转化为小写字母res=searchword(data,info,key)print(key,"查找结果是:",res)答案(1)2(2)①k=ord(d[0])-ord('a')②q!=-1andd>data[q][0]③info[k]=i(3)data[p][1]10.(2024届强基联盟联考,15)某校针对高三高考成绩进行分析时,其中有两个主要指标:班级各科平均成绩和班级总分平均成绩。高考成绩保存在“kscj.csv”文件中,格式如图a所示,每行有四个项目,分别是“学号”“姓名”“学科”和“得分”,其中“学号”的前两位表示班级编号,后两位表示该学生班内编号,两种编号均从“01”递增编排。设计如下Python程序,执行后输出上述两个主要指标,如图b所示。请回答下列问题。(1)通读下列程序代码后,可知程序中各班级队列采用的数据结构为(选填,数组/链表)。

(2)函数dataToClassQue功能:根据班级编号,将数据分配到各个班级队列。请在划线处填入合适的代码。defdataToClassQue(data):num=len(data)foriinrange(num):classId=data[i][0]ifqueInfo[classId-1][0]==-1:queInfo[classId-1][0]=ielse:

queInfo[classId-1][1]=ireturn(3)函数dataProcessing功能:统计各班各科平均分和班总分平均分。请在划线处填入合适的代码。defdataProcessing(data):forclassIdinrange(1,classNumber+1):①

score=[[0,0]foriinrange(10)]#班级各科平均分和人数初始化p=queInfo[classId-1][0]whilep!=-1:subjectId=data[p][3]total+=data[p][4]②

score[subjectId][1]+=1p=data[p][-1]forsubjectIdinrange(10):ifscore[subjectId][1]!=0:t=③

averageScore[classId-1][subjectId]=round(t,1)averageScore[classId-1][10]=round(total/score[0][1],1)returndefreadFile(data):#读入原始学生数据,预处理后,存储到data中,代码略#data数据格式:[[6,10,'白凯修',0,117,-1],[6,10,'白凯修',1,109,-1],……]#每条记录包括班级编号,班内编号,姓名,学科编号,得分和预留值-1returnmaxClassId#返回最大班级编号deffmtPrint():#格式化输出,如图b所示,代码略return#主程序course={'语文':0,'数学':1,'英语':2,'物理':3,'化学':4,'生物':5,'政治':6,'历史':7,'地理':8,'技术':9}data=[]#存储读入的数据classNumber=readFile(data)queInfo=[[-1,-1]foriinrange(classNumber)]#初始化队列,用于存储各班级信息averageScore=[[0forkinrange(11)]foriinrange(classNumber)]dataToClassQue(data)dataProcessing(data)fmtPrint()答案(1)链表(2)data[queInfo[classId-1][1]]=i(3)①total=0②score[subjectId][0]+=data[p][4]③score[subjectId][0]/score[subjectId][1]11.(2024届百校起点调研测试,15)某医院的团体体检流程如下:编号登记:为n位体检者设置体检编号1~n。体检呼叫:体检项目处空闲时呼叫下一个体检者(编号小的优先),若多个项目同时呼叫,体检者到优先级小的项目处体检。仅考虑常规体检项目,各个项目的优先级及体检时间如图所示。项目名称B超心电图抽血尿常规C14检测胸透一般常规优先级0123456时间(min)12522221前去体检:各个体检项目之间相互独立,互不影响;病人排队体检和体检完毕到下一科室之间没有时间延迟。(1)某个团队4人(分别用编号1,2,3,4表示)参加体检,开始体检后第5分钟,4号在检查(填写项目名称)项目。

(2)定义如下lst(n)函数,生成n人体检队列。若体检人数为4,则que生成结果如图所示。队列索引号体检编号已检测项目01[]12[]23[]34[]deflst(n):que=[]foriinrange(n):temp=[i+1,[]]que.append(temp)returnque若加框处语句改为:foriinrange(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:一般常规→抽血→尿常规→C