资源简介

9.3　以数组形式组织数据
学习目标　
1.掌握采用桶等数据结构来记录相应的数据,优化数据访问的时间的方法。
2.要数据遍历过程中,掌握采用队列等数据记录临时处理的数据,以达到优化算法的效果。
(2024年1月浙江选考)某项活动有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]<1st[j][1]: tmp=1st[j]
　　　　1st[j]=1st[j-1]
　　　　1st[j-1]=tmp
if 1st[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)
解析　(1)1号剩余5人,5号和2号剩余人数单独分组后,再次剩余人数为2和3,因此圴不能加入到这些新分组中。3号剩余人数编码为第8组,1号的剩余人数可以加入到该组。(2)①程序实现从后往前冒泡降序排序,因此第1次执行后,最左边的数据最大。②第4趟排序后,lst[i][1]的值为0,执行break语句,结束排序。(3)①每m人分配到一个新建小组中,不足m人的剩余员工暂不分配。新建一个分组后,该组内的人数将减少m个。②新一个大小为m列表b表示各个分组的剩余人数,b[0]至b[m-1]的初值均为0。对每个单位的剩余员工人数降序排序,并遍历n个单位,首先查找是否存在一个大于等于该单位剩余人数最小分组,其方法是用循环while j　　针对情境较为复杂、结构化程度较低的问题,能抽象数据特征、创造性地运用数据结构优化算法。数据往往经过采集、传输、处理和存储的过程,而数据在加工处理过程中,要考虑算法的优越性,提高算法的效率。数据在加工过程中,临时存放的数据可以存储在队列、栈和二维数组中,利用其不用查找就可以操作或者把当前正在处理的数据放置一个较小的数组中的特性,加快数据的处理时间。
例题 某区域有m个设备(编号为1到m)需要联网。单台无线路由器的Wi-Fi信号可以覆盖一个圆形范围。现有n个可供安装路由器的位置(编号为0到n-1)。编写程序,找到最少数量的路由器安装位置,确保所有设备都能被覆盖。查找算法如下:
步骤1:选择一个覆盖设备最多的位置安装路由器。在设备数量相同的情况下,优先选择编号较小的安装位置。
步骤2:将该路由器覆盖范围内的设备,从其他安装位置的覆盖范围中移除。
步骤3:在剩余安装位置中继续选择覆盖设备最多的安装位置并安装路由器。
步骤4:重复上述步骤,直到所有设备都被覆盖。
若m的值为7,n的值为3,每个安装位置的路由器能覆盖的设备如图所示。位置0的路由器能覆盖编号为1至4的设备,设备编号区间用列表[1,4]表示。在位置2的覆盖设备中移除设备4,位置2覆盖设备编号区间为[5,7],2台路由器的覆盖区间为[1,7],能覆盖所有设备。
程序中用到的列表函数与方法如下表所示:
函数与方法 功能
lst.append(x) 在列表lst末尾添加元素x
lst.insert(i,x) 在列表lst中下标为i位置处插入元素x
lst.pop(i) 将列表lst中下标为i的元素删除
(1)若有4个位置可以安装路由器,每个安装位置覆盖的设备编号如下表所示,需覆盖7个设备,按上述查找算法,则安装路由器的位置依次是　　　　。
安装位置 0 1 2 3
设备编号 1,2,4,7 1,5,7 2,3,4,6 3,5,6,7
(2)定义如下addup(lst,m)函数,参数lst存储安装位置能覆盖设备的编号,如lst=[[1,2,4,7],[1,5,7],[2,3,4,6],[3,5,6,7]],元素lst[0]表示安装位置0可以覆盖编号为1,2,4,7的设备,参数m表示总共设备的数量。函数功能统计各个设备可被覆盖的安装位置。
def addup(lst,m):
　　sta=[[]for i in range(m+1)]
　　for i in range(len(lst)):　#统计各个设备可被覆盖的安装位置
　　　　for d in lst[i]:
　　　　　　sta[d].append(i)
　　return sta
若lst为[[1,2,4,7],[1,5,7],[2,3,4,6],[3,5,6,7]],m为7,调用addup(lst,m)后,sta的最后一个元素值为　　　　。
(3)实现查找最少安装位置功能的部分Python程序如下,请在划线处填入合适代码。
def search(lst):
　　#函数功能:返回列表lst中长度最大元素的下标,若有多个,返回第1个,代码略。
def plan(left,right,segs):用指针i遍历segs,找到位置i并在其前面插入新区间或合并的i区间。
　　i=0
　　while isegs[i][1]+1:
　　　　i+=1
　　if len(segs)==0 or right+1　　　　segs.insert(i,[left,right])
　　elif right+1==segs[i][0]:
　　　　segs[i][0]=left
　　elif i　　　　segs[i][1]=segs[i+1][1]
　　　　segs.pop(i+1)
　　else:
　　　　①　　　　　
def dellst(x,sta,lst):　#函数功能:删除列表lst中值为x的数据项。
　　for d in ②　　　　　　:
　　　　i=0
　　　　while lst[d][i]!=x:
　　　　　　i+=1
　　　　lst[d].pop(i)
'''
读取需覆盖的设备数量存入m,可供安装路由器的位置数量存入n;
读取各个安装位置能覆盖设备的编号,依次存入列表lst中,列表lst各元素的数据项升序排列。代码略。
'''
sta=addup(lst,m)
ans,segs=[],[]
while segs!=[[1,m]]:
　　pos=search(lst)
　　tmp=[d for d in lst[pos]] #将列表lst[pos]各个元素复制到tmp列表
　　i,j=0,0
　　while j　　　　whilej　　　　　　j+=1
　　　　plan(tmp[i],tmp[j-1],segs)
　　　　③　　　　　
　　ans.append(pos)
　　for x in tmp:
　　　　dellst(x,sta,lst)
#依次输出安装路由器的位置及数量,代码略。
思维点拨
明考向 本题考查顺序查找算法以及桶的应用
精点拨 (1)在位置0安装路由器,覆盖设备1,2,4,7,去除已经覆盖后,在位置3安装路由器,实现全覆盖。(2)函数功能统计各个设备可被覆盖的安装位置。最后一个元素指位置7安装了编号为0,1,3共3个设备。(3)①有4种情况要在区间i前插入新区间[left,right],若条件right+1==segs[i][0]成立,合并到区间i的左侧。若条件i答案　(1)0,3　(2)[0,1,3]
(3)①segs[i][1]=right　②x　③i=j
变式 银行有k个办理业务的窗口(编号0~k-1),窗口分为普通和VIP两种类型。VIP窗口在没有VIP客户的时候,也可以接待普通客户。各窗口按客户到达的先后为他们办理业务,若客户到达时刻相同,则先接待服务时长短的客户。办理规则是:
①如果有空闲的VIP窗口,先安排已到达的VIP客户办理业务;
②如果没有空闲的VIP窗口,VIP客户可到其它窗口办理业务,但需要和普通客户一起按到达先后办理业务;
③有多个空闲窗口时,把客户安排到编号小的窗口办理
以k=3,窗口2为VIP窗口为例,客户信息如图a所示。时刻0,3个窗口均空闲,A和B两个客户已到达(类型0指普通客户,1指VIP客户)。VIP客户B按规则①到VIP窗口2,客户A到编号较小的窗口0。时刻5,VIP客户C按规则②到窗口1办理业务。全部的接待顺序如图b所示。
到达时刻 服务时长 类型 客户名称
0 12 0 A
0 15 1 B
5 16 1 C
5 18 0 D
5 20 0 E
11 13 1 F
图a
办理时刻 窗口0、1、2 结束服务时间 说明
0 [12,0,15] B到窗口2、 A到窗口0
5 [12,21,15] C到窗口1
12 [30,21,28] D到窗口0
15 [30,21,28] F到窗口2
21 [30,41,28] E到窗口1
图b
窗口0接待:A,D 窗口1接待:C,E 窗口2接待:B,F
图c
编写程序模拟接待过程,输出各窗口接待的客户序列,如图c所示。请回答以下问题:
(1)若客户F的到达时刻是50,窗口2接待的客户序列是　　　　。
(2)定义如下的sortD(d)函数,列表d的每个元素存储客户信息,由到达时刻,服务时长,类型和客户名称四个数据项组成,且列表d已经按到达时间升序排序。函数的功能是将客户信息进一步加工为到达时刻相同时,按服务时长升序排列。
def sortD(d):
　　for i in range(1,len(d)):
　　　　j=i-1
　　　　while j>=0:
　　　　　　if d[j][0]　　　　　　　　break
　　　　　　d[j],d[j+1]=d[j+1],d[j]　#①
　　　　　　j-=1
　　return
用以下3组数据测试sortD(d),①处语句执行次数最少的是　　　　(单选:填字母)。
A.[[0,16,0,'A'],[0,18,0,'B'],[2,20,0,'C'],[2,23,0,'D'],[2,12,0,'E'],[2,15,0,'F']]
B.[[0,16,0,'A'],[0,18,0,'B'],[2,20,0,'C'],[2,12,0,'E'],[2,23,0,'D'],[2,15,0,'F']]
C.[[0,18,0,'B'],[0,16,0,'A'],[2,12,0,'E'],[2,20,0,'C'],[2,15,0,'F'],[2,23,0,'D']]
(3)实现窗口接待客户的Python程序段如下,请在程序中划线处填入合适的代码。
函数与方法 功能
viper.append(x) 在列表viper末尾添加元素x
t=viper.pop(x) 将列表x位置元素赋值给t,并将其从viper中删除
#读取n条客户信息存储到列表d中,每个元素由到达时刻,服务时长,类型和客户名称组成,代码略
sortD(d)
k=6　#窗口总数
vipwin=[2,4,5]　#VIP窗口编号
wins=[0]*k
lst=[[] for i in range(k)]　#lst[i]存放编号为i的窗口接待客户序列
viper=[]
for i in range(n):
　　if d[i][2]==1:
　　　　①　　　　　
i=0
while i　　cur=min(wins)　#min函数返回列表wins中的最小值
　　if cur　　　　cur=d[i][0]
　　for j in vipwin:
　　　　if wins[j]<=cur:　#按规则①
　　　　　　if len(viper)>0 and d[viper[0]][0]<=cur:
　　　　　　　　t=viper.pop(0)
　　　　　　　　②　　　　　
　　　　　　　　lst [j].append(d[t][3])
　　　　　　　　d[t][2]=-1
　　　　　　else:
　　　　　　　　break
　　for j in range(k):
　　　　if wins[j]<=cur:
　　　　　　while ③　　　　　　:
　　　　　　　　i+=1
　　　　　　if i　　　　　　　　if d[i][2]==1:
　　　　　　　　　　viper.pop(0)
　　　　　　　　wins[j]=cur+d[i][1]
　　　　　　　　lst[j].append(d[i][3])
　　　　　　　　i+=1
#输出各窗口的接待客户序列,代码略
答案　(1)B,E,F　(2)C　(3)①viper.append(i)
②wins[j]=cur+d[t][1]
③i解析　(1)若客户F到达时刻是50,全部接待顺序如下,窗口2接待的客户顺序为B,E,F。
办理时刻 窗口0、1、2 结束服务时间 说明
0 [12,0,15] B到窗口2, A到窗口0
5 [12,21,15] C到窗口1
12 [30,21,15] D到窗口0
15 [30,21,35] E到窗口2
50 [50,50,50] F到窗口2
(2)函数sortD功能采用插入排序,将未排序部分的元素i向前交换,直至不满足交换条件。A选项共交换4次,B选项交换3次,C选项交换2次。(3)①调用sortD函数,整理了原始数据的处理优先级,将VIP客户和普通分开单独存储到viper列表中。②wins数组存储每个窗口的结束时间,若当前结束的是VIP窗口,且有VIP客户已经到达(d[viper[0]][0]<=cur),则优先接待VIP客户(viper.pop(0)),同时更新当前窗口处理结束时间为wins[j]=cur+d[t][1](开始处理时间+需要处理时长)。③已经接待过的VIP用户t,采用语句d[t][2]=-1标记为-1,处理时需要在d中跳过已经被接待的用户。
1.有n种原材料,这些材料将被用在k条不同的流水线进行产品加工,每个流水线所需的材料各不相同。因此,要求每个流水线提出自己的材料需求,这些需求用一串n位,由0、1和-1三种值组成的数表示,其中:1表示当前流水线必须使用该材料;0表示该材料可加可不加,-1表示当前流水线不需要该材料。如0110-1-1表示当前流水线必需第2、第3种材料,不需要第5、第6种材料,第1、第4中材料可有可无。
现通过编程计算能否找到一个用最少原材料种类,且能满足所有流水线的生产需求的最佳原材料生产方案。如图所示为两条流水线给出的需求,可给出原材料的最佳生产方案为:110001。该01组成的串表示1号、2号、6号原材料需生产,3号、4号、5号原材料无需生产。
流水线1 流水线2
材料编号 1 2 3 4 5 6 1 2 3 4 5 6
需求 1 1 0 -1 0 1 0 1 -1 -1 -1 1
(1)现在有3种原材料,4条流水线分别给出的需求为1,0,1;1,-1,0;0,0,1;1,-1,1。能满足所有流水线的原材料生产方案为　　　　(用原材料编号顺序01组合的串表示生产方案)。
(2)定义chan(s,n,k)函数,将01字符串s转换成包含k个数据元素,每个数据元素包含n个数据项的数据存储形式。
def chan(s,n,k):
　　a=[[] for i in range(k)]
　　p=0;i=0
　　while p　　　　if s[p]!="-":
　　　　　　a[i].append(int(s[p]))
　　　　　　p+=1
　　　　else:
　　　　　　a[i].append(int(s[p:p+2]))
　　　　　　p+=2
　　　　if len(a[i])==n:
　　　　　　i+=1
　　return a
若字符串s的值为“110-10101-1-1-11”调用chan(s,6,2)函数,则语句“i+=1”的执行次数为　　　　。
(3)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
#读取原材料种类n,流水线数量k及k条流水线的材料需求保存在字符串s中,s的格式形如“1011-100011-11”,代码略。
b=[0]*(n+1)
a=chan(s,n,k)
p=True
while ①　　　　　　:
　　j=n
　　while b[j]==1:
　　　　j-=1
　　b[j]=1
　　for i in range(j+1,n+1):
　　　　②　　　　　
　　p=False
　　for i in range(len(a)):
　　　　for j in range(len(a[i])):
　　　　　　if a[i][j]==1 and b[j+1]==0 or ③　　　　:
　　　　　　　　p=True
if p==True:
　　print("无最佳原材料生产方案!")
else:
　　for i in range(1,n+1):
　　　　if b[i]==1:
　　　　　　print("原材料",i,"必须生产")
　　　　else:
　　　　　　print("原材料",i,"无需生产")
答案　(1)101　(2)2
(3)①p==True and b[0]==0　②b[i]=0
③a[i][j]==-1 and b[j+1]==1
解析　(1)2号材料为非必要材料。(2)函数将字符串s转换二维列表存储的数据项。二维列表包含k个数据元素,每个数据元素包含n个数据项。现调用的自定义函数为:chan(s,6,2)函数,k值为2,故i+=1语句执行两次。(3)①遍历所有的可能方案,若b[0]==1,则表示已遍历所有可能。若p=False,则已找到最优方案,推出循环。②j从n位置开始遍历,若b[j]==1,将该位置值置为0,并向j-1位置进位,循环往复,直到b[j]==0退出循环,并将b[j]置为1。此处为退出循环后,统一将n到j+1位置的b数组值置为0。③遍历二维数组,若发现不符合:1表示当前流水线必须使用该材料;-1表示当前流水线不需要该材料。
2.某餐厅餐桌设置如下表:
餐桌型号 2人 小桌 4人 方桌 6人 大方桌 12人 大圆桌
餐桌数量 8 15 10 4
平均就餐 时间(分钟) 25 45 60 80
有客人来就餐时其叫号系统会自动生成一个号码,并根据人数安排餐桌型号;当对应餐桌型号有空桌时,按餐桌编号(由小到大)即时分配餐桌安排客人就餐;当对应餐桌型号没有空桌时,客人按先后顺序排队。程序部分运行界面如下:
11号客人,给您安排的是4人桌,前面还有0人在等位。 11号客人请用餐→4人桌2号 12号客人,给您安排的是2人桌,前面还有1人在等位。 13号客人,给您安排的是2人桌,前面还有2人在等位。
(1)定义如下gettype函数,功能为输入客人人数,返回对应桌型,请在程序划线处填入合适代码。
def gettype(num):
　　type=-1
　　for i in range(len(size)):
　　　　if num<=size[i]:
　　　　　　type=i
　　　　　　　　　
　　return type
(2)定义如下checktable()函数,功能为输入桌型,返回对应桌型空桌的编号,返回值类型为列表,请在程序划线处填入合适代码。
def checktable(n):
　　ans=[]
　　for i in range(nums[n]):
　　　　if 　　　　　　:
　　　　　　ans.append(i)
　　return ans
(3)解决上述问题的主程序如下,请在程序划线处填入合适代码。
size=[2,4,6,12]　#每种桌型最大就餐人数
nums=[8,15,10,4]　#每种桌型的餐桌数量
times=[25,45,60,80]　#每种桌型平均就餐时间
flags=[[True]*nums[i] for i in range(4)]
#标记每张桌子的初始状态
s_time=10*60*60　#开始营业时间——10点整,转化为秒
e_time=14*60*60　#结束营业时间——14点整,转化为秒
maxn=50　#假设队列已经足够深
qc=[[0]*maxn for i in range(4)]　#循环队列
now_time=s_time
id=0
head,tail=[0]*4,[0]*4
while now_time　　number=getinfo()　#调用函数getinfo(),获取客人人数
　　if number>0:
　　　　id+=1
　　　　type=gettype(number)　#根据就餐人数确定餐桌类型
　　　　if type!=-1:
　　　　　　qc[type][tail[type]]=id
　　　　　　tail[type]=(tail[type]+1)%maxn
　　　　　　qc_len=①　　　　　
　　　　　　print(id,"号客人,给您安排的是",size[type],"人桌,前面还有",qc_len-1,"人在等位")
　　　　else:
　　　　　　print(id,"号客人,非常抱歉,没有适合您的桌型!")
　　for i in range(4):
　　　　tables=checktable(i)
　　　　if ②　　　　　　:
　　　　　　flags[i][tables[0]]=False　#入座第一个空桌
　　　　　　print(qc[i][head[i]],"号客人请用餐→",size[i],"人桌",tables[0],"号")
　　　　　　head[i]=(head[i]+1)%maxn
　　now_time+=1
　　#更新每张餐桌的就餐情况,代码略
答案　(1)break　(2)flags[n][i]==True
(3)①(tail[type]-head[type]+maxn)%maxn
②len(tables)>0 and head[i]!=tail[i] 或
tables and head[i]!=tail[i]
解析　本题考查循环队列的基本应用。(1)gettype函数功能为输入客人人数,返回对应桌型。size数组存储每种桌型最大就餐人数,从小桌开始枚举,找到相应的规格就结束查找。(2)checktable函数功能找到对应桌型的空桌编号。nums 每种桌型的餐桌数量,flags 二维数组标记每种桌型每张桌子的初始状态,n为桌型编号,nums[n]表示该种桌型中最多就餐桌位,在flags[n]列表中从头开始(循环变量i 从0至nums[n]-1中枚举)查找值为True(空桌)的编号,并将这些编号添加到列表ans中,因此答案为flag[n][j]==True。(3)①求队列长度,qc存储循环列表的信息,type表示餐桌类型,qc[type]就是存储该类型的循环列表,循环队列长度公式(tail-head+ maxn)% maxn,因此①答案为(tail[type]-head[type]+ maxn) % maxn。②输出安排就餐情况。变量i表示每种桌型,安排座位的条件有两个,一是这种桌型有客人来,即qc[i]队列不为空;二是这种桌型有空位,tables调用checktable(i)函数,获取空位列表。
3.某社区共有n位居民,每位居民都有一个唯一的编号,编号为1到n。工作人员在调查中发现这n位居民之间存在k个亲属关系。每个亲属关系可以用一个列表[a,b]来表示(a编写程序:给定n位居民的编号及k个亲属关系的具体信息,求n位居民中总共有多少个不同的家庭以及最大的家庭中有多少人。请回答下列问题:
(1)若社区中有10位居民,编号从1到10。经过初步调查,社区工作人员发现了以下6个亲属关系:[3,7]、[9,10]、[5,6]、[2,3]、[4,5]、[1,4],根据给定的亲属关系可以确定这10位居民总共组成了　　　　个不同的家庭。
(2)定义如下merge(lst1,lst2)函数,参数lst1和lst2的每个元素包含2个数据项,分别存放一对亲属关系。lst1和lst2均已按第一个数据项升序排列。函数功能是将lst2中的元素合并到lst1中,lst1按第一个数据项保持升序排列,函数返回lst1。
def merge(lst1,lst2):
　　x=len(lst1)-1;y=len(lst2)-1
　　tail=x+y+1
　　for i in range(y+1):
　　　　lst1.append([0,0])
　　while y>=0:
　　　　if x>=0 and lst1[x][0]>lst2[y][0]:
　　　　　　lst1[tail]=lst1[x];x-=1
　　　　else:
　　　　　　lst1[tail]=lst2[y];y-=1
　　　　tail-=1
　　return lst1
若lst1为[[1,2],[3,4],[10,11],[12,13],[17,18]],lst2为[[5,6],[9,10],[14,15],[15,16],[19,20]],调用merge(lst1,lst2)函数,则语句“lst1[tail]=lst1[x]”的执行次数为　　　　。
(3)实现上述功能的部分Python程序如下,请在程序中划线处填入合适的代码。
def check(x):
　　num=0;q.append(x)
　　f[x]=1;num+=1
　　while ①　　　　　　:
　　　　t=q.pop()
for i in range(0,len(s[t])):
　　if f[s[t][i]]==0:
　　　　q.append(s[t][i])
　　　　f[s[t][i]]=1;num+=1
　　return num
n=int(input("请输入社区总人数:"))
q=[];f=[0]*(n+1)
total=0;maxsum=0
#读取csv文件中的关系数据,存入列表r1、r2,2个列表中的每个元素包含2个数据项,分别存放一对亲属关系。2个列表的数据已分别按编号升序排列,代码略。
a=merge(r1,r2)
#根据列表r1、r2中亲属关系数据,进行合并排序
s=[]
for i in range(n+1):
　　s.append([])　#s[i]初始为空列表,存放编号为i的居民直接相关的亲属编号
k=len(a)
for i in range(k):
　　②　　　　　
for i in range(1,n+1):
　　if f[i]==0:
　　　　tmp=check(i)
　　　　if tmp>maxsum:
　　　　　　maxsum=tmp
　　　　③　　　　　
print(n,'位居民中总共有',total,'个不同的家庭')
print('最大的家庭中有',maxsum,'人')
答案　(1)4　(2)3　(3)①len(q)>0或len(q)!=0
②s[a[i][0]].append(a[i][1])　③total+=1
解析　(1)略。(2)通过模拟计算,lst1[tail]=lst1[x]的执行次数为3次。(3)①len(q)>0或len(q)!=0来判断队列q是否还有元素。如果队列不为空,说明还有居民没有处理完,需继续循环处理这些居民。②把2个居民的亲属关系记录下来,构建一个居民和他们亲属关系。③统计社区里有多少个独立的家庭。每当发现一个新的家庭时,就把家庭数量total加1。
1.有n位员工申请m个培训项目。每位员工对项目有志愿顺序;每个项目对员工进行匹配度评估得到具体分值,分值均不相同。每个项目最多录取cap位员工,项目可以不满员,员工也可以不被录取。
培训项目录取规则如下:依次处理每位员工,依照其志愿顺序尝试录取。若当前志愿的项目未招满,则拟录取该员工.若已招满,则当前员工与该项目拟录取员工中匹配度最低者进行比较:①若当前员工匹配度更高,则拟录取该员工,匹配度最低者被淘汰并等待下次处理;②若当前员工匹配度更低,则对当前员工的下一志愿项目尝试录取.直到所有员工都已被拟录取或者未被拟录取员工所有志愿均已尝试,录取过程结束。
例如,有3位员工(用大写字母表示)和3个项目(用正整数表示),每个项目最多录取2位员工。各员工的志愿顺序如图a所示,各项目的员工匹配度如图b所示,录取过程如下:员工A被项目3拟录取→员工B被项目3拟录取→员工C被项目3拟录取(员工B被淘汰)→员工B被项目1拟录取。录取结束,结果为:项目1录取B,项目2没有录取员工,项目3录取A和C。
员工编号 志愿顺序
A 项目3,项目2,项目1
B 项目3,项目1,项目2
C 项目3,项目1,项目2
图a
　　　 员工编号 志愿顺序 A B C
1 71 82 93
2 88 96 90
3 78 69 89
图b
请回答下列问题:
(1)若员工B的志愿顺序修改为“项目2,项目1,项目3”,按上述规则进行录取,则员工B的录取结果是　　　　(单选,填字母:A.被项目1录取/B.被项目2录取/C.未被录取)。
(2)定义如下sel(a,s,stf)函数,参数a表示某项目已拟录取的员工,参数s表示该项目的员工匹配度,参数stf表示当前待录取员工.员工编号“A”~“Z”用0~25表示。
def sel(a,s,stf):
　　idx=0
　　for j in range(1,len(a)):
　　　　if s[a[j]]　　　　　　idx=j
　　if s[a[idx]]　　　　return idx
　　else:
　　　　return-1
调用sel函数,若a值为[2,3],s值为[90,80,85,70],stf值为1,则函数返回的结果为　　　　。(单选,填字母:A.-1/B.0/C.1/D.2)
(3)实现录取过程的部分Python程序如下,请在划线处填入合适的代码。
#读取项目对员工的匹配度分值存储到列表scores,如[[71,82,93],...];读取员工的志愿顺序存储到列表pstf,如[[3,2,1],...]。读取项目人数上限值存储到cap.代码略.
m n=len(scores),len(pstf)　　#m个项目,n位员工(n≤26)
cur=[0]*n
adm=[[]for i in range(m)]　　　　#生成包含m个空列表的列表
waitlst=[I for i in range(n+1)]　　#生成从0到n的整数列表
head,tail=0,n
while ①　　　　　　　　:
　　stf=waitlst[head]
　　head=(head+1)%(n+1)
　　for i in range(cur[stf],m):
　　　　p=pstf[stf][i]-1
　　　　if ②　　　　　　　　:
　　　　　　adm[p].append(stf)　　#为adm[p]追加一个元素stf
　　　　　　break
　　　　else:
　　　　　　ret=sel(adm[p],scores[p],stf)
　　　　　　if ret!=-1:
　　　　　　　　waitlst[tail]=adm[p][ret]
　　　　　　　　tail=(tail+1)%(n+1)
　　　　　　　　③　　　　　　　
　　　　　　　　break
　　cur[stf]=i+1
for i in range(len(adm)):
　　print("项目"+str(i+1)+"录取的员工:",end="")
　　for j in adm[i]:
　　　　print(chr(j+ord("A")),end="")
　　print()
答案　(1)B　(2)C　(3)①head!=tail　②len(adm[p])解析　本题考查队列的综合应用。(1)员工A被项目3录取,员工B录取2,员工C第一志愿项目3,项目3当前和员工A和C。(2)参数a表示某项目已拟录取的员工,值为[2,3]。参数s表示0~3员工的分数,当前员工stf值为1,分数80,函数功能会找到a中得分最低分员工。员工2为85分,员工3为70分,返回最低分的索引1。(3)①当队列非空时head!=tail,继续处理队列中数据。②当前项目录取人数len(adm[p])未达上限cap时可直接录取。③将当前员工stf放入被淘汰员工的位置adm[p][ret]。
2.在数据压缩前,对数据进行预处理可以在一定程度上提高压缩效率。以下模拟对长度为n的字符串data(由小写字母组成)进行预处理,步骤如下:
步骤1:将“$”字符添加到字符串data末尾得到新字符串;
步骤2:将新字符串循环右移1位,重复n次后,共得到n+1个循环字符串;
步骤3:将步骤2得到的所有字符串进行升序排序(“$”的ASCII码比英文字母都小);
步骤4:取排序后每个字符串的最后一个字符拼接,得到字符串datas。
如字符串data="abcbc",经过变换后得到datas="c$cabb",变换过程如图所示。
编写Python程序,将变换后的字符串datas还原为data。
(1)若变换后datas的结果为“abc$”,则变换前的字符串data为　　　　。
(2)定义sortd(datas)函数如下:
def sortd(datas):
　　k=[i for i in range(len(datas))]
　　for i in range(len(datas)):
　　　　for j in range(len(datas)-1-i):
　　　　　　if datas[k[j]]>datas[k[j+1]]:
　　　　　　　　k[j],k[j+1]=k[j+1],k[j]
　　return k
若datas为"abc$",调用sortd(datas)后,函数的返回值为[　　　　]。
(3)实现“还原”功能的部分Python程序如下,请在划线处填入合适的代码。
datas=input("输入变换后的字符串datas:")
k=sortd(datas)
link=[]
for i in range(len(datas)):
　　link.append([datas[i],①　　　　　　])
head=②　　　　　
ans=""
q=link[head][1]
while ③　　　　　　:
　　ans+=link[q][0]
　　q=link[q][1]
print("还原的结果为:",ans)
答案　(1)cba　(2)3,0,1,2　(3)①k[i]　②k[0]　③q!=head或q!=k[0]
解析　(1)升序各子串的第1个字母依次为$abc,排序后以$开头的子串中,a在最后,因此a的后面是$。同理可得,b的后面是a,c的后面是b,a的后面又是$,形成一个环。(2)列表k的初值为[0,1,2,3],按字母进行索引排序(升序)后,最小字母的索引为3,因此函数的返回值为[3,0,1,2]。(3)由第(1)小题可知,加密后的字符串是原字符串中各个字母按升序构成的一个环,根据加密后的位置能推断出加密前该字母后一个字母。①先对字符串各个字母进行升序列表,其索引存储在列表k中,遍历加密后的各个字母,当前字母的下一个就是升序排列后的索引位置。②将“$”字符添加到字符串data末尾得到新字符串,因此$下一个字母是加密前的第1个字母,q从头节点的下一个节点开始遍历,因此头指针是k[0]。③指针q从第2个节点开始遍历,当遍历到头节点时,把所有的字母进行了还原。
3.小阳的创意工坊,每天都会接到很多订单,且每个订单花费一个单位时间。其中order列表中存储每个订单的截止时间和利润。假设他的工作是从0时刻开始算,订单能在截止时间内(包括截止时间)完成,就会获得利润。他可以选择完成当前时间之后的任意一个订单,过了截止时间的订单就会自动取消。
(1)为了获得较高利润,小阳想到按时间优先的方式来完成订单。为此定义tsort(lst)函数,其中参数lst的每个元素包括截止时间和利润。函数的功能是根据订单截止时间升序排列。
def tsort(lst):
　　n=len(lst)
　　for i in range(n-1):
　　　　for j in range(n-i-1):
　　　　　　if lst[j][0]>lst[j+1][0]:
　　　　　　　　lst[j],lst[j+1]=lst[j+1],lst[j]
　　return lst
调用该函数,若lst=[[2,4],[1,4],[1,2],[3,5],[2,3],[3,6]],虚线框中的程序段执行次数为　　　　。
(2)小阳发现按时间优先设计的算法,获得的利润并不是最大的。在截止时间进行排序后的订单基础上对算法重新设计:依次对每个订单进行处理,确保每个截止时间要完成的订单利润为当前订单队列和所有未超时订单中利润最高。部分python程序段如下,
请在划线处填入合适的代码。
order=[[2,5],[1,4],[1,3],[3,1],[3,2],[2,6]];n=len(order)
ans=0　#ans存放最大利润之和
que=[[] for i in range(n)]　#利润优先订单队列
head=tail=0
order=tsort(order)
def enque(tmp,tail,head):　#数组模拟优先队列入队
　　p=tail
　　que[tail]=tmp
　　tail+=1
　　for i in range(tail-1,head,-1):
　　　　if que[i-1][1]>tmp[1]:
　　　　　　que[i]=que[i-1]
　　　　　　①　　　　　
　　que[p]=tmp
　　return tail
for i in range(n):
　　if ②　　　　　　:
　　　　tail=enque(order[i],tail,head)
　　　　ans+=order[i][1]
　　else:
　　　　if order[i][1]>que[head][1]:
　　　　　　③　　　　　
　　　　　　head+=1
　　　　　　tail=enque(order[i],tail,head)
　　　　　　ans+=order[i][1]
print("利润最大为"+str(ans))
(3)小阳接到订单 order=[[2,5],[1,4],[1,3],[3,1],[3,2],[2,6]],输出结果为　　　　。
答案　(1)3　(2)①p=i-1　②order[i][0]>tail-head　③ans-=que[head][1]　(3)利润最大为13
解析　(1)加框处语句为冒泡排序中数组的交换次数,程序实现升序排列,只需找到数据中的逆序对。[2,4]和[1,4],[1,2]是逆序对,[3,5]和[2,3]是逆序对。(2)①实现在有序的队列que中插入新数据订单tmp,从后往前遍历,若大于tmp[1]的元素,则将其后移一位que[i]=que[i-1],同时更新变量p的值。②将没有超时的订单入队,并计算队列中所有订单的总利润。③在当前订单和已经入队的订单中删除一个利润最小的订单。若当前订单的利润大于队首订单的利润(队首订单利润最低),删除队首订单(出队处理),然后将当前订单入队并插入到合适的位置,从而保证利润总和最大。而ans已经存储了之前入队的订单利润和,因此当删除队首订单时,需要减去原队首订单利润,并加上当前入队订单利润。(3)利润最大为5+6+2。
4.某工厂生产的产品包含n个(编号为0~n-1)组件,其组装可由多名工人共同协助完成。组装时每个组件都不可遗漏并能按序完成,有些组件存在前置组件(以下简称“前置”),即安装有先后顺序。例如,某产品有6个组件,如图a所示,组件3的前置是组件1和组件2,即安装组件3需要在组件1和组件2完成之后。若0~5号组件的组装所需单位时间分别为2,5,2,4,3,5,则在工人数量不限的情况下,所有组件安装完成最短需要14个单位时间。
为了梳理产品组件的组装顺序,并计算所有组件安装完成所需的最短时间,编写程序模拟组装过程:先同时组装前置总数为0的组件,完成后更新每个组件的前置总数,再重复以上步骤,直至所有组件安装完毕,程序运行结果如图b所示,请回答下列问题:
编号为0~5的组件组装所需单位时间分别为:[2,5,2,4,3,5] 组件组装顺序:[0,1,2,3,4,5] 安装完成所需最短时间:14
图b
(1)图a所示产品的1号组件组装时长若缩短为3个单位时间,其它时间保持不变,则所有组件安装完成所需最短时间为　　　　个单位时间。
(2)定义如下cal(a,n)函数,参数a列表的每个元素包含两项,a[i][1]是组件编号,a[i][0]是a[i][1]的前置编号,例如a中某个元素值为[2,3],表示组件2是组件3的前置。该函数的返回值是列表s和列表pre,其中s记录所有组件的相互关系,pre[i]记录初始情况下组件i的前置总数。
def cal(a,n):
　　pre=[0]*n
　　s=[[0 for i in range(n)] for j in range(n)]　#创建n×n的二维数组s,元素初始值为0
　　for i in range(len(a)):
　　　　x,y=a[i][0],a[i][1]
　　　　s[x][y]=1
　　　　pre[y]=　　　　　
　　return pre,s
(3)定义如下proc(n,s,pre)函数,该函数的返回值是列表v,v[i]代表从开始到组件i完成组装所需的最短时间。请在划线处填入合适的代码。
def proc(n,s,pre):
　　head=tail=0
　　que=[0]*n
　　for i in range(n):
　　　　if pre[i]==0:
　　　　　　que[tail]=i
　　　　　　tail+=1
　　while head　　　　x=que[head]
　　　　head+=1
　　　　for i in range(n):
　　　　　　if s[x][i]==1:
　　　　　　　　pre[i]-=1
　　　　　　　　if pre[i]==0:
　　　　　　　　　　que[tail]=i
　　　　　　　　　　tail+=1
　　　　　　　　v[i]=max(v[i],①　　　　　　)
　　return v
#组装编号0~n-1的单个组件所需时间存入t列表,组件前置关系存入a列表,如图a所需时间t=[2,5,2,4,3,5];a=[[0,2],[2,3],[1,3],[3,5],[3,4],[4,5]]
n=len(t);v=t[:]
pre,s=cal(a,n)
v=proc(n,s,pre)
data=[0]*n
result=[i for i in range(n)]　#创建列表result=[0,1,2,……,n-1]
for i in range(n):
　　data[i]=v[i]-t[i]　#data[i]表示组件i开始安装时间
for i in range(n-1):　#按组件开始安装时间升序排序,开始安装时间相同时按组件序号升序
　　for j in range(n-1-i):
　　　　if data[result[j]]>data[result[j+1]]:
　　　　　　②　　　　　
print("组件组装顺序:",result,",安装完成所需最短时间:",max(v))
(4)以下选项与题(3)加框处代码功能相同的是　　　　(多选,填字母)。
A.head!=tail B.headC.tail<=n D.len(que)> 0
答案　(1)13　(2)pre[y]+1　(3)①t[i]+v[x]　②result[j],result[j+1]=result[j+1],result[j]　(4)AB
解析　(1)有0→2→3→5,1→3→5,4→5三个组件链,在组件3前面两个并行的任务链,1号组件组装时长若缩短为3个单位时间,其时间分为2+2,3,较长时间为4,组件3的时间为4,合计为8,而组件4所需时间为3,因此总共所需时间为8+5=13。(2)①函数cal统计各个组件的前置总数,组件y的前置是组件x,因此组件y的前置总数pre[y]等于自身加1。②函数proc功能是计算每个组件i从开始到组件i完成组装所需的最短时间v[i]。先将前置组件数为0的索引入队,因此队列元素依次为0,1,4。队首为组件0,其后置组件2所需时间为前置组件0与他本身时间之和,v[2]=2+2=4。执行语句pre[i]-=1,i入队,接着组件1出队计算其后置组件3即v[3]的时间为3+4=7;接着4出队,v[5]时间为3+5=8。接着2出队,v[x]值为4,组件3即v[3]的时间为4+4=8,在两个前置中找一个较大值作为最短时间。遍历各个组件,条件s[x][i]==1表示组件x是组件i的前置,完成组件x所需时间为v[x],那么完成组件i总共所需时间为v[x]+t[i]。完成组件i可能有多个前置,完成组件x之前的最长时间为v[i],在两个时间中取出一个较大值。(3)data[i]表示组件i开始安装时间,result存储的是从小到大排列的组件序号,当条件data[result[j]]>data[result[j+1]]成立就交换两个索引位置。若data[result[j]]和data[result[j+1]]相等,本身也是按序号排列的,因此无需交换。(4)加框处代码为队列不为空的意思,而队列的长度就是n,因此AB选项符合题意。
5.有一个内存大小为n的内存条a,起始为空,每次进来一个任务它都会占用空余的最前面的一段或多段内存,删除任务则解放它占用的所有内存部分。
例如:n=100
进内存S01 20 S01占用的内存为[0,20),a存储为[0,20)
进内存S02 10 S02占用的内存为[20,30),a存储为[0,20),[20,30)
进内存S03 30 S03占用的内存为[30,60),a存储为[0,20),[20,30),[30,60)
删除S02 内存[20,30)清空,a存储为[0,20),[30,60)
进内存S04 20 S04占用的内存为[20,30),[60,70),a存储为[0,20),[20,30),[30,60),[60,70)
(1)已知内存大小为100的占用情况为[0,10),[20,25),[30,45),[70,75)。现有任务:进内存S02130,所占用的内存区间为　　　　。
(2)在划线处填上合适代码。
a=[]　#保存元素存储情况
dict1={};tmp=0　#将任务名按照顺序对应 0,1,2,3…以便列表作为元素下标
ans=[]
def add(name,v):
　　start=0;i=0
　　while i　　　　now=a[i][0]-start
　　　　if now>=v:
　　　　　　a.insert(i,[start,start+v])
　　　　　　ans[name].append(start)
　　　　　　i+=1
　　　　　　break
　　　　elif ①　　　　　　:
　　　　　　a.insert(i,[start,a[i][0]])
　　　　　　ans[name].append(start)
　　　　　　v-=now
　　　　　　i+=1
　　　　②　　　　　
　　　　i+=1
def find(key):
　　L=0;R=len(a)-1
　　while L<=R:
　　　　m=(L+R)//2
　　　　if a[m][0]==key:
　　　　　　③　　　　　
　　　　elif a[m][0]　　　　　　L=m+1
　　　　else:
　　　　　　R=m-1
def delete(name):
　　for i in range(len(ans[name])):
　　　　t=④　　　　　
　　　　a.pop(t)
n=int(input())
a.append([n+1,n+1])
while True:
　　T=input().split()
　　if T[0]=="进内存":　#T[1]表示占用的任务名,T[2]表示任务内存大小
　　　　dict1[T[1]]=tmp
　　　　tmp+=1
　　　　ans.append([])
　　　　add(dict1[T[1]],int(T[2]))
　　else:　#T[1]表示删除的任务名
　　　　delete(dict1[T[1]])
　　print(a)
答案　(1)[10,20),[25,30),[45,60)　(2)①now!=0　②start=a[i][1]　③return m　④find(ans[name][i])
解析　(1)进内存S021 30需要占用30的空间,当前已经占用[0,10),[20,25),[30,45),[70,75),该任务占用的区间为[10,20),[25,30),[45,60)。(2)函数add用于进内存,参数name表示任务名,参数v表示任务内存大小。遍历已占用部分区间,根据当前空余区间的情况以及待存入任务内存大小,选取相应区间。①当前空余区间大于待存入任务内存大小,更新列表a中的区间占用情况,并在列表ans中根据任务编号对应的位置添加当前占用区间的起始值。当空闲区间now不足以存储整个待存入任务,则先将该部分区间占用,并更新对应的内存占用情况(列表a)、待存任务的区间占用情况(列表ans)、以及待存入任务的剩余待处理部分。②更新内存区间起点start为当前区间的结束位置a[i][1]。③函数find用于查找区间位置,参数key表示该区间的起始位置。列表a中的每个元素包括占用区间的起始位置和结束位置。通过二分查找算法进行当前区间的查找,以供后续区间删除函数delete使用。④name表示任务名,每个任务存在占用多个区间的情况,待存任务的区间占用列表ans中每个数据元素中存储了若干个区间的起始位置,列表ans的索引即为任务名,此处需要根据每个区间的起始位置在内存占用列表a中查找到对应区间,并将其删除。9.3　以数组形式组织数据
学习目标　
1.掌握采用桶等数据结构来记录相应的数据,优化数据访问的时间的方法。
2.要数据遍历过程中,掌握采用队列等数据记录临时处理的数据,以达到优化算法的效果。
(2024年1月浙江选考)某项活动有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]<1st[j][1]: tmp=1st[j]
　　　　1st[j]=1st[j-1]
　　　　1st[j-1]=tmp
if 1st[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)
　　针对情境较为复杂、结构化程度较低的问题,能抽象数据特征、创造性地运用数据结构优化算法。数据往往经过采集、传输、处理和存储的过程,而数据在加工处理过程中,要考虑算法的优越性,提高算法的效率。数据在加工过程中,临时存放的数据可以存储在队列、栈和二维数组中,利用其不用查找就可以操作或者把当前正在处理的数据放置一个较小的数组中的特性,加快数据的处理时间。
例题 某区域有m个设备(编号为1到m)需要联网。单台无线路由器的Wi-Fi信号可以覆盖一个圆形范围。现有n个可供安装路由器的位置(编号为0到n-1)。编写程序,找到最少数量的路由器安装位置,确保所有设备都能被覆盖。查找算法如下:
步骤1:选择一个覆盖设备最多的位置安装路由器。在设备数量相同的情况下,优先选择编号较小的安装位置。
步骤2:将该路由器覆盖范围内的设备,从其他安装位置的覆盖范围中移除。
步骤3:在剩余安装位置中继续选择覆盖设备最多的安装位置并安装路由器。
步骤4:重复上述步骤,直到所有设备都被覆盖。
若m的值为7,n的值为3,每个安装位置的路由器能覆盖的设备如图所示。位置0的路由器能覆盖编号为1至4的设备,设备编号区间用列表[1,4]表示。在位置2的覆盖设备中移除设备4,位置2覆盖设备编号区间为[5,7],2台路由器的覆盖区间为[1,7],能覆盖所有设备。
程序中用到的列表函数与方法如下表所示:
函数与方法 功能
lst.append(x) 在列表lst末尾添加元素x
lst.insert(i,x) 在列表lst中下标为i位置处插入元素x
lst.pop(i) 将列表lst中下标为i的元素删除
(1)若有4个位置可以安装路由器,每个安装位置覆盖的设备编号如下表所示,需覆盖7个设备,按上述查找算法,则安装路由器的位置依次是　　　　。
安装位置 0 1 2 3
设备编号 1,2,4,7 1,5,7 2,3,4,6 3,5,6,7
(2)定义如下addup(lst,m)函数,参数lst存储安装位置能覆盖设备的编号,如lst=[[1,2,4,7],[1,5,7],[2,3,4,6],[3,5,6,7]],元素lst[0]表示安装位置0可以覆盖编号为1,2,4,7的设备,参数m表示总共设备的数量。函数功能统计各个设备可被覆盖的安装位置。
def addup(lst,m):
　　sta=[[]for i in range(m+1)]
　　for i in range(len(lst)):　#统计各个设备可被覆盖的安装位置
　　　　for d in lst[i]:
　　　　　　sta[d].append(i)
　　return sta
若lst为[[1,2,4,7],[1,5,7],[2,3,4,6],[3,5,6,7]],m为7,调用addup(lst,m)后,sta的最后一个元素值为　　　　。
(3)实现查找最少安装位置功能的部分Python程序如下,请在划线处填入合适代码。
def search(lst):
　　#函数功能:返回列表lst中长度最大元素的下标,若有多个,返回第1个,代码略。
def plan(left,right,segs):用指针i遍历segs,找到位置i并在其前面插入新区间或合并的i区间。
　　i=0
　　while isegs[i][1]+1:
　　　　i+=1
　　if len(segs)==0 or right+1　　　　segs.insert(i,[left,right])
　　elif right+1==segs[i][0]:
　　　　segs[i][0]=left
　　elif i　　　　segs[i][1]=segs[i+1][1]
　　　　segs.pop(i+1)
　　else:
　　　　①　　　　　
def dellst(x,sta,lst):　#函数功能:删除列表lst中值为x的数据项。
　　for d in ②　　　　　　:
　　　　i=0
　　　　while lst[d][i]!=x:
　　　　　　i+=1
　　　　lst[d].pop(i)
'''
读取需覆盖的设备数量存入m,可供安装路由器的位置数量存入n;
读取各个安装位置能覆盖设备的编号,依次存入列表lst中,列表lst各元素的数据项升序排列。代码略。
'''
sta=addup(lst,m)
ans,segs=[],[]
while segs!=[[1,m]]:
　　pos=search(lst)
　　tmp=[d for d in lst[pos]] #将列表lst[pos]各个元素复制到tmp列表
　　i,j=0,0
　　while j　　　　whilej　　　　　　j+=1
　　　　plan(tmp[i],tmp[j-1],segs)
　　　　③　　　　　
　　ans.append(pos)
　　for x in tmp:
　　　　dellst(x,sta,lst)
#依次输出安装路由器的位置及数量,代码略。
变式 银行有k个办理业务的窗口(编号0~k-1),窗口分为普通和VIP两种类型。VIP窗口在没有VIP客户的时候,也可以接待普通客户。各窗口按客户到达的先后为他们办理业务,若客户到达时刻相同,则先接待服务时长短的客户。办理规则是:
①如果有空闲的VIP窗口,先安排已到达的VIP客户办理业务;
②如果没有空闲的VIP窗口,VIP客户可到其它窗口办理业务,但需要和普通客户一起按到达先后办理业务;
③有多个空闲窗口时,把客户安排到编号小的窗口办理
以k=3,窗口2为VIP窗口为例,客户信息如图a所示。时刻0,3个窗口均空闲,A和B两个客户已到达(类型0指普通客户,1指VIP客户)。VIP客户B按规则①到VIP窗口2,客户A到编号较小的窗口0。时刻5,VIP客户C按规则②到窗口1办理业务。全部的接待顺序如图b所示。
到达时刻 服务时长 类型 客户名称
0 12 0 A
0 15 1 B
5 16 1 C
5 18 0 D
5 20 0 E
11 13 1 F
图a
办理时刻 窗口0、1、2 结束服务时间 说明
0 [12,0,15] B到窗口2、 A到窗口0
5 [12,21,15] C到窗口1
12 [30,21,28] D到窗口0
15 [30,21,28] F到窗口2
21 [30,41,28] E到窗口1
图b
窗口0接待:A,D 窗口1接待:C,E 窗口2接待:B,F
图c
编写程序模拟接待过程,输出各窗口接待的客户序列,如图c所示。请回答以下问题:
(1)若客户F的到达时刻是50,窗口2接待的客户序列是　　　　。
(2)定义如下的sortD(d)函数,列表d的每个元素存储客户信息,由到达时刻,服务时长,类型和客户名称四个数据项组成,且列表d已经按到达时间升序排序。函数的功能是将客户信息进一步加工为到达时刻相同时,按服务时长升序排列。
def sortD(d):
　　for i in range(1,len(d)):
　　　　j=i-1
　　　　while j>=0:
　　　　　　if d[j][0]　　　　　　　　break
　　　　　　d[j],d[j+1]=d[j+1],d[j]　#①
　　　　　　j-=1
　　return
用以下3组数据测试sortD(d),①处语句执行次数最少的是　　　　(单选:填字母)。
A.[[0,16,0,'A'],[0,18,0,'B'],[2,20,0,'C'],[2,23,0,'D'],[2,12,0,'E'],[2,15,0,'F']]
B.[[0,16,0,'A'],[0,18,0,'B'],[2,20,0,'C'],[2,12,0,'E'],[2,23,0,'D'],[2,15,0,'F']]
C.[[0,18,0,'B'],[0,16,0,'A'],[2,12,0,'E'],[2,20,0,'C'],[2,15,0,'F'],[2,23,0,'D']]
(3)实现窗口接待客户的Python程序段如下,请在程序中划线处填入合适的代码。
函数与方法 功能
viper.append(x) 在列表viper末尾添加元素x
t=viper.pop(x) 将列表x位置元素赋值给t,并将其从viper中删除
#读取n条客户信息存储到列表d中,每个元素由到达时刻,服务时长,类型和客户名称组成,代码略
sortD(d)
k=6　#窗口总数
vipwin=[2,4,5]　#VIP窗口编号
wins=[0]*k
lst=[[] for i in range(k)]　#lst[i]存放编号为i的窗口接待客户序列
viper=[]
for i in range(n):
　　if d[i][2]==1:
　　　　①　　　　　
i=0
while i　　cur=min(wins)　#min函数返回列表wins中的最小值
　　if cur　　　　cur=d[i][0]
　　for j in vipwin:
　　　　if wins[j]<=cur:　#按规则①
　　　　　　if len(viper)>0 and d[viper[0]][0]<=cur:
　　　　　　　　t=viper.pop(0)
　　　　　　　　②　　　　　
　　　　　　　　lst [j].append(d[t][3])
　　　　　　　　d[t][2]=-1
　　　　　　else:
　　　　　　　　break
　　for j in range(k):
　　　　if wins[j]<=cur:
　　　　　　while ③　　　　　　:
　　　　　　　　i+=1
　　　　　　if i　　　　　　　　if d[i][2]==1:
　　　　　　　　　　viper.pop(0)
　　　　　　　　wins[j]=cur+d[i][1]
　　　　　　　　lst[j].append(d[i][3])
　　　　　　　　i+=1
#输出各窗口的接待客户序列,代码略
1.有n种原材料,这些材料将被用在k条不同的流水线进行产品加工,每个流水线所需的材料各不相同。因此,要求每个流水线提出自己的材料需求,这些需求用一串n位,由0、1和-1三种值组成的数表示,其中:1表示当前流水线必须使用该材料;0表示该材料可加可不加,-1表示当前流水线不需要该材料。如0110-1-1表示当前流水线必需第2、第3种材料,不需要第5、第6种材料,第1、第4中材料可有可无。
现通过编程计算能否找到一个用最少原材料种类,且能满足所有流水线的生产需求的最佳原材料生产方案。如图所示为两条流水线给出的需求,可给出原材料的最佳生产方案为:110001。该01组成的串表示1号、2号、6号原材料需生产,3号、4号、5号原材料无需生产。
流水线1 流水线2
材料编号 1 2 3 4 5 6 1 2 3 4 5 6
需求 1 1 0 -1 0 1 0 1 -1 -1 -1 1
(1)现在有3种原材料,4条流水线分别给出的需求为1,0,1;1,-1,0;0,0,1;1,-1,1。能满足所有流水线的原材料生产方案为　　　　(用原材料编号顺序01组合的串表示生产方案)。
(2)定义chan(s,n,k)函数,将01字符串s转换成包含k个数据元素,每个数据元素包含n个数据项的数据存储形式。
def chan(s,n,k):
　　a=[[] for i in range(k)]
　　p=0;i=0
　　while p　　　　if s[p]!="-":
　　　　　　a[i].append(int(s[p]))
　　　　　　p+=1
　　　　else:
　　　　　　a[i].append(int(s[p:p+2]))
　　　　　　p+=2
　　　　if len(a[i])==n:
　　　　　　i+=1
　　return a
若字符串s的值为“110-10101-1-1-11”调用chan(s,6,2)函数,则语句“i+=1”的执行次数为　　　　。
(3)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
#读取原材料种类n,流水线数量k及k条流水线的材料需求保存在字符串s中,s的格式形如“1011-100011-11”,代码略。
b=[0]*(n+1)
a=chan(s,n,k)
p=True
while ①　　　　　　:
　　j=n
　　while b[j]==1:
　　　　j-=1
　　b[j]=1
　　for i in range(j+1,n+1):
　　　　②　　　　　
　　p=False
　　for i in range(len(a)):
　　　　for j in range(len(a[i])):
　　　　　　if a[i][j]==1 and b[j+1]==0 or ③　　　　:
　　　　　　　　p=True
if p==True:
　　print("无最佳原材料生产方案!")
else:
　　for i in range(1,n+1):
　　　　if b[i]==1:
　　　　　　print("原材料",i,"必须生产")
　　　　else:
　　　　　　print("原材料",i,"无需生产")
2.某餐厅餐桌设置如下表:
餐桌型号 2人 小桌 4人 方桌 6人 大方桌 12人 大圆桌
餐桌数量 8 15 10 4
平均就餐 时间(分钟) 25 45 60 80
有客人来就餐时其叫号系统会自动生成一个号码,并根据人数安排餐桌型号;当对应餐桌型号有空桌时,按餐桌编号(由小到大)即时分配餐桌安排客人就餐;当对应餐桌型号没有空桌时,客人按先后顺序排队。程序部分运行界面如下:
11号客人,给您安排的是4人桌,前面还有0人在等位。 11号客人请用餐→4人桌2号 12号客人,给您安排的是2人桌,前面还有1人在等位。 13号客人,给您安排的是2人桌,前面还有2人在等位。
(1)定义如下gettype函数,功能为输入客人人数,返回对应桌型,请在程序划线处填入合适代码。
def gettype(num):
　　type=-1
　　for i in range(len(size)):
　　　　if num<=size[i]:
　　　　　　type=i
　　　　　　　　　
　　return type
(2)定义如下checktable()函数,功能为输入桌型,返回对应桌型空桌的编号,返回值类型为列表,请在程序划线处填入合适代码。
def checktable(n):
　　ans=[]
　　for i in range(nums[n]):
　　　　if 　　　　　　:
　　　　　　ans.append(i)
　　return ans
(3)解决上述问题的主程序如下,请在程序划线处填入合适代码。
size=[2,4,6,12]　#每种桌型最大就餐人数
nums=[8,15,10,4]　#每种桌型的餐桌数量
times=[25,45,60,80]　#每种桌型平均就餐时间
flags=[[True]*nums[i] for i in range(4)]
#标记每张桌子的初始状态
s_time=10*60*60　#开始营业时间——10点整,转化为秒
e_time=14*60*60　#结束营业时间——14点整,转化为秒
maxn=50　#假设队列已经足够深
qc=[[0]*maxn for i in range(4)]　#循环队列
now_time=s_time
id=0
head,tail=[0]*4,[0]*4
while now_time　　number=getinfo()　#调用函数getinfo(),获取客人人数
　　if number>0:
　　　　id+=1
　　　　type=gettype(number)　#根据就餐人数确定餐桌类型
　　　　if type!=-1:
　　　　　　qc[type][tail[type]]=id
　　　　　　tail[type]=(tail[type]+1)%maxn
　　　　　　qc_len=①　　　　　
　　　　　　print(id,"号客人,给您安排的是",size[type],"人桌,前面还有",qc_len-1,"人在等位")
　　　　else:
　　　　　　print(id,"号客人,非常抱歉,没有适合您的桌型!")
　　for i in range(4):
　　　　tables=checktable(i)
　　　　if ②　　　　　　:
　　　　　　flags[i][tables[0]]=False　#入座第一个空桌
　　　　　　print(qc[i][head[i]],"号客人请用餐→",size[i],"人桌",tables[0],"号")
　　　　　　head[i]=(head[i]+1)%maxn
　　now_time+=1
　　#更新每张餐桌的就餐情况,代码略
3.某社区共有n位居民,每位居民都有一个唯一的编号,编号为1到n。工作人员在调查中发现这n位居民之间存在k个亲属关系。每个亲属关系可以用一个列表[a,b]来表示(a编写程序:给定n位居民的编号及k个亲属关系的具体信息,求n位居民中总共有多少个不同的家庭以及最大的家庭中有多少人。请回答下列问题:
(1)若社区中有10位居民,编号从1到10。经过初步调查,社区工作人员发现了以下6个亲属关系:[3,7]、[9,10]、[5,6]、[2,3]、[4,5]、[1,4],根据给定的亲属关系可以确定这10位居民总共组成了　　　　个不同的家庭。
(2)定义如下merge(lst1,lst2)函数,参数lst1和lst2的每个元素包含2个数据项,分别存放一对亲属关系。lst1和lst2均已按第一个数据项升序排列。函数功能是将lst2中的元素合并到lst1中,lst1按第一个数据项保持升序排列,函数返回lst1。
def merge(lst1,lst2):
　　x=len(lst1)-1;y=len(lst2)-1
　　tail=x+y+1
　　for i in range(y+1):
　　　　lst1.append([0,0])
　　while y>=0:
　　　　if x>=0 and lst1[x][0]>lst2[y][0]:
　　　　　　lst1[tail]=lst1[x];x-=1
　　　　else:
　　　　　　lst1[tail]=lst2[y];y-=1
　　　　tail-=1
　　return lst1
若lst1为[[1,2],[3,4],[10,11],[12,13],[17,18]],lst2为[[5,6],[9,10],[14,15],[15,16],[19,20]],调用merge(lst1,lst2)函数,则语句“lst1[tail]=lst1[x]”的执行次数为　　　　。
(3)实现上述功能的部分Python程序如下,请在程序中划线处填入合适的代码。
def check(x):
　　num=0;q.append(x)
　　f[x]=1;num+=1
　　while ①　　　　　　:
　　　　t=q.pop()
for i in range(0,len(s[t])):
　　if f[s[t][i]]==0:
　　　　q.append(s[t][i])
　　　　f[s[t][i]]=1;num+=1
　　return num
n=int(input("请输入社区总人数:"))
q=[];f=[0]*(n+1)
total=0;maxsum=0
#读取csv文件中的关系数据,存入列表r1、r2,2个列表中的每个元素包含2个数据项,分别存放一对亲属关系。2个列表的数据已分别按编号升序排列,代码略。
a=merge(r1,r2)
#根据列表r1、r2中亲属关系数据,进行合并排序
s=[]
for i in range(n+1):
　　s.append([])　#s[i]初始为空列表,存放编号为i的居民直接相关的亲属编号
k=len(a)
for i in range(k):
　　②　　　　　
for i in range(1,n+1):
　　if f[i]==0:
　　　　tmp=check(i)
　　　　if tmp>maxsum:
　　　　　　maxsum=tmp
　　　　③　　　　　
print(n,'位居民中总共有',total,'个不同的家庭')
print('最大的家庭中有',maxsum,'人')
1.有n位员工申请m个培训项目。每位员工对项目有志愿顺序;每个项目对员工进行匹配度评估得到具体分值,分值均不相同。每个项目最多录取cap位员工,项目可以不满员,员工也可以不被录取。
培训项目录取规则如下:依次处理每位员工,依照其志愿顺序尝试录取。若当前志愿的项目未招满,则拟录取该员工.若已招满,则当前员工与该项目拟录取员工中匹配度最低者进行比较:①若当前员工匹配度更高,则拟录取该员工,匹配度最低者被淘汰并等待下次处理;②若当前员工匹配度更低,则对当前员工的下一志愿项目尝试录取.直到所有员工都已被拟录取或者未被拟录取员工所有志愿均已尝试,录取过程结束。
例如,有3位员工(用大写字母表示)和3个项目(用正整数表示),每个项目最多录取2位员工。各员工的志愿顺序如图a所示,各项目的员工匹配度如图b所示,录取过程如下:员工A被项目3拟录取→员工B被项目3拟录取→员工C被项目3拟录取(员工B被淘汰)→员工B被项目1拟录取。录取结束,结果为:项目1录取B,项目2没有录取员工,项目3录取A和C。
员工编号 志愿顺序
A 项目3,项目2,项目1
B 项目3,项目1,项目2
C 项目3,项目1,项目2
图a
　　　 员工编号 志愿顺序 A B C
1 71 82 93
2 88 96 90
3 78 69 89
图b
请回答下列问题:
(1)若员工B的志愿顺序修改为“项目2,项目1,项目3”,按上述规则进行录取,则员工B的录取结果是　　　　(单选,填字母:A.被项目1录取/B.被项目2录取/C.未被录取)。
(2)定义如下sel(a,s,stf)函数,参数a表示某项目已拟录取的员工,参数s表示该项目的员工匹配度,参数stf表示当前待录取员工.员工编号“A”~“Z”用0~25表示。
def sel(a,s,stf):
　　idx=0
　　for j in range(1,len(a)):
　　　　if s[a[j]]　　　　　　idx=j
　　if s[a[idx]]　　　　return idx
　　else:
　　　　return-1
调用sel函数,若a值为[2,3],s值为[90,80,85,70],stf值为1,则函数返回的结果为　　　　。(单选,填字母:A.-1/B.0/C.1/D.2)
(3)实现录取过程的部分Python程序如下,请在划线处填入合适的代码。
#读取项目对员工的匹配度分值存储到列表scores,如[[71,82,93],...];读取员工的志愿顺序存储到列表pstf,如[[3,2,1],...]。读取项目人数上限值存储到cap.代码略.
m n=len(scores),len(pstf)　　#m个项目,n位员工(n≤26)
cur=[0]*n
adm=[[]for i in range(m)]　　　　#生成包含m个空列表的列表
waitlst=[I for i in range(n+1)]　　#生成从0到n的整数列表
head,tail=0,n
while ①　　　　　　　　:
　　stf=waitlst[head]
　　head=(head+1)%(n+1)
　　for i in range(cur[stf],m):
　　　　p=pstf[stf][i]-1
　　　　if ②　　　　　　　　:
　　　　　　adm[p].append(stf)　　#为adm[p]追加一个元素stf
　　　　　　break
　　　　else:
　　　　　　ret=sel(adm[p],scores[p],stf)
　　　　　　if ret!=-1:
　　　　　　　　waitlst[tail]=adm[p][ret]
　　　　　　　　tail=(tail+1)%(n+1)
　　　　　　　　③　　　　　　　
　　　　　　　　break
　　cur[stf]=i+1
for i in range(len(adm)):
　　print("项目"+str(i+1)+"录取的员工:",end="")
　　for j in adm[i]:
　　　　print(chr(j+ord("A")),end="")
　　print()
2.在数据压缩前,对数据进行预处理可以在一定程度上提高压缩效率。以下模拟对长度为n的字符串data(由小写字母组成)进行预处理,步骤如下:
步骤1:将“$”字符添加到字符串data末尾得到新字符串;
步骤2:将新字符串循环右移1位,重复n次后,共得到n+1个循环字符串;
步骤3:将步骤2得到的所有字符串进行升序排序(“$”的ASCII码比英文字母都小);
步骤4:取排序后每个字符串的最后一个字符拼接,得到字符串datas。
如字符串data="abcbc",经过变换后得到datas="c$cabb",变换过程如图所示。
编写Python程序,将变换后的字符串datas还原为data。
(1)若变换后datas的结果为“abc$”,则变换前的字符串data为　　　　。
(2)定义sortd(datas)函数如下:
def sortd(datas):
　　k=[i for i in range(len(datas))]
　　for i in range(len(datas)):
　　　　for j in range(len(datas)-1-i):
　　　　　　if datas[k[j]]>datas[k[j+1]]:
　　　　　　　　k[j],k[j+1]=k[j+1],k[j]
　　return k
若datas为"abc$",调用sortd(datas)后,函数的返回值为[　　　　]。
(3)实现“还原”功能的部分Python程序如下,请在划线处填入合适的代码。
datas=input("输入变换后的字符串datas:")
k=sortd(datas)
link=[]
for i in range(len(datas)):
　　link.append([datas[i],①　　　　　　])
head=②　　　　　
ans=""
q=link[head][1]
while ③　　　　　　:
　　ans+=link[q][0]
　　q=link[q][1]
print("还原的结果为:",ans)
3.小阳的创意工坊,每天都会接到很多订单,且每个订单花费一个单位时间。其中order列表中存储每个订单的截止时间和利润。假设他的工作是从0时刻开始算,订单能在截止时间内(包括截止时间)完成,就会获得利润。他可以选择完成当前时间之后的任意一个订单,过了截止时间的订单就会自动取消。
(1)为了获得较高利润,小阳想到按时间优先的方式来完成订单。为此定义tsort(lst)函数,其中参数lst的每个元素包括截止时间和利润。函数的功能是根据订单截止时间升序排列。
def tsort(lst):
　　n=len(lst)
　　for i in range(n-1):
　　　　for j in range(n-i-1):
　　　　　　if lst[j][0]>lst[j+1][0]:
　　　　　　　　lst[j],lst[j+1]=lst[j+1],lst[j]
　　return lst
调用该函数,若lst=[[2,4],[1,4],[1,2],[3,5],[2,3],[3,6]],虚线框中的程序段执行次数为　　　　。
(2)小阳发现按时间优先设计的算法,获得的利润并不是最大的。在截止时间进行排序后的订单基础上对算法重新设计:依次对每个订单进行处理,确保每个截止时间要完成的订单利润为当前订单队列和所有未超时订单中利润最高。部分python程序段如下,
请在划线处填入合适的代码。
order=[[2,5],[1,4],[1,3],[3,1],[3,2],[2,6]];n=len(order)
ans=0　#ans存放最大利润之和
que=[[] for i in range(n)]　#利润优先订单队列
head=tail=0
order=tsort(order)
def enque(tmp,tail,head):　#数组模拟优先队列入队
　　p=tail
　　que[tail]=tmp
　　tail+=1
　　for i in range(tail-1,head,-1):
　　　　if que[i-1][1]>tmp[1]:
　　　　　　que[i]=que[i-1]
　　　　　　①　　　　　
　　que[p]=tmp
　　return tail
for i in range(n):
　　if ②　　　　　　:
　　　　tail=enque(order[i],tail,head)
　　　　ans+=order[i][1]
　　else:
　　　　if order[i][1]>que[head][1]:
　　　　　　③　　　　　
　　　　　　head+=1
　　　　　　tail=enque(order[i],tail,head)
　　　　　　ans+=order[i][1]
print("利润最大为"+str(ans))
(3)小阳接到订单 order=[[2,5],[1,4],[1,3],[3,1],[3,2],[2,6]],输出结果为　　　　。
4.某工厂生产的产品包含n个(编号为0~n-1)组件,其组装可由多名工人共同协助完成。组装时每个组件都不可遗漏并能按序完成,有些组件存在前置组件(以下简称“前置”),即安装有先后顺序。例如,某产品有6个组件,如图a所示,组件3的前置是组件1和组件2,即安装组件3需要在组件1和组件2完成之后。若0~5号组件的组装所需单位时间分别为2,5,2,4,3,5,则在工人数量不限的情况下,所有组件安装完成最短需要14个单位时间。
为了梳理产品组件的组装顺序,并计算所有组件安装完成所需的最短时间,编写程序模拟组装过程:先同时组装前置总数为0的组件,完成后更新每个组件的前置总数,再重复以上步骤,直至所有组件安装完毕,程序运行结果如图b所示,请回答下列问题:
编号为0~5的组件组装所需单位时间分别为:[2,5,2,4,3,5] 组件组装顺序:[0,1,2,3,4,5] 安装完成所需最短时间:14
图b
(1)图a所示产品的1号组件组装时长若缩短为3个单位时间,其它时间保持不变,则所有组件安装完成所需最短时间为　　　　个单位时间。
(2)定义如下cal(a,n)函数,参数a列表的每个元素包含两项,a[i][1]是组件编号,a[i][0]是a[i][1]的前置编号,例如a中某个元素值为[2,3],表示组件2是组件3的前置。该函数的返回值是列表s和列表pre,其中s记录所有组件的相互关系,pre[i]记录初始情况下组件i的前置总数。
def cal(a,n):
　　pre=[0]*n
　　s=[[0 for i in range(n)] for j in range(n)]　#创建n×n的二维数组s,元素初始值为0
　　for i in range(len(a)):
　　　　x,y=a[i][0],a[i][1]
　　　　s[x][y]=1
　　　　pre[y]=　　　　　
　　return pre,s
(3)定义如下proc(n,s,pre)函数,该函数的返回值是列表v,v[i]代表从开始到组件i完成组装所需的最短时间。请在划线处填入合适的代码。
def proc(n,s,pre):
　　head=tail=0
　　que=[0]*n
　　for i in range(n):
　　　　if pre[i]==0:
　　　　　　que[tail]=i
　　　　　　tail+=1
　　while head　　　　x=que[head]
　　　　head+=1
　　　　for i in range(n):
　　　　　　if s[x][i]==1:
　　　　　　　　pre[i]-=1
　　　　　　　　if pre[i]==0:
　　　　　　　　　　que[tail]=i
　　　　　　　　　　tail+=1
　　　　　　　　v[i]=max(v[i],①　　　　　　)
　　return v
#组装编号0~n-1的单个组件所需时间存入t列表,组件前置关系存入a列表,如图a所需时间t=[2,5,2,4,3,5];a=[[0,2],[2,3],[1,3],[3,5],[3,4],[4,5]]
n=len(t);v=t[:]
pre,s=cal(a,n)
v=proc(n,s,pre)
data=[0]*n
result=[i for i in range(n)]　#创建列表result=[0,1,2,……,n-1]
for i in range(n):
　　data[i]=v[i]-t[i]　#data[i]表示组件i开始安装时间
for i in range(n-1):　#按组件开始安装时间升序排序,开始安装时间相同时按组件序号升序
　　for j in range(n-1-i):
　　　　if data[result[j]]>data[result[j+1]]:
　　　　　　②　　　　　
print("组件组装顺序:",result,",安装完成所需最短时间:",max(v))
(4)以下选项与题(3)加框处代码功能相同的是　　　　(多选,填字母)。
A.head!=tail B.headC.tail<=n D.len(que)> 0
5.有一个内存大小为n的内存条a,起始为空,每次进来一个任务它都会占用空余的最前面的一段或多段内存,删除任务则解放它占用的所有内存部分。
例如:n=100
进内存S01 20 S01占用的内存为[0,20),a存储为[0,20)
进内存S02 10 S02占用的内存为[20,30),a存储为[0,20),[20,30)
进内存S03 30 S03占用的内存为[30,60),a存储为[0,20),[20,30),[30,60)
删除S02 内存[20,30)清空,a存储为[0,20),[30,60)
进内存S04 20 S04占用的内存为[20,30),[60,70),a存储为[0,20),[20,30),[30,60),[60,70)
(1)已知内存大小为100的占用情况为[0,10),[20,25),[30,45),[70,75)。现有任务:进内存S02130,所占用的内存区间为　　　　。
(2)在划线处填上合适代码。
a=[]　#保存元素存储情况
dict1={};tmp=0　#将任务名按照顺序对应 0,1,2,3…以便列表作为元素下标
ans=[]
def add(name,v):
　　start=0;i=0
　　while i　　　　now=a[i][0]-start
　　　　if now>=v:
　　　　　　a.insert(i,[start,start+v])
　　　　　　ans[name].append(start)
　　　　　　i+=1
　　　　　　break
　　　　elif ①　　　　　　:
　　　　　　a.insert(i,[start,a[i][0]])
　　　　　　ans[name].append(start)
　　　　　　v-=now
　　　　　　i+=1
　　　　②　　　　　
　　　　i+=1
def find(key):
　　L=0;R=len(a)-1
　　while L<=R:
　　　　m=(L+R)//2
　　　　if a[m][0]==key:
　　　　　　③　　　　　
　　　　elif a[m][0]　　　　　　L=m+1
　　　　else:
　　　　　　R=m-1
def delete(name):
　　for i in range(len(ans[name])):
　　　　t=④　　　　　
　　　　a.pop(t)
n=int(input())
a.append([n+1,n+1])
while True:
　　T=input().split()
　　if T[0]=="进内存":　#T[1]表示占用的任务名,T[2]表示任务内存大小
　　　　dict1[T[1]]=tmp
　　　　tmp+=1
　　　　ans.append([])
　　　　add(dict1[T[1]],int(T[2]))
　　else:　#T[1]表示删除的任务名
　　　　delete(dict1[T[1]])
　　print(a)

展开更多......

收起↑