程序一：树统计与层序遍历

补全程序并完成第 1～5 题。

int leaf(Node* u) {
    if (____①____) return 0;
    if (____②____) return 1;
    return ____③____;
}
int height(Node* u) {
    if (!u) return 0;
    return ____④____;
}
void level(Node* root) {
    queue<Node*> q; q.push(root);
    while (!q.empty()) {
        Node* u = ____⑤____;
        q.pop();
        if (u->left) q.push(u->left);
        if (u->right) q.push(u->right);
    }
}

第 1 题

①处应填（ ）。

{{ select(1) }}

• u==nullptr
• u->left
• u->right
• u->val==0

---

第 2 题

②处应填（ ）。

{{ select(2) }}

• u->left || u->right
• !u->left && !u->right
• u==nullptr
• u->left==u->right

---

第 3 题

③处应填（ ）。

{{ select(3) }}

• leaf(u->left)+leaf(u->right)
• leaf(u)
• u->val
• 1

---

第 4 题

④处应填（ ）。

{{ select(4) }}

• height(u->left)+height(u->right)
• 1+max(height(u->left),height(u->right))
• max(u->left,u->right)
• 1

---

第 5 题

⑤处应填（ ）。

{{ select(5) }}

• q.back()
• q.front()
• root
• nullptr

---

程序二：哈夫曼 WPL

补全程序并完成第 6～12 题。

priority_queue<int, vector<int>, greater<int>> q;
for (int x : w) q.push(x);
int ans = 0;
while (____⑥____) {
    int x = q.top(); q.pop();
    int y = q.top(); q.pop();
    int z = ____⑦____;
    ans += ____⑧____;
    ____⑨____;
}
cout << ____⑩____;

第 6 题

⑥处应填（ ）。

{{ select(6) }}

• q.empty()
• q.size()>1
• q.size()==1
• ans==0

---

第 7 题

⑦处应填（ ）。

{{ select(7) }}

• x-y
• x+y
• max(x,y)
• 1

---

第 8 题

⑧处应填（ ）。

{{ select(8) }}

• x
• y
• z
• 1

---

第 9 题

⑨处应填（ ）。

{{ select(9) }}

• q.push(z)
• q.pop()
• q.push(ans)
• break

---

第 10 题

⑩处应填（ ）。

{{ select(10) }}

• q.size()
• ans
• w.size()
• z-x

---

第 11 题

若有 $n$ 个权值，使用小根堆实现的时间复杂度是（ ）。

{{ select(11) }}

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

---

第 12 题

哈夫曼算法每轮采用的局部选择是（ ）。

{{ select(12) }}

• 选择最大的两个
• 选择最小的两个
• 选择最早输入的两个
• 随机选择两个

---