第10课 队列2——队列应用-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固PPT课件（浙教版2019）

第三章│字符串、队列和栈 ——3.2　队列，教材P74～81 第10课　队列2——队列应用 新课程目标 1.掌握队列的基本操作，并能编程实现。　2.能使用队列的基本操作解决实际问题。 目录 CONTENTS 教材整体感悟 知本与探源 01 02 命题整体感知 尝试与研析 01 教材整体感悟 知本与探源 教材整体感悟 知本与探源 本课核心点 ● 重难点 1．信息加密 给定一个字符串“12…n”，按如下过程加密：取出第一个字符“1”，将第二个字符“2”放到字符串的末尾“n”后面，得到字符串“3…n2”；接着把“3”取出，“4”放到字符串的末尾“2”后面……直到所有字符被取出。这些字符按取出的顺序形成一个新的字符串，称为密串。请编写一个加密程序，输入一个字符串(长度小于等于100)，输出该字符串的密串。 代码为： 教材整体感悟 知本与探源 s＝input(”请输入字符串：　”) que＝[””]*100 head＝tail＝0 for i in range(len(s))：　#把原串全部压入队列 que[tail]＝s[i] tail＋＝1 print(”密串为：　”) 教材整体感悟 知本与探源 while head<tail：　 #队列非空时循环进行 print(que[head]，end＝” ”) head＋＝1 if head<tail：　 #队列非空时，出队的元素加入队尾 que[tail]＝que[head] tail＋＝1 head＋＝1 教材整体感悟 知本与探源 运行结果为： 教材整体感悟 知本与探源 2． 队列思维的应用 只要问题中存在着“先进先出、后进后出”的特性，就可以使用队列来解决。例如：银行叫号排队系统，可以采用队列结构，用入队(取号)、出队(叫号)实现系统功能。 代码为： que＝[－1]*1000 head＝tail＝0 教材整体感悟 知本与探源 print(”请输入具体的操作编号：　”) print(”1.新到顾客取号”) print(”2.下一个顾客叫号”) print(”3.程序结束”) x＝int(input(”请输入操作 ”)) while x！＝3： if x＝＝1： 教材整体感悟 知本与探源 que[tail]＝que[tail]＋1 print(”您当前的号码为：　A%d，需要等待的人数为：　 %d”%(tail，tail－head)) tail＋＝1 if x＝＝2： if head＝＝tail： print(”对不起，　没有等待的客户”) 教材整体感悟 知本与探源 else： 　　print(”请A%d号客户准备，　马上将为您办理业 务。　”%(head)) head＋＝1 x＝int(input(”请输入操作 ”)) 运行结果为： 教材整体感悟 知本与探源 请输入具体的操作编号： 1.新到顾客取号 2.下一个顾客叫号 3.程序结束 请输入操作 1 您当前的号码为：A0，需要等待的人数为0 教材整体感悟 知本与探源 请输入操作 1 您当前的号码为：A1，需要等待的人数为1 请输入操作 1 您当前的号码为：A2，需要等待的人数为2 请输入操作 教材整体感悟 知本与探源 2 请A0号客户准备，马上将为您办理业务。 请输入操作 1 您当前的号码为：A3，需要等待的人数为2 请输入操作 3 教材整体感悟 知本与探源 3．队列的链式存储结构 队列的链式存储结构称为链队列，为了操作方便，可设置队首指针head记录链表的头节点，队尾指针tail记录链表的队尾节点。 02 命题整体感知 尝试与研析 命题整体感知 尝试与研析 例1为了对某信息系统中的字符串数据进行加密，小蓝同学设计了加密函数secret(s，k)，其中s为明文，k为正整数密钥，函数的返回值为密文。secret()函数的Python代码如下： def secret(s，k)： a＝[i for i in s] a．append('*') n＝len(s)＋1 命题整体感知 尝试与研析 ans＝”” t＝0 head，tail＝0，n－1 t＝t＋1 if t＝＝k： ans＋＝a[head] 命题整体感知 尝试与研析 t＝0 else： 　　a[tail]＝a[head] 　　tail＝(tail＋1)%n head＝(head＋1)%n return ans 命题整体感知 尝试与研析 下列关于该加密过程的说法中，不正确的是(　　) A．该加密过程用到的数据结构为队列 B．该加密过程属于对称加密中的替代加密法 C．若原文s为python，密钥k＝3，则加密得到的密文为tnhyop D．将方框处代码改为“head<tail”可能会影响最终的加密结果 B 命题整体感知 尝试与研析 【解析】 选项A，用到的是循环队列，选项正确；选项B，将明文中的字符通过一定的规则重新排列，是换位密码法，选项错误；选项C，代入程序可知选项正确；选项D，用到的是循环队列，判断队列是否为空条件只能是tail！＝head，和head<tail不等价，修改代码可能会影响结果，选项正确。 命题整体感知 尝试与研析 变式1小雪根据凯撒加密算法，设计了一种新的字符加密方法——小雪加密算法。她设计的加密规则如下： ①大小写转换：将明文中的大写字母转换成小写字母，如“A”转换成“a”。 ②置换加密：根据输入的置换密钥，将字符串中的小写字母逐个加上置换密钥中的对应数字循环右移，置换密钥可以循环使用。如原文为“world2022”，置换密钥为“412”，则加密为“aptpe2022”。(字母w、o、r、l、d分别循环右移4、1、2、4、1位) (1)主程序 命题整体感知 尝试与研析 text＝input(”请输入需要加密的字符串：　”) key＝input(”请输入置换密钥：　”) encode＝”” for ch in text： encode＝encode＋change(ch) encode＝encypt(encode，key) print(”加密结果为：　”，　　　　　　) 命题整体感知 尝试与研析 横线处填入的代码应为_________________。 (2)大小写转换函数代码如下： def change(ch)： #将ch的大写转换为小写 if ch>＝”A” and ch<＝”Z”： ch＝chr(　　　　　　) return ch 横线处填入的代码应为___________________________________。 　encode　 　ord(ch)－ord(”a”)＋ord(”A”)　 命题整体感知 尝试与研析 (3)置换加密函数，将字符串中的小写字母按照置换密钥key逐个进行循环右移变换。 def encypt(encode，key)： #将encode按照置换密钥key进行置换加密 q＝[] result＝”” for x in key： q．append(int(x)) #将密钥逐个转为数值，并放到q中 命题整体感知 尝试与研析 head＝0 for ch in encode： if ch>＝”a” and ch<＝”z”： 　　x＝q[head] 　　①　　　　　　 　　q．append(x) #将x放到q的末尾 　　t＝ord(ch)－ord(”a”) 命题整体感知 尝试与研析 　　t＝②　　　　　　 　　ch＝chr(ord(”a”)＋t) result＝result＋ch return result 横线处填入的代码应为：①_________________________________； ② __________________。 【解析】 (1)阅读主程序，由encode＝encypt(encode，key)可知，加密处 　head＝head＋1 或 q．pop(0) 　 　(t＋x)%26　 命题整体感知 尝试与研析 理的结果存储在变量encode中。 (2)此处需要在自定义函数中完成从大写字母到小写字母的转换。根据对位大小写字母的变化规律， 结合字符转换为ASCII码的函数即可推出。 (3)此处自定义函数结合队列和凯撒加密算法来实现。根据上一行程序“x＝q[head]” 取出队首元素存入变量x中和下一行程序“q.append(x)” 将x放到q的末尾，结合本题的算法是要利用密钥进行循环右移变换，可以得知每次取出的队首元素x即为本次字符加密所需密钥，队首元素出队后需要将头指针head后移，故①的答案为head＝head＋1。根据字母所在 命题整体感知 尝试与研析 位置往右移动x个位置得到加密后的字符，字母表需视为首尾相连，因此结合取余运算来得到右移后字符所在的位置。故②的答案为(t＋x)%26。 命题整体感知 尝试与研析 例2就餐叫号排队系统。餐厅中客满的情况下，当有新客人时，服务员通过就餐叫号排队系统进行取号操作，若客人未提前预约，则排在当前队列的最后；若客人已提前预约，则排在当前队列中提前预约客人的后一个位置(若当前队列中没有提前预约客人，则该客人排在当前队列的最前面)；当餐厅中有位置时服务员就进行叫号操作，程序运行界面如下图所示： 1为取号操作， 2为叫号操作， 3为程序结束 请输入具体的操作编号： 命题整体感知 尝试与研析 1 请问是否提前预约(y/n)： n 您当前的号码为A0， 您需要等待的人数为0 ！ 号码为A0的顾客需要等待0桌！ 请输入操作： 1 请问是否提前预约(y/n)： y 您当前的号码为A1(预约)， 您需要等待的人数为0 ！ 命题整体感知 尝试与研析 号码为A1(预约) 的顾客需要等待0桌！ 号码为， A0的顾客需要等待1桌！请输入操作： 1 请问是否提前预约(y/n)　： y 您当前的号码为A2(预约)， 您需要等待的人数为1 ！ 号码为A1(预约) 的顾客需要等待0桌！ 号码为A2(预约) 的顾客需要等待1桌！ 号码为， A0的顾客需要等待2桌！ 命题整体感知 尝试与研析 请输入操作： 1 请问是否提前预约(y/n)　： n 您当前的号码为A3， 您需要等待的人数为3 ！ 号码为A1(预约) 的顾客需要等待0桌！ 号码为A2(预约) 的顾客需要等待1桌！ 号码为A0的顾客需要等待2桌！ 号码为A3的顾客需要等待3桌！ 命题整体感知 尝试与研析 请输入操作： 2 请号码为A1(预约) 的顾客就餐！ 号码为A2(预约) 的顾客需要等待0桌！ 号码为A0的顾客需要等待1桌！ 号码为A3的顾客需要等待2桌！ 请回答下列问题。 (1)若程序运行到如上图所示时，再次执行叫号操作，号码为_____ (选填： 　A2　 命题整体感知 尝试与研析 A0/A2/A3)的顾客就餐。 (2)实现上述功能的Python程序如下，请在横线处填入合适的代码。 q＝[[”，0]]*1000；head＝0；tail＝0 print(”1为取号操作，　2为叫号操作，　3为程序结束”) print(”请输入具体的操作编号：　”) x＝int(input()) while x！＝3： 命题整体感知 尝试与研析 if x＝＝1： bk＝input(”请问是否提前预约　(y/n)　：　”) #提前预约输入y， 否则输入n if bk＝＝'n'： #客人未提前预约，则排在当前等待队列的最 后面 q[tail]＝[”A”＋str(tail)，0] print(”您当前的号码为”，q[tail][0]，end＝”，　”) 命题整体感知 尝试与研析 print(”您需要等待的人数为”，tail－head，”！　”) else： 　　 j＝tail－1 　　 while ①_____________________________________________　 _______： q[j＋1]＝q[j] j＝j－1 j>＝head and q[j][1]＝＝0或j>＝head and q[j][1]！ ＝1　 命题整体感知 尝试与研析 　　q[j＋1]＝[”A”＋str(tail)＋”(预约)”，1] 　　print(”您当前的号码为”，q[j＋1][0]，end＝”，　”) 　　print(”您需要等待的人数为”，j＋1－head，”！　”) tail＝tail＋1 elif x＝＝2： if head！＝tail： print(”请号码为”，q[head][0]，”的顾客就餐！　”) 命题整体感知 尝试与研析 ②　_____________________　 else： 　　print(”当前没有等待的顾客！　”) for i in range(head，tail)： print(”号码为”，q[i][0]，”的顾客需要等待”， ③　______________________　，”桌！　”) x＝int(input(”请输入操作：　”)) head＝head＋1 i－head 或 str(i－head) 命题整体感知 尝试与研析 【解析】 (1)由图可知A2是预约用户， 排在其他顾客前面， 所以A2先就餐。 (2)①处是预约顾客的处理代码，预约顾客插在预约顾客与非预约顾客的中间， 所以需要将所有的非预约顾客(条件为q[j][0]＝0)向后移动一个位置，另外队列中没有预约顾客时，所有的顾客都要向后移动，条件为j>＝head， 综合以上两个方面，②处排在队首的顾客就餐后， 应该将该顾客出队， 头指针后移，③处填写当前顾客需要等待的桌数， 也就是与头指针的差值。 命题整体感知 尝试与研析 例3[2023·宁波中学检测]为防止某病毒发生大规模传染，若发现某人具有该病毒，则与该人员直接或间接接触过的人员都要进行隔离措施。例如，A 具有该病毒，A 和B 接触过，B 属于与A 直接接触的人员，需要被隔离，B和C 接触过，C 和D 接触过，那么C 属于与A 间接接触的人员，也需要隔离，D 不属于与A 间接接触的人员，不需要隔离。 已知有n 个人，将这些人用0，1，2，…，n－1 进行编号，并用一个关系矩阵模拟他们之间是否直接接触，相互之间有直接接触的在矩阵中用1 表示；没有直接接触的用0 表示，对于自身用1 表示，即矩阵的左上角 命题整体感知 尝试与研析 到右下角的对角线全为1。例如，图1的矩阵表示0 号人员与2 号人员直接接触，1 号人员与2 号人员直接接触。 编写Python 程序，随机产生一个关系矩阵，输出该关系矩阵，输入具有病毒的人员编号，输出所有需要隔离的人员编号。Python 程序运行界面如图2所示。 命题整体感知 尝试与研析 (1)分析图2所示的矩阵，若病人编号为3，则需要隔离的人员编号为 ______________(按编号从小到大写，编号与编号之间用空格隔开)。 (2)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 import random n＝10 s＝[[0 for i in range(n)]for j in range(n)] for i in range(n)： 　3 4 5 8　 命题整体感知 尝试与研析 for j in range(i，n)： if i＝＝j： s[i][j]＝1 else： 　　s[i][j]＝random.randint(0，1) 　　①　_________________　 #输出关系矩阵，代码略 s[j][i]＝s[i][j] 命题整体感知 尝试与研析 bh＝int(input(”请输入具有病毒的人员编号：　”)) gl＝[False]*n que＝[－1]*n；head＝0；tail＝0 que[tail]＝bh；tail＝tail＋1；gl[bh]＝True zj＝True while head<tail： c＝que[head] 命题整体感知 尝试与研析 head＝head＋1 ②　____________________： if s[c][i]＝＝1 and c！＝i： if zj＝＝True： ③　_______________　 tail＝tail＋1 gl[i]＝True for i in range(n) que[tail]＝i 命题整体感知 尝试与研析 zj＝False print(”需要隔离的人员编号为：　”) for i in range(n)： if gl[i]＝＝True： print(i，end＝” ”) 【解析】 若病人编号为3，与其直接接触的是5号，间接接触的是4号和8号，所以隔离人员编号是：3，4，5，8。①空用于得到矩阵对角线左下 命题整体感知 尝试与研析 角部分的数据，与随机获得的右上角数据对称位置相等，所以其位置上的值是s[j][i]＝s[i][j]；②空逐列遍历与队列出队元素编号的接触情况，如果是与带病人员接触的人员，则入队进入下一轮与其接触的人员编号情况。 命题整体感知 尝试与研析 例4[2023·浙江1月选考]有2 组器件共n 个，要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先级。优先级有m(1<m<6)个等级，由高到低分别用0～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 均已按送达时间升序排列。 　6　 命题整体感知 尝试与研析 函数功能是将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”，会导致某些情况 　4　 命题整体感知 尝试与研析 下无法得到符合函数功能的结果。调用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 程序如下，请 　A　 命题整体感知 尝试与研析 在横线处填入合适的代码。 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[i]追加一个元素－1 curtime＝0 waitnum＝0 i＝0 ①　_______________　 while i<n or waitnum>0： if i<n and data[i][0]<＝curtime： total＝0 命题整体感知 尝试与研析 k＝data[i][2] if queinfo[k][0]＝＝－1： queinfo[k][0]＝i else： 　　 ②　___________________　 　　 data[p][3]＝i queinfo[k][1]＝i p＝queinfo[k][1] 命题整体感知 尝试与研析 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 ''' queinfo[k][0]＝data[p][3] 命题整体感知 尝试与研析 读取2 组器件的数据，分别存入列表data1 和data2 中。2 个列表的每个元素包含3 个数据项，分别对应器件的送达时间、检测时长和优先级。data1 和data2 中的数据已分别按送达时间升序排列，代码略 读取优先级等级个数存入m中，代码略 ''' data＝merge(data1，data2) print(proc(data，m)) 命题整体感知 尝试与研析 【解析】 本题考查基于问题解决的程序综合阅读能力，涉及的知识点有程序基础、自定义函数、双指针、链式队列和顺序查找算法等。 (1)从表格中可以看出A 的优先级为2，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 为[[0，3，2]，[1，1，2]，[12，2，2]]，lst2 为[[2，1，1]，[4，3，0]，[11，3，2]]，结合自定义函数的程序，将具体数据代入，程序先在lst1 后添加len(lst2)个数据元素，再进行比大小，将较大值从后往前放入lst1 中，过程如下图所示，可知循环体执行了4 次。 命题整体感知 尝试与研析 ②若函数中while 语句的条件“j>＝0”误写为“k>＝0”，j 是指向lst2 的指针，则当lst2 中的数据已经处理完时，会出问题，故选项A正确。 (3)解决问题的方式是采用链表实现的队列，即链式队列，需要2 个指针来控制(头和尾)，二维列表queinfo就用来存储每个优先级的头尾指针。data 追加一个元素－1 用来存储下一个处理的指针。 ①整段自定义函数要计算平均等待时间，从total/n 可以看出，程序需要通过total＋＝curtime－data[p][0]累计total 值，因此①处答案为total＝0。 ②核心程序循环体部分框架比较明显，第1 个条件i<n and data[i][0]<＝ 命题整体感知 尝试与研析 curtime 成立的情况下，执行入队操作，第2 个条件waitnum>0 成立的情况下执行出队操作，最后else 部分执行更新curtime 操作。以数据data＝[[1，5，1]，[10，25，3]，[20，13，0]，[21，9，0]，[22，2，0]，[23，5，2]，[24，2，0]]为例，第1 个器件是时刻1到达的，先进入第3 个条件，更新curtime 为1，然后进入第1 个条件，根据优先级1，将器件索引0 入队，即queinfo[1]更新为[0，0]，接着进入第2 个条件进行处理，该器件的等待时间为0，curtime 更新为该器件处理完的时刻6，处理即出队操作，因为队列中没有其他等待器件索引，因此queinfo[1][0]更新为－1， 命题整体感知 尝试与研析 最终queinfo更新为[[－1，－1]， [－1， 0]， [－1，－1]， [－1，－1]]。处理第2 个器件时，curtime 更新为10，先入队， 即queinfo[3]更新为[1，1]，再出队，queinfo[3][0]更新为－1，queinfo 更新为[[－1，－1]， [－1，0]， [－1，－1]， [－1，1]]，curtime 更新为时刻35，该器件的等待时间为0。后面器件时入队时前面器件还没处理完，入队等待，第3 个器件到达时queinfo[0]更新为[2，2]，第4 个器件到达时queinfo[0]更新为[2，3]，第5 个器件到达时queinfo[0]更新为[2，4]，第7 个器件到达时queinfo[0]更新为[2，6]，队列queinfo[0]中存储的是优先级为0 的器件的 命题整体感知 尝试与研析 头尾索引，此过程通过queinfo[k][1]＝i 实现，在此之前需要更新data 中最后一个元素(存储指针区域)，让其指向下一个节点，由data[p][3]＝i 推理②处答案为p＝queinfo[k][1]。 ③出队时，[2，6]依次更新为[3，6]、[4，6]、[6，6]、[－1，6]，因此③处答案为queinfo[k][0]＝data[p][3]。 命题整体感知 尝试与研析 |随|堂|检|测| 1．小萌对文本数据进行加密处理，加密算法设计如下： 第一步：换位加密。将明文字符串首尾相接围成一圈，从第一个字符开始计数，计数到m时相应的字符出圈，然后从下一个字符重新计数，直到最后圈中的字符全部出圈。出圈的序列就是该换位加密后的密文。例如明文“abY82？”，密钥m＝4，按照上述规则得到的密文为“8baY？2”。 第二步：替代加密。将第一步得到的密文中的大小写字母和数字进行加密，密文字符由正常顺序的字母表或数字表右移m个位置替换得到。 命题整体感知 尝试与研析 例如当m＝4时，替换情况如图所示。当m＝4时，“8baY？2”经过处理后的密文为“2feC？6”。 请回答下列问题。 (1)明文字符串“5c－W”经过上述加密方法，密钥m＝3处理后的密文字符串为_________。 　－fZ8　 命题整体感知 尝试与研析 (2)小萌根据上述加密策略编写的Python程序如下，请在横线处填入合适的代码。 mingwen＝input(”请输入明文：　”) m＝int(input(”请输入密钥：　”)) q＝[”]*1000 miwen＝”” n＝len(mingwen) 命题整体感知 尝试与研析 for i in range(n)： q[i]＝mingwen[i] head，tail＝0，n i，s＝1，0 while i<＝n： tmp＝q[head]；head＋＝1 s＋＝1 命题整体感知 尝试与研析 if ①　________________________　： miwen＋＝tmp i＋＝1 s＝0 else： ②　__________________　 tail＋＝1 s＝＝m 或 s%m＝＝0 q[tail]＝tmp 命题整体感知 尝试与研析 ans＝”” for i in miwen： if i>＝”A” and i<＝”Z”： x＝chr((ord(i)－65＋m)%26＋65) #大写字母A的 ASCII码值为 65 elif i>＝”a” and i<＝”z”： x＝chr((ord(i)－97＋m)%26＋97) #小写字母a的 ASCII码值为 97 elif i>＝”0” and i<＝”9”： 命题整体感知 尝试与研析 ③_______________________________________________________　 #数字字符0的 ASCII码值为 48 else： 　　 x＝i ans＋＝x print(ans) 【解析】 (1)原始数据为5c－W，m＝3；第一步：换位加密，－cW5； 　x＝str((int(i)＋m)%10) 或 x＝chr((ord(i)－48＋m)%10＋48 ) 命题整体感知 尝试与研析 第二步：替代加密，－fZ8。 (2) “while i<＝n：循环”执行换位操作，其中s用于计数，是否达到了m；先出队列，tmp存储出队字符，如果计数达到m，则放入miwen字符串；计数没到m则重新入队；故①处用于判断计数是否达到m，答案为s＝＝m；②处是重新入队，答案为q[tail]＝tmp。“for i in miwen：”语句用于替代加密，③处是数字后移，答案为x＝str((int(i)＋m)%10) 或 x＝chr((ord(i)－48＋m)%10＋48)。 命题整体感知 尝试与研析 2．[2023·学军中学检测]某工厂有一批货物需要加工，现已知每批货物到达工厂的时间和需要加工的时间，为了提高加工的效率，工厂管理员想到两个加工的方法： ①先到先加工：按货物到达的时间顺序依次加工，若第i件货物正在加工，第i＋1件货物已经到达工厂，则需等待第i件货物加工完成后，才能开始第i＋1 件货物的加工。 ②优先加工“需加工时间”最短的货物：在已经到达工厂的货物中，找出“需加工时间”最短的货物进行加工，其他货物等其加工完后再加工； 已 命题整体感知 尝试与研析 到达工厂的剩余货物按同样的方法加工。 工厂管理员想知道按这两种不同的方法对货物进行加工，需要等待的时间分别为多少， 以便更好地选择加工方案。 某件货物的等待时间＝该货物开始加工的时间－该货物到达工厂的时间 总等待时间＝所有货物的等待时间之和 某批货物加工时间如下表所示： 命题整体感知 尝试与研析 (1)若上表中货物4的需加工时间改为4，则使用方案①进行加工，加工整批货物的总等待时间为________。 (2)按方案①进行加工的Python程序如下， 请在横线处填入合适的代码。 def FCFS(P，n)： 货物 到达时间 需加工时间 方案①等待时间 方案②等待时间 货物1 0 10 0 0 货物2 1 1 9 9 货物3 2 5 9 12 货物4 3 1 13 8 货物5 4 2 14 8 总等待时间 44 37 　47　 命题整体感知 尝试与研析 wait_time＝0 finish＝P[0][1] for i in range(1，len(P))： 　_________________________　# if P[i][1]<finish： 　　wait_time＋＝finish－P[i][1] return wait_time finish＋＝P[i－1][0] 命题整体感知 尝试与研析 (3)按方案②进行加工的Python程序如下，请在横线处填入合适的代码。其中，为了能快速地找出已到达工厂的所有货物中、加工时间最短的货物，可使用Python的优先队列类PriorityQueue，该队列类常用的方法如下表： 方法 示例 说明 PriorityQueue() q＝PriorityQueue() 创建一个优先队列q put(x) q.put(x) 将数据x加入队列q中 get() x＝q.get() 将队列q中的最小值出队，并赋给变量x empty() q.empty() 判断队列q是否为空，若为空返回True，否则返回False 命题整体感知 尝试与研析 def SJF(P，n)： wait_time＝cur_time＝0 q＝PriorityQueue() i＝0 while i<n or not q．empty()： if q．empty()： q．put(P[i]) 命题整体感知 尝试与研析 i＋＝1 eli f i<n and ①　_____________________　： 　　 q．put(P[i]) 　　 i＋＝1 else： 　　 min_p＝q.get() 　　 ②　_______________________________________ P[i][1]<＝cur time wait time＋＝cur time－min p[1]　 命题整体感知 尝试与研析 　　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) 【解析】 (1)从题目观察，货物4的加工时间增加3， 货物5的等待时间增加3。 命题整体感知 尝试与研析 (2)注意：本题未考虑上一货物已加工完成，但下一批货物未到加工厂的情况。默认情况是货物到加工厂等待加工，finish指上一货物加工完成的时间。 (3)①完成一项加工任务后，更新cur_time(某个货物的完成时间)，将到达时间在cur_time时间之前的货物都加入队列，等待挑选。这批货物全部入队后，才开始第三种情况：出队。 ②处更新等待时间， 现开始加工对内加工时长最短的物品，开始加工时间为：cur_time，故该货物等待时间为：开始时间－货物到达工厂时间。 感谢聆听，再见！ while ： $$