NOIP 提高组初赛 · NOIP 2018 提高组初赛试题 第 4 题

根节点深度为 $0$，一棵深度为 $h$ 的满 $k(k>1)$ 叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 $k$ 个子结点的树，共有（ ）个结点。

这题就是考等比数列求和，拿到题先想：根是k^0，每层乘k，加到第h层，直接套公式，别把根漏了。

学生最容易把根结点漏掉，或者把求和上限搞错成h-1，导致答案少一层；也有人把等比数列求和公式记混，分母写成k+1或者分子写成k^h-1，这样就算出的结果跟选项对不上。还有的同学误以为满k叉树最后一层也有k个子节点，其实定义里最后一层是叶子，没有子节点，但结点数依然按k^h算，别被这个细节带偏。

考点概念：满 k 叉树的结点数

满 k 叉树深度为 h（根结点深度 0）：

• 第 i 层有 k^i 个结点（i = 0..h）

总结点数 = 1 + k + k² + … + k^h = (k^(h+1) − 1) / (k − 1)

选 A。

命题视角：为什么考这个？

命题人喜欢用“满 k 叉树”这种定义很严谨的模型，背后其实就是等比数列求和。它不考你背公式，而是考你理解每一层的规律：根是 k^0=1，下一层是 k^1，再下一层是 k^2……一直推到第 h 层是 k^h。然后让你把这些加起来。这种题目在 CSP 提高级、NOIP 初赛都出现过，尤其是 2023、2026 这两年考得特别多，说明命题人很看重你对树形结构和数列求和的直观把握。