NOIP 普及组初赛 · NOIP 2010 普及组初赛试题 第 19 题

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

这题考完全二叉树顺序存储的核心性质，拿到题先别慌，直接记牢数组下标从1开始时，父节点就是k除以2向下取整，左孩子是2k，右孩子是2k+1，套公式就能秒杀。

最容易掉进命题人挖的坑就是看错问法，题目明明问的是父结点，学生却惯性思维算成了孩子位置，选了A或B；另一种是记混公式，把向下取整写成向上取整，或者把k/2记成k/2+1，导致选了D。一定要确认题目问的是父还是子，再对应公式。

这题考什么

完全二叉树在顺序存储（数组）中的下标规律。这是数据结构里最基础也最容易考的计算题，NOIP普及组初赛年年都爱出这种送分题，但送分就送得你掉坑里。

知识点人话版

想象把一棵完全二叉树的结点，从上到下、从左到右，像填格子一样一个个塞进数组里。根结点塞在数组下标1的位置。这时候，下标之间就藏着漂亮的数学关系：

• 第k号结点的左孩子，正好排在数组的 $2k$ 号位置；
• 第k号结点的右孩子，正好排在数组的 $2k+1$ 号位置；
• 反过来，第k号结点的父结点，就是 $k$ 除以 $2$ 后向下取整，即 $ig floor rac{k}{2}$。

记住这三条，这题就通了。