#TK1160. 2025年3月CCF-GESP编程能力等级认证C++编程六级真题

2025年3月CCF-GESP编程能力等级认证C++编程六级真题

2025年3月CCF-GESP编程能力等级认证C++编程六级真题

一、单选题（每题 2 分，共 30 分）

第 1 题 在面向对象编程中，类是一种重要的概念。下面关于类的描述中，不正确的是（ ）。
{{ select(1) }}

  • 类是一个抽象的概念，用于描述具有相同属性和行为的对象集合。
  • 类可以包含属性和方法，属性用于描述对象的状态，方法用于描述对象的行为。
  • 类可以被实例化，生成具体的对象。
  • 类一旦定义后，其属性和方法不能被修改或扩展。

第 2 题 哈夫曼编码是一种数据压缩算法。以下关于哈夫曼编码的描述中，不正确的是（ ）。
{{ select(2) }}

  • 哈夫曼编码是一种变长编码，频率高的字符使用较短的编码，频率低的字符使用较长的编码。
  • 在构造哈夫曼树时，频率越低的字符离根节点越近，频率越高的字符离根节点越远。
  • 哈夫曼编码的生成过程基于贪心算法，每次选择频率最低的两个节点进行合并。
  • 哈夫曼编码是一种前缀编码，任何一个字符的编码都不会是另一个字符编码的前缀，因此可以实现唯一解码。

第 3 题 以下代码实现了树的哪种遍历方式？

void traverse(TreeNode* root) { 
  if (root == nullptr) return; 
  cout << root->val << " "; 
  traverse(root->left); 
  traverse(root->right); 
}

{{ select(3) }}

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层次遍历

第 4 题 以下关于完全二叉树的代码描述，正确的是（ ）。

bool isCompleteTree(TreeNode* root) { 
  if (root == nullptr) return true; 
  queue<TreeNode*> q; 
  q.push(root); 
  bool hasNull = false; 
  while (!q.empty()) { 
    TreeNode* node = q.front(); 
    q.pop(); 
    if (node == nullptr) { 
      hasNull = true; 
    } else { 
      if (hasNull) return false; 
      q.push(node->left); 
      q.push(node->right); 
    } 
  } 
  return true; 
}

{{ select(4) }}

  • 该代码用于判断一棵树是否为满二叉树
  • 该代码用于判断一棵树是否为完全二叉树
  • 该代码用于判断一棵树是否为二叉搜索树
  • 该代码用于计算树的高度

第 5 题 以下代码实现了二叉排序树的哪种操作？

TreeNode* op(TreeNode* root, int val) { 
  if (root == nullptr) return new TreeNode(val); 
  if (val < root->val) { 
    root->left = op(root->left, val); 
  } else { 
    root->right = op(root->right, val); 
  } 
  return root; 
}

{{ select(5) }}

  • 查找
  • 插入
  • 删除
  • 遍历

第 6 题 给定字符集 {A, B, C, D} 的出现频率分别为 {5, 1, 6, 2} ，则正确的哈夫曼编码是（ ）。
{{ select(6) }}

  • A: 0, B: 100, C: 11, D: 101
  • A: 11, B: 100, C: 0, D: 101
  • A: 0, B: 101, C: 11, D: 100
  • A: 10, B: 101, C: 0, D: 100

第 7 题 关于动态规划的描述，正确的是（ ）。
{{ select(7) }}

  • 动态规划算法的时间复杂度总是低于贪心算法。
  • 动态规划要求问题必须具有最优子结构和重叠子问题两个性质。
  • 动态规划通过递归实现时不需要存储中间结果。
  • 动态规划的核心思想是将问题分解为互不重叠的子问题。

第 8 题 以下代码中，类的构造函数被调用了（ ）次。

class MyClass { 
public: 
  MyClass() { 
    cout << "Constructor called!" << endl; 
  } 
}; 
int main() { 
  MyClass obj1; 
  MyClass obj2 = obj1; 
  return 0; 
}

{{ select(8) }}

  • 1
  • 2
  • 3
  • 0

第 9 题 以下代码实现了循环队列的哪种操作？

class CircularQueue { 
  int* arr; 
  int front, rear, size; 
public: 
  CircularQueue(int k) { 
    size = k; 
    arr = new int[k]; 
    front = rear = -1; 
  } 
  bool enQueue(int value) { 
    if (isFull()) return false; 
    if (isEmpty()) front = 0; 
    rear = (rear + 1) % size; 
    arr[rear] = value; 
    return true; 
  } 
};

{{ select(9) }}

  • 入队
  • 出队
  • 查看队首元素
  • 判断队列是否为空

第 10 题 以下代码实现了二叉树的深度优先搜索（DFS），并统计叶子结点的数量，则横线上应填写（ ）。

int countLeafNodes(TreeNode* root) { 
  if (root == nullptr) return 0; 
  stack<TreeNode*> s; 
  s.push(root); 
  int count = 0; 
  while (!s.empty()) { 
    TreeNode* node = s.top(); 
    s.pop(); 
    if (node->left == nullptr && node->right == nullptr) { 
      count++; 
    } 
    if (node->right) s.push(node->right); 
    ________________________________ // 在此处填入代码 
  } 
  return count; 
}

{{ select(10) }}

  • if (node->left) s.push(node->left);
  • if (node->left) s.pop(node->left);
  • if (node->left) s.front(node->left);
  • if (node->left) s.push(node->right);

第 11 题 以下代码实现了二叉树的广度优先搜索（BFS），并查找特定值的节点，则横线上应填写（ ）。

TreeNode* findNode(TreeNode* root, int target) { 
  if (root == nullptr) return nullptr; 
  queue<TreeNode*> q; 
  q.push(root); 
  while (!q.empty()) { 
    TreeNode* current = q.front(); 
    q.pop(); 
    if (current->val == target) { 
      return current; // 找到目标节点 
    } 
    ________________________________ // 在此处填入代码 
  } 
  return nullptr; // 未找到目标节点 
}

{{ select(11) }}

  • if (current->left) q.push(current->left); if (current->right) q.push(current->right);
  • if (current->left) q.pop(current->left); if (current->right) q.pop(current->right);
  • if (current->left) q.front(current->left); if (current->right) q.front(current->right);
  • if (current->left) q.push(current->right); if (current->right) q.push(current->left);

第 12 题 以下代码用于生成 ( n ) 位格雷编码。横线上应填写（ ）。

vector<string> generateGrayCode(int n) { 
  if (n == 0) return {"0"}; 
  if (n == 1) return {"0", "1"}; 
  vector<string> prev = generateGrayCode(n - 1); 
  vector<string> result; 
  for (string s : prev) { 
    result.push_back("0" + s); // 在前缀添加 0 
  } 
  for (int i = prev.size() - 1; i >= 0; i--) { 
    ________________________________ // 在此处填入代码 
  } 
  return result; 
}

{{ select(12) }}

  • result.push_back("1" + prev[i]);
  • result.push_back("0" + prev[i]);
  • result.push_back(prev[i] + "1");
  • result.push_back(prev[i] + "0");

第 13 题 以下代码实现了0/1背包问题的动态规划解法。假设物品重量为 weights[]，价值为 values[]，背包容量为 W，横线上应填写（ ）。

int knapsack(int W, vector<int>& weights, vector<int>& values) { 
  int n = weights.size(); 
  vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
  for (int i = 1; i <= n; i++) { 
    for (int j = 1; j <= W; j++) { 
      if (weights[i-1] > j) { 
        dp[i][j] = dp[i-1][j]; // 当前物品装不下 
      } else { 
        dp[i][j] = max(_________________________); // 在此处填入代码 
      } 
    } 
  } 
  return dp[n][W]; 
}

{{ select(13) }}

  • A. dp[i-1][j], values[i-1]
  • B. dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1]
  • C. dp[i][j-1], values[i-1]
  • D. dp[i-1][j - weights[i-1]] + values[i-1], dp[i][j-1]

第 14 题 以下代码用于检查字符串中的括号是否匹配，横线上应填写（ ）。

bool isBalanced(string s) { 
  stack<char> st; 
  for (char c : s) { 
    if (c == '(' || c == '[' || c == '{') { 
      st.push(c); 
    } else { 
      if (st.empty()) return false; // 无左括号匹配 
      char top = st.top(); 
      st.pop(); 
      if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) { 
        return false; 
      } 
    } 
  } 
  return ________________; //在此处填入代码 
}

{{ select(14) }}

  • A. true
  • B. false
  • C. st.empty()
  • D. !st.empty()

第 15 题 关于下面代码，说法错误的是（ ）。

class Shape { 
protected: 
  string name; 
public: 
  Shape(const string& n) : name(n) {} 
  virtual double area() const { return 0.0; } 
};
class Circle : public Shape { 
private: 
  double radius; // 半径 
public: 
  Circle(const string& n, double r) : Shape(n), radius(r) {} 
  double area() const override { return 3.14159 * radius * radius; } 
};
class Rectangle : public Shape { 
private: 
  double width; // 宽度 
  double height; // 高度 
public: 
  Rectangle(const string& n, double w, double h) : Shape(n), width(w), height(h) {} 
  double area() const override { return width * height; } 
};
int main() { 
  Circle circle("MyCircle", 5.0); 
  Rectangle rectangle("MyRectangle", 4.0, 6.0); 
  Shape* shapePtr = &circle; 
  cout << "Area: " << shapePtr->area() << endl; 
  shapePtr = &rectangle; 
  cout << "Area: " << shapePtr->area() << endl; 
  return 0; 
}

{{ select(15) }}

  • A. 语句 Shape* shapePtr = &circle; 和 shapePtr = &rectangle; 出现编译错误
  • B. Shape 为基类，Circle 和 Rectangle 是派生类
  • C. 通过继承，Circle 和 Rectangle 复用了 Shape 的属性和方法，并扩展了新的功能
  • D. Circle 和 Rectangle 通过重写（override）基类的虚函数 area 和基类指针，实现了运行时多态

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

第 1 题 哈夫曼树在构造过程中，每次合并权值最小的两个节点，最终生成的树带权路径长度最小。（ ）
{{ select(16) }}

  • 对
  • 错

第 2 题 格雷编码的相邻两个编码之间必须有多位不同，以避免数据传输错误。（ ）
{{ select(17) }}

  • 对
  • 错

第 3 题 在树的深度优先搜索（DFS）中，使用队列作为辅助数据结构以实现“先进后出”的访问顺序。（ ）
{{ select(18) }}

  • 对
  • 错

第 4 题 以下代码实现的是二叉树的中序遍历：

void traverse(TreeNode* root) { 
  if (root == nullptr) return; 
  traverse(root->left); 
  cout << root->val << " "; 
  traverse(root->right); 
}

{{ select(19) }}

  • 对
  • 错

第 5 题 C++ 支持构造函数重载，但默认无参数的构造函数只能有一个。（ ）
{{ select(20) }}

  • 对
  • 错

第 6 题 二叉排序树（BST）中，若某节点的左子树为空，则该节点一定是树中的最小值节点。（ ）
{{ select(21) }}

  • 对
  • 错

第 7 题 在动态规划解决一维硬币找零问题时，若硬币面额为 [1, 3, 4]，目标金额为 6，则最少需要 2 枚硬币（3+3）。（ ）
{{ select(22) }}

  • 对
  • 错

第 8 题 面向对象编程中，封装是指将数据和行为绑定在一起，并对外隐藏实现细节。（ ）
{{ select(23) }}

  • 对
  • 错

第 9 题 以下代码创建的树是一棵完全二叉树：

TreeNode* root = new TreeNode{1}; 
root->left = new TreeNode{2}; 
root->right = new TreeNode{3}; 
root->left->left = new TreeNode{4};

{{ select(24) }}

  • 对
  • 错

第 10 题 栈和队列均可以使用双向链表实现，插入和删除操作的时间复杂度为 (O(1))。（ ）
{{ select(25) }}

  • 对
  • 错

三、编程题（每题 25 分，共 50 分）

3.1 编程题 1

  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. © 2021-2025 Hydro.ac
  5. Worker 0 in 130ms
  6. Hydro v5.0.0-beta.1-401bb50-dirty Professional