GESP 八级 · 2024 真题

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

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

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

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

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

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

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

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

在下⾯的程序中，使⽤整数表⽰⼀种组合。整数⼆进制表⽰的某⼀位为 $1$，表⽰该位对应的数被选中，反之为 $0$ 表⽰未选中。例如，从 $0 - 5$ 这 $6$ 个数中选出 $3$ 个，则 0b111000 代表选中选中 $0 , 3, 4$ 三个数。$3, 4, 5$ 三个数，0b011001 代表 zuhe_next 函数按组合对应的整数由⼤到⼩的顺序，求出组合 $c$ 的下⼀个组合。横线处可以填⼊的是（ ）。

01int intlow2(int c) {
02    return ________;  // 在此处填入选项
03}
04int zuhe_next_incur(int c, int n, int l) {
05    if (n == l) return c;
06    if ((c & (1 << l)) == 0) {
07        int d = intlow2(c);
08        c = (c & ~d);
09        c = (c | (d >> 1));
10    } else {
11        c = (c & ~(1 << l));
12        c = zuhe_next_incur(c, n - 1, l + 1);
13        int d = intlow2(c);
14        c = (c | (d >> 1));
15    }
16    return c;
17}
18// 从n个数中选m个，当前组合为c
19int zuhe_next(int c, int n, int m) {
20    return zuhe_next_incur(c, n, 0);
21}

下⾯程序的输出为（ ）。

01#include <iostream>
02using namespace std;
03int main() {
04    int N = 15, cnt = 0;
05    for (int x = 0; x + x + x <= N; x++)
06        for (int y = x; x + y + y <= N; y++)
07            for (int z = y; x + y + z <= N; z++)
08                cnt++;
09    cout << cnt << endl;
10    return 0;
11}

下⾯最长公共⼦序列程序中，横线处应该填⼊的是（ ）。

01#define MAX(A, B) (((A) > (B)) ? (A) : (B))
02#define MIN(A, B) (((A) < (B)) ? (A) : (B))
03int dp[MAX_L + 1][MAX_L + 1];
04int LCS(char str1[], char str2[]) {
05    int len1 = strlen(str1);
06    int len2 = strlen(str2);
07    for (int i = 0; i < len1; i++)
08        for(int j = 0; j < len2; j++)
09            if (str1[i] == str2[j])
10                dp[i + 1][j + 1] = dp[i][j] + 1;
11            else
12                ___________;    // 在此处填入选项
13    return dp[len1][len2];
14}

下列 Dijkstra 算法程序及其时间复杂度：

01typedef struct Edge {
02    int in, out;     // 从下标in顶点到下标out顶点的边
03    int len;         // 边长度
04    struct Edge * next;
05} Edge;
06// v: 顶点个数, graph: 出边邻接表, start: 起点下标, dis: 输出每个顶点的最短距离
07void dijkstra(int v, Edge * graph[], int start, int * dis) {
08    const int MAX_DIS = 0x7fffff;
09    for (int i = 0; i < v; i++)
10        dis[i] = MAX_DIS;
11    dis[start] = 0;
12    int * visited = new int[v];
13    for (int i = 0; i < v; i++)
14        visited[i] = 0;
15    visited[start] = 1;
16    for (int t = 0; ; t++) {
17        int min = MAX_DIS, minv = -1;
18        for (int i = 0; i < v; i++) {
19            if (visited[i] == 0 && min > dis[i]) {
20                min = dis[i];
21                minv = i;
22            }
23        }
24        if (minv < 0)
25            break;
26        visited[minv] = 1;
27        for (Edge * e = graph[minv]; e != NULL; e = e->next) {
28            _________;  // 在此处填入选项
29        }
30    }
31    delete[] visited;
32}

下列快速排序程序及其时间复杂度：

01void quick_sort(int a[], int n) {
02    if (n <= 1)
03        return;
04    int pivot = 0, l = 0, r = n - 1;
05    while (______) {  // 在此处填入选项
06        while (r > pivot && a[r] >= a[pivot])
07            r--;
08        if (r > pivot) {
09            int temp = a[pivot];
10            a[pivot] = a[r];
11            a[r] = temp;
12            pivot = r;
13        }
14        while (l < pivot && a[l] <= a[pivot])
15            l++;
16        if (l < pivot) {
17            int temp = a[pivot];
18            a[pivot] = a[l];
19            a[l] = temp;
20            pivot = l;
21        }
22    }
23    quick_sort(a, pivot);
24    quick_sort(______);  // 在此处填入选项
25}

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

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

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

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

使⽤ math.h 或 cmat.h 头⽂件中的函数，表达式 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$ 取⼩于等于哈希表⼤⼩的素数，可保证不发⽣碰撞。

杨辉三角中的第 $i$ ⾏、第 $j$ 项，即为将⼆项式 $(a+b)^n$ 展开后 $a^{n-m}b^m$ 项的系数。

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

要求解⼀元⼆次⽅程 $x^2+ax+b=0$，需要先判断表达式 a ^ 2 - b * 4 >= 0 是否为真。