GESP 客观题评测系统

2023-12-Level-8

试卷解析总览，可直接查看每题答案与解析。

单选题（每题 2 分）

第 1 题（单选题）

小杨要从A城到B城，又想顺路游览一番。他有两个选项：1、坐高铁路到C城游览，再坐高铁或飞机到B城；2、坐船到D城游览，再坐船、高铁或飞机到B城。请问小杨从A城到B城共有几种交通方案可以选择？（）。

正确答案C

解析详情

【答案】C

【考点】乘法原理与加法原理

【解析】经 C 城的方案数是 1×2=2，经 D 城的方案数是 1×3=3。两条路线互斥，因此总方案数为 2+3=5。

【易错点】先分路线，再在每条路线内部用乘法原理，最后再相加。

第 2 题（单选题）

以下哪个函数声明是符合语法的，且在调用时可以将二维数组的名字作为实际参数传递给形式参数 a？（）。

void QuickSort(int a[][10], int n);

void QuickSort(int a[5][], int m);

void QuickSort(int a[][], int n, int m);

void QuickSort(int ** a, int n, int m);

正确答案A

解析详情

【答案】A

【考点】二维数组作函数参数

【解析】二维数组传参时，除第一维外，其余维度必须写明，所以 int a[][10] 合法。B 和 C 都缺少必要维度信息，D 的 int** 也不能直接接普通二维数组名。

【易错点】数组形参里“第一维可省略，后面的维度必须确定”是关键规则。

第 3 题（单选题）

下面有关C++类和对象的说法，错误的是（）。

对象的生命周期开始时，会执行构造函数。

对象的生命周期结束时，会执行析构函数。

类的析构函数可以为虚函数。

类的构造函数可以为虚函数。

正确答案D

解析详情

【答案】D

【考点】构造函数与析构函数

【解析】对象创建时会调用构造函数，生命周期结束时会调用析构函数，析构函数也可以是虚函数。构造函数不能声明为虚函数，所以错误说法是 D。

【易错点】虚析构很常见，但虚构造函数在 C++ 中不存在。

第 4 题（单选题）

使用邻接矩阵表达 n 个顶点的有向图，则该矩阵的大小为（）。

n \times (n+1)

n \times n

n \times (n-1)

n \times (n-1)/2

正确答案B

解析详情

【答案】B

【考点】邻接矩阵表示

【解析】邻接矩阵的行和列都对应顶点集合。无论有向图还是无向图，只要有 n 个顶点，矩阵大小都是 n×n。

【易错点】边数多少会影响矩阵中非零元素个数，但不会改变矩阵尺寸。

第 5 题（单选题）

5 位同学排队，其中一位同学不能排在第一，则共有多少种可能的排队方式？（）。

120

正确答案C

解析详情

【答案】C

【考点】排列计数中的限制条件

【解析】 5 人全排列共有 5!=120 种。若那位同学排在第一位，其余 4 人任意排，有 4!=24 种，因此满足条件的排法是 120-24=96。

【易错点】 “不能排第一”最稳的做法是用总数减去违背条件的情况。

第 6 题（单选题）

一个无向图包含 n 个顶点，则其最小生成树包含多少条边？（）。

n - 1

n + 1

最小生成树可能不存在。

正确答案D

解析详情

【答案】D

【考点】最小生成树存在条件

【解析】最小生成树只在图连通时才存在。题目只说“无向图包含 n 个顶点”，没有保证连通，因此最小生成树可能不存在，D 正确。

【易错点】 n-1 条边是连通图的生成树性质，不是所有无向图都自动满足。

第 7 题（单选题）

已知三个 double 类型的变量 a、b 和 theta 分别表示一个三角形的两条边长及二者的夹角（弧度），则下列哪个表达式可以计算这个三角形的面积？（）。

a * b * sin(theta) / 2

(a + b) * sin(theta) / 2

a * b * cos(theta) / 2

sqrt(a * a + b * b - 2 * a * b * cos(theta))

正确答案A

解析详情

【答案】A

【考点】三角形面积公式

【解析】已知两边及夹角时，三角形面积公式为 S = a*b*sin(theta)/2。C 用的是余弦，D 算的是第三边长度，不是面积。

【易错点】 “已知两边夹角求面积”对应正弦，不对应余弦定理。

第 8 题（单选题）

对有 n 个元素的二叉排序树进行中序遍历，其时间复杂度是（）。

O(1)

O(\log(n))

O(n)

O(n^2)

正确答案C

解析详情

【答案】C

【考点】树遍历复杂度

【解析】中序遍历需要访问二叉排序树中的每个结点一次，因此总时间与结点数成正比，复杂度为 O(n)。

【易错点】即使树比较平衡，完整遍历所有结点也不可能只有 O(log n)。

第 9 题（单选题）

假设输入参数 m 和 n 满足 $m \leq n$ ，则下面程序的最差情况的时间复杂度为（）。

int gcd(int m, int n) {
    while (m > 0) {
        int t = m;
        m = n % m;
        n = t;
    }
    return n;
}

O(\log(n))

O(n)

O(n \times m)

O(m \times \log(n))

正确答案A

解析详情

【答案】A

【考点】欧几里得算法复杂度

【解析】代码实现的是辗转相除法：m = n % m，每轮都会显著缩小参数规模。其最坏时间复杂度与较大数的对数同阶，为 O(log n)。

【易错点】不要把循环次数和数值大小线性对应，取模会让规模快速下降。

第 10 题（单选题）

下面程序的时间复杂度为（）。

long long power_mod (long long a, long long n, long long mod) {
    if (n == 0)
        return 1;
    a = a % mod;
    if (n == 1)
        return a;
    long long pw = power_mod(a, n / 2, mod);
    long long pw2 = pw * pw % mod;
    if (n % 2 == 0)
        return pw2;
    return pw2 * a % mod;
}

O(n)

O(a^n)

O(\log n)

O(\log n \times a)

正确答案C

解析详情

【答案】C

【考点】快速幂复杂度

【解析】函数每次递归都把指数 n 减半，只做常数次乘法和取模，因此递归深度是 O(log n)，总时间复杂度也是 O(log n)。

【易错点】快速幂的核心优势就是“指数减半”，不是每次只减 1。

第 11 题（单选题）

下面程序的时间复杂度为（）。

int record_choose[MAXN][MAXM];
int choose(int n, int m) {
    if (m == 0 || m == n)
        return 1;
    if (record_choose[n][m] == 0)
        record_choose[n][m] = choose(n - 1, m - 1) + choose(n - 1, m);
    return record_choose[n][m];
}

O(2^n)

O(2^m \times (n - m))

O(C(n,m))

O(m \times (n - m))

正确答案D

解析详情

【答案】D

【考点】记忆化搜索状态数

【解析】 choose(n,m) 只会计算到 0≤j≤m 且 j≤i≤n 的必要状态，每个状态至多求一次。状态总数约为 m*(n-m) 量级，所以复杂度选 D。

【易错点】有记忆化后，复杂度不再是朴素递归的指数级。

第 12 题（单选题）

下面的程序使用出边的邻接表表达有向图，则下列选项中哪个是它表达的图？（）。

#include <iostream>

struct Edge {
    int e;
    Edge * next;
};

struct Node {
    Edge * first;
};

int main() {
    Edge e[5] = {{1, nullptr}, {2, &e[2]}, 
                 {3, nullptr}, {3, nullptr}, {0, nullptr}};
    Node n[4] = {{&e[0]}, {&e[1]}, {&e[3]}, {&e[4]}};
    ;//其他处理
    return 0;
}

正确答案B

解析详情

【答案】B

【考点】有向图邻接表

【解析】由 Node n[4] = {{&e[0]}, {&e[1]}, {&e[3]}, {&e[4]}} 可知有 4 个顶点。边表给出的出边依次是 0→1，1→2→3，2→3，3→0，与选项 B 的图一致。

【易错点】读邻接表时要顺着 next 指针把同一顶点的整条边链看完整。

第 13 题（单选题）

下面程序的输出为（）。

#include <iostream>
using namespace std;

int main() {
    int cnt = 0;
    for (int a = 1; a <= 10; a++)
        for (int b = 1; b <= 10; b++)
            for (int h = 1; h <= 10; h++)
                if ((a + b) * h == 20)
                    cnt++;
    cout << cnt << endl;
    return 0;
}

正确答案B

解析详情

【答案】B

【考点】三重枚举与约数计数

【解析】条件 (a+b)*h=20，先枚举 s=a+b。当 s 为 20 的正因子且 2≤s≤20 时，h 被唯一确定；而对每个 s，满足 a+b=s 的正整数对有 s-1 个。把 s=2,4,5,10,20 对应的个数相加得 1+3+4+9+1=18。

【易错点】先把条件改写成乘积形式，再按因子分类统计，比硬枚举更清楚。

第 14 题（单选题）

下面程序的输出为（）。

#include <iostream>
using namespace std;

int main() {
    const int N = 30;
    int cnt = 0;
    for (int a = 1; a <= N; a++)
        for (int b = a; a + b <= N; b++)
            for (int c = b; a + b + c <= N; c++)
                if (a * a + b * b == c * c)
                    cnt++;
    cout << cnt << endl;
    return 0;
}

正确答案A

解析详情

【答案】A

【考点】枚举勾股数

【解析】程序统计满足 a≤b≤c、a+b+c≤30 且 a^2+b^2=c^2 的三元组。只有 (3,4,5)、(6,8,10)、(5,12,13) 三组，所以输出 3。

【易错点】同一个勾股数组的倍数也要检查是否仍满足周长不超过 30。

第 15 题（单选题）

下面的程序中，二维数组 h 和 v 分别代表如下图所示的网格中的水平边的时间消耗和垂直边的时间消耗。程序使用动态规划计算从左下角到右上角的最小时间消耗，则横线处应该填写下列哪个选项的代码？（）。

int dis[MAXY][MAXX];
int shortest_path(int x, int y) {
    dis[0][0] = 0;
    for (int i = 0; i < y; i++)
        dis[i + 1][0] = dis[i][0] + v[i][0];
    for (int j = 0; j < x; j++)
        dis[0][j + 1] = dis[0][j] + h[0][j];
    for (int i = 0; i < y; i++)
        for (int j = 0; j < x; j++)
            // 在此处填写代码
    return dis[y][x];
}

dis[i][j] = min(dis[i - 1][j] + v[i - 1][j], dis[i][j - 1] + h[i][j - 1]);

dis[i][j] = min(dis[i - 1][j] + h[i - 1][j], dis[i][j - 1] + v[i][j - 1]);

dis[i + 1][j + 1] = min(dis[i][j + 1] + v[i][j + 1], dis[i + 1][j] + h[i + 1][j]);

dis[i + 1][j + 1] = min(dis[i][j + 1] + h[i][j + 1], dis[i + 1][j] + v[i + 1][j]);

正确答案C

解析详情

【答案】C

【考点】网格动态规划转移

【解析】循环变量是 i=0..y-1, j=0..x-1，因此当前要填的是右上角状态 dis[i+1][j+1]。它可以从下方 dis[i][j+1] 经过竖边 v[i][j+1] 到达，或从左侧 dis[i+1][j] 经过横边 h[i+1][j] 到达，所以应取两者最小值，对应 C。

【易错点】先看循环下标决定“正在更新哪个格子”，再写转移式。

判断题（每题 2 分）

第 1 题（判断题）

C++语言非常强大，可以用来求解方程的解。例如，如果变量 x 为 double 类型的变量，则执行语句 x * 2 - 4 = 0；后，变量 x 的值会变为 2.0。

正确答案错误

解析详情

【答案】错误

【考点】赋值语句合法性

【解析】 x * 2 - 4 = 0 不是合法赋值语句，因为等号左边不是可修改左值，而是一个算术表达式。它不会把 x 变成 2.0。

【易错点】程序里的 = 是赋值，不是“解方程”。

第 2 题（判断题）

一个袋子中有3个完全相同的红色小球、2个完全相同的蓝色小球。每次从中取出1个，且不放回袋子，这样进行3次后，将取出的小球依次排列，则可能的颜色顺序有7种。

正确答案正确

解析详情

【答案】正确

【考点】分类计数

【解析】不放回取 3 次，颜色序列只可能由红 R、蓝 B 组成，但蓝球最多 2 个，所以 BBB 不可能，其余 8 个长度为 3 的二进制序列中剩下 7 个都可实现。故题干正确。

【易错点】这里统计的是颜色顺序，不是具体哪一个球。

第 3 题（判断题）

杨辉三角，是二项式系数的一种三角形排列，在中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现，是中国数学史上的一项伟大成就。

正确答案正确

解析详情

【答案】正确

【考点】杨辉三角的历史背景

【解析】题干对杨辉三角的历史表述是常见且正确的：它对应二项式系数排列，并且在杨辉《详解九章算法》中有系统记载。

【易错点】杨辉三角虽然国际上也常见，但中国古代文献中的记载更早。

第 4 题（判断题）

N 个顶点的有向完全图（不带自环）有 $N \times (N - 1)/2$ 条边。

正确答案错误

解析详情

【答案】错误

【考点】有向完全图边数

【解析】有向完全图中，从每个顶点到其余 N-1 个顶点都各有一条边，因此总边数是 N*(N-1)。N*(N-1)/2 是无向完全图的边数。

【易错点】有向图里 u→v 和 v→u 是两条不同的边。

第 5 题（判断题）

如果待查找的元素确定，只要哈希表的大小不小于查找元素的个数，就一定存在不会产生冲突的哈希函数。

正确答案正确

解析详情

【答案】正确

【考点】完美哈希思想

【解析】对一组确定的有限关键字，只要表长不少于关键字个数，就可以构造一个无冲突的单射映射，也就是完美哈希。题干说的是“存在”，因此判断为正确。

【易错点】 “存在某个无冲突哈希函数”和“随便选一个哈希函数都无冲突”是两回事。

第 6 题（判断题）

动态规划算法的时间复杂度一般为：必要状态的数量，乘以计算一次状态转移方程的时间复杂度。

正确答案正确

解析详情

【答案】正确

【考点】动态规划复杂度估计

【解析】动态规划的总复杂度通常可以估成“状态数 × 单次转移代价”。这是分析 DP 复杂度时最常用的基本方法。

【易错点】别只看状态数，还要把每个状态转移时遍历了多少可能也乘进去。

第 7 题（判断题）

已知 int 类型的变量 a、b 和 h 中分别存储着一个梯形的顶边长、底边长和高，则这个梯形的面积可以通过表达式 $(a + b) * h / 2$ 求得。

正确答案错误

解析详情

【答案】错误

【考点】整数除法与面积公式

【解析】梯形面积公式本身是 (a+b)*h/2，但当 a、b、h 都是 int 时，这个表达式按整型计算，结果可能被截断，不一定得到真实面积，所以题干说法不严谨。

【易错点】涉及除以 2 的面积公式时，要注意是否发生整除截断。

第 8 题（判断题）

判断图是否连通只能用广度优先搜索算法实现。

正确答案错误

解析详情

【答案】错误

【考点】图连通性的搜索方法

【解析】判断图是否连通既可以用广度优先搜索，也可以用深度优先搜索。两者都能从某个起点出发检查是否访问到全部顶点。

【易错点】 BFS 和 DFS 经常只是遍历顺序不同，不是“一个能做、一个不能做”。

第 9 题（判断题）

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

正确答案错误

解析详情

【答案】错误

【考点】最好情况复杂度

【解析】在二叉排序树中查找时，若目标正好在根结点，只需常数次比较，因此最好情况复杂度是 O(1)，不是 O(log N)。

【易错点】 “最好情况”看的是最理想输入，不是平均情况或平衡树情况。

第 10 题（判断题）

给定 double 类型的变量 x，且其值大于等于 0，我们可以通过二分法求出 $\sqrt{x}$ 的近似值。

正确答案正确

解析详情

【答案】正确

【考点】二分法求平方根

【解析】当 x≥0 时，函数 f(t)=t^2 在非负区间上单调递增，因此可以在 [0,max(1,x)] 上用二分法逼近满足 t^2=x 的非负根。

【易错点】二分法要依赖单调性，所以区间必须限制在非负范围内。