NOIP 普及 2018 第一轮 第 7 题：深度 h 的满 k 叉树结点数

题目

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

选项

• A. $\dfrac{k^{h+1}-1}{k-1}$
• B. $k^{h-1}$
• C. $k^h$
• D. $\dfrac{k^{h-1}}{k-1}$

答案

A

题解

考点定位

本题考「满 k 叉树结点数」,对应大纲 3.2.2 树（难度【2】）。

解题过程

深度 h（根为 0）的满 k 叉树：各层 1,k,k²,…,k^h，总和：

$$\frac{k^{h+1}-1}{k-1}$$

选 A。

易错提醒

① 等比求和公式（k−1 为分母）；② 根深度 0 ⇒ 共 h+1 层。