深耕专业教研，探索前沿技术
信息技术来源：湖州、衢州、丽水2026年4月三地市高三教学质量检测

第 15 题

答案与解析

第(1)小题

参考答案

4

中途没有出库操作，最终分堆只取决于已入库编号的连续关系。将编号升序排列，得到1、2、3、5、6、7、10、11、13、14，连续区间为：

连续编号 物品数量
1～3 3
5～7 3
10～11 2
13～14 2

区间之间分别缺少4、8和9、12，不能继续合并。按数量升序排列只改变各堆的先后次序，不改变堆数，因此共4堆。

第(2)小题

参考答案

4

程序分析

def cnt(t):                         # 计算t指向的堆的物品数量
    return data[t][1]-data[t][0]+1
def proc(p,m):
    k=data[p][2]
    while k!=-1 and cnt(k)<cnt(m):
        p=k
        k=data[k][2]
    data[p][2]=m
    data[m][2]=k

题干规定每个结点的前两项是堆的起止编号，第三项是后继结点下标。调用proc(2,3)时，p初值为2，m为待插入结点3。函数先令k指向p的后继，再通过cnt(k)与cnt(m)比较堆的大小；cnt用“终止编号−起始编号＋1”计算数量。

当后继存在且数量小于待插入堆时，p移到k，k再移到其后继。因此p、k始终是相邻的两个位置；循环停在表尾，或第一个数量不小于待插入堆的结点之前。最后依次设置p的后继为m、m的后继为k，完成p→m→k的连接。

待插入结点3表示编号5～6，共2件。由p=2出发，原后继链为2→1→0→4→−1，其中结点1、0各有1件，结点4有6件。

比较前p 比较前k cnt(k)与2比较 处理结果
2 1 1<2 p=1，k=0
1 0 1<2 p=0，k=4
0 4 6<2不成立 停止查找

插入后连接关系为2→1→0→3→4→−1。data[3][2]保存结点3的后继下标，值为4；它不是该堆的物品数量。

第(3)小题

参考答案

  1. cnt(data[p][2])<=n

  2. head=data[head][2]

  3. total-=item[1]

程序分析

data=[]
head=-1
total=0
for item in items:
    if item[0]=="in":
        head=stockin(head,item[1])
        total+=1
    else:
        if total>=item[1]:
            result,head=stockout(head,item[1])
            ③
            # 按要求输出result的内容，代码略
        else:
            # 取消本次需求，代码略

主程序令head=-1、total=0，从空仓库开始处理操作。入库时调用stockin更新链表，并将total增加1；出库前用total与申请数量item[1]比较，可确定total记录当前库存总件数。库存足够时，调用stockout得到出库编号列表result和更新后的head，随后由空③更新库存总量。stockout中的形参n最初等于本次申请数量。

def stockout(head,n):
    res=[]
    while n!=0:
        if cnt(head)>n:
            # 从head指向的堆取n个物品，将其编号加入列表res，代码略
            data[head][0]+=n
            n=0
        else:
            ...
    return res,head

题干规定每个结点依次保存堆的起始编号、终止编号和后继结点下标，cnt用“终止编号−起始编号＋1”计算堆的数量。链表按数量升序排列，head指向最小堆。

stockout用res保存已取出的物品编号，在n不为0时继续处理。若cnt(head)>n，则所有堆的数量都大于当前需求，从首堆取n件即可；起始编号增加n，n置0，结束本次出库。首堆剩余数量更小，仍应位于表头。否则进入整堆出库分支。

        else:
            q=-1
            p=head
            while data[p][2]!=-1 and ①:
                q=p
                p=data[p][2]
            n=n-cnt(p)
            # 取出p指向的堆中全部物品，将其编号加入列表res，代码略
            if p==head:
                ②
            else:
                data[q][2]=data[p][2]

p从head开始，q初值为-1。每次前进先令q=p，再令p指向后继，因此p离开表头后，q始终指向p的前驱。空①与“后继存在”共同控制查找是否继续。

查找结束后，将p所指堆全部出库，并从n中减去cnt(p)，据此可确定n需要记录尚需出库的数量。随后删除该结点：若p不是表头，令前驱的指针域保存p的后继下标；若p是表头，则由空②更新head。其余堆的相对顺序保持不变，下一轮仍可按数量升序查找。

填空分析

①

进入整堆出库分支时，首堆数量不大于n。题目要求优先取恰好为n的堆，否则取小于n的最大堆。沿数量升序的链表，只要下一堆的数量不大于n，就继续向后查找，填写：

cnt(data[p][2])<=n

等号使数量恰好为n的后继堆也能被选中。前半个条件先检查后继是否存在，利用and的短路求值避免将-1作为结点下标访问。

②

p==head时，出库后需要删除首结点，应让head指向原首结点的后继，填写：

head=data[head][2]

若这是最后一个结点，其后继为-1，更新后即为空链表。

③

库存足够时才调用stockout，函数返回后，本次申请的item[1]件物品已全部出库。因此应从原库存总件数total中扣除item[1]，填写：

total-=item[1]