二、判断题（每题 2 分，共 20 分）

第 1 题 当基类可能被多态使用，其析构函数应该声明为虚函数。

{{ select(1) }}

• 正确
• 错误

第 2 题 哈夫曼编码是最优前缀码，且编码结果唯一。

{{ select(2) }}

• 正确
• 错误

第 3 题 一个含有 $100$ 个节点的完全二叉树，高度为 $8$。

{{ select(3) }}

• 正确
• 错误

第 4 题 在 C++ STL 中，栈（std::stack）的 pop 操作返回栈顶元素并移除它。

{{ select(4) }}

• 正确
• 错误

第 5 题 循环队列通过模运算循环使用空间。

{{ select(5) }}

• 正确
• 错误

第 6 题 一棵有 $n$ 个节点的二叉树一定有 $n-1$ 条边。

{{ select(6) }}

• 正确
• 错误

第 7 题 以下代码实现了二叉树的中序遍历。输入以下二叉树，中序遍历结果是 4 2 5 1 3 6 。

//     1
//    / \
//   2   3
//  / \   \
// 4   5   6

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorderIterative(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* curr = root;
    
    while (curr || !st.empty()) {
        while (curr) {
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top(); st.pop();
        cout << curr->val << " ";
        curr = curr->right;
    }
}

{{ select(7) }}

• 正确
• 错误

第 8 题 下面代码实现的二叉排序树的查找操作时间复杂度是 $O(h)$ ，其中 $h$ 为树高。

TreeNode* searchBST(TreeNode* root, int val) {
    while (root && root->val != val) {
        root = (val < root->val) ? root->left : root->right;
    }
    return root;
}

{{ select(8) }}

• 正确
• 错误

第 9 题 下面代码实现了动态规划版本的斐波那契数列计算，其时间复杂度是 $O(2^n)$。

int fib_dp(int n) {
    if (n <= 1) return n;
    vector<int> dp(n+1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

{{ select(9) }}

• 正确
• 错误

第 10 题 有一排香蕉，每个香蕉有不同的甜度值。小猴子想吃香蕉，但不能吃相邻的香蕉。以下代码能找到小猴子吃到最甜的香蕉组合。

// bananas：香蕉的甜度
void findSelectedBananas(vector<int>& bananas, vector<int>& dp) {
    vector<int> selected;
    int i = bananas.size() - 1;
    
    while (i >= 0) {
        if (i == 0) {
            selected.push_back(0);
            break;
        }
        
        if (dp[i] == dp[i-1]) {
            i--;
        } else {
            selected.push_back(i);
            i -= 2;
        }
    }
    
    reverse(selected.begin(), selected.end());
    cout << "小猴子吃了第: ";
    for (int idx : selected)
        cout << idx+1 << " ";
    cout << "个香蕉" << endl;
}

int main() {
    vector<int> bananas = {1, 2, 3, 1}; // 每个香蕉的甜度
    
    vector<int> dp(bananas.size());
    dp[0] = bananas[0];
    dp[1] = max(bananas[0], bananas[1]);
    for (int i = 2; i < bananas.size(); i++) {
        dp[i] = max(bananas[i] + dp[i-2], dp[i-1]);
    }
    findSelectedBananas(bananas, dp);
    
    return 0;
}

{{ select(10) }}

• 正确
• 错误