第 12 题

head = proc(head, d)  # 加框处

主程序先调用 proc，并把返回值重新赋给 head。题干给出，保留这次调用时输出 6、9、8，删除调用时输出 −12、6、−7、9、8、−6；两组输出相比，负数消失，其余数据的相对顺序不变。proc 需要完成这一处理。

def proc(head, d):
    # 算法的流程图如第12题图所示，代码略

p 从 head 开始，q 初值为 −1。p 不等于 −1 时，用 d[p][0]<0 区分负数与非负数：负数再按 q 是否为 −1 分别进入 (1)、(2)，非负数进入 (3)。这与题干所示的负数消失、其余数据保留相对应。

三条路径最后都执行 p←d[p][1]，把当前记录的第二项作为下一次访问 d 的下标，再回到 p≠-1?。因此这些记录通过下标依次连接，构成链表：每个 d[p] 是一个结点，第一项保存数据，第二项保存后继结点下标；head 是头指针，指向链表的头结点；−1 表示空指针。p 指向当前待处理的结点，沿后继依次遍历，变为 −1 时遍历结束，返回 head。

p = head
while p != -1:
    print(d[p][0])
    p = d[p][1]

函数返回后，p 先指向头结点，输出所指结点的数据，再沿后继继续遍历。因此，输出取决于头指针 head 和各结点的后继链接。要让负数不再输出，应让遍历路径跳过负数结点，同时保持其余结点的连接顺序。

由此可知，proc 的循环需要逐一判断 p 所指向的结点是否应被删除：数据为负数时，通过改变头指针或前驱结点的后继链接，将该结点从链表中删除；否则保留该结点。删除非头结点需要找到它的前驱，而流程图又用 q 是否为 −1 区分两种删除情况，因此可推测 q 用于指向 p 所指结点在当前链表中的前驱结点，−1 则表示没有前驱。

候选④修改 d[q][1]，即 q 所指结点的后继链接；要用它跳过 p 所指结点，q 就必须指向该结点在当前链表中的前驱。这也确认了前面对 q 的推测：它指向此前最后一个保留结点，q 为 −1 时则表示没有这样的结点，此时 p 指向头结点。

(1) 位于 d[p][0]<0 且 q=-1 的分支，需要删除头结点，因此要让头指针指向它的后继，即 head←d[p][1]，选③。若开头连续有负数，q 继续保持 −1，便可逐个删除头结点。

(2) 需要在当前数据为负数且 q≠-1 时删除 p 所指向的非头结点，并接好剩余链表。此时 q 指向 p 所指结点的前驱，删除前的连接为“q 所指结点→p 所指结点→p 的后继结点”，删除后应成为“q 所指结点→p 的后继结点”。因此需要改变 q 所指结点的后继字段，把 d[p][1] 写入 d[q][1]，即 d[q][1]←d[p][1]，选④。

这里 q 仍指向原来的前驱结点；若 p 指向尾结点，d[p][1]=-1，后续赋值也会正确结束循环。

(3) 需要保留 p 所指向的非负数结点，并让 q 为下一轮指向正确的前驱结点。因此应让 q 指向当前节点，即 q←p，选②；随后流程中的 p←d[p][1] 再使 p 指向下一个待处理结点。若填①，q 会指向尚未处理的后继结点，无法保持删除操作所需的前驱关系。

三处依次为③④②，对应 D。