深耕专业教研，探索前沿技术
信息技术来源：浙江省新阵地教育联盟2026届第二次联考技术试题卷

第 15 题

答案与解析

第(1)小题

参考答案

101→105→107

各层编号均按升序排列。下一结点编号不大于目标时向右跳；下一结点编号大于目标时，保留当前位置并向下一层继续查找。

当前层 查找过程 本层结束位置
层2 从101开始，下一结点109大于107，不能向右跳 101，下降至层1
层1 从101跳到105；下一结点109大于107 105，下降至层0
层0 105的下一结点是107，命中目标 107

按题目示例，下降到同一编号在下一层的对应结点时不重复记录编号；被比较但没有跳到的109也不计入跳跃顺序。因此得到101→105→107。

第(2)小题

参考答案

  1. t = len(skip[i]) - 1

  2. p2 = skip[i][p2][2]

程序分析

n = len(books)
layers = len(step_list)
skip = [[] for i in range(layers)]
for i in range(layers):# 构建每一层链表
    skip[i].append([books[0], -1, -1]) # 添加头节点
    step = step_list[i]
    t = 0
    for j in range(step, n, step):
        ...
    skip[i][t][2] = -1

函数先为每层创建空的结点列表。题目规定每个结点的三个字段依次为[编号，下层索引，本层下一索引]，所以字段0保存图书编号，字段1和2保存链接用的下标，-1表示对应方向没有结点。
每层先把books[0]放在索引0处作为头结点，t初值为0；随后按该层步长选取books中的后续编号。例如步长为4时，取原列表下标0、4、8处的编号，而这些结点在本层的存储下标依次是0、1、2。

for j in range(step, n, step):
    node = [books[j], -1, -1]
    skip[i].append(node)
    skip[i][t][2] = len(skip[i]) - 1
    ①

新结点追加到skip[i]末尾后，其本层索引为len(skip[i])-1。已有语句把t所指结点的“本层下一索引”改为这个新索引，完成从原结点到新结点的横向连接。为了让后续结点接在已有链表末尾，t需要持续指向本层尾结点；空①负责维护这个状态。外层循环末尾再将尾结点的后继设为-1。

for i in range(layers - 1, 0, -1):# 建立层与层之间的链接
    p1 = 0 #p1为下层索引
    p2 = 0
    while p2 !=-1:
        ...
return skip

横向链表建立后，再从最高层向下处理相邻两层，为上层结点寻找下层中编号相同的结点。各层只保留部分图书，因此同一编号在上下两层的索引未必相同，必须建立映射。

while p2 !=-1:
    if skip[i][p2][0]==skip[i-1][p1][0]:
        skip[i][p2][1] =p1
        ②
    p1=skip[i-1][p1][2]

比较式用p2访问第i层、用p1访问第i-1层，因此p2是上层当前结点索引，p1是下层当前结点索引。编号相等时，将p1写入上层结点的字段1，建立向下链接；不相等时，上层当前结点保持等待。每轮末尾p1沿下层的字段2向右移动。由于上层是下层的子集，并且两层均升序排列，这样扫描能够依次找到上层各结点在下层的对应位置。

填空分析

①

前一行已将原尾结点连到新追加的结点，现在要让t指向这个新尾结点，填写t = len(skip[i]) - 1。本层结点按顺序逐个追加，下标连续增加，因此t += 1也等价。若不更新t，后续连接会反复覆盖旧结点的后继，不能形成完整链表。

②

当前上层结点已找到下层对应结点并完成向下链接，应转向上层的下一个结点。其索引保存在字段2，所以填写p2 = skip[i][p2][2]。这一步位于编号相等的分支内，未匹配时不能提前移动p2；处理上层尾结点后p2变为-1，下一次循环判断时结束。

第(3)小题

参考答案

  1. q != -1 and skip[i][q][0] <= target

  2. p = skip[i][p][1]

程序分析

p = 0
for i in range(len(skip) - 1, -1, -1):
    q =skip[i][p][2]
    while ①:
        ...
    if skip[i][p][0] == target:
        return True
    ②
return False

主程序先调用build_skip得到多层链表，再把skip和目标编号传给search_skip。p初值为0，对应最高层的头结点；i从最高层逐层减到0。每进入一层，先通过当前结点的字段2取得后继索引q，因此p表示本层当前位置，q表示准备判断的下一个位置。

while ①:
    p = q
    q = skip[i][p][2]

条件成立时，p移到原来的q，再从新位置读取下一结点索引。连续执行这两步，就沿本层链表向右移动；空①控制是否还能继续向右。

if skip[i][p][0] == target:
    return True
②

本层向右移动结束后，检查当前位置的编号是否等于target，命中则立即返回True；未命中时执行空②，为下一层查找准备位置。若第0层仍未找到，外层循环结束，函数返回False。

填空分析

①

继续向右必须同时满足：后继存在，即q != -1；后继编号没有超过目标，即skip[i][q][0] <= target。用and连接，填写q != -1 and skip[i][q][0] <= target。
存在性判断应放在前面，使q为-1时不再访问skip[i][q]，避免把Python的末项索引误当作有效后继。等号也必须保留：遇到恰好等于目标的后继时，要先令p移到它，后面的相等判断才能命中。

②

本层不能继续向右且尚未命中时，应下降到当前编号在下一层的对应结点，其下层索引保存在字段1，填写p = skip[i][p][1]。例如层1的105位于本层索引1，它在层0的索引是2，不能直接沿用本层下标。第0层的下层索引为-1，赋值后外层循环结束，不会再用这个值访问下一层。