深耕专业教研，探索前沿技术
信息技术来源：宁波“十校”2026届高三3月联考技术试题卷

第 15 题

答案与解析

第(1)小题

参考答案

2

把 4 号货物改为 B 类、价值 6 后，每次只在当前相邻且不同类的货物对中比较价值差；取走一对后，按原顺序补齐，再重新判断相邻关系。

轮次 取走的货物对 价值差 剩余货物编号（从左到右）
初始 — — 0，1，2，3，4，5，6，7，8
1 〈0，1〉 1 2，3，4，5，6，7，8
2 〈4，5〉 3 2，3，6，7，8
3 〈7，8〉 3 2，3，6
4 〈3，6〉 8 2

第 2 轮中，〈4，5〉与〈7，8〉的价值差都为 3，按“相同时取最左边”的规则先取〈4，5〉。随后〈7，8〉的差为 3，小于〈6，7〉的 4 和〈3，6〉的 8，故第 3 轮取〈7，8〉。最后只剩 2、3、6，其中 2、3 同为 B 类，能取的是〈3，6〉，最终剩余编号 2。

第(2)小题

参考答案

que[i+1]=que[i]

解题思路

程序先在列表末尾添加新元素，再从原有序部分的末尾向左比较，属于插入排序中插入一个新元素的过程。

程序分析

def insert_que(que,hwd):
    que.append(hwd)    #在列表que末尾添加一个元素hwd
    if len(que)!=1:
        i=len(que)-2
        while i>=0 and (que[i][2]>hwd[2] or que[i][2]==hwd[2] and que[i][0]>hwd[0]):
            que[i]=que[i-1]
            i=i-1
        que[i+1]=hwd
    return que

每个货物对保存为 [左侧货物编号，右侧货物编号，价值差]。循环条件先比较价值差，差相同时再比较左侧编号，对应题目要求的“价值差小的优先，差相同时左边的优先”。

append 后，i=len(que)-2 指向原有序部分的最后一项。循环向左检查优先级低于 hwd 的元素，结束后将 hwd 写入 i+1 处；加框语句需要在此过程中维持原有元素的顺序。

填空分析

que[i]=que[i-1]

循环条件成立时，que[i] 应排在 hwd 后面，需要右移到 i+1 处，为 hwd 腾出位置，因此改为：

que[i+1]=que[i]

原句 que[i]=que[i-1] 会用前一个元素覆盖当前元素，i＝0 时还会读到列表末尾的 que[-1]。改正后，循环从右向左移动元素，避免覆盖尚未移动的内容；若 i 降至 -1，最后的 que[i+1]=hwd 就把新货物对插入开头。

第(3)小题

参考答案

  1. st[a[1]]=True

  2. q=link[a[1]][1]

  3. p==-1 or q==-1

程序分析

que=[];count=0
st=[False for i in range(len(link))]
que=bl_link(que,link,head)

题干规定用列表 link 模拟双向链表，编号就是结点下标；每个结点的下标 0、1、2、3 依次保存前驱、后继、类别、价值，-1 表示没有相应邻居。que 初始为空，count 从 0 开始，各编号对应的布尔标记 st 初值为 False。接着调用 bl_link 收集当前可取的货物对。

def bl_link(que,link,head):    #寻找当前可取货物对
    p=head
    while link[p][1]!=-1:
        q=link[p][1]
        if link[p][2]!=link[q][2]:
            c=abs(link[p][3]-link[q][3])
            que=insert_que(que,[p,q,c])
        p=link[p][1]
    return que

从 head 出发，沿后继指针逐个访问结点。每次令 q 为 p 的后继，因此 p、q 是当前相邻的两个货物编号；只有类别不同时，才计算价值差的绝对值，并把 [p,q,c] 交给已改正的 insert_que 按优先级插入 que。到达没有后继的结点后停止，所得 que 保存初始可取货物对。

while len(que)!=0:
    a=que.pop(0)    #将列表que第一个元素赋值给a，并将其从que中删除
    if not st[a[0]] and not st[a[1]]:
        ...

每轮取出 que 中优先级最高的候选货物对 a。只有 a[0]、a[1] 对应的标记都为 False，才进入分支处理；其他候选直接丢弃。

st[a[0]]=True
①
count+=1
#存储取走的货物对编号，代码略

程序将 a[0] 的标记置为 True，并把 count 增加 1，结合题干可知，st 记录货物是否已被取走，count 记录取走的对数。que 中可能保留涉及已取货物的旧候选，循环中的标记检查用于排除这些候选。

p=link[a[0]][0]
②
link[p][1]=q
link[q][0]=p
if ③:
    continue
if link[p][2]!=link[q][2]:
    c=abs(link[p][3]-link[q][3])
    que=insert_que(que,[p,q,c])

p 取得 a[0] 的前驱下标。随后两条赋值试图把 p 的后继设为 q、把 q 的前驱设为 p，使被删除货物对两侧的剩余结点直接相连。连接后若两侧货物类别不同，就将新货物对插入 que；其他相邻关系不变，无须重新遍历链表。原题把边界检查放在指针赋值之后，存在下标为 -1 时误改结点的问题，详见空③。

填空分析

①

一次取走一对货物，已知语句只标记了 a[0]，还需用 st[a[1]]=True 标记另一件。否则，包含 a[1] 的旧候选仍可能通过标记检查，造成重复取货。

②

p 是被删货物对左侧的前驱；q 应取右侧货物 a[1] 的后继，才能跨过整对货物连接剩余部分，所以填 q=link[a[1]][1]。

③

后续只需检查删除位置两侧新形成的货物对。p 或 q 为 -1 时，相应一侧没有货物，应跳过类别比较和入队，因此填写 p==-1 or q==-1。

但这个条件无法阻止前面两条赋值误用 -1 下标。Python 的 link[-1] 是列表最后一个真实结点；取走首部的〈0，1〉时，p＝-1，link[p][1]=q 会把末尾结点的后继误改为 2。按第（1）问修改后的数据运行，程序最后会错误取走〈6，2〉、剩下 3，而按取货规则应取走〈3，6〉、剩下 2。

固定指针更新部分的修正建议如下，仅用于说明边界处理，不作为原题已有代码：

if p!=-1:
    link[p][1]=q
else:
    head=q
if q!=-1:
    link[q][0]=p
if p==-1 or q==-1:
    continue

这样仅在结点存在时修改其指针，删除首部货物对时更新头指针 head；两侧结点都存在时，再检查是否产生新的可取货物对。