CSP-S 2024 第一轮 第11题：假设有一棵h层的完全二叉树，该树最多包含多少个结点？

题目

假设有一棵 $h$ 层的完全二叉树，该树最多包含多少个结点？

选项

• A. $2^h-1$
• B. $2^{h+1}-1$
• C. $2^h$
• D. $2^{h+1}$

答案

A

题解

选 A．\(2^h-1\)。

根结点算第 \(1\) 层，第 \(i\) 层最多有 \(2^{i-1}\) 个结点。要使结点数最多，每层都要填满，所以总数为：

\[ 1+2+4+\cdots+2^{h-1}=2^h-1 \]

例如，\(h=3\) 时，最多有 \(1+2+4=7\) 个结点。

注意：题目说的是 \(h\) 层，因此最后一层最多有 \(2^{h-1}\) 个结点，别多算一层。