GESP-C++八级(2024-12)
CCF GESP C++ 八级 (2024 年 12 月)
一、单选题（每题 2 分，共 30 分）
第 1 题小杨家响应国家 “以旧换新” 政策，将自家的汽油车置换为新能源汽车，正在准备自编车牌。自编车牌包括 5 位数字或英文字母，要求第5 位必须是数字，前 4 位中可以有最多 1 位英文字母。英文字母必须是大写，而且不能是 O 或 I（因为容易与数字 0 或 1 混淆）。请问自编车牌共有多少种可能性？( )
{{ select(1) }}
- 100,000
- 1,060,000
- 1,360,000
- 1,460,000
第 2 题新年到，四家人在一起聚会。其中两家有三口人，另外两家有两口人。现在要安排大家在一张十人圆桌坐下，要求一家人必须相邻就座。由于有 “主座” 的习俗，每个座位都被认为是不同的。请问共有多少种就座方案？( )
{{ select(2) }}
- 8640
- 6912
- 144
- 60
第 3 题下面关于 C++ 类继承的说法，错误的是 ( )。
{{ select(3) }}
- 一个类可以继承多个类。
- 一个类可以被多个类继承。
- 一个类可以继承另一个类的子类。
- 抽象类必须被至少一个类继承，否则会编译错误。
第 4 题使用邻接表表达一个简单有向图，图中包含 v 个顶点、e 条边，则该出边表中边节点的个数为 ( )。
{{ select(4) }}
第 5 题以下将二维数组作为参数的函数声明，哪个是符合语法的？( )
{{ select(5) }}
- void Bubble(int a[10][], int m);
- void Bubble(int a[][], int n, int m);
- void Bubble(int (*a)[20], int n);
- void Bubble(int *a[20], int n);
第 6 题已知两个点 A、B 在平面直角坐标系下的坐标分别为 ((x_a, y_a)) 和 ((x_b, y_b)) ，并分别定义变量double xa, ya, xb, yb;存储坐标。假设直线 AB 的斜率存在，下列哪个表达式可以用来表达它？( )
{{ select(6) }}
- (xa - xb) / (ya - yb)
- (xa - xb) / (yb - ya)
- (ya - yb) / (xa - xb)
- (ya - yb) / (xb - xa)
第 7 题二项式 的展开式中 项的系数是 ( )。
{{ select(7) }}
- 6
- 15
- 20
- 120
第 8 题以下关于动态规划的说法中，错误的是 ( )。
{{ select(8) }}
- 动态规划方法有递推和递归两种实现形式。
- 递归实现动态规划方法的时间复杂度总是不低于递推实现。
- 动态规划方法将原问题分解为一个或多个相似的子问题。
- 动态规划方法通常能够列出递推公式。
第 9 题在下面的程序中，使用整数表示一种组合。整数二进制表示的某一位为 1，表示该位对应的数被选中，反之 0 表示未选中。例如，从 0 - 5 这 6 个数中选出 3 个，则0b111000代表选中 3, 4, 5 三个数，0b011001代表选中 0, 3, 4 三个数。zuhe_next函数按组合对应的整数由大到小的顺序，求出组合c的下一个组合。横线处可以填入的是 ( )。
int intlow2(int c) {
return ___________; // 在此处填入选项
}
int zuhe_next_incur(int c, int n, int l) {
if (n == 1) return c;
if ((c & (1 << l)) == 0) {
int d = intlow2(c);
c = (c & ~d);
c = (c | (d >> 1));
} else {
c = (c & ~(1 << l));
c = zuhe_next_incur(c, n - 1, l + 1);
int d = intlow2(c);
c = (c | (d >> 1));
}
return c;
}
// 从n个数中选m个，当前组合为c
int zuhe_next(int c, int n, int m) {
return zuhe_next_incur(c, n, 0);
}
{{ select(9) }}
- ((c - 1) ^ c)
- (((c - 1) ^ c) + 1)
- (((c - 1) ^ c) >> 1)
- ((((c - 1) ^ c) + 1) >> 1)
第 10 题下面程序的输出为 ( )。
#include <iostream>
using namespace std;
int main() {
int N = 15, cnt = 0;
for (int x = 0; 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(10) }}
- 174
- 447
- 816
- 4096
第 11 题下面最长公共子序列程序中，横线处应该填入的是 ( )。
#define MAX(A, B) (((A) > (B)) ? (A) : (B))
#define MIN(A, B) (((A) < (B)) ? (A) : (B))
int dp[MAX_L + 1][MAX_L + 1];
int LCS(char str1[], char str2[]) {
int len2 = strlen(str2);
int len1 = strlen(str1);
for (int i = 0; i < len1; i++)
for (int j = 0; j < len2; j++)
if (str1[i] == str2[j])
dp[i + 1][j + 1] = dp[i][j] + 1;
else
_______________;// 在此处填入选项
return dp[len1][len2];
}
{{ select(11) }}
- dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
- dp[i + 1][j + 1] = MIN(dp[i][j + 1], dp[i + 1][j])
- dp[i + 1][j + 1] = MAX(dp[i][j + 1], dp[i + 1][j])
- dp[i + 1][j + 1] = MAX(dp[i][j + 1], dp[i + 1][j]) + 1
第 12 题下列 Dijkstra 算法中，横线处应该填入的是 ( )。
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) {
// 在此处填入选项
}
}
delete[] visited;
}
if (dis[e->out] > e->len)
dis[e->out] = e->len;
if (dis[e->out] > min + e->len)
dis[e->out] = min + e->len;
if (dis[e->in] > e->len)
dis[e->in] = e->len;
if (dis[e->in] > min + e->len)
dis[e->in] = min + e->len;
{{ select(12) }}
- 1
- 2
- 3
- 4
第 13 题假设图graph中顶点数v、边数e，上题程序的时间复杂度为 ( )。
{{ select(13) }}
第 14 题下面的快速排序程序中，两处横线处分别应填入的是 ( )。
void quick_sort(int a[], int n) {
if (n <= 1)
return;
int pivot = 0, l = 0, r = n - 1;
while (________) { // 在此处填入选项
while (r > pivot && a[r] >= a[pivot])
r--;
if (r > pivot) {
int temp = a[pivot];
a[pivot] = a[r];
a[r] = temp;
pivot = r;
}
while (l < pivot && a[l] <= a[pivot])
l++;
if (l < pivot) {
int temp = a[pivot];
a[pivot] = a[l];
a[l] = temp;
pivot = l;
}
}
quick_sort(a, pivot);
quick_sort(________); // 在此处填入选项
}
{{ select(14) }}
- 1. l < r 2. a + pivot + 1, n - pivot - 1
- 1. l < r 2. a + pivot + 1, n - pivot
- 1. l <= r 2. a + pivot + 1, n - pivot - 1
- 1. l <= r 2. a + pivot + 1, n - pivot
第 15 题上题程序的时间复杂度为 ( )。
{{ select(15) }}
二、判断题（每题 2 分，共 20 分）
第 1 题表达式'3' + '5'的结果为'8'，类型为char。
{{ select(16) }}
- 对
- 错
第 2 题在 C++ 语言中，可以在函数内定义结构体，但该结构体类型只能在该函数内使用。
{{ select(17) }}
- 对
- 错
第 3 题对 n 个元素的数组进行排序，快速排序和归并排序的平均时间复杂度都为 (O(n log n)) 。但快速排序存在退化情况，使得时间复杂度升高至 ；归并排序需要额外的空间开销。
{{ select(18) }}
- 对
- 错
第 4 题二维数组的最后一维在内存中一定是连续的，但第一维在内存中可能不连续。
{{ select(19) }}
- 对
- 错
第 5 题使用math.h或cmath头文件中的函数，表达式log(1000)的结果类型为double、值约为 3。
{{ select(20) }}
- 对
- 错
第 6 题你有三种硬币，分别面值 2 元、5 元和 7 元，每种硬币都有足够多。买一本书需要 27 元，则有 8 种硬币组合（组合与顺序无关，“1 个 2 元 + 1 个 5 元 + 1 个 2 元” 与 “1 个 5 元 + 2 个 2 元” 认为是同样的组合）可以正好付清，且不需要对方找钱。
{{ select(21) }}
- 对
- 错
第 7 题使用哈希函数 (f(x)=x % p) 建立键值为int类型的哈希表，只要p取小于等于哈希表大小的素数，可保证不发生碰撞。
{{ select(22) }}
- 对
- 错
第 8 题杨辉三角中的第n 行、第m 项，即为将二项式 展开后 项的系数。
{{ select(23) }}
- 对
- 错
第 9 题判断图是否连通，可以通过广度优先搜索实现。
{{ select(24) }}
- 对
- 错
第 10 题要求解一元二次方程 ，需要先判断表达式 是否为真。
{{ select(25) }}
- 对
- 错