CCF GESP 2025年9月认证 C++ 6级

二 判断题
共 10 道 每题 2 分 共计 20 分
第 1 题

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

正确
错误
第 2 题

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

正确
错误
第 3 题

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

正确
错误
第 4 题

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

正确
错误
第 5 题

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

正确
错误
第 6 题

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

正确
错误
第 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;
    }
}
正确
错误
第 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;
}
正确
错误
第 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];
}
正确
错误
第 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;
}
正确
错误
判断题部分已到底了。