资源简介

专题19　基于数据结构的算法实现
学业要求 知　识　点 学业水平等级
1.针对模型较为隐蔽的实际问题，能认识数组、链表在组织结构、操作特性等方面的差异 4
2.从数据结构的视角审视基于数组、链表与字符串的程序，解释程序中数据的组织形式，描述数据的逻辑结构、存储结构及其操作 4
知识点　链表在数据组织中的作用
【知识梳理】
1.创建一个链表data的两条语句data＝[]；________＝－1。
2.链表data的指针区域索引为1，当前节点为q，则他下一个节点的索引是________。
3.链表data的指针区域索引为1，在头节点head前插入索引为i的节点两条语句data[i][1]＝head、________。
4.删除头链表data节点head的语句____________。
5.判断链表为空的条件是____________，链表data的首尾两个节点分别为head和tail，若链表中只有一个节点，两者关系____________。
6.将索引为i节点链接到节点tail的后面，同时更新tail的两条语句data[tail][1]＝i、________。
7.将索引为i节点插入到节点q(节点q不是头节点)的前面，pre为节点q的前驱，语句为data[pre][1]＝i；________________。
【经典案例】
由于队列是只能在队首位置出队，在队尾位置入队的受限的线性表，意味着队列中间的元素不进行操作，因此用链表存储的队列往往只要用队首head和队尾tail两个指针来记录队列的存储情况，其他节点通过指针域的值依次连接起来。在链表的链尾插入元素，然后让队尾指针指向链尾元素。链式队列的出队，就是将链表的首元节点从链表中删去，让其后继节点成为首元节点，然后让队头指针指向该节点。
【例1】 某工程包含n个任务(编号为0～n－1)，每天可以有多个任务同时进行。某些任务之间有依赖关系，如图a所示，任务4依赖于任务1，任务1依赖于任务2。即任务2完成后才可以开始任务1，任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务，或多个任务依赖于同一个任务的情况。现已对该工程的依赖关系进行了梳理，结果如图b所示，标记“T”表示依赖关系需保留，标记“F”表示依赖关系需删除。
根据每个任务完成所需的天数和梳理后的依赖关系，编写程序，首先删除标记为“F”的依赖关系，然后计算工程最快完成所需的天数，并以工程最快完成所需的天数为期限，计算每个任务最晚必须开始的时间。
请回答下列问题：
(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(lst)的数，则语句“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
任务间的依赖关系存入lst列表
lst[0]包含3项，任务lst[i][0]依赖于任务lst[i][1]，lst[i][2]存放保留/删除标记，任务数据存入task列表
task[i]包含2项，task[i][0]为完成任务所需天数，task[i][1]的初值为－1
代码略
'''
proc(n，lst，task)
思维点拨
明考向 本题考查数组的遍历、链表的遍历、创建等操作
精点拨 (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不是尾节点，该任务必须在其后续任务完成前开始，开始时间为后续任务的最晚开始时间减去当前任务完成时间
【变式1】 题目描述如例1，请回答下列问题。
(1)任务2和任务4最晚开始时间分别为________，________。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
def proc(n，lst，task)：
　 pr＝[0]*n
　 for i in range(len(lst))：
　 　　if lst[i][2]＝＝″T″：
　 　　　　task[lst[i][1]][1]＝lst[i][0]
　　　 ①________
　 fhead＝[]；days＝0
　for i in range(n)：
　　　if pr[i]＝＝0：
　　 　 fhead.append([i，task[i][0]])
　 　　　　q＝task[i][1]
　　 　 while q！＝－1：
　 　　　　　　fhead[－1][1]＋＝task[q][0]
　　 　　　 ②________
　　　　　 if fhead[－1][1]>days：
　　 　　　 days＝fhead[－1][1]
　 w＝[0]*n
　 for i in range(len(fhead))：
　 　　pre＝fhead[i][0]
　 　　w[pre]＝days－fhead[i][1]＋1
　 　　q＝task[pre][1]
　 　　while q！＝－1：
　　 　 ③________
　 　　　　pre＝q
　　 　 q＝task[q][1]
print(″工期所需最短时间″＋str(days)＋″天，各任务最晚开始时间：″，w)
lst＝[[0，5，″T″]，[5，4，″F″]，[4，1，″T″]，[1，2，″T″]，[2，3，″F″]]
task＝[[2，－1]，[1，－1]，[3，－1]，[5，－1]，[1，－1]，[6，－1]]
n＝6
proc(n，lst，task)
【变式2】 题目描述如例1，实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
def proc(n，lst，task)：
pre＝[0]*n
w＝[0]*n　#w[i]存放任务i最晚必须开始的时间
m＝len(lst)
for i in range(m)：
if lst[i][2]＝＝″T″：
　 　　　task[lst[i][0]][1]＝lst[i][1]　
#创建关系链表
　　　　 ①________
heads＝[]
days＝0　#days存放工程最快完成所需的天数
for i in range(n)：
if pre[i]＝＝0：　#若为链表的头节点
　　　　 heads.append(i)
　　　　 ②________
　　　　 s＝0
　　　 　while k！＝－1：
　　　　　　 s＋＝task[k][0]
　　　　　 　k＝task[k][1]
　　　　 if s>days：
　　　　　 　days＝s
for h in heads：
w[h]＝days－task[h][0]＋1
p＝h
k＝task[h][1]
while k！＝－1：
　　　 　③________
　　　 　p＝k
　　　　 k＝task[k][1]
print(″工期所需最短时间″＋str(days)＋″天，各任务最晚开始时间：″，w)
lst＝[[0，5，″T″]，[5，4，″F″]，[4，1，″T″]，[1，2，″T″]，[2，3，″F″]]
task＝[[2，－1]，[1，－1]，[3，－1]，[5，－1]，[1，－1]，[6，－1]]
n＝6
proc(n，lst，task)
【例2】 有2组器件共n个，要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先级。优先级有m(1编写程序模拟检测过程，先合并2组器件的数据，然后计算所有器件的平均等待时长，其中每个器件等待时长为其开始检测的时间与送达时间的时间差。(时间单位均为秒)
请回答下列问题：
(1)由题意可知，图中器件A、B、C、D的检测顺序为A－C－D－B，A、C、D的等待时长分别为0、1、0，B的等待时长是________。
送达时间 检测时长 优先级
A 0 3 2
B 1 1 2
C 2 1 1
D 4 3 0
11 3 2
12 2 2
(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]] lst1＝[[1，1，2]]
B.lst2＝[[1，1，2]] lst2＝[[0，3，2]，[4，3，0]]
C.lst1＝[[1，1，2]，[4，3，0]] lst1＝[[4，3，0]]
D.lst2＝[[0，3，2]] 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 i0：
if i　　　　 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的下一个器件位置，完成删除操作
听课笔记：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式3】 某花瓶厂有三台不同型号的机器，可生产ABC三种不同型号的花瓶。厂家每天会收到很多网上订单，每个客户的订单信息包含订单号、型号、数量和状态，其中状态值为1表示确认订单，－1表示取消订单。工作人员首先挑选出确认的订单，然后对订单按花瓶型号进行分类统计，最后交给工作人员生产。订单信息存储在“orders.csv”文件中，文件数据格式如图a所示。请回答下列问题。
(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所示。请在程序划线处填入合适的代码。
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 ik＝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 py＝tlist[p][0]
total＝0
while y！＝－1：
print(orders[y][0：3]，″→″，end＝″ ″)
②________
y＝orders[y][3]
print(″共计″，total，″个″)
③________
综合题　基于数据结构的算法
【经典案例】
【例题】 某工程的A项目有n个任务组(编号为0～n－1)，供料商每小时只提供1份原料，各组按到达时刻(到达时刻各不相同)陆续加入领料队列，领取1份原料后到队列末尾重新等待，直至领完所需原料，离开队列。若多组同时入队，则到达时刻早的优先入队。编写程序模拟领料过程，先筛选出属于A项目的任务组，再计算每个任务组完成领料的时刻(时间单位：小时)，请回答下列问题：
任务组别 到达时刻 原料需求量
第0组 0 3
第1组 1 2
第2组 2 1
图a
时刻 领料队列 轮到领料的组别
0 0 0
1 0，1 0
2 1，0，2 1
3 0，2，1 0
4 ▲
5 1 1
注：领料队列中数字代表任务组编号
图b
(1)某项目任务组信息如图a所示，部分领料过程如图 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的值是__________。
(3)编写程序模拟任务组领料过程，输出每个任务组完成领料的时刻，部分Python 程序如下，请在划线处填入合适的代码。
def proc(task, st)：
m＝filte(task, st)
for i in range(m)：
task[i].append(－1)
order＝[0] * m
i＝0；ct＝0；t＝0
while i < m or tif i < m and task[i][1] <＝ct：
　　　 　if i＝＝t：
　　　　 　　①________
　　　　　 　task[p][3]＝i
　　　　 else：
　　　　　 　task[i][3]＝task[p][3]
　　　　　 　task[p][3]＝i
　　　　　 　p＝i
　　　　i＋＝1
if i>t：
　　　 　②________
　　　　 task[k][2]＝task[k][2] － 1
　　　 　if task[k][2]＝＝0：
　　　　　 　order[k]＝ct
　　　　　 　③__________
　　　　　 　t＋＝1
　　　　 else：
　　　　　 　p＝task[p][3]
ct＋＝1
return order
'″每个任务初始数据存入 task 列表，task[i]包含 3 项，task[i][0]为该组项目名称，task[i][1]为该组到达时刻，task[i][2]为该组原料需求量，数据按到达时刻升序排列，代码略'″
st＝″A″
print(proc(task，st))　#输出该项目中每个任务组完成领料的时刻
思维点拨
明考向 本题考查循环队列的链式存储运算
精点拨 (1)领料组0已经完成领料，不再入队，因此队列中为2，1，正在领料的是2。(2)变量j从0开始遍历，当条件task[j][0]＝＝st成立时，执行i ＋＝1，因此i表示st 的值是'A'的数量。(3)①ct表示当前时间，当条件task[i][1] <＝ct成立，表示将索引i的task元素入队。从条件task[k][2]＝＝0来看，表示该组任务完成，因此t表示完成任务的数量。当i和t相等时，表示链表队列中数量为0，当前队列中只有一个元素，语句task[p][3]＝i表示节点p的后继是i，访元素的后继是本身，这就符合循环队列的特征，队尾指向队首。单向队列中若已知队尾可以得到队首位置，已知队首须遍历链表才能得到队尾，因此p为队尾，共初值为i。②当i大于t时，表示入队的元素数量大于完成数量，需进行出队操作，k为队首指针，其值为队尾p的后继。③当队首完成领料后，需从链表中删除头节点
听课笔记：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式】 某医院有m个类型的科室(编号为0至m－1)，每个科室都有若干位医生坐诊。假设每位患者都是就诊后再离开，当患者到达时，如果就诊的科室有空闲医生就直接就诊，无需等待；否则在门口排队等待看病。当前面就诊的患者离开时，后面排队的患者按排队顺序就诊。文件“mydlata.txt”记录每个科室所有就诊数据，患者等候的总时间，以便医院合理调配医生。数据样例如图a所示，每行数据包含到达或离开、就诊科室类型、到达或离开时间3项，其中时间格式为HH：MM。程序的运行结果如图b所示。
到达，0，08：00 到达，1，08：05 离开，0，08：10 到达，2，08：15 到达，1，08：25 离开，2，08：55 ……
图a
请输入科室类型的数量m：3 请输入类型0的科室坐诊医生人数：2 请输入类型1的科室坐诊医生人数：1 请输入类型2的科室坐诊医生人数：3 0类型科室的总等待时间为80分钟 1类型科室的总等待时间为80分钟 2类型科室的总等待时间为30分钟
图b
到达，0，08：00 到达，1，08：10 到达，1，08：15 离开，1，08：45 离开，1，08：35 离开，2，08：55 ……
图c
(1)若类型1的科室有两名坐诊医生，患者到达或离开的数据如图c所示，则该科室的患者总等待时间________分钟。
(2)定义如下read_data(file_path，a)函数，参数file_path表示数据文件名，参数a为列表用于存储数据，返回a。
def read_data(file_path, a)：
with open(file_path, 'r', encoding＝'utf－8') as file：　#读取TXT文件
for line in file：　#逐行读取
　　　 　row＝line.strip().split('，')
　　　 　a.append(list(map(str.strip，row)))　#将每行数据转换为列表，添加到a中
n＝len(a)
for i in range(n － 1)：
for j in range(n －i －1)：
　　　 　if a[j][2] > a[j＋1][2]：
　　　　 　　a[j], a[j ＋ 1]＝a[j ＋ 1]，a[j]
return a
下列代码和加框处代码实现相同功能的是________。(多选，填字母)
A.for i in range(1，n)：
for j in range(i，0，－1)：
if a[j][2] < a[j－1][2]：
　　　　 a[j－1]，a[j]＝a[j]，a[j－1]
B.for i in range(n － 1)：
for j in range(n － i － 1)：
if a[j][2]< a[j＋1][2]：
　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
C.for i in range(1，n)：
for j in range(i，1，－1)：
if a[j－1][2] > a[j][2]：
　　　 a[j－1], a[j]＝a[j]，a[j－1]
D.for i in range(n － 1)：
for j in range(1, n － i)：
if a[j][2]　　　　 a[j], a[j－1]＝a[j－1], a[j]
(3)实现上述功能的部分 Python程序如下，请在划线处填入合适的代码。
def ct(s)：　#时间HH：MM转化为分钟
minutes＝int(s[0：2])* 60 ＋ int(s[3：])
return minutes
m＝5　#科室类型的数量
num＝[2，1，3，2，3]　#每种科室的坐诊医生数量列
a＝[]
a＝read_data('mydata.txt'，a)　#调用read_data()函数完成数据读取及排序
queinfo＝[]
for i in range(m)：
queinfo.append([－1，－1])
q＝[]
wait＝[0]* m
for i in range(len(a)) ：
k＝int(a[i][1])　#科室类型
if a[i][0]＝＝'离开'：　#a[i][0]代表状态“到达”或“离开”
num[k] ＋＝1　#对应类型科室空闲医生增加1
if queinfo[k][0] ！＝－1：
　　　 　t＝ct(a[i][2]) － ct(q[queinfo[k][0]][1])　#a[i][2]代表时间
　　　 　①________
　　　　 next_in_queue＝q[queinfo[k][0]][2]
　　　 　if next_in_queue ！＝－1：
　　　　　 　queinfo[k][0]＝next_in_queue
　　　　 else：
　　　　　 　queinfo[k][0]＝－1
　　　　 num[k] －＝1
else：
if num[k] > 0：
　　　　 ②________
else：
　　　　 q.append([k，a[i][2]，－1])
　　　 　if queinfo[k][0]＝＝－1：
　　　　　 　queinfo[k][0]＝len(q)－1
　　　　 else：
　　　　　 　③________
　　　　 queinfo[k][1]＝len(q) － 1
for i in range(m)：
print(i，″类型科室的总等待时间为″， wait[i]，″分钟″)
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, 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 9：15时刻使用了积分翻倍卡； 10：20时刻使用了积分翻倍卡； 10：55时刻生效的积分翻倍卡过期； 总共获得积分为：57分，剩余积分卡有：0张。
图b
(1)若某同学参加游戏的记录如图c所示，则他获得的积分是________分。
序号　 类型 积分 开始时间 完成时间 1, 0, 10, 14：15, 14：20 2, 1, 5, 14：30, 14：33 3, 0, 15, 14：40, 14：47， 4, 1, 5, 15：10, 15：13
图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 headprint(que[head]//60，″：″，que[head] % 60，″时刻生效的″＋″积分翻倍卡过期；″)
head＋＝1
if headprint(b[i][3]//60，″：″，b[i][3]%60，″时刻使用了积分翻倍卡；″)
③________
head＋＝1
else：
total＋＝b[i][2]
print(″总共获得积分为：″，total，″分，″，″剩余积分卡有：″，tail－head，″张。″)
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秒才能完成)。
(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 ilink.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 iq＝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.学校筹办校庆，向校友提供“教室预约”服务。校友以班级为单位，在线提交预约申请。学校当前预备了 m个教室，按“教室名”升序排序后编定“教室序号”。教室信息和预约申请内容如下图所示(教室已按教室名升序排序，预约申请中“预约序号”为 0 的记录表示：91 届 1 班的校友申请在 8：00－9：30 期间使用教室)。
教室序号 教室名
0 立德楼101
1 立德楼102
2 立德楼201
3 立德楼202
4 行知楼101
5 行知楼102
6 行知楼201
7 行知楼202
8 行知楼203
图a
预约序号 校友班名 起始时间 结束时间 电话 …
0 91届1班 08：00 09：30 … …
1 88届1班 08：00 10：00 … …
2 07届6班 13：00 14：30 … …
3 00届5班 10：30 11：30 … …
4 94届2班 09：30 11：30 … …
5 12届3班 12：30 14：00 … …
6 15届2班 09：30 11：00 … …
7 22届9班 13：00 15：00 … …
8 20届3班 15：00 16：30 … …
9 19届3班 14：00 16：00 … …
图b
学校按“预约序号”顺序，逐条处理预约申请，处理时按“教室序号”顺序，逐个教室检查，安排使用第一个预约时间不冲突的教室。按此规则逐条处理上图的 10 条申请，“立德楼 101”教室将安排“预约序号”为 0、2、 3、8 的申请。
编写程序实现预约功能，按时间顺序输出各个教室接受的预约安排，如图c所示。
接受申请的教室具体安排如下： 立德楼101： 91届1班08：00—09：30　00届5班10：30—11：30　07届6班13：00—14：30　20届3班15：00—16：30 立德楼102： 88届1班08：00—10：00　12届3班12：30—14：00　19届3班14：00—16：00 立德楼201： 94届2班09：30—11：30　22届9班13：00—15：00 立德楼202： 15届2班09：30—11：00 >>>
图c
部分代码如下，请回答以下问题。
(1)上例中若新增一个使用时间为“8：00－9：00”的申请，应安排的“教室序号”为________。(填写 0－8 的数字)
(2)定义 check(k，i)函数，功能为判断预约序号为 k 的申请，能否安排到序号为 i 的教室。
def check(k，i)：
n＝len(jslst[i][2])　#列表 jslst[i][2]存储教室序号为 i 的教室已接受的预约序号
if n＝＝0：
return True
for p in jslst[i][2]：
if not(yylst[k][3] <＝yylst[p][2] or ________):
return False
return True
划线处应填写代码：________
(3)定义 work(k)函数，功能为依次枚举每个教室，为“预约序号”为 k 的申请安排教室。
def work(k)：
p＝－1
for i in range(len(jslst))：
if ________：
jslst[i][2].append(k)　#将“预约序号”k存入“教室序号”为i的教室
　　　 　p＝i
　　　 　break
return p
划线处应填写代码：________
(4)定义sort(a)函数，参数列表a中的存储“预约序号”，将这些申请按题意排序。
def sort(a)：
n＝len(a)
for i in range(n－1)：
for j in range(0，n－i－1)：
　　　 　if yylst[a[i]][2]__>__yylst[a[i＋1]][2]__：
　　　　 　　a[i]，a[i＋1]＝a[i＋1]，a[i]
若将划线处的代码修改为 yylst[a[i]][3] > yylst[a[i＋1]][3]，排序结果________改变。(填：会/不会)
(5)主程序。读入预约申请信息存入列表 yylst，存储格式为[预约班名，开始时间，结束时间，教室序号], 如[3，'00 届 5 班'，'10：30'，'11：30'，1]，“预约序号”为 3 的申请，安排在“教室序号”为 1 的教室，时间格式统一为 5 位字符组成″××：××″。
读入升序排序的教室清单存入一维数组 jslst，如[0，'立德楼 101'，[0，2，4]]，表示“教室序号”为 0 的教室，接受“预约序号”为 0，2，4 的 3 个预约申请。
for i in range(len(yylst))：　#按“预约序号”顺序，逐条处理预约申请
t＝work(i)
if ________：
print(″预约序号为″，i，″的申请无法被安排″)
else：
yylst[i][4]＝t
for i in range(len(jslst)): #对各个教室接受的预约安排进行排序
sort(jslst[i][2])
#输出各个教室接受的预约安排，代码略。
划线处应填写代码：________
5.某医院的看病流程为：患者通过网上、自助设备或人工窗口成功挂号后，到门诊的签到处签到，签到成功后即可排队等待叫号就诊。简化的排队规则如下：
①当天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 ik＝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
6.某医院为实现就诊顺序规则的相对公正，实行就诊前“挂号＋签到”模式，排队规则如下：
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的患者信息，程序运行后，加框处的语句总共执行________次。
专题19　基于数据结构的算法实现
知识点
知识梳理
1.head　2.data[q][1]　3.head＝i　4.head＝data[head][1]　5.head＝＝－1　head＝＝tail　6.tail＝i　7.data[i][1]＝q
经典案例
例1　(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　(1)4，8　(2)①pr[lst[i][0]]＝1　②q＝task[q][1]
③w[q]＝w[pre]＋task[pre][0]
解析　本题考查链表的构建和遍历。(1)任务2、1、4共需时间为5天，那么任务2作为大任务最晚开始时间为8－5＋1＝4，任务2的完成时间4＋3＝7，任务1的开始时间就是任务2的完成时间，任务1的完成时间为8，因此任务4的开始时间为第8天。(2)①在task链表中，节点lst[i][1]的后继是lst[i][0]，从而说明节点lst[i][0]是有前驱的。②fhead数组中存储每个链表头指针和每项任务的天数和，在遍历该链表时，节点q应向后移动。②计算每个节点的最晚开始时间，当作任务的开始时间就是前一任务的结束时间，而前一任务的结束时间为他的开始时间w[pre]与他的所需天数task[pre][0]之和。
变式2　①pre[lst[i][1]]＝1　②k＝i　③w[k]＝w[p]－task[k][0]
解析　本题与例1的不同点在于链表的构建语句：task[lst[i][0]][1]＝lst[i][1]，即lst[i][0]的后继是lst[i][1]，因此是反向构建链表。①lst[i][1]有前驱。②当前节点k从没有前驱的节点i开始遍历。③链表的头节点是这一组任务最后一个需完成的任务，因此他的后继是他前面的任务，该后继的开始时间是他的完成时间减去任务所需时间，而他任务的完成时间应该是他前驱的开始时间。
例2　(1)6　(2)①4　②A　(3)①total＝0　②p＝queinfo[k][1]　③queinfo[k][0]＝data[p][3]
变式3　(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。
综合题
经典案例
例题　(1)B　(2)3　(3)①p＝i　②k＝task[p][3] ③task[p][3]＝task[k][3]
变式　(1)20　(2)AD　(3)①wait[k]＋＝t ②num[k]－＝1　③q[queinfo[k][1]][2]＝len(q)－1
解析　(1)前2名患者无需等待，队列中只有第3名患者，08：35的患者离开后，队列中的患者开始就诊，因此他的等待时间为20分钟。(2)程序的功能是按时间进行升序排列，A选项是插入排序，将第i个数据与前i－1个数据进行一趟相邻数据的比较和交换，使得前i个数据有序。B选项实现了降序排列。C选项j的终值只能取到2，因此数据a[0]未参加排序。D选项从前往后排序，j的终值为n－i－1，当i的值为0时，能对全部数据区域进行排序。(3)①计算等待时间。num[k]表示类型k科室空闲医生数量，当该元素值大于0，表示有闲医生，可以不用等待，否则进行队列等待就诊，那么该科室的总等待时间就是队列中患者的等待时间之和。queinfo[k]存储类型k科室的队首和队尾指针，当队首不为空时，表示队列中有患者，那么其等待时间就是开始就诊时间减去到达时间，而前面一名患者的离开时间恰好是该患者的就诊时间。②条件num[k]>0表示科室有空闲医生，患者无需等待，不用入队，但空闲医生的数量将要减少一名。③条件queinfo[k][0]＝＝－1表示队列为空，否则队列有元素，那么在队尾queinfo[k][1]进行入队，原队尾节点q[queinfo[k][1]]将指向该新增节点，同时将更新队尾指针。
当堂过关检测
1.(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.(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.(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)yylst[k][2] >＝yylst[p][3]　(3)check(k，i)或check(k，i)＝＝True　
(4)不会　(5)t＝＝－1
解析　(1)序号0、1、2教室使用时间为[08：00－09：30]、[08：00－10：00]、[09：30－11：30]，因此安排序号为2号教室。(2)函数check的功能为判断预约序号为k的申请能否安排到序号为i的教室，需要对已接受预约序号对应的时间区间进行遍历，早于已预约区间的起始时间或迟于已预约区间的结束时间都能被安排到该教室。(3)调用check检测当前预约序号k是否能够安排教室序号i。(4)输出结果按照每个预约申请占用的时间区间来排序，故自定义函数sort按照起始时间和结束时间都可以。(5)若预约申请无法被安排，函数work的返回结果为－1。
5.(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)略。
6.(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。

展开更多......

收起↑