深耕专业教研，探索前沿技术
信息技术来源：2026年4月嘉兴市高三教学测试

第 15 题

答案与解析

第(1)小题

参考答案

3，4

每架容量为15。改题后，三种商品数量分别为39、10、20。第一轮仍按商品编号从小到大放满整架：

商品编号 第一轮使用的货架 留到第二轮的数量
1 1、2 39−2×15=9
2 无 10
3 3 20−15=5

第二轮按剩余量10、9、5的顺序，依次处理商品2、1、3：

当前商品 放置过程 放置后有关货架的空位
2（10个） 货架1～3均已满，新增货架4 货架4剩5个空位
1（9个） 货架4放不下，新增货架5 货架4剩5个、货架5剩6个空位
3（5个） 货架4、5都能放下，优先选空位更少的货架4 货架4恰好装满

商品3第一轮使用货架3，第二轮使用货架4，依次为3，4。

第(2)小题

参考答案

lst[p][2]=len(lst)-1

程序分析

def lnkinsert(x,head):
    if head==-1:
        lst.append([x[0],x[1],-1])
        head=0
    elif x[1]>lst[head][1]:
        lst.append([x[0],x[1],head])
        head=len(lst)-1
    else:
        ...
    return head

题目给定lst的每个结点为[商品编号,剩余数量,后继指针]，指针保存结点在lst中的下标，−1表示链尾。程序从空的lst开始建链：head为−1时，第一个结点下标为0，后继为−1。
若新商品剩余量大于头结点，新增结点的后继保存原head，再将head改为新增结点下标，完成头插。否则进入else，查找链中插入位置。

p=q=head
while q!=-1 and x[1]<lst[q][1]:
    p=q
    q=lst[q][2]
lst.append([x[0],x[1],q])

循环沿后继指针移动q，并让p保留刚经过的结点。只要至少向后移动过一次，停止时p就是插入位置的前驱，q指向第一个剩余量不大于新商品的结点，或为−1。
append已将新结点加到lst末尾，并让它指向q。此时新结点的物理下标为len(lst)−1，但前驱的链接尚未改接；列表中追加了结点，不等于链中已经连入该结点。

填空分析

划线处

在p为前驱的情况下，原连接为p→q，插入后应变为p→新结点→q。上一行已经保存“新结点→q”，因此只需把p的后继改为新结点下标，填写lst[p][2]=len(lst)-1。若q为−1，同一写法也能完成尾插。

原程序还存在等值边界缺陷：当x[1]等于头结点剩余量时，while一次也不执行，p=q=head。新结点指向head，再将head的后继指向新结点，会形成环；若相等值出现在链中，严格小于条件又会把新商品插到同量旧商品前面，不符合“编号小的优先”。
本题按商品编号递增调用插入函数，应让查找越过已有的同量结点，即把固定while中的x[1]<lst[q][1]改为x[1]<=lst[q][1]。这是空缺之外需要修正的条件，仅填写上述连接语句不能消除该缺陷。

第(3)小题

参考答案

  1. goods[i][1] -= m

  2. rest[j]>=cnt and rest[j]<empty

  3. hjbh += 1

程序分析

lst=[]
m=int(input("m="))
goods=[[1,31],[2,17],[3,11],[4,40]]
print(place(goods, m))

主程序先建立空链表，输入每架容量m，再把按商品编号排列的goods交给place处理。goods中的每项保存商品编号和数量；进入place后，商品数量会随第一轮放置而减少。

def place(goods, m):
    n = len(goods)
    result = []  #存放各类商品所放置的货架编号
    for i in range(n + 1):
        result.append([])
    rest = [m] * 101  #假设货架数不超过100个
    hjbh = 0
    head=-1

result建立n+1个空列表，以商品编号直接作下标，result[0]不用。rest为货架预留容量记录，初始各项均为m；hjbh从0开始，每次启用货架时递增。head=−1表示尚未建立剩余商品链表。

for i in range(n):
    while goods[i][1] >= m:
        hjbh=hjbh+1
        result[goods[i][0]].append(hjbh)
        ①
    if goods[i][1]>0:
        head=lnkinsert(goods[i],head)

第一轮逐类处理商品。数量不少于m时，先启用下一编号的货架，再将该编号加入当前商品的result列表。循环结束后，若仍有剩余，则调用lnkinsert将商品编号和剩余量加入链表，供第二轮按顺序处理。

start=hjbh+1
p=head
while p!=-1:
    cnt = lst[p][1]
    empty = m
    for j in range(start, hjbh+1):
        ...
    if empty == m:  # 若找不到，则新增一个货架，将其放置在新货架上
        ...
    result[lst[p][0]].append(ans)
    rest[ans]-=lst[p][1]
    p=lst[p][2]

第一轮结束后，1至hjbh号货架已经放满，start固定为下一编号，所以第二轮只搜索从start开始启用的货架。第一轮虽未把对应rest值清零，但这些整架不在搜索范围内，不参与后续空位比较。
p从head出发，cnt读取当前结点的剩余数量。选定货架后，将ans记入该商品的结果列表，并从rest[ans]扣除实际放入的数量；最后沿后继指针处理下一种商品。

cnt = lst[p][1]
empty = m
for j in range(start, hjbh+1):
    if ②:
        empty = rest[j]
        ans = j

货架按编号从小到大扫描。条件成立时，同时用当前货架的空位数更新empty、用编号更新ans，因此二者共同记录当前选中的候选货架。empty初值为m，用作尚未找到可用货架的标记。

if empty == m:  # 若找不到，则新增一个货架，将其放置在新货架上
    ③
    ans=hjbh
result[lst[p][0]].append(ans)
rest[ans]-=lst[p][1]
p=lst[p][2]

若搜索后empty仍为m，则进入新增货架分支，之后将hjbh作为ans。新增与复用两条路径共用后面的结果记录和空位扣减，因此新增货架也会在本轮结束时更新其剩余空位。

填空分析

①

每执行一轮while，就已经安排当前商品放满一个容量为m的货架。因此应把当前商品尚未放置的数量减去m，填写goods[i][1] -= m。不断相减后，剩余量才会降到m以下，结束第一轮整架放置。
比较表达式goods[i][1] == m不会改变数量，无法使循环结束；此处需要减法赋值。

②

货架首先必须容纳整批剩余商品，即rest[j]>=cnt；在能容纳的货架中，还要比当前候选空位更少，即rest[j]<empty。两项同时满足才更新，填写rest[j]>=cnt and rest[j]<empty。
扫描顺序按编号递增，空位相等时不更新，便能保留先遇到的较小编号，所以后一比较必须用严格小于。前一比较保留等号，允许恰好装满。
第二轮只处理0<cnt<m的剩余量，已启用货架至少放过一件商品，空位必小于m。因此empty=m能够区分“未找到”与“已找到”，不会把已选中的货架误判为未找到。

③

找不到可用货架时，应启用下一个货架编号，填写hjbh += 1。随后已有的ans=hjbh将新编号作为放置位置。rest预先设为m，无需重复初始化；后面的rest[ans]-=lst[p][1]会扣去本次放置量。
本问填空解决两轮放置的局部逻辑；剩余量相等时，仍须注意第（2）问已说明的链表缺陷。