信息技术来源：诸暨市2026年5月高三诊断性考试

第 12 题

答案与解析

参考答案

a = [[1,5],[5,2],[2,4],[2,0],[4,-1],[3,1]]
p = head = 3; q = a[p][1]
x = random.randint(1,5)
while q != -1 and a[q][0] < x:
    p,q = q,a[q][1]
t = p

程序以q访问a[q][0]，再用a[q][1]取得下一下标，直到q为-1。因此a[i][0]是结点数据，a[i][1]是后继结点下标，-1表示没有后继。由头指针head=3沿链接访问，下标顺序为3→0→5→1→2→4，数据顺序为2→1→3→5→2→4。x随机取1～5中的整数。

p从首结点开始，q从其后继开始。第一个循环跳过首结点之后连续小于x的结点，p、q分别保持为当前结点的前驱和当前结点。停止后t=p，标记前部区段的末结点；这个区段包括首结点及其后连续小于x的结点。

while q != -1:
    if a[q][0] < x:
        ...
    else:
        ...

第二个 while 从当前结点 q 继续向链表尾部遍历，并根据当前结点的数据是否小于 x 采用两种链表操作。

if a[q][0] < x:
    a[p][1] = a[q][1]; a[q][1] = a[t][1]
    a[t][1] = q; t,q = a[t][1],a[p][1]

当前结点q的数据小于x时，a[p][1]=a[q][1]让前驱p越过q，将q从原位置摘下；接着让q指向t的原后继，再让t指向q，完成在t之后的插入。最后t移到刚插入的结点，q移到p的新后继，继续检查尚未处理的部分。

else:
    p = q; q = a[q][1]

当前结点的数据不小于 x 时，不需要修改链表链接。程序令 p=q，再让 q 指向下一个结点，相当于前驱指针和当前指针各向后移动一位。

首结点保持不动，其后数据小于x的结点依原有次序集中到前部，其余结点也保持原有相对次序。

按上述分区规则，x的全部取值对应如下结果：

例如x=3时，后面的结点2被移到结点1之后，而3、5、4保持原次序。表中已覆盖x的全部可能取值，没有选项D的序列。

解析有疑问或显示异常？请先复制题目信息，再打开反馈表单填写。

题目编号：2026_05_G3_zhujimoni_q012