题目背景

GESP 2024年12月认证 C++ 8级真题

一. 单选题 (每题 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) }}

• O(V)
• O(E)
• O(E+V)
• O(log(V+E))

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 在平面直角坐标系下的坐标分别为 (xa, ya) 和 (xb, yb)，下列哪个表达式可以用于计算直线 AB 的斜率？

   {{ select(6) }}

• (xa - xb) / (ya - yb)
• (xa - xb) / (yb - ya)
• (ya - yb) / (xa - xb)
• (ya - yb) / (xb - xa)

7. 二项式 $(x + y)^6$ 的展开式中 $xy^5$ 项的系数是多少？

   {{ select(7) }}

• 6
• 15
• 20
• 120

8. 以下关于动态规划的说法中，错误的是？

   {{ select(8) }}

• 动态规划方法有递推和递归两种实现形式。
• 递归实现动态规划方法的时间复杂度总是不低于递推实现。
• 动态规划方法将原问题分解为一个或多个相似的子问题。
• 动态规划方法通常能够列出递推公式。

9. 在二进制组合表示法中，整数 0b111000 代表选中 3, 4, 5 三个数， 0b011001 代表选中 0, 3, 4 三个数。zuhe_next 函数按组合对应的整数由大到小的顺序，求出组合 c 的下一个组合，横线处可以填入的代码是？

   int intlow2(int c) {
       return ________;  // 在此处填入选项
   }
   

{{ 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. 在最长公共子序列（LCS）程序中，横线处应该填入哪个选项？

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

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

//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;

{{ select(12) }}

• A
• B
• C
• D

13. 假设图 graph 中顶点数 v、边数 e，Dijkstra 算法的时间复杂度为？

{{ select(13) }}

• O(V^2)
• O(E + V log V)
• O(E log V)
• O(E + V)

14. 在快速排序程序中，while 循环条件应填入哪个选项？

while (________) {
    while (r > pivot && a[r] >= a[pivot])
        r--;
    if (r > pivot) {
        swap(a[pivot], a[r]);
        pivot = r;
    }
    while (l < pivot && a[l] <= a[pivot])
        l++;
    if (l < pivot) {
        swap(a[pivot], a[l]);
        pivot = l;
    }
}

{{ select(14) }}

• l < r
• l <= r
• l < pivot
• l <= pivot

15. 快速排序算法的平均时间复杂度是多少？

{{ select(15) }}

• O(N log N)
• O(N^2)
• O(N)
• O(log N)

二. 判断题 (每题 2 分，共 20 分)

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

    {{ select(16) }}

• 正确
• 错误

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

    {{ select(17) }}

• 正确
• 错误

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

    {{ select(18) }}

• 正确
• 错误

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

    {{ select(19) }}

• 正确
• 错误

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

    {{ select(20) }}

• 正确
• 错误

21. 在 N 个元素的二叉排序树中查找一个元素，最差情况的时间复杂度是 $O(log N)$。

    {{ select(21) }}

• 正确
• 错误

22. C++ 语言中，可以为同一个类定义多个析构函数。

    {{ select(22) }}

• 正确
• 错误

23. 使用单链表和使用双向链表，查找元素的时间复杂度相同。

    {{ select(23) }}

• 正确
• 错误

24. 为解决哈希函数冲突，可以使用不同的哈希函数为每个表项各建立一个子哈希表，用来管理该表项的所有冲突元素。这些子哈希表一定不会发生冲突。

    {{ select(24) }}

• 正确
• 错误

25. 要判断无向图的连通性，在深度优先搜索和广度优先搜索中选择，深度优先的平均时间复杂度更低。

    {{ select(25) }}

• 正确
• 错误