CCF GESP 2024年12月认证 C++ 8级

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

小杨家响应国家“以旧换新”政策，将自家的汽油车置换为新能源汽车，正在准备自编车牌。自编车牌包括 5 位数字或英文字母，要求第 5 位必须是数字，前 4 位中可以有最多 1 位英文字母。英文字母必须是大写，而且不能是 O 或 I（因为容易与数字 0 或 1 混淆）。请问自编车牌共有多少种可能性？（ ）

A

$100000$
B

$1060000$
C

$1360000$
D

$1460000$
第 2 题

新年到，四家人在一起聚会。其中两家有三口人，另外两家有两口人。现在要安排大家在一张十人圆桌坐下，要求一家人必须相邻就座。由于有“主座”的习俗，每个座位都被认为是不同的。请问共有多少种就座方案？（ ）

A

$8640$
B

$6912$
C

$144$
D

$60$
第 3 题

下面关于 C++ 类继承的说法，错误的是（ ）。

A

一个类可以继承多个类。
B

一个类可以被多个类继承。
C

一个类可以继承另一个类的子类。
D

抽象类必须被至少一个类继承，否则会编译错误。
第 4 题

使用邻接表表达一个简单有向图，图中包含 $v$ 个顶点、$e$ 条边，则该出边表中边节点的个数为（ ）。

A

$v \times (v - 1)$
B

$v \times v$
C

$2 \times e$
D

$e$
第 5 题

以下将二维数组作为参数的函数声明，哪个是符合语法的？（ ）。

A

void Bubble(int a[10][], int m);
B

void Bubble(int a[][], int n, int m);
C

void Bubble(int (*a)[20], int n);
D

void Bubble(int * a[20], int n);
第 6 题

已知两个点 A、 B 在平面直角坐标系下的坐标分别为 $(xa, ya)$ 和 $(xb, yb)$，并分别定义变量 double xa, ya, xb, yb; 存储坐标。假设直线 AB 的斜率存在，下列哪个表达式可以用来表达它？（ ）。

A

$(xa - xb) / (ya - yb)$
B

$(xa - xb) / (yb - ya)$
C

$(ya - yb) / (xa - xb)$
D

$(ya - yb) / (xb - xa)$
第 7 题

二项式 $(x + y)^6$ 的展开式中 $x^3 y^3$ 项的系数是（ ）。

A

$6$
B

$15$
C

$20$
D

$120$
第 8 题

以下关于动态规划的说法中，错误的是（ ）。

A

动态规划方法有递推和递归两种实现形式。
B

递归实现动态规划方法的时间复杂度总是不低于递推实现。
C

动态规划方法将原问题分解为一个或多个相似的子问题。
D

动态规划方法通常能够列出递推公式。
第 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);
}
A

((c - 1) ^ c)
B

(((c - 1) ^ c) + 1)
C

(((c - 1) ^ c) >> 1)
D

((((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;
}
A

$174$
B

$447$
C

$816$
D

$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 len1 = strlen(str1);
    int len2 = strlen(str2);
    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];
}
A

dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
B

dp[i + 1][j + 1] = MIN(dp[i][j + 1], dp[i + 1][j])
C

dp[i + 1][j + 1] = MAX(dp[i][j + 1], dp[i + 1][j])
D

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;
}
A 
if (dis[e->out] > e->len)
    dis[e->out] = e->len;
B 
if (dis[e->out] > min + e->len)
    dis[e->out] = min + e->len;
C 
if (dis[e->in] > e->len)
    dis[e->in] = e->len;
D 
if (dis[e->in] > min + e->len)
    dis[e->in] = min + e->len;
第 13 题

假设图 graph 中顶点数 $v$、边数 $e$，上题程序的时间复杂度为（ ）。

A

$O(e)$
B

$O(v^2)$
C

$O(v \log v + e)$
D

$O((v + e) \log v)$
第 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(________); // 在此处填入选项
}
A 
l < r
a + pivot + 1, n - pivot - 1
B 
l < r
a + pivot + 1, n - pivot
C 
l <= r
a + pivot + 1, n - pivot - 1
D 
l <= r
a + pivot + 1, n - pivot
第 15 题

上题程序的时间复杂度为（ ）。

A

$O(n)$
B

$O(n^2)$
C

$O(2^n)$
D

$O(n \log n)$
单选题部分已到底了。