资源简介

9.2　以链表形式组织数据
学习目标　
1.能根据问题特点规划节点的数据域和指针域,完成创建链表、访问链表节点的操作。
2.对已有数据进行分类处理,掌握记录每个类别的第1个数据节点和每个数据节点之间的前后关系,形成多条数据链表的方法。
(2024年6月浙江选考)某工程包含n个任务(编号为0~n-1),每天可以有多个任务同时进行。某些任务之间有依赖关系,如图a所示,任务4依赖于任务1,任务1依赖于任务2。即任务2完成后才可以开始任务1,任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务,或多个任务依赖于同一个任务的情况。现已对该工程的依赖关系进行了梳理,结果如图b所示,标记“T”表示依赖关系需保留,标记“F”表示依赖关系需删除。
根据每个任务完成所需的天数和梳理后的依赖关系,编写程序,首先删除标记为“F”的依赖关系,然后计算工程最快完成所需的天数,并以工程最快完成所需的天数为期限,计算每个任务最晚必须开始的时间。
任务A 任务B 标记
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注:任务A依赖于任务B
图b
请回答下列问题:
(1)若某工程有6个任务,任务间依赖关系如图a所示,完成任务0~5所需天数分别为2,1,3,5,1,6,则工程最快完成需要　　　　天。
(2)定义如下erase(lst)函数,参数lst列表的每个元素表示一个依赖关系。函数的功能是删除标记为“F”的依赖关系,返回保留的依赖关系的个数。
def erase(lst):
　　i=0;j=len(lst)-1
　　while i<=j:
　　　　if lst[i][2]=='T':
　　　　　　i+=1
　　　　else:
　　　　　　if lst[j][2]=='T':
　　　　　　　 lst[i]=lst[j];i+=1
　　　　　　j -=1
　　return i
若lst列表依次存储图b所示的依赖关系,如lst[0]为[0,5,'T'],调用erase(lst)的数,则语句“lst[i]=lst[j]”的执行次数为　　　　。
(3)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
def proc(n,lst,task):
　　pr=[0]*n;w=[0]*n
　　m=erase(lst)
　　for i in ①　　　　　　:
　　　　task[lst[i][1]][1]=lst[i][0]
　　　　pr[lst[i][0]]=1
　　c=[];days=0
　　for i in range(n):
　　　　if pr[i]==0:
　　　　　　k=i;s=0
　　　　　　while k!=-1:
　　　　　　　　c.append(k)
　　　　　　　　s+=task[k][0]
　　　　　　　　②　　　　　
　　　　　　if s>days:
　　　　　　　　days=s
　　for i in range(n-1,-1,-1):
　　　　k=c[i]
　　　　if task[k][1]==-1:
　　　　　　w[k]=days-task[k][0]+1
　　　　else:
　　　　　　③　　　　　
　　#输出days,以及保存在w中的每个任务最晚必须开始的时间,代码略
#工程包含的任务数存入变量n。任务间的依赖关系存入1st列表,1st[0]包含3项,任务1st[i][0]依赖于任务1st[i][1],1st[i][2]存放保留/删除标记,任务数据存入task列表task[i]包含2项,task[i][0]为完成任务所需天数,task[i][1]的初值为-1,代码略。
proc(n,lst,task)
高中阶段的数据结构不是讨论如何使用数据结构,而是通过对数据集进行简单的操作,理解和创建数据结构。能将有限制条件的、真实情境中的数据关系进行抽象,根据数据特点与求解要求,选择适当的数据类型表示各种数据,并用合适的数据结构表达数据的逻辑关系。在已有数据集的基础上,通过链接关系构造逻辑上先后遍历顺序,构建链表,将有层次非线性结构或二维数组转换为一维数组,再遍历一维数组,得到问题的解。当原始数据量大,且每个数据元素有多个数据项时,直接对其进行复制会浪费大量空间和时间,可进行基于索引的引用,提高效率。
例题 某市举行体育赛事活动,n所学校的选手已完成预赛,现计划根据预赛的成绩挑选s名选手参加市决赛。成绩位列所在学校前w名次的选手直接入选,剩余名额按成绩由高到低依次挑选,成绩相同的选手一并入选,选中的选手数一旦达到或超过s名,挑选结束。
现给定所有选手预赛的成绩数据表,每位选手的数据包含学校编号(0~n-1)、选手编号、成绩,成绩数据表已按成绩由高到低排列。编写程序,计算各选手的校内名次,再按上述规则挑选决赛选手,按成绩数据表中的顺序输出选手编号,同时提供查询功能。选手校内名次的计算方法是:若选手所在学校有m人成绩高于该选手,则该选手的名次为m+1。
在如图所示的样例中,n、s、w分别为3、8、2,根据图中前3行数据计算出了每位选手的校内名次,进而选出实际入选的9名选手。
学校编号 0 2 2 0 0 2 2 0 1 1 1 1
选手编号 0002 2027 2002 0072 0182 2071 2128 0012 1081 1002 1008 1208
成绩 198 185 183 182 182 177 177 176 175 163 161 161
校内名次 1 1 2 2 2 3 3 4 1 2 3 3
是否入选 True True True True True True True False True True False False
请回答下列问题:
(1)对于如图所示前4行数据,若s、w分别为5和1,则0号学校入选人数是　　　　。
(2)定义如下search(data,sid,score)函数,data列表每个元素的前5个数据项依次为学校编号、选手编号、成绩、校内名次、是否入选,列表已按成绩由高到低排列。函数功能是查找选手编号为sid、成绩为score的元素,返回其下标,若未找到则返回-1。
def search(data,sid,score):
　　left,right=0,len(data)-1
　　f=-1
　　while left<=right:
　　　　mid=(left+right)//2
　　　　if score==data[mid][2]:
　　　　　　f=mid;left=mid+1
　　　　elif score　　　　　　left=mid+1
　　　　else:
　　　　　　right=mid-1
　　if f==-1:
　　　　return -1
　　for i in range(f,len(data)):
　　　　if data[i][2]!=score:
　　　　　　return -1
　　　　elif data[i][1]==sid:
　　　　　　return i
①调用search函数,若data列表长度为12,data[0][2],data[1][2],…,data[11][2]的值依次为:198,185,183,182,182,177,177,176,175,163,161,161,score值为177,则while语句中循环体的执行次数是　　　　。
②程序中加框处代码有错,请改正。
(3)实现根据选手成绩(成绩不超过200)计算校内名次,以及挑选决赛选手功能的Python程序如下,请在划线处填入合适的代码。
def proc(data,n,s,w):
　　#创建r列表,共n个元素,每个元素的值均为[0,0,201],代码略
　　heads=[-1,-1];tails=[-1,-1]
　　cnt=0
　　for i in range(len(data)):
　　　　①　　　　　
　　　　r[k][1]+=1
　　　　if data[i][2]　　　　　　r[k][2]=data[i][2]
　　　　　　②　　　　　
　　　　data[i][3]=r[k][0]
　　　　data[i].append(-1)　#为data[i]追加一个元素-1
　　　　v=1
　　　　if data[i][3]<=w:
　　　　　　data[i][4]=True
　　　　　　cnt+=1;v=0
　　　　if heads[v]==-1:
　　　　　　heads[v]=i
　　　　else:
　　　　　　data[tails[v]][5]=i
　　　　tails[v]=i
　　p,q=heads[0],heads[1]
　　res=[]　#res列表用于存放入选决赛的选手编号,顺序与data列表保持一致
　　while cnt　　　　tmp=data[q][2]
　　　　while q!=-1 and data[q][2]==tmp:
　　　　　　③　　　　　　:
　　　　　　　　res.append(data[p][1])
　　　　　　　　p=data[p][5]
　　　　　　res.append(data[q][1])
　　　　　　data[q][4]=True;cnt+=1
　　　　　　q=data[q][5]
　　while p!=-1:
　　　　res.append(data[p][1])
　　　　p=data[p][5]
　　return res
#读取n、s、w;读取选手成绩数据表存入data列表,每个元素包含学校编号、选手编号、成绩、校内名次(初值为0)、是否入选(初值为False)5个数据项,代码略
res=proc(data,n,s,w)
#输出res列表中的入选选手编号,代码略
#读取待查询的选手编号与成绩,调用search函数,根据返回值输出查询结果,代码略
变式 某市A区域有一套租车系统,设有m个公共自行车租车点(编号0~m-1),市政部门投放n辆自行车(编号1~n,n为m的倍数)并平均分配。用户可在租车点借车,之后将自行车归还到任意租车点。每天特定时间,工作人员根据系统指示,从存量超出平均数的租车点回收最新归还的若干辆自行车,再分配给存量低于平均数的租车,以保证各租车点自行车数量相等。
若m为3,n为12,初始自行车分配情况如图a所示。经过若干次租借与归还操作(记录如图b)之后,各租车点的自行车编号如图c所示。
租车点 车编号
A0 1,2,3,4
A1 5,6,7,8
A2 9,10,11,12
图a
车编号 租车点 还车点
1 A0 A2
8 A1 A2
6 A1 A0
图b
租车点 车编号
A0 6,2,3,4
A1 5,7
A2 8,1,9,10,11,12
图c
回收时,工作人员从A2租车点回收8号和1号自行车,并重新分配给A1租车点,完成后,A1租车点的自行车编号为8,1,5,7;A2租车点的自行车编号为9,10,11,12。
(1)若将图b中最后一条租借信息的自行车编号由6修改为5,则次日A0租车点的自行车编号为　　　　。
(2)定义如下rent(x,y,z)函数,参数x,y,z分别表示编号x的自行车从y租车点借出后归还至z租车点。函数功能是处理一条借还车记录。
def rent(x,y,z):
　　queinfo[y][1]-=1;queinfo[z][1]+=1
　　head=queinfo[y][0]
　　if x==bikelst[head][0]:
　　　　　　　　　　　　
　　else:
　　　　#处理编号x的自行车在y租车点其他位置的情况,代码略
加框处代码由下列3条语句组成,①bikelst[head][1]=queinfo[z][0];②queinfo[z][0]=head;③queinfo[y][0]=bikelst[head][1]。正确的排列顺序为　　　　。
(3)实现回收和重新分配自行车的部分Python程序如下,请在划线处填入合适代码。
def proc(bikelst,queinfo,m,num):
　　#从自行车存量超平均数的租车点回收自行车
　　head,tail=-1,-1
　　for i in range(m):
　　　　q=queinfo[i][0]
　　　　if queinfo[i][1]>num:
　　　　　　if head==-1:
　　　　　　　　head=queinfo[i][0]
　　　　　　else:
　　　　　　　　①　　　　　
　　　　　　while queinfo[i][1]> num:
　　　　　　　　p=q;q=bikelst[q][1]
　　　　　　　　②　　　　　
　　　　　　queinfo[i][0]=q;tail=p
　　#将回收的自行车重新分配到各租车点
　　q=head
　　for i in range(m):
　　　　③　　　　　
　　　　if cnt>0:
　　　　　　while cnt>0:
　　　　　　　　p=q;q=bikelst[q][1]
　　　　　　　　cnt-=1
　　　　　　bikelst[p][1]=queinfo[i][0]
　　　　　　queinfo[i][0]=head;head=q
　　　　　　queinfo[i][1]=num
#读取自行车和租车点数量,分别存入变量n和m,代码略
#读取租车信息,过滤租车点与还车点编号前的字母A后存入lst列表。#lst[i][0],lst[i][1],lst[i][2]分别表示第i条租车记录中自行车编号,租车点编号,还车点编号,代码略。
num=n//m　#每个租车点分配的自行车数量
bikelst=[[i,i]for i in range(1,n+1)]
bikelst[n-1][1]=-1
queinfo=[]　#列表queinfo存放各租车点相关信息
for i in range(0,n,num):
　　queinfo.append([i,num])
for i in range(len(lst)):
　　rent(lst[i][0],lst[i][1],lst[i][2])
proc(bikelst,queinfo,m,num)　#回收并重新分配自行车
1.某音乐播放器中的“最近播放功能”是一种记录用户近期音乐播放历史的功能,该功能实现逻辑如下:(a)缓存容量限制n(n>0):最近播放列表中最多存储n首歌曲。(b)当播放列表中歌曲播放时:若已在缓存中,将其移动到最近播放列表最前端。若不在缓存中且缓存未满,直接加入最近播放列表最前端。若不在缓存中且缓存已满,删除最近播放列表末尾的歌曲,再将新歌曲加入最近播放列表最前端。
现给定用户的歌单列表data,每首歌曲的信息包含歌曲编号、歌曲名称、歌曲推荐值(0-100之间),data中歌曲按照歌曲推荐值降序排序,编写程序模拟播放data歌单列表过程中实时输出最近播放记录。当n=3,data 排序后数据如下表所示时,播放过程中的最近播放记录如下表最后一行显示。
歌曲编号 A1001 A1002 B2201 B2202 B2201 C1001 D1008
歌曲名称 《吻别》 《晴天》 《望》 《孤勇者》 《望》 《如愿》 《光亮》
歌曲推荐值 86 80 73 73 73 70 68
最近播放记录 《吻别》 《晴天》 《望》 《孤勇者》 《望》 《如愿》 《光亮》
《吻别》 《晴天》 《望》 《孤勇者》 《望》 《如愿》
《吻别》 《晴天》 《晴天》 《孤勇者》 《望》
(1)对于上表中data数据,若n更改为5时,data列表中歌曲播放完毕后,最近播放记录中最后一首歌曲名称为　　　　。
(2)定义如下函数bubble_sort(data),data列表中每个元素包含三项,分别是歌曲编号、歌曲名称、歌曲推荐值,该函数实现对data列表按照歌曲推荐值降序排序。
def bubble_sort (data):
　　n=len(data)
　　for i in range(n-1):
　　　　flag=False
　　　　for j in range (n -i -1):
　　　　　　if　　　　:
　　　　　　　　data[j],data[j+1]=data[j+1],data[j]
　　　　　　　　flag=True
　　　　if not flag:break
　　return data
①请在划线处填入正确的代码。
②加框处代码替换为下列哪个选项不影响函数功能　　　　(单选,填字母)。
A.n-2,i-1,-1 B.1,n-i
C.n-l,i,-1 D.i,n-i
(3)实现模拟音乐播放时显示最近播放记录的部分Python程序如下,请在划线处填入合适的代码。
#函数功能为在链表lst中查找歌曲编号为songid的位置,head为头节点,lst中每个节点有三个区域,分别为歌曲编号、歌曲名称和指向下个节点的指针
def find_song(lst,head,songid):
　　pre=p=head
　　while p!=-1:
　　　　if lst [p][0]==songid:
　　　　　　break
　　　　pre=p;p=lst[p][2]
　　return pre,p
#读取缓存容量限制n,用户的播放数据存入data列表data[0]包含3项,data[0][0]存放歌曲编号,data[0][1]存放歌曲名称,data[0][2]存放歌曲推荐值,代码略
lst=[];head=-1
length=0 　#存储播放记录中歌曲数量
data=bubble_sort(data)
for song in data:
　　pre,cur=find_song(lst,head,song[0])
　　if cur==-1:
　　　　lst.append([song[0],song[1],-1])　#列表lst中末尾追加一个新的节点
　　　　length+=1
　　　　if length<=n:
　　　　　　if length==1:head=0
　　　　else:
　　　　　　p=q=head
　　　　　　while lst[q][2]!=-1:
　　　　　　　　p=q;q=lst[q][2]
　　　　　　①　　　　　
　　　　if length>1:
　　　　　　lst[-1][2]=head;head=len(lst)-1
　　else:
　　　　if cur!=head:
　　　　　　lst[pre][2]=lst[cur][2]
　　　　　　②　　　　　
　　　　　　head=cur
#从lst中head节点开始输出每个节点的歌曲名称,代码略
2.某省举行大型考试,现需对考试数据进行统计分析:输入特定分数区间的最低分和最高分(分数为0~750的整数),统计该区间人数并按成绩降序输出该区间考生信息。若输入区间最低分为-1,则结束统计。输出的考生信息包含三项数据:学校名称、准考证号和考试成绩。
考试数据与学校信息分别存储在不同的表中,如考试部分数据如图a所示,学校信息部分数据如图b所示。
学校代码 准考证号 考试成绩
0101 2310108005 695
0103 2310115001 694
0803 2310106003 707
0501 2310103006 699
0909 2310122002 698
…… …… ……
图a
学校代码 学校名称
0101 A中学
0103 B中学
0501 C中学
0803 D中学
0804 E中学
…… ……
图b
请回答下列问题:
(1)若该考试分数段680~698的考生人数为2185人,分数段690~698的考生人数为708人,则分数段680~689的考生人数为　　　　。
(2)定义如下search(school,key)函数,功能为在school中查找学校代码为key的学校名称。
def search(school,key):
　　i,j=0,len(school)-1
　　while i<=j:
　　　　m=(i+j)//2
　　　　if school[m][0]>key:
　　　　　　j=m-1
　　　　else:
　　　　　　i=m+1
　　return school[j][1]
调用该函数,若school为[['0101','A中学'],['0103','B中学'],['0501','C中学'],['0803','D中学'],['0804','E中学'],['0909','F中学']],请回答①和②两个问题:
①若查找key的值为“0909”,则需要查找的次数为　　　　。
②若将“return school[j][1]”改为“return school[m][1]”,会导致某些情况下无法得到符合函数功能的结果。下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.key='0101' B.key='0103'
C.key='0803' D.key='0909'
(3)实现上述功能的Python程序如下,请在划线处填入合适代码。
#读取n名考生的考试数据存到列表data中,data中每个元素包含3个数据项,分别对应每位考生的学校代码、准考证号和考试成绩;
#读取参加本次考试的学校信息存储到列表school中,school中每个元素包含2个数据项,分别为学校代码和学校名称,并按学校代码升序排序;代码略
m=750;head=[-1]*(m+1)
for i in range(n):
　　data[i].append(-1)
sum=[0]*(m+1)　#sum[i]存储大于等于分数i的人数
for i in range(n):
　　k=data[i][2]
　　sum[k]+=1
　　①　　　　　
　　head[k]=i
for k in range(m-1,-1,-1):
　　sum[k]+=sum[k+1]
while True:
　　low=int(input("请输入区间最低分:"))
　　high=int(input("请输入区间最高分:"))
　　if low==-1: break
　　i=high
　　while i>=low:
　　　　②　　　　　
　　　　while p!=-1:
　　　　　　s=search(school,data[p][0])
　　　　　　print("学校",s,"学号",data[p][1],"成绩",data[p][2])
　　　　　　p=data[p][3]
　　　　i-=1
③　　　　　
print(low,"~",high,"区间的总人数为:",total)
3.“抢单”是外卖骑手的日常,当外卖平台上一个新的订单出现时,骑手需要在短时间内考虑是否抢单。平台根据骑手的实际信息,给出是否抢单的建议,若建议抢单则给出到达各个取送点的顺序。平台判断是否抢单的算法设计如下:
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,　　　　(选填:影响/不影响)程序执行。
def totd(riderlist,h):
　　speed=0.3　#speed为骑手每分钟公里数
　　total=0;pre=h
　　cur=riderlist[pre][4]
　　while cur!=-1:
　　　　#计算pre与cur两个节点所在位置间的路程,存储在变量d中
　　　　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];p=head=0
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.某快递驿站有A、B两类货架,收到的包裹重量小于等于10存放于A货架,其余存放于B货架。编写程序模拟生成取件码和顾客的取件过程,取件码是根据当前已处理的包裹数量生成,如A-0001表示当天第一个处理的包裹存放在A货架,B-0003表示当天第三个处理的包裹存放在B货架。取件码与顾客手机号关联,程序根据输入的手机号显示其所有包裹的取件码,并允许顾客一次性提取或者部分提取。程序的部分运行界面如图a和图b所示。
(1)当前已处理的包裹取件码是A-0158,若下一个包裹重量是12,其取件码为　　　　。
(2)定义函数save(pnum,code),参数pnum为手机号,code为取件码。函数功能是将一条包裹信息存储到列表goods和列表dic中。如图a的包裹数据,手机号“180****1215”在两个列表中的数据分别为goods[4]=["B-0005",-1]、goods[9]=["A-0010",4]和dic[2]=["180****1215",9,2]。
①若调用该函数继续存储手机号“180****1215”的包裹,其取件码是“B-0011”,则对应dic[2]的值变为["180****1215",　　　　,　　　　]。
②函数save代码如下,程序中加框处代码有错,请改正。
def save(pnum,code):
　　goods.append([code,-1])
　　n=len(goods)-1
　　print(n,"号包裹的手机号:",pnum,"取件码:",code)
　　num=search(dic,pnum)　#函数返回手机号pnum 在dic中的索引号,未找到返回-1
　　if num==-1:
　　　　dic.append([pnum,n,1])　#新增一个包裹信息
　　else:
　　　　goods[n][1]=dic[num][1]
　　　　dic[num][1]=n
　　　　dic[num][2]+=1
(3)实现取件功能的部分Python程序如下,请在划线处填入合适的代码。
x=input("请输入您的手机号:")
num=search(dic,x)
if num!=-1:
　　#输出手机号为x的当前所有包裹信息,代码略
　　op=int(input("输入0取全部包裹,输入1取部分包裹:"))
　　if op==0:
　　　　print("您的包裹已经取完!")
　　　　del dic[num] #删除dic中索引为num的元素
　　else:
　　　　order=input("请输入本次的取件码,只输入#表示结束取件:")
　　　　while order!="#":
　　　　　　①　　　　　
　　　　　　p,q=head,head
　　　　　　while goods[q][0]!=order:
　　　　　　　　p=q
　　　　　　　　②　　　　　
　　　　　　if p==head:
　　　　　　　　dic[num][1]=goods[q][1]
　　　　　　else:
　　　　　　　　goods[p][1]=goods[q][1]
　　　　　　dic[num][2]-=1
　　　　　　if dic[num][2]==0:
　　　　　　　　print("您的包裹已经取完!")
　　　　　　　　break
　　　　　　#输出手机号为x的当前所有包裹信息,代码略
　　　　　　order=input("请输入本次的取件码,只输入#表示结束取件:")
else:
　　print("查无此号,请检查后重新输入!")
2.某校进行体育之星评比,现有引体向上、俯卧撑、仰卧起坐、跳绳四个项目。学生自愿参加其中一项评比,成绩前num名(包含num,同名次均可)同学为该项目的体育之星。保证每个项目都有超过num人参加。编写程序完成上述功能并输出结果。
(1)定义如下函数insert(a,i,k),函数的功能是实现数据的有序插入。
def insert(a,i,k):
　　if queinfo[k][1]==-1:
　　　　queinfo[k][1]=i
　　elif a[i][3]>=a[queinfo[k][0]][3]:
　　　　a[i][4]=queinfo[k][0]
　　　　queinfo[k][0]=i
　　elif 　　　　　　:
　　　　a[queinfo[k][1]][4]=i
　　　　queinfo[k][1]=i
　　else:
　　　　q=queinfo[k][0];p=a[q][4]
　　　　while p!=-1 and a[p][3]>a[i][3]:
　　　　　　q=p;p=a[p][4]
　　　　a[i][4]=p;a[q][4]=i
①若函数中加框语句改成“p!=-1 and a[p][3]②在划线处填写合适的代码。
(2)实现上述功能的Python程序如下,请在程序中划线处填入合适的代码。
#读取数据存入列表data中,代码略
#列表data[i]包含五个元素,data[i][0]、data[i][1]、data[i][2]、data[i][3]、data[i][4]分别表示班级、姓名、项目名称、成绩、指针域。如["101班","王**","引体向上",2,-1]
queinfo=[[-1,-1] for i in range(4)]
programe={"引体向上":0,"俯卧撑":1,"仰卧起坐":2,"跳绳":3}
num=50;rs=[0]*4
for i in range(len(data)):
　　①　　　　　
　　if queinfo[k][0]==-1:
　　　　queinfo[k][0]=i
　　if rs[k]>=num and data[queinfo[k][1]][3]>data[i][3]:
　　　　continue
　　insert(data,i,k);rs[k]+=1
for i in programe:
　　print('\n',i,"项目体育之星如下:")
　　count=1
　　q=②　　　　　
　　p=data[q][4]
　　print(data[q][0],data[q][1],end='、')
　　while count　　　　count+=1
　　　　print(data[p][0],data[p][1],end='、')
　　　　q=p;p=data[p][4]
(3)data数据为[["101班","周**","跳绳",100,-1],["103班","叶*","跳绳",50,-1],["107班","幸**","跳绳",105,-1],["111班","陈**","跳绳",100,-1],["113班","郑*","跳绳",171,-1]],若num值为3,则需要输出跳绳项目的体育之星insert(a,i,k)函数调用　　　　次。
3.某学校举办社团节,在一条直路的同侧依次有n个社团展位,按展位到入口距离从1至n依次编号。从入口处走到第1个展位需要花费dis[0]单位时间,从第i个展位走到第i+1个展位需要花费dis[i]单位时间。每个展位举行若干活动,每参加一个活动需要5单位时间。对于第i个展位,第一次参加活动获得a[i-1]个积分,第二次参加活动获得a[i-1]-b[i-1]个积分,第三次参加活动获得a[i-1]-2*b[i-1]个积分……以此类推。现在小明从入口处出发,他共有m单位时间自主选择参与社团的活动并回到入口处。编写程序实现规定时间内获得最多积分的活动方案及获得的积分数。
例:
展位 1 2 3
首次活动积分 10 15 20
每次下降的积分 4 6 4
与前一展位之间步行所花时间 1 3 4
若小明可用时间为28,部分方案如下:
方案1:参加前1个展位活动,有5次活动机会,可得积分为10+6+2=18
方案2:参加前2个展位活动,有4次活动机会,可得积分为15+10+9+6=40
方案3:参加前3个展位活动,有2次活动机会,可得积分为20+16=36
则可获得的最多积分为40,运行界面如图所示。
展位数:3 可用时间:28 各展位首次参加活动可获得的积分:10 15 20 各展位每次下降的积分:4 6 4 相邻展位之间步行花费时间:1 3 4 能获得的最多积分是:40 各展位参加的活动次数分别为:[2,2,0]
(1)若小明可用时间为32,按上表数据可得最多积分为　　　　。
(2)定义如下insert(head,r)函数,功能是在首节点下标为head的链表中插入下标为r的节点,返回新的链首节点下标。data[i]存储下标为i的节点数据,data[i][0]存储目前参加活动能获得的积分,data[i][1]存储参加活动后要下降的积分,data[i][2]存储后继节点下标。
def insert(head,r):
　　p=q=head
　　while q!=-1 and data[r][0]　　　　p=q;q=data[q][2]
　　if q==head:
　　　　data[r][2]=head;head=r
　　else:
　　　　data[p][2]=r;data[r][2]=q
　　return head
若函数加框处代码误写为"data[r][0]A.data=[[6,6,-1],[10,3,3],[2,11,-1],[7,5,2]];head=1;r=0
B.data=[[6,6,-1],[10,3,3],[2,11,-1],[7,5,0]];head=1;r=2
C.data=[[6,6,2],[10,3,0],[2,11,-1],[7,5,-1]];head=1;r=3
D.data=[[6,6,2],[10,3,-1],[2,11,-1],[7,5,0]];head=3;r=1
(3)实现上述功能的Python程序如下,请在划线处填入合适的代码。
#展位数存入变量n,可用时间存入变量m,各展位首次参加活动可获得的积分存入a列表,各展位每参加一次活动要下降的积分存入b列表,相邻展位之间步行花费时间存入dis列表,dis[0]为入口到第1个展位步行花费时间,dis[i](i>0)为第i个展位到第i+1个展位步行花费时间,代码略
for i in range(1,n):
　　dis[i]=①　　　　　
data=[]
for i in range(n):
　　data.append([a[i],b[i],-1])
ans=0　#记录能够获得的最多积分
best=[]　#记录一种能够获得最多积分的活动方案
for i in range(n):
　　head=-1
　　for j in range(i+1):
　　　　data[j][0]=a[j]
　　　　head=insert(head,j)
　　t=(m-2*dis[i])//5
　　if t<=0: break
　　total=0;count=[0]*n　#记录临时方案
　　while ②　　　　　　:
　　　　p=head;head=data[head][2]
　　　　total+=data[p][0]
　　　　count[p]+=1
　　　　data[p][0]=③　　　　　
　　　　if data[p][0]>0:
　　　　　　head=insert(head,p)
　　　　t-=1
　　if total>ans:
　　　　#更新ans和best代码略
#输出代码略
4.有2组器件共n个,要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先级。优先级有m(1编写程序模拟检测过程,先合并2组器件的数据,然后计算所有器件的平均等待时长,其中每个器件等待时长为其开始检测的时间与送达时间的时间差。(时间单位均为秒)
请回答下列问题:
(1)由题意可知,图中器件A、B、C、D的检测顺序为A-C-D-B,A、C、D的等待时长分别为0、1、0,B的等待时长是　　　　。
(2)定义如下merge(lst1,lst2)函数,参数lst1和lst2的每个元素由送达时间、检测时长和优先级3项构成,lst1和lst2均已按送达时间升序排列。函数功能是将lst2中的元素合并到lst1中,并将lst1按送达时间升序排列,函数返回lst1。
def merge(lst1,lst2):
　　i=len(lst1)-1;j=len(lst2)-1
　　for t in range(len(lst2)):
　　　　lst1.append([0,0,0])　#为lst1追加一个元素[0,0,0]
　　k=len(lst1)-1
　　while j>=0:
　　　　if i>=0 and lst1[i][0]>lst2[j][0]:
　　　　　　lst1[k]=lst1[i];i-=1
　　　　else:
　　　　　　lst1[k]=lst2[j];j-=1
　　　　k-=1
　　return lst1
①调用merge(lst1,lst2)函数,若lst1为[[0,3,2],[1,1,2],[12,2,2]],lst2为[[2,1,1],[4,3,0],[11,3,2]],则while语句中循环体的执行次数是　　　　。
②若函数中while 语句的条件“j>=0”误写为“k>=0”,会导致某些情况下无法得到符合函数功能的结果。调用merge(lst1,lst2)函数,下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.lst1=[[0,3,2],[4,3,0]]
lst2=[[1,1,2]]
B.lst1=[[1,1,2]]
lst2=[[0,3,2],[4,3,0]]
C.lst1=[[1,1,2],[4,3,0]]
lst2=[[0,3,2]]
D.lst1=[[4,3,0]]
lst2=[[0,3,2],[1,1,2]]
(3)实现模拟检测过程并计算平均等待时长的部分Python程序如下,请在划线处填入合适的代码。
def proc(data,m):
　　n=len(data)
　　queinfo=[[-1,-1] for i in range(m)]
　　for i in range(n):
　　　　data[i].append(-1)　#data[i]追加一个元素-1
　　curtime=0;waitnum=0;i=0
　　①　　　　　
　　while i0:
　　　　if i　　　　　　k=data[i][2]
　　　　　　if queinfo[k][0]==-1:
　　　　　　　　queinfo[k][0]=i
　　　　　　else:
　　　　　　　　②　　　　　
　　　　　　　　data[p][3]=i
　　　　　　queinfo[k][1]=i
　　　　　　waitnum+=1;i+=1
　　　　elif waitnum>0:
　　　　　　k=0
　　　　　　while queinfo[k][0]==-1:
　　　　　　　　k+=1
　　　　　　p=queinfo[k][0]
　　　　　　total+=curtime-data[p][0]
　　　　　　curtime+=data[p][1]
　　　　　　③　　　　　
　　　　　　waitnum-=1
　　　　else:
　　　　　　curtime=data[i][0]
　　return total/n
#读取2组器件的数据,分别存入列表data1和data2中。2个列表的每个元素包含3个数据项,分别对应器件的送达时间、检测时长和优先级。data1和data2中的数据已分别按送达时间升序排列,代码略
#读取优先级等级个数存入m,代码略
data=merge(data1,data2)
print(proc(data,m))
5.在科学研究中往往会使用超级计算机来进行数据处理。某超级计算机需要根据第二天的预约计划安排计算任务,预约计划包含项目名称、数据上传时刻和计算所需时长,数据上传之后才能开始计算。为保证计算的正确率,每个任务开始之后不能中断,计算完成之后才能开始下一个任务。该计算机每天开机time时刻后,需关机进行维护。现根据预约计划安排计算任务。
安排任务的规则为:舍弃time时刻内无法完成计算的任务后,若没有等待中的任务,上传时刻最早的任务安排计算;若有等待中的任务,等待任务中所需时间最短的任务安排计算。
设time=100,预约计划如图所示。任务B、E无法在time时刻内完成被舍弃,F最早完成数据上传开始计算,计算中任务A、C、D完成数据上传等待计算。F计算完成后,A开始计算。最后的任务安排为FACD。请回答下列问题:
项目 上传时刻 时长
A 30 10
B 70 65
C 25 25
D 30 35
E 40 70
F 0 30
(1)若将图中项目E的所需时长改为5后重新安排计算任务,则任务安排为　　　　。
(2)定义如下retain(a)函数,参数a的每个元素由项目名称、数据上传时刻和所需时长构成。函数的功能是根据数据上传时刻对a进行升序排序,同时返回能够在time时刻内完成的任务数。
def retain(a,time):
　　n=len(a);k=n
　　i=0;jc=0;flag=False
　　while not flag:
　　　　flag=True;c=0;jc+=1
　　　　for j in range(1,k):
　　　　　　if a[j-1][1]+a[j-1][2]>time or a[j-1][1]>a[j][1]:
　　　　　　　　a[j],a[j-1]=a[j-1],a[j]
　　　　　　　　flag=False
　　　　　　　　c=j
　　　　k=c
　　i,j=0,n-1
　　while i<=j:
　　　　mid=(i+j)//2
　　　　if a[mid][1]+a[mid][2]>time:
　　　　　　j=mid-1
　　　　else:
　　　　　　i=mid+1
　　return　　　
①调用retain(a)函数,若time为100,a为[["A",0,30],["B",10,65],["C",15,25],["D",30,80],["E",40,5],["F",30,10]],则变量jc的值为　　　　。
②划线处应填入的代码为　　　　(单选,填字母:A.i/B.j/C.mid)。
(3)实现任务安排的Python程序如下,请在划线处填入合适的代码。
def proc(a,m):
　　now=i=0
　　task=[];h=-1
　　while i　　　　if i=now and h==-1:
　　　　　　①　　　　　
　　　　　　if now<=time:
　　　　　　　　task.append(a[i][0])
　　　　　　i+=1
　　　　elif i　　　　　　if h==-1:
　　　　　　　　h=i
　　　　　　else:
　　　　　　　　if a[i][2]　　　　　　　　　　a[i][3]=h
　　　　　　　　　　h=i
　　　　　　　　else:
　　　　　　　　　　q=p=h
　　　　　　　　　　while p!=-1 and a[i][2]>=a[p][2]:
　　　　　　　　　　　　q=p
　　　　　　　　　　　　p=a[p][3]
　　　　　　　　　　a[q][3]=i
　　　　　　　　　　③　　　　　
　　　　　　i+=1
　　　　else:
　　　　　　now+=a[h][2]
　　　　　　if now<=time:
　　　　　　　　task.append(a[h][0])
　　　　　　h=a[h][3]
　　　　if now>time:
　　　　　　break
　　return task
#读取time;读取预约计划存入a列表,每个元素包含项目名称、数据上传时刻和计算所需时长,代码略
m=retain(a,time)
for i in range(m):
　　a[i].append(-1)
ans=proc(a,m)
print(ans)9.2　以链表形式组织数据
学习目标　
1.能根据问题特点规划节点的数据域和指针域,完成创建链表、访问链表节点的操作。
2.对已有数据进行分类处理,掌握记录每个类别的第1个数据节点和每个数据节点之间的前后关系,形成多条数据链表的方法。
(2024年6月浙江选考)某工程包含n个任务(编号为0~n-1),每天可以有多个任务同时进行。某些任务之间有依赖关系,如图a所示,任务4依赖于任务1,任务1依赖于任务2。即任务2完成后才可以开始任务1,任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务,或多个任务依赖于同一个任务的情况。现已对该工程的依赖关系进行了梳理,结果如图b所示,标记“T”表示依赖关系需保留,标记“F”表示依赖关系需删除。
根据每个任务完成所需的天数和梳理后的依赖关系,编写程序,首先删除标记为“F”的依赖关系,然后计算工程最快完成所需的天数,并以工程最快完成所需的天数为期限,计算每个任务最晚必须开始的时间。
任务A 任务B 标记
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注:任务A依赖于任务B
图b
请回答下列问题:
(1)若某工程有6个任务,任务间依赖关系如图a所示,完成任务0~5所需天数分别为2,1,3,5,1,6,则工程最快完成需要　　　　天。
(2)定义如下erase(lst)函数,参数lst列表的每个元素表示一个依赖关系。函数的功能是删除标记为“F”的依赖关系,返回保留的依赖关系的个数。
def erase(lst):
　　i=0;j=len(lst)-1
　　while i<=j:
　　　　if lst[i][2]=='T':
　　　　　　i+=1
　　　　else:
　　　　　　if lst[j][2]=='T':
　　　　　　　 lst[i]=lst[j];i+=1
　　　　　　j -=1
　　return i
若lst列表依次存储图b所示的依赖关系,如lst[0]为[0,5,'T'],调用erase(lst)的数,则语句“lst[i]=lst[j]”的执行次数为　　　　。
(3)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
def proc(n,lst,task):
　　pr=[0]*n;w=[0]*n
　　m=erase(lst)
　　for i in ①　　　　　　:
　　　　task[lst[i][1]][1]=lst[i][0]
　　　　pr[lst[i][0]]=1
　　c=[];days=0
　　for i in range(n):
　　　　if pr[i]==0:
　　　　　　k=i;s=0
　　　　　　while k!=-1:
　　　　　　　　c.append(k)
　　　　　　　　s+=task[k][0]
　　　　　　　　②　　　　　
　　　　　　if s>days:
　　　　　　　　days=s
　　for i in range(n-1,-1,-1):
　　　　k=c[i]
　　　　if task[k][1]==-1:
　　　　　　w[k]=days-task[k][0]+1
　　　　else:
　　　　　　③　　　　　
　　#输出days,以及保存在w中的每个任务最晚必须开始的时间,代码略
#工程包含的任务数存入变量n。任务间的依赖关系存入1st列表,1st[0]包含3项,任务1st[i][0]依赖于任务1st[i][1],1st[i][2]存放保留/删除标记,任务数据存入task列表task[i]包含2项,task[i][0]为完成任务所需天数,task[i][1]的初值为-1,代码略。
proc(n,lst,task)
答案　(1)8　(2)1　(3)①range(m)或 range(0,m)或 range(0,m,1)或 range(m-1,-1,-1)或 range(erase(lst))或 range(0,erase(lst))或 range(0,erase(lst),1)或 range(erase(lst) -1,-1,-1)　
②k=task[k][1]　③w[k]=w[task[k][1]]-task[k][0]或 w[k]=w[c[i+1]]-task[k][0]
解析　本题考查数组的遍历、链表的遍历、创建等操作。(1)任务5和任务0有依赖关系,完成天数为8天,任务4、1、2有依赖关系,完成天数为5天,任务3需5天,存在3条链表,每天可以有多个任务同时进行,因此取最长链表所花时间,至少需要8天。(2)变量i和j分别指向数组lst的头尾元素位置,从头元素开始遍历,若遍历的元素lst[i][2]不是'T',将尾元素为'T'的元素覆盖当前元素,并将变量j向前移动。在题干图b中,当i值为1时,标记为F,由于尾元素也不是T,因此仅仅变量j向前移动,变量i并未增加,再次遍历时,将一条为T的元素覆盖,因此该语句只执行了一次。(3)①首先删除标记为“F”的依赖关系,从题干图中可以看出,任务a依赖于任务b,任务b完成后才可以开始任务a,任务b的后继是任务a,因此语句task[lst[i][1]][1]=lst[i][0]的作用是创建链表,并将不是头节点的元素用pr数组标记为1。变量m调用函数返回保留的依赖关系的个数,因此需对有依赖关系的记录进行标记。②遍历每一个任务,当条件pr[i]==0成立时,表示当前任务是某条链表的头节点,并开始遍历该条链表,将节点添加到列表c中,并统计该条链表所需天数s。当前节点完成遍历后,要到下一节点。③以工程最快完成所需的天数为期限,计算每个任务最晚必须开始时间,如题干图a中,工程最快完成所需的8天,任务5最迟在第1天完成,任务5完成在第6天,任务0则完成时间在第7、8两天,因此最迟在第7天开始。当条件task[k][1]==-1 成立时,表示任务k是任务链的尾节点,至少应该从倒数第task[k][0]天开始,或者顺数第days-task[k][0]+1开始;若任务 k不是尾节点,该任务必须在其后续任务完成前开始,开始时间为后续任务的最晚开始时间减去当前任务完成时间。
高中阶段的数据结构不是讨论如何使用数据结构,而是通过对数据集进行简单的操作,理解和创建数据结构。能将有限制条件的、真实情境中的数据关系进行抽象,根据数据特点与求解要求,选择适当的数据类型表示各种数据,并用合适的数据结构表达数据的逻辑关系。在已有数据集的基础上,通过链接关系构造逻辑上先后遍历顺序,构建链表,将有层次非线性结构或二维数组转换为一维数组,再遍历一维数组,得到问题的解。当原始数据量大,且每个数据元素有多个数据项时,直接对其进行复制会浪费大量空间和时间,可进行基于索引的引用,提高效率。
例题 某市举行体育赛事活动,n所学校的选手已完成预赛,现计划根据预赛的成绩挑选s名选手参加市决赛。成绩位列所在学校前w名次的选手直接入选,剩余名额按成绩由高到低依次挑选,成绩相同的选手一并入选,选中的选手数一旦达到或超过s名,挑选结束。
现给定所有选手预赛的成绩数据表,每位选手的数据包含学校编号(0~n-1)、选手编号、成绩,成绩数据表已按成绩由高到低排列。编写程序,计算各选手的校内名次,再按上述规则挑选决赛选手,按成绩数据表中的顺序输出选手编号,同时提供查询功能。选手校内名次的计算方法是:若选手所在学校有m人成绩高于该选手,则该选手的名次为m+1。
在如图所示的样例中,n、s、w分别为3、8、2,根据图中前3行数据计算出了每位选手的校内名次,进而选出实际入选的9名选手。
学校编号 0 2 2 0 0 2 2 0 1 1 1 1
选手编号 0002 2027 2002 0072 0182 2071 2128 0012 1081 1002 1008 1208
成绩 198 185 183 182 182 177 177 176 175 163 161 161
校内名次 1 1 2 2 2 3 3 4 1 2 3 3
是否入选 True True True True True True True False True True False False
请回答下列问题:
(1)对于如图所示前4行数据,若s、w分别为5和1,则0号学校入选人数是　　　　。
(2)定义如下search(data,sid,score)函数,data列表每个元素的前5个数据项依次为学校编号、选手编号、成绩、校内名次、是否入选,列表已按成绩由高到低排列。函数功能是查找选手编号为sid、成绩为score的元素,返回其下标,若未找到则返回-1。
def search(data,sid,score):
　　left,right=0,len(data)-1
　　f=-1
　　while left<=right:
　　　　mid=(left+right)//2
　　　　if score==data[mid][2]:
　　　　　　f=mid;left=mid+1
　　　　elif score　　　　　　left=mid+1
　　　　else:
　　　　　　right=mid-1
　　if f==-1:
　　　　return -1
　　for i in range(f,len(data)):
　　　　if data[i][2]!=score:
　　　　　　return -1
　　　　elif data[i][1]==sid:
　　　　　　return i
①调用search函数,若data列表长度为12,data[0][2],data[1][2],…,data[11][2]的值依次为:198,185,183,182,182,177,177,176,175,163,161,161,score值为177,则while语句中循环体的执行次数是　　　　。
②程序中加框处代码有错,请改正。
(3)实现根据选手成绩(成绩不超过200)计算校内名次,以及挑选决赛选手功能的Python程序如下,请在划线处填入合适的代码。
def proc(data,n,s,w):
　　#创建r列表,共n个元素,每个元素的值均为[0,0,201],代码略
　　heads=[-1,-1];tails=[-1,-1]
　　cnt=0
　　for i in range(len(data)):
　　　　①　　　　　
　　　　r[k][1]+=1
　　　　if data[i][2]　　　　　　r[k][2]=data[i][2]
　　　　　　②　　　　　
　　　　data[i][3]=r[k][0]
　　　　data[i].append(-1)　#为data[i]追加一个元素-1
　　　　v=1
　　　　if data[i][3]<=w:
　　　　　　data[i][4]=True
　　　　　　cnt+=1;v=0
　　　　if heads[v]==-1:
　　　　　　heads[v]=i
　　　　else:
　　　　　　data[tails[v]][5]=i
　　　　tails[v]=i
　　p,q=heads[0],heads[1]
　　res=[]　#res列表用于存放入选决赛的选手编号,顺序与data列表保持一致
　　while cnt　　　　tmp=data[q][2]
　　　　while q!=-1 and data[q][2]==tmp:
　　　　　　③　　　　　　:
　　　　　　　　res.append(data[p][1])
　　　　　　　　p=data[p][5]
　　　　　　res.append(data[q][1])
　　　　　　data[q][4]=True;cnt+=1
　　　　　　q=data[q][5]
　　while p!=-1:
　　　　res.append(data[p][1])
　　　　p=data[p][5]
　　return res
#读取n、s、w;读取选手成绩数据表存入data列表,每个元素包含学校编号、选手编号、成绩、校内名次(初值为0)、是否入选(初值为False)5个数据项,代码略
res=proc(data,n,s,w)
#输出res列表中的入选选手编号,代码略
#读取待查询的选手编号与成绩,调用search函数,根据返回值输出查询结果,代码略
思维点拨
明考向 本题考查二分查找、顺序查找、最值问题以及链表的相关知识
精点拨 (1)根据题意可得,当s,w分别为5,1时,每个学校先选取成绩最高的一名学生入选决赛,编号分别是”0002”、“2027”、“1081”,剩余的名额按照成绩由高到低分别是“2002”,0072”,“0182”,所以0号学校入选3人次。(2)自定义函数search功能是查找选手编号为sid、成绩为score元素的索引。①采用二分查找算法查找data中成绩为score的元素位置。查找的数据依次为177,175,176和177,查找次数为4次。f和right的值为6,即返回最后一个177元素的位置,left的值为7,当出现多个同分数据时,f返回的是最右边的元素位置。②若找到成绩为score元素,从索引为f的节点开始查找对应选手编号是否为sid。若找到,返回对应节点的索引,否则继续往前(左)查找,直到将同分段的所有元素查找完毕为止。加框处代码为从f开始往前查找选手编号sid,所以应修改为f,-1,-1。(3)①数组r中的每个子列表[0,0,201],分别是当前选手的校内排名、统计到当前选手为止该学校的总人数以及该学校目前的最低成绩,因此根据r[k][1]+=1,可判定k是需要确定当前选手所属的学校编号data[i][0]。②判定条件在更新当前选手所属学校的最低成绩,同时结合下一行的表达式data[i][3]=r[k][0],可以确定是在给当前选手排名,并且是在自己学校的校内排名。根据题干中的描述,所有数据已经按照降序排好,则排名时要根据该选手是当前学校的第几人以及同分情况,若所有选手分数都不同,则排名数据和人数数据一致,但若出现同分情况,则在发现分数不一致时,才需要将排名数据更新成人数数据,因此第②空答案为r[k][0]=r[k][1];根据后续代码的描述可以发现,head[0]是直接入选的链表表头,head[1]是剩余选手的表头,tail中存储的是相应链表的表尾,根据第(2)小题的程序结果res中应该存储进入决赛选手数据,并且顺序与data列表保持一致,因此在遍历过程中如果pq,则将剩余选手的数据加入res中
答案　(1)3　(2)①4　②f,-1,-1 或 right,-1,-1 或 left-1,-1,-1
(3)①k=data[i][0]　②r[k][0]=r[k][1]　③while p!=-1 and p变式 某市A区域有一套租车系统,设有m个公共自行车租车点(编号0~m-1),市政部门投放n辆自行车(编号1~n,n为m的倍数)并平均分配。用户可在租车点借车,之后将自行车归还到任意租车点。每天特定时间,工作人员根据系统指示,从存量超出平均数的租车点回收最新归还的若干辆自行车,再分配给存量低于平均数的租车,以保证各租车点自行车数量相等。
若m为3,n为12,初始自行车分配情况如图a所示。经过若干次租借与归还操作(记录如图b)之后,各租车点的自行车编号如图c所示。
租车点 车编号
A0 1,2,3,4
A1 5,6,7,8
A2 9,10,11,12
图a
车编号 租车点 还车点
1 A0 A2
8 A1 A2
6 A1 A0
图b
租车点 车编号
A0 6,2,3,4
A1 5,7
A2 8,1,9,10,11,12
图c
回收时,工作人员从A2租车点回收8号和1号自行车,并重新分配给A1租车点,完成后,A1租车点的自行车编号为8,1,5,7;A2租车点的自行车编号为9,10,11,12。
(1)若将图b中最后一条租借信息的自行车编号由6修改为5,则次日A0租车点的自行车编号为　　　　。
(2)定义如下rent(x,y,z)函数,参数x,y,z分别表示编号x的自行车从y租车点借出后归还至z租车点。函数功能是处理一条借还车记录。
def rent(x,y,z):
　　queinfo[y][1]-=1;queinfo[z][1]+=1
　　head=queinfo[y][0]
　　if x==bikelst[head][0]:
　　　　　　　　　　　　
　　else:
　　　　#处理编号x的自行车在y租车点其他位置的情况,代码略
加框处代码由下列3条语句组成,①bikelst[head][1]=queinfo[z][0];②queinfo[z][0]=head;③queinfo[y][0]=bikelst[head][1]。正确的排列顺序为　　　　。
(3)实现回收和重新分配自行车的部分Python程序如下,请在划线处填入合适代码。
def proc(bikelst,queinfo,m,num):
　　#从自行车存量超平均数的租车点回收自行车
　　head,tail=-1,-1
　　for i in range(m):
　　　　q=queinfo[i][0]
　　　　if queinfo[i][1]>num:
　　　　　　if head==-1:
　　　　　　　　head=queinfo[i][0]
　　　　　　else:
　　　　　　　　①　　　　　
　　　　　　while queinfo[i][1]> num:
　　　　　　　　p=q;q=bikelst[q][1]
　　　　　　　　②　　　　　
　　　　　　queinfo[i][0]=q;tail=p
　　#将回收的自行车重新分配到各租车点
　　q=head
　　for i in range(m):
　　　　③　　　　　
　　　　if cnt>0:
　　　　　　while cnt>0:
　　　　　　　　p=q;q=bikelst[q][1]
　　　　　　　　cnt-=1
　　　　　　bikelst[p][1]=queinfo[i][0]
　　　　　　queinfo[i][0]=head;head=q
　　　　　　queinfo[i][1]=num
#读取自行车和租车点数量,分别存入变量n和m,代码略
#读取租车信息,过滤租车点与还车点编号前的字母A后存入lst列表。#lst[i][0],lst[i][1],lst[i][2]分别表示第i条租车记录中自行车编号,租车点编号,还车点编号,代码略。
num=n//m　#每个租车点分配的自行车数量
bikelst=[[i,i]for i in range(1,n+1)]
bikelst[n-1][1]=-1
queinfo=[]　#列表queinfo存放各租车点相关信息
for i in range(0,n,num):
　　queinfo.append([i,num])
for i in range(len(lst)):
　　rent(lst[i][0],lst[i][1],lst[i][2])
proc(bikelst,queinfo,m,num)　#回收并重新分配自行车
答案　(1)5,2,3,4　(2)③①②
(3)①bikelst[tail][1]=queinfo[i][0]
②queinfo[i][1]-=1　③cnt=num-queinfo[i][1]
解析　本题考查多队列链表及算法的综合实现。(1)A0租车点的编号有2,3,4,再将自行车编号5还车到A0后,最新还车的编号应写在最前,A0租车点的编号为5,2,3,4。(2)从主程序可知,用数组bikelst构建了从编号1至编号n的链表,如[[1,1],[2,2],……,[n-1,-1]]。数组queinfo每个元素存储每个租车点第1辆车的在数组bikelst的索引(相当于每个租车点的头指针)和车辆数,如[[0,num] [num,num] ……,[(m-1)* num,num]]。head是y租车点的第1辆车索引,若还车的编号x正好是bikelst[head]节点的车辆编号,需要把索引为head的节点从租车点y删除,并插入到租车点z的头部。应先把该辆车从y租车点删除,即更新租车点y头指针,再将head节点指向z租车点原头节点,最后更新z租车点的头指针。(3)回收的自行车时,构建一条以head为头指针、tail为尾指针的链表,将多于平均值的出租点前面的节点采用尾插法接入到新链表中。重新分配自行车到各租车点时,将每个出租点所需数量cnt采用头插法插入到相应的出租点中,同时更新head的值。①若有2个或2个以上租车点多于平均车辆数,则尾节点tail需指向下一个回收租车点的头节点,才能使得多段回收车辆的链表链表起来。②遍历当前租车点i,若该租车点车辆数queinfo[i][1]大于num,需从该租车点的头指针开始遍历num个节点,每当遍历出租点i的一个节点,节点的数量queinfo[i][1]减少一个。③计算当前租车点i要增加的车辆数cnt的方法是:增加后的平均数num减去该租车点原来的车辆数queinfo[i][1]。
1.某音乐播放器中的“最近播放功能”是一种记录用户近期音乐播放历史的功能,该功能实现逻辑如下:(a)缓存容量限制n(n>0):最近播放列表中最多存储n首歌曲。(b)当播放列表中歌曲播放时:若已在缓存中,将其移动到最近播放列表最前端。若不在缓存中且缓存未满,直接加入最近播放列表最前端。若不在缓存中且缓存已满,删除最近播放列表末尾的歌曲,再将新歌曲加入最近播放列表最前端。
现给定用户的歌单列表data,每首歌曲的信息包含歌曲编号、歌曲名称、歌曲推荐值(0-100之间),data中歌曲按照歌曲推荐值降序排序,编写程序模拟播放data歌单列表过程中实时输出最近播放记录。当n=3,data 排序后数据如下表所示时,播放过程中的最近播放记录如下表最后一行显示。
歌曲编号 A1001 A1002 B2201 B2202 B2201 C1001 D1008
歌曲名称 《吻别》 《晴天》 《望》 《孤勇者》 《望》 《如愿》 《光亮》
歌曲推荐值 86 80 73 73 73 70 68
最近播放记录 《吻别》 《晴天》 《望》 《孤勇者》 《望》 《如愿》 《光亮》
《吻别》 《晴天》 《望》 《孤勇者》 《望》 《如愿》
《吻别》 《晴天》 《晴天》 《孤勇者》 《望》
(1)对于上表中data数据,若n更改为5时,data列表中歌曲播放完毕后,最近播放记录中最后一首歌曲名称为　　　　。
(2)定义如下函数bubble_sort(data),data列表中每个元素包含三项,分别是歌曲编号、歌曲名称、歌曲推荐值,该函数实现对data列表按照歌曲推荐值降序排序。
def bubble_sort (data):
　　n=len(data)
　　for i in range(n-1):
　　　　flag=False
　　　　for j in range (n -i -1):
　　　　　　if　　　　:
　　　　　　　　data[j],data[j+1]=data[j+1],data[j]
　　　　　　　　flag=True
　　　　if not flag:break
　　return data
①请在划线处填入正确的代码。
②加框处代码替换为下列哪个选项不影响函数功能　　　　(单选,填字母)。
A.n-2,i-1,-1 B.1,n-i
C.n-l,i,-1 D.i,n-i
(3)实现模拟音乐播放时显示最近播放记录的部分Python程序如下,请在划线处填入合适的代码。
#函数功能为在链表lst中查找歌曲编号为songid的位置,head为头节点,lst中每个节点有三个区域,分别为歌曲编号、歌曲名称和指向下个节点的指针
def find_song(lst,head,songid):
　　pre=p=head
　　while p!=-1:
　　　　if lst [p][0]==songid:
　　　　　　break
　　　　pre=p;p=lst[p][2]
　　return pre,p
#读取缓存容量限制n,用户的播放数据存入data列表data[0]包含3项,data[0][0]存放歌曲编号,data[0][1]存放歌曲名称,data[0][2]存放歌曲推荐值,代码略
lst=[];head=-1
length=0 　#存储播放记录中歌曲数量
data=bubble_sort(data)
for song in data:
　　pre,cur=find_song(lst,head,song[0])
　　if cur==-1:
　　　　lst.append([song[0],song[1],-1])　#列表lst中末尾追加一个新的节点
　　　　length+=1
　　　　if length<=n:
　　　　　　if length==1:head=0
　　　　else:
　　　　　　p=q=head
　　　　　　while lst[q][2]!=-1:
　　　　　　　　p=q;q=lst[q][2]
　　　　　　①　　　　　
　　　　if length>1:
　　　　　　lst[-1][2]=head;head=len(lst)-1
　　else:
　　　　if cur!=head:
　　　　　　lst[pre][2]=lst[cur][2]
　　　　　　②　　　　　
　　　　　　head=cur
#从lst中head节点开始输出每个节点的歌曲名称,代码略
答案　(1)《晴天》　(2)①data[j][2](3)①lst[p][2]=-1 或lst[p][2]=lst[q][2]或lst[p][2]=lst[lst[p][2]][2]　②lst[cur][2]=head
解析　(1)最近播放记录为《如愿》,《望》,《孤勇者》,《晴天》,《吻别》。播放《光亮》后,末尾的《吻别》被删除,所以最近播放记录中最后一首歌曲为《晴天》。(2)①按推荐值降序排序,data[i]元素中歌曲推荐值在索引值2。②若实现从后往前冒泡,第1次比较的索引是n-1和n-2,则j的初值为n-2。每次排序后,位置i有序,因此最后1次比较的索引是i和i+1,由于range是一个左闭右开的区间,因此其值为i-1。(3)①查找歌曲编号为songid的歌曲是否在链表中,若不在,则p为该歌曲对应的索引值位置。若cur的值为-1,则歌曲不在播放记录中,条件length>n成立,则播放记录已达上限,需删除末尾元素(即q)。②若cur值不为-1,则歌曲已经在播放记录中,只需将cur节点移动到链表头即可。
2.某省举行大型考试,现需对考试数据进行统计分析:输入特定分数区间的最低分和最高分(分数为0~750的整数),统计该区间人数并按成绩降序输出该区间考生信息。若输入区间最低分为-1,则结束统计。输出的考生信息包含三项数据:学校名称、准考证号和考试成绩。
考试数据与学校信息分别存储在不同的表中,如考试部分数据如图a所示,学校信息部分数据如图b所示。
学校代码 准考证号 考试成绩
0101 2310108005 695
0103 2310115001 694
0803 2310106003 707
0501 2310103006 699
0909 2310122002 698
…… …… ……
图a
学校代码 学校名称
0101 A中学
0103 B中学
0501 C中学
0803 D中学
0804 E中学
…… ……
图b
请回答下列问题:
(1)若该考试分数段680~698的考生人数为2185人,分数段690~698的考生人数为708人,则分数段680~689的考生人数为　　　　。
(2)定义如下search(school,key)函数,功能为在school中查找学校代码为key的学校名称。
def search(school,key):
　　i,j=0,len(school)-1
　　while i<=j:
　　　　m=(i+j)//2
　　　　if school[m][0]>key:
　　　　　　j=m-1
　　　　else:
　　　　　　i=m+1
　　return school[j][1]
调用该函数,若school为[['0101','A中学'],['0103','B中学'],['0501','C中学'],['0803','D中学'],['0804','E中学'],['0909','F中学']],请回答①和②两个问题:
①若查找key的值为“0909”,则需要查找的次数为　　　　。
②若将“return school[j][1]”改为“return school[m][1]”,会导致某些情况下无法得到符合函数功能的结果。下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.key='0101' B.key='0103'
C.key='0803' D.key='0909'
(3)实现上述功能的Python程序如下,请在划线处填入合适代码。
#读取n名考生的考试数据存到列表data中,data中每个元素包含3个数据项,分别对应每位考生的学校代码、准考证号和考试成绩;
#读取参加本次考试的学校信息存储到列表school中,school中每个元素包含2个数据项,分别为学校代码和学校名称,并按学校代码升序排序;代码略
m=750;head=[-1]*(m+1)
for i in range(n):
　　data[i].append(-1)
sum=[0]*(m+1)　#sum[i]存储大于等于分数i的人数
for i in range(n):
　　k=data[i][2]
　　sum[k]+=1
　　①　　　　　
　　head[k]=i
for k in range(m-1,-1,-1):
　　sum[k]+=sum[k+1]
while True:
　　low=int(input("请输入区间最低分:"))
　　high=int(input("请输入区间最高分:"))
　　if low==-1: break
　　i=high
　　while i>=low:
　　　　②　　　　　
　　　　while p!=-1:
　　　　　　s=search(school,data[p][0])
　　　　　　print("学校",s,"学号",data[p][1],"成绩",data[p][2])
　　　　　　p=data[p][3]
　　　　i-=1
③　　　　　
print(low,"~",high,"区间的总人数为:",total)
答案　(1)1477　(2)①3　②A
(3)①data[i][3]=head[k]　②p=head[i]
③total=sum[low]-sum[high+1]
解析　(1)人数为2185-708=1477。(2)①查找'0909',要查找的次数为3次。②查找BDF中学时,m值和最后的j值一致,因此只有当其查找A中学时,m值不一致。(3)①每个分数建立一个链表,分数i的所有人组成一个链表,头指针放在head[i]中。①统计了k分的总人数,存放在sum[k]中,采用头插法将新节点data[i]插入到总分是k的链表的头节点前,新节点指针data[i][3]指向原来的头指针。②循环输出分数在high到low之间的人,从头指针head[i]开始逐个输出,当前指针p指向分数i的头指针。③求分数大于等于low,小于等于high的总人数,应将大于等于low的总人数减去大于等于high+1的总人数。
3.“抢单”是外卖骑手的日常,当外卖平台上一个新的订单出现时,骑手需要在短时间内考虑是否抢单。平台根据骑手的实际信息,给出是否抢单的建议,若建议抢单则给出到达各个取送点的顺序。平台判断是否抢单的算法设计如下:
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,　　　　(选填:影响/不影响)程序执行。
def totd(riderlist,h):
　　speed=0.3　#speed为骑手每分钟公里数
　　total=0;pre=h
　　cur=riderlist[pre][4]
　　while cur!=-1:
　　　　#计算pre与cur两个节点所在位置间的路程,存储在变量d中
　　　　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];p=head=0
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。
1.某快递驿站有A、B两类货架,收到的包裹重量小于等于10存放于A货架,其余存放于B货架。编写程序模拟生成取件码和顾客的取件过程,取件码是根据当前已处理的包裹数量生成,如A-0001表示当天第一个处理的包裹存放在A货架,B-0003表示当天第三个处理的包裹存放在B货架。取件码与顾客手机号关联,程序根据输入的手机号显示其所有包裹的取件码,并允许顾客一次性提取或者部分提取。程序的部分运行界面如图a和图b所示。
(1)当前已处理的包裹取件码是A-0158,若下一个包裹重量是12,其取件码为　　　　。
(2)定义函数save(pnum,code),参数pnum为手机号,code为取件码。函数功能是将一条包裹信息存储到列表goods和列表dic中。如图a的包裹数据,手机号“180****1215”在两个列表中的数据分别为goods[4]=["B-0005",-1]、goods[9]=["A-0010",4]和dic[2]=["180****1215",9,2]。
①若调用该函数继续存储手机号“180****1215”的包裹,其取件码是“B-0011”,则对应dic[2]的值变为["180****1215",　　　　,　　　　]。
②函数save代码如下,程序中加框处代码有错,请改正。
def save(pnum,code):
　　goods.append([code,-1])
　　n=len(goods)-1
　　print(n,"号包裹的手机号:",pnum,"取件码:",code)
　　num=search(dic,pnum)　#函数返回手机号pnum 在dic中的索引号,未找到返回-1
　　if num==-1:
　　　　dic.append([pnum,n,1])　#新增一个包裹信息
　　else:
　　　　goods[n][1]=dic[num][1]
　　　　dic[num][1]=n
　　　　dic[num][2]+=1
(3)实现取件功能的部分Python程序如下,请在划线处填入合适的代码。
x=input("请输入您的手机号:")
num=search(dic,x)
if num!=-1:
　　#输出手机号为x的当前所有包裹信息,代码略
　　op=int(input("输入0取全部包裹,输入1取部分包裹:"))
　　if op==0:
　　　　print("您的包裹已经取完!")
　　　　del dic[num] #删除dic中索引为num的元素
　　else:
　　　　order=input("请输入本次的取件码,只输入#表示结束取件:")
　　　　while order!="#":
　　　　　　①　　　　　
　　　　　　p,q=head,head
　　　　　　while goods[q][0]!=order:
　　　　　　　　p=q
　　　　　　　　②　　　　　
　　　　　　if p==head:
　　　　　　　　dic[num][1]=goods[q][1]
　　　　　　else:
　　　　　　　　goods[p][1]=goods[q][1]
　　　　　　dic[num][2]-=1
　　　　　　if dic[num][2]==0:
　　　　　　　　print("您的包裹已经取完!")
　　　　　　　　break
　　　　　　#输出手机号为x的当前所有包裹信息,代码略
　　　　　　order=input("请输入本次的取件码,只输入#表示结束取件:")
else:
　　print("查无此号,请检查后重新输入!")
答案　(1)B-0159　(2)①10、3　②dic[num][2]+=1 或 dic[num][2]=dic[num][2]+1
(3)①head=dic[num][1]　②q=goods[q][1]
解析　(1)包裹重量是12,放在B货架,当前是0158,下一件是0159。(2)①dic[2]存储了手机号码为"180****1215"包裹的头指针(在goods中的索引)和包裹总数量,增加一件后,将该包裹以头插的形式链接入goods链表,数量各增加1,dic[2]原值为["180****1215",9,2]。②该手机号码包裹总数量增加一件。(3)①该手机号在dic中索引为num,将该手机号的头指针dic[num][1]赋值给head。②指针q从头指针开始遍历,将跳转到下一个节点。
2.某校进行体育之星评比,现有引体向上、俯卧撑、仰卧起坐、跳绳四个项目。学生自愿参加其中一项评比,成绩前num名(包含num,同名次均可)同学为该项目的体育之星。保证每个项目都有超过num人参加。编写程序完成上述功能并输出结果。
(1)定义如下函数insert(a,i,k),函数的功能是实现数据的有序插入。
def insert(a,i,k):
　　if queinfo[k][1]==-1:
　　　　queinfo[k][1]=i
　　elif a[i][3]>=a[queinfo[k][0]][3]:
　　　　a[i][4]=queinfo[k][0]
　　　　queinfo[k][0]=i
　　elif 　　　　　　:
　　　　a[queinfo[k][1]][4]=i
　　　　queinfo[k][1]=i
　　else:
　　　　q=queinfo[k][0];p=a[q][4]
　　　　while p!=-1 and a[p][3]>a[i][3]:
　　　　　　q=p;p=a[p][4]
　　　　a[i][4]=p;a[q][4]=i
①若函数中加框语句改成“p!=-1 and a[p][3]②在划线处填写合适的代码。
(2)实现上述功能的Python程序如下,请在程序中划线处填入合适的代码。
#读取数据存入列表data中,代码略
#列表data[i]包含五个元素,data[i][0]、data[i][1]、data[i][2]、data[i][3]、data[i][4]分别表示班级、姓名、项目名称、成绩、指针域。如["101班","王**","引体向上",2,-1]
queinfo=[[-1,-1] for i in range(4)]
programe={"引体向上":0,"俯卧撑":1,"仰卧起坐":2,"跳绳":3}
num=50;rs=[0]*4
for i in range(len(data)):
　　①　　　　　
　　if queinfo[k][0]==-1:
　　　　queinfo[k][0]=i
　　if rs[k]>=num and data[queinfo[k][1]][3]>data[i][3]:
　　　　continue
　　insert(data,i,k);rs[k]+=1
for i in programe:
　　print('\n',i,"项目体育之星如下:")
　　count=1
　　q=②　　　　　
　　p=data[q][4]
　　print(data[q][0],data[q][1],end='、')
　　while count　　　　count+=1
　　　　print(data[p][0],data[p][1],end='、')
　　　　q=p;p=data[p][4]
(3)data数据为[["101班","周**","跳绳",100,-1],["103班","叶*","跳绳",50,-1],["107班","幸**","跳绳",105,-1],["111班","陈**","跳绳",100,-1],["113班","郑*","跳绳",171,-1]],若num值为3,则需要输出跳绳项目的体育之星insert(a,i,k)函数调用　　　　次。
答案　(1)①会　②a[i][3]<=a[queinfo[k][1]][3]或a[i][3](2)①k=programe[data[i][2]]
②queinfo[programe[i]][0]
(3)5
解析　(1)①insert函数的功能时将列表data中的数据根据项目名称进行分组,同一组的项目按照成绩从高到低降序排列。②当前节点的对应的项目成绩大于对应链表的头节点成绩,则当前节点作为链表的头节点。当前节点的对应的项目成绩小于对应链表的尾节点成绩,则当前节点作为链表的尾节点。(2)①遍历链表data,其中data[i][2]表示体育项目,表达式programe[data[i][2]] 从字典取出表示当前数据节点的项目编号并赋值给变量k。②获取当前项目链表的头指针。(3)如果当前编号为k项目链表中对应的节点数达到了num个且当前节点对应的成绩小于链表尾节点的成绩,则不用插入。由于后面数据的值大于尾节点50,因此insert(a,i,k)函数调用5次。
3.某学校举办社团节,在一条直路的同侧依次有n个社团展位,按展位到入口距离从1至n依次编号。从入口处走到第1个展位需要花费dis[0]单位时间,从第i个展位走到第i+1个展位需要花费dis[i]单位时间。每个展位举行若干活动,每参加一个活动需要5单位时间。对于第i个展位,第一次参加活动获得a[i-1]个积分,第二次参加活动获得a[i-1]-b[i-1]个积分,第三次参加活动获得a[i-1]-2*b[i-1]个积分……以此类推。现在小明从入口处出发,他共有m单位时间自主选择参与社团的活动并回到入口处。编写程序实现规定时间内获得最多积分的活动方案及获得的积分数。
例:
展位 1 2 3
首次活动积分 10 15 20
每次下降的积分 4 6 4
与前一展位之间步行所花时间 1 3 4
若小明可用时间为28,部分方案如下:
方案1:参加前1个展位活动,有5次活动机会,可得积分为10+6+2=18
方案2:参加前2个展位活动,有4次活动机会,可得积分为15+10+9+6=40
方案3:参加前3个展位活动,有2次活动机会,可得积分为20+16=36
则可获得的最多积分为40,运行界面如图所示。
展位数:3 可用时间:28 各展位首次参加活动可获得的积分:10 15 20 各展位每次下降的积分:4 6 4 相邻展位之间步行花费时间:1 3 4 能获得的最多积分是:40 各展位参加的活动次数分别为:[2,2,0]
(1)若小明可用时间为32,按上表数据可得最多积分为　　　　。
(2)定义如下insert(head,r)函数,功能是在首节点下标为head的链表中插入下标为r的节点,返回新的链首节点下标。data[i]存储下标为i的节点数据,data[i][0]存储目前参加活动能获得的积分,data[i][1]存储参加活动后要下降的积分,data[i][2]存储后继节点下标。
def insert(head,r):
　　p=q=head
　　while q!=-1 and data[r][0]　　　　p=q;q=data[q][2]
　　if q==head:
　　　　data[r][2]=head;head=r
　　else:
　　　　data[p][2]=r;data[r][2]=q
　　return head
若函数加框处代码误写为"data[r][0]A.data=[[6,6,-1],[10,3,3],[2,11,-1],[7,5,2]];head=1;r=0
B.data=[[6,6,-1],[10,3,3],[2,11,-1],[7,5,0]];head=1;r=2
C.data=[[6,6,2],[10,3,0],[2,11,-1],[7,5,-1]];head=1;r=3
D.data=[[6,6,2],[10,3,-1],[2,11,-1],[7,5,0]];head=3;r=1
(3)实现上述功能的Python程序如下,请在划线处填入合适的代码。
#展位数存入变量n,可用时间存入变量m,各展位首次参加活动可获得的积分存入a列表,各展位每参加一次活动要下降的积分存入b列表,相邻展位之间步行花费时间存入dis列表,dis[0]为入口到第1个展位步行花费时间,dis[i](i>0)为第i个展位到第i+1个展位步行花费时间,代码略
for i in range(1,n):
　　dis[i]=①　　　　　
data=[]
for i in range(n):
　　data.append([a[i],b[i],-1])
ans=0　#记录能够获得的最多积分
best=[]　#记录一种能够获得最多积分的活动方案
for i in range(n):
　　head=-1
　　for j in range(i+1):
　　　　data[j][0]=a[j]
　　　　head=insert(head,j)
　　t=(m-2*dis[i])//5
　　if t<=0: break
　　total=0;count=[0]*n　#记录临时方案
　　while ②　　　　　　:
　　　　p=head;head=data[head][2]
　　　　total+=data[p][0]
　　　　count[p]+=1
　　　　data[p][0]=③　　　　　
　　　　if data[p][0]>0:
　　　　　　head=insert(head,p)
　　　　t-=1
　　if total>ans:
　　　　#更新ans和best代码略
#输出代码略
答案　(1)51　(2)B　(3)①dis[i]+dis[i-1]
②t>0 and head!=-1
③data[p][0]-data[p][1] 或者data[p][0]-b[p]
解析　(1)第3个展台距离入口所花时间为1+3+4=8,往返需16,还可以有32-16=16的时间用于活动,即可以完成3个活动,积分最大的20+16+15=51。(2)insert函数功能是在首节点下标为head的链表中插入下标为r的节点,返回新的链首节点下标。当节点r数据区域值小于尾节点,条件data[r][0]4.有2组器件共n个,要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先级。优先级有m(1编写程序模拟检测过程,先合并2组器件的数据,然后计算所有器件的平均等待时长,其中每个器件等待时长为其开始检测的时间与送达时间的时间差。(时间单位均为秒)
请回答下列问题:
(1)由题意可知,图中器件A、B、C、D的检测顺序为A-C-D-B,A、C、D的等待时长分别为0、1、0,B的等待时长是　　　　。
(2)定义如下merge(lst1,lst2)函数,参数lst1和lst2的每个元素由送达时间、检测时长和优先级3项构成,lst1和lst2均已按送达时间升序排列。函数功能是将lst2中的元素合并到lst1中,并将lst1按送达时间升序排列,函数返回lst1。
def merge(lst1,lst2):
　　i=len(lst1)-1;j=len(lst2)-1
　　for t in range(len(lst2)):
　　　　lst1.append([0,0,0])　#为lst1追加一个元素[0,0,0]
　　k=len(lst1)-1
　　while j>=0:
　　　　if i>=0 and lst1[i][0]>lst2[j][0]:
　　　　　　lst1[k]=lst1[i];i-=1
　　　　else:
　　　　　　lst1[k]=lst2[j];j-=1
　　　　k-=1
　　return lst1
①调用merge(lst1,lst2)函数,若lst1为[[0,3,2],[1,1,2],[12,2,2]],lst2为[[2,1,1],[4,3,0],[11,3,2]],则while语句中循环体的执行次数是　　　　。
②若函数中while 语句的条件“j>=0”误写为“k>=0”,会导致某些情况下无法得到符合函数功能的结果。调用merge(lst1,lst2)函数,下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.lst1=[[0,3,2],[4,3,0]]
lst2=[[1,1,2]]
B.lst1=[[1,1,2]]
lst2=[[0,3,2],[4,3,0]]
C.lst1=[[1,1,2],[4,3,0]]
lst2=[[0,3,2]]
D.lst1=[[4,3,0]]
lst2=[[0,3,2],[1,1,2]]
(3)实现模拟检测过程并计算平均等待时长的部分Python程序如下,请在划线处填入合适的代码。
def proc(data,m):
　　n=len(data)
　　queinfo=[[-1,-1] for i in range(m)]
　　for i in range(n):
　　　　data[i].append(-1)　#data[i]追加一个元素-1
　　curtime=0;waitnum=0;i=0
　　①　　　　　
　　while i0:
　　　　if i　　　　　　k=data[i][2]
　　　　　　if queinfo[k][0]==-1:
　　　　　　　　queinfo[k][0]=i
　　　　　　else:
　　　　　　　　②　　　　　
　　　　　　　　data[p][3]=i
　　　　　　queinfo[k][1]=i
　　　　　　waitnum+=1;i+=1
　　　　elif waitnum>0:
　　　　　　k=0
　　　　　　while queinfo[k][0]==-1:
　　　　　　　　k+=1
　　　　　　p=queinfo[k][0]
　　　　　　total+=curtime-data[p][0]
　　　　　　curtime+=data[p][1]
　　　　　　③　　　　　
　　　　　　waitnum-=1
　　　　else:
　　　　　　curtime=data[i][0]
　　return total/n
#读取2组器件的数据,分别存入列表data1和data2中。2个列表的每个元素包含3个数据项,分别对应器件的送达时间、检测时长和优先级。data1和data2中的数据已分别按送达时间升序排列,代码略
#读取优先级等级个数存入m,代码略
data=merge(data1,data2)
print(proc(data,m))
答案　(1)6　(2)①4　②A　(3)①total=0
②p=queinfo[k][1]　③queinfo[k][0]=data[p][3]
解析　本题考查队列的链接式存储算法实现。(1)A在处理时,B和C在等待,A在时刻3处结束,B和C等待了2秒和1秒,C的优先级比B的优先级高,C先处理,从时刻2到达,在时刻4结束。D在时刻4到达,优先级比B高,D先处理,在时刻7结束,因此B在7时刻开始处理,每个器件等待时长为其开始检测的时间与送达时间的时间差,因此B的等待时长为7-1=6。(2)①先在lst1后添加len(lst2)个数据元素,从两个列表的后面开始,将lst2归并到lst1中。依次归并[12,2,2]、[11,3,2]、[4,3,0]、[2,1,1],j的值小于0,结束归并,共循环4次。②若函数中while 语句的条件“j>=0”误写为“k>=0”,j是指向lst2的指针,则当lst2中的数据已经处理完时,会出问题,因此答案选A。(3)①总时间的变量total,通过total+=curtime-data[p][0]累计total值,设置初始值为0。解决问题的方式采用链表实现的队列,即链式队列,二维列表queinfo就用来存储每个优先级的头尾指针。data追加一个元素-1用来存储下一个处理的指针,存储链表信息。②若该等级已存在其他器件,由于器件是按时间升序遍历。因此将该器件添加到k等级链表表尾。通过访问k等级虚点对应的链表表尾,找到表尾位置p(p=queinfo[k][1]),然后在链表表尾追加当前器件的索引位置i,完成待处理器件的入队操作。③在k等级链表中,找到最高k等级单链表指向的位置p,p为单链表中队首器件位置。此处是将p指向的器件删除,通过更新k等级链表表头queinfo[k][0],使链表表头指向p的下一个器件位置,完成删除操作。
5.在科学研究中往往会使用超级计算机来进行数据处理。某超级计算机需要根据第二天的预约计划安排计算任务,预约计划包含项目名称、数据上传时刻和计算所需时长,数据上传之后才能开始计算。为保证计算的正确率,每个任务开始之后不能中断,计算完成之后才能开始下一个任务。该计算机每天开机time时刻后,需关机进行维护。现根据预约计划安排计算任务。
安排任务的规则为:舍弃time时刻内无法完成计算的任务后,若没有等待中的任务,上传时刻最早的任务安排计算;若有等待中的任务,等待任务中所需时间最短的任务安排计算。
设time=100,预约计划如图所示。任务B、E无法在time时刻内完成被舍弃,F最早完成数据上传开始计算,计算中任务A、C、D完成数据上传等待计算。F计算完成后,A开始计算。最后的任务安排为FACD。请回答下列问题:
项目 上传时刻 时长
A 30 10
B 70 65
C 25 25
D 30 35
E 40 70
F 0 30
(1)若将图中项目E的所需时长改为5后重新安排计算任务,则任务安排为　　　　。
(2)定义如下retain(a)函数,参数a的每个元素由项目名称、数据上传时刻和所需时长构成。函数的功能是根据数据上传时刻对a进行升序排序,同时返回能够在time时刻内完成的任务数。
def retain(a,time):
　　n=len(a);k=n
　　i=0;jc=0;flag=False
　　while not flag:
　　　　flag=True;c=0;jc+=1
　　　　for j in range(1,k):
　　　　　　if a[j-1][1]+a[j-1][2]>time or a[j-1][1]>a[j][1]:
　　　　　　　　a[j],a[j-1]=a[j-1],a[j]
　　　　　　　　flag=False
　　　　　　　　c=j
　　　　k=c
　　i,j=0,n-1
　　while i<=j:
　　　　mid=(i+j)//2
　　　　if a[mid][1]+a[mid][2]>time:
　　　　　　j=mid-1
　　　　else:
　　　　　　i=mid+1
　　return　　　
①调用retain(a)函数,若time为100,a为[["A",0,30],["B",10,65],["C",15,25],["D",30,80],["E",40,5],["F",30,10]],则变量jc的值为　　　　。
②划线处应填入的代码为　　　　(单选,填字母:A.i/B.j/C.mid)。
(3)实现任务安排的Python程序如下,请在划线处填入合适的代码。
def proc(a,m):
　　now=i=0
　　task=[];h=-1
　　while i　　　　if i=now and h==-1:
　　　　　　①　　　　　
　　　　　　if now<=time:
　　　　　　　　task.append(a[i][0])
　　　　　　i+=1
　　　　elif i　　　　　　if h==-1:
　　　　　　　　h=i
　　　　　　else:
　　　　　　　　if a[i][2]　　　　　　　　　　a[i][3]=h
　　　　　　　　　　h=i
　　　　　　　　else:
　　　　　　　　　　q=p=h
　　　　　　　　　　while p!=-1 and a[i][2]>=a[p][2]:
　　　　　　　　　　　　q=p
　　　　　　　　　　　　p=a[p][3]
　　　　　　　　　　a[q][3]=i
　　　　　　　　　　③　　　　　
　　　　　　i+=1
　　　　else:
　　　　　　now+=a[h][2]
　　　　　　if now<=time:
　　　　　　　　task.append(a[h][0])
　　　　　　h=a[h][3]
　　　　if now>time:
　　　　　　break
　　return task
#读取time;读取预约计划存入a列表,每个元素包含项目名称、数据上传时刻和计算所需时长,代码略
m=retain(a,time)
for i in range(m):
　　a[i].append(-1)
ans=proc(a,m)
print(ans)
答案　(1)FAEC　(2)①3　②A
(3)①now=a[i][1]+a[i][2]　②a[i][1]<=now　③a[i][3]=p
解析　(1)F和A完成后,当前时间为40,等待中的任务有C、D和E,其中E所需时间最短,因此接下来将C,此时当前时间为70,D将超时。(2)①程序实现从前往后冒泡的排序,a[j-1][1]+a[j-1][2] >time表示超时的任务,即按上传时间升序排列,并将超时的任务往后移动。flag表示本趟有无交换的标志,k表示最后一个无序的边界。任务D超时,第1趟将D排到最后,第2趟交换E和F,第3趟数据无交换,结束。②返回能够在time时刻内完成的任务数,结束二分查找后,i指向两个时间之和大于time的位置,j指向两个时间之和小于等于time的位置,因此总的任务数索引为0至j,即共有i个任务。(3)①用变量i去遍历所有可能不超时的任务,h表示等待任务的头指针,now表示当前时间,若上传时刻小于等于当前时间且没有等待任务,更新该任务完成后的当前时间now为a[i][1]+a[i][2],若该任务不超时,将该任务添加到task列表中。②若上传时刻a[i][1]小于等于当前时间now,但有等待任务,将该任务添加到等待任务列表中,且按所需时长进行升序排列。③节点p从头节点h开始遍历链表,将节点i插入到节点p的前面,节点q的后面,需修改节点q指向节点i,节点i指向节点p。

展开更多......

收起↑