资源简介

专题18　基于数据结构的算法实现
学习目标　1.掌握队列中元素入队和出队的条件；
2.掌握链表的构建方法.
队列是线性结构的一种，因此也可以用链式结构的方式来实现。并且链式结构的队列，由于节点空间都是在入队的时候动态申请的 ，因此在计算机内存空间足够的情况下，一般不需要考虑队满的情况，也就不存在溢出的情况，所以不需要使用循环链式队列来处理假溢出的情况。 链式队列在链表的链尾插入元素，然后让队尾指针指向链尾元素。链式队列的出队，就是将链表的首元节点从链表中删去，让其后继节点成为首元节点，然后让队头指针指向该节点。
(2024年1月浙江省选考)某项活动有n个单位(编号1到n)参加，需将员工分成若干个小组，每个小组的人数上限为m，小组编号按新建次序从1开始编号。分组时，首先按单位编号次序依次在各单位内部分分组，每m人分配到一个新建小组中，不足m人的剩余员工暂不分配；然后按剩余员工人数由大到小的顺序，依次为各单位剩余员工分配小组。
若某单位剩余员工人数为k，则分配方法为：在已建的小组中查找空位数(该小组还可容纳的人数)大于或等于k的小组，如果找到的小组有多个，则选择空位数最少的小组，将此k人分配到该小组中；如果没有找到，则新建一个小组，将此k人分配到该小组中。
设n为5，m为20，各单位员工人数及单位内部的分组过程如图a所示，各单位剩余员工的分组过程如图b所示。
编写程序：给定各单位编号及员工人数，根据上述方法进行分组处理，按单位编号次序输出各单位所分配的分组编号。请回答下列问题：
(1)由题意可知，若仅将图a中1号单位的员工人数修改为25，然后对图中5个单位重新分组，则1号单位所分配的分组编号为________。
(2)定义如下bubble_sort(lst)函数，参数lst的每个元素由单位编号和剩余员工人数2个数据项组成。函数的功能是根据每个单位的剩余员工人数，对lst进行降序排序。
def bubble_sort(lst):
　 n＝len(lst)
for i in range(0, n－1)：
　 return
调用该函数，若lst为[[1，0]，[2，0]，[3，18]，[4，0]，[5，19]，[6，17]]，请回答①和②两个问题。
①虚线框中的程序段第1次执行后，关于lst中的剩余员工人数，下列说法正确的是________(单选，填字母)。
A.lst[0][1]数值最小 B.lst[0][1]数值最大
C.lst[5][1]数值最小 D.lst[5][1]数值最大
②虚线框中的程序段执行的次数为________。
(3)实现分组功能的部分Python程序如下，程序中用到的列表函数与方法如图c所示，请在程序中划线处填入合适的代码。
函数与方法 功能
w.append(x) 在列表w末尾添加元素x
x＝w.pop() 将列表w末尾元素赋值给x，并将其从w中删除
图c
def group(data, m):
　 n＝len(data)
　 a＝[]
　 for i in range(n＋1)：
　 a.append([])　#a[i]初始化为空列表，存放编号为i的单位所分配的分组编号
　　gnum＝0
　　for i in range(n)：　#各单位内部分组
　 while data[i][1]>＝m：
　　　 gnum＋＝1
　　　　　 k＝data[i][0]
　　　 a[k].append(gnum)
　　　 ①________
　　bubble_sort(data)　#根据每个单位的剩余员工人数，对data进行降序排序
　　b＝[]
　　for i in range(m):
　b.append([])
　　i＝0
　　while i　 ②________
　 while j　　　 j＋＝1
　 if j　　　 v＝b[j].pop()
　 else：
　　　 gnum＋＝1
　　　 v＝gnum
　 a[data[i][0]].append(v)
　 ③________
　 i＋＝1
　　#输出各单位的分组编号，代码略
'''
读取小组人数上限存入 m；读取 1 至 n 号单位的数据，依次存入列表 data 的 data[0]至 data[n－1]中。data[i]包含 2 个数据项，data[i][0]，data[i][1]分别存放单位编号及员工人数，代码略
'''
group(data, m)
重难点1　构建链表建立索引关系
高中阶段的数据结构不是讨论如何使用数据结构，而是通过对数据集进行简单的操作，理解和创建数据结构。能将有限制条件的、真实情境中的数据关系进行抽象，根据数据特点与求解要求，选择适当的数据类型表示各种数据，并用合适的数据结构表达数据的逻辑关系。在已有数据集的基础上，通过链接关系构造逻辑上先后遍历顺序，构建链表，将有层次非线性结构或二维数组转换为一维数组，再遍历一维数组，得到问题的解。当原始数据量大，且每个数据元素有多个数据项时，直接对进行复制会浪费大量空间和时间，可进行基于索引的引用，提高效率。
例题 有2组器件共n个，要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先级。优先级有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均已按送达时间升序排列。函数功能是将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”，会导致某些情况下无法得到符合函数功能的结果。调用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程序如下，请在划线处填入合适的代码。
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：
　　　 k ＝ data[i][2]
　　　 if queinfo[k][0] ＝＝ －1：
　　　　　 queinfo[k][0] ＝ i
　　　 else：
　　　　　 ②　　　　
　　　　　 data[p][3] ＝ i
　　　 queinfo[k][1] ＝ i
　　　 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
'''
读取2组器件的数据，分别存入列表data1和data2中。2个列表的每个元素包含3个数据项，分别对应器件的送达时间、检测时长和优先级。data1 和data2中的数据已分别按送达时间升序排列，代码略
读取优先级等级个数存入m，代码略
'''
data ＝ merge(data1， data2)
print(proc(data， m))
变式 某工程包含n个任务(编号为0～n－1)，每天可以有多个任务同时进行。某些任务之间有依赖关系，如图a所示，任务4依赖于任务1，任务1依赖于任务2。即任务2完成后才可以开始任务1，任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务，或多个任务依赖于同一个任务的情况。现已对该工程的依赖关系进行了梳理，结果如图b所示，标记“T”表示依赖关系需保留，标记“F”表示依赖关系需删除。
根据每个任务完成所需的天数和梳理后的依赖关系，编写程序，首先删除标记为“F”的依赖关系，然后计算工程最快完成所需的天数，并以工程最快完成所需的天数为期限，计算每个任务最晚必须开始的时间。
图a
任务A 任务B 标记
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注：任务a依赖于任务b。
图b
请回答下列问题：
(1)若某工程有6个任务，任务间依赖关系如图a所示，完成任务0～5所需天数分别为2，1，3，5，1，6，则工程最快完成需要　　　　天。
(2)定义如下erase(lst)函数，参数lst列表的每个元素表示一个依赖关系。函数的功能是删除标记为“F”的依赖关系，返回保留的依赖关系的个数。
def erase(lst)：
　 i＝0
　 j ＝ len(lst)－1
　 while i<＝ j：
　 if lst[i][2]＝＝ 'T'：
　　　 i＋＝1
　 else：
　　　 if lst[j][2] ＝＝ 'T'：
　　　 lst[i]＝lst[j]
　　　　 i ＋ ＝ 1
　　　 j － ＝ 1
return i
若lst列表依次存储图b所示的依赖关系，如lst[0]为[0，5，'T']，调用erase(Ist)的数，则语句“lst[i] ＝lst[j]”的执行次数为　　　　。
(3)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
def proc(n，lst，task)：
　 pr＝[0]*n
　 w＝[0]*n　#w[i]存放任务1最晚必须开始的时间
　 m＝erase(lst)
　 for i in ①　　　　：
　　 task[lst[i][1]][1]＝lst[i][0]
　　 pr[lst[i][0]]＝1
　 c＝[]
　 days＝0　#days存放工程最快完成所需的天数
　 for i in range(n)：
　 if pr[i]＝＝0：
　　　 k＝i
　　　 s＝0
　　　 while k！＝－1：
　　　　　　 c.append(k)
　　　　　　 s＋＝task[k][0]
　　　　　　 ②　　　　
　　　 if s>days：
　　　　　　 days＝s
　　for i in range(n－1，－1，－1)：
　　 k＝c[i]
　　 if task[k][1]＝＝－1：
　　　　 w[k]＝days－task[k][0]＋1
　　 else：
　　　 ③　　　　
　　　#输出days，以及保存在w中的每个任务最晚必须开始的时间，代码略
'''
工程包含的任务数存入变量n
任务间的依赖关系存入1st列表
1st[0]包含3项，任务1st[i][0]依赖于任务1st[i][1]，1st[i][2]存放保留/删除标记，任务数据存入task列表
task[i]包含2项，task[i][0]为完成任务所需天数，task[i][1]的初值为－1
代码略
'''
proc(n，lst，task)
重难点2　构建数组存储临时数据
针对情境较为复杂、结构化程度较低的问题，能抽象数据特征、创造性地运用数据结构优化算法。数据往往经过采集、传输、处理和存储的过程，而数据在加工处理过程中，要考虑算法的优越性，提高算法的效率。数据在加工过程中，临时存放的数据可以存储在队列、栈和二维数组中，利用其不用查找就可以操作或者把当前正在处理的数据放置一个较小的数组中的特性，加快数据的处理时间。
例题 某店使用加工设备制作m种类型的甜品，每分钟只能制作一种类型，且不超过n个。每个订单包含订单编号、下单时间、类型和数量。编排制作顺序的规则为：下单时间早的类型优先，下单时间相同时数量多的类型优先。下单时间最早的订单数量不足n，可以先制作部分已下单相同类型甜品。每分钟完成后，有新增订单时，合并相同类型订单，按上述规则重新编排顺序，若编排后，新订单仍有剩余，则剩余数量按实际下单时间继续参与编排。
设m为3，n为10，某时段各个订单如图a所示，则制作甜品的顺序为AABACB，数量为10、10、10、4、8、5，如图b所示。编写Python程序，根据订单，输出甜品的制作顺序和数量。
订单编号 下单时间 类型 数量
0406001 8：01 A 24
0406002 8：01 B 3
0406003 8：03 C 8
0406004 8：03 B 12
图a
图b
(1)如图a所示，若订单0406003提前到8：01下单，则制作顺序为　　　　。
(2)定义如下least(tpr，ud，m)函数，参数tpr存储当前各类甜品的下单时间，如tpr＝[[481，482]，[]，[]]表示当前A类型有8：01(将字符串时间格式8：01转换为分钟数字481)和8：02共2个订单，B和C无订单。参数ud存储当前各个类型的订单数量之和，如ud＝[4，0，0]表示当前A类型所有订单数量和为4，B和C无订单。参数m表示甜品种类。函数功能是查找当前待制作甜品的类型。
def least(tpr，ud，m)：
　 post＝0
　 for i in range(1，m)：
　 if len(tpr[i])>0：
　　　　 if
：
　　　　　　post＝i
　　　　elif tpr[i][0]＝＝tpr[post][0]：
　　　　　　if ud[i]>ud[post]：
　　　　　　　 post＝i
　　　return post
若加框处条件误写为“tpr[i][0]A.tpr＝[[481]，[481]，[482，483]]
ud＝[2，25，5]
B.tpr＝[[]，[482]，[482，483]]
ud＝[0，3，2]
C.tpr＝[[481，485]，[]，[482，483]]
ud＝[2，0，5]
D.tpr＝[[481，485]，[]，[]]
ud＝[2，0，0]
(3)实现上述功能的部分Python程序如下，程序中用到的列表函数与方法如下表所示，请在划线处填入合适的代码。
函数与方法 功能
w.append(x) 在列表w末尾添加元素x
w.pop(i) 删除列表w索引为i的元素
sum(w) 累加列表w中的元素
#读取各个订单的数据，存入列表lst，每个元素包含订单编号、下单时间、类型和数量。lst中的数据已按下单时间升序排列，代码略。
#读取甜品种类和每分钟最多加工的数量，分别存入变量m和n，代码略。
def convert(s)：
　 #将字符串格式时间s转换成分钟数，如convert(″08：00″)的值为480，代码略。
tpr＝[[]for i in range(m)]
npr＝[[]for i in range(m)]
ud＝[0 for i in range(m)]
curtime＝convert(lst[0][1])　#当前时间为第1个订单的下单时间
i＝0
while i 0：
　　while i　 t＝ord(lst[i][2])－ord(″A″)
　 tpr[t].append(convert(lst[i][1]))
　 npr[t].append(lst[i][3])
　 ①　　　　
　 i＋＝1
　　k＝least(tpr，ud，m)
　　tot＝0　　
　　while　ud[k]>0 and tot　 if 　 ②　 ：
　　　 ud[k]－＝npr[k][0]
　　　 tot＋＝npr[k][0]
　　　 tpr[k].pop(0)
　　　 npr[k].pop(0)
　 else：
　　　 npr[k][0]－＝n－tot
　　　 ud[k]－＝n－tot
　　　 tot＝n
　　　 #输出当前时间加工的甜品类型及数量，代码略
　　　 curtime＋＝1
　　　 if i　 ③　　　　
变式 有新订单产生。公司安排的打包工作时间为12：00－18：00，假设当日订单在工作时间内就能完成。公司有甲、乙、丙三位师傅对货品进行打包，货品按照甲、乙、丙的顺序分配给各师傅处理，每位师傅一次打包一件货品。打包规则：若下单时间相同，优先级越高(数字越小，优先级越高)的货品，先全部打包完成；若不同，则下单时间更早的货品先处理完成。
订单输入格式示例：7A2B、4B10A(说明：4B10A指订单中有4件B类货品，10件A类货品)。编写程序，输出某天甲、乙、丙货品打包顺序和打包报酬，甲的输出示例：3A5B1C，200元。
货品 优先级 打包报酬(元/件)
A 1 30
B 2 20
C 3 10
表1
下单时间 货品及数量
12：00 2B7A
14：00 7B
15：00 6B5C
表2
(1)若某天货品下单信息如表2所示，则甲的打包顺序为3A5B1C，乙的打包报酬为　　　　元。
(2)定义如下convert(data)函数，参数data为一个订单，包括货品和数量，函数功能将订单转换成货品名称序列，如订单2B1A1C转换成ABBC。请在划线处填上合适的代码。
def convert(data)：
　 num，q ＝ 0，″″
　 qsort ＝ [″″，″″，″″]
　 for i in range(len(data))：
　 if data[i] >＝″0″ and data[i] <″9″：
　　　 num ＝ 　　　　
　 else：
　　　 for j in range(num)：
　　　　　 q ＋＝ data[i]
　　　 qsort[ord(data[i])－ord(″A″)] ＝ q
　　　 num，q ＝ 0，″″
　　　s ＝ qsort[0]＋qsort[1]＋qsort[2]
　　　return s
(3)实现该功能的 Python 主程序如下，请在划线处填入合适的代码。
goods ＝ [30， 20， 10]
m ＝ (18－12)*2　#12：00－18：00之间每半个小时为一个时间节点
b ＝ [ ]
for i in range(m)：
　 b.append(″″)　#append()用于在列表的末尾添加一个元素
a ＝ [[″12：00″，″2B7A″][″14：00″，″7B″]，[″15：00″，″6B3C″]]
for i in range(len(a))：
　 que ＝ convert(①　　　　)
　 x ＝ (int(a[i][0][0：2])－12)*2　#将时间转换为对应的结点
　 while len(b[x]) ＝＝ 3：
　　　 x ＝ x＋1
　 while len(que) > 0：
　　 t ＝ 3－len(b[x])
　　 if len(que) < t：
　　　 t ＝ len(que)
　　 b[x] ＝ ②　　　　
　　 if t ＝＝ len(que)：
　　　 que＝″″
　　 else：
　　　 que ＝ que[t：]
　　 x ＋＝ 1
s1， salary ＝″″， 0
for i in range(m)：　#甲处理顺序和打包报酬输出
　 if b[i] ！＝″″：
　　 s1 ＋＝ b[i][0]
　　 salary ＋＝③　　　　
#将s1中形如“ABBCC”的格式，转换成“1A2B2C”的格式，代码略
print(″甲处理顺序和打包报酬：″， s1， str(salary)＋″元″)
#乙、丙处理顺序和打包报酬输出略
重难点1　构建链表建立索引关系
1.某花瓶厂有三台不同型号的机器，可生产ABC三种不同型号的花瓶。厂家每天会收到很多网上订单，每个客户的订单信息包含订单号、型号、数量和状态，其中状态值为1表示确认订单，－1表示取消订单。工作人员首先挑选出确认的订单，然后对订单按花瓶型号进行分类统计，最后交给工作人员生产。订单信息存储在“orders.csv”文件中，文件数据格式如图a所示。请回答下列问题。
图a
订单号 型号 数量 状态
s001 A 1000 1
s002 B 2000 1
s003 B 1500 －1
s004 C 900 1
s005 B 800 1
s006 C 700 1
s007 A 500 －1
s008 B 600 1
图b
(1)若某天的订单如图b所示，则当天应生产的B型号花瓶数量为　　　　。
(2)定义如下readdata()函数，函数功能是从订单文件中挑选出确认的订单，并将订单的订单号、型号和数量存储在列表orders中，程序划线处应填入的语句为　　　　。
def readdata()：
　 import csv
　 f＝open(″orders.csv″，″r″，encoding＝″utf－8″)
　 f_csv＝csv.reader(f)
　 title＝next(f_csv)　#读取标题行
　 for line in f_csv：　#逐行读取数据
　 if line[3]＝＝″1″：
　　　　orders.append([line[0]， 　　　　　，int(line[2])])
　 f.close()
　 return orders
(3)实现按花瓶型号分类统计花瓶数量的Python程序如下，程序运行结果如图c所示。请在程序划线处填入合适的代码。
当天订单信息为： [['s001'，'B'，6000]，['s002'，'A'，9000]，['s003'，'C'，9500]，['s008'，'A'，5000]] 分类订单统计结果为： ['s002'，'A'，9000]→['s005'，'A'，6200]→['s008'，'A'，5000]→共计20200个 ['s001'，'B'，6000]→['s006'，'B'，3000]→共计9000个 ['s003'，'C'，7000]→['s007'，'C'，9500]→共计16500个
图c
orders＝[]　#存储订单信息
readdata()
print(″当天订单信息为：\\n″，orders)
n＝len(orders)；m＝3
tlist＝[]　#以链表形式存储相同型号花瓶首尾订单的索引值
for i in range(n)：
　 orders[i].append(－1)　#orders[i]追加一个元素－1
for i in range(m)：
　 tlist.append([－1，－1])　#tlist 追加一个元素[－1，－1]
i＝0
while i　　k＝ord(orders[i][1])－ord(″A″)
　　　if tlist[k][0]＝＝－1：
　 tlist[k][0]＝i
　 else：
　　 p＝tlist[k][1]
　　 ①　　　　
　 tlist[k][1]＝i
　 i＋＝1
p＝0
print(″分类订单统计结果为：″)
while p　　　y＝tlist[p][0]
　　　total＝0
　　　while y！＝－1：
　　print(orders[y][0：3]，″→″，end＝″″)
　　②　　　　
　　y＝orders[y][3]
　　　print(″共计″，total，″个″)
　　　③　　　　
2.张三是一名计算机专业的大学生，为了帮助同学们学习专业相关的英语词汇，编写一个简易字典程序。该程序中存放词汇数据库，在学习中输入英文单词，可以获得中文翻译结果。程序中的词汇数据库采用链表方式存储，首字母相同时按升序排序。查找单词时，首先根据首字母找到同首字母最小单词所在链表，再按照链表顺序查找该单词。
(1)根据题意，部分的单词库数据逻辑结构如图所示，查找单词”byte”的过程是”binary”→”bit”→”byte”， 补充图中空白单元格的值为　　　　。
列表索引 数据区域 指针区域
0 audio 音频 －1
1 binary 二进制数 6
2 byte 字节 －1
3 cursor 光标 －1
4 access 存取 0
5 cache 高速缓存 3
6 bit 比特 　　　　
(2)wordlist(data，info)函数实现将词汇数据库data以链表的方式按字母序升序排列。info表示词汇数据库中各字母开头的最小单词位置，如info[0]表示字母a开头的最小单词在词汇数据库data中的位置。实现该功能的程序如下，请在划线处填入合适的代码。
info＝[]
def wordlist(data，info)：
　 n ＝ len(data)
　 for i in range(n)：
　 data[i].append(－1) #data[i]追加一个元素－1
　 for i in range(n)：
　 d ＝ data[i][0]
　 ①　　　　
　 if info[k] ＝＝ －1：
　　　 info[k] ＝ i
　 else：
　　　 head ＝ info[k]
　　　　　q ＝ head
　　　 while ②　　　　 ：
　　　　　 p ＝ q
　　　　　 q ＝ data[q][2]
　　　 if q ！＝ head：
　　　　　 data[p][2] ＝ i
　　　　　 data[i][2] ＝ q
　　　 else：
　　　　　 data[i][2] ＝ head
　　　　　 ③　　　　
　 return data，info
(3)searchword(data，info，key)函数实现单词的查找。程序如下，请在划线处填入合适的代码。
def searchword(data，info，key)：
　 k ＝ ord(key[0]) － ord(″a″)
　 head ＝ info[k]
　 p ＝ head
　 while p ！＝ －1：
　 if data[p][0] ＝＝ key：
　　 　return 　　　　　
　 p ＝ data[p][2]
　 return″没有找到该单词″
'''
读取词汇数据库，存入列表data中，列表的每个元素包含2个数据项，分别为英文单词和中文翻译，如data ＝ [[‘audio’，‘音频’]，[‘binary’，‘二进制数’] …]，数据读取存入的代码略。
'''
info ＝ [－1] * 26
data，info ＝ wordlist(data，info)
key ＝ input(″请输入查找单词：″).lower()　#转化为小写字母
res ＝ searchword(data，info，key)
print(key，″查找结果是：″， res)
3.某外卖平台推出同城代购服务，外卖骑手可接多个订单，但是同一时间只能完成一项订单。接单规则为：
·若骑手当前没有订单任务，则自动接收最先提交的订单任务；
·若骑手在当前订单完成前都没有接到新的订单，则输出当前订单，并接收排在最前面的订单任务；
·若骑手当前正在执行订单任务，期间有用户提交订单，则订单进入等候区，并按照所需用时升序排列。
订单信息存储在“dingdan.txt”文件中，文件格式如图a所示。文件按照下单时间升序存储所有订单信息，每一行数据存储每个订单的接收时间和完成订单的所需用时，如
(“D1，07：15：36，2400”表示：D1号订单，于07：15：36下单，需要2400秒才能完成)。
图a
订单名称　 完成时间　 　D1　　　　07：55：36　 　D3　　　　09：05：36　 　D2　　　　10：35：36　 　D4　　　　11：32：02　 　D5　　　　14：37：30　
图b
(1)如果某骑手一天内接到的订单如表所示：
订单号 接收时间 所需用时(秒)
D1 08：00：00 600
D2 08：05：00 1500
D3 08：30：00 1800
D4 08：33：00 900
D5 08：33：00 600
骑手在完成所有订单后，各个订单的完成顺序为：　　　　(订单号之间用逗号隔开，如D1，D2，D3，D4，D5)。
(2)定义如下convert()函数，函数功能是转换时间格式，如将3663秒转换为“01：01：03”，程序划线处应填入的语句为　　　　。
def convert(t)：
　 s ＝″″
　 while t ！＝ 0：
　　 trs ＝ str(t % 60)
　　 if len(trs) < 2：
　　　 trs ＝″0″ ＋ trs
　　 s ＝″：″ ＋ trs ＋ s
　　 　　　　
　 return s[1：]
(3)运行如下程序，从文件中读取订单信息，经过加工处理后，按照骑手的完成顺序依次输出各个订单的名称以及该订单的完成时间，运行结果如图b所示。请在划线处填入合适的代码。
def read(file)：
　 #read()函数读取订单文件中的数据，整理后返回data列表
　 #若第一条订单数据为：“D1，01：01：00，600”则存储到列表data中的第一个元素data[0]＝['D1'， 3660， 600]
　 #代码略
data ＝ read(″dingdan.txt″)
link ＝ []
n ＝ len(data)
head ＝ －1；i ＝ 0
finish ＝ 0 #结束时间
print(″订单名称 完成时间″)
while ①　　　　：
　 if head ＝＝ －1 and i < n：　#骑手当前没有任务
　 link.append([data[i][0]，data[i][2]，－1])#向列表link中添加元素
　head ＝ len(link) － 1
　
　 i ＋＝ 1
　elif i ＝＝ n or data[i][1] > finish ：
　 print(link[head][0]，convert(finish))
　　head ＝ link[head][2]　#每完成一个订单，头节点指向下一个节点
　 finish ＋＝ link[head][1]
　elif data[i][1] <＝ finish and i < n：　#头节点订单正在执行，新订单加入链表等待
　 q ＝ head
　 k ＝②　　　
　 link.append([data[i][0]，data[i][2]，－1])
　 while k ！＝ －1 and link[k][1] <＝ data[i][2]：
　　　 q ＝ k
　　　 k ＝ link[k][2]
　 link[len(link)－1][2] ＝ k
　 link[q][2] ＝ len(link) － 1
　 i ＋＝ 1
(4)程序加框处有误，请改正。
4.某医院为实现就诊顺序规则的相对公正，实行就诊前“挂号＋签到”模式，排队规则如下：
1)初诊患者签到后，按挂号序号自小到大的顺序排队
2)复诊患者按签到顺序，以“隔2插1”的规则排队
3)年龄大于等于80岁的患者，可以优先就诊
现系统根据签到顺序记录了某天下午某科室挂号患者的信息如图a所示，包括挂号序号、姓名、年龄、初诊复诊情况(0表示初诊，1表示复诊)。经系统处理后，输出患者的就诊顺序如图b所示，请回答问题。
(1)若有7位患者“挂号＋签到”后的信息如图c所示，则输出的就诊顺序中，第三位就诊的患者姓名是　　　　。
(2)实现按排队规则输出患者就诊顺序的部分Python程序如下，请在划线处填入合适的代码。
def insert(a，i)：
　 p＝head
　 while a[p][4]！＝－1 and a[a[p][4]][2]>＝80：
　
　 a[i][4]＝a[p][4]
　 a[p][4]＝i
def sort(a，i)：
　 p＝head
　 while p！＝－1 and ①　　　　：
　　 q＝p
　　 p＝a[p][4]
　 a[q][4]＝i
　 a[i][4]＝p
#读取患者信息存入列表a中，列表的每个元素包含4个数据项，分别对应挂号序号、姓名、年龄、初诊/复诊，为方便处理，在列表前加入一个虚拟节点，如a＝[[0，'姓名'，200，0]，[3，'阮*倩'，30，1]，[9，'岑*光'，85，1]，……]，代码略
n＝len(a)
for i in range(n)：
　 a[i].append(－1)
b＝[]
head＝0
for i in range(1，n)：
　 if a[i][2]>＝80：
　 a[i][1]＝a[i][1]＋'(优)'
　 insert(a，i)
　 elif a[i][3]＝＝0：
　 sort(a，i)
　 else：
　 a[i][1]＝a[i][1]＋'(复)'
　 b.append(a[i])
print('患者就诊顺序：')
left＝0；right＝len(b)
p＝②　　　　
while p！＝－1 and left！＝right：
　 for k in range(2)：
　 print(a[p][0]，'号'，a[p][1])
　 p＝a[p][4]
　 if p＝＝－1：break
　 print(b[left][0]，'号'，b[left][1])
　 ③　　　　
#输出剩余就诊患者信息，代码略
(3)若列表a依次存储图c的患者信息，程序运行后，加框处的语句总共执行　　　　次。
重难点2　构建数组存储临时数据
1.某单位有多个部门，部门编号0～n－1，人数不尽相同，如图a所示。现举行某项活动，需要将所有人重新分组。分组前按部门人数由少到多的顺序(升序)排列，从人数最少的部门开始，按每m人一组划分，最后一组若不足m人，则该组不参加活动转做后勤。例如设定每组人数m＝7，各部门人数存于列表a中，a＝[3，4，2，1，6，4]，则分组情况如图b所示。
(1)由题意可知，若仅将图a中1号部门的员工人数修改为2，则分组后第2组内的部门是　　　　。(请填写正确的部门编号，若有多个编号则用逗号隔开，例如1，2，3)
(2)定义如下rank(a)函数，该函数的功能是返回1个列表，列表元素为各部门编号，并按部门人数升序排列。
def rank(a)：　#参数 a 为列表，表示各部门人数，例如[3， 6， 2， 1]
　 n ＝ len(a) ；
　 p ＝ [0] * n　#各部门初始排名号为0
　 b ＝ [0] * n
　return b　#返回列表b，例如[3，2，0，1]，表示人数最少是3号部门，最多的是1号部门
若a的值是[5，3，4，1]，执行rank(a)，函数中虚线框内程序结束后p列表的值是　　　　。
(3)实现分组的部分Python程序如下，请在程序中划线处填入合适的代码。
def group(a，m)：
　 b ＝ rank(a)
　 n ＝ len(a) ； gnum ＝ 0 ； c ＝ [[]]
　 ①　　　　
　 for i in range(n)： 　#共 n 个部门
　 tot ＋＝ a[b[i]]
　 c[gnum].append(b[i])
　 while　②　　　　：
　　　 tot ＝ tot － m
　　　 c.append([])
　　　③　　　　
　　　if tot > 0：
　　　　　　c[gnum].append(b[i])
　　　#判断最后一个部门的分组情况
　　　if tot > 0： 　#最后一个部门有剩余且不足 m 人
　 c.pop() 　#去掉多余数据，将列表 c 最后一个元素删除
　 print(tot，″人转做后勤″)
　　　print(″团建共有″，gnum，″组，分组情况为：″ ， c)
'''读取每组人数 m 值；读取每个部门原始人数，依次存入列表 a 的 a[0]至 a[n－1]中。a[i]包含 1 个数据项，表示第 i 号部门的原始人数，代码略'''
group(a， m)
2.设计一个简单的快递算法。有n位骑手为一个大型超市提供同城配送服务，假设每送完一单，骑手需回超市取货。由于该超市的顾客有不同等级，因此骑手先送优先级高的订单，若优先级相同，则先送距离近的订单。编写程序实现该算法，假设不考虑路况，忽略取货、卸货花费的时间并且每位骑手的平均速度相同，则可将距离转换成单程配送时间(单位：分钟)，优先级用数字表示，数字越小，优先级越高。请回答下列问题：
订单号 优先级 单程配送时间
A 4 3
B 4 5
C 3 6
D 2 2
E 1 3
F 3 2
G 1 6
(1)若有如图所示的订单，并有2位骑手甲和乙，订单总是先派给空闲的骑手，若都空闲，则先给甲。则订单“C”的顾客需要等待的时间为　　　　分钟。(填数字)
(2)定义sort_bag(a)函数，参数a列表中每个元素由优先级、单程配送时间2项构成。函数功能是将a的元素按优先级和配送时间按题意中的要求排序。代码如下：
def sort_bag(a)：
　 n＝len(a)
　 for i in range(n－1)：
　 for j in range()：
　　 if a[j][0]>a[j＋1][0]：
　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
　　　　 elif　②　　　　：
　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
　 return a
①程序加框处代码有错，请改正。
②请补充程序划线处。
(3)以下代码模拟派送过程，并计算顾客的平均等待时长和订单完成(以最后一位骑手返回超市的时间为准)的总时间，请在划线处补充代码。
#读入订单数据 data，由优先级、单程配送时间 2 项构成，并使用 sort_bag 函数 进行排序。代码略
n＝int(input())　#骑手数量
rider＝[0]*n
nowtime，waittime，i＝0，0，0
while i　 for j in range(n)：
　 if ①　　　　：
　　　　 rider[j]＝rider[j]＋data[i][1]*2
　　　　 waittime＝waittime＋ ②　　　　
　　　 　i＝i＋1
　 if i＝＝len(data)：　#如果所有快递都已经送出
　　　　 break
　 nowtime＝nowtime＋1
maxt＝0
for i in range(n)：
　　　if maxt　maxt＝rider[i]
print('顾客平均等待时长：'，waittime/len(data))
print('订单完成时间：'，maxt)
3.某驿站每个时刻(以秒计)都可能有一批商品到达，编写Python程序，统计商品到达时，在过去一个小时内共有几个地区(用两个大写字母表示)的商品以及商品的数量，并按商品数量从多到少显示。部分商品按到达时刻到达信息以及统计结果如表所示。
时刻(秒) 商品所属地区 各地区商品情况
1 SU KU KA KA KA SU SU KU 3　KA 3　SU 3　KU 2
3 SG KA SU SU 4　SU 5　KA 4　KU 2　SG 1
3601 KA KA SG 3　KA 3　SU 2　SG 2
3604 SG SG AU SG (略)
如上表所示，第1秒有8个商品达到，分属于3个地区。第3秒的4个商品到达后，地区数量有4个，其中商品最多的是SU。第3601秒的3个商品到达后，由于只统计1小时内的数据，因此第1秒的商品不能计算在内，该时刻的商品地区数只有3个。
请回答以下问题。
(1)对于上表中第3604秒时刻，一共有　　　　个不同地区的商品(填数量)。
(2)主程序。小林用数组c保存各个地区的商品数量和它的排名位次，用数组rank保存地区序号和商品数量并用以排序。地区序号由大写字母对应的序号转换而来。实现程序如下，请将划线处程序补充完整。
def toInt(s)：
　 res ＝ ord(s[1])－ord('A')
　 res ＋＝ (ord(s[0])－ord('A')) * 26
　 return res
def toStr(x)：
　 res ＝ chr(x % 26 ＋ 65)
　 res ＝ chr(x ∥ 26 % 26 ＋ 65) ＋ res
　 return res
rank， c， q ＝ []， []， []
for i in range(26 * 26 ＋ 1)：
　 c.append([0， －1])　#c元素的第1个区域表示商品数量，第2个区域表示排名位次
　 rank.append([0，－1])
rank[0] ＝ [99999，－1]
head ＝ tail ＝ ans ＝ 0
delta ＝ 1 * 60 * 60
for i in range(n)：
　 #rank元素的第1个区域表示商品数量，第2个区域表示国家
　 #0号位置上放一个数量异常大的虚拟元素
　 #n表示需要处理的数据数量，即一共有n个时刻要处理
　 #读入一个数据到line，line[0]表示时刻，line[1：]表示各国家(地区)对应字母
　 t ＝ int(line[0])
　 while head ！＝ tail：
　　　 if ①　　　　 ：
　　　 x ＝ q[head][1]
　　　 c[x][0] －＝ 1
　　　 if c[x][0] ＝＝ 0：
　　　　　　 ans －＝ 1
　　　 move_bottom(x)　#x国家(地区)的排位可能要往后移动，该程序代码略
　　　 head ＋＝ 1
　　　 else：
　　　 break
for s in line[1：]：
　 x ＝ toInt(s)
　 c[x][0] ＋＝ 1
　 if c[x][0] ＝＝ 1：
　　　②　　　　
　　　c[x][1] ＝ ans
　 move_top(x)　#x国家(地区)的排名可能要往前移动
　 q.append([t， x])
　 tail ＋＝ 1
#输出该时刻的国家(地区)数量与各国(地区) 商品数量，输出结果如表中第三列所示
print(ans)
for i in range(1， ans＋1)：
　 print(toStr(rank[i][1])， rank[i][0])
(3)数据移动函数。为了保持数据按商品数量从大到小排序，当某国(地区)的商品数量变大时， 该国(地区) 的排名位次可能要往前移动，同时还要调整 c 数组中该国(地区) 商品数量排名位次的更新。小林用 move_top 函数实现了数据的移动，请将程序补充完整。
def move_top(x)：
　　num ＝ c[x][0]　#取x国(地区)商品的数量值
　　i ＝ c[x][1] － 1　#取x国(地区)的排位次序
　　while num > rank[i][0]：
　　　 ①　　　　
　　　 rank[i＋1] ＝ rank[i]
　　　 i －＝ 1
　　②　　　　
　　c[x][1] ＝ i＋1
重难点1　构建链表建立索引关系
1.使用Python编写按文件后缀名进行分类的程序。要求实现的功能为：从文件夹中读取所有文件名，存储到 file 列表中，如：[[″000. mp3″]， [″001. pptx″]， [″002. pptx″]， [″003. jpg″]，…，[″099. jpg″]]，然后按文件后缀名进行分类，并统计每个类别下文件的数量，输出结果如图所示。
mp3类型的文件： 097.mp3 095.mp3 090.mp3 087.mp3 086.mp3 077.mp3 056.mp3 055.mp3 053.mp3 052.mp3 048.mp3 033.mp3 026.mp3 022.mp3 021.mp3 008.mp3 006.mp3 000.mp3 共18个 pptx类型的文件： 091.pptx 089.pptx 081.pptx 079.pptx 078.pptx 073.pptx 071.pptx 065.pptx 062.pptx 051.pptx 044.pptx 032.pptx 029.pptx 017.pptx 013.pptx 007.pptx 004.pptx 002.pptx 001.pptx 共19个 jpg类型的文件： 099.jpg 098.jpg 096.jpg 085.jpg 082.jpg 069.jpg 068.jpg 067.jpg 064.jpg 061.jpg 060.jpg 058.jpg 050.jpg 045.jpg 041.jpg 037.jpg 036.jpg 035.jpg 034.jpg 031.jpg 030.jpg 012.jpg 010.jpg 005.jpg 003.jpg 共25个 xlsx类型的文件： 094.xlsx 093.xlsx 088.xlsx 083.xlsx 080.xlsx 076.xlsx 074.xlsx 072.xlsx 066.xlsx 057.xlsx 049.xlsx 047.xlsx 042.xlsx 040.xlsx 027.xlsx 024.xlsx 023.xlsx 019.xlsx 018.xlsx 016.xlsx 共23个 docx类型的文件： 092.docx 084.docx 075.docx 070.docx 063.docx 059.docx 054.docx 046.docx 043.docx 039.docx 038.docx 028.docx 025.docx 020.docx 011.docx 共15个
(1)定义如下ft(s)函数，参数s为文件名(如″000.mp3″)。函数功能是将文件名中的后缀名取出，并返回该后缀名。完成程序空白处代码。
def ft(s)：
　 n＝len(s)－1
　 while 　　　　：
　　 n－＝1
　 return s[n＋1：]
(2)按后缀名将文件名分为五类，分别为“mp3、pptx、jpg、xlsx、docx”。分类的具体代码如下，请在划线处填入合适的代码。
#从目录读取文件名到file列表过程略
for i in range(len(file))：
　 file[i].append(－1)　#append()功能：为列表增加一个元素
fhead＝[]
for i in range(len(file))：
　 ①　　　　
　 j＝0
　 while j　　 j＋＝1
　 if j　　 file[i][1]＝fhead[j][1]
　　 ②　　　　
　 else：
　　 fhead.append([a，i])　#append()功能：为列表增加一个元素
(3)按后缀名类型将文件名输出，效果如图所示(文件名输出每10个换一行)。具体代码如下，请在划线处填入合适的代码。
for i in range(len(fhead))：
　 print(fhead[i][0]＋″类型的文件：″)
　 ①　　　　
　 n＝0
　 while p！＝－1：
　　 n＋＝1
　　 print(file[p][0]，end＝″″)
　　 if n%10＝＝0：
　　　 print(″″)
　　②　　　　
　print(″″)
　print(″共″＋str(n)＋″个″)
2.某学校工会举行飞镖大赛，共有n位老师报名参赛，每位选手共掷5支镖，每镖得分为0至10分，选手总分为5镖成绩之和，每位选手的比赛数据记录在文本文件中，如图a所示。
图a
处理前的数据为： [['s001'，38]，['s002'，8]，['s003'，26]，['s004'，25]，['s005'，36]，['s006'，27]，['s007'，28]，['s008'，18]] 处理后的数据为： [['s001'，38，4]，['s002'，8，－1]，['s003'，26，3]，['s004'，25，7]，['s005'，36，6]，['s006'，27，2]，['s007'，28，5]，['s008'，18，1]] 从高分到低分依次输出选手的编号和总分为： ['s001'，38] ['s005'，36] ['s007'，28] ['s006'，27] ['s003'，26] ['s004'，25] ['s008'，18] ['s002'，8] NULL
图b
处理要求：数据读入数组data中，计算出每位选手的总分，在不改变数据在原数组data中的位置的条件下，按总分从高到低输出选手的编号和总分。
(1)主程序。采用链表结构处理数据。程序运行结果如图b所示。请在程序中划线处填入合适的代码。
data ＝ readdata(″scores.txt″)　#读取数据，计算总分
print(″处理前的数据为：\\n″，data)
n＝len(data)
flag＝[True]*n　#标记数据被使用情况
head＝findmax()　#返回data中可使用状态最大数的位置
k＝head
for i in range(1，n)：
　 posi＝findmax()
　 data[k].append(posi)
　 　　　　　　
data[k].append(－1)
print(″处理后的数据为：\\n″，data)
print(″从高分到低分输出为：″)
output(head)
(2)编写readdata函数，功能为从文本文件读取数据，计算出总分，返回列表。代码如下，请在程序中划线处填入合适的代码。
def readdata(filename)：
　 f＝open(filename)
　 line＝f.readline()
　 lst＝[]
　 while line：　#获取每位选手的编号和总分数据
　 line＝line.split(″，″)
　s＝0
　for i in range(1，len(line))：
　　　 　　　　
　 lst.append([line[0]，s])
　line＝f.readline()
　 return lst
(3)编写findmax函数，功能为返回data中可使用状态最大数的位置pos，并设置该数的使用状态为False。请在程序中划线处填入合适的代码。
def findmax()：
　 maxnum＝0
　 for i in range(n)：
　 if ①　　　　：
　　　 maxnum＝data[i][1]
　　　 pos＝i
　 ②　　　　
　 return pos
(4)编写output函数，功能为从高分到低分输出选手的信息。代码如下，加框处的代码有误，请改正。
def output(q)：
　 while　：
　 print(data[q][0：2]，end＝″ ″)
　q＝data[q][2]
print(″NULL″)　#表示结束
3.某医院的看病流程为：患者通过网上、自助设备或人工窗口成功挂号后，到门诊的签到处签到，签到成功后即可排队等待叫号就诊。简化的排队规则如下：
①当天08：00之前完成签到的患者，按照挂号顺序从小到大排队就诊；
②08：00之后签到的患者，按照挂号的序号从小到大的次序插入候诊队伍中；
③队伍中前3名患者(包括正在就诊患者)视为已进入待诊状态，插队的患者只能插到这3名待诊患者后的队伍中。
假设医生从08：00开始叫号就诊，对每位患者的诊断时间均为3分钟，忽略相邻患者就诊的时间间隔。编写程序实现以下功能：若有患者签到，则根据规则更新候诊队伍；医生每完成一名患者的诊断，电子屏幕上按顺序显示待诊的患者姓名和每个患者预计就诊的时间。
(1)若当前已签到患者信息如表所示：
姓名 挂号序号 签到时间
A 3 07：47：03
B 1 07：51：12
C 6 07：55：32
D 4 07：57：10
E 8 07：59：52
F 2 08：02：07
则患者F的预计就诊时间为　　　　(格式如08：07：20)。
(2)08：00：00之前签到的患者原始数据存在列表lst中，每位患者信息包括姓名、挂号序号、签到时间，以下函数将列表中的数据按挂号序号从小到大排序，并构建候诊队伍。
def init(lst)：　#构建 8 点前签到的候诊队伍
　 i＝0；n＝len(lst)
　 while i　 k＝i；i＝n－1
　for j in range(n－1，k，－1)：
　　　 if lst[j][1]　　　　　 lst[j]，lst[j－1]＝lst[j－1]，lst[j]
　 　　　　　　　　　
　　for i in range(n)：
　 lst[i][2]＝180*i　#修改时间格式，每位患者诊断时间为3分钟
　lst[i].append(i＋1)
　　lst[n－1][3]＝－1　#尾结点指针域处理，如['E'， 8， 720， －1]
程序划线处的代码是　　　　(单选，填字母)。
A.i＝i＋1 B.i＝j＋1
C.i＝k－1 D.i＝j
(3)每当一位患者就诊结束，更新队伍并按就诊顺序输出待诊的患者姓名和每个患者预计就诊的时间。请补充程序划线处。
def gs(t)：　#时间格式转换，将时间戳127转成“08：02：07”形式
　 t＝t＋8*60*60
　 h＝t∥3600
　 m＝　　　　　　
　 s＝t%60
　 time＝'%02d'%h＋'：'＋'%02d'%m＋'：'＋'%02d'%s
　 return time
def mov(lst，head)：
　 #更新队伍并输出，代码略
　 return head
(4)若有患者签到，则更新候诊队伍。请将程序划线处代码补充完整。
def tc(time)：　#时间格式转换，将“08：02：07”转换成以秒为单位的时间戳127
　 t＝int(time[0：2])*60*60＋int(time[3：5])*60＋int(time[6：])
　 t＝t－8*60*60　#8点开始叫号看诊
　 return t
def insnew(lst，head，data)：　#将新签到的患者插入候诊队伍中，并更新每个患者预计就诊的时间
　 data[2]＝tc(data[2])
　 data.append(－1)
　 p＝head； q＝p； k＝0
　 if head＝＝－1：　#无人排队
　 lst.append(data)
　 ①　　　　
　 else：
　 while q！＝－1 and (②　　　　)：
　　　 k＝k＋1
　　　 p＝q
　　　q＝lst[q][3]
　 data[2]＝lst[p][2]＋180
　 data[3]＝q
　 lst.append(data)
　 lst[p][3]＝len(lst)－1
　 p＝len(lst)－1
　 while q！＝－1：
　　　 lst[q][2]＝lst[p][2]＋180
　　　 p＝q
　　　 q＝lst[q][3]
　 return head
4.现有n项先后出现的任务，每项任务需要一定的时间完成，且每个时刻只能执行某一项任务。任务的处理规则如下：
1)每项任务有一个紧急程度，用数字表示，数字越大紧急程度越高。紧急程度最高的任务优先执行，紧急程度相同先出现先执行。
2)若某项任务在执行过程中出现了一个紧急程度更高的任务，则正在执行的任务将被暂停，执行该紧急程度更高的任务。
编写Python程序，实现如下功能：程序运行时，按编号升序输出各项任务数据显示如图a所示，然后根据任务先后完成的情况显示结果，如图b所示。
请回答下列问题：
(1)若有3个任务需要完成，数据如下：
1号任务：时刻1出现，完成所需时长4，紧急程度1
2号任务：时刻2出现，完成所需时长2，紧急程度2
3号任务：时刻7出现，完成所需时长1，紧急程度3
则这3个任务的完成的顺序为　　　　(单选，填字母：A.1号、2号、3号 /B.2号、3号、1号 / C.2号、1号、3号)。
(2)实现上述功能的Python程序如下，请在划线处填入合适的代码。
n＝8　#n保存总任务数
w＝[[4，20，2，3]，[5，21，9，4]，[1，1，5，3]，[7，23，5，2]，[8，24，2，4]，[2，10，5，1]，[3，12，7，2]，
　[6，22，9，4]]　#w中每个元素依次保存，任务编号、出现时刻、所需时长和紧急程度数据
#读取任务编号、出现时刻、完成所需时长和紧急程度的数据，代码略
for i in range(n－1)：
　 for j in range(0，①　　　　)：
　　 if w[j][0]>w[j＋1][0]：
　　　　　w[j]，w[j＋1]＝w[j＋1]，w[j]
#输出图a数据，代码略
cur＝1　#记录当前任务时刻
q＝[－1]*20　#q数组按优先顺序存储已出现的任务编号
t＝[i[2] for i in w]
tail＝head＝0
print(″任务编号″，″完成时刻″)
i＝0
while ②　　　　：
　 if tail>head：
　　　t[q[head]]－＝1
　　　if ③　　　　：
　　　　　print(w[q[head]][0]，cur)
　　　　　head＋＝1
　 if i　　　④　　　　
　　　tail＋＝1
　　　i＋＝1
　　j＝tail－1
　　while j>head and w[q[j]][3]>w[q[j－1]][3]：
　　　　q[j]，q[j－1]＝q[j－1]，q[j]
　　　　j－＝1
　　cur＋＝1
重难点2　构建数组存储临时数据
1.某市举办科技嘉年华活动，为了激发学生的参与积极性，举办方推出了玩游戏得积分，积分兑换礼物的活动。活动中游戏分为简单和困难两种，参与游戏就可以获得相应的积分，当完成困难游戏时，除了获得相应积分外，还可获得一张“积分翻倍卡”，一张“积分翻倍卡”可用于一个简单游戏，使简单游戏的积分翻倍。
“积分翻倍卡”使用规则如下：
(1)当简单游戏开始时，如果有“积分翻倍卡”可用，则一定会使用。
(2)“积分翻倍卡”需在15分钟内使用。比如困难游戏完成时间是9：15分，则获得的“积分翻倍卡”将在9：15分激活，且超过9：30分将失效。
3)如果有多张“积分翻倍卡”，则优先使用最早的“积分翻倍卡”。
某同学的游戏记录如图a所示(类型0表示困难游戏，类型1表示简单游戏)，小明读取游戏记录，编写Python程序计算出该同学游戏的最终得分。程序运行结果如图b 所示，请回答下列问题：
序号 类型 积分 开始时间 完成时间
1 0 10 9：10 9：15
2 1 3 9：15 9：28
3 1 5 9：38 9：42
4 0 12 9：58 10：05
5 1 3 10：20 10：36
6 0 15 10：48 10：55
7 1 3 11：25 11：29
图a
(1)若某同学参加游戏的记录如图c所示，则他获得的积分是　　　　分。
(2)定义如下函数 change(t)，参数t为游戏时间，函数功能是将时间t转换为分钟并返回。如：t＝″9：20″时，转换为整数(分钟)值是560，函数返回值为560。函数代码如下，请在划线处填入合适的语句。
def change(t)：　#参数t的时间格式为：″小时：分钟″
　 m＝t.split(″：″)
　 s＝　　　　
return s
(3)计算游戏积分的部分Python程序如下，请在划线处填入合适的代码。
从Excel文件中读取游戏过程记录，存储在列表s中，如s＝[[1，0，10，550，565]，[2，1，3，565，568]，...]，s[i]表示第i个游戏记录，s[i][0]，s[i][1]，s[i][2]，s[i][3]，s[i][4]依次存储游戏的序号、类型、积分、开始时间，完成时间；当游戏类型s[i][1]值为日时表示困难游戏，为1则表示简单游戏；
将困难游戏取出存入列表a中，列表 a按游戏完成时间升序排序；
将简单游戏取出存入列表b中，列表b按游戏开始时间升序排序，代码略
que＝[－1]*(len(a)＋len(b)＋1)
head＝tail＝0
total＝0
for i in range(len(a))：　#累加游戏积分，将“积分翻倍卡”激活时间加入队列
　 total＋＝a[i][2]
　 ①　　　　
　 tail＋＝1
for i in range(len(b)) ：
　 while head　 print(que[head]∥60，″：″， que[head] % 60，″时刻生效的″＋″积分翻倍卡过期；″)
　 head＋＝1
　 if head　 print(b[i][3]∥60，″：″， b[i][3]%60，″时刻使用了积分翻倍卡；″)
　 ③　　　　
　 head＋＝1
　 else：
　 total＋＝b[i][2]
print(″总共获得积分为：″，total，″分，″，″剩余积分卡有：″，tail－head，″张。″)
2.某学校有n个社团组织招新(社团编号为1－n)，每个社团最多可招收m人。学生在线提交申请信息，提交内容为社团编号和对该社团的喜好程度(1－5分)，学生可同时提交报名多个社团，但只能被1个社团录取。后台自动记录学生的报名序号和全部报名信息。报名序号从1开始编号，申请信息的记录格式如图a所示，报名序号为1的学生报名3号社团喜好程度为3，同时报名2号社团喜好程度为4，还报名了1号社团喜好程度为5。
学生报名完毕后，n个社团通过抽签决定招新顺序，抽签号为1－100的随机整数，抽到数字小的社团先招录学生。每个社团招录时，系统调取报名该社团的申请信息，根据学生提交的喜好程度从高到低录取，尚未被其他社团录取的学生，喜好程度相同则按报名序号(学生的报名先后顺序)从小到大录取。
编写程序，读取每位学生的报名序号及报名信息、各社团的抽签序号，程序自动完成社团招新并输出录取结果。
例如，3个社团招新，每社团最多招收2人，社团的抽签序号依次为1、3、2，那么图a中的报名信息，招新结果如图b所示。
报名 序号 申请信息(每2个数字为一组，表示社团编号，喜好程度)
1 3，3，2，4，1，5
2 3，1
3 3，2，1，4，2，4
4 3，1，1，1
5 2，1，3，1
图a
社团编号 抽签序号 有意向学生(括号中为喜好程度) 录取结果
1 1 1(5)，3(4)，4(1) 1，3
2 3 1(4)，3(4)，5(1) 5
3 2 1(3)，2(1)，3(2)，4(1)，5(1) 2，4
图b
请回答下列问题：
(1)若每个社团最多招收人数为3人，1、2、3号社团抽签序号仍为1、3、2时，对图a中的数据进行重新执行招录操作，则3号社团录取的学生为　　　　。
(2)定义如下px(clubs)函数，参数clubs存储社团数据，club[i]包含2个数据项，club[i][0]和club[i][1]分别存储社团编号及抽签序号。
def px(clubs)：
　 n ＝ len(clubs)
　 ans＝[]
　 for i in range(n)：　#①
　 for j in range(n－1，i，－1)：
　　　　 if clubs[j][1] < clubs[j－1][1]：
　　　　 clubs[j]，clubs[j－1]＝clubs[j－1]，clubs[j]
　 ans.append(clubs[i][0])
　 return ans
已知clubs为[[1，8]，[2，25]，[3，3]，[4，9]，[5，1]，[6，25]]，若①处的语句改为“for i in range(n－1)”，执行a＝px(clubs)，a的值为　　　　。(单选，填字母)。
A.[5，3，1，4，2，6] B.[5，3，1，4，2]
C.[5，3，1，4，6，2] D.[5，3，1，4，6]
(3)实现社团招录功能的Python代码如下，请在程序中划线处填入合适的代码。
def assign(stus，clubs，n，m)：
　 ans＝[[] for i in range(n＋1)]
　 #预处理，对社团i，好感j分的全部报名序号存入f[i][j]
　 f＝[[[] for j in range(6)] for i in range(n＋1)]
　 for item in stus：
　for x in range(0， len(item[1])， 2)：
　　　　 st＝item[1][x]
　　　　 fs＝①　　　　
　　　　 f[st][fs].append(item[0])
　　rs＝len(stus)
　　flag＝[False]*(rs＋1)
　　b＝px(clubs)
　　for i in b：　#各社团按顺序依次招新
　t＝m
　fs＝5
　while fs>0 ：
　　　　 ②　　　　
　　　　 for j in x：
　　　　 if ③　　　　：
　　　　　 ans[i].append(j)
　　　　　 flag[j]＝True
　　　　　 t－＝1
　　　 fs－＝1
　return ans
#读取学生报名信息，报名序号为i的信息存储在stus[i]中，stus[i][0]存储报名序号，stus[i][1]存储申请信息，代码略。
#读取社团数n和每个社团可招录的学生数m，代码略。
#读取社团编号和抽签序号，存入clubs中，clubs[i][0]存储社团编号，clubs[i][1]存储抽签序号，代码略。
ans＝assign(stus，clubs，n，m)
for i in range(1，len(ans))：
　 print(″社团″＋str(i)＋″：″，ans[i])
3.某餐厅的订单数据由线上、线下多条订单合并而成。各条订单含下单时间、菜品列表两个数据项，下单时间(各订单下单时间互不相同)的数据格式为“时：分钟”；菜品列表由互不重复的大写字母构成，按字母升序排列如“ABC”，每个字母代表一种菜品，合并后的订单数据如图a所示。
由于厨师一锅能烹饪5份同种菜品，为了提升烹饪效率，餐厅打算为厨师提供烹饪提示队列。按合并订单数据中下单时间的先后顺序逐条处理，对各条订单中的不同菜品进行统计：当某种菜品中首份菜品的下单时间超过10分钟时，或某种菜品累计份数达到5份时，该种菜品及累计份数将进入烹饪提示队列，入队后该种菜品重新开始统计。
当多种菜品符合某个入队条件时，按各菜品中首份菜品下单时间先后时间顺序入队。所有订单处理完毕，剩余未入队的菜品直接进入派单提示器队列，处理结果如图b所示。
编写程序：给定订单数据，根据上述方法进行处理，输出派单提示器队列。请回答下列问题：
(1)由题意可知，若仅将图a中的数据项['10：00'， 'ABC']修改为['10：00'， 'BC']，则A菜品第1次烹饪的数量为　　　　份。
(2)定义如下merged_list(lst1，lst2)函数，参数lst1和lst2的每个元素由下单时间和菜品列表2项构成，lst1和lst2均已按下单时间升序排列。函数功能是将lst2中的元素合并到lst1中，lst1按下单时间保持升序排列，函数返回lst1。
def merged_list(lst1，lst2)：
　 m ＝ len(lst1) － 1
　 n ＝ len(lst2) － 1
　 tail ＝ m ＋ n ＋ 1　#①
　 for i in range(n ＋ 1)：　#②
　 lst1.append([″″，″″])
　 while n >＝ 0：
　 if lst1[m][0] > lst2[n][0]：　#③
　　　　 lst1[tail] ＝ lst1[m]
　　　 m －＝ 1
　 else：
　　　 lst1[tail] ＝ lst2[n]
　　　 n －＝ 1
　 tail －＝ 1
　 return lst1
若lst1为[['10：01'，'AFHM']，['10：04'，'EIQZ']，['10：05'，'CPVXZ']]，lst2为[['10：00'，'AKVY']，['10：02'，'GLQS']，['10：06'，'FGQY']]，调用merged_list(lst1，lst2)，发现运行结果有误，应从程序中①、②、③三处语句中选择　　　　(单选：填序号)处，将其修改为　　　　。
(3)实现派单提示器队列功能的部分Python程序如下，程序中用到的列表函数与方法如表所示，请在程序划线处填入合适的代码。
函数与方法 功能
dc.append(x) 在列表dc末尾添加元素x
head＝qu.pop(x) 将列表x位置元素赋值给head，并将其从qu中删除
def inttime(time)：
　 t＝int(time[0：2])*60＋int(time[3：])
　 return t
def proc(orders)：
　 dc，qu＝[]，[]
　 for i in range(26)：
　 dc.append([0，0])
　 for i in range(len(orders))：
　 t＝inttime(orders[i][0])
　①　　　　
　for j in range(len(dishes_str))：　#处理单个订单中的每种菜品
　　　　dish＝ord(dishes_str[j])－ord(″A″)
　　　　dc[dish][0] ＋＝ 1
　　　　if dc[dish][0]＝＝1：
　　　　　 dc[dish][1]＝t
　　　　　 qu.append(dish)
　 pret＝0　#检查某种菜品是否需要进入烹饪派单提示器队列
　 if i　　　pret＝inttime(orders[i＋1][0])
　 while ②　　　　：　#当某种菜品中首份菜品的下单时间超过10分钟时
　　　head＝qu.pop(0)
　　　print(″菜品″， chr(head＋ord('A'))，″烹饪″，dc[head][0]，″份。″)
　　　dc[head][0] ＝ 0
　 k＝0
　 while k　　　 if dc[qu[k]][0]＝＝5：
　　　 ③　　　　
　　　　 print(″菜品″， chr(pdish＋ord('A'))，″烹饪″，dc[pdish][0]，″份。″)
　　　　 dc[pdish][0] ＝ 0
　　　 else：
　　　　 k＋＝1
#所有订单完毕后，剩余未入队的菜品直接进入派单提示器队列，代码略
″″″
读取线上、线下多条订单存入列表order1、order2，2个列表中的每个元素包含2个数据项，分别存放下单时间、菜品列表。2个列表的数据已分别按下单时间升序排列，代码略
″″″
orders ＝ merged_list(order2， order1)
proc(orders)
专题18　基于数据结构的算法实现
学习目标　1.掌握队列中元素入队和出队的条件；
2.掌握链表的构建方法.
队列是线性结构的一种，因此也可以用链式结构的方式来实现。并且链式结构的队列，由于节点空间都是在入队的时候动态申请的 ，因此在计算机内存空间足够的情况下，一般不需要考虑队满的情况，也就不存在溢出的情况，所以不需要使用循环链式队列来处理假溢出的情况。 链式队列在链表的链尾插入元素，然后让队尾指针指向链尾元素。链式队列的出队，就是将链表的首元节点从链表中删去，让其后继节点成为首元节点，然后让队头指针指向该节点。
(2024年1月浙江省选考)某项活动有n个单位(编号1到n)参加，需将员工分成若干个小组，每个小组的人数上限为m，小组编号按新建次序从1开始编号。分组时，首先按单位编号次序依次在各单位内部分分组，每m人分配到一个新建小组中，不足m人的剩余员工暂不分配；然后按剩余员工人数由大到小的顺序，依次为各单位剩余员工分配小组。
若某单位剩余员工人数为k，则分配方法为：在已建的小组中查找空位数(该小组还可容纳的人数)大于或等于k的小组，如果找到的小组有多个，则选择空位数最少的小组，将此k人分配到该小组中；如果没有找到，则新建一个小组，将此k人分配到该小组中。
设n为5，m为20，各单位员工人数及单位内部的分组过程如图a所示，各单位剩余员工的分组过程如图b所示。
编写程序：给定各单位编号及员工人数，根据上述方法进行分组处理，按单位编号次序输出各单位所分配的分组编号。请回答下列问题：
(1)由题意可知，若仅将图a中1号单位的员工人数修改为25，然后对图中5个单位重新分组，则1号单位所分配的分组编号为________。
(2)定义如下bubble_sort(lst)函数，参数lst的每个元素由单位编号和剩余员工人数2个数据项组成。函数的功能是根据每个单位的剩余员工人数，对lst进行降序排序。
def bubble_sort(lst):
　 n＝len(lst)
for i in range(0, n－1)：
　 return
调用该函数，若lst为[[1，0]，[2，0]，[3，18]，[4，0]，[5，19]，[6，17]]，请回答①和②两个问题。
①虚线框中的程序段第1次执行后，关于lst中的剩余员工人数，下列说法正确的是________(单选，填字母)。
A.lst[0][1]数值最小 B.lst[0][1]数值最大
C.lst[5][1]数值最小 D.lst[5][1]数值最大
②虚线框中的程序段执行的次数为________。
(3)实现分组功能的部分Python程序如下，程序中用到的列表函数与方法如图c所示，请在程序中划线处填入合适的代码。
函数与方法 功能
w.append(x) 在列表w末尾添加元素x
x＝w.pop() 将列表w末尾元素赋值给x，并将其从w中删除
图c
def group(data, m):
　 n＝len(data)
　 a＝[]
　 for i in range(n＋1)：
　 a.append([])　#a[i]初始化为空列表，存放编号为i的单位所分配的分组编号
　　gnum＝0
　　for i in range(n)：　#各单位内部分组
　 while data[i][1]>＝m：
　　　 gnum＋＝1
　　　　　 k＝data[i][0]
　　　 a[k].append(gnum)
　　　 ①________
　　bubble_sort(data)　#根据每个单位的剩余员工人数，对data进行降序排序
　　b＝[]
　　for i in range(m):
　b.append([])
　　i＝0
　　while i　 ②________
　 while j　　　 j＋＝1
　 if j　　　 v＝b[j].pop()
　 else：
　　　 gnum＋＝1
　　　 v＝gnum
　 a[data[i][0]].append(v)
　 ③________
　 i＋＝1
　　#输出各单位的分组编号，代码略
'''
读取小组人数上限存入 m；读取 1 至 n 号单位的数据，依次存入列表 data 的 data[0]至 data[n－1]中。data[i]包含 2 个数据项，data[i][0]，data[i][1]分别存放单位编号及员工人数，代码略
'''
group(data, m)
答案　(1)1，8　(2)①B　②4次　(3)①data[i][1]－＝m　②j＝data[i][1]　③b[j－data[i][1]].append(v)
解析　本题考查冒泡排序和桶的应用。(1)1号剩余5人，5号和2号剩余人数单独分组后，再次剩余人数为2和3，因此圴不能加入到这些新分组中。3号剩余人数编码为第8组，1号的剩余人数可以加入到该组。(2)①程序实现从后往前冒泡降序排序，因此第1次执行后，最左边的数据最大。②第4趟排序后，lst[i][1]的值为0，执行break语句，结束排序。(3)①每m人分配到一个新建小组中，不足m人的剩余员工暂不分配。新建一个分组后，该组内的人数将减少m个。②新一个大小为m列表b表示各个分组的剩余人数，b[0]至b[m－1]的初值均为0。对每个单位的剩余员工人数降序排序，并遍历n个单位，首先查找是否存在一个大于等于该单位剩余人数最小分组，其方法是用循环while j重难点1　构建链表建立索引关系
高中阶段的数据结构不是讨论如何使用数据结构，而是通过对数据集进行简单的操作，理解和创建数据结构。能将有限制条件的、真实情境中的数据关系进行抽象，根据数据特点与求解要求，选择适当的数据类型表示各种数据，并用合适的数据结构表达数据的逻辑关系。在已有数据集的基础上，通过链接关系构造逻辑上先后遍历顺序，构建链表，将有层次非线性结构或二维数组转换为一维数组，再遍历一维数组，得到问题的解。当原始数据量大，且每个数据元素有多个数据项时，直接对进行复制会浪费大量空间和时间，可进行基于索引的引用，提高效率。
例题 有2组器件共n个，要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先级。优先级有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均已按送达时间升序排列。函数功能是将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”，会导致某些情况下无法得到符合函数功能的结果。调用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程序如下，请在划线处填入合适的代码。
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：
　　　 k ＝ data[i][2]
　　　 if queinfo[k][0] ＝＝ －1：
　　　　　 queinfo[k][0] ＝ i
　　　 else：
　　　　　 ②　　　　
　　　　　 data[p][3] ＝ i
　　　 queinfo[k][1] ＝ i
　　　 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
'''
读取2组器件的数据，分别存入列表data1和data2中。2个列表的每个元素包含3个数据项，分别对应器件的送达时间、检测时长和优先级。data1 和data2中的数据已分别按送达时间升序排列，代码略
读取优先级等级个数存入m，代码略
'''
data ＝ merge(data1， data2)
print(proc(data， m))
思维点拨
明考向 本题考查链表节点元素的构建
精点拨 ((1)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后添加len(lst2)个数据元素，从两个列表的后面开始，将lst2归并到lst1中。依次归并[12，2，2]、[11，3，2]、[4，3，0]、[2，1，1]，j的值小于0，结束归并，共循环4次。②若函数中while 语句的条件“j >＝ 0”误写为“k>＝0”，j是指向lst2的指针，则当lst2中的数据已经处理完时，会出问题，因此答案选A。(3)①总时间的变量total，通过total ＋＝ curtime － data[p][0]累计total值，设置初始值为0。解决问题的方式采用链表实现的队列，即链式队列，二维列表queinfo就用来存储每个优先级的头尾指针。data追加一个元素－1用来存储下一个处理的指针，存储链表信息。②若该等级已存在其他器件，由于器件是按时间升序遍历。因此将该器件添加到k等级链表表尾。通过访问k等级虚点对应的链表表尾，找到表尾位置p(p＝queinfo[k][1])，然后在链表表尾追加当前器件的索引位置i，完成待处理器件的入队操作。③在k等级链表中，找到最高k等级单链表指向的位置p，p为单链表中队首器件位置。此处是将p指向的器件删除，通过更新k等级链表表头queinfo[k][0]，使链表表头指向p的下一个器件位置，完成删除操作
答案　(1)6　(2)①4　②A　(3)①total ＝ 0　②p ＝ queinfo[k][1]　③queinfo[k][0] ＝ data[p][3]
变式 某工程包含n个任务(编号为0～n－1)，每天可以有多个任务同时进行。某些任务之间有依赖关系，如图a所示，任务4依赖于任务1，任务1依赖于任务2。即任务2完成后才可以开始任务1，任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务，或多个任务依赖于同一个任务的情况。现已对该工程的依赖关系进行了梳理，结果如图b所示，标记“T”表示依赖关系需保留，标记“F”表示依赖关系需删除。
根据每个任务完成所需的天数和梳理后的依赖关系，编写程序，首先删除标记为“F”的依赖关系，然后计算工程最快完成所需的天数，并以工程最快完成所需的天数为期限，计算每个任务最晚必须开始的时间。
图a
任务A 任务B 标记
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注：任务a依赖于任务b。
图b
请回答下列问题：
(1)若某工程有6个任务，任务间依赖关系如图a所示，完成任务0～5所需天数分别为2，1，3，5，1，6，则工程最快完成需要　　　　天。
(2)定义如下erase(lst)函数，参数lst列表的每个元素表示一个依赖关系。函数的功能是删除标记为“F”的依赖关系，返回保留的依赖关系的个数。
def erase(lst)：
　 i＝0
　 j ＝ len(lst)－1
　 while i<＝ j：
　 if lst[i][2]＝＝ 'T'：
　　　 i＋＝1
　 else：
　　　 if lst[j][2] ＝＝ 'T'：
　　　 lst[i]＝lst[j]
　　　　 i ＋ ＝ 1
　　　 j － ＝ 1
return i
若lst列表依次存储图b所示的依赖关系，如lst[0]为[0，5，'T']，调用erase(Ist)的数，则语句“lst[i] ＝lst[j]”的执行次数为　　　　。
(3)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
def proc(n，lst，task)：
　 pr＝[0]*n
　 w＝[0]*n　#w[i]存放任务1最晚必须开始的时间
　 m＝erase(lst)
　 for i in ①　　　　：
　　 task[lst[i][1]][1]＝lst[i][0]
　　 pr[lst[i][0]]＝1
　 c＝[]
　 days＝0　#days存放工程最快完成所需的天数
　 for i in range(n)：
　 if pr[i]＝＝0：
　　　 k＝i
　　　 s＝0
　　　 while k！＝－1：
　　　　　　 c.append(k)
　　　　　　 s＋＝task[k][0]
　　　　　　 ②　　　　
　　　 if s>days：
　　　　　　 days＝s
　　for i in range(n－1，－1，－1)：
　　 k＝c[i]
　　 if task[k][1]＝＝－1：
　　　　 w[k]＝days－task[k][0]＋1
　　 else：
　　　 ③　　　　
　　　#输出days，以及保存在w中的每个任务最晚必须开始的时间，代码略
'''
工程包含的任务数存入变量n
任务间的依赖关系存入1st列表
1st[0]包含3项，任务1st[i][0]依赖于任务1st[i][1]，1st[i][2]存放保留/删除标记，任务数据存入task列表
task[i]包含2项，task[i][0]为完成任务所需天数，task[i][1]的初值为－1
代码略
'''
proc(n，lst，task)
答案　(1)8　(2)1　(3) ①range(m)或range(0，m)或range(0，m，1)或range(m－1，－1，－1)或range(erase(lst))或range(0，erase(lst))或range(0，erase(lst)，1)或range(erase(lst) －1，－1，－1)　②k＝task[k][1]　③w[k]＝w[task[k][1]]－task[k][0]或w[k]＝w[c[i＋1]]－task[k][0]
解析　本题考查数组的遍历、链表的遍历、创建等操作。(1)任务5和任务0有依赖关系，完成天数为8天，任务4、1、2有依赖关系，完成天数为5天，任务3需5天，存在3条链表，每天可以有多个任务同时进行，因此取最长链表所花时间，至少需要8天。(2)变量i和j分别指向数组lst的头尾元素位置，从头元素开始遍历，若遍历的元素lst[i][2]不是'T'，将尾元素为'T'的元素覆盖当前元素，并将变量j向前移动。在图b中，当i值为1时，标记为F，由于尾元素也不是T，因此仅仅变量j向前移动，变量i并未增加，再次遍历时，将一条为T的元素覆盖，因此该语句只执行了一次。(3)①首先删除标记为“F”的依赖关系，从图中可以看出，任务a依赖于任务b，任务b完成后才可以开始任务a，任务b的后继是任务a，因此语句task[lst[i][1]][1]＝lst[i][0]的作用是创建链表，并将不是头节点的元素用pr数组标记为1。变量m调用函数返回保留的依赖关系的个数，因此需对有依赖关系的记录进行标记。②遍历每一个任务，当条件pr[i]＝＝0成立时，表示当前任务是某条链表的头节点，并开始遍历该条链表，将节点添加到列表c中，并统计该条链表所需天数s。当前节点完成遍历后，要到下一节点。③以工程最快完成所需的天数为期限，计算每个任务最晚必须开始时间，如图a中，工程最快完成所需的8天，任务5最迟在第1天完成，任务5完成在第6天，任务0则完成时间在第7、8两天，因此最迟在第7天开始。当条件task[k][1] ＝＝－1 成立时，表示任务k是任务链的尾节点，至少应该从倒数第task[k][0]天开始，或者顺数第days－task[k][0]＋1开始；若任务 k不是尾节点，该任务必须在其后续任务完成前开始，开始时间为后续任务的最晚开始时间减去当前任务完成时间。
重难点2　构建数组存储临时数据
针对情境较为复杂、结构化程度较低的问题，能抽象数据特征、创造性地运用数据结构优化算法。数据往往经过采集、传输、处理和存储的过程，而数据在加工处理过程中，要考虑算法的优越性，提高算法的效率。数据在加工过程中，临时存放的数据可以存储在队列、栈和二维数组中，利用其不用查找就可以操作或者把当前正在处理的数据放置一个较小的数组中的特性，加快数据的处理时间。
例题 某店使用加工设备制作m种类型的甜品，每分钟只能制作一种类型，且不超过n个。每个订单包含订单编号、下单时间、类型和数量。编排制作顺序的规则为：下单时间早的类型优先，下单时间相同时数量多的类型优先。下单时间最早的订单数量不足n，可以先制作部分已下单相同类型甜品。每分钟完成后，有新增订单时，合并相同类型订单，按上述规则重新编排顺序，若编排后，新订单仍有剩余，则剩余数量按实际下单时间继续参与编排。
设m为3，n为10，某时段各个订单如图a所示，则制作甜品的顺序为AABACB，数量为10、10、10、4、8、5，如图b所示。编写Python程序，根据订单，输出甜品的制作顺序和数量。
订单编号 下单时间 类型 数量
0406001 8：01 A 24
0406002 8：01 B 3
0406003 8：03 C 8
0406004 8：03 B 12
图a
图b
(1)如图a所示，若订单0406003提前到8：01下单，则制作顺序为　　　　。
(2)定义如下least(tpr，ud，m)函数，参数tpr存储当前各类甜品的下单时间，如tpr＝[[481，482]，[]，[]]表示当前A类型有8：01(将字符串时间格式8：01转换为分钟数字481)和8：02共2个订单，B和C无订单。参数ud存储当前各个类型的订单数量之和，如ud＝[4，0，0]表示当前A类型所有订单数量和为4，B和C无订单。参数m表示甜品种类。函数功能是查找当前待制作甜品的类型。
def least(tpr，ud，m)：
　 post＝0
　 for i in range(1，m)：
　 if len(tpr[i])>0：
　　　　 if
：
　　　　　　post＝i
　　　　elif tpr[i][0]＝＝tpr[post][0]：
　　　　　　if ud[i]>ud[post]：
　　　　　　　 post＝i
　　　return post
若加框处条件误写为“tpr[i][0]A.tpr＝[[481]，[481]，[482，483]]
ud＝[2，25，5]
B.tpr＝[[]，[482]，[482，483]]
ud＝[0，3，2]
C.tpr＝[[481，485]，[]，[482，483]]
ud＝[2，0，5]
D.tpr＝[[481，485]，[]，[]]
ud＝[2，0，0]
(3)实现上述功能的部分Python程序如下，程序中用到的列表函数与方法如下表所示，请在划线处填入合适的代码。
函数与方法 功能
w.append(x) 在列表w末尾添加元素x
w.pop(i) 删除列表w索引为i的元素
sum(w) 累加列表w中的元素
#读取各个订单的数据，存入列表lst，每个元素包含订单编号、下单时间、类型和数量。lst中的数据已按下单时间升序排列，代码略。
#读取甜品种类和每分钟最多加工的数量，分别存入变量m和n，代码略。
def convert(s)：
　 #将字符串格式时间s转换成分钟数，如convert(″08：00″)的值为480，代码略。
tpr＝[[]for i in range(m)]
npr＝[[]for i in range(m)]
ud＝[0 for i in range(m)]
curtime＝convert(lst[0][1])　#当前时间为第1个订单的下单时间
i＝0
while i 0：
　　while i　 t＝ord(lst[i][2])－ord(″A″)
　 tpr[t].append(convert(lst[i][1]))
　 npr[t].append(lst[i][3])
　 ①　　　　
　 i＋＝1
　　k＝least(tpr，ud，m)
　　tot＝0　　
　　while　ud[k]>0 and tot　 if 　 ②　 ：
　　　 ud[k]－＝npr[k][0]
　　　 tot＋＝npr[k][0]
　　　 tpr[k].pop(0)
　　　 npr[k].pop(0)
　 else：
　　　 npr[k][0]－＝n－tot
　　　 ud[k]－＝n－tot
　　　 tot＝n
　　　 #输出当前时间加工的甜品类型及数量，代码略
　　　 curtime＋＝1
　　　 if i　 ③　　　　
思维点拨
明考向 本题考查队列和二维数组的应用
精点拨 (1)8：01有A，B，C共3种类型的订单，数量分别为24，3，8。前2分钟制作A类型甜品，完成后A，B，C数量分别为4，3，8，8：03时B类型订单有12，可以提前完成7个甜品，接下来制作B，C类型甜品，剩余A，B类型的数量分别为4和5，由于B类型下单时间为8：03，因此最后制作B类型甜品。(2)本题考查顺序查找，post的初值为0，变量i从1开始遍历，B选项中初值为空，因此tpr[post][0]的值为空，程序会报错。(3)①变量t为类型的编号，该订单数量u[t]数量增加lst[i][3]。②调用自定义函数least求当前制作订单编号k，语句tpr[k].pop(0)的功能是弹出订单k，表示该订单已完成，因此该订单数量须满足小于等于n－tot。③若当前时间小于新订单到来时间，须更新当前时间为新订单的到来时间
答案　(1)AABCAB　(2)B　(3)①ud[t]＋＝lst[i][3]
②npr[k][0]<＝n－tot
③curtime＝convert(lst[i][1])
变式 有新订单产生。公司安排的打包工作时间为12：00－18：00，假设当日订单在工作时间内就能完成。公司有甲、乙、丙三位师傅对货品进行打包，货品按照甲、乙、丙的顺序分配给各师傅处理，每位师傅一次打包一件货品。打包规则：若下单时间相同，优先级越高(数字越小，优先级越高)的货品，先全部打包完成；若不同，则下单时间更早的货品先处理完成。
订单输入格式示例：7A2B、4B10A(说明：4B10A指订单中有4件B类货品，10件A类货品)。编写程序，输出某天甲、乙、丙货品打包顺序和打包报酬，甲的输出示例：3A5B1C，200元。
货品 优先级 打包报酬(元/件)
A 1 30
B 2 20
C 3 10
表1
下单时间 货品及数量
12：00 2B7A
14：00 7B
15：00 6B5C
表2
(1)若某天货品下单信息如表2所示，则甲的打包顺序为3A5B1C，乙的打包报酬为　　　　元。
(2)定义如下convert(data)函数，参数data为一个订单，包括货品和数量，函数功能将订单转换成货品名称序列，如订单2B1A1C转换成ABBC。请在划线处填上合适的代码。
def convert(data)：
　 num，q ＝ 0，″″
　 qsort ＝ [″″，″″，″″]
　 for i in range(len(data))：
　 if data[i] >＝″0″ and data[i] <″9″：
　　　 num ＝ 　　　　
　 else：
　　　 for j in range(num)：
　　　　　 q ＋＝ data[i]
　　　 qsort[ord(data[i])－ord(″A″)] ＝ q
　　　 num，q ＝ 0，″″
　　　s ＝ qsort[0]＋qsort[1]＋qsort[2]
　　　return s
(3)实现该功能的 Python 主程序如下，请在划线处填入合适的代码。
goods ＝ [30， 20， 10]
m ＝ (18－12)*2　#12：00－18：00之间每半个小时为一个时间节点
b ＝ [ ]
for i in range(m)：
　 b.append(″″)　#append()用于在列表的末尾添加一个元素
a ＝ [[″12：00″，″2B7A″][″14：00″，″7B″]，[″15：00″，″6B3C″]]
for i in range(len(a))：
　 que ＝ convert(①　　　　)
　 x ＝ (int(a[i][0][0：2])－12)*2　#将时间转换为对应的结点
　 while len(b[x]) ＝＝ 3：
　　　 x ＝ x＋1
　 while len(que) > 0：
　　 t ＝ 3－len(b[x])
　　 if len(que) < t：
　　　 t ＝ len(que)
　　 b[x] ＝ ②　　　　
　　 if t ＝＝ len(que)：
　　　 que＝″″
　　 else：
　　　 que ＝ que[t：]
　　 x ＋＝ 1
s1， salary ＝″″， 0
for i in range(m)：　#甲处理顺序和打包报酬输出
　 if b[i] ！＝″″：
　　 s1 ＋＝ b[i][0]
　　 salary ＋＝③　　　　
#将s1中形如“ABBCC”的格式，转换成“1A2B2C”的格式，代码略
print(″甲处理顺序和打包报酬：″， s1， str(salary)＋″元″)
#乙、丙处理(共159张PPT)
第一部分　信息与信息系统
专题18　基于数据结构的算法实现
1.掌握队列中元素入队和出队的条件；
2.掌握链表的构建方法.
目 录
CONTENTS
体系构建
01
真题再现
02
考点精练
03
当堂检测
04
课后练习
05
体系构建
1
队列是线性结构的一种，因此也可以用链式结构的方式来实现。并且链式结构的队列，由于节点空间都是在入队的时候动态申请的 ，因此在计算机内存空间足够的情况下，一般不需要考虑队满的情况，也就不存在溢出的情况，所以不需要使用循环链式队列来处理假溢出的情况。 链式队列在链表的链尾插入元素，然后让队尾指针指向链尾元素。链式队列的出队，就是将链表的首元节点从链表中删去，让其后继节点成为首元节点，然后让队头指针指向该节点。
真题再现
2
(2024年1月浙江省选考)某项活动有n个单位(编号1到n)参加，需将员工分成若干个小组，每个小组的人数上限为m，小组编号按新建次序从1开始编号。分组时，首先按单位编号次序依次在各单位内部分分组，每m人分配到一个新建小组中，不足m人的剩余员工暂不分配；然后按剩余员工人数由大到小的顺序，依次为各单位剩余员工分配小组。
若某单位剩余员工人数为k，则分配方法为：在已建的小组中查找空位数(该小组还可容纳的人数)大于或等于k的小组，如果找到的小组有多个，则选择空位数最少的小组，将此k人分配到该小组中；如果没有找到，则新建一个小组，将此k人分配到该小组中。
设n为5，m为20，各单位员工人数及单位内部的分组过程如图a所示，各单位剩余员工的分组过程如图b所示。
编写程序：给定各单位编号及员工人数，根据上述方法进行分组处理，按单位编号次序输出各单位所分配的分组编号。请回答下列问题：
(1)由题意可知，若仅将图a中1号单位的员工人数修改为25，然后对图中5个单位重新分组，则1号单位所分配的分组编号为________。
(2)定义如下bubble_sort(lst)函数，参数lst的每个元素由单位编号和剩余员工人数2个数据项组成。函数的功能是根据每个单位的剩余员工人数，对lst进行降序排序。
　 return
调用该函数，若lst为[[1，0]，[2，0]，[3，18]，[4，0]，[5，19]，[6，17]]，请回答①和②两个问题。
①虚线框中的程序段第1次执行后，关于lst中的剩余员工人数，下列说法正确的是________(单选，填字母)。
A.lst[0][1]数值最小 B.lst[0][1]数值最大
C.lst[5][1]数值最小 D.lst[5][1]数值最大
②虚线框中的程序段执行的次数为________。
(3)实现分组功能的部分Python程序如下，程序中用到的列表函数与方法如图c所示，请在程序中划线处填入合适的代码。
函数与方法 功能
w.append(x) 在列表w末尾添加元素x
x＝w.pop() 将列表w末尾元素赋值给x，并将其从w中删除
图c
读取小组人数上限存入 m；读取 1 至 n 号单位的数据，依次存入列表 data 的 data[0]至 data[n－1]中。data[i]包含 2 个数据项，data[i][0]，data[i][1]分别存放单位编号及员工人数，代码略
'''
group(data, m)
答案　(1)1，8　(2)①B　②4次　(3)①data[i][1]－＝m　②j＝data[i][1]　
③b[j－data[i][1]].append(v)
解析　本题考查冒泡排序和桶的应用。(1)1号剩余5人，5号和2号剩余人数单独分组后，再次剩余人数为2和3，因此圴不能加入到这些新分组中。3号剩余人数编码为第8组，1号的剩余人数可以加入到该组。(2)①程序实现从后往前冒泡降序排序，因此第1次执行后，最左边的数据最大。②第4趟排序后，lst[i][1]的值为0，执行break语句，结束排序。(3)①每m人分配到一个新建小组中，不足m人的剩余员工暂不分配。新建一个分组后，该组内的人数将减少m个。②新一个大小为m列表b表示各个分组的剩余人数，b[0]至b[m－1]的初值均为0。对每个单位的剩余员工人数降序排序，并遍历n个单位，首先查找是否存在一个大于等于该单位剩余人数最小分组，其方法是用循环while j考点精练
3
重难点1　构建链表建立索引关系
高中阶段的数据结构不是讨论如何使用数据结构，而是通过对数据集进行简单的操作，理解和创建数据结构。能将有限制条件的、真实情境中的数据关系进行抽象，根据数据特点与求解要求，选择适当的数据类型表示各种数据，并用合适的数据结构表达数据的逻辑关系。在已有数据集的基础上，通过链接关系构造逻辑上先后遍历顺序，构建链表，将有层次非线性结构或二维数组转换为一维数组，再遍历一维数组，得到问题的解。当原始数据量大，且每个数据元素有多个数据项时，直接对进行复制会浪费大量空间和时间，可进行基于索引的引用，提高效率。
例题 有2组器件共n个，要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先级。优先级有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均已按送达时间升序排列。函数功能是将lst2中的元素合并到lst1中，并将lst1按送达时间升序排列，函数返回lst1。
思维点拨
明考向 本题考查链表节点元素的构建
精点拨 (1)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后添加len(lst2)个数据元素，从两个列表的后面开始，将lst2归并到lst1中。依次归并[12，2，2]、[11，3，2]、[4，3，0]、
思维点拨
明考向 本题考查链表节点元素的构建
精点拨 [2，1，1]，j的值小于0，结束归并，共循环4次。②若函数中while 语句的条件“j >＝ 0”误写为“k>＝0”，j是指向lst2的指针，则当lst2中的数据已经处理完时，会出问题，因此答案选A。(3)①总时间的变量total，通过total ＋＝ curtime － data[p][0]累计total值，设置初始值为0。解决问题的方式采用链表实现的队列，即链式队列，二维列表queinfo就用来存储每个优先级的头尾指针。data追加一个元素－1用来存储下一个处理的指针，存储链表信息。②若该等级已存在其他器件，由于器件是按时间升序遍历。因此将该器件添加到k等级链表表尾。通过访问k等级虚点对应的链表表尾，找到表尾位置p(p＝queinfo[k][1])，然后在链表表尾追加当前器件的索引位置i，完成待处理器件的入队操作。③在k等级链表中，找到最高k等级单链表指向的位置p，p为单链表中队首器件位置。此处是将p指向的器件删除，通过更新k等级链表表头queinfo[k][0]，使链表表头指向p的下一个器件位置，完成删除操作
答案　(1)6　(2)①4　②A　(3)①total ＝ 0　②p ＝ queinfo[k][1]　③queinfo[k][0] ＝ data[p][3]
变式 某工程包含n个任务(编号为0～n－1)，每天可以有多个任务同时进行。某些任务之间有依赖关系，如图a所示，任务4依赖于任务1，任务1依赖于任务2。即任务2完成后才可以开始任务1，任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务，或多个任务依赖于同一个任务的情况。现已对该工程的依赖关系进行了梳理，结果如图b所示，标记“T”表示依赖关系需保留，标记“F”表示依赖关系需删除。
根据每个任务完成所需的天数和梳理后的依赖关系，编写程序，首先删除标记为“F”的依赖关系，然后计算工程最快完成所需的天数，并以工程最快完成所需的天数为期限，计算每个任务最晚必须开始的时间。
图a
任务A 任务B 标记
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
图b
注：任务a依赖于任务b。
答案　(1)8　(2)1　(3) ①range(m)或range(0，m)或range(0，m，1)或range(m－1，－1，－1)或range(erase(lst))或range(0，erase(lst))或range(0，erase(lst)，1)或range(erase(lst) －1，－1，－1)　②k＝task[k][1]　③w[k]＝w[task[k][1]]－task[k][0]或w[k]＝w[c[i＋1]]－task[k][0]
解析　本题考查数组的遍历、链表的遍历、创建等操作。(1)任务5和任务0有依赖关系，完成天数为8天，任务4、1、2有依赖关系，完成天数为5天，任务3需5天，存在3条链表，每天可以有多个任务同时进行，因此取最长链表所花时间，至少需要8天。(2)变量i和j分别指向数组lst的头尾元素位置，从头元素开始遍历，若遍历的元素lst[i][2]不是'T'，将尾元素为'T'的元素覆盖当前元素，并将变量j向前移动。在图b中，当i值为1时，标记为F，由于尾元素也不是T，因此仅仅变量j向前移动，变量i并未增加，再次遍历时，将一条为T的元素覆盖，因此该语句只执行了一次。(3)①首先删除标记为“F”的依赖关系，从图中可以看出，任务a依赖于任务b，任务b完成后才可以开始任务a，任务b的后继是任务a，因此语句task[lst[i][1]][1]＝lst[i][0]的作用是创建链表，并将不是头节点的元素用pr数组标
记为1。变量m调用函数返回保留的依赖关系的个数，因此需对有依赖关系的记录进行标记。②遍历每一个任务，当条件pr[i]＝＝0成立时，表示当前任务是某条链表的头节点，并开始遍历该条链表，将节点添加到列表c中，并统计该条链表所需天数s。当前节点完成遍历后，要到下一节点。③以工程最快完成所需的天数为期限，计算每个任务最晚必须开始时间，如图a中，工程最快完成所需的8天，任务5最迟在第1天完成，任务5完成在第6天，任务0则完成时间在第7、8两天，因此最迟在第7天开始。当条件task[k][1] ＝＝－1 成立时，表示任务k是任务链的尾节点，至少应该从倒数第task[k][0]天开始，或者顺数第days－task[k][0]＋1开始；若任务 k不是尾节点，该任务必须在其后续任务完成前开始，开始时间为后续任务的最晚开始时间减去当前任务完成时间。
重难点2　构建数组存储临时数据
针对情境较为复杂、结构化程度较低的问题，能抽象数据特征、创造性地运用数据结构优化算法。数据往往经过采集、传输、处理和存储的过程，而数据在加工处理过程中，要考虑算法的优越性，提高算法的效率。数据在加工过程中，临时存放的数据可以存储在队列、栈和二维数组中，利用其不用查找就可以操作或者把当前正在处理的数据放置一个较小的数组中的特性，加快数据的处理时间。
例题 某店使用加工设备制作m种类型的甜品，每分钟只能制作一种类型，且不超过n个。每个订单包含订单编号、下单时间、类型和数量。编排制作顺序的规则为：下单时间早的类型优先，下单时间相同时数量多的类型优先。下单时间最早的订单数量不足n，可以先制作部分已下单相同类型甜品。每分钟完成后，有新增订单时，合并相同类型订单，按上述规则重新编排顺序，若编排后，新订单仍有剩余，则剩余数量按实际下单时间继续参与编排。
设m为3，n为10，某时段各个订单如图a所示，则制作甜品的顺序为AABACB，数量为10、10、10、4、8、5，如图b所示。编写Python程序，根据订单，输出甜品的制作顺序和数量。
订单编号 下单时间 类型 数量
0406001 8：01 A 24
0406002 8：01 B 3
0406003 8：03 C 8
0406004 8：03 B 12
图a
图b
(1)如图a所示，若订单0406003提前到8：01下单，则制作顺序为　　　　。
(3)实现上述功能的部分Python程序如下，程序中用到的列表函数与方法如下表所示，请在划线处填入合适的代码。
函数与方法 功能
w.append(x) 在列表w末尾添加元素x
w.pop(i) 删除列表w索引为i的元素
sum(w) 累加列表w中的元素
思维点拨
明考向 本题考查队列和二维数组的应用
精点拨 (1)8：01有A，B，C共3种类型的订单，数量分别为24，3，8。前2分钟制作A类型甜品，完成后A，B，C数量分别为4，3，8，8：03时B类型订单有12，可以提前完成7个甜品，接下来制作B，C类型甜品，剩余A，B类型的数量分别为4和5，由于B类型下单时间为8：03，因此最后制作B类型甜品。(2)本题考查顺序查找，post的初值为0，变量i从1开始遍历，B选项中初值为空，因此tpr[post][0]的值为空，程序会报错。(3)①变量t为类型的编号，该订单数量u[t]数量增加lst[i][3]。②调用自定义函数least求当前制作订单编号k，语句tpr[k].pop(0)的功能是弹出订单k，表示该订单已完成，因此该订单数量须满足小于等于n－tot。③若当前时间小于新订单到来时间，须更新当前时间为新订单的到来时间
答案　(1)AABCAB　(2)B　(3)①ud[t]＋＝lst[i][3]
②npr[k][0]<＝n－tot
③curtime＝convert(lst[i][1])
变式 有新订单产生。公司安排的打包工作时间为12：00－18：00，假设当日订单在工作时间内就能完成。公司有甲、乙、丙三位师傅对货品进行打包，货品按照甲、乙、丙的顺序分配给各师傅处理，每位师傅一次打包一件货品。打包规则：若下单时间相同，优先级越高(数字越小，优先级越高)的货品，先全部打包完成；若不同，则下单时间更早的货品先处理完成。
订单输入格式示例：7A2B、4B10A(说明：4B10A指订单中有4件B类货品，10件A类货品)。编写程序，输出某天甲、乙、丙货品打包顺序和打包报酬，甲的输出示例：3A5B1C，200元。
货品 优先级 打包报酬(元/件)
A 1 30
B 2 20
C 3 10
表1
下单时间 货品及数量
12：00 2B7A
14：00 7B
15：00 6B5C
表2
(1)若某天货品下单信息如表2所示，则甲的打包顺序为3A5B1C，乙的打包报酬为　　　　元。
答案　(1)180　(2)num*10＋int(data[i])(3)①a[i][1]　②b[x]＋que[0：t]　
③goods[ord(b[i][0])－ord(″A″)]或goods[ord(b[i][0])－65]
解析　(1)12：00下单的货品需1.5个小时，在下一个时间点之前能处理完，因此甲乙丙分别处理3A、2A1B、2A1B，后面2个单子可以合并处理，甲乙丙分别处理5B1C、4B2C、4B2C。(2)取出订单data货品的数量，当数量的值大于9时，如字符串“192”转换成数字192时，依次表示为0＋1，10＋9，190＋2。(3)①遍历若干个订单数据，采用convert(data)函数将参数data订单(如2B1A1C)转换成ABBC的形式。②将当前订单写入队列que中，先找到处理的时间节点x。变量m为每半个小时为一个时间节点数量，b列表记录每个结点甲乙丙打包的货品。当b列表长度为3时，表示每个人都有工作，接下来的货品将在下一个节点完成。若货品序列没放完则需要继续按照时间节点放置，t 表示当前第 x 个时间节点还可以存放货品的个数，将新放入的货品从序列中切出来累加到当前结点 b[x]中去。③在列表中找出对应货品的打包报酬累加到总报酬中。
当堂检测
4
重难点1　构建链表建立索引关系
重难点2　构建数组存储临时数据
1.某花瓶厂有三台不同型号的机器，可生产ABC三种不同型号的花瓶。厂家每天会收到很多网上订单，每个客户的订单信息包含订单号、型号、数量和状态，其中状态值为1表示确认订单，－1表示取消订单。工作人员首先挑选出确认的订单，然后对订单按花瓶型号进行分类统计，最后交给工作人员生产。订单信息存储在“orders.csv”文件中，文件数据格式如图a所示。请回答下列问题。
图a
订单号 型号 数量 状态
s001 A 1000 1
s002 B 2000 1
s003 B 1500 －1
s004 C 900 1
s005 B 800 1
s006 C 700 1
s007 A 500 －1
s008 B 600 1
图b
(3)实现按花瓶型号分类统计花瓶数量的Python程序如下，程序运行结果如图c所示。请在程序划线处填入合适的代码。
当天订单信息为：
[['s001'，'B'，6000]，['s002'，'A'，9000]，['s003'，'C'，9500]，['s008'，'A'，5000]]
分类订单统计结果为：
['s002'，'A'，9000]→['s005'，'A'，6200]→['s008'，'A'，5000]→共计20200个
['s001'，'B'，6000]→['s006'，'B'，3000]→共计9000个
['s003'，'C'，7000]→['s007'，'C'，9500]→共计16500个
图c
答案　(1)3400　(2)line[1]　(3)①orders[p][3]＝I ②total＝total＋orders[y][2]或total＋＝orders[y][2]　③p＝p＋1或p＋＝1
解析　(1)当天应生产B型号花瓶数量为2000＋800＋600＝3400个。(2)readdata()函数的功能是过滤撤消的订单，根据第4列的订单状态，从文件中读取的前3列的数据，因此划线处代码为line[1]。(3)先根据订单中的花瓶型号构建三张链表(tlist[0]、tlist[1]和tlist[2])，分别存储不同型号花瓶的订单信息，链表tlist[]只记录首尾两张订单的索引号，中间的订单信息则记录在orders表示的链表中。要在链表中增加一个节点，可以通过tlist[i][1]直接找到链表尾节点，然后接在后面，并且更新tlist[i][1]作为新的链表尾节点，因此①处代码为orders[p][3]＝i；然后统计每张链表中的花瓶数量，统计时，首先获取当前链表中第一张订单的索引号，然后按照链表顺序将各订单的花瓶数量累加，从而求出各种型号花瓶的总数量，因此②处代码为total＝total＋orders[y][2]，接下去对存储另外型号花瓶的链表进行处理，因此③处代码为p＝p＋1或p＋＝1。
2.张三是一名计算机专业的大学生，为了帮助同学们学习专业相关的英语词汇，编写一个简易字典程序。该程序中存放词汇数据库，在学习中输入英文单词，可以获得中文翻译结果。程序中的词汇数据库采用链表方式存储，首字母相同时按升序排序。查找单词时，首先根据首字母找到同首字母最小单词所在链表，再按照链表顺序查找该单词。
(1)根据题意，部分的单词库数据逻辑结构如图所示，查找单词”byte”的过程是”binary”→”bit”→”byte”， 补充图中空白单元格的值为　　　　。
列表索引 数据区域 指针区域
0 audio 音频 －1
1 binary 二进制数 6
2 byte 字节 －1
3 cursor 光标 －1
4 access 存取 0
5 cache 高速缓存 3
6 bit 比特 　　　　
答案　(1)2　(2)①k ＝ ord(d[0]) － ord(″a″)　②q ！＝ －1 and d > data[q][0]　
③info[k] ＝ I (3)data[p][1]
解析　 本题考查链表的构建、遍历和节点的插入。(1)采用链表方式存储字母，首字母相同时按升序排序。单词bit的下一个单词为byte，因此其指针区域值为索引2。(2)①将单词d首字母转换为字母表中对应数字，info[0]表示字母 a 开头的最小单词，因此k为字母a－z对应0－25的索引号。②遍历data链表，找到单词d位置。当前节点q从头节点开始，当q值不为－1，且满足d比当前节点数据区域值大。(3)返回单词key对应的中文。每个元素包含英文单词和中文翻译。
3.某外卖平台推出同城代购服务，外卖骑手可接多个订单，但是同一时间只能完成一项订单。接单规则为：
·若骑手当前没有订单任务，则自动接收最先提交的订单任务；
·若骑手在当前订单完成前都没有接到新的订单，则输出当前订单，并接收排在最前面的订单任务；
·若骑手当前正在执行订单任务，期间有用户提交订单，则订单进入等候区，并按照所需用时升序排列。
订单信息存储在“dingdan.txt”文件中，文件格式如图a所示。文件按照下单时间升序存储所有订单信息，每一行数据存储每个订单的接收时间和完成订单的所需用时，如
(“D1，07：15：36，2400”表示：D1号订单，于07：15：36下单，需要2400秒才能完成)。
图a
订单名称　 完成时间　
　D1　　　　07：55：36　
　D3　　　　09：05：36　
　D2　　　　10：35：36　
　D4　　　　11：32：02　
　D5　　　　14：37：30　
图b
(1)如果某骑手一天内接到的订单如表所示：
订单号 接收时间 所需用时(秒)
D1 08：00：00 600
D2 08：05：00 1500
D3 08：30：00 1800
D4 08：33：00 900
D5 08：33：00 600
骑手在完成所有订单后，各个订单的完成顺序为：　　　　(订单号之间用逗号隔开，如D1，D2，D3，D4，D5)。
答案　(1)D1，D2，D5，D4，D3　(2)t＝t∥60
(3)①i(4)finish＝data[i][1]＋data[i][2]
解析　(1)D1在9：10完成，D2在9：35完成，D3、D4、D5在等候区，按时间小的先完成。(2)将数字的时间转换为小时、分钟和秒，t除以60的余数得到秒，整除60得到后的数，除以60的余数为分，整数为小时。(3)①遍历完所有订单，即订单均完成或都进入等候区，还一种情况是有订单还在等候区没有完成，即所有订单链表为空。②k表示当前节点，从头节点的下一个节点开始遍历。(4)该订单的完成时间为订单到达时间和所需时间之和。
4.某医院为实现就诊顺序规则的相对公正，实行就诊前“挂号＋签到”模式，排队规则如下：
1)初诊患者签到后，按挂号序号自小到大的顺序排队
2)复诊患者按签到顺序，以“隔2插1”的规则排队
3)年龄大于等于80岁的患者，可以优先就诊
现系统根据签到顺序记录了某天下午某科室挂号患者的信息如图a所示，包括挂号序号、姓名、年龄、初诊复诊情况(0表示初诊，1表示复诊)。经系统处理后，输出患者的就诊顺序如图b所示，请回答问题。
(3)若列表a依次存储图c的患者信息，程序运行后，加框处的语句总共执行　　　　次。
答案　(1)沈*思　(2)①(a[p][2]>＝80 or a[p][0]解析　(1)复诊患者按签到顺序，以“隔2插1”的规则排队。(2)①不能插在80岁老人或比他号小的前面。②为方便处理，在列表前加入一个虚拟节点，即头节点的后继才是链表的第1个有效节点。③依次从a队列出队2个元素，再从b队列出队1个元素，因此left需加1。(3)由于a链表有一个虚拟的头节点， 3个老人依次插入队列，指针p的移动次数依次为0、1、2。
1.某单位有多个部门，部门编号0～n－1，人数不尽相同，如图a所示。现举行某项活动，需要将所有人重新分组。分组前按部门人数由少到多的顺序(升序)排列，从人数最少的部门开始，按每m人一组划分，最后一组若不足m人，则该组不参加活动转做后勤。例如设定每组人数m＝7，各部门人数存于列表a中，a＝[3，4，2，1，6，4]，则分组情况如图b所示。
答案　(1)0，5，4　(2)[3，1，2，0]　(3)①tot＝0　②tot>＝m　③gnum＋＝1
解析　(1)第1组为3号1人，1号2人，2号2人，0号2人。第2组0号1人，5号4人，4号2人。(2)p[i]数组用于统计比了a[i]小的数的个数。比5小的数有3个，比3小的数有1个，比4小的数有2个，比0小的数有0个，因此p的值为[3，1，2，0]。(3)①从语句tot ＋＝ a[b[i]]可以得出该处应对tot赋值为0。②先按人数进行升序排列，将各组的人数累加到tot中，并将组号添加到c[gnum]。若人数达到或超过m人，将新增一组，gnum表示组号。
2.设计一个简单的快递算法。有n位骑手为一个大型超市提供同城配送服务，假设每送完一单，骑手需回超市取货。由于该超市的顾客有不同等级，因此骑手先送优先级高的订单，若优先级相同，则先送距离近的订单。编写程序实现该算法，假设不考虑路况，忽略取货、卸货花费的时间并且每位骑手的平均速度相同，则可将距离转换成单程配送时间(单位：分钟)，优先级用数字表示，数字越小，优先级越高。请回答下列问题：
订单号 优先级 单程配送时间
A 4 3
B 4 5
C 3 6
D 2 2
E 1 3
F 3 2
G 1 6
答案　(1)18　(2)①n－i－1或0，n－i－1或n－2，i－1，－1　②a[j][0]＝＝a[j＋1][0]anda[j][1]>a[j＋1][1]　(3)①rider[j]<＝nowtime或rider[j]＝＝nowtime　②nowtime＋data[i][1]或rider[j]－data[i][1]
解析　(1)先送优先级高的订单，若优先级相同，则先送距离近的订单。订单顺序为EGDFCAB，甲和乙先送订单E和G，甲回到超市时间为6，接着送D，回到超市时间为10，接着送F。乙回到超市时间为12，接着送C，所需时间为6，顾客需要等待的时间为18。(2)冒泡排序一定是一端固定，可以从前往后冒泡，也可以从后往前冒泡。若从前往后冒泡，可以修改为n－i－1。若从后往前冒泡，应为n－2，i－1，－1。(3)①rider数组存储每个骑手回到超市的时间点，nowtime表示当前时间，当前时间等于骑手回到超市时rider[j]，开始分配配送任务。②计算顾客等待时长为当前时间加上单程配送时间。由于已经更新骑手回到超市时间，也可以用骑手返回超市时间减去单程配送时间。
3.某驿站每个时刻(以秒计)都可能有一批商品到达，编写Python程序，统计商品到达时，在过去一个小时内共有几个地区(用两个大写字母表示)的商品以及商品的数量，并按商品数量从多到少显示。部分商品按到达时刻到达信息以及统计结果如表所示。
时刻(秒) 商品所属地区 各地区商品情况
1 SU KU KA KA KA SU SU KU 3　KA 3　SU 3　KU 2
3 SG KA SU SU 4　SU 5　KA 4　KU 2　SG 1
3601 KA KA SG 3　KA 3　SU 2　SG 2
3604 SG SG AU SG (略)
如上表所示，第1秒有8个商品达到，分属于3个地区。第3秒的4个商品到达后，地区数量有4个，其中商品最多的是SU。第3601秒的3个商品到达后，由于只统计1小时内的数据，因此第1秒的商品不能计算在内，该时刻的商品地区数只有3个。
请回答以下问题。
(1)对于上表中第3604秒时刻，一共有　　　　个不同地区的商品(填数量)。
(2)主程序。小林用数组c保存各个地区的商品数量和它的排名位次，用数组rank保存地区序号和商品数量并用以排序。地区序号由大写字母对应的序号转换而来。实现程序如下，请将划线处程序补充完整。
def toInt(s)：
答案　(1)3 (2)①t－q[head][0]>＝delta　②ans＋＝1
(3)①c[rank[i][1]][1]＋＝1或c[rank[0][1]][1]＝i＋1 ②rank[i＋1]＝[num，x]
解析　(1)在第3604秒，第3秒的商品不能计算在内，则第3601秒只有KASG，当第3604秒的商品达到后，增加了AU，所以一共有3个地区，答案填写3。(2)列表c存储地区的商品数量和名次，列表rank存储商品数量和地区，列表q存储所有地区和到达时间。①符合条件c[x][0]＝1(x地区商品减1)和head＋＝1(出队列)时，q队列中head指向的节点时刻与当前时刻t已经超过1小时了。②处理每个时刻到达的所有地区的数据，c[x][0]为1，说明x地区的货物首次到达，从后面输出该时刻的地区数量和各国商品数量可知，ans是当前时刻的总的地区数量，那么当x地区首次出现的时候，ans应该增加1。(3)用插入排序的方式来实现x地区在rank列表中的位置。①while条件成立时，x地区商品数量超过第i名地区的商品数量，将第i名地区数据在rank列表中后移一位，那么第i名地区的相应的名次数字也要增加1。②完成数据移动后，就要把x国的数据[商品数量，地区编码]放到rank列表的合适位置，因while循环结束时num已经小于等于rank[i][0]，那么x国数据应放到rank的i＋1位置。
课后练习
5
重难点1　构建链表建立索引关系
重难点2　构建数组存储临时数据
1.使用Python编写按文件后缀名进行分类的程序。要求实现的功能为：从文件夹中读取所有文件名，存储到 file 列表中，如：[[″000. mp3″]， [″001. pptx″]， [″002. pptx″]， [″003. jpg″]，…，[″099. jpg″]]，然后按文件后缀名进行分类，并统计每个类别下文件的数量，输出结果如图所示。
mp3类型的文件：
097.mp3 095.mp3 090.mp3 087.mp3 086.mp3 077.mp3 056.mp3 055.mp3 053.mp3 052.mp3 048.mp3 033.mp3 026.mp3 022.mp3 021.mp3 008.mp3 006.mp3 000.mp3
共18个
pptx类型的文件：
091.pptx 089.pptx 081.pptx 079.pptx 078.pptx 073.pptx 071.pptx 065.pptx 062.pptx 051.pptx 044.pptx 032.pptx 029.pptx 017.pptx 013.pptx 007.pptx 004.pptx 002.pptx 001.pptx
共19个
jpg类型的文件：
099.jpg 098.jpg 096.jpg 085.jpg 082.jpg 069.jpg 068.jpg 067.jpg 064.jpg 061.jpg 060.jpg 058.jpg 050.jpg 045.jpg 041.jpg 037.jpg 036.jpg 035.jpg 034.jpg 031.jpg 030.jpg 012.jpg 010.jpg 005.jpg 003.jpg
共25个
xlsx类型的文件：
094.xlsx 093.xlsx 088.xlsx 083.xlsx 080.xlsx 076.xlsx 074.xlsx 072.xlsx 066.xlsx 057.xlsx 049.xlsx 047.xlsx 042.xlsx 040.xlsx 027.xlsx 024.xlsx 023.xlsx 019.xlsx 018.xlsx 016.xlsx
共23个
docx类型的文件：
092.docx 084.docx 075.docx 070.docx 063.docx 059.docx 054.docx 046.docx 043.docx 039.docx 038.docx 028.docx 025.docx 020.docx 011.docx
共15个
答案　(1)n>＝0 and s[n]！＝″.″　(2)①a＝ft(file[i][0])　②fhead[j][1]＝i　
(3)①p＝fhead[i][1]　②p＝file[p][1]
解析　本题考查链表的构建和遍历。(1)文件名最后一个点的后面为后缀名，因此查找若不是点，继续查找。 (2)①语句fhead.append([a，i])为列表增加一个元素，结合语句print(fhead[i][0]＋″类型的文件：″)，因此a为后缀名，调用函数求file[i][0]的后缀。②变量j在fhead遍历，因此若在该列表中能找到a，则j的值小于len(fhead)，语句file[i][1]＝fhead[j][1]的功能是将该节点指向原头指针位置，需更新该链表的头指针。(3)①变量i遍历列表fhead，因此表示第几条链表，当前节点q从第几条链表的头指针开始遍历整个链表。②当前节点将指向下一个位置，链表信息存储在数组file中。
2.某学校工会举行飞镖大赛，共有n位老师报名参赛，每位选手共掷5支镖，每镖得分为0至10分，选手总分为5镖成绩之和，每位选手的比赛数据记录在文本文件中，如图a所示。
图a
处理前的数据为：
[['s001'，38]，['s002'，8]，['s003'，26]，['s004'，25]，['s005'，36]，['s006'，27]，['s007'，28]，['s008'，18]]
处理后的数据为：
[['s001'，38，4]，['s002'，8，－1]，['s003'，26，3]，['s004'，25，7]，['s005'，36，6]，['s006'，27，2]，['s007'，28，5]，['s008'，18，1]]
从高分到低分依次输出选手的编号和总分为：
['s001'，38] ['s005'，36] ['s007'，28] ['s006'，27] ['s003'，26] ['s004'，25] ['s008'，18] ['s002'，8] NULL
图b
处理要求：数据读入数组data中，计算出每位选手的总分，在不改变数据在原数组data中的位置的条件下，按总分从高到低输出选手的编号和总分。
(1)主程序。采用链表结构处理数据。程序运行结果如图b所示。请在程序中划线处填入合适的代码。
data ＝ readdata(″scores.txt″)　#读取数据，计算总分
print(″处理前的数据为：\\n″，data)
n＝len(data)
flag＝[True]*n　#标记数据被使用情况
head＝findmax()　#返回data中可使用状态最大数的位置
k＝head
for i in range(1，n)：
答案　(1)k＝posi　(2)s＋＝ int(line[i])
(3)①maxnum②flag[pos]＝False　(4)q！＝－1
解析　(1)查找数组中的最大值的位置，利用位置关系串成一个降序链表，最后遍历链表输出。k是当前元素的位置，posi是下一个元素的位置，找到的数应该在节点posi后面。(2)readdata函数功能是读取“scores.txt”文件，生成一个二维列表。变量s累计的总分。(3)findmax函数找到最大数所在位置，同时将改位置设置位False。(4)遍历链表，输出节点相关数据域的内容。
3.某医院的看病流程为：患者通过网上、自助设备或人工窗口成功挂号后，到门诊的签到处签到，签到成功后即可排队等待叫号就诊。简化的排队规则如下：
①当天08：00之前完成签到的患者，按照挂号顺序从小到大排队就诊；
②08：00之后签到的患者，按照挂号的序号从小到大的次序插入候诊队伍中；
③队伍中前3名患者(包括正在就诊患者)视为已进入待诊状态，插队的患者只能插到这3名待诊患者后的队伍中。
假设医生从08：00开始叫号就诊，对每位患者的诊断时间均为3分钟，忽略相邻患者就诊的时间间隔。编写程序实现以下功能：若有患者签到，则根据规则更新候诊队伍；医生每完成一名患者的诊断，电子屏幕上按顺序显示待诊的患者姓名和每个患者预计就诊的时间。
(1)若当前已签到患者信息如表所示：
姓名 挂号序号 签到时间
A 3 07：47：03
B 1 07：51：12
C 6 07：55：32
D 4 07：57：10
E 8 07：59：52
F 2 08：02：07
则患者F的预计就诊时间为　　　　(格式如08：07：20)。
答案　(1)08：09：00　(2)D　(3)t%3600∥60或t∥60%60　(4)①head＝len(lst)－1　②k<3 or data[1]>lst[q][1]
解析　(1)按照挂号的序号从小到大的次序插入前3名患者后面的候诊队伍中，每位患者的诊断时间均为3分钟，因此预计时间为08：09：00。(2)构建8点前签到的按挂号的序号从小到大候诊队伍。实现从后往前冒泡排序，前面的数据先有序，变量i记录最后一次数据交换的位置，即有序数据的个数，也就是下一趟排序的左端点。(3)m表示将时间戳转换为分，t是以秒为单位，则去除完整的小时数为t%3600，在这个数据中有多少个完整的60。(4)当无人排队时，将新签到患者直接插入候诊队伍，head将指向列表表尾；当队伍中有人排队且待诊人数不足3人时需要按优先级进入待诊队伍。
4.现有n项先后出现的任务，每项任务需要一定的时间完成，且每个时刻只能执行某一项任务。任务的处理规则如下：
1)每项任务有一个紧急程度，用数字表示，数字越大紧急程度越高。紧急程度最高的任务优先执行，紧急程度相同先出现先执行。
2)若某项任务在执行过程中出现了一个紧急程度更高的任务，则正在执行的任务将被暂停，执行该紧急程度更高的任务。
编写Python程序，实现如下功能：程序运行时，按编号升序输出各项任务数据显示如图a所示，然后根据任务先后完成的情况显示结果，如图b所示。
请回答下列问题：
(1)若有3个任务需要完成，数据如下：
1号任务：时刻1出现，完成所需时长4，紧急程度1
2号任务：时刻2出现，完成所需时长2，紧急程度2
3号任务：时刻7出现，完成所需时长1，紧急程度3
则这3个任务的完成的顺序为　　　　(单选，填字母：A.1号、2号、3号 /B.2号、3号、1号 / C.2号、1号、3号)。
答案　(1)C　(2)①n－i－1　②i head ③t[q[head]]＝＝0　
④q[tail]＝w[i][0]
解析　本题考查队列的操作。(1)1号任务在时刻1出现，在时刻2被任务2中断，时刻4任务完成，任务1继续，直到时刻7。(2)①按任务编号从前往后冒泡升序排列。第i趟实现第n－1－i个数据有序，因此j的终值为n－i－2，但range是一个左闭右开的区间。②任务没有结束的条件，变量i表示任务数量，当前入队数量i小于n或者队列中还有任务时，继续任务。③列表t存储每个任务所需时长，每次总是队首的所需时长减1，当队首元素所需时长为0时，表示该元素已经完成，需要出队。④cur记录当前任务时刻，若当前时刻有元素要入队。从输出语句print(w[q[head]][0]，cur)来看，需将任务编号w[i][0]入队。
1.某市举办科技嘉年华活动，为了激发学生的参与积极性，举办方推出了玩游戏得积分，积分兑换礼物的活动。活动中游戏分为简单和困难两种，参与游戏就可以获得相应的积分，当完成困难游戏时，除了获得相应积分外，还可获得一张“积分翻倍卡”，一张“积分翻倍卡”可用于一个简单游戏，使简单游戏的积分翻倍。
“积分翻倍卡”使用规则如下：
(1)当简单游戏开始时，如果有“积分翻倍卡”可用，则一定会使用。
(2)“积分翻倍卡”需在15分钟内使用。比如困难游戏完成时间是9：15分，则获得的“积分翻倍卡”将在9：15分激活，且超过9：30分将失效。
3)如果有多张“积分翻倍卡”，则优先使用最早的“积分翻倍卡”。
某同学的游戏记录如图a所示(类型0表示困难游戏，类型1表示简单游戏)，小明读取游戏记录，编写Python程序计算出该同学游戏的最终得分。程序运行结果如图b 所示，请回答下列问题：
序号 类型 积分 开始时间 完成时间
1 0 10 9：10 9：15
2 1 3 9：15 9：28
3 1 5 9：38 9：42
4 0 12 9：58 10：05
5 1 3 10：20 10：36
6 0 15 10：48 10：55
7 1 3 11：25 11：29
图a
(1)若某同学参加游戏的记录如图c所示，则他获得的积分是　　　　分。
答案　(1)40　(2)int(m[0])*60＋int(m[1])　(3)①que[tail]＝a[i][4]　②que[head]＋15解析　本题考查队列的基本操作。(1)完成困难游戏获得积分翻倍卡，一张积分翻倍卡使简单游戏的积分翻倍，但积分卡在15分钟内有效，14：47激活卡，15：10已经过期。积分为10＋5*2＋15＋5。(2)将时间按冒号分隔，得到一个列表，列表中有两个值，分别为m[0]和m[1]。(3)①将积分卡激活时间加入队列，困难游戏完成时间就是卡激活时间。②遍历列表b，简单游戏一开始就可以使用翻倍卡，因此计算翻倍卡的激活时间与当前简单游戏开始时间的时间差，该时间差大于15分钟时，卡失效。③使用翻倍卡，积分将翻倍。
2.某学校有n个社团组织招新(社团编号为1－n)，每个社团最多可招收m人。学生在线提交申请信息，提交内容为社团编号和对该社团的喜好程度(1－5分)，学生可同时提交报名多个社团，但只能被1个社团录取。后台自动记录学生的报名序号和全部报名信息。报名序号从1开始编号，申请信息的记录格式如图a所示，报名序号为1的学生报名3号社团喜好程度为3，同时报名2号社团喜好程度为4，还报名了1号社团喜好程度为5。
学生报名完毕后，n个社团通过抽签决定招新顺序，抽签号为1－100的随机整数，抽到数字小的社团先招录学生。每个社团招录时，系统调取报名该社团的申请信息，根据学生提交的喜好程度从高到低录取，尚未被其他社团录取的学生，喜好程度相同则按报名序号(学生的报名先后顺序)从小到大录取。
编写程序，读取每位学生的报名序号及报名信息、各社团的抽签序号，程序自动完成社团招新并输出录取结果。
例如，3个社团招新，每社团最多招收2人，社团的抽签序号依次为1、3、2，那么图a中的报名信息，招新结果如图b所示。
报名序号 申请信息(每2个数字为一组，表示社团编号，喜好程度)
1 3，3，2，4，1，5
2 3，1
3 3，2，1，4，2，4
4 3，1，1，1
5 2，1，3，1
图a
社团编号 抽签序号 有意向学生(括号中为喜好程度) 录取结果
1 1 1(5)，3(4)，4(1) 1，3
2 3 1(4)，3(4)，5(1) 5
3 2 1(3)，2(1)，3(2)，4(1)，5(1) 2，4
图b
请回答下列问题：
(1)若每个社团最多招收人数为3人，1、2、3号社团抽签序号仍为1、3、2时，对图a中的数据进行重新执行招录操作，则3号社团录取的学生为　　　　。
已知clubs为[[1，8]，[2，25]，[3，3]，[4，9]，[5，1]，[6，25]]，若①处的语句改为“for i in range(n－1)”，执行a＝px(clubs)，a的值为　　　　。(单选，填字母)。
A.[5，3，1，4，2，6] B.[5，3，1，4，2]
C.[5，3，1，4，6，2] D.[5，3，1，4，6]
答案　(1)2，5　(2)B　(3)①item[1][x＋1]　②x＝f[i][fs]　③flag[j]＝＝False and t>0
解析　(1)招生人数为三人时，1号社团将录取：1，3，4号同学；故第二个录取的3号社团只能录取：2，5同学。(2)排序后clubs数组为[[5，1]，[3，3]，[1，8]，[4，9]，[2，25]，[6，25]]，若抽签序号相同，则数组原顺序不变。只剩2个元素时，ans仅存储了倒数第2个(n－2)，最后一个元素(n－1)未被添加。(3)把原来的报名信息转换存储为每个社团的报名情况(包含报名序号和喜好程度)用f来存储，f[st][fs]表示社团st喜好fs的报名序号。①空所在代码是求得该报名情况的喜好程度fs＝item[1][x＋1]；②空所在代码是枚举各社团按喜好程度从高到低去选择出m个序号。fs这里起到了从最高分5分逐次到低分的选择过程(也是排序思想)，那么x的赋值就应该是各个报名序号，所以为x＝f[i][fs]；③空所在条件需要表达该社团人数未满，且该报名序号未被选择，所以应该填写为flag[j]＝＝False and t>0。
3.某餐厅的订单数据由线上、线下多条订单合并而成。各条订单含下单时间、菜品列表两个数据项，下单时间(各订单下单时间互不相同)的数据格式为“时：分钟”；菜品列表由互不重复的大写字母构成，按字母升序排列如“ABC”，每个字母代表一种菜品，合并后的订单数据如图a所示。
由于厨师一锅能烹饪5份同种菜品，为了提升烹饪效率，餐厅打算为厨师提供烹饪提示队列。按合并订单数据中下单时间的先后顺序逐条处理，对各条订单中的不同菜品进行统计：当某种菜品中首份菜品的下单时间超过10分钟时，或某种菜品累计份数达到5份时，该种菜品及累计份数将进入烹饪提示队列，入队后该种菜品重新开始统计。
当多种菜品符合某个入队条件时，按各菜品中首份菜品下单时间先后时间顺序入队。所有订单处理完毕，剩余未入队的菜品直接进入派单提示器队列，处理结果如图b所示。
(3)实现派单提示器队列功能的部分Python程序如下，程序中用到的列表函数与方法如表所示，请在程序划线处填入合适的代码。
函数与方法 功能
dc.append(x) 在列表dc末尾添加元素x
head＝qu.pop(x) 将列表x位置元素赋值给head，并将其从qu中删除
答案　(1)5　
(2)③　if m>＝0 and lst1[m][0]>lst2[n][0]：或if m>＝0 and lst1[m][0]>＝lst2[n][0]：
(3)①dishes_str＝orders[i][1]
②len(qu)>0 and pret－dc[qu[0]][1]>10
③pdish＝qu.pop(k)
解析　(1)从10：03分到10：11分没超过10分钟，但A菜品累计份数到达了5份，需要进入烹饪。(2)从后往前比较lst1和lst2中将下单时间晚的合并到lst1中，但如果lst1的下单时间均大于lst2的下单时间，则会发现运行有误。将变量m的边界进行限制，故答案为if m >＝ 0 and lst1[m][0] > lst2[n][0]。(3)将完成菜品k出队，并将菜品名称赋值给pbish.

展开更多......

收起↑