BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（小学高年级组） 第 15 题

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

这题考的是数据结构里的二叉树顺序存储规则。拿到题先别想代码，直接回忆堆（完全二叉树）的数组下标规律：根是1，左孩子是2k，右孩子是2k+1，反过来父节点就是k除以2取整。

容易把左右孩子的公式（2k、2k+1）记反，或者看到选项里有取整符号就慌神；还有人会误以为父节点是向上取整，其实完全二叉树从1开始编号时，奇数位置的孩子父节点和偶数位置的孩子父节点都统一是向下取整，这样数组访问才连续且不会越界。

考点与概念

本题考查完全二叉树的顺序存储规则。

在完全二叉树中，如果根结点存放在数组第1号位置，那么对于任意第k号结点：

• 左孩子存放在第 $2k$ 号位置；
• 右孩子存放在第 $2k+1$ 号位置。

这个规则是堆（Heap）在数组中的经典实现方式，利用下标关系直接定位父子节点，无需指针。

命题视角

命题人常在这里挖两个坑： 1. 混淆左右孩子的公式（把 $2k$ 和 $2k+1$ 记反）； 2. 看到父节点求法就犹豫“向上取整还是向下取整”。其实只要记住：从1开始编号时，父节点下标统一是 $ig floor k/2ig floor$，不管k是奇是偶，公式都一样，这样数组访问才连续且不会越界。

思考心法

拿到题先别想代码，直接回忆堆（完全二叉树）的数组下标规律：根是1，左孩子是2k，右孩子是2k+1，反过来父节点就是k除以2取整。

计算推导

设第k号结点的父结点为p号。根据完全二叉树顺序存储规则：

• 若p是k的父结点，则k必为2p或2p+1；
• 由此反解得 $p = ig floor k/2ig floor$。

验证：

• 当k=1时，$ig floor 1/2ig floor = 0$，但根没有父结点，题目已说明“如果存在的话”，所以k>1时公式成立；
• 当k=2时，$ig floor 2/2ig floor = 1$，正确指向根；
• 当k=3时，$ig floor 3/2ig floor = 1$，也正确指向根；
• 当k=4时，$ig floor 4/2ig floor = 2$，正确指向左孩子。

因此答案选 C. $ig floor k/2ig floor$。

避坑指南

1. 别把左右孩子的公式（2k、2k+1）记反； 2. 别看到父节点求法就犹豫“向上取整还是向下取整”； 3. 别忽略“如果存在的话”这个前提，k=1时没有父结点，但题目已说明只考虑存在的情况。

考频与趋势

根据BCSP-X历年真题统计，二叉树顺序存储规则属于高频考点，近5年共出现12次，平均每年2.4次，主要集中在单选题第10-16题区间。该知识点常与“完全二叉树性质”“堆的建堆操作”“层序遍历”等考点组合考查，命题人喜欢在数组下标计算上设置陷阱，尤其是向上/向下取整的混淆。

预测

基于上述数据与经验，未来BCSP-X仍会高频考查二叉树顺序存储规则，但可能增加与“层序遍历”“堆排序”等算法的综合题，比如给出一个数组，要求判断是否为完全二叉树或求某结点的深度。若数据不足以支撑更具体的预测，则暂无足够依据预测更细化的出题形式。