第二章 链表-浙江高中信息技术高三复习作业本

陶小波编写 11 第二章 链表 第一题 【来源 2023 年 11 月温州一模】 图 a 图 b (1) 某项目任务组信息如第 1题图 a 所示，部分领料过程如第 1 题图 b所示，结合题意， 第 4 时刻的领料队列是 (单选，填字母：A.2,1,0/B.2,1/C.2,0,1)。 (2) 定义如下 filte(task,st)函数。 def filte(task,st): i=0;j=0;n=len(task)-1 while j<=n: if task[j][0]==st: task[i]=task[j] i+=1 j+=1 return i 若 task 的值是[['A',0,3],['B',1,3],[B',2,6],['A',3,4],['A',4,5]],st 的值是“A”, 执行语句 m=filte(task,st)后，m的值是 陶小波编写 12 (3) 编写程序模拟任务组领料过程，输出每个任务组完成领料的时刻，部分 Python 程序如 下，请在划线处填入合适的代码。 ”所有任务组数据存入 task 列表，task[i]包含 3 项，task[i][0]为该任务组项目名称， task[i[1]为该任务组到达时刻，task[i][2]为该任务组原料需求量，数据按到达时刻升序 排列代码略" st=’A’ Print(proc(task,st))#输出该项目中每个任务组完成领料的时刻 陶小波编写 13 第二题 【来源 2023 年 11 月台州一模】 某工厂的业务较多，每个业务 i 都有对应的截止时间 ti 以及收益 vi,工厂每天最多能完成 k 个业务，且每个业务所需的加工时长相同。由于业务量多，有时候无法完成所有的业务，因 此工厂管理者需要对一段时间内的业务进行规划安排，以实现工厂累计收益的最大化。 例如工厂 3天内的业务明细如第 2题图 a 所示，已知工厂每天能够完成的业务量 k 为 2。为 了实现 3天的累计收益最大化,工厂安排的业务方案如第 2 题图 b 所示，这样工厂能够获得 最大累计收益为 105。 编写程序，实现在任意时间段内，根据每个业务的截止时间和收益，统计工厂在该时间段内 的最大累计收益。 图 a 图 b (1) 如第 2 题图 a 所示，若工厂每天能够完成的业务量 k 为 3,则工厂在 3 天内获得的最大 收益为 (2) 定义如下 insert(lst,head,pos)函数，参数 lst 是一个由列表模拟的链表结构数据， 其每个节点由收益数据和指向下一个位置的指针组成；参数 head 是其中一条链表的头指针， 由该指针构建的链表已经按收益数据升序排列；参数 pos 是某个节点的指针。函数功能是将 pos 节点插入到 head 指针指向的链表中，并保持链表按收益数据升序排列，最后返回头指 针数据。 陶小波编写 14 ①若函数加框处代码误写为“lst[p][0]<lst[pos][0]”,会导致某些情况下无法得到符合函 数功能的结果。调用 insert(lst,head,pos)函数，下列 4 组数据中能测试出这一问题的是 (单选，填字母) ②请在划线处填入合适的代码。 (3) 实现对每个业务完成时间的合理安排，使得工厂获得最大累计收益的部分 Python 程序 如下，请在划线处填入合适的代码。 “先输入规划安排的天数 n 和每天能够处理的最大业务量 k,代码略。 依 次 输入 m 个 业 务的 截 止 时间 t(t ≤ n) 和 收 益 v, 存 储 在数 组 tran 中 ， 如： [[1,25][1,10][2,15]],表示共有 3 个业务，第一个业务的截止时间为 1,收益为 25……,代 码略 3 ” 陶小波编写 15 陶小波编写 16 第三题 【来源 2023 年 11 月绍兴诊断】 在一个平面坐标系内，有 n 个矩形障碍物沿 x 轴从左向右依次排列(不存在障碍物竖直边重 合情况)。某机器人从原点出发，沿障碍物外围向右行进。现根据障碍物的位置信息，寻找 机器人的行进路线。 图 a 图 b 行进路线是由一系列“转折点”组成的序列，每个“转折点”用 x、y 坐标值来表示。每个 障碍物的位置信息由其左上顶点的坐标及宽度值来表示，如第 3 题图 a 所示，3 个障碍物的 位 置 信 息 为 [[1,3,4],[3,7,5],[7,5,3]], 最 后 得 到 的 行 进 路 线 为 [[1,3],[3,7],[8,5],[10,0]]。为了简化表示，行进路线中不需要存储连续相同高度的“转 折点”,如[1,3],[3,3]两个点只需保留[1,3]。具体寻找方法如下： ①计算出障碍物左上、右上顶点的坐标，并用“L”和“R”进行标记。根据每个顶点 的 x 坐标值升序排序； ②从左往右依次扫描障碍物的顶点。如果遇到左上顶点，将其高度值存储到序列中，若存储 高度值的序列最大值发生变化，则产生一个“转折点”;如果遇到右上顶点，从序列中删除 其高度值(若有重复值，只删除一次),若删除后存储高度值的序列最大值发生变化，也产生 一个“转折点”。 (1)定义函数 toPoint(boxes),功能为：计算障碍物左上、右上顶点的坐标，进行标记；再 根据 x 坐标值升序排序并返回结果，如第 3 题图 c 所示。具体 Python 代码如下： 图 c 陶小波编写 17 #将障碍物的初始位置信息存储于列表 boxes 中，其中 boxes[i][0]表示第 i 个障碍物左上 顶点的 x 坐标值，boxes[i][1]表示第 i 个障碍物左上顶点的 y 坐标值，boxes[i][2]表示第 i个障碍物的宽度值，代码略 若 boxes 的值是 [[1,3,4],[3,7,5],[7,5,3]],则调用函数 toPoint(boxes)时，语句 “ps[j+1]=ps[j]”的执行次数为 。 (2) 若经计算后障碍物位置信息是 [[1,5,'L'],[3,9,'L],[5,9,'L'],[6,9,'R'],[8,5,'R’],[10,7,'L'],[11,9,'R'],[15,7,R” ]],则得到的行进路线为：[[1,5], ,[15,0]](补全简化后的“转折点”,用逗号分 隔) (3) 实现寻找行进路线功能的部分 Python 程序如下，请在划线处填入合适的代码。 陶小波编写 18 陶小波编写 19 第四题 【来源 2023 年 11 月宁波一模】 某医院的看病流程为：患者通过网上、自助设备或人工窗口成功挂号后，到门诊的签到处签 到，签到成功后即可排队等待叫号就诊。简化的排队规则如下： ①当天 08:00 之前完成签到的患者，按照挂号顺序从小到大排队就诊； ②08:00 之后签到的患者，按照挂号的序号从小到大的次序插入候诊队伍中； ③队伍中前 3 名患者(包括正在就诊患者)视为已进入待诊状态，插队的患者只能插到这 3 名待诊患者后的队伍中。 假设医生从 08:00 开始叫号就诊，对每位患者的诊断时间均为 3分钟，忽略相邻患者就诊的 时间间隔。编写程序实现以下功能：若有患者签到，则根据规则更新候诊队伍；医生每完成 一名患者的诊断，电子屏幕上按顺序显示待诊的患者姓名和每个患者预计就诊的时间。 (1) 若当前已签到患者信息如下表所示： 则患者 F 的预计就诊时间为 (格式如 08:07:20)。 陶小波编写 20 (2)08:00:00 之前签到的患者原始数据存在列表 lst 中，每位患者信息包括姓名、挂号序号、 签到时间，以下函数将列表中的数据按挂号序号从小到大排序，并构建候诊队伍。 (3)每当一位患者就诊结束，更新队伍并按就诊顺序输出待诊的患者姓名和每个患者预计就 诊的时间。请补充程序划线处。 (4)若有患者签到，则更新候诊队伍。请补充程序划线处。 陶小波编写 21 陶小波编写 22 第五题 【来源 2023 年 11 月湖丽衢一模】 某快递驿站有 A、B 两类货架，收到的包裹重量小于等于 10 存放于 A 货架，其余存放于 B 货架。编写程序模拟生成取件码和顾客的取件过程，取件码是根据当前已处理的包裹数量生 成，如 A-0001 表示当天第一个处理的包裹存放在 A 货架，B-0003 表示当天第三个处理的包 裹存放在 B货架。取件码与顾客手机号关联，程序根据输入的手机号显示其所有包裹的取件 码，并允许顾客一次性提取或者部分提取。程序的部分运行界面如第 5题图 a和第 5题图 b 所示。 图 a 图 b (1) 当前已处理的包裹取件码是 A-0158,若下一个包裹重量是 12,其取件码为 。 (2) 定义函数 save(pnum,code),参数 pnum 为手机号，code 为取件码。函数功能是将一条包 裹信息存储到列表 goods 和列表 dic 中。如第 5题图 a 的包裹数据，手机号“180****1215” 在两个列表中的数据分别为 goods[4]=["B-0005",-1]、 goods[9]=["A-0010” ,4]和 dic[2]=["180****1215",9,2]。 ①若调用该函数继续存储手机号“180****1215”的包裹，其取件码是“B-0011”,则对应 dic[2]的值变为["180****1215", , ]。 ②函数 save 代码如下，程序中加框处代码有错，请改正。 陶小波编写 23 (3)实现取件功能的部分 Python 程序如下，请在划线处填入合适的代码。 陶小波编写 24 第六题 【来源 2023 年 11 月杭州一模】 某工厂生产的产品包含 n 个(编号为 0～n-1)组件，其组装可由多名工人共同协助完成。组 装时每个组件都不可遗漏并能按序完成，有些组件存在前置组件(以下简称“前置”),即安 装有先后顺序。例如，某产品有 6个组件，如第 6 题图 a所示，组件 3的前置是组 件 1 和组件 2,即安装组件 3 需要在组件 1 和组件 2 完成之后。若 0～5号组件的组装所需 单位时间分别为 2,5,2,4,3,5,则在工人数量不限的情况下，所有组件安装完成最短需要 14 个单位时间。 图 a 为了梳理产品组件的组装顺序，并计算所有组件安装完成所需的最短时间，编写程序模拟组 装过程：先同时组装前置总数为 0的组件，完成后更新每个组件的前置总数，再重复以上步 骤，直至所有组件安装完毕，程序运行结果如第 6 题图 b所示，请回答下列问题： 图 b (1) 第 6 题图 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 的前置总数。 陶小波编写 25 (3)定义如下 proc(n,s,pre)函数，该函数的返回值是列表 v,v[i]代表从开始到组件 i完成 组装所需的最短时间。请在划线处填入合适的代码。 组装编号 0～n-1 的单个组件所需时间存入 t 列表，组件前置关系存入 a 列表，如第 6 题图 a所需时间 t=[2,5,2,4,3,5];a=[[0,2],[2,3],[1,3],[3,5],[3,4]] 陶小波编写 26 (4)以下选项与题(3)加框处代码功能相同的是 (多选，填字母)。(注：全部选对的 得 2 分，选对但不全的得 1 分，不选或有选错的得 0分) A.head !=tail B.head <n C.tail <=n D.len(que)>0 陶小波编写 27 第七题 【来源 2023 年 10 月浙南名校】 某工厂将送达的各批次物品按品种打包。小李将各批次物品信息按送达时间顺序合并，得到 如第 7 题图 a-2 所示数据 data。同一个包裹只能装入同一品种任意批次的物品，当某一个 品种物品 A送达使得已送达的该品种物品总重量超过 m 时，则将在该物品之前送达的物品按 重量由大到小依次装入包裹，其余重量不足 m 的品种，按各品种依次装入包裹。编写程序， 读取物品合并更新后的信息，按送达时间顺序打包，输出各包裹中的物品序号，运行结果如 第 7 题图 b所示。 图 a-1 图 a-2 图 b 请回答下列问题： (1) 送达物品信息合并后如第 7 题图 a-2 所示，若包裹装入物品重量不能超过 8 千克，则首 先打包完成的包裹中装入品种为 0,各物品的序号依次是 。 陶小波编写 28 (2)定义 data_sort(lst)函数。先将数据(如第 7题图 a-1 中所示)合并得到 Ist 列表(如第 7 题图 a-1 中所示),函数 data_sort(Ist)的功能是对 Ist 列表按送达时间升序排列，并对序 号进行更新。 执行上述代码后， (填写：能/不能)正确得到如第 7题图 a-2 中的数据。 (3)实现上述功能的部分 Python 程序如下，请在划线处填入合适的代码。 合并后排序得到 n 件物品的数据存储在数组 data 中并输出，包裹最大承受最大重量为 m 千 克。物品品种的数量是 sn,代码略 陶小波编写 29 陶小波编写 30 第八题 【来源 2023 年 9 月百校起点】 某医院的团体体检流程如下： 编号登记：为 n位体检者设置体检编号 1～n。 体检呼叫：体检项目处空闲时呼叫下一个体检者(编号小的优先),若多个项目同时呼叫，体 检者到优先级小的项目处体检。仅考虑常规体检项目，各个项目的优先级及体检时间如第 8 题表 1所示： 表 1 前去体检：各个体检项目之间相互独立，互不影响；病人排队体检和体检完毕到下一科室之 间没有时间延迟。 (1)某日下午，仅 1 个团队 4 人(分别用编号 1,2,3,4 表示)参加体检，开始体检后第 5 分钟， 4在检查 (填写项目名称)项目。 (2)定义如下 lst(n)函数，生成 n人体检队列。若体检人数为 4 人，则 que 生成结果如第 8 题表 2所示。 表 2 陶小波编写 31 则执行语句 lst(4),que 的生成结果 (选填：是/否)相同。 (3)用 Python 程序模拟一个 10 人团队参加体检的流程。程序运行后，体检完成顺序如第 8题图 1 所示： 图 1 Python 部分程序如下，请在划线处填入合适的代码。 陶小波编写 32 陶小波编写 33 第九题 【来源 2023 年 8 月 Z20】 小明同学去看病，当他在一位医生的诊室门口等待就诊的时候，发现了叫号系统的页面上有 两行病人名单。第一行名单为正常排队等待就诊的序号，第二行名单为过号或检后再诊而等 待的序号。叫号的规则是先在第一行叫 2 个就诊序号，再到第二行叫 1 个就诊序号。小明同 学回家后将刚才发现的叫号规则编写了 Python 程序。 如第 9题图示例所示： 图①:当前到来的就诊序号是 3 号，为过号或检后再诊序号，进入第二行，先到达先就诊图 ②:当前到来的就诊序号是 4 号，为过号或检后再诊序号，进入第二行 图③:当前到来的就诊序号是 16 号，为正常排队等待就诊的序号，进入第一行，按就诊序号 顺序排列图④:开始叫号，按照正常排队等待就诊叫号 2 位，过号或检后再诊叫号 1 位，得 到新的顺序 (1)请在划线处填入合适的代码 陶小波编写 34 #a、b 初值，代码略 #如第 9 题图示例①所示：a=[[13,1],[15,2],[17,-1]];b=[3] 陶小波编写 35 第十题 【来源 2023 年 8 月 A9】 张三是一名计算机专业的大学生，为了帮助同学们学习专业相关的英语词汇，编写一个简易 字典程序。该程序中存放词汇数据库，在学习中输入英文单词，可以获得中文翻译结果。程 序中的词汇数据库采用链表方式存储，首字母相同时按升序排序。查找单词时，首先根据首 字母找到同首字母最小单词所在链表，再按照链表顺序查找该单词。 (1) 根据题意，部分的单词库数据逻辑结构如第 10 题图所示，查找单词”byte”的过程是” binary”→”bit”→"byte",补充图中空白单元格的值为 (2) wordlist(data,info)函数实现将词汇数据库 data 以链表的方式按字母序升序排列。 info 表示词汇数据库中各字母开头的最小单词位置，如 info[0]表示字母 a 开头的最小单词 在词汇数据库 data 中的位置。实现该功能的程序如下，请在划线处填入合适的代码。 陶小波编写 36 (3)searchword(data,info,key)函数实现单词的查找。程序如下，请在划线处填入合适的代 码。 陶小波编写 37 第十一题 【来源 2023 年 5 月柯桥卷】 操作系统在管理磁盘时，会将磁盘分为一个个“盘块”。在为文件分配空间时，可以将文件 装到离散的盘块中。读取一个文件时，首先在目录结构中找到文件项。从文件项中可以获取 文件名、存储时间、该文件在存储块中的起始地址等基本信息，但不包含文件具体内容，然 后在磁盘文件分配表中找到对应的文件。磁盘文件分配表如第 11 题图 1 所示。 文件结束块用-1 表示，空闲盘块用 0xff 表示。 目录结构 11 题图 1 (1)根据文件的起始地址，能方便地找到文件的其它盘块。如第 11 题图 1 中，文件 abc 在磁 盘中的盘块号依次是 (注：各盘块号用→分隔)。 (2)如果目录结构损坏，就不能获取文件的基本信息和起始地址。但我们可以借助文件分配 表来恢复部分数据(不考虑恢复文件名、存储时间等信息)。 函数 regain 的功能是模拟数据恢复，找到各个文件的起始地址和大小(盘块数量),并返回以 [[起始地址，文件大小],…]形式的列表 lst。变量 allot 存储文件分配表信息。 陶小波编写 38 若 allot 为[3,7,13,9,0xff,Oxff,Oxff,8,-1,-1,0xff;1,0,11,0xff,Oxff],调用 regain 函 数， ①则语句 Ist[j][1]=lst[j][1]+fsize 一共会被执行 次。 ②如果把 while p!=-1 and p not in visited 改写为 while p!=I,对程序的影响是 （多选） A.会增加 while 的循环体执行次数 B.返回的 Ist 中的节点数量保持不变 C.while 循环不能正常结束 D.返回的 Ist 中，文件的起始地址部分不正 确 (3)在创建文件时，若新文件需要占据 5 个盘块大小，只需要从头到尾找到空闲盘块，并依 次链接，并把首地址存放到文件项中。为了有效管理空闲块，我们可以将所有空闲盘区(每 个空闲盘区可以包括若干个空闲盘块)构建到一条空闲链 freelst 中。freelst 每个节点存 储本空闲盘区的盘块号、长度和指向下个盘块的指针，创建时把新节点链接到 freelst 尾部。 图 2 如第 11 题图 2 所示，共有 3 个空闲盘区，盘块号依次为 4、5、6、10、14、15 请在划线处 填上合适的代码。 陶小波编写 39 陶小波编写 40 第十二题 【来源 2023 年 5 月新昌临海卷】 程序运行时，以内存单元为基本单位对内存进行分配，若干个连续的内存单元称为一个内存 块，每个内存块的信息包含首地址和大小。编写 Python 程序模拟内存分配和释放的过程。 1)初始化空闲内存块，将信息存储在链表 flink 中。 2)分配大小为 size 的内存。先依次查找链表 flink 中是否存在不小于 size 的内存块。若存 在且等于 size,则将其从链表 flink 中删除；若存在且大于 size,则修改该内存块的信息； 若不存在，则对不连续的空闲内存块按顺序进行分配，如果空闲内存块之和仍小于 size,则 分配失败。 3)释放内存。将释放的内存块信息插入链表 flink,链表 flink 各节点按首地址从小到大排 列。如果释放的内存块与链表中的某个内存块相邻，则将它们合并成一个更大的内存块。请 回答下列问题： (1)初始空闲内存块大小为 16,进行两次分配和一次释放的过程如图所示。若继续分配大小 为 8 的内存块， (填写：能/不能)成功。 ①初始化空闲内存块，大小为 16 ②第 1次分配，大小为 4,分配后空闲 12 ③第 2次分配，大小为 8,分配后空闲 4 ④释放第 1次分配的内存，释放后空闲 8(不连续) (2)定义如下 allocate(flink,head,size)函数，参数 flink 是空闲内存块链表，head 是 flink 头指针，size 为所需内存块大小。函数功能为分配 size 大小的空闲内存块，并返回 分配的内存块信息及头指针 head。请在划线处填入合适的代码。 陶小波编写 138 （九）解析 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 第二章 链表 第一题 【来源 2023 年 11 月温州一模】 （1）B （2）3 （3） ①p=i ②k=task[p][3] ③task[p][3]=task[k][3] 第二题 【来源 2023 年 11 月台州一模】 （1）135 （2） ①B ②lst[q][1]=pos （3） ①info[cur][0]=pos 或 info[cur][0]=len(lst)-1 ②p ③lst[p][0] 第三题 【来源 2023 年 11 月绍兴诊断】 （1）2 （2） [3,9][11,7] （3） ①que.append([t[1],h]) ②que[que[p][1]][0]!=t[1] 或 que[p][1]!=-1 and que[que[p][1]][0]!=t[1] ③preHeight=que[h][0] 第四题 【来源 2023 年 11 月宁波一模】 （1）08:09:00 （2）D （3）t%3600//60 （4） ①head=len(lst)-1 陶小波编写 139 ②k<3 or data[1]>lst[q][1] 第五题 【来源 2023 年 11 月湖丽衢一模】 （1）B-0159 （2） ①10、3 ②dic[num][2]+=1 （3） ①head=dic[num][1] ②q=goods[q][1] 第六题 【来源 2023 年 11 月杭州一模】 （1）13 （2）pre[y]+=1 （3） ①t[i]+v[i] ②result[j],result[j+1]=result[j+1],result[j] （4） AB 第七题 【来源 2023 年 10 月浙南名校】 （1）3 1 （2）不能 （3） ①b[k][1] ②x[i]=p ③p!=-1 and data[i][4]<=data[p][4] 第八题 【来源 2023 年 9 月百校起点】 （1）胸透 （2）是 （3） ①f[num]=que[p][0] ②time-t[i]==dis[i][1] ③n-1,-1,-1 第九题 【来源 2023 年 8 月 Z20】 （1） ①head_a 或 a[0][0] ②a[p][1] ③len(a)-1 ④b[head_b] 陶小波编写 140 （2） p!=-1 and i<2 或 p!=-1 and i<=1 第十题 【来源 2023 年 8 月 A9】 （1）2 （2） ①k=ord(d[0])-ord(“a”) ②q !=-1 and d>data[q][0] ③info[k]=i （3） data[p][1] 第十一题 【来源 2023 年 5 月柯桥卷】 （1）9-4-3-7 （2） ①2 ②AD （3） ①j<n and allot[j]=0xff ②cur=freelst[cur][2] 或 cur=len(freelst)-1 ③freelst[p][0]+i 第十二题 【来源 2023 年 5 月新昌临海卷】 （1）能 （2） ①cur=flink[cur][2] ②flink[pre][2]==flink[cur][2] （3） ①cur==head ②flink[pre][1]=flink[pre][1]+flink[cur][1] 第十三题 【来源 2023 年 4 月天域卷】 （1） 6.5 （2） D （3） ①ok=0 ②a[pre][3]=a[head][3] ③okinfo[num]=1 第十四题 【来源 2023 年 4 月绍兴二模卷】 （1） 224 （2） 3 [3,4,1,2] （3） ① free[lst[i]][1]<size 陶小波编写 141 ② address=free[curr][0] ③free[curr][0]+=size 第十五题 【来源 2023 年 3 月温州二模卷】 （1） 600 （2） AD （3） ① lst[j][1]==i+1 ② q[k][1]=j ③val+=v 或 val+=lst[k][2] 第十六题 【来源 2023 年 8 月名校协作体】 （1） 8 （2） [t,link[p][1]] （3） C （4） ① 3+(length*3)*2 ② g=fun() 第十七题 【来源 2023 年 11 月稽阳联考】 （1） 60 （2） A （3） ① head=t ②(a[head][2]-a[head][1])*(a[p][2]-a[p][1]) ③p=a[pre][3] 第十八题 【来源 2023 年 12 月 Z20】 （1） 3 （2） ① pos[tail] ②cful[pos[i]]+1 ③cful[c]=i ④top-=1 第十九题 【来源 2023 年 12 月嘉兴一模】 （1） 5000 （2） lst （3） ① tlist[k][1]=i ②y=tlist[k][0] ③total=total+orders[y][1] （4） p!=-1 and orders[p][0]!=ddh 第二十题 【来源 2023 年 12 月精诚联盟】 （1） A24 （2） ① ht[i]=h ②b[h][1]=q （3） ③insert(len(b)-1,ord(w[o])-65) （4） B 陶小波编写 142 第二十一题 【来源 2023 年 12 月强基联盟】 （1） 13 （2） 3 （3） ① k=path[i][0] ②p=head[i] ③curtime+=cmpt[p][0] 第二十二题 【来源 2023 年 12 月台州名校】 （1） 4 （2） lst[lst[x][1]][0]=lst[x][0] （3） ① data[i]!=data[i-1] ②head+=1 ③data[t]!=data[lst[t][0]] 第二十三题 【来源 2023 年 12 月县域名校】 （1） 沈*思 （2） ① （a([p][2]>=80 or a[p][0]<a[i][0]） ②a[head][4] ③left+=1 （3） 3 第二十四题 【来源 2023 年 12 月浙江四校】 （1） 015432 （2） ① B ②B （3） ① pre[kc[i][1]]+=1 ②pre[i]==0 ③que[tail]=link[u] 第二十五题 【来源 2023 年 12 月诸暨模拟】 （1） 125,2,110 （2） ① sp[j][1]<0 ②sp[i][1]<sp[pre][1] ③anext[pre]=i ④p==-1 第二十六题 【来源 2022 年 12 月诸暨诊断】 （1） ① link[n-1][0]==link[p][0] ②link[q][2]=n-1 （2） link[p][2]!=2 第二十七题 【来源 2022 年 12 月浙里卷天下】 （1） ① q=b[q][2] ②c[j][1]>=cj[j-1][1] ③i>=n*0.1 and cj[i][1]<cj[i-1][1] （2） 冒泡排序 235 第二十八题 【来源 2023 年 1 月高考真题】 (1) 6 (2) ① 4 ② A 陶小波编写 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