Skip to content

2023年 408 数据结构 第 2 题

数据结构2023年选择题2分

题目

现有非空双向链表 L,其结点结构为:

prev | data | next

prev 是指向直接前驱结点的指针,next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点(非尾结点)之后插入指针 s 指向的新结点,则在执行了语句序列 s->next = p->next; p->next = s; 后,还要执行( )。

错因

A

s->next->prev = p 这一步直接错——s->next 是 p 原来的下一个结点(设为 q),它的新前驱应该是 s,不是 p。把"前驱"想成 p 是因为没意识到 s 已经插在 p 和 q 中间,q 的前驱就该跟着变。s->prev = p 本身没错,但前一句已经把 q 的反向指针写错了。

B

两条语句单独看都对:第一条把 q(即 p->next)的前驱设为 s;第二条把 s 的前驱设为 p。问题在于已经执行的两条 s->next = p->next; p->next = s; 之后,p->next 的值已经被改成了 s——所以 p->next->prev = s 实际是 s->prev = s,把 s 的前驱指向自己。这是顺序陷阱:先改 p->next 再用它做引用,引用值已经变了。

D

p->next->prev = s->prev 等价于"把 q 的前驱设成 s 的前驱",但 s 的 prev 此时还没被赋值(垃圾值),且语义本身就错——q 的新前驱应该是 s 自己,不是 s 的前驱。s->next->prev = p 又把 q 的前驱直接写成 p,跳过了 s——本质和 A 同样的错误。

总解析

插入要修改的指针总数:4 条

指针目标值
s->nextq(原来的 p->next
p->nexts
s->prevp
q->prevs

题干已经做了前两条。剩下两条要补:把 s 的 prev 指向 p、把 q 的 prev 指向 s。

关键陷阱:p->next 的值已经变了

执行完 p->next = s; 后,p->next 不再等于 q,而是等于 s。所以不能再用 p->next->prev 来表示"q 的前驱"——它现在表示的是"s 的前驱"。要再次拿到 q,必须通过 s->next(因为 s->next 已经被赋成 q)。

逐条核对 C:

  • s->prev = s->next->prevs->next 是 q,q->prev 此时还是 p(q 还没被改),所以右边 = p;执行后 s->prev = p
  • s->next->prev = ss->next 是 q,把 q->prev 改成 s ✓

两条都成立,且顺序正确(必须先用 q->prev 取出 p、再覆盖 q->prev,否则就拿不到 p 了)。

最终答案是 C。这道题的关键不是记忆四条赋值,而是理解"指针赋值是按序生效的,先用后改"

最后更新:

🎬 可视化演示
加载中...

提示:可在可视化区直接操作播放、步进、修改参数