第三章 栈与队列-浙江高中信息技术高三复习作业本

陶小波编写 86 第三章 栈与队列 第一题 【来源 2023 年 5 月新阵地】 有 n 位用户需要办理事务，每位用户的信息包含到达时间及办理时长。共有 m 条通道可以进 行办理。每位用户均选择完成事务时间最早的通道入队，若存在多条相同完成时间的通道， 则选择编号靠前的通道入队(在某条通道入队，则表示该条通道中前一位用户出队)。每条通 道每办理 5个用户的事务后，将休息 10 分钟。 编写程序模拟办理过程，先按到达时间加工数据，然后计算所有用户的平均等待时长，其中 每位用户的等待时长为其开始办理的时间与其到达时间的时间差。(时间单位为分钟)请回答 下列问题： (1)结合题意，若有 3 条通道可以办理事务，则用户 D 的等待时长为 (填数字)分钟。 (2)定义如下 procl(rawdata)函数，参数 rawdata 的每个元素由到达时间及办理时长构成， 并已按到达时间升序排列形[['09:01',7],['09:01',13],['09:02',5],['09:04',9]……]。 函数功能是计算到达时间与 9点整相差的分钟数，并将其追加至 rawdata 的每个元素中。 下列选项中，符合划线处功能要求的是 (多选，填字母)。(注：全部选对的得 2 分， 选对但不全的得 1 分，不选或有选错的得 0分) A.rawdata[i][0][3:] B.rawdata[i][0][-2:] C.rawdata[i][0][:-3:-1] D.rawdata[i][0][-2::-1] 陶小波编写 87 (3)计算所有用户平均等待时长的部分 Python 程序如下，请在划线处填入合适的代码。 读取原始数据，存入列表 rawdata 中，该列表的每个元素包含 2 个数据项，分别对应用户的 到达时间及办理时长。rawdata 中的数据已按到达时间升序排列，代码略读取可办理事务的 通道数存入变量 m 中，代码略 data=proc1(rawdata) print(proc2(data,m)) 陶小波编写 88 第二题 【来源 2023 年 5 月卓越联盟】 某游戏中有一密码锁，由 n 个拨轮组成，每个拨轮有十个数字，每个拨轮从 0'到 9 可以正 反两方向自由旋转，例如旋转一次可从 0'转到 1或'9'。其中锁还带有引爆装置，若不小心 拨到与爆炸数组 bz 中的任一状态相同或者解锁时间过长，则启动爆炸，表示解锁失败。小 明在游戏中发现，能通过游戏获取到锁的解锁状态及引爆状态的相关提示，但经常由于转动 时间超时而不能解锁。假设拨轮每旋转一次用时相等，为尽快解锁，则应尽可能减少旋转的 次数。现用 Python 编写程序：在旋转的次数尽可能少的前提下，输出从初始状态到解锁状 态的解锁过程(如有多个转动次数相同的解锁过程，只需输出一种即可)。程序运行界面如图 所示： 请回答下列问题： (1)在上图所示例子中，若锁的引爆状态增加一组数据"0100",则根据程序运行，输出结果为： 最快解锁过程需旋转 次 (2)程序部分代码如下，请在划线处填入正确的代码。 (3)程序中加框的代码有误，运行中发现在输出正确解锁过程的同时，有时也会输出"无法找 到安全解锁方案",则需将加框处代码修改为 陶小波编写 89 陶小波编写 90 第三题 【来源 2023 年 4 月杭州】 某工厂需要加工 n 批货物，但同一时间只能加工同一批货物。货物的信息包含送达时间、加 工时间和是否加急(0 表示不加急，1表示加急),每批货物的送达时间各不相同，已送达的货 物按照是否加急分别排队，先到达先入队，每次加工都优先处理加急货物队列，选取队首货 物出队进行加工(同一时刻出现入队和出队时，先处理入队)。求出所有货物的平均等待时长， 其中每批货物等待时长为其开始加工的时间与送达时间的时间差。 (1)由题意可知，第 16 题图中待加工货物 A、B、C、D、E 的加工顺序应为 A-C-B-E-D。A、C、 B、E 的等待时长分别为 0、0、2、1、那么 D 等待时长为： (2)实现模拟加工过程并计算平均等待时长的部分 Python 程序段如下，请在划线处填入合适 代码。 (3)加框处代码错误，请改正。 “” 读取 n批待加工货物信息存于列表 data,data 中的数据已经按货物送达时间升序排列。例如 存储题中实例的数据：data=[[”A”,0,2,0],[”B”,1,3,0],[”C”,2,1,1],[”D”,4,2,0],[” E”,5,2,1]] “” 陶小波编写 91 陶小波编写 92 第四题 【来源 2022 年 12 月学军】 某工厂有一批货物需要加工，现已知每批货物到达工厂的时间和需要加工的时间，为了提高 加工的效率，工厂管理员想到两个加工的方法。 ● ①先到先加工：按货物到达的时间顺序依次加工，若第 i 件货物正在加工，第 i+1 件货 物已经到达工厂，则需等待第 i 件货物加工完成后，才能开始第 i+1 件货物的加工； ● ②优先加工“加工时间”最短的货物：在已经到达工厂的货物中，找出“加工时间”最 短的货物进行加工，其他货物等其加工完再加工；已到达工厂的剩余货物按同样的方法加工。 工厂管理员想知道按这两种不同的方法对货物进行加工，需要等待的时间分别为多少，以便 更好选择加工方案。 · 某件货物的等待时间=该货物开始加工的时间-该货物到达工厂的时间 · 总等待时间=所有货物的等待时间之和 如某批货物加工时间如下表所示。 (1)若上表中货物 4 需加工的时间改为 4,则使用方案①进行加工，加工整批货物的总等待时 间为 。 (2)按方案①进行加工的算法如下，请在划线处填入合适的代码。 (3)按方案②进行加工的算法如下，请在划线处填入合适的代码。其中，为了能快速的找出 已到达工厂的所有货物中、加工时间最短的货物，本算法使用 Python 的优先队列类 PriorityQueue,该队列类常用的方法如下： 陶小波编写 93 （4）主程序如下： 陶小波编写 94 第五题 【来源 2022 年 12 月 Z20】 一面木板墙，每块木板的宽度都是 1,现在想在木板墙上沿着平行于地面的方向切割出一块 矩形区域。如果知道每块木板的高度，如何切出的矩形面积最大?木板墙如第 5 题图所示： 图中有 7块木板，每块木板的高度分别为：2、4、4、3、5、1、1。尝试后，我们发现最大 的矩形就是波浪图案部分所示。也就是切割了高度为 4、4、3、5 四块木板，形成了一个高 度为 3,宽度为 4的矩形，这个最大面积为 12。 经过尝试，可以发现：切下来的最大矩形，一定是以最大矩形所在的区域中最短的那块木板 为矩形的高度值。 这样我们可以枚举每一块木板，每次都以当前木板作为高度。就是把当前木板当成是切出来 的矩形区域中最矮的木板，然后分别向左右延伸，切出此时的最大矩形区域。当把所有的木 板都尝试过一遍后，我们在所有的结果中比较出最大值，这个最大值就是我们要求的最大矩 形面积。如果木板的数量为 n,那么这种算法的时间复杂度接近于 0(n²)。但是，如果利用好 栈这种数据结构，就能快速的定位左右延伸的最远位置，将算法的时间复杂的降低到 0(n)。 实现上述时间复杂度为 0(n)的 Python 程序代码如下，完成以下问题。 (1)如果 7 块木板从左往右依次的高度是 2、1、4、5、1、3、3,切割出来的最大矩形面积是 陶小波编写 95 (2)完成划线处代码。 陶小波编写 143 (3) ① total=0 ② p=queinfo[k][1] ③ queinfo[k][0] =data[p][3] 第二十九题 【来源 2023 年 6 月高考真题】 (1) 8 (2) 1 (3) ① range(m) ② k=task[k][1] ③ w[k] =w[task[k][1]]-task[k][0] 第三十题 【来源 2024 年 1 月高考真题】 (1)1,8 (2)①B ②4 次 (3)①data[i][1]-=m ②j=data[i][1] ③b[j-data[i][1]].append(v) 第三十一题 【来源 2024 年 3 月温州二模】 (1) 10 或者“10” (2)ml (3)①p=lst[p][3] ②1st[ml][1]+lst[m2][1] ③prem2 ==ml 第三章 栈与队列 第一题 【来源 2023 年 5 月新阵地】 （1）3 （2）AB （3） ①que[x][head[x]]-data[i][2] ②data[i][2]+data[i][1] ③tail[x]%5==0 或 head[x]%5==4 第二题 【来源 2023 年 5 月卓越联盟】 （1）4 （2）①p=father[p] ②xz(strNum[i],type) ③tail+=1 （3）que[head-1]!=mbz 第三题 【来源 2023 年 4 月杭州】 （1）4 （2）①k==1 陶小波编写 144 ②i+=1 ③sum+=curtime-datat[p][1] （3）HeadA!=tailA or headB!=tailB 第四题 【来源 2022 年 12 月学军】 （1）47 （2）finish+=P[i-1][0] （3）①P[i][1]<=cur_time ②wait_time+=cur_time-min_p[1] 第五题 【来源 2022 年 12 月 Z20】 （1）8 （2） ①h[st[top]]>=h[i] ②L[i]=st[top] ③(R[i]-L[i]-1)*h[i] 第四章 排序 第一题 【来源 2022 年 12 月精诚联盟】 （1）6 （2） ①a[j][2]>a[k][2] ②break （3） ①index=idx[m] ② a[index][1]<key 第二题 【来源 2022 年 12 月强基联盟】 （1）B （2） ①a[i][0:b+2:b+1] ②res[j][1]<res[j-1][1] ③(i+1)*n （3）ABC 第三题 【来源 2022 年 12 月北斗联盟】 （1） ①i+=2 ②d[j][1]<d[j+1][1] ③f[d[i][0]]=1 ④change(diff,qA,qB) 第四题 【来源 2024 年 3 月 9+1 联盟】 (1)57 (2)8