深耕专业教研，探索前沿技术
信息技术来源：2025学年第二学期精诚联盟高三适应性联考

第 12 题

答案与解析

本题解析

参考答案

A

程序分析

h=h1=p=0; h2=q=6
while p!=q:
    ...

题干说明d模拟链表，每个结点由数据域和指针域组成。结合后面的比较与后继访问可知，d[i][0]保存结点i的数据，d[i][1]保存其后继结点的下标。

h、p从第一条链表的首结点下标0开始，q从第二条链表的首结点下标6开始。第一条链表的首结点数据较小，所以合并后的头指针h保持为0。外层条件p!=q比较的是结点下标：p、q指向同一个结点时结束，而不是两个结点的数据相等时结束。

t=d[p][1]
while d[t][0]<d[q][0]:
    p=t
    t=d[t][1]

t先保存p的后继结点下标。只要t所指结点的数据小于q所指结点的数据，就让p移到t，再让t移到下一个结点。因此，这段循环沿p所在链表向后查找，越过数据小于d[q][0]的连续结点。

停止时，p仍是t的前驱，且d[t][0]≥d[q][0]，t所指结点已经不能排在q所指结点之前。两条链表共享末尾结点，查找至迟会在该结点停止，不需要越过表尾。

填空分析

加框处

为保持升序，下一步应把q所指结点接在p之后，执行d[p][1]=q。原来p的后继下标已经保存在t中，修改链接后，原链表尚未合并的部分仍可从t找到。

接链后，应从刚接入的q所指结点继续向后查找，把以t起始的剩余链段作为新的比较对象。因此先执行p=q，再执行q=t；顺序不能颠倒，否则会丢失原q所指结点的位置。应填入：

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

用图中数据说明各轮接链位置。下表中的数均为结点的数据域，不是存储下标：

轮次 内层循环结束时p、t、q所指结点的数据 新建立的连接 更新后p、q所指结点的数据
1 2、7、3 2→3 3、7
2 5、9、7 5→7 7、9
3 7、9、9 7→9 9、9

第三轮中t、q指向同一个公共尾结点，更新后p=q，外层循环结束。最终链表为1→2→3→4→5→7→9，公共尾结点只保留一次。