情境一：19 个结点的完全二叉树

按层序从 1 开始编号。完成第 1～6 题。

第 1 题

树的深度是多少？

{{ input(1) }}

---

第 2 题

叶子结点共有多少个？

{{ input(2) }}

---

第 3 题

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

{{ input(3) }}

---

第 4 题

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

{{ input(4) }}

---

第 5 题

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

{{ input(5) }}

---

第 6 题

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

{{ input(6) }}

---

程序二：共享一棵非完全二叉树

0 表示空。完成第 7～12 题。

int lc[9]={0,2,4,6,0,7,0,0,0};
int rc[9]={0,3,5,0,0,8,0,0,0};

第 7 题

树中共有多少个结点？

{{ input(7) }}

---

第 8 题

叶子结点共有多少个？

{{ input(8) }}

---

第 9 题

树的深度是多少？

{{ input(9) }}

---

第 10 题

前序遍历是什么？

{{ input(10) }}

---

第 11 题

中序遍历是什么？

{{ input(11) }}

---

第 12 题

层序遍历是什么？

{{ input(12) }}

---

情境三：遍历序列还原

前序 A B D E C F G，中序 D B E A F C G。完成第 13～18 题。

第 13 题

根结点是谁？

{{ input(13) }}

---

第 14 题

左子树有几个结点？

{{ input(14) }}

---

第 15 题

后序遍历是什么？

{{ input(15) }}

---

第 16 题

层序遍历是什么？

{{ input(16) }}

---

第 17 题

后序遍历的最后一个结点是谁？

{{ input(17) }}

---

第 18 题

结点值互不相同时，这两条序列能否唯一还原？

{{ select(18) }}

• 能
• 不能

---

程序四：遍历代码的修改影响

对上题还原出的满二叉树分析。

void f(Node* u) {
    if (!u) return;
    cout << u->val << " ";
    f(u->left);
    f(u->right);
}

第 19 题

当前函数执行的是（ ）。

{{ select(19) }}

• 前序
• 中序
• 后序
• 层序

---

第 20 题

把输出移到两个递归调用之间后，变成（ ）。

{{ select(20) }}

• 前序
• 中序
• 后序
• 层序

---

第 21 题

把输出移到两个递归调用之后，变成（ ）。

{{ select(21) }}

• 前序
• 中序
• 后序
• 层序

---

第 22 题

层序遍历若每次先把右孩子入队、再把左孩子入队，输出是什么？

{{ input(22) }}

---

第 23 题

遍历所有 $n$ 个结点的时间复杂度是（ ）。

{{ select(23) }}

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

---

第 24 题

退化成链时，递归遍历的额外栈空间最坏为（ ）。

{{ select(24) }}

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

---