深耕专业教研，探索前沿技术
信息技术来源：Z20+名校联盟2026届高三第三次学情诊断

第 12 题

答案与解析

本题解析

参考答案

A

程序分析

d=[['D',5],['B',6],['A',4],['C',0],['B',3],['D',1],['E',-1]]
t=h=2
p=d[h][1]
while p!=-1:
    ...

d 的每项由字符和一个下标组成，p 从 d[h][1] 取得下一个结点下标，并以 -1 为结束标记，可据此按链表理解：第 0 项是数据，第 1 项是后继指针，h=2 是头指针。初始链接为 2(A)→4(B)→3(C)→0(D)→5(D)→1(B)→6(E)→-1，括号前是结点下标，括号内是字符。t 初值为 2，p 初值为 4，外层循环从结点 4 开始处理。

d[t][1]=p ; k=p
q=d[p][1]

每轮先把 t 所指结点的后继设为 p，使它连接到当前处理结点。k 从 p 开始，q 从 p 的后继开始，准备检查后面的结点。

while q!=-1:
    if d[p][0]!=d[q][0]:
        d[k][1]=q
        k=q
    else:
        d[t][1]=d[p][1]
    q=d[q][1]

q 沿后继指针向后扫描。若 q 的字符与 p 不同，就把 q 接到 k 后面，再令 k 移到 q；这样 k 记录本轮已经接入的最后一个结点。若字符相同，k 不移动，后续接入不同字符的结点时便会越过这个重复结点；同时修改 t 的后继，使它越过 p。这里使用的是当前的 d[p][1]，它可能已在前面的重新连接中改变。

if d[t][1]==p:
    t=p
p=d[p][1]

扫描结束后，若 t 的后继仍是 p，说明本轮没有把 p 从 t 后面跳过，便将 t 移到 p；否则 t 保持不变。因此，t 用于记录已处理部分的最后一个保留结点，供下一轮重新连接。随后 p 沿本轮更新后的后继继续前进。

按上述链接变化，只跟踪影响 d[3][1] 的过程：

本轮 p 关键变化 本轮结束后的 t、p d[3][1]
4(B) 扫描到 1(B) 时发现重复，令 d[2][1]=3；随后接入 6(E)，令 d[5][1]=6，跳过结点 1 t=2，p=3 0
3(C) 后续的 D、D、E 均与 C 不同，结点 3 保留 t=3，p=0 0
0(D) q=5 时发现另一个 D，先令 d[3][1]=d[0][1]=5；q=6 时字符不同，再令 d[0][1]=6 t=3，p=6 5
6(E) 本轮开头执行 d[t][1]=p，即 d[3][1]=6；E 没有后继，内层循环不执行 t=6，p=-1 6

此时外层循环结束，最终有效链接为 2(A)→3(C)→6(E)→-1，所以 d[3][1] 的最终值是 6。