NOIP 提高组初赛 · NOIP 2010 提高组初赛试题 第 9 题

完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的 $1$ 号位置上，则第 $k$ 号结点的父结点如果存在的话，应当存放在数组中的（   ）号位置。

拿到题先别急着套公式，脑子里过一遍层序编号的规律：根是 1，左孩子翻倍，右孩子翻倍加一。反过来想，只要把 k 除以 2 取整，就正好回到父节点。

最容易掉进命题人的陷阱就是记反了方向，看到 k 就下意识想 2k 或 2k+1，那是求孩子结点的，不是求父结点。还有种情况是死记硬背公式，没理解为什么是向下取整，导致遇到奇数 k 时算错，比如 k=3 时误算成 1.5 或 2，其实父结点必须是整数下标，所以必须用 floor 函数。

考点定位 这道题考查的是数据结构中完全二叉树的顺序存储方案，核心就是记住层序编号下的父子下标关系。

概念拆解（人话版） 完全二叉树如果按层序从上到下、从左到右编号，根结点永远是 1 号。这个编号有个特别巧的性质：

• 任意结点 k 的左孩子下标是 2k；
• 任意结点 k 的右孩子下标是 2k+1。

反过来，如果你有一个结点 k，想知道它的父结点在哪，那就要做逆运算。因为编号是从根 1 开始往下扩大的，所以父结点的编号一定比 k 小。怎么算呢？

• 如果 k 是偶数，比如 k=4，那它是 2 号结点的左孩子，父结点就是 4/2=2；
• 如果 k 是奇数，比如 k=5，那它是 2 号结点的右孩子，父结点就是 (5-1)/2=2。

你会发现，不管 k 是奇是偶，直接用 k 除以 2 并向下取整（也就是数学上的 floor 函数），结果永远是对的。所以父结点下标就是 ⌊k/2⌋。

命题人怎么挖坑 命题人最喜欢在概念上玩“左右颠倒”或者“逆运算搞反”的小把戏。这题选项里就藏了两个典型坑：

• A 选项 2k：这是求左孩子的，完全答反了方向；
• B 选项 2k+1：这是求右孩子的，也是方向反了；
• D 选项 (k+1)/2：这个看着挺像那么回事，但它是把奇数 k 算成了 (k+1)/2，比如 k=3 时算成 2，其实 3 号结点的父结点明明是 1 号，所以这个公式在奇数情况下会多算 1，是个很隐蔽的错误。

只有 C 选项 ⌊k/2⌋ 才是普适的正确答案。

思考心法：拿到题先想什么？ 1. 确认题目场景：完全二叉树、顺序存储、根在 1 号位。 2. 回忆层序编号规律：左孩子 2k，右孩子 2k+1。 3. 逆向思维：既然求父结点，就要用除法，而且因为是向下取整，所以是 ⌊k/2⌋。 4. 代入验证：随便拿几个数试一下，比如 k=3，⌊3/2⌋=1（根），k=5，⌊5/2⌋=2，k=6，⌊6/2⌋=3，全对。 5. 排除干扰项：把 2k、2k+1、(k+1)/2 这些选项快速划掉，因为它们要么方向反了，要么公式不对。

避坑提醒 千万别把“求孩子”和“求父”搞混，这是最基础的陷阱。另外，看到 k 是奇数时，一定要记得用 floor 而不是直接除，否则容易算成小数或者多算 1。

考频与趋势 在二叉树基础这个大类下，题库一共考过 220 道题，覆盖 8 个考试级别（2008-2026）。从年份分布看，2023 年突然考了 20 题，2024 年更是飙到 60 题，2025 年达到 67 题，2026 年也有 28 题，说明这两年二叉树相关题目在初赛中的比重急剧上升。分赛事来看，GESP 六级考了 100 题，七级 56 题，八级 19 题，NOIP 提高组初赛考了 9 题，CSP 提高级 8 题，入门级也考了 8 题，可见二叉树是高频考点。

预测 基于 2023-2026 年连续三年高位运行的数据，以及 GESP 六级高达 100 题的体量，可以合理预测：二叉树顺序存储、层序编号、父子下标关系这类基础但容易混淆的知识点，在未来 1-2 年的 NOIP 提高组初赛、GESP 七级/八级以及 CSP 入门级/提高级中，仍将以单选题形式高频出现，命题人可能会继续通过“左右颠倒”或“奇偶边界”来设置陷阱。暂无足够依据预测具体年份的题量变化，但掌握这一类逆运算公式是必做功课。

答案 综合以上分析，第 k 号结点的父结点存放在 ⌊k/2⌋ 号位置，正确选项是 C。