16. 当基类可能被多态使用，其析构函数应该声明为虚函数。 {{ select(16) }}

• 正确
• 错误

17. 哈夫曼编码是最优前缀码，且编码结果唯一。 {{ select(17) }}

• 正确
• 错误

18. 一个含有 $n$ 个节点的完全二叉树，高度为 $\log_2 n$。 {{ select(18) }}

• 正确
• 错误

19. 在 C++ STL 中，栈（std::stack）的 pop 操作返回栈顶元素并移除它。 {{ select(19) }}

• 正确
• 错误

20. 循环队列通过模运算循环使用空间。 {{ select(20) }}

• 正确
• 错误

21. 一棵有 $n$ 个节点的二叉树一定有 $n-1$ 条边。 {{ select(21) }}

• 正确
• 错误

22. 以下代码实现了二叉树的中序遍历。输入以下二叉树，中序遍历结果是 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(22) }}

• 正确
• 错误

23. 下面代码实现的二叉排序树的查找操作时间复杂度是 $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(23) }}

• 正确
• 错误

24. 下面代码实现了动态规划版本的斐波那契数列计算，其时间复杂度是 $O(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(24) }}

• 正确
• 错误

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

// 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(25) }}

• 正确
• 错误