链表+算法综合三
班级 姓名
1.【202303温州二模】某物流公司将物流优先级分成一级到四级，派件费分别为300、200、100、80元/件。
每天有n件物品分批进仓，每件包含单号、派送批次、派件费。为实现物流派件优先规则，送货员在仓库中选择派件优先级最高的一件派送，接下来选择剩余部分和新进批次中派件优先级最高的一件派送，每派送一件，新的一批到达仓库。根据要求编写程序计算送货员某天前m件物品的派件费总额。请回答下列问题：
(1)由题意可知，观察下图。前4件物品的派件费总额是900元，则前3件物品的派件费总额是_______ 元。
(2)定义如下sort(lst)函数，参数lst的每个元素由单号、派送批次、派件费三项构成。函数功能是将lst 中的元素按送派件批次升序排列，函数返回lst。
def sort(lst):
n=len(lst) ; i=0
while ifor j in range(n-2, i-1, -1):
if lst[j][1]>lst[j+1][1]: lst[j], lst[j+1]=lst[j+1], lst[j]
___________
return lst
上述程序段，划线处语句正确的是_________（多选，填字母）
A.i=i+1 B.i=j C.i=j-1 D.i=j+1
(3)上述计算派件费总额的部分 Python 程序如下，请在划线处填入合适的代码。
def imitate(lst, m):
n=len(lst)
for i in range(n):
lst[i].append(-1)
val=0 ; j=0 ; q={300:[-1,-1], 200:[-1,-1], 100:[-1,-1], 80:[-1,-1]}
for i in range(m):
while jk=lst[j][2]
if q[k][0]==-1:
q[k][0]=j
else:
lst[q[k][1]][3]=j
②______ __
j+=1
for v in [300,200,100,80]:
k=q[v][0]
if k!=-1:
③______ __
q[v][0]=lst[k][3] ; break
return val
'''读取快递数据，存入列表 task 中。列表的每个元素包含 3 个数据项,分别快递单的单号、派送批次、派件费。读取派送件数，存入m，代码略'''
task=sort(task) ; val=imitate(task, m)
print(val)
2.【202212学军模拟】某工厂有一批货物需要加工，现已知每批货物到达工厂的时间和需要加工的时间，为了提高加工的效率，工厂管理员想到两个加工的方法。
①先到先加工：按货物到达的时间顺序依次加工，若第i件货物正在加工，第i+1件货物已经到达工厂，则需等待第i件货物加工完成后，才能开始第i+1件货物的加工；
②优先加工“加工时间”最短的货物：在已经到达工厂的货物中，找出“加工时间”最短的货物进行加工，其他货物等其加工完成再加工；已到达工厂的剩余货物按同样的方法加工。
工厂管理员想知道按这两种不同的方法对货物进行加工，需要等待的时间分别为多少，以便更好选择方案。
◆某件货物的等待时间=该货物开始加工的时间-该货物到达工厂的时间
◆总等待时间=所有货物的等待时间之和
如某批货物加工时间如下表所示。
(1)若上表中货物4需加工的时间改为4，则使用方案①进行加工，加工整批货物的总等待时间为 。
(2)按方案进行加工的算法如下，请在划线处填入合适的代码。
def FCFS(P,n):
wait_time=0 ; finish=P[0][1]
for i in range(1,len(P)):
if P[i][1]wait_time+=finish-P[i][1]
return wait_time
(3)按方案②进行加工的算法如下，请在划线处填入合适的代码。其中，为了能快速的找出已到达工厂的所有货物中加工时间最短的货物，本算法使用Python的优先队列类PriorityQueue,该队列类常用的方法 如下：
def SJF(P,n):
wait_time=cur_time=0
q=PriorityQueue() ; i=0
while iif q.empty():
q.put(P[i]) ; i+=1
elif iq.put(P[i]) ; i+=1
else:
min_p=q.get()
②
cur_time+=min_p[0]
return wait_time
(4)主程序如下：
if __name__=="__main__":
#按货物的到达时间，依次读取n个货物的信息，存入数组P中
#其中P[i][0]、P[i][1]分别存储第i个货物的加工时间和到达时间
#例如，读取上表5个货物的数据：P=[[10,0],[1,1],[5,2],[1,3],[2,4]],代码略
time1=FCFS(P,n)
time2=SJF(P,n)
print("方案①总等待时间：",time1)
print("方案②总等待时间：",time2)
3.【202301选考真题】有2组器件共n个，要用一台检测设备检测。每个送检器件信息包含送达时间、检测时长和优先级。优先级有m（l编写程序模拟检测过程，先合并2组器件的数据，然后计算所有器件的平均等待时长，其中每个器件等待时长为其开始检测的时间与送达时间的时间差。（时间单位均为秒）
请回答下列问题：
(1) 由题意可知，图中器件A、B、C、D的检测顺序为A-C-D-B，A、C、D的等待时长分别为0、l、0，B的等待时长是__________。
(2)定义如下merge(1stl,lst2)函数，参数lstl和lst2的每个元素由送达时间、检测时长和优先级3项构成，1stl和lst2均已按送达时间升序排列。函数功能是将lst2中的元素合并到1stl中，并将1stl按送达时间升序排列，函数返回lstl。
def merge(lst1,lst2):
i=len(lst1)-1
j=len(lst2)-1
for t in range(len(lst2)):
lst1.append([0,0,0]) #为1stl追加一个元素[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-=l
k-=1
return lst1
①调用merge(1stl,lst2)函数，若lstl为[[0,3,2],[1,1,2],[12,2,2]],1st2为[[2,l,1],[4,3,0],[1l,3,2]]，则while语句中循环体的执行次数是___________。
②若函数中while语句的条件“j>=0”误写为“k>=0”，会导致某些情况下无法得到符合函数功能的结果。调用merge(lstl,lst2)函数，下列4组数据中能测试出这一问题的是_________(单选，填字母)。
A.lstl=[[0,3,2],[4,3,0]] B.lstl=[[1,1,2]]
lst2=[[1,1,2]] lst2=[[0,3,2],[4,3,0]]
C.lst1=[[l,1,2],[4,3,0]] D.lstl=[[4,3,0]]
lst2=[[0,3,2]] lst2=[[0,3,2],[l,1,2]]
(3)实现模拟检测过程并计算平均等待时长的部分Python程序如下，请在划线处填入合适的代码。
def proc(data,m):
n=len(data)
queinfo=[]
for i in range(m):
queinfo.append([-1,-1]) #queinfo追加一个元素[-1,-1]
for i in range（n）：
data[i].append(-1) #data]追加一个元素-1
curtime=0
waitnum=0
i=0
①_______ __
while i0：
if ik=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.【202303温州二模】
(1)600
(2)AD
(3)①lst[j][1]==i+1
②q[k][1]=j
③val+=v 或 val+=lst[k][2]
2.【202212学军模拟】
(1)47
(2)finish+=P[i-1][0]
(3)①P[i][1]<=cur_time
②wait_time+=cur_time-min_p[1]
3.【202301选考真题】
(1)6 或 6秒
(2)①4
②A
(3)①total=0
②p=queinfo[k][1]
③queinfo[k][0]=data[p][3]
