2024年9月 GESP CCF C++八级编程能力等级考试认证真题

1 单选题（每题 2 分，共 30 分）
第 1 题下面关于C++类和对象的说法，错误的是（）。
A. 类的析构函数可以为虚函数。
B. 类的构造函数不可以为虚函数。
C. class中成员的默认访问权限为private。
D. struct中成员的默认访问权限为private。

第 2 题对于一个具有个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为（）。
A.n * (n/2)
B.n * n
C.(n-1)*(n-1)
D.(n+1)*(n+1)

第 3 题设有编号为A、B、C、D、E的5个球和编号为A、B、C、D、E的5个盒子。现将这5个球投入5个盒子，要求每个盒子放一个球，并且恰好有两个球的编号与盒子编号相同，问有多少种不同的方法？（）。
A. 5
B. 120
C. 20
D. 60

第 4 题从甲地到乙地，可以乘高铁，也可以乘汽车，还可以乘轮船。一天中，高铁有10班，汽车有5班，轮船有2班。那么一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法？（）。
A. 100
B. 60
C. 30
D. 17

第 5 题个结点的二叉树，执行释放全部结点操作的时间复杂度是（）。

A.
B.
C.
D.

第 6 题在一个单位圆上，随机分布个点，求这个点能被一个单位半圆周全部覆盖的概率（）。
A.
B.
C.
D.

第 7 题下面 pailie 函数是一个实现排列的程序，横线处可以填入的是（）。

#include <iostream>
using namespace std;
int sum = 0;
void swap(int & a, int & b) {
   int temp = a;
   a = b;
   b = temp;
}
void pailie(int begin, int end, int a[]) {
   if (begin == end) {
       for (int i = 0; i < end; i++)
       cout << a[i];
       cout << endl;
   }
   for (int i = begin; i < end; i++) {
       __________ // 在此处填入选项
   }
}
A.
swap(a[begin + 1], a[i]);
pailie(begin + 1, end, a);
swap(a[i], a[begin]);

B.
swap(a[begin], a[i]);
pailie(begin, end, a);
swap(a[i], a[begin]);
C.
swap(a[begin], a[i]);
pailie(begin + 1, end, a);
swap(a[i], a[begin]);
D.
swap(a[begin] + 1, a[i]);
pailie(begin + 1, end, a);
swap(a[i], a[begin + 1]);

第 8 题上一题中，如果主函数为如下的程序，则最后的排列数是多少个？（）。
int main() {
int a[5] = {1, 2, 3, 4, 5};
pailie(0, 5, a);
return 0;
}
A. 120
B. 60
C. 240
D. 180

第 9 题下列程序实现了输出杨辉三角形，代码中横线部分应该填入的是（）。
#include <iostream>
using namespace std;
#define N 35
int a[N][N];
int main() {
   int n;
   cin >> n;
   for (int i = 1; i <= n; i++)
   for (int j = 1; j <= i; j++) {
       if (j == 1 || j == i)
       a[i][j] = 1; else
       __________ // 在此处填入选项
   }
   for (int i = 1; i <= n; i++) {
       for (int j = 1; j <= i; j++)
       cout << a[i][j];
       cout<<endl;
   }
   return 0;
}
A. a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
B. a[i][j] = a[i][j - 1] + a[i - 1][j];
C. a[i][j] = a[i - 1][j] + a[i - 1][j];
D. a[i][j] = a[i - 1][j - 1] + a[i][j];

第 10 题下面最小生成树的Kruskal算法程序中，横线处应该填入的是（）。
include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
   int u, v, weight;
   bool operator <(const Edge & other) const {
       return weight < other.weight;
   }
}
;
int findParent(int vertex, vector<int> & parent) {
   if (parent[vertex] == -1)
   return vertex;
   return parent[vertex] = findParent(parent[vertex], parent);
}
int main() {
   int n, m;
   cin >> n >> m;
   // n: 顶点数, m: 边数
   vector<Edge> edges(m);
   vector<int> parent(n, -1);
   int totalWeight = 0;
   for (int i = 0; i < m; i++)
   cin >> edges[i].u >> edges[i].v >> edges[i].weight;
   sort(edges.begin(), edges.end());
   for (const auto & edge : edges) {
       int uParent = findParent(edge.u, parent);
       int vParent = findParent(edge.v, parent);
       if (__________) {
           // 在此处填入选项
           parent[uParent] = vParent;
           totalWeight += edge.weight;
       }
   }
}
A. uParent == vParent
B. uParent >= vParent
C. uParent != vParent
D. uParent <= vParent