2024年12月 GESP C++ 8级

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

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

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

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

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

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

二项式 (a+b)6(a + b)^6(a+b)6 的展开式中 a4b2a^4 b^2a4b2 项的系数是（ ）。

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

在下面的程序中，使用整数表示一种组合。整数二进制表示的某一位为 $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);
}

下面程序的输出为（ ）。

#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;
}

下面最长公共子序列程序中，横线处应该填入的是（ ）。

#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];
}

下列 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;
}

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

下面的快速排序程序中，两处横线处分别应填入的是（ ）。

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(________); // 在此处填入选项
}

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

表达式 '3' + '5' 的结果为 '8'，类型为 char。

在 C++ 语言中，可以在函数内定义结构体，但该结构体类型只能在该函数内使用。

对 $n$ 个元素的数组进行排序，快速排序和归并排序的平均时间复杂度都为 $O(n\log n)$。但快速排序存在退化情况，使得时间复杂度升高至 O(n2)O(n^2)O(n2)；归并排序需要额外的空间开销。

二维数组的最后一维在内存中一定是连续的，但第一维在内存中可能不连续。

使用 math.h 或 cmath 头文件中的函数，表达式 log(1000) 的结果类型为 double、值约为 $3$。

你有三种硬币，分别面值 $2$ 元、$5$ 元和 $7$ 元，每种硬币都有足够多。买一本书需要 $27$ 元，则有 $8$ 种硬币组合（组合与顺序无关，“$1$ 个 $2$ 元 + $1$ 个 $5$ 元 + $1$ 个 $2$ 元”与“$1$ 个 $5$ 元 + $2$ 个 $2$ 元”认为是同样的组合）可以正好付清，且不需要对方找钱。

使用哈希函数 $f(x)=x\%p$ 建立键值为 int 类型的哈希表，只要 $p$ 取小于等于哈希表大小的素数，可保证不发生碰撞。

杨辉三角中的第 $n$ 行、第 $k$ 项，即为将二项式 (a+b)n(a + b)^n(a+b)n 展开后 an−kbka^{n-k} b^kan−kbk 项的系数。

判断图是否连通，可以通过广度优先搜索实现。

要求解一元二次方程，需要先判断表达式 a ^ 2 - b * 4 >= 0 是否为真。

试题名称：树上移动

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

小杨有一棵包含 $n$ 个节点的树，其中节点的编号从 $1$ 到 $n$，每个节点的颜色要么是白色要么是黑色，小杨可以任意选择节点 $s$ 和节点 $t$ 并从节点 $s$ 出发移动到节点 $t$，移动过程中小杨不能够经过重复节点。

小杨希望自己在至多经过 $k$ 个黑色节点的前提下，经过的总节点数尽可能多，请你帮小杨选择经过最多的节点数是多少。

输入格式

第一行包含两个正整数 $n,k$，代表节点数量和至多经过的黑色节点数。

第二行包含 $n$ 个正整数 a1,a2,…,ana_1,a_2,\dots,a_na1​,a2​,…,an​，代表节点颜色，如果 ai=0a_i=0ai​=0，代表节点颜色为白色，如果 ai=1a_i=1ai​=1，代表节点颜色为黑色。

之后 $n-1$ 行，每行包含两个正整数 ui,viu_i,v_iui​,vi​，代表存在一条连接 uiu_iui​ 和 viv_ivi​ 的边。

输出格式

输出一个正整数，代表最多经过的节点数。

样例输入 #1

5 1
0 0 1 1 1
1 2
2 3
2 5
1 4

样例输出 #1

3

说明/提示

对于全部数据，保证有 $1\le n\le 1000$，$0\le k\le 1000$，0≤ai≤10\leq a_i\leq 10≤ai​≤1。

试题名称：排队

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

小杨所在班级共有 $n$ 位同学，依次以 $1,2,\dots ,n$ 标号。这 $n$ 位同学想排成一行队伍，其中有些同学之间关系非常好，在队伍里需要排在相邻的位置。具体来说，有 $m$ 对这样的关系（$m$ 是一个非负整数）。当 $m\ge 1$ 时，第 $i$ 对关系（$1\le i\le m$）给出 ai,bia_i,b_iai​,bi​，表示排队时编号为 aia_iai​ 的同学需要排在编号为 bib_ibi​ 的同学前面，并且两人在队伍中相邻。

现在小杨想知道总共有多少种排队方式。由于答案可能很大，你只需要求出答案对 109+710^9+7109+7 取模的结果。

输入格式

第一行，两个整数 $n,m$，分别表示同学们的数量与关系数量。

接下来 $m$ 行，每行两个整数 ai,bia_i,b_iai​,bi​，表示一对关系。

输出格式

一行，一个整数，表示答案对 109+710^9+7109+7 取模的结果。

样例输入 #1

4 2
1 3
2 4

样例输出 #1

2

样例输入 #2

3 0

样例输出 #2

6

样例输入 #3

3 2
1 2
2 1

样例输出 #3

0

说明/提示

对于 $20\%$ 的测试数据点，保证 $1\le n\le 8$，$0\le m\le 10$。

对于另外 $20\%$ 的测试数据点，保证 1≤n≤1031\leq n\leq 10^31≤n≤103，$0\le m\le 1$。

对于所有测试数据点，保证 1≤n≤2×1051\leq n\leq 2\times 10^51≤n≤2×105，0≤m≤2×1050\leq m\leq 2\times 10^50≤m≤2×105。