CCF GESP C++ 八级 (2025 年 09 月)

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

1. ⼩杨想点⼀杯奶茶外卖，但还差5元起送。于是，⼩杨决定点⼀些⼩料。可选的⼩料包括：珍珠1元、椰果2 元、奶冻3元、奶盖4元。每种⼩料最多点1份。请问共有多少种满⾜起送条件的点⼩料⽅案？（ ）。

{{ select(1) }}

• 16
• 10
• 9
• 7

2. ⼩杨和⼩刘是好朋友，她们在逛商场时发现新设置的⼤头贴⾃拍机，于是决定⼀起拍⼀组照⽚。⼀组照⽚包 括4张，这4张照⽚没有顺序区分。拍每张照⽚时，可以选择有相框或⽆相框、两⼈可以分别选择有头饰或⽆头饰、 还可以从2种位置（⼩杨在左，或⼩刘在左）中选出⼀种。她们不希望⼀组照⽚中出现完全相同的相框、头饰、位置 的组合。请问⼀组照⽚共有多少种不同的⽅案？（ ）。

{{ select(2) }}

• 1820
• 70
• 24
• 16

3. 下列关于C++类的说法，错误的是（ ）

{{ select(3) }}

• 派⽣类对象占⽤的内存总是不⼩于基类对象。
• 派⽣类可以不实现基类的虚函数。
• 如果⼀个类包含纯虚函数，则它不能包含成员变量。
• 如果⼀个类包含纯虚函数，则不能⽤它定义对象。

4. 下列关于树和图的说法，错误的是（ ）

{{ select(4) }}

• 每个连通图都存在⽣成树。
• 每个存在⽣成树的有向图，都⼀定是强连通的。
• 保留树的所有节点，并把树的每个节点指向其⽗节点，则可以将树转换为⼀个有向弱连通图。
• 保留树的所有节点，并把树的每个节点指向其⼦节点，则可以将树转换为⼀个有向⽆环图。

5. ⼀对夫妻⽣男⽣⼥的概率相同。这对夫妻希望⼉⼥双全。请问这对夫妻⽣下三个孩⼦时，实现⼉⼥双全的概 率是多少？（ ）。 A. B. C. D.

{{ select(5) }}

• $\dfrac{1}{4}$
• $\dfrac{1}{2}$
• $\dfrac{3}{4}$
• $\dfrac{7}{8}$

6. ⼆项式 的展开式中 项的系数是（ ）

{{ select(6) }}

• 720
• 120
• 20
• 15

7. 对⼀个包含 个顶点、 条边的图，执⾏⼴度优先搜索，其最优时间复杂度是（ ） A. B. C. D.

{{ select(7) }}

• $O(V)$
• $O(V + E)$
• $O(V^2)$
• $O(E)$

8. 以下关于贪⼼法和动态规划的说法中，错误的是（ ）

{{ select(8) }}

• 动态规划能解决⼤部分多阶段决策问题。
• 对特定的问题，贪⼼法不⼀定适⽤。
• 当特定的问题适⽤贪⼼法时，通常⽐动态规划的时间复杂度更低。
• 对很多问题，递推实现和递归实现动态规划⽅法的时间复杂度相当。

9. 下⾯程序的输出为（ ）

#include <iostream>
using namespace std;
int main() {
  int N = 15, cnt = 0;
  for (int x = 1; x + x + x <= N; x++)
    for (int y = x; x + y + y <= N; y++)
      for (int z = y; x + y + z <= N; z++)
        cnt++;
  cout << cnt << endl;
  return 0;
}

{{ select(9) }}

• 45
• 102
• 174
• 3375

10. 下⾯程序的时间复杂度为（ ） A. B. C. D.

int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve() {
  for (int n = 2; n <= MAXN; n++) {
    if (!isPrime[n])
      primes[num++] = n;
    for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
      isPrime[n * primes[i]] = true;
      if (n % primes[i] == 0)
        break;
      }
  }
}

{{ select(10) }}

• $O(n \log n)$
• $O(n \log \log n)$
• $O(n)$
• $O(\log n)$

11. 下列Dijkstra算法，假设图 中顶点数 、边数 ，则程序的时间复杂度为（ ） A. B. C. D.

typedef struct Edge {
  int in, out; // 从下标in顶点到下标out顶点的边
  int len; // 边长度
  struct Edge * next;
} Edge;

// v：顶点个数，graph：出边邻接表，start：起点下标，dis：输出每个顶点的最短距离

void dijkstra(int v, Edge * graph[], int start, int * dis) {
  const int MAX_DIS = 0x7fffff;
  for (int i = 0; i < v; i++)
    dis[i] = MAX_DIS;
  dis[start] = 0;
  int * visited = new int[v];
  for (int i = 0; i < v; i++)
    visited[i] = 0;
  visited[start] = 1;
  for (int t = 0; ; t++) {
    int min = MAX_DIS, minv = -1;
    for (int i = 0; i < v; i++) {
      if (visited[i] == 0 && min > dis[i]) {
        min = dis[i];
        minv = i;
      }
    }
    if (minv < 0)
      break;
    visited[minv] = 1;
    for (Edge * e = graph[minv]; e != NULL; e = e->next)
      if (dis[e->out] > e->len)
        dis[e->out] = e->len;
  }
  delete[] visited;
}

{{ select(11) }}

• $O(v^2)$
• $O(v \log v + e)$
• $O((v + e) \log v)$
• $O(v + e)$

12. 下⾯ count_triple 函数的时间复杂度为( ) A. B. C. D.

int gcd(int m, int n) {
  if (m == 0) return n;
  return gcd(n % m, m);
}
int count_triple(int n) {
  int cnt = 0;
  for (int v = 1; v * v * 4 <= n; v++)
    for (int u = v + 1; u * (u + v) * 2 <= n; u += 2)
    if (gcd(u, v) == 1) {
      int a = u * u - v * v;
      int b = u * v * 2;
      int c = u * u + v * v;
      cnt += n / (a + b + c);
    }
  return cnt;
}

{{ select(12) }}

• $O(n^2)$
• $O(n^2 \log n)$
• $O(n)$
• $O(n \log n)$

13. 下⾯ merge_sort 函数试图实现归并排序算法，横线处应该填⼊的是（ ） 6 10 A. B. C. D.

#include <vector>
using namespace std;
void merge_sort(vector<int> & arr, int left, int right) {
  if (right - left <= 1)
    return;
  int mid = (left + right) / 2;
  merge_sort(________); // 在此处填入选项
  merge_sort(________); // 在此处填入选项
  vector<int> temp(right - left);
  int i = left, j = mid, k = 0;
  while (i < mid && j < right)
    if (arr[i] <= arr[j])
      temp[k++] = arr[i++];
    else
      temp[k++] = arr[j++];
  while (i < mid)
    temp[k++] = arr[i++];
  while (j < right)
    temp[k++] = arr[j++];
  for (i = left, k = 0; i < right; ++i, ++k)
    arr[i] = temp[k];
}

{{ select(13) }} A.

arr, left, mid
arr, mid, right

B.

arr, left, mid + 1
arr, mid + 1, right

C.

arr, left, mid
arr, mid + 1, right

D.

arr, left, mid + 1
arr, mid + 1, right + 1

• A
• B
• C
• D

14. 下⾯Prim算法程序中，横线处应该填⼊的是（ ） A. B. C. D.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int prim(vector<vector<int>> & graph, int n) {
vector<int> key(n, INT_MAX);
vector<int> parent(n, -1);
key[0] = 0;
for (int i = 0; i < n; i++) {
int u = min_element(key.begin(), key.end()) - key.begin();
if (key[u] == INT_MAX)
break;
for (int v = 0; v < n; v++) {
if (__________) { // 在此处填入选项
key[v] = graph[u][v];
parent[v] = u;
}
}
}
int sum = 0;
for (int i = 0; i < n; i++) {
if (parent[i] != -1) {
cout << "Edge: " << parent[i] << " - " << i << " Weight: " << key[i] << endl;
sum += key[i];
}
}
return sum;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = w;
graph[v][u] = w;
}
int result = prim(graph, n);
cout << "Total weight of the minimum spanning tree: " << result << endl;
return 0;
}

{{ select(14) }}

• graph[u][v] >= 0 && key[v] > graph[u][v]
• graph[u][v] <= 0 && key[v] > graph[u][v]
• graph[u][v] == 0 && key[v] > graph[u][v]
• graph[u][v] != 0 && key[v] > graph[u][v]

15. 下⾯的程序使⽤出边邻接表表达的带权⽆向图，则从顶点0到顶点3的最短距离为（ ）

#include <vector>
using namespace std;
class Edge {
public:
int dest;
int weight;
Edge(int d, int w) : dest(d), weight(w) {}
};
class Graph {
private:
int num_vertex;
vector<vector<Edge>> vve;
public:
Graph(int v) : num_vertex(v), vve(v) {}
void addEdge(int s, int d, int w) {
vve[s].emplace_back(d, w);
vve[d].emplace_back(s, w)
}
};
int main() {
Graph g(4);
g.addEdge(0, 1, 8);
g.addEdge(0, 2, 5);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 3);
g.addEdge(2, 3, 7);
return 0;
}

{{ select(15) }}

• 12
• 11
• 10
• 9

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

1. C++语⾔中，表达式 '9' ^ 3 的结果值为 '999'

{{ select(16) }}

• 对
• 错

2. 下列C++语⾔代码，能够安全地输出 arr[5] 的值

int n = 5;
int arr[n] = {1, 2, 3};
std::cout << arr[5];

{{ select(17) }}

• 对
• 错

3. 对 个元素的数组进⾏排序，最差情况的时间复杂度为 $O(n^2)$。

{{ select(18) }}

• 对
• 错

4. 有4个红球、3个蓝球和2个绿球排成⼀排（相同⾊球视为完全相同），则不同的排列⽅案数为1260种

{{ select(19) }}

• 对
• 错

5. 使⽤ math.h 或 cmath 头⽂件中的函数，对于 int 类型的变量 x ，表达式 fabs(x) 和 sqrt(x * x) 的结 果总是近似相等的。

{{ select(20) }}

• 对
• 错

6. 运算符重载是C++语⾔静态多态的⼀种典型体现，⽽使⽤C语⾔则⽆法实现运算符重载

{{ select(21) }}

• 对
• 错

7. 存在⼀个简单⽆向图满⾜：顶点数为6，边数为8，6个顶点的度数分别为3、3、3、3、2、2

{{ select(22) }}

• 对
• 错

8. 已知两个 double 类型的变量 r 和 theta 分别表⽰⼀个扇形的圆半径及圆⼼角（弧度），则扇形的周长可 以通过表达式 (2 + theta) * r 求得。

{{ select(23) }}

• 对
• 错

9. Dijkstra算法的时间复杂度为$O(V^2)$。 ，其中 为图中顶点的数量

{{ select(24) }}

• 对
• 错

10. 从32名学⽣中选出2⼈分别担任男⽣班长和⼥⽣班长（男⽣班长必须是男⽣，⼥⽣班长必须是⼥⽣），则共有C(32,2)/2 种不同的选法。

{{ select(25) }}

• 对
• 错