Skip to content

2016年 408 数据结构 第 1 题

数据结构2016年选择题2分

题目

已知表头元素为 c 的单链表在内存中的存储状态如下表所示。现将 f 存放于 1014H 处并插入单链表,若 f 在逻辑上位于 a 和 e 之间,则 a, e, f 的"链接地址"依次是( )。

2016 真题第 1 题:单链表存储状态表

结构(文字版):表中每行给出"地址 / 元素 / 链接地址"。

地址元素链接地址
1000Ha1010H
1004Hb100CH
1008Hc1000H
100CHdNULL
1010He1004H
1014H(空)(空)

表头元素是 c(位于 1008H)。1014H 是新结点 f 的预留位置。

错因

A

把 f 插到了 e 和 b 之间,而不是 a 和 e 之间。"a→1010H"表示 a 的链接没改(仍指向 e),"e→1014H"表示 e 改指 f,"f→1004H"表示 f 指向 b。这样实际链表是 c→a→e→f→b→d,f 跑到 e 后面去了。把"f 在 a 和 e 之间"误读成"f 在 e 之后"。

B

完全没把 f 接进链表里。"a→1010H 不变、e→1004H 不变"表示 a 和 e 的链接都没修改,"f→1014H"表示 f 指向自己(自环)。f 只是被放到 1014H 这个内存地址,但 next 指针没指向链表中的任何节点,逻辑上是孤立的。错因是只看见"f 存于 1014H"就把 1014H 填到 f 的链接地址里,没理解"插入"需要修改三个指针的协同关系。

C

知道 a 要改指 f(a→1014H ✓),但把 e 和 f 的下一跳填反了:让 e 指向自己(1010H 自环),让 f 指向 b(1004H)。这相当于把 f 直接接到了 a 和 b 之间,绕过 e;e 反而被孤立成自环。错因是搞清了"a 要改",但具体"f 下一跳是谁、e 下一跳是谁"没分清——其实只要记住"e 在原链表里指向谁,插入后还指向谁"就不会出错。

总解析

先理清原链表的逻辑顺序

从表头 c (1008H) 开始顺着"链接地址"列追:

  • c 的链接地址 = 1000H → 下一个是 a
  • a (1000H) 的链接 = 1010H → 下一个是 e
  • e (1010H) 的链接 = 1004H → 下一个是 b
  • b (1004H) 的链接 = 100CH → 下一个是 d
  • d (100CH) 的链接 = NULL → 结束

所以原链表是 c → a → e → b → d

插入 f 在 a 和 e 之间,新链表应是 c → a → f → e → b → d

修改三处指针(其它结点保持不变):

结点原链接地址新链接地址含义
a (1000H)1010H(指向 e)1014H(改指 f)a 的后继从 e 变成 f
f (1014H)(新建)1010H(指向 e)f 的后继是 e
e (1010H)1004H(指向 b)1004H(不变)e 后面仍是 b,无需改

关键洞察:插入只动插入点前驱新结点两处,插入点后继的 next 不变。这里插入点前驱是 a,插入点后继是 e,e 仍指向 b,不需要改。

a, e, f 的链接地址依次是 1014H, 1004H, 1010H

最终答案是 D(1014H, 1004H, 1010H)

最后更新:

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

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