深耕专业教研，探索前沿技术
信息技术来源：2025学年第二学期天域全国名校协作体高三4月联考

第 15 题

答案与解析

第(1)小题

参考答案

O202303→O202304→O202305

订单编号已按升序排列，以数组下标0～4为初始查找区间。每次对分点下标取(left+right)//2；目标编号大于对分点编号时，只需在右侧继续查找。

查找区间（下标） 对分点下标 访问的订单编号 比较及下一步
0～4 2 O202303 目标更大，转向3～4
3～4 3 O202304 目标更大，转向4～4
4～4 4 O202305 相等，查找结束

依次访问的订单编号为O202303→O202304→O202305。

第(2)小题

参考答案

n-i-1

解题思路

程序用两层循环比较lst中相邻位置对应的车辆，并在顺序不符合要求时交换这两个位置，采用冒泡排序。交换的是车辆结点索引，nodes中的车辆记录和下一结点索引不随之改变。

程序分析

n = len(lst)
for i in range(n-1):
    for j in range():
        idx1 = lst[j]
        idx2 = lst[j+1]
        if nodes[idx1][1] < nodes[idx2][1] or nodes[idx1][1] == nodes[idx2][1] and nodes[idx1][2] > nodes[idx2][2]:
            lst[j], lst[j+1] = lst[j+1], lst[j]

n是空闲车辆索引列表lst的长度。idx1=lst[j]、idx2=lst[j+1]取出两个相邻位置所保存的结点索引，再用nodes[idx1]、nodes[idx2]访问对应车辆记录；j是lst中的位置，idx1、idx2是nodes中的结点索引，不能混为一谈。

比较条件分为两种情况：左车电量较低时交换，使电量较高的车向左移动；电量相同但左车续航里程较大时交换，使续航里程较小的车向左移动。这个条件共同规定了“电量降序，同电量续航升序”的排列关系。

填空分析

划线处

采用从左向右扫描的冒泡过程。第i轮开始时，末尾已有i辆车就位，待排序区间为lst[0]至lst[n-i-1]。比较相邻的lst[j]、lst[j+1]，因此j应取0至n-i-2；一轮结束后，当前区间中优先级最低的车辆索引移到最右端。

range的结束值不包含在取值范围内，所以填写n-i-1，形成range(n-i-1)。这样每轮少比较末尾一个已就位元素，同时保证j+1不越界。

第(3)小题

参考答案

  1. d <= 10 and (len(parks) < 2 or parks[-1][1] == d)

  2. [nx, ny, d + 1]

  3. nodes[idx][3] = p

程序分析

def findPark(pos, ps):  # pos:当前位置[x,y]，ps:还车点列表[[编号,x,y,空闲车位,服务费],...]
    q = [[pos[0], pos[1], 0]]  # 队列q：[x,y,距离]
    visited = [pos]  # 存放已遍历坐标
    parks = []  # 存储前2个最近的还车点
    dirs = [[-1,0], [1,0], [0,-1], [0,1]]  # 上下左右移动方向

findPark从当前位置开始搜索。q中的每项按[x,y,距离]保存，起点距离为0；visited记录已经加入搜索的坐标，parks用于保存候选还车点。dirs给出每次可移动的4个相邻方向。

    while q:
        cx, cy, d = q.pop(0)
        ...

q.pop(0)从队首取出一个坐标及距离，本轮先检查该坐标是否为可用还车点，再扩展相邻坐标。

        for p in ps:
            if p[1]==cx and p[2]==cy and p[3]>0:
                if ①:
                    parks.append([p[0], d, p[4]])
                else: break

遍历ps时，先核对还车点坐标与当前坐标相同，且空闲车位数大于0。满足后由空①决定是否加入parks，保存的信息为[编号,距离,服务费]。这里的else: break只退出for p in ps，不会退出外层while，也不会阻止本轮继续扩展相邻坐标。

        for dx, dy in dirs:
            nx, ny = cx+dx, cy+dy
            if -10<= nx <=10 and -10<= ny <=10 and [nx, ny] not in visited:
                visited.append([nx, ny])
                q.append(②)

对4个移动方向分别计算相邻坐标。坐标位于给定正方形范围内且尚未访问时，先登记到visited，再追加到队尾，避免同一坐标反复入队。空②需要保持队列记录格式，并反映移动一步后的距离。注意，-10≤nx,ny≤10限制的是坐标范围，不等于从当前位置移动不超过10步。

    # 筛选服务费最低的还车点，代码略
    return bestPark[0], bestPark[1]

题面省略了按服务费筛选bestPark的代码，最后返回其编号和距离。仅凭展示部分不能验证候选为空时的处理；本题只补全三个指定位置。

def insertCar(head, idx, nodes):
    p, pre = head, -1
    while p != -1 and (nodes[p][1] > nodes[idx][1] or (nodes[p][1] == nodes[idx][1] and nodes[p][2] < nodes[idx][2])):
        pre, p = p, nodes[p][3]

nodes结点的第3项保存下一结点索引，-1表示链表结束。head保存首结点索引，idx是本次待插入车辆的结点索引；调用前该结点应尚未接入当前空闲链表。

p从首结点开始检查，pre初值-1。当前车辆电量更高，或电量相同而续航更小时，它应排在待插入车辆之前，于是执行pre, p = p, nodes[p][3]：pre记住刚经过的结点，p沿下一结点索引继续向后。停止时，pre是插入位置的前驱，p是插入位置原来的后继；p=-1表示插在末尾。

    if pre == -1:
        nodes[idx][3] = head
        new_head = idx
    else:
        ③
        nodes[pre][3]=idx
        new_head=head
    return new_head

pre=-1时，在首部插入：先让新结点连接原首结点，再把新头指针设为idx。否则，已知语句nodes[pre][3]=idx会使前驱连接新结点，头指针仍为head；空③还需处理新结点与原后继的连接。最后返回new_head。

填空分析

①

按参考答案采用“保留前两个，并保留与第二个同距离的并列还车点”的口径。候选不足2个时可以加入；已达到2个时，只有当前距离与最后一个已选候选相同才继续加入。len(parks)<2位于or左侧，候选为空时短路成立，不会访问不存在的parks[-1]。

但题干还要求移动距离不超过10，因此完整条件应为：

d <= 10 and (len(parks) < 2 or parks[-1][1] == d)

参考答案只有括号内的部分，遗漏距离限制。例如从[0,0]到[10,1]需要11步，坐标仍在程序允许范围内；若候选未满，参考写法会错误接纳该点。此处按题干补充d<=10，不改动其余固定语句。

并列口径可能使候选数超过2；若将“前2个”严格理解为最多两个，题面尚需明确并列时如何取舍。加入距离条件后只保证推荐候选不超过10步，原while仍会继续搜索正方形中的其余坐标。

②

相邻位置的坐标为nx、ny，每移动一步距离增加1，因此按[x,y,距离]的格式填写：

[nx, ny, d + 1]

队首出队、队尾入队，每次移动代价都为1，因而按距离逐层展开，构成广度优先搜索。先发现的可用还车点不会比后发现的更远。题给[2,3]到P01、P02都为2步，到P04为5步，到P03为7步，最近候选为P01、P02，其中P01服务费更低。

③

插入前，pre所指结点的后继是p；后面的已知语句会把pre的后继改成idx，因此应先让新结点连接原后继，填写：

nodes[idx][3] = p

也可写nodes[idx][3] = nodes[pre][3]，因为此时前驱的链接尚未修改。两次赋值完成pre→idx→p的连接；末尾插入时p=-1，新结点自然成为末结点。