2025年6月选考 T11 真题解析

通过动画逐步演示链表遍历与记忆化思想，理解 tag 数组的含义。

题目

有如下 Python 程序段（高亮行表示当前执行位置）：

tag=[0]*len(data)
p=i=0
while i<len(data):
    if tag[p]==0 and data[p][1]!=-1:
        tag[i]+=1
        p=data[p][1]
    else:
        tag[i]+= tag[p]
        i+=1
        p=i

若 data = [[11,3],[23,-1],[15,0],[26,1],[63,2]]，运行该程序段后，tag[4] 的值为 ?

数据表

索引 i	data[i][0]	data[i][1] 下一个

tag 数组

tag[i] 表示从节点 i 到终点的“步数”

链表结构

演示控制

动画速度：300ms

点击“开始”逐步查看程序执行过程。

思路解析

链表结构：data[i][1] 保存的是节点 i 的“下一个”节点索引，把所有节点串成链。终点节点的 data[i][1] == -1。
tag[i] 的含义：从节点 i 出发，沿着 next 指针走到终点，一共经过多少条边（即链的长度）。
记忆化思想：当遍历到某个节点发现 tag[p] 已经被计算过，就直接把 tag[p] 加到当前结果中，避免重复遍历。这是典型的“空间换时间”。
本题答案：从节点 4 出发，路径为 4 → 2 → 0 → 3 → 1，共 4 条边，因此 tag[4] = 4。