深耕专业教研，探索前沿技术
信息技术来源：温州市普通高中2026届高三第二次适应性考试

第 15 题

答案与解析

第(1)小题

参考答案

1

订单101需要A类设备，从时刻2运行3个单位时间，在时刻5完成；订单102也需要A类设备，恰好在时刻5开始，因此二者应合并为从时刻2连续运行到时刻11的订单。

按开始时刻依次分配合并后的订单：

订单 所需类型 开始时刻 分配依据与结果
101与102合并 A 2 A类设备0、1、2原完成时刻分别为0、2、4，选完成时刻最早且可用的设备0，更新其完成时刻为11
103 C 7 设备3为C类，完成时刻5不晚于7，可承接该订单，更新其完成时刻为12
104 A 8 设备0要到11才完成，不能使用；设备1、2的完成时刻仍为2、4，均可用，其中设备1完成得更早

因此104应分配给设备1。参考答案给出0，但设备0在时刻8仍执行合并订单，与“每台设备一次只能处理一个订单”不符；按当前题干和图示数据计算，应为1。

第(2)①小题

参考答案

4

程序分析

res = []
for i in range(len(orders)):
    tp, st, t = orders[i][1], orders[i][2], orders[i][3]
    ...
return res

调用merge(orders)后，先建立空列表res，再按orders原有顺序处理各订单。依据题给数据项，tp、st、t依次取当前订单的设备类型、开始时刻和运行时长。

k = -1
for j in range(len(res) - 1, -1, -1):
    if res[j][0] == tp:
        k = j
        break

从res末尾向前查找，遇到第0项与当前设备类型tp相同的记录，就把其下标保存到k并停止查找。因此k指向res中位置最后的同类型记录；若没有找到，k保留为－1。这里比较的是设备类型，不要求两笔订单在原输入中相邻。

if k != -1 and res[k][1] + res[k][2] == st:
    res[k][2] += t
else:
    res.append([tp, st, t])

append([tp, st, t])表明res中每条记录依次保存设备类型、开始时刻、运行时长，不保留订单编号。若找到同类型记录，其开始时刻与运行时长之和就是完成时刻；只有这个完成时刻等于当前订单开始时刻，才把当前时长累加到原记录中，实现连续运行。否则追加一条新记录。合并只改变运行时长，不改变原记录的开始时刻及其在res中的下标。

按函数的合并规则处理这6笔订单：

当前订单 处理结果 res中的记录数
101：A，1，1 追加A类记录 1
102：C，1，3 尚无C类记录，追加 2
103：B，2，4 尚无B类记录，追加 3
104：C，4，3 原C类记录在1＋3＝4完成，与当前开始时刻相同，合并后运行时长为6 3
105：B，7，2 原B类记录在2＋4＝6完成，不等于7，不能合并，追加 4
106：C，7，2 原C类记录在1＋6＝7完成，可继续合并，运行时长增至8 4

最终返回[["A",1,1],["C",1,8],["B",2,4],["B",7,2]]，共有4条订单记录。

第(2)②小题

参考答案

1

共用程序分析见第(2)①小题。

最后处理订单106，其设备类型为C。此时res中下标0、1、2、3处的类型依次为A、C、B、B。反向查找先检查下标3、2，均为B；到下标1时找到C，将k置为1并break。

随后对该记录累加运行时长，不会改变k；函数也不再处理新的订单。因此k的最终值为1。

第(3)小题

参考答案

  1. lst[best][2] > a[1]

  2. lst[best][2] = a[1] + a[2]

  3. lst[p][3] = lst[best][3]

程序分析

for i in range(m):
    lst[i].append(i + 1)
lst[m - 1][3] = -1
orders = merge(orders)

按主程序执行顺序看，lst中的每条设备记录原有设备编号、设备类型、完成时刻三项。追加的第3项保存下一个设备结点在lst中的下标，最后一个结点用－1表示没有后继，由此建立以列表存储结点的单链表。设备编号保存在lst[i][0]，不能把编号与结点下标混为一谈。

orders经过merge后，每条记录只含设备类型、开始时刻和运行时长。这里按第（3）小题的说明，各设备完成时刻初值均为0；第（1）小题图b是另一组给定的设备状态。

head = 0
for i in range(len(orders)):
    p = proc(orders[i],head)
    # 输出订单分配后的设备信息，代码略

head初值为0，指向初始链表的首结点。主程序逐条将合并订单和头指针传入proc。进入函数后，参数a的三项a[0]、a[1]、a[2]分别表示该订单所需设备类型、开始时刻和运行时长。

p,best = -1,head
while best != -1:
    if ①:
        best = -1
        break
    if lst[best][1] == a[0] and lst[best][2] <= a[1]:
        print("启动的设备编号为：",lst[best][0])
        break
    p = best
    best = lst[best][3]

best从首结点开始沿后继下标移动；每次移动前把当前下标交给p，因此查找过程中p保存best所指结点的前驱下标，－1表示尚无前驱。

第二个if同时检查设备类型与可用时刻：类型与a[0]一致，并且设备完成时刻不晚于订单开始时刻a[1]，就选中该设备并输出其编号。否则继续沿链表查找。空①成立时，会把best置为－1并结束查找，转入后面的分配失败处理。

if best == -1:
    # 分配失败，该订单另作处理，代码略
else:
    ...
return head

best为－1时分配失败；否则进入成功分支，处理被选设备，并最终返回头指针head。以下三个部分都属于成功分支。

②
if best == head:
    head = lst[head][3]
else:
    ③

选中首结点时，head改为原首结点的后继下标，使原首结点退出当前链表。best仍保留该设备结点的下标，其记录仍存放在lst中，后续可以再次接入链表。选中的不是首结点时，程序进入空③所在分支。

p,cur=-1,head
while cur != -1 and lst[cur][2] <= lst[best][2]:
    p = cur
    cur = lst[cur][3]

重新从当前首结点查找，依次越过完成时刻不大于被选设备完成时刻的结点。若其余结点已按完成时刻非递减排列，停止时cur指向第一个完成时刻更大的结点，或为－1表示已到链表末尾；p保存插入位置的前驱下标。这里重新给p赋值，它已不再表示被选设备原来的前驱。

if p == -1:
    lst[best][3] = head
    head = best
else:
    lst[best][3] = cur
    lst[p][3] = best

p为－1时，在首结点之前插入：先让被选设备的后继指向原首结点，再把head改为best。否则先让被选设备的后继指向cur，再让p所指结点的后继指向best，形成“p所指结点→被选设备→cur所指结点”；cur为－1时就是插在末尾。完成时刻相等的已有结点已被前面的循环越过，因此新插入结点排在这些结点之后。

整体功能

第（3）小题中设备完成时刻初值均为0，初始链表已有序。三个空需要配合已知代码，使一次成功分配后先更新完成时刻、移出被选结点，再按新完成时刻重新插入，从而保持链表按完成时刻非递减排列。查找时才可以通过从前往后扫描，优先选到完成时刻最早的同类可用设备。

原主程序另有一处不属于填空的错误：proc返回新的头指针，但调用处写成p = proc(orders[i],head)，没有更新下一轮使用的head。首结点改变后，后续查找可能从旧首结点开始而遗漏设备。例如两台A类设备初始完成时刻均为0，先后处理开始时刻1、3且时长均为1的两笔订单，第一次应选设备0，之后设备1完成时刻更早；原主程序却可能连续两次选设备0。三个填空可分别确定，但不能据此认定原主程序的连续分配已经正确。以下填写只针对proc在传入有效头指针、有序链表时应完成的操作。

填空分析

①

此处需要填写允许提前判定分配失败的条件。链表按完成时刻非降序排列，若当前设备完成时刻已经晚于订单开始时刻，后面的设备也都来不及承接该订单，无须继续检查类型。因此填写：

lst[best][2] > a[1]

完成时刻恰好等于开始时刻时，设备可以立即承接新订单，所以这里使用严格大于。

②

分配成功后，设备将在订单规定的开始时刻a[1]启动，运行a[2]个时间单位，因此新的完成时刻是a[1]＋a[2]，应写入被选设备记录中下标为2的数据项：

lst[best][2] = a[1] + a[2]

不能在设备原完成时刻上直接加运行时长，因为设备可能先空闲一段时间，到订单开始时刻才重新运行。

③

此处处理被选设备不是首结点的情况。此时p仍保存该结点原来的前驱下标，lst[best][3]保存其原后继下标。为将被选结点移出原位置，应让前驱直接连接它的原后继，填写：

lst[p][3] = lst[best][3]

这样只改变链表连接关系，不删除lst中的设备记录，后续仍可按best重新插入。若被选设备原在末尾，其后继下标为－1，同一赋值也能正确处理。