深耕专业教研，探索前沿技术
信息技术来源：浙江七校2026年普通高等学校招生全国统一考试模拟考试

第 15 题

答案与解析

第(1)小题

参考答案

8:40

等待队列只记录尚未开始执行的任务，不包含正在执行的任务。任务1、3、4、5的GPU需求数均不超过8，先考虑分配给集群B。

时刻 事件 B正在执行的任务 B等待队列（队首→队尾）
8:02 任务1到达并开始执行，需14分钟 1，至8:16结束 空
8:05 任务3到达 1 3
8:10 任务4到达 1 3、4
8:15 修改到达时间后的任务5到达 1 3、4，已达容量2

此时B的等待队列已满，任务5转入集群S。此前没有任务转入S，S可以在8:15立即开始执行任务5。训练时长为25分钟，因此完成时间为8:15＋25分钟＝8:40。

第(2)小题

参考答案

i >= 0 and data[q[i]][2] < data[k][2]

解题思路

q原来已经有序，程序从原有序部分的末尾向前比较，将元素逐个右移，最后把k放入空出的位置，这是插入排序中的一次插入操作。本题移动的是任务在data中的下标，比较的是这些任务的GPU需求数。

程序分析

def insert_task(data, q, k):
    q.append(k)
    i = len(q)-2
    while :
        q[i+1] = q[i]
        i -= 1
    q[i+1] = k

q.append(k)先在末尾增加一个位置，i=len(q)-2指向追加前的最后一个元素。q[i]保存某个任务在data中的下标，data[q[i]][2]才是该任务的GPU需求数；待插入任务的GPU需求数为data[k][2]。

循环中q[i+1]=q[i]把当前任务下标右移一位，再令i减1，继续向前比较。循环结束后，用q[i+1]=k将待插入任务下标放入最终位置。

填空分析

while条件

要保持GPU需求数从大到小排列，应把GPU需求数小于待插入任务的已有任务右移，所以比较条件为data[q[i]][2] < data[k][2]。同时，i必须仍在原有序部分内，即i >= 0。两者都成立才继续移动，填写：

i >= 0 and data[q[i]][2] < data[k][2]

先检查i >= 0，利用and的短路求值避免越过左边界后继续访问q[i]。当原队列为空，或所有原有任务都已右移时，i=-1，最终在q[0]插入k；遇到GPU需求数相同的任务时停止移动，新任务排在已有同需求任务之后。

第(3)小题

参考答案

  1. wait[srv[j]] = 0

  2. k = srv[j]

  3. insert_task(tasks, q[2], i)

程序分析

def schedule(tasks, c):
    n = len(tasks)
    curr = [0] * 3                 #集群的当前时间
    q = [[] for i in range(3)]
    srv = [-1] * 3                 #各集群当前正在处理的任务索引
    start = [-1] * n
    wait = [-1] * n                #记录每个任务的等待时间
    for i in range(n):
        for j in range(3):
            ...
        if tasks[i][2] > 8 and len(q[0]) < c:
            ...
        elif tasks[i][2] <= 8 and len(q[1]) < c:
            ...
        else:
            ...

主程序把任务按到达时间依次存入tasks后调用schedule。tasks[i][1]、tasks[i][2]、tasks[i][3]分别是第i个任务的到达时间、GPU需求数和训练时长，i是列表下标，不是题面任务编号。

函数为三个集群各建立一个等待队列q[j]，srv[j]初值为-1，表示尚未启动任务；start、wait按任务下标保存开始时间和等待时间。外层循环依次处理新到达任务，每次先推进三个集群已有任务的执行，再为新任务选择队列。

        for j in range(3):
            k = srv[j]
            while len(q[j]) > 0 and (k == -1 or curr[j] + tasks[k][3] <= tasks[i][1]):
                srv[j] = q[j].pop(0)  #pop(0)删除列表中索引为0的元素
                if k == -1:
                    curr[j] = tasks[srv[j]][1]
                    start[srv[j]] = curr[j]
                    ①
                else:
                    curr[j] += tasks[k][3]
                    if curr[j] < tasks[srv[j]][1]:
                        curr[j] = tasks[srv[j]][1]
                        wait[srv[j]] = 0
                    else:
                        wait[srv[j]] = curr[j] - tasks[srv[j]][1]
                    start[srv[j]] = curr[j]
                ②

k=srv[j]取得该集群当前记录的任务下标。只有等待队列非空，并且满足“集群尚未启动任务”或“所记录任务能在新任务到达前（含到达时刻）完成”这两个条件之一，才从q[j]队首取出下一任务，写入srv[j]。

若k=-1，程序以取出任务的到达时间作为开始时间。否则，curr[j]先加上前一任务的训练时长，得到其完成时间；若下一任务尚未到达，则将curr[j]推迟到它的到达时间，等待时间为0；若已经到达，则以开始时间减到达时间求等待时间。

因此，任务启动后curr[j]记录它的开始时间，curr[j]+tasks[k][3]用于判断它何时完成。while会连续推进到新任务到达时刻之前能够启动的队首任务，空②需要使下一轮的任务下标与已经更新的执行状态对应。

        if tasks[i][2] > 8 and len(q[0]) < c:
            q[0].append(i)
        elif tasks[i][2] <= 8 and len(q[1]) < c:
            q[1].append(i)
        else:
            ③

GPU需求数大于8且q[0]未满时，新任务下标i追加到q[0]；GPU需求数不超过8且q[1]未满时，追加到q[1]。由这两个分支可以确定q[0]、q[1]分别是A、B的等待队列，剩余的q[2]对应S。A、B按到达顺序追加、从队首取出，保持先到先执行；else分支处理相应等待队列已满的任务。

填空分析

①

此分支已将取出任务的开始时间设为它自身的到达时间，所以等待时间为0。srv[j]保存刚取出任务的下标，应更新这个任务的等待时间，填写：

wait[srv[j]] = 0

②

本轮已经从队首取出新任务，将其下标写入srv[j]，并把curr[j]更新为它的开始时间。下一轮判断时，要用这一任务的训练时长计算完成时间，因此k也必须更新为当前srv[j]，填写：

k = srv[j]

若k仍保留前一任务的下标，下一轮就会使用旧任务的训练时长；若仍为-1，还会误入首次启动分支。

③

对应的A或B等待队列已满，新任务应转入S，并按GPU需求数从大到小插入S的等待队列。调用第（2）题的insert_task，三个实参依次为任务数据tasks、S的队列q[2]和新任务下标i，填写：

insert_task(tasks, q[2], i)