资源简介

9.1　自定义函数功能实现及调试
学习目标　
1.掌握自定义函数的构造和调用方法。
2.掌握模块的导入方法和常用函数的应用。
(2024年6月浙江选考)某数据序列data中的元素均为小于127的正整数。现在要对data进行加密,处理过程分“变换”和“重排”两步。“变换”处理方法是用指定的n组序列R_0、R_1…R_(n-1)依次对data进行变换。利用Ri对data进行变换的过程是:在data中查找所有与Ri相同的子序列,将找到的每个子序列中的元素值加上Ri的长度值Li,并在各子序列前插入一个标记元素(值为127+Li),这些子序列及标记元素不再参与后续的变换。
如data为[3,5,1,6,3,8,7,5,1,8,7],指定的两组序列为[5,1]、[3,8,7],“变换”处理后的data为[3,129,7,3,6,130,6,11,10,129,7,3,8,7]。
对data“重排”处理通过给定的shuff函数实现。请回答下列问题:
(1)若data为[3,5,1,6,3,8,7,5,1,8,7],指定的两组序列为[5,1]、[8,7],经过“变换”处理后,data中插入的标记元素个数为　　　　。
(2)“重排”处理的shuff函数如下:
def shuff(data,c):　#根据列表c对列表data进行重排
　　#若列表data的长度不是列表c长度的整数倍,则用0补足,代码略
　　m=len(c);s=[0]*m
　　k=0
　　while k　　　　for i in range(m):
　　　　　　s[i]=data[k+i]
　　　　for i in range(m):
　　　　　　data[k+i]=s[c[i]]
　　　　k+=m
若data为[3,129,7,3,130,6,11,10],c为[1,3,0,2],调用shuff(data,c)后,data的最后一个元素值为　　　　。
　　选考真题的第15题往往会体现模块化的程序设计算法思想,突出表现是将某些功能封装在特定的自定义函数中,其第二小题就是典型的代表。往往要考查学生对程序的阅读理解能力,如程序运行的结果,程序运行后某个变量的值,修改语句后某些功能未能实现,能测试出这些问题的数据是什么。本节课需要学生理解自定义函数的参数传递、返回的值以及调用的方法。
例1 有n个作业要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都必须先在M1上加工完成后,才能在M2上加工。要求确定这n个作业的最优加工顺序,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的最少时间。某批次作业数据如下表所示:
作业编号 M1上加工的时间t1 M2上加工的时间t2
1 5 6
2 12 2
3 4 14
4 8 7
加工方法为:每个作业取t1和t2的较小值,按此最小值进行升序排序,得到作业编号依次为2,3,1,4。若t1<=t2,则在M1上优先加工,且优先加工t1时间短的作业,得出前2个加工的作业为作业3和作业1;若t1>t2,则在M1上优先加工t2时间长的作业,得出后2个加工的作业为作业4和作业2。最终所有作业的加工顺序为3,1,4,2。
(1)如表所示的作业数据,加工完成所有作业的最少时间为　　　　。
(2)定义如下自定义函数bubble_sort(lst),参数lst的每个元素由作业编号、M1上加工的时间t1、M2上加工的时间t2三个数据项组成。函数的功能是安排合理的加工顺序,使得作业尽早完成。
def bubble_sort(lst):
　　n=len(lst)
　　for i in range(n-1):
　　　　for j in range(n-1,i,-1):
　　　　　　a=min(lst[j][1],lst[j][2])
　　　　　　b=min(lst[j-1][1],lst[j-1][2])
　　　　　　if a　　　　　　　 lst[j],lst[j-1]=lst[j-1],lst[j]
　　order=[0]*n
　　i=0;j=n-1
　　for k in range(n):
　　　　if lst[i][1]<=lst[j][2]:
　　　　　　order[i]=lst[k][0]
　　　　　　i+=1
　　　　else:
　　　　　　order[j]=lst[k][0]
　　　　　　j-=1
　　return order
①调用该函数,若lst为[[1,5,6],[2,12,2],[3,4,14],[4,8,7]],则加框处的代码执行的次数是　　　　。
②程序中划线处代码有错,请改正。
变式1 为提升交通信号灯的巡查管理效率,某交通管理局为一条道路制定了一套智能信号灯巡查优先级编排方案。每个信号灯都有其坐标位置和权重值,权重值越大越重要。巡查编排方案如下:
①先选取权重值最大的n个信号灯作为主信号灯,记入巡查列表。
②然后在每个主信号灯的左右坐标位置距离k范围内,寻找权重值最大的且尚未在巡查列表中的m个信号灯作为辅助信号灯记入巡查列表。如主信号灯坐标位置是10,k=3时,能被选取的辅助信号灯的坐标位置值为“7、8、9、11、12、13”。若能被选取的辅助信号灯数量不足m个,则全部选取。请回答下列问题:
(1)每个信号灯的数据格式为[坐标位置,权重],若道路信号灯数据是[[1,10],[3,20],[5,15],[7,30],[9,25],[11,5],[13,35],[15,40],[17,22]],n、k、m分别为2、4和3时,则被选择记入巡查列表的信号灯总数是　　　　。
(2)定义如下findn(data,n,usedlst)函数。data数组中存储着信号灯数据,函数功能是从data数组中选取权重最大的n个(按索引升序排列)主信号灯,只能选取那些索引不在usedlst中的信号灯。
def findn(data,n,usedlst):
　　ls=[]
　　for i in range(len(data)):
　　　　if i not in usedlst:
　　　　　　ls.append(i)
　　if len(ls)<=n:return ls
　　for i in range(n):
　　　　for j in range(len(ls)-i):
　　　　　　if data[ls[j]][1]>data[ls[j-1]][1]:
　　　　　　　　ls[j],ls[j-1]=ls[j-1],ls[j]
　　　　j=i
　　　　while j>0 and ls[j]　　　　　　ls[j],ls[j-1]=ls[j-1],ls[j]
　　　　　　j-=1
　　return ls[:n]
①调用findtn函数,若data为[[1,10],[3,20],[5,15],[7,30],[9,25],[11,5],[13,35],[15,40],[17,42]],n=4,usedlst为[3,4,5],则函数返回值是　　　　。
②程序中加框处代码有错,请改正。
例2 某计算机中,CPU通过主存单元编号访问数据。当CPU访问的主存单元数据在Cache(高速缓存)中时,访问结果为命中,无需从主存调入数据;当CPU访问的主存单元数据不在Cache中时,访问结果为缺失,需要从主存中将被访问的主存单元数据调入Cache,若Cache容量已满,则替换在Cache中且下次最晚访问数据。如某Cache的容量为3,且其中已有编号为10、20和30的主存单元数据,CPU依次访问的主存单元编号为“10、40、50、40、30、10、30”。第1次访问编号10,命中;第2次访问编号40,当前Cache中容量已满,编号20不再出现,编号40替换编号20。第3次访问编号50,内存中的3个单元数据中,编号10最后出现,编号50替换编号10,依此类推,共替换3次。
(1)若Cache容量为2,且其中已有编号为1和2的主存单元数据,CPU对编号为“4,2,3,2,3,1”的主存单元数据依次进行访问,此过程中替换的次数为　　　　。
(2)定义getpos(info)函数,参数info列表元素表示CPU依次访问主存单元数据的编号。
def getpos(info):
　　last=[-1] *1024;nxt=[len(info)]*1024
　　for i in range(len(info)):
　　　　k=info[i]
　　　　if last[k]!=-1:
　　　　　　nxt[last[k]]=i
　　　　last[k]=i
　　return nxt[:len(info)]
若info为[4,2,3,2,3,1],执行语句nxt=getpos(info)后,则返回值为　　　　。
变式2 某大项目由m个小项目(编号为1~m)构成,n个员工(编号为1~n)参与该大项目。大项目完成后员工需汇报,汇报员工参与的项目须涵盖所有小项目,每个员工想知道自己至少要和其他哪些员工合作才可以完成大项目汇报。每个员工参与小项目情况用[a,b,c]表示,若a≤b,则表示c员工参与了[a,b]区间的小项目,若a>b,则表示c员工参与了[a,m]和[1,b]区间的小项目(一个员工参与的项目区间不会被另一员工参与的项目区间包含)。如4人参与8个小项目的情况为[3,5,1],[8,3,2],[7,1,3],[5,7,4],则1号员工至少需要和2号、4号员工合作完成大项目汇报,3号员工则需和所有员工合作才能完成大项目的汇报。编写程序,求每个员工为完成大项目汇报所需的最少员工编号组合。
(1)若5人参与完成10个小项目的情况为[2,4,1],[6,10,2],[5,9,3],[8,3,4],[3,7,5],则2号员工至少需要和　　　　(填员工编号)合作才能完成大项目的汇报。
(2)定义如下GetNext函数,参数列表x由n个元素组成,满足x[i][0]≤x[i][1](0≤idef GetNext(n,x):
　　j=0;gn=[]
　　for i in range(n):
　　　　while j=x[j][0]:
　　　　　　j=j+1
　　　　gn.append(j-1)
　　return gn
若x为[[2,4,1],[3,7,5],[4,8,2],[6,9,3],[8,13,6],[10,15,4]],n为6,调用GetNext(n,x)后,则gn[1]的值为　　　　。
1.将四字成语进行分类。例如,“心心相印”属于AABC类型,“喜气洋洋”属于ABCC类型。编写Python程序实现从文本文件中读取所有四字成语,进行分类并输出,
(1)若收集了3个四字成语为“百花齐放”“同心同德”“一心一意”,则一共出现　　　　(填数字)种类型。
(2)定义如下ctype(s)函数,参数s是一个字符串类型的四字成语。函数的功能是返回四字成语s的类型,例如,ctype("一动不动"),返回值是"ABCB"。
def ctype(s):
　　ret="A"
　　k=65　#字母"A"的ASCII码值为65
　　for i in range(1,4):
　　　　for j in range(i):
　　　　　　if s[i]==s[j]:
　　　　　　　　ret+=ret[j]
　　　　　　　　break
　　　　if s[i]!=s[j]:
　　　　　　k+=1
　　　　　　ret+=chr(k)
　　return ret
①调用ctype(s)函数,若变量s为“熙熙攘攘”,则函数运行结束时,变量k的值是　　　　。
②若将加框处代码“ret[j]”误写成“chr(k)”,则导致某些情况下无法得到符合函数功能的结果。调用ctype(s)函数,下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.s="炯炯有神" B.s="人才济济"
C.s="同心同德" D.s="博学多才"
2.根据社会学研究表明,人们都喜欢找和自己身高相近的人做朋友。现在有n名身高各不相同的同学依次走入教室,调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时,这名同学会更想和高的那个人做朋友,对于第1个走入教室的同学不做预测,后面进入教室的人,选择和他身高差值最小的人做朋友,若有多个最小差值,则选择身高最高的人做朋友。若有6人依次进入教室,选择的朋友如下表所示。
序号 1 2 3 4 5 6
身高 110 120 190 140 180 185
朋友序号 不预测 1 2 2 3 3
(1)若教室中再走入第7人,身高为175,他将选择第　　　　人做朋友。
(2)定义如下bsort(a)函数,参数a列表为依次走入的同学身高。函数的功能是返回数组a中数据从小到大的序号。
def bsort(a):
　　n=len(a)
　　b=[i for i in range(n)]
　　for i in range(n-1):
　　　　flag=False
　　　　for j in range(n-i-1):
　　　　　　if a[b[j]]>a[b[j+1]]:
　　　　　　　　b[j],b[j+1]=b[j+1],b[j]
　　　　　　　　flag=True
　　　　if flag==False: break
　　return b
若列表a的值为[110,120,190,140,180,185],调用bsort(a)函数,①加框处的语句执行次数为　　　　。②函数的返回值是　　　　　　。
3.某评选活动有n个评委,需从m个品牌中评选一个最佳品牌,评选采取多轮淘汰制,每轮投票后得票最少的品牌被淘汰(得票并列最少的品牌一起淘汰)。如此循环淘汰,若最后只剩下一个品牌,即告评选成功,输出当选品牌编号。如果在某轮投票中,当时未被淘汰的所有候选品牌(大于等于两个品牌)得票数都相同,即告评选失败。
每位评委根据预设的态度序列投票。如某评委的态度序列为:3、1、2,则表示该评委优先投3号,当3号被淘汰时投1号,仅剩2号时才投2号的票。选票的序列中可以用0表示弃权,如某评委的评选态度序列为3、0,则表示该评委优先投3号,当3号被淘汰时(弃权)。
如有5个评委,3个品牌,评委的态度列表为[[3,1,0],[2,1,3],[1,0],[1,3,0],[2,3,1]],评选过程如下:
轮次 评委1 评委2 评委3 评委4 评委5 评选结果
第1轮 投3 投2 投1 投1 投2 1得2票,2得3票,3得1票,3淘汰
第2轮 投1 投2 投1 投1 投2 1得3票,2得2票,2淘汰,最佳品牌为1
现编写Python程序,模拟投票过程。请回答以下问题。
(1)若有5个评委,3个品牌,评委评选态度序列为lst=[[3,1,2],[3,1,0],[1,3,2],[1,2,3],[2,1,0]],则告评选　　　　(填:成功/失败)。
(2)定义如下vote(lst,m)函数,参数m表示品牌数量,lst列表每个元素有m个0至m的数据项,表示评委的投票态度。函数功能是评选并返回一个最佳品牌,若评选失败,则返回-1。
def vote(lst,m):
　　ans=m;f=[0]*(m+1)
　　while ans>1:
　　　　cnt=[0]*(m+1)
　　　　for i in range(len(lst)):
　　　　　　for x in lst[i]:
　　　　　　　　if x!=0 and f[x]!=-1:
　　　　　　　　　　cnt[x]+=1
　　　　　　　　　　break
　　　　
　　　　for i in range(1,m+1):
　　　　　　if cnt[i]==minc:　#②划线处语句
　　　　　　　　ans-=1
　　　　　　　　f[i]=-1
　　for i in range(1,m+1):
　　　　if f[i]!=-1:
　　　　　　return i
　　return -1
①若将加框处代码修改为如下代码:
minc=cnt[1]
for i in range(2,m+1):
　　if f[i]!=-1 and minc>cnt[i]:
　　　　minc=cnt[i]
　　minc=cnt[1]
会导致某些情况下无法得到符合函数功能的结果。调用vote(lst,m)函数,m的值均为3,下列4组数据中能测试出这一问题的lst值是　　　　(单选,填字母)。
A.[[3,2,1],[3,1,0],[3,1,0],[3,2,0],[3,1,0]]
B.[[3,2,1],[3,1,0]]
C.[[2,0,0],[2,0,0],[1,0,0],[1,0,0]]
D.[[3,0,0],[2,1,3],[2,1,0]]
②程序中划线处代码有错,请改正。
4.对某数据序列data中的元素进行“掺杂”加密,按照data中元素的个数,随机分割成若干段,如data中有9个元素,若数据分割表为[4,2,3],则表示将data分割为三组,第一组4个数据、第二组2个数据、第三组3个数据,分别在每组数据的后面插入1个随机的杂质数据。请回答下列问题:
(1)若data中有7个元素,数据分割表为[4,3],经过“掺杂”处理后,则插入杂质数据的个数为　　　　(填数字)个。
(2)定义如下insert(data)函数,函数功能将存储在data中的一组数分割成若干段,每段的后面插入一个[128,254]之间的随机数,返回插入后的数据以及原始数据中每段的个数(不含插入的数据)。实现加密功能的部分Python程序如下,请在划线处填入合适的代码。
def insert(data):
　　seg=[];x=0;n=len(data)
　　while x　　　　y=random.randint(2,6)
　　　　seg.append(y)
　　　　x+=y
　　seg[-1]=①　　　　　
　　res=[0]*(n+len(seg))
　　x,y=0,0
　　for i in seg:
　　　　for j in range(i):
　　　　　　②　　　　　
　　　　　　x+=1;y+=1
　　　　res[x]=random.randint(128,254)
　　　　③　　　　　
　　return res,seg
5.某技能培训需要修完n(编号为0~n-1)门课程,每门课程可以有若干个前置课程(先完成前置课程学习才能学习本课程),但最多只能作为一门课程的前置课程。若n=5,如图所示课程间的依赖关系,完成课程4必须先完成课程0与课程5,完成课程3必须先完成课程1与课程4。可行的一种课程顺序可以为:0,5,4,1,3,2。
(1)若将图中加框处中的“3”改为“4”,请写出其中一组可行的课程顺序:　　　　　　。
(2)定义judge(n,kc)函数,参数n表示课程的数量,参数kc存储各门课程之间依赖关系,每个元素有2个数据项,前者是后者的前置课程,如kc=[[0,1],[1,2],[2,0]]。函数的功能检测是否有可行的课程顺序。
def judge(n,kc):
　　link=[-1]*n
　　for i in range(len(kc)):
　　　　link[kc[i][0]]=kc[i][1]
　　for i in range(len(kc)):
　　　　f=[0]*n;p=i
　　　　while p!=-1:
　　　　　　if f[p]==0:
　　　　　　　　f[p]+=1
　　　　　　else:
　　　　　　　　return False
　　　　　　p=link[p]
　　return True
若n的值为4,kc的值为[[0,2],[2,3],[3,1],[1,2]],则加框处语句运行的次数是　　　　。函数的返回值为　　　　。
6.某机构采购了n类(编号1~n)紧急救援食品,储存条件分冷藏和常温。每个货柜的最大容量为m袋,货柜编号从1开始。按容量从大到小依次存放,若当前需存放食品容量为k,存放的方法:在已存放食品的货柜内寻找空余空间不少于k的货柜,且满足已存食品与当前食品的储存条件相同(冷藏或常温)。若存在多个这样的货柜,则挑选空余空间最小的来存放,若不存在,则存放于新的货柜。
(1)设m为100,n为4,每类食品容量依次为10,90,85,15,其中类别为3的食品需冷藏,其余为常温。则类别4所放置的货柜编号为　　　　。
(2)定义getroom(a,key,f)函数,参数a中每个元素由货柜的空位数和储存条件(0常温,1冷藏)两个数据项构成。参数key表示需要存储食品的数量,参数f表示储存条件。函数的功能是为各类剩余食品寻找储存的货柜编号。
def getroom(a,key,f):
　　flag=True
　　k,i=0,0
　　while i　　　　if a[i][0]>=key and a[i][1]==f:
　　　　　　if flag or a[i][0]<=a[k][0]:
　　　　　　　　k=i;flag=False
　　　　i+=1
　　if flag==False:
　　　　return k
　　return len(a)
若a为[[0,0],[25,1],[30,0],[20,1],[15,0]]。①key为15,f为1,调用getroom(a,key,f)后,返回的值为　　　　。②key为35,f为0,调用getroom(a,key,f)后,返回的值为　　　　。
1.小海对括号串问题非常感兴趣,他设计了一个编辑括号串的程序。程序支持三个操作:
①L:将光标左移一格;
②R:将光标右移一格;
③D:删除光标处的括号到与它对应的括号之间的所有括号(包括当前光标处的括号和其对应的括号)。在删除之后,光标会跳到它右边的没有被删除的最左边的括号处;若右边没有括号了,则光标会跳到它左边的没有被删除的最右边的括号处。图a即为两个D操作的例子。
(1)若括号串为"(()(()))",当前光标所在位置为2(从左往右数第二个括号处),则进行一次D操作后,括号串变为　　　　。
(2)定义如下match(bracket)函数,参数bracket是由左右小括号组成的字符串。函数功能是检测 bracket中的左右括号是否匹配,若匹配,则函数返回True;否则函数返回False。
def match(bracket):
　　stack=['']*len(bracket);top=-1
　　flag=True
　　for c in bracket:
　　　　if c=='(':
　　　　　　top=top+1;stack[top]=c
　　　　elif c==')':
　　　　　　if top!=-1:
　　　　　　　　top-=1
　　　　　　else:
　　　　　　　　flag=False;break
　　if top!=-1 or not flag:
　　　　return False
　　else:
　　　　return True
①调用match(bracket)函数,若bracket为“()((()))”,则程序执行过程中,变量top的最大值为　　　　。
②若函数中加框处的条件“top!=-1 or not flag”误写为“not flag”,会导致某些情况下无法得到符合函数功能的结果。调用match(bracket)函数,下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.bracket="()()"
B.bracket=")()"
C.bracket=")()("
D.bracket="(()"
2.小华开发了一个简单的医院门诊预约管理系统,用于模拟病人的预约和取消操作。系统输入格式如下:若输入"预约"开头,后面两个数字为预约开始时间和持续时长。若能找到符合病人预约要求的空闲时间段则预约成功,系统按照预约顺序分配病人编号,其中病人起始编号为1。若输入"取消"加病人编号,系统会查找指定编号并释放相应的预约时间段。
假设该门诊系统每天可预约的时间范围为0到99,则图a门诊系统的时间段分配情况如图b所示,每行表示一个时间段的预约情况。
请回答下列问题:
(1)若门诊的可预约时间为0~45,在执行了图a的前4行输入后,门诊系统分配的时间段为:0~9:空闲,10~29:空闲,30~39:病人2,　　　　。(请完善最后一段时间段门诊预约情况)
(2)定义如下book(sch,st,time,id)函数,参数sch列表用于存储每个时间段的预约情况,每个元素有病人序号,是否预约,起始时间,结束时间共4个数据项。病人序号为0表示该时间段空闲。参数st和time表示预约开始时间和持续时长,id表示病人的序号。函数的功能是将病人分配到指定的时间段。实现上述功能的程序如下,请在划线处填入合适的代码。
def book(sch,st,time,id):
　　①　　　　　
　　i=0
　　while i　　　　block=sch[i]
　　　　if not block[1] and block[2]<=st and block[3]>=ed:
　　　　　　sch[i]=[id,True,st,ed]
　　　　　　if block[2]　　　　　　　　sch=sch[:i]+[[0,False,block[2],st-1]]+sch[i:]
　　　　　　　　②　　　　　
　　　　　　if ③　　　　　　:
　　　　　　　　sch=sch[:i+1]+[[0,False,ed+1,block[3]]]+sch[i+1:]
　　　　　　return sch,id
　　　　i+=1
　　return sch,-1
3.某机器在上午8点到12点的时间段可以安排加工产品。按以下规则选择部分产品加工:先选择所有产品中加工结束时间最早的产品(若有多个产品的结束时间相同,则优先选择加工时长少的产品),然后在剩余产品中选择时间不冲突的结束时间最早的产品进行加工,依次类推……直至选择完毕。编写一个Python程序,实现以下功能:读取n个产品的编号、预计到达时间和所需加工时长,输出选择加工的产品编号、加工起始时间和结束时间。
(1)有6个产品,产品编号、预计到达时间和所需加工时长(分钟)如下:
[[1,"08:00",105],[2,"08:30",60],[3,"09:35",105],[4,"10:30",90],[5,"10:00",35],[6,"09:40",40]],则选择加工的第2个产品的编号为　　　　(填数字)。
(2)实现上述功能的Python程序如下,请在划线处填入合适代码。
def convert1(t):
　　#把时间格式 t 转化为整数,如"08:30"转化为510。代码略
def convert2(t):
　　#把整数t 转换为时间格式,如 510 转化为"08:30"。代码略
'''
读取n个产品的数据存入列表a[0]至 a[n-1]中,a[i]包含3个数据项,a[i][0]、a[i][1]和a[i][2]分别存放产品编号、预计到达时间和所需时长,代码略
'''
for i in range(n):
　　st=convert1(a[i][1])
　　a[i].append(st)
　　ed=st+a[i][2]
　　a[i].append(ed)
flag=[False]*n
for i in range(n-1):
　　①　　　　　
　　for j in range(i+1,n):
　　　　if a[j][4]　　　　　　k=j
　　　　a[i],a[k]=a[k],a[i]
st=convert1("08:00")
ed=convert1("12:00")
for i in range(n):
　　if a[i][3]>=st and a[i][4]<=ed:
　　　　flag[i]=True
　　　　②　　　　　
print("产品编号","起始时间","结束时间")
for i in range(n):
　　if ③　　　　　　:
　　　　print(a[i][0],a[i][1],convert2(a[i][4]))
4.同源词指由相同字母(全部为小写字母)重排列形成的字符串,包括相同的字符串。当给定两个字符串s和p(s长度大于p长度),找到s中所有是p的同源词的子串,按出现的顺序输出这些子串的起始索引。如s的值为"cbaebacdbabc",p的值为"abc",则同源词的起点为[0,4,9]。
(1)若s的值为"cbaebacdbabc",p的值为"ab",则同源词的起点为　　　　。
(2)实现该功能的程序代码如下:
def judge(s,p):
　　scount=[0]*26;pcount=[0]*26
　　m=len(s);n=len(p);ans=[]
　　for i in range(n):
　　　　scount[ord(s[i])-ord("a")]+=1
　　　　pcount[ord(p[i])-ord("a")]+=1
　　if scount==pcount:ans.append(0)
　　for i in range(m):　#②题改错
　　　　scount[ord(s[i])-ord("a")]-=1
　　　　scount[ord(s[i+n])-ord("a")]+=1
　　　　if scount==pcount:
　　　　　　ans.append(i+1)
　　return ans
①若删除函数中加框处语句,会导致某些情况下无法得到符合函数功能的结果。若s的值为"dbabdccbaeb",调用judge(s,p)函数,下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.p="ab" B.p="cd"
C.p="dbc" D.p="bad"
②程序代码for i in range(m)中,参数m有错,应修改为　　　　。
5.小明研制一种药物,采集了n种原料,现对每种原料先进行放射试验,再进行加热试验的顺序进行精密分析。实验室同一时间最多只能做一个放射试验和一个加热试验,为尽早完成试验,小明将放射试验用时短的尽量排前面,加热试验时间用时短的尽量排后面。例如:有A~E共5种原料,每种原料需要的试验时间如图a所示;最终各原料的试验安排如图b所示。
原料名称 放射试验时间 加热试验时间
A 8 5
B 4 2
C 4 10
D 16 7
E 3 5
图a
试验安排顺序为:E→C→D→A→B→ 结束试验的最早时间:38
图c
编写程序:给定各种原料所需试验的时间,根据上述方法安排试验顺序并计算所有原料完成试验的最早结束时间,输出结果如图c所示。
(1)若将原料E的放射试验时间3修改为13,则结束试验的最早时间为　　　　。
(2)定义如下自定义函数order(task,n),参数task的每个元素由原料名称、放射时间和加热时间3个数据项构成,参数n为原料种类。函数功能是安排合理的试验顺序,使得试验尽早完成。
def order(task,n):
　　f=[False]*n;odr=[-1]*n
　　st=-1;ed=n
　　for i in range(n):
　　　　min=30000　#已知每个试验时间最多不超过30000
　　　　for j in range(n):
　　　　　　if f[j]==False:
　　　　　　　　for k in range(1,3):
　　　　　　　　　　if task[j][k]　　　　　　　　　　　　min=task[j][k]
　　　　　　　　　　　　bestj=j
　　　　　　　　　　　　bestk=k
　　　　f[bestj]=True
　　　　if bestk==1:
　　　　　　st+=1;odr[st]=bestj
　　　　else:
　　　　　　ed-=1;odr[ed]=bestj
　　return odr
若task=[["A",5,2],["B",4,2],["C",1,8]],n=3,请回答下列问题。
①调用该函数后,st和ed的值分别为　　　　,　　　　。
②odr的值为　　　　。
③将虚线框处代码改成for j in range(n-1,-1,-1),　　　　 (单选,填字母:A.会/B.不会)影响原料试验的安排顺序。
6.通配符“*”通常用于模式匹配,例如在文件操作或者搜索时用来代替任意数量的字符,“*.txt”匹配所有txt文件。匹配样例如图所示。
文本内容 key 匹配结果
强化学习 强化 False
神经网络 *神经 False
知识图谱 知*谱 True
深度学习 深度* True
咕噜咕噜 *咕噜 True
(1)现有4个单词:Carper、 Carver、Carpenter、Carrier,能匹配上述单词的最长key是　　　　。
(2)编写自定义函数judge(name,key),参数key中可能包含若干个“*”,函数的功能是判断字符串name是否可以用key来描述。
def judge(name,key):
　　i=j=0
　　flag=False
　　while i　　　　if j　　　　　　i+=1;j+=1
　　　　elif j　　　　　　flag=True
　　　　　　step=0　#记录通配符匹配的字符数量
　　　　　　temp=[i,j]
　　　　　　j+=1　#跳过通配符"*",处理key的下一个字符
　　　　elif flag:
　　　　　　step+=1　#增加通配符匹配的字符数量
　　　　　　i=temp[0]+step　#尝试匹配更多字符
　　　　　　j=temp[1]+1　#重置j到通配符后的位置
　　　　else:
　　　　　　return False
　　if j 　　return True
若name为"causeless",key为"ca*l*s",调用judge(name,key)后,加框处语句step+=1运行的次数为　　　　。
(3)若去除代码if j A."ca*l*" B."a*l*s"
C."c*s*es" C."c*"
7.某车间生产三种不同的产品,不同产品可以同时开始生产,三种产品按照不同的部件顺序完成。如“产品0”生产顺序为“部件1”→“部件0”,即“部件1”完成后才开始“部件0”,即部件1是部件0的前驱部件,每个部件仅有一个前驱部件,如图a所示。每个部件自身又需同编号的一个材料完成才能开始生产,如“部件0”需要“材料0”,“部件1”需要“材料1”……,各种材料按各自的开始生产时刻进行,完成所需时长也有所不同,如图b所示,部件完成所需时长不包括材料生产在内。现编写程序,模拟该生产过程,并计算每个产品的部件完成的时刻。
图a
产品号 部件顺序 材料生产 开始时刻 材料生产 所需时长 部件完成 所需时长
产品0 部件1 3 3 2
部件0 2 2 1
产品1 部件2 3 2 2
部件4 4 1 3
部件5 9 2 2
图b
(1)若有2个产品,“产品0”由“部件1”→“部件0”完成,“产品1”由“部件2”→“部件4”→“部件3”完成,所需材料开始生产时刻和完成所需时长如图b所示。经计算产品0的完成时刻是9,请回答产品1完成的时刻是　　　　　　。
(2)定义pre(arr)函数,参数arr每个元素2个数据项,arr[i][0]表示arr[i][1]的前驱部件,arr[i][1]为-1时表示arr[i][0]为某个产品中最后的部件。函数功能查找每个产品所需的第1个部件。
def pre(arr):
　　i=0;j=i+1;flag=True
　　h=[]
　　while i　　　　if j　　　　　　j+=1
　　　　else:
　　　　　　flag=False
　　　　if j==len(arr) or not flag:
　　　　　　if flag==True:
　　　　　　　　h.append(arr[i][0])
　　　　　　i+=1;j=0
　　　　　　flag=True
　　return h
path=[[0,-1],[1,0],[2,4],[3,-1],[4,3]],调用该函数,pre(path),则加框处代码执行　　　　次,函数的返回值为　　　　。
8.使用某浏览器浏览网页时,在内存中只会保留最近浏览过的k个网页,浏览的网页数达到或超过k个时,会将最近k个网页中访问频率最高的网页存入cache。如k为3,依次访问6个网页如图a所示;当连续浏览网页数达到3个时,将最近3个网页中访问频率最高的网页存入cache,存入情况如图b所示。Cache中改写和保持的过程如图c所示,程序只记录改写的2张网页P1和P5。
(1)由题意可知,若仅将图a中网页名称为p4的访问频率改为5,则cache改写的次数为　　　　。
(2)定义如下find(data,k)函数,参数data每个元素包含网页名称及访问频率共2个数据项,参数k存储内存中存储网页的最大容量。程序功能根据data网页信息及容量k,返回依次改写cache的值。
def find(data,k):
　　result=[]
　　que=[-1]*100
　　head=tail=0
　　for i in range(len(data)):
　　　　if tail>head and que[head]<=i-k:
　　　　　　head+=1
　　　　while tail>head and data[que[tail-1]][1]　　　　　　tail=tail-1
　　　　que[tail]=i
　　　　tail+=1
　　　　if i>=k-1:
　　　　　　result.append(data[que[head]][0])
　　return result
①调用find函数,若data的值依次为["p2",2],["p2",2],["p3",2],["p1",4],["p4",5],k值为3,则while语句中循环体tail=tail-1的执行次数是　　　　。
②程序中加框处代码有错,请改正。9.1　自定义函数功能实现及调试
学习目标　
1.掌握自定义函数的构造和调用方法。
2.掌握模块的导入方法和常用函数的应用。
(2024年6月浙江选考)某数据序列data中的元素均为小于127的正整数。现在要对data进行加密,处理过程分“变换”和“重排”两步。“变换”处理方法是用指定的n组序列R_0、R_1…R_(n-1)依次对data进行变换。利用Ri对data进行变换的过程是:在data中查找所有与Ri相同的子序列,将找到的每个子序列中的元素值加上Ri的长度值Li,并在各子序列前插入一个标记元素(值为127+Li),这些子序列及标记元素不再参与后续的变换。
如data为[3,5,1,6,3,8,7,5,1,8,7],指定的两组序列为[5,1]、[3,8,7],“变换”处理后的data为[3,129,7,3,6,130,6,11,10,129,7,3,8,7]。
对data“重排”处理通过给定的shuff函数实现。请回答下列问题:
(1)若data为[3,5,1,6,3,8,7,5,1,8,7],指定的两组序列为[5,1]、[8,7],经过“变换”处理后,data中插入的标记元素个数为　　　　。
(2)“重排”处理的shuff函数如下:
def shuff(data,c):　#根据列表c对列表data进行重排
　　#若列表data的长度不是列表c长度的整数倍,则用0补足,代码略
　　m=len(c);s=[0]*m
　　k=0
　　while k　　　　for i in range(m):
　　　　　　s[i]=data[k+i]
　　　　for i in range(m):
　　　　　　data[k+i]=s[c[i]]
　　　　k+=m
若data为[3,129,7,3,130,6,11,10],c为[1,3,0,2],调用shuff(data,c)后,data的最后一个元素值为　　　　。
答案　(1)4　(2)11
解析　本题考查索引数组和二维数组的应用。
(1)data中包含2个[5,1]和2个[8,7],因此插入标记元素为4个。(2)shuff函数的功能是以列表c长度进行分组,第1个for循环是将某段的数据读入到s数组中,第2个for是将c列表中索引位置重新进行排列。data共分2组,第2组数据为[130,6,11,10],按c为[1,3,0,2]进行调整,重排后为[6,10,130,11],因此最后一个数据为11。
　　选考真题的第15题往往会体现模块化的程序设计算法思想,突出表现是将某些功能封装在特定的自定义函数中,其第二小题就是典型的代表。往往要考查学生对程序的阅读理解能力,如程序运行的结果,程序运行后某个变量的值,修改语句后某些功能未能实现,能测试出这些问题的数据是什么。本节课需要学生理解自定义函数的参数传递、返回的值以及调用的方法。
例1 有n个作业要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都必须先在M1上加工完成后,才能在M2上加工。要求确定这n个作业的最优加工顺序,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的最少时间。某批次作业数据如下表所示:
作业编号 M1上加工的时间t1 M2上加工的时间t2
1 5 6
2 12 2
3 4 14
4 8 7
加工方法为:每个作业取t1和t2的较小值,按此最小值进行升序排序,得到作业编号依次为2,3,1,4。若t1<=t2,则在M1上优先加工,且优先加工t1时间短的作业,得出前2个加工的作业为作业3和作业1;若t1>t2,则在M1上优先加工t2时间长的作业,得出后2个加工的作业为作业4和作业2。最终所有作业的加工顺序为3,1,4,2。
(1)如表所示的作业数据,加工完成所有作业的最少时间为　　　　。
(2)定义如下自定义函数bubble_sort(lst),参数lst的每个元素由作业编号、M1上加工的时间t1、M2上加工的时间t2三个数据项组成。函数的功能是安排合理的加工顺序,使得作业尽早完成。
def bubble_sort(lst):
　　n=len(lst)
　　for i in range(n-1):
　　　　for j in range(n-1,i,-1):
　　　　　　a=min(lst[j][1],lst[j][2])
　　　　　　b=min(lst[j-1][1],lst[j-1][2])
　　　　　　if a　　　　　　　 lst[j],lst[j-1]=lst[j-1],lst[j]
　　order=[0]*n
　　i=0;j=n-1
　　for k in range(n):
　　　　if lst[i][1]<=lst[j][2]:
　　　　　　order[i]=lst[k][0]
　　　　　　i+=1
　　　　else:
　　　　　　order[j]=lst[k][0]
　　　　　　j-=1
　　return order
①调用该函数,若lst为[[1,5,6],[2,12,2],[3,4,14],[4,8,7]],则加框处的代码执行的次数是　　　　。
②程序中划线处代码有错,请改正。
思维点拨
明考向 本题考查自定义函数应用及数据的排序
精点拨 (1)当M1上完成全部作业加工,时间为4+5+8+12=29,作业3在M1上完成时间为4,在M2上开始时间从4开始,M2上总共时间为4+16+6+7+2=33,因此总共时间为33。(2)变量a和b分别是每个元素第2和第3个数据项中的最小值,排序后的结果是[[2,12,2],[3,4,14],[1,5,6],[4,8,7]],即[1,5,6]和[2,12,2]交换一次,[3,4,14]和[1,5,6]交换一次,共2次。②指针i和j分别指向order的开始和结束位置,依次遍历排序后的kst,若t1<=t2,则在M1上优先加工,且优先加工t1时间(lst[k][1])短的作业编号存入到order[i],因此比较的条件是lst[k][1]<=lst[k][2]
答案　(1)33　(2)①2　②lst[k][1]<=lst[k][2]
变式1 为提升交通信号灯的巡查管理效率,某交通管理局为一条道路制定了一套智能信号灯巡查优先级编排方案。每个信号灯都有其坐标位置和权重值,权重值越大越重要。巡查编排方案如下:
①先选取权重值最大的n个信号灯作为主信号灯,记入巡查列表。
②然后在每个主信号灯的左右坐标位置距离k范围内,寻找权重值最大的且尚未在巡查列表中的m个信号灯作为辅助信号灯记入巡查列表。如主信号灯坐标位置是10,k=3时,能被选取的辅助信号灯的坐标位置值为“7、8、9、11、12、13”。若能被选取的辅助信号灯数量不足m个,则全部选取。请回答下列问题:
(1)每个信号灯的数据格式为[坐标位置,权重],若道路信号灯数据是[[1,10],[3,20],[5,15],[7,30],[9,25],[11,5],[13,35],[15,40],[17,22]],n、k、m分别为2、4和3时,则被选择记入巡查列表的信号灯总数是　　　　。
(2)定义如下findn(data,n,usedlst)函数。data数组中存储着信号灯数据,函数功能是从data数组中选取权重最大的n个(按索引升序排列)主信号灯,只能选取那些索引不在usedlst中的信号灯。
def findn(data,n,usedlst):
　　ls=[]
　　for i in range(len(data)):
　　　　if i not in usedlst:
　　　　　　ls.append(i)
　　if len(ls)<=n:return ls
　　for i in range(n):
　　　　for j in range(len(ls)-i):
　　　　　　if data[ls[j]][1]>data[ls[j-1]][1]:
　　　　　　　　ls[j],ls[j-1]=ls[j-1],ls[j]
　　　　j=i
　　　　while j>0 and ls[j]　　　　　　ls[j],ls[j-1]=ls[j-1],ls[j]
　　　　　　j-=1
　　return ls[:n]
①调用findtn函数,若data为[[1,10],[3,20],[5,15],[7,30],[9,25],[11,5],[13,35],[15,40],[17,42]],n=4,usedlst为[3,4,5],则函数返回值是　　　　。
②程序中加框处代码有错,请改正。
答案　(1)5　(2)①[1,6,7,8]　②len(ls)-1,i,-1
解析　(1)先挑选2个权重最大的为[13,35]和[15,40],接着在这两个数值的索引下标差值为4 以内的5个数据中挑选3个权重值最大的,一共挑选了5个。(2)①第1趟排序结果为[8,0,1,2,6,7],第2趟为[8,7,0,1,2,6],再将前2项升序排序排列。第3趟[7,8,6,0,1,2],再将前3项升序排序得到[6,7,8,0,1,2],第4趟排序结束 ls=[1,7,8,6,0,2],取前4项的结果为[1,6,7,8]。②冒泡方向为从右往左才能保证前n项结果为最大不重复值,故答案为len(ls)-1,i,-1。
例2 某计算机中,CPU通过主存单元编号访问数据。当CPU访问的主存单元数据在Cache(高速缓存)中时,访问结果为命中,无需从主存调入数据;当CPU访问的主存单元数据不在Cache中时,访问结果为缺失,需要从主存中将被访问的主存单元数据调入Cache,若Cache容量已满,则替换在Cache中且下次最晚访问数据。如某Cache的容量为3,且其中已有编号为10、20和30的主存单元数据,CPU依次访问的主存单元编号为“10、40、50、40、30、10、30”。第1次访问编号10,命中;第2次访问编号40,当前Cache中容量已满,编号20不再出现,编号40替换编号20。第3次访问编号50,内存中的3个单元数据中,编号10最后出现,编号50替换编号10,依此类推,共替换3次。
(1)若Cache容量为2,且其中已有编号为1和2的主存单元数据,CPU对编号为“4,2,3,2,3,1”的主存单元数据依次进行访问,此过程中替换的次数为　　　　。
(2)定义getpos(info)函数,参数info列表元素表示CPU依次访问主存单元数据的编号。
def getpos(info):
　　last=[-1] *1024;nxt=[len(info)]*1024
　　for i in range(len(info)):
　　　　k=info[i]
　　　　if last[k]!=-1:
　　　　　　nxt[last[k]]=i
　　　　last[k]=i
　　return nxt[:len(info)]
若info为[4,2,3,2,3,1],执行语句nxt=getpos(info)后,则返回值为　　　　。
思维点拨
明考向 本题考查自定义函数应用以及链表指针的建立
精点拨 (1)访问1,2,3均为缺失,1最后出现,状态更新为[3,2]。2,3命中,访问1缺失,共缺失次数为4。(2)遍历info列表中的每个主存单元编号,用last[k]记录最后一次k出现的位置,next数组用于记录每个主存单元编号下一次被访问的位置。根据info=[1,2,3,2,3,1],得出next值为[5,3,4,6,6,6]
答案　(1)4　(2)[5,3,4,6,6,6]
变式2 某大项目由m个小项目(编号为1~m)构成,n个员工(编号为1~n)参与该大项目。大项目完成后员工需汇报,汇报员工参与的项目须涵盖所有小项目,每个员工想知道自己至少要和其他哪些员工合作才可以完成大项目汇报。每个员工参与小项目情况用[a,b,c]表示,若a≤b,则表示c员工参与了[a,b]区间的小项目,若a>b,则表示c员工参与了[a,m]和[1,b]区间的小项目(一个员工参与的项目区间不会被另一员工参与的项目区间包含)。如4人参与8个小项目的情况为[3,5,1],[8,3,2],[7,1,3],[5,7,4],则1号员工至少需要和2号、4号员工合作完成大项目汇报,3号员工则需和所有员工合作才能完成大项目的汇报。编写程序,求每个员工为完成大项目汇报所需的最少员工编号组合。
(1)若5人参与完成10个小项目的情况为[2,4,1],[6,10,2],[5,9,3],[8,3,4],[3,7,5],则2号员工至少需要和　　　　(填员工编号)合作才能完成大项目的汇报。
(2)定义如下GetNext函数,参数列表x由n个元素组成,满足x[i][0]≤x[i][1](0≤idef GetNext(n,x):
　　j=0;gn=[]
　　for i in range(n):
　　　　while j=x[j][0]:
　　　　　　j=j+1
　　　　gn.append(j-1)
　　return gn
若x为[[2,4,1],[3,7,5],[4,8,2],[6,9,3],[8,13,6],[10,15,4]],n为6,调用GetNext(n,x)后,则gn[1]的值为　　　　。
答案　(1)4,5　(2)4
解析　(1)若5人参与完成10个小项目的情况为[2,4,1],[6,10,2],[5,9,3],[8,3,4],[3,7,5],则2号员工自己完成了[6,10]至少需要[1,5],4号员工可完成[1,3][8,10],5号员工可完成[3,7],因此4,5号员工可以与2号员工一起完成。(2)函数功能是x在按照左端点值升序排序后,去找到第一个x[i][1]+1>=x[j][0]即第一个左端点大于当前i的右端点的位置,将其前一个区间作为当前i的下一节点,存入gn中,当i=1时,右端点的值为7,则第一个满足x[i][1]+1>=x[j][0]条件的是[8,13,6],j=5,因此gn[1]的值为4。
1.将四字成语进行分类。例如,“心心相印”属于AABC类型,“喜气洋洋”属于ABCC类型。编写Python程序实现从文本文件中读取所有四字成语,进行分类并输出,
(1)若收集了3个四字成语为“百花齐放”“同心同德”“一心一意”,则一共出现　　　　(填数字)种类型。
(2)定义如下ctype(s)函数,参数s是一个字符串类型的四字成语。函数的功能是返回四字成语s的类型,例如,ctype("一动不动"),返回值是"ABCB"。
def ctype(s):
　　ret="A"
　　k=65　#字母"A"的ASCII码值为65
　　for i in range(1,4):
　　　　for j in range(i):
　　　　　　if s[i]==s[j]:
　　　　　　　　ret+=ret[j]
　　　　　　　　break
　　　　if s[i]!=s[j]:
　　　　　　k+=1
　　　　　　ret+=chr(k)
　　return ret
①调用ctype(s)函数,若变量s为“熙熙攘攘”,则函数运行结束时,变量k的值是　　　　。
②若将加框处代码“ret[j]”误写成“chr(k)”,则导致某些情况下无法得到符合函数功能的结果。调用ctype(s)函数,下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.s="炯炯有神" B.s="人才济济"
C.s="同心同德" D.s="博学多才"
答案　(1)2　(2)①66　②C
解析　(1)若收集的四字成语为“百花齐放”“同心同德”“一心一意”,则一共出现ABCD、ABAC两种类型。(2)①调用ctype(s)函数,若变量s为“熙熙攘攘”,即AABB类型,代码“k+=1”只被执行1次(k初始为65),故函数运行结束时,变量k的值是66。②若将加框处代码“ret[j]”误写成“chr(k)”,当出现相同的字不在相邻位置时,k值发生了变化,则无法通过chr(k)来表示相同字母,C选项修改后的返回值为ABBC。
2.根据社会学研究表明,人们都喜欢找和自己身高相近的人做朋友。现在有n名身高各不相同的同学依次走入教室,调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时,这名同学会更想和高的那个人做朋友,对于第1个走入教室的同学不做预测,后面进入教室的人,选择和他身高差值最小的人做朋友,若有多个最小差值,则选择身高最高的人做朋友。若有6人依次进入教室,选择的朋友如下表所示。
序号 1 2 3 4 5 6
身高 110 120 190 140 180 185
朋友序号 不预测 1 2 2 3 3
(1)若教室中再走入第7人,身高为175,他将选择第　　　　人做朋友。
(2)定义如下bsort(a)函数,参数a列表为依次走入的同学身高。函数的功能是返回数组a中数据从小到大的序号。
def bsort(a):
　　n=len(a)
　　b=[i for i in range(n)]
　　for i in range(n-1):
　　　　flag=False
　　　　for j in range(n-i-1):
　　　　　　if a[b[j]]>a[b[j+1]]:
　　　　　　　　b[j],b[j+1]=b[j+1],b[j]
　　　　　　　　flag=True
　　　　if flag==False: break
　　return b
若列表a的值为[110,120,190,140,180,185],调用bsort(a)函数,①加框处的语句执行次数为　　　　。②函数的返回值是　　　　　　。
答案　(1)5　(2)①2　②[0,1,3,4,5,2]
解析　(1)他与5号身高之差为5,差值最小。(2)①从前往后冒泡,第1趟有数据交换,第2趟没有数据交换,结束排序,因此共循环了2次。②列表b的初值为[0,1,2,3,4,5],索引为2的数据190被交换到最后。
3.某评选活动有n个评委,需从m个品牌中评选一个最佳品牌,评选采取多轮淘汰制,每轮投票后得票最少的品牌被淘汰(得票并列最少的品牌一起淘汰)。如此循环淘汰,若最后只剩下一个品牌,即告评选成功,输出当选品牌编号。如果在某轮投票中,当时未被淘汰的所有候选品牌(大于等于两个品牌)得票数都相同,即告评选失败。
每位评委根据预设的态度序列投票。如某评委的态度序列为:3、1、2,则表示该评委优先投3号,当3号被淘汰时投1号,仅剩2号时才投2号的票。选票的序列中可以用0表示弃权,如某评委的评选态度序列为3、0,则表示该评委优先投3号,当3号被淘汰时(弃权)。
如有5个评委,3个品牌,评委的态度列表为[[3,1,0],[2,1,3],[1,0],[1,3,0],[2,3,1]],评选过程如下:
轮次 评委1 评委2 评委3 评委4 评委5 评选结果
第1轮 投3 投2 投1 投1 投2 1得2票,2得3票,3得1票,3淘汰
第2轮 投1 投2 投1 投1 投2 1得3票,2得2票,2淘汰,最佳品牌为1
现编写Python程序,模拟投票过程。请回答以下问题。
(1)若有5个评委,3个品牌,评委评选态度序列为lst=[[3,1,2],[3,1,0],[1,3,2],[1,2,3],[2,1,0]],则告评选　　　　(填:成功/失败)。
(2)定义如下vote(lst,m)函数,参数m表示品牌数量,lst列表每个元素有m个0至m的数据项,表示评委的投票态度。函数功能是评选并返回一个最佳品牌,若评选失败,则返回-1。
def vote(lst,m):
　　ans=m;f=[0]*(m+1)
　　while ans>1:
　　　　cnt=[0]*(m+1)
　　　　for i in range(len(lst)):
　　　　　　for x in lst[i]:
　　　　　　　　if x!=0 and f[x]!=-1:
　　　　　　　　　　cnt[x]+=1
　　　　　　　　　　break
　　　　
　　　　for i in range(1,m+1):
　　　　　　if cnt[i]==minc:　#②划线处语句
　　　　　　　　ans-=1
　　　　　　　　f[i]=-1
　　for i in range(1,m+1):
　　　　if f[i]!=-1:
　　　　　　return i
　　return -1
①若将加框处代码修改为如下代码:
minc=cnt[1]
for i in range(2,m+1):
　　if f[i]!=-1 and minc>cnt[i]:
　　　　minc=cnt[i]
　　minc=cnt[1]
会导致某些情况下无法得到符合函数功能的结果。调用vote(lst,m)函数,m的值均为3,下列4组数据中能测试出这一问题的lst值是　　　　(单选,填字母)。
A.[[3,2,1],[3,1,0],[3,1,0],[3,2,0],[3,1,0]]
B.[[3,2,1],[3,1,0]]
C.[[2,0,0],[2,0,0],[1,0,0],[1,0,0]]
D.[[3,0,0],[2,1,3],[2,1,0]]
②程序中划线处代码有错,请改正。
答案　(1)成功　(2)①D　②f[i]!=-1 and cnt[i]==minc
解析　(1)第一轮,2号得1票,淘汰。第2轮,5号评委投1号,3号得2票,1号得3票,3号淘汰。(2)①当1号淘汰后,他的得票数不能作为最小值。②若minc的值为0,则cnt[0]也符合条件,那么ans会多减少一次。
4.对某数据序列data中的元素进行“掺杂”加密,按照data中元素的个数,随机分割成若干段,如data中有9个元素,若数据分割表为[4,2,3],则表示将data分割为三组,第一组4个数据、第二组2个数据、第三组3个数据,分别在每组数据的后面插入1个随机的杂质数据。请回答下列问题:
(1)若data中有7个元素,数据分割表为[4,3],经过“掺杂”处理后,则插入杂质数据的个数为　　　　(填数字)个。
(2)定义如下insert(data)函数,函数功能将存储在data中的一组数分割成若干段,每段的后面插入一个[128,254]之间的随机数,返回插入后的数据以及原始数据中每段的个数(不含插入的数据)。实现加密功能的部分Python程序如下,请在划线处填入合适的代码。
def insert(data):
　　seg=[];x=0;n=len(data)
　　while x　　　　y=random.randint(2,6)
　　　　seg.append(y)
　　　　x+=y
　　seg[-1]=①　　　　　
　　res=[0]*(n+len(seg))
　　x,y=0,0
　　for i in seg:
　　　　for j in range(i):
　　　　　　②　　　　　
　　　　　　x+=1;y+=1
　　　　res[x]=random.randint(128,254)
　　　　③　　　　　
　　return res,seg
答案　(1)2　(2)①n-(x-y)　②res[x]=data[y] 　③x+=1
解析　(1)数据分割表为[4,3],分成两段,插入两个数据。(2)①y是每次产生的数据项的长度,x是累加长度,当累加长度大于或等于n时,结束分段,但最后一段可能超出了总长度n。最后一段的长度为n减去倒数第二段前面的累加和x-y。②存储在data中的一组数分割成若干段,每段的后面插入一个[128,254]之间的随机数,返回res列表,因此y是data的下标,x是res下标,将data[y]赋值给res[x]。③插入一个随机数后,x的下标向后移动一个位置。
5.某技能培训需要修完n(编号为0~n-1)门课程,每门课程可以有若干个前置课程(先完成前置课程学习才能学习本课程),但最多只能作为一门课程的前置课程。若n=5,如图所示课程间的依赖关系,完成课程4必须先完成课程0与课程5,完成课程3必须先完成课程1与课程4。可行的一种课程顺序可以为:0,5,4,1,3,2。
(1)若将图中加框处中的“3”改为“4”,请写出其中一组可行的课程顺序:　　　　　　。
(2)定义judge(n,kc)函数,参数n表示课程的数量,参数kc存储各门课程之间依赖关系,每个元素有2个数据项,前者是后者的前置课程,如kc=[[0,1],[1,2],[2,0]]。函数的功能检测是否有可行的课程顺序。
def judge(n,kc):
　　link=[-1]*n
　　for i in range(len(kc)):
　　　　link[kc[i][0]]=kc[i][1]
　　for i in range(len(kc)):
　　　　f=[0]*n;p=i
　　　　while p!=-1:
　　　　　　if f[p]==0:
　　　　　　　　f[p]+=1
　　　　　　else:
　　　　　　　　return False
　　　　　　p=link[p]
　　return True
若n的值为4,kc的值为[[0,2],[2,3],[3,1],[1,2]],则加框处语句运行的次数是　　　　。函数的返回值为　　　　。
答案　(1)0,1,5,4,3,2(0,1,5的顺序可以任意)　(2)5　False
解析　(1)课程0,1,5是课程4的前置课程,4是3的前置,3是2的前置。(2)先遍历列表kc各个节点,构建各个节点的链接关系。再次遍历列表kc各个节点,以当前节点作为头节点,统计经过节点p的次数,若链表某个节点经过2次或2次以上,表示该链表形成环,不符合最多只能作为一门课程的前置课程。link的值为[2,2,3,1],当p为0时,课程0的遍历次数增加1,接着遍历课程2,课程3,课程1,接着将再次遍历课程2,因此共判断了5次,返回值为False。
6.某机构采购了n类(编号1~n)紧急救援食品,储存条件分冷藏和常温。每个货柜的最大容量为m袋,货柜编号从1开始。按容量从大到小依次存放,若当前需存放食品容量为k,存放的方法:在已存放食品的货柜内寻找空余空间不少于k的货柜,且满足已存食品与当前食品的储存条件相同(冷藏或常温)。若存在多个这样的货柜,则挑选空余空间最小的来存放,若不存在,则存放于新的货柜。
(1)设m为100,n为4,每类食品容量依次为10,90,85,15,其中类别为3的食品需冷藏,其余为常温。则类别4所放置的货柜编号为　　　　。
(2)定义getroom(a,key,f)函数,参数a中每个元素由货柜的空位数和储存条件(0常温,1冷藏)两个数据项构成。参数key表示需要存储食品的数量,参数f表示储存条件。函数的功能是为各类剩余食品寻找储存的货柜编号。
def getroom(a,key,f):
　　flag=True
　　k,i=0,0
　　while i　　　　if a[i][0]>=key and a[i][1]==f:
　　　　　　if flag or a[i][0]<=a[k][0]:
　　　　　　　　k=i;flag=False
　　　　i+=1
　　if flag==False:
　　　　return k
　　return len(a)
若a为[[0,0],[25,1],[30,0],[20,1],[15,0]]。①key为15,f为1,调用getroom(a,key,f)后,返回的值为　　　　。②key为35,f为0,调用getroom(a,key,f)后,返回的值为　　　　。
答案　(1)3　(2)①3　②5
解析　(1)按容量从大到小排列,存放的顺序为90,85,15,10。90放在1号柜中,剩余10个空间;85需冷藏,放在2号柜中;15放在3号柜中,10放在1号柜中。(2)函数功能为各类剩余食品寻找储存的货柜编号。找出类别为1且剩余袋数大于等于key的最小值下标。①key为15,f为1,能够存放储存条件1的最小柜号为3。②key为35,f为0,则找不到可以存储该容量的柜子,因此返回新的柜号5。
1.小海对括号串问题非常感兴趣,他设计了一个编辑括号串的程序。程序支持三个操作:
①L:将光标左移一格;
②R:将光标右移一格;
③D:删除光标处的括号到与它对应的括号之间的所有括号(包括当前光标处的括号和其对应的括号)。在删除之后,光标会跳到它右边的没有被删除的最左边的括号处;若右边没有括号了,则光标会跳到它左边的没有被删除的最右边的括号处。图a即为两个D操作的例子。
(1)若括号串为"(()(()))",当前光标所在位置为2(从左往右数第二个括号处),则进行一次D操作后,括号串变为　　　　。
(2)定义如下match(bracket)函数,参数bracket是由左右小括号组成的字符串。函数功能是检测 bracket中的左右括号是否匹配,若匹配,则函数返回True;否则函数返回False。
def match(bracket):
　　stack=['']*len(bracket);top=-1
　　flag=True
　　for c in bracket:
　　　　if c=='(':
　　　　　　top=top+1;stack[top]=c
　　　　elif c==')':
　　　　　　if top!=-1:
　　　　　　　　top-=1
　　　　　　else:
　　　　　　　　flag=False;break
　　if top!=-1 or not flag:
　　　　return False
　　else:
　　　　return True
①调用match(bracket)函数,若bracket为“()((()))”,则程序执行过程中,变量top的最大值为　　　　。
②若函数中加框处的条件“top!=-1 or not flag”误写为“not flag”,会导致某些情况下无法得到符合函数功能的结果。调用match(bracket)函数,下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.bracket="()()"
B.bracket=")()"
C.bracket=")()("
D.bracket="(()"
答案　(1)((()))　(2)①2　②D
解析　(1)删除第1对括号,即光标所在左括号和之与对应的右括号。(2)①左括号" ("入栈,遇到右括号")"马上出栈,接着有3个左括号入栈,top从0开始计数,因此最大值为2。②flag为假时表示左括号的数量小于右括号,B和C选项当遍历到第1个右括号时,没有左括号,返回假。当左括号的数量大于右括号时,栈中还有左括号,此时栈不为空,D选项循环结束后,flag的值真,但栈中还有一个左括号。
2.小华开发了一个简单的医院门诊预约管理系统,用于模拟病人的预约和取消操作。系统输入格式如下:若输入"预约"开头,后面两个数字为预约开始时间和持续时长。若能找到符合病人预约要求的空闲时间段则预约成功,系统按照预约顺序分配病人编号,其中病人起始编号为1。若输入"取消"加病人编号,系统会查找指定编号并释放相应的预约时间段。
假设该门诊系统每天可预约的时间范围为0到99,则图a门诊系统的时间段分配情况如图b所示,每行表示一个时间段的预约情况。
请回答下列问题:
(1)若门诊的可预约时间为0~45,在执行了图a的前4行输入后,门诊系统分配的时间段为:0~9:空闲,10~29:空闲,30~39:病人2,　　　　。(请完善最后一段时间段门诊预约情况)
(2)定义如下book(sch,st,time,id)函数,参数sch列表用于存储每个时间段的预约情况,每个元素有病人序号,是否预约,起始时间,结束时间共4个数据项。病人序号为0表示该时间段空闲。参数st和time表示预约开始时间和持续时长,id表示病人的序号。函数的功能是将病人分配到指定的时间段。实现上述功能的程序如下,请在划线处填入合适的代码。
def book(sch,st,time,id):
　　①　　　　　
　　i=0
　　while i　　　　block=sch[i]
　　　　if not block[1] and block[2]<=st and block[3]>=ed:
　　　　　　sch[i]=[id,True,st,ed]
　　　　　　if block[2]　　　　　　　　sch=sch[:i]+[[0,False,block[2],st-1]]+sch[i:]
　　　　　　　　②　　　　　
　　　　　　if ③　　　　　　:
　　　　　　　　sch=sch[:i+1]+[[0,False,ed+1,block[3]]]+sch[i+1:]
　　　　　　return sch,id
　　　　i+=1
　　return sch,-1
答案　(1)40-45:空闲　(2)①ed=st+time-1　②i+=1　③ed解析　(1)可预约时间为0~45,则开始预约40,执行时间10的记录无法完成预约。病人2的结束时间为39,因此从40到45是空闲时间。(2)①根据参数预约开始时间st和持续时长time确定结束ed。②若当前时间段sch[i]空闲且符合开始时间和结束时间的要求,先将该时间段设置为[id,True,st,ed],若预约时段大于该时间的开始时间,则要在预约开始前划分一个新的空闲时段,那么当前时段下标i将增加1。③遍历各个时间段sch,若当前时间段没有预约,且预约时间小于等于起始时间,ed小于等于结束时间,表示该时间段可以预约。若条件block[2]3.某机器在上午8点到12点的时间段可以安排加工产品。按以下规则选择部分产品加工:先选择所有产品中加工结束时间最早的产品(若有多个产品的结束时间相同,则优先选择加工时长少的产品),然后在剩余产品中选择时间不冲突的结束时间最早的产品进行加工,依次类推……直至选择完毕。编写一个Python程序,实现以下功能:读取n个产品的编号、预计到达时间和所需加工时长,输出选择加工的产品编号、加工起始时间和结束时间。
(1)有6个产品,产品编号、预计到达时间和所需加工时长(分钟)如下:
[[1,"08:00",105],[2,"08:30",60],[3,"09:35",105],[4,"10:30",90],[5,"10:00",35],[6,"09:40",40]],则选择加工的第2个产品的编号为　　　　(填数字)。
(2)实现上述功能的Python程序如下,请在划线处填入合适代码。
def convert1(t):
　　#把时间格式 t 转化为整数,如"08:30"转化为510。代码略
def convert2(t):
　　#把整数t 转换为时间格式,如 510 转化为"08:30"。代码略
'''
读取n个产品的数据存入列表a[0]至 a[n-1]中,a[i]包含3个数据项,a[i][0]、a[i][1]和a[i][2]分别存放产品编号、预计到达时间和所需时长,代码略
'''
for i in range(n):
　　st=convert1(a[i][1])
　　a[i].append(st)
　　ed=st+a[i][2]
　　a[i].append(ed)
flag=[False]*n
for i in range(n-1):
　　①　　　　　
　　for j in range(i+1,n):
　　　　if a[j][4]　　　　　　k=j
　　　　a[i],a[k]=a[k],a[i]
st=convert1("08:00")
ed=convert1("12:00")
for i in range(n):
　　if a[i][3]>=st and a[i][4]<=ed:
　　　　flag[i]=True
　　　　②　　　　　
print("产品编号","起始时间","结束时间")
for i in range(n):
　　if ③　　　　　　:
　　　　print(a[i][0],a[i][1],convert2(a[i][4]))
答案　(1)6　(2)①k=i　②st=a[i][4]或等价答案
③flag[i]或 flag[i]==True
解析　(1)第1个加工产品是[1,"08:00",105]结束时刻是9:45,此时到达的产品有,[2,"08:30",60],[3,"09:35",105],[6,"09:40",40],根据规则优先加工时间少的产品,因此第2个加工编号是6号。(2)①空通过排序方式,实现所有产品中加工结束时间最早的产品(若有多个产品的结束时间相同,则优先选择加工时长少的产品)初始化比较索引为当前索引。②依次选择不冲突的产品进行加工,并更新当前时间。③根据标记输出已经加工的产品。
4.同源词指由相同字母(全部为小写字母)重排列形成的字符串,包括相同的字符串。当给定两个字符串s和p(s长度大于p长度),找到s中所有是p的同源词的子串,按出现的顺序输出这些子串的起始索引。如s的值为"cbaebacdbabc",p的值为"abc",则同源词的起点为[0,4,9]。
(1)若s的值为"cbaebacdbabc",p的值为"ab",则同源词的起点为　　　　。
(2)实现该功能的程序代码如下:
def judge(s,p):
　　scount=[0]*26;pcount=[0]*26
　　m=len(s);n=len(p);ans=[]
　　for i in range(n):
　　　　scount[ord(s[i])-ord("a")]+=1
　　　　pcount[ord(p[i])-ord("a")]+=1
　　if scount==pcount:ans.append(0)
　　for i in range(m):　#②题改错
　　　　scount[ord(s[i])-ord("a")]-=1
　　　　scount[ord(s[i+n])-ord("a")]+=1
　　　　if scount==pcount:
　　　　　　ans.append(i+1)
　　return ans
①若删除函数中加框处语句,会导致某些情况下无法得到符合函数功能的结果。若s的值为"dbabdccbaeb",调用judge(s,p)函数,下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.p="ab" B.p="cd"
C.p="dbc" D.p="bad"
②程序代码for i in range(m)中,参数m有错,应修改为　　　　。
答案　(1)1,4,8,9　(2)①D　②m-n
解析　(1)下标为9的“a”与前面后面的“b”都可以组合,所以答案为1,4,8,9。(2)利用了“滑动窗口”思想,scount统计s中各个字符出现的次数,pcount则存储了p中各个字符出现的个数。子串长度一定等于p的长度,所以将索引i位置的值移除,就需要将索引i+n的值加入统计,保持scount中的字符长度不变,且scount的统计结果和pcount的结果相同时,就说明找到了新子串。①当子串出现在索引位置0时,将会出错。D选项子串在索引位置0找到了。②在长度m的字符串s中查找是否包括长度为n的字符串p,那么最后一个子串的起始位置应是m-n-1,参数修改为m-n。
5.小明研制一种药物,采集了n种原料,现对每种原料先进行放射试验,再进行加热试验的顺序进行精密分析。实验室同一时间最多只能做一个放射试验和一个加热试验,为尽早完成试验,小明将放射试验用时短的尽量排前面,加热试验时间用时短的尽量排后面。例如:有A~E共5种原料,每种原料需要的试验时间如图a所示;最终各原料的试验安排如图b所示。
原料名称 放射试验时间 加热试验时间
A 8 5
B 4 2
C 4 10
D 16 7
E 3 5
图a
试验安排顺序为:E→C→D→A→B→ 结束试验的最早时间:38
图c
编写程序:给定各种原料所需试验的时间,根据上述方法安排试验顺序并计算所有原料完成试验的最早结束时间,输出结果如图c所示。
(1)若将原料E的放射试验时间3修改为13,则结束试验的最早时间为　　　　。
(2)定义如下自定义函数order(task,n),参数task的每个元素由原料名称、放射时间和加热时间3个数据项构成,参数n为原料种类。函数功能是安排合理的试验顺序,使得试验尽早完成。
def order(task,n):
　　f=[False]*n;odr=[-1]*n
　　st=-1;ed=n
　　for i in range(n):
　　　　min=30000　#已知每个试验时间最多不超过30000
　　　　for j in range(n):
　　　　　　if f[j]==False:
　　　　　　　　for k in range(1,3):
　　　　　　　　　　if task[j][k]　　　　　　　　　　　　min=task[j][k]
　　　　　　　　　　　　bestj=j
　　　　　　　　　　　　bestk=k
　　　　f[bestj]=True
　　　　if bestk==1:
　　　　　　st+=1;odr[st]=bestj
　　　　else:
　　　　　　ed-=1;odr[ed]=bestj
　　return odr
若task=[["A",5,2],["B",4,2],["C",1,8]],n=3,请回答下列问题。
①调用该函数后,st和ed的值分别为　　　　,　　　　。
②odr的值为　　　　。
③将虚线框处代码改成for j in range(n-1,-1,-1),　　　　 (单选,填字母:A.会/B.不会)影响原料试验的安排顺序。
答案　(1)48　(2)①0,1　②[2,1,0]　③A
解析　(1)试验安排顺序为C→D→E→A→B,C、D、E在14、27、38完成,A放射完成时间为41,加热完成是46,B放射完成时间为45,加热完成是48。(2)①先对原料按放射时间短的尽可能排在前面,加热时间长的尽可能排在前面。odr存储代加工原料的序号,st是从前往后的索引,ed是从后往前的索引。先在最后存储原料A,st值为2,接着从后往前存储原料B,st值为1。最后在最前面存储原料C,st为0。因此②返回odr的值为[2,1,0]。③选择排序的范围从后往前,那么当较短的时间一样的时候,先排后面再排前面,所以会影响原料实验的安排顺序。
6.通配符“*”通常用于模式匹配,例如在文件操作或者搜索时用来代替任意数量的字符,“*.txt”匹配所有txt文件。匹配样例如图所示。
文本内容 key 匹配结果
强化学习 强化 False
神经网络 *神经 False
知识图谱 知*谱 True
深度学习 深度* True
咕噜咕噜 *咕噜 True
(1)现有4个单词:Carper、 Carver、Carpenter、Carrier,能匹配上述单词的最长key是　　　　。
(2)编写自定义函数judge(name,key),参数key中可能包含若干个“*”,函数的功能是判断字符串name是否可以用key来描述。
def judge(name,key):
　　i=j=0
　　flag=False
　　while i　　　　if j　　　　　　i+=1;j+=1
　　　　elif j　　　　　　flag=True
　　　　　　step=0　#记录通配符匹配的字符数量
　　　　　　temp=[i,j]
　　　　　　j+=1　#跳过通配符"*",处理key的下一个字符
　　　　elif flag:
　　　　　　step+=1　#增加通配符匹配的字符数量
　　　　　　i=temp[0]+step　#尝试匹配更多字符
　　　　　　j=temp[1]+1　#重置j到通配符后的位置
　　　　else:
　　　　　　return False
　　if j 　　return True
若name为"causeless",key为"ca*l*s",调用judge(name,key)后,加框处语句step+=1运行的次数为　　　　。
(3)若去除代码if j A."ca*l*" B."a*l*s"
C."c*s*es" C."c*"
答案　(1)Car*er　(2)5　(3)C
解析　(1)这4个单词以Car开头,er结尾,因此最长的key为Car*er。(2)变量i和j分别遍历name和key中每个位置,若这两个位置上字符相同,同时向后移动;若j位置上对应的是通配符"*",用temp[0]记录i的位置,用temp[1]记录j的位置,flag的值为True,若下次再次遇到"*",则更新temp的值。第1个"*"匹配到了"use",第2个"*"匹配到了"es",共匹配到5个字符,因此累加5次。(3)C选项"c*s*es"中第2个"*"匹配到了s后面所有字符,匹配到"eless",j指针值为4,"c*s*es"中还有"es"未检验,但name中又没有。
7.某车间生产三种不同的产品,不同产品可以同时开始生产,三种产品按照不同的部件顺序完成。如“产品0”生产顺序为“部件1”→“部件0”,即“部件1”完成后才开始“部件0”,即部件1是部件0的前驱部件,每个部件仅有一个前驱部件,如图a所示。每个部件自身又需同编号的一个材料完成才能开始生产,如“部件0”需要“材料0”,“部件1”需要“材料1”……,各种材料按各自的开始生产时刻进行,完成所需时长也有所不同,如图b所示,部件完成所需时长不包括材料生产在内。现编写程序,模拟该生产过程,并计算每个产品的部件完成的时刻。
图a
产品号 部件顺序 材料生产 开始时刻 材料生产 所需时长 部件完成 所需时长
产品0 部件1 3 3 2
部件0 2 2 1
产品1 部件2 3 2 2
部件4 4 1 3
部件5 9 2 2
图b
(1)若有2个产品,“产品0”由“部件1”→“部件0”完成,“产品1”由“部件2”→“部件4”→“部件3”完成,所需材料开始生产时刻和完成所需时长如图b所示。经计算产品0的完成时刻是9,请回答产品1完成的时刻是　　　　　　。
(2)定义pre(arr)函数,参数arr每个元素2个数据项,arr[i][0]表示arr[i][1]的前驱部件,arr[i][1]为-1时表示arr[i][0]为某个产品中最后的部件。函数功能查找每个产品所需的第1个部件。
def pre(arr):
　　i=0;j=i+1;flag=True
　　h=[]
　　while i　　　　if j　　　　　　j+=1
　　　　else:
　　　　　　flag=False
　　　　if j==len(arr) or not flag:
　　　　　　if flag==True:
　　　　　　　　h.append(arr[i][0])
　　　　　　i+=1;j=0
　　　　　　flag=True
　　return h
path=[[0,-1],[1,0],[2,4],[3,-1],[4,3]],调用该函数,pre(path),则加框处代码执行　　　　次,函数的返回值为　　　　。
答案　(1)13　(2)①3　②[1,2]
解析　(1)产品1由部件2→4→3顺序完成。则先计算部件2完成时间,但部件2开始时间又材料2时间决定,材料2时间计算:3+2=5,则部件2完成时刻:5+2=7然后是部件4的计算。材料4:4+1=5小于其前驱部件2从而形成等待,则部件4完成时刻为7+3=10。最后材料3因为完成时刻是11,因为部件4是部件3的前驱,但部件4在时刻10已经完成部件3只剩下等待自身材料在时刻11完成才能开始,最后得11+2=13。(2)flag=False的执行次数即为非头节点的个数,原多链表为1→0,2→4→3,非头节点为0,4,3,所以执行3次。2个头指针分别为1和2。
8.使用某浏览器浏览网页时,在内存中只会保留最近浏览过的k个网页,浏览的网页数达到或超过k个时,会将最近k个网页中访问频率最高的网页存入cache。如k为3,依次访问6个网页如图a所示;当连续浏览网页数达到3个时,将最近3个网页中访问频率最高的网页存入cache,存入情况如图b所示。Cache中改写和保持的过程如图c所示,程序只记录改写的2张网页P1和P5。
(1)由题意可知,若仅将图a中网页名称为p4的访问频率改为5,则cache改写的次数为　　　　。
(2)定义如下find(data,k)函数,参数data每个元素包含网页名称及访问频率共2个数据项,参数k存储内存中存储网页的最大容量。程序功能根据data网页信息及容量k,返回依次改写cache的值。
def find(data,k):
　　result=[]
　　que=[-1]*100
　　head=tail=0
　　for i in range(len(data)):
　　　　if tail>head and que[head]<=i-k:
　　　　　　head+=1
　　　　while tail>head and data[que[tail-1]][1]　　　　　　tail=tail-1
　　　　que[tail]=i
　　　　tail+=1
　　　　if i>=k-1:
　　　　　　result.append(data[que[head]][0])
　　return result
①调用find函数,若data的值依次为["p2",2],["p2",2],["p3",2],["p1",4],["p4",5],k值为3,则while语句中循环体tail=tail-1的执行次数是　　　　。
②程序中加框处代码有错,请改正。
答案　(1)3　(2)①3　②i>=k-1 and (result==[] or data[que[head]][0]!=result[-1])
解析　(1)网页序号0-3的最高值为4,1次改写,3次保持。网页序号4和网页序号6各改写一次。(2)①将最近k个网页中访问频率最高的网页存入cache,若第i个网页是第k+1张网页,要删除前面不是近k个网页,head为访问频率最高网页索引,即i-que[head]+1>=k+1。访问到p3时,没有执行while语句,head和tail的值分别为0和3,访问到p1时,先执行if语句让第1个p2出队,接着p1的高于队列中两个网页,while循环体执行2次,p1再入队。访问p4时,while循环体执行1次,p4再入队。②result只保存第1个进入cache和改写cache的值,而不记录保持的值。

展开更多......

收起↑