试题出自试卷《重庆大学2018年917计算机专业基础综合真题解析》

问题1选项
A.2 ⁱ
B.2 ⁱ-1
C.2 ^i-1
D.不可确定。

C

利用归纳法容易证得此性质。
i=1时，只有一个根结点。显然，2^i-1=2⁰=1是对的。
现在假定对所有的j，1≤j<i，命题成立，即第j层上至多有2^i-1个结点。那么，可以证明j=i时命题也成立。
由归纳假设：第i-1层上至多有2^i-2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2×2^i-2=2^i-1。
故本题选C。