深耕专业教研，探索前沿技术
信息技术来源：金丽衢十二校2025学年高三第二次联考

第 15 题

答案与解析

第(1)小题

参考答案

3

每次从已经到达使用时间的申请中，先选优先级数值最小者；同级按使用时间先后安排，使用时间相同再按提交顺序安排。a 与 e 的优先级和使用时间都相同，a 先提交，所以 a 先运行。以下时段采用左闭右开形式，例如 [480,490) 表示从第 480 分钟开始，到第 490 分钟前结束，共 10 分钟。

实际使用时段 使用者 调度依据 该段结束后 a 的剩余时长
[480,490) a a 先于同级、同时到达的 e 10
[490,520) c 0 级 c 抢占 2 级 a；510 时到达的 b 与 c 同级，不能抢在使用时间更早的 c 前 10
[520,535) b b 为 0 级，优先于 1 级 f 和 2 级 a 10
[535,541) f f 为 1 级，优先于 a 10
[541,550) a 高优先级待运行申请暂时为空，a 继续运行 1
[550,570) d 1 级 d 到达，抢占 a 1
[570,571) a d 完成后，a 用完最后 1 分钟 0

a 实际运行的三段分别持续 10、9、1 分钟，合计 20 分钟，因此用了 3 个连续时段。

第(2)小题

参考答案

  1. head[rank]=i

  2. data[head[i]][3]-=1

  3. head[i]=data[head[i]][4]

  4. data[i][j]==data[i][j-1]+1

程序分析

head=[-1]*3
t=[[] for i in range(len(data))]
for i in range(len(data)):
    rank=data[i][1]
    time=data[i][2]
    if head[rank]==-1:
        head[rank]=i
    else:
        ...

题干规定每条 data 记录的前五项依次为账号、优先级、使用时间、使用时长和指针，下标分别为 0～4。程序按 data 的原有顺序处理申请，因此处理顺序就是提交顺序。
rank 取当前申请的优先级，time 取其使用时间。head 有三个元素，分别对应 0、1、2 级；值为－1 表示该级当前没有结点。遇到该级第一个申请时，head[rank]=i 将它的数组下标记为表头。

p=q=head[rank]
while p!=-1 and time>=data[p][2]:
    q=p
    p=data[p][-1]

p 从该级表头出发，沿记录中的指针寻找插入位置；此时每条记录只有五项，所以 data[p][-1] 就是下标 4 的后继指针。这表明每个优先级对应一条用数组下标链接的链表。
只要已有结点的使用时间不晚于新申请，就令 q 保存该结点，再让 p 转到其后继。退出时，p 是第一个使用时间更晚的结点，或为－1；非表头插入时，q 是插入位置的前驱。条件使用 >=，使新申请越过使用时间相同的已有结点，从而保留提交先后的顺序。

if p==head[rank]:
    data[i][-1]=p
    ①
else:
    data[q][-1]=i
    data[i][-1]=p

如果查找后 p 仍为原表头，新申请应放在链表最前面。已有的 data[i][-1]=p 已使新结点指向原表头，空①还要处理链表入口。
否则，程序把前驱 q 的后继改为 i，再把新结点 i 的后继设为 p，形成 q→i→p 的连接；p 为－1 时，同一写法完成表尾插入。

clock=480 #实验室开放时间
while head!=[-1,-1,-1]: #安排机器使用
    for i in range(3):
        if head[i]!=-1 and data[head[i]][2]<=clock and data[head[i]][3]>0:
            ②
            data[head[i]].append(clock)
            if data[head[i]][3]==0:
                ③
            break
    clock+=1

clock 从 480 开始，每轮增加 1，表示逐分钟安排使用。内层 i 按 0、1、2 的顺序扫描优先级，只选择链表非空、使用时间已到且剩余时长大于 0 的表头申请。
找到申请后，用 append(clock) 记录本次分配的分钟，随后 break 结束优先级扫描，所以同一分钟最多分给一个申请。每分钟重新从 0 级检查，便允许新到达的高优先级申请抢占低优先级申请；同级由按使用时间和提交顺序排列的链表决定先后。
下标 3 的值参与“还有时间”和“已经完成”两个判断，因而在调度中作为剩余时长使用。记录分钟后，data 每行会增长，但前五项的位置保持不变；第一个实际使用分钟在下标 5，后续分钟依次追加。若三个级别当前都没有可运行的申请，就只推进 clock。

for i in range(len(data)):#合并连续时间存储在列表中
    t[i].append(data[i][0])
    st=ed=data[i][5]
    for j in range(6,len(data[i])):
        ...
    t[i].append([st,ed])

调度结束后，逐个处理账号的分钟记录。t[i] 先保存账号；st、ed 都从该账号的第一个使用分钟开始，分别记录当前连续段的起点和终点。
内层处理其余分钟，结束后再追加最后一段，避免最后一段因后面没有新记录而遗漏。这里保存的是包含首尾分钟编号的区间，例如 [480,489] 表示 10 个一分钟使用单位。

for j in range(6,len(data[i])):
    if ④:
        ed=data[i][j]
    else:
        t[i].append([st,ed])
        st=ed=data[i][j]

条件成立时，只把当前段的终点 ed 扩展到新分钟；否则，先保存旧段，再以新分钟同时作为下一段的起点和终点。无论进入哪个分支，本轮结束后 ed 都等于刚处理的分钟，因此下一轮开始时，ed 也就是上一条分钟记录。

填空分析

①

当前是表头插入。已有语句已让新结点 i 指向原表头 p，还须让该优先级的入口指向新结点，因此填写 head[rank]=i。这样才能从 head[rank] 访问新结点及其后的整条链表。

②

本轮为 head[i] 对应的申请分配了 1 分钟，而下标 3 保存其剩余使用时长，所以应将它减 1，填写 data[head[i]][3]-=1，也可写为 data[head[i]][3]=data[head[i]][3]-1。
不能写成 data[head[i]][3]=1：这会把剩余时长反复设为 1，后面的等于 0 条件始终不能成立，该申请无法正常完成并退出。

③

剩余时长减到 0 后，该申请已经完成，应从本优先级链表的表头移除，让表头转到它的后继，填写 head[i]=data[head[i]][4]。后继为－1 时，该级链表变空。
此时程序已经追加了使用分钟，data[head[i]][-1] 指向的是最后记录的分钟，不再是后继指针，因此必须用固定下标 4。

④

当前分钟比上一条记录恰好多 1 时，两次使用连续，可合并到同一时段。因此填写 data[i][j]==data[i][j-1]+1。由于进入本轮时 ed 等于上一条分钟记录，写成 data[i][j]==ed+1 也等价。
若相差大于 1，说明中间有暂停，应保存原时段并另起一段。