CCF GESP 2025年3月认证 C++ 8级

一 单选题
共 15 道 每题 2 分 共计 30 分
第 1 题

国家“以旧换新”政策仍在继续，小杨家决定在家里旧的冰箱、电视、洗衣机、微波炉中选两种换新。其中，冰箱有 4 种型号可选，电视有 6 种型号可选，洗衣机有 3 种型号可选，微波炉有 5 种型号可选。请问小杨家共有多少种换新的方案？（ ）。

A

18
B

119
C

238
D

360
第 2 题

小杨和 3 位朋友约好一起去看电影“哪吒 2”。打开购票软件，他们发现，已经没有同一排连续的四个座位了（图中每个方框代表一个座位，红色方框代表已经售出）。朋友们商量了一下，决定分为两组，每组两人在同一排的相邻两个座位，且两组之间至少有一对座位是前后相邻的。请问共有多少种购票方案？（ ）。

A

495
B

96
C

7
D

4
第 3 题

下面关于 C++ 类构造和析构函数的说法，错误的是（ ）。

A

构造函数不能声明为虚函数。
B

析构函数必须声明为虚函数。
C

类的默认构造函数可以被声明为 private。
D

类的析构函数可以被声明为 private。
第 4 题

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

A

树是一种有向无环图，有向无环图都是一棵树。
B

如果把树看做有向图，每个节点指向其子节点点，则该图是弱连通图。
C

$N$ 个顶点且连通的无向图，其最小生成树一定包含 $N - 1$ 个条边。
D

$N + 1$ 个顶点、$N$ 条边的有向图，一定不是强连通的。
第 5 题

从 1 到 2025 这 2025 个数中，包含数字 5 的个数（ ）。

A

600
B

601
C

602
D

603
第 6 题

已定义 double 类型的变量 r 和 theta，分别表示图中圆半径和圆心角。下列表达式中可以求出弦长 s 的是（ ）。

A

r * cos(theta)
B

r * cos(theta / 2) * 2
C

r * sin(theta)
D

r * sin(theta / 2) * 2
第 7 题

$N$ 个节点的平衡二叉树的高为（ ）。

A

$\lfloor \log_2 N \rfloor$
B

$\lceil \log_2 N \rceil$
C

$\lfloor \log_2 N \rfloor + 1$
D

无法确定。
第 8 题

下列关于算法的说法，错误的是（ ）。

A

如果有足够的时间和空间，枚举法能解决一切有限的问题。
B

分治算法将原问题分为多个子问题进行求解，且分解出的子问题必须相互独立。
C

如果能找到合理的贪心原则，贪心算法往往能够比其他方法更快求解。
D

倍增法在搜索未知长度的有序数组时，通过动态倍增或减半步长，快速定位目标范围。
第 9 题

2025 是个神奇的数字，因为它是由两个数 20 和 25 拼接而成，而且 $2025 = (20 + 25)^2$。小杨决定写个程序找找小于 $N$ 的正整数中共有多少这样神奇的数字。下面程序横线处应填入的是（ ）。

#include <string>
int count_miracle(int N) {
    int cnt = 0;
    for (int n = 1; n * n < N; n++) {
        int n2 = n * n;
        std::string s = std::to_string(n2);
        for (int i = 1; i < s.length(); i++)
            if (s[i] != '0') {
                std::string s1 = s.substr(0, i);
                std::string sr = s.substr(i);
                int n1 = std::stoi(s1);
                int nr = std::stoi(sr);
                if (__________) // 在此处填入选项
                    cnt++;
            }
    }
    return cnt;
}
A

n1 + nr == n
B

n1 + nr == n2
C

(n1 + nr) * (n1 + nr) == n
D

(n1 + nr) ^ 2 == n2
第 10 题

2025 是个神奇的数字，因为它是由两个数 20 和 25 拼接而成，而且 $2025 = (20 + 25)^2$。小杨决定写个程序找找小于 $N$ 的正整数中共有多少这样神奇的数字。该函数的时间复杂度为（ ）。

#include <string>
int count_miracle(int N) {
    int cnt = 0;
    for (int n = 1; n * n < N; n++) {
        int n2 = n * n;
        std::string s = std::to_string(n2);
        for (int i = 1; i < s.length(); i++)
            if (s[i] != '0') {
                std::string s1 = s.substr(0, i);
                std::string sr = s.substr(i);
                int n1 = std::stoi(s1);
                int nr = std::stoi(sr);
                if (__________) // 在此处填入选项
                    cnt++;
            }
    }
    return cnt;
}
A

$O(N \log N)$
B

$O(N^{1/2})$
C

$O(N^{1/2} \log N)$
D

$O(N^{1/2} (\log N)^2)$
第 11 题

下面的欧氏筛法程序中，两个横线处应填入的分别是（ ）。

int primes[MAXP], num = 0;
bool isPrime[MAXN + 1] = {false};
void sieve() {
    for (int n = 2; n <= MAXN; n++) {
        if (!isPrime[n]) {
            primes[num++] = n;
            for (int i = 0; i < num && ________; i++) { // 在此处填入选项
                isPrime[n * primes[i]] = true;
                if (________) // 在此处填入选项
                    break;
            }
        }
    }
}
A 
n * primes[i] < MAXN
n % primes[i] == 0
B 
n * primes[i] < MAXN
primes[i] > n
C 
n * primes[i] <= MAXN
n % primes[i] == 0
D 
n * primes[i] <= MAXN
primes[i] > n
第 12 题

下面 Floyd 算法中，横线处应该填入的是（ ）。

#include <iostream>
using namespace std;
 
#define N 21
#define INF 9999999
int map[N][N];
int main() {
    int n, m, t1, t2, t3;
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)
                map[i][j] = 0;
            else
                map[i][j] = INF;
        }
    }
 
    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2 >> t3;
        map[t1][t2] = t3;
    }
 
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (map[i][j] > map[i][k] + map[k][j])
                    ________; // 在此处填入选项
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout.width(4);
            cout << map[i][j];
        }
        cout << endl;
    }
}
A

map[i][j] = map[i][k] + map[k][j]
B

map[i][k] = map[i][j] - map[k][j]
C

map[i][j] = map[i][k] - map[k][j]
D

map[k][j] = map[i][j] - map[i][k]
第 13 题

下面 Floyd 算法程序的时间复杂度为（ ）。

#include <iostream>
using namespace std;
 
#define N 21
#define INF 9999999
int map[N][N];
int main() {
    int n, m, t1, t2, t3;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)
                map[i][j] = 0;
            else
                map[i][j] = INF;
        }
    }
 
    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2 >> t3;
        map[t1][t2] = t3;
    }
 
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (map[i][j] > map[i][k] + map[k][j])
                    ________; // 在此处填入选项
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout.width(4);
            cout << map[i][j];
        }
        cout << endl;
    }
}
A

$O(N)$
B

$O(N^2)$
C

$O(N^3)$
D

$O(N^2 \log N)$
第 14 题

下列程序实现了输出杨辉三角形，代码中横线部分应该填入的是（ ）。

#include <iostream>
using namespace std;
 
#define N 35
int a[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        a[i] = 1;
        for (int j = i - 1; j > 0; j--)
            ________; // 在此处填入选项
        for (int j = 0; j <= i; j++)
            cout << a[j] << " ";
        cout << endl;
    }
    return 0;
}
A

a[j] += a[j + 1]
B

a[j] += a[j - 1]
C

a[j - 1] += a[j]
D

a[j + 1] += a[j]
第 15 题

下列程序实现了输出杨辉三角形，其时间复杂度为（ ）。

#include <iostream>
using namespace std;
 
#define N 35
int a[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        a[i] = 1;
        for (int j = i - 1; j > 0; j--)
            ________; // 在此处填入选项
        for (int j = 0; j <= i; j++)
            cout << a[j] << " ";
        cout << endl;
    }
    return 0;
}
A

$O(n)$
B

$O(n \log n)$
C

$O(n^2)$
D

$O(n^3)$
单选题部分已到底了。