GESP C++ 六 级 2025年9月真题（180 分钟，总分 100 分）

判断题（共 10 题，每题 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ⁿ)。

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) }}

• 正确
• 错误