浙教版（2019）信息技术选考二轮复习系列专题配套练习——队列+算法综合二

队列+算法综合二 班级 姓名 1.【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]<finish: 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 i<n or not q.empty(): if q.empty(): q.put(P[i]) i+=1 elif i<n and ① : q.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) 2.【202211台州一模】为了让全班同学参加文艺汇演，小王设计了一个节目：先让k个同学同时出现在舞台上开始表演，当某1个同学率先完成他的表演部分，马上离开舞台，第k+1个同学会立即出现在舞台上并开始表演；当第2个同学离开舞台时，第k+2个同学也随即出现在舞台…… 以此类推，直到所有同学上台，当最后一个同学完成他舞台上的表演，节目结束。 由于表演时长有限，小王希望在表演限定时长tmax内，确定最少在舞台上同时表演的同学数量k。他根据上述要求编写 Python程序，读取n个同学的表演时长（秒），通过不断增加同时表演的人数k，找到第一个表演时长小于等于tmax的k值并输出。 (1)若有6位同装参加表演，他们的表演顺序及时长（秒）分别为“20，40，15，25，10，30”，同时在舞台表演的人数为3.则全部同学完成表演所需的时长为 秒。 (2)在计算表演时长的过程，为了快速获取舞台上最先完成表演的时间，.小王采用 Python中现成的优先队列类PriorityQueue，该类常用的方法如下图所示 实现上述功能的 python 程序如下，请在划线处填入合适的代码。 from queue import PriorityQueue