情境一：1 下标完全二叉树

一棵完全二叉树共有 10 个结点，按层序从 1 开始编号。完成第 1～6 题。

第 1 题

这棵树的深度是多少？

{{ input(1) }}

---

第 2 题

叶子结点共有多少个？

{{ input(2) }}

---

第 3 题

编号 5 的结点有几个孩子？

{{ input(3) }}

---

第 4 题

编号 9 的父结点编号是多少？

{{ input(4) }}

---

第 5 题

编号为 i 的结点是叶子的充要条件是（ ）。

{{ select(5) }}

• i > n/2
• i < n/2
• 2*i <= n
• i 为奇数

---

第 6 题

度为 2 的结点共有多少个？

{{ input(6) }}

---

情境二：结点度数关系

某非空二叉树有 7 个叶子结点、3 个度为 1 的结点。完成第 7～10 题。

第 7 题

度为 2 的结点共有多少个？

{{ input(7) }}

---

第 8 题

整棵树共有多少个结点？

{{ input(8) }}

---

第 9 题

整棵树共有多少条边？

{{ input(9) }}

---

第 10 题

二叉树第 5 层最多有多少个结点？

{{ input(10) }}

---

程序三：用编号统计叶子

leaf(i,n) 返回以编号 i 为根、总结点数为 n 的完全二叉树子树中的叶子数。

int leaf(int i, int n) {
    if (i > n) return 0;
    if (2 * i > n) return 1;
    return leaf(2 * i, n) + leaf(2 * i + 1, n);
}

第 11 题

leaf(2,10) 的返回值是多少？

{{ input(11) }}

---

第 12 题

计算 leaf(1,n) 时，每个存在的结点最多访问一次，时间复杂度是（ ）。

{{ select(12) }}

• $O(1)$
• $O(\log n)$
• $O(n)$
• $O(n^2)$

---