NOIP 提高 2018 第一轮 第 4 题：设根节点深度为0，一棵深度为h 的满k（k 1）叉树，即除最后一层无任何

题目

根节点深度为 $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】）。

解题过程

结点总数 = (k^{h+1}−1)/(k−1)。

选 A。

易错提醒

① 与普及组同题；② 等比数列求和分母 k−1。