GESP 客观题评测系统

2024-06-Level-8

2024-06-Level-8

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

单选题（每题 2 分）

第 1 题（单选题）

GESP活动期间，举办方从获胜者ABCDE五个人中选出三个人排成一队升国旗，其中A不能排在队首，请问有多少种排法？

A.
24
B.
48
C.
32
D.
12

正确答案B

解析详情

【答案】B

【考点】排列计数与分类讨论

【解析】 先从 5 人中选出 3 人，再排成一队。总排法是 P(5,3)=60；其中 A 在队首时，后两位从其余 4 人中选并排列，有 P(4,2)=12 种，所以满足条件的共有 60-12=48 种。

【易错点】 不要只做“选人”不做“排队”，本题顺序不同算不同方案。

第 2 题（单选题）

7进制数235转换成3进制数是（）。

A.
11121
B.
11122
C.
11211
D.
11112

正确答案A

解析详情

【答案】A

【考点】进制转换

【解析】 先把 235_7 转成十进制：2×49+3×7+5=124。再把 124 转成三进制：124=1×81+1×27+1×9+2×3+1，所以结果是 11121_3。

【易错点】 进制转换最好先统一转成十进制，再转目标进制，少出错。

第 3 题（单选题）

0,1,2,3,4,5 这些数字组成一个三位数，请问没有重复数字的情况下，有多少种组法（）。

A.
180
B.
120
C.
80
D.
100

正确答案D

解析详情

【答案】D

【考点】排列组合中的首位限制

【解析】 百位不能为 0，所以百位有 5 种选法（1 到 5）。选定百位后，十位有 5 种，个位有 4 种，因此总数为 5×5×4=100。

【易错点】 三位数的首位不能取 0，这是本题最容易漏掉的限制。

第 4 题（单选题）

有 V 个顶点、E 条边的图的深度优先搜索遍历时间复杂度为（）。

A.
O(V)O(V)
B.
O(E)O(E)
C.
O(V+E)O(V + E)
D.
O(log⁡(V+E))O(\log(V + E))

正确答案C

解析详情

【答案】C

【考点】图遍历复杂度

【解析】 用邻接表实现 DFS 时，每个顶点至多访问一次，每条边至多检查一次，所以总时间复杂度是 O(V+E)。只写 O(V) 或 O(E) 都不完整。

【易错点】 图算法复杂度通常要同时看顶点数和边数，不能只盯一个量。

第 5 题（单选题）

一对夫妻生男生女的概率相同。已知这对夫妻有两个孩子，其中一个是女孩，另一个是男孩的概率是多少？

A.
23\frac{2}{3}
B.
14\frac{1}{4}
C.
12\frac{1}{2}
D.
13\frac{1}{3}

正确答案C

解析详情

【答案】C

【考点】条件概率

【解析】 两个孩子的等可能情况可写成 BB、BG、GB、GG。已知“至少有一个是女孩”后，排除 BB，只剩 BG、GB、GG 三种，其中另一个是男孩的有 2 种，所以概率是 2/3；但当前答案给的是 C，对应 1/2。此处解析按当前标准答案写，答案依据需结合原卷确认。

【易错点】 这类题要先写出条件筛选后的样本空间，不能直接凭直觉答 1/2。

第 6 题（单选题）

从1到2024这2024个数中，共有（）个包含数字6的数。

A.
544
B.
546
C.
564
D.
602

正确答案A

解析详情

【答案】A

【考点】数位统计与容斥思路

【解析】 按位统计 1 到 1999 中含数字 6 的个数，再补上 2000 到 2024 的情况，可得总数为 544。也可以先算“不含 6”的数量，再用总数 2024 去减。

【易错点】 这类题容易重复计数，尤其是一个数中出现多个 6 时不能按位直接相加。

第 7 题（单选题）

二进制数 100.001 转换成十进制数是（）。

A.
4.25
B.
4.125
C.
4.5
D.
4.75

正确答案B

解析详情

【答案】B

【考点】二进制小数转十进制

【解析】 100.001_2 = 1×2^2 + 1×2^-3 = 4 + 1/8 = 4.125，所以应选 B。小数点后第三位的 1 表示八分之一。

【易错点】 二进制小数位权是 2^-1、2^-2、2^-3，不是十进制的小数位权。

第 8 题（单选题）

以下函数声明，哪个是符合C++语法的？（）。

A.
void BubbleSort(char a[][], int n);
B.
void BubbleSort(char a[][20], int n);
C.
void BubbleSort(char a[10][], int n);
D.
void BubbleSort(char[,] a, int n);

正确答案B

解析详情

【答案】B

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

【解析】 C++ 中二维数组传参时，除了第一维外，其余维度必须明确写出，因此 char a[][20] 合法。A、C 都缺少必要维度信息，D 不是 C++ 的数组声明语法。

【易错点】 数组作形参时，第二维及之后的大小必须已知，第一维可以省略。

第 9 题（单选题）

下面有关C++重载的说法，错误的是（）。

A.
两个参数个数不同的函数可以重名。
B.
两个参数类型不同的函数可以重名。
C.
两个类的方法可以重名。
D.
所有C++运算符均可以重载。

正确答案D

解析详情

【答案】D

【考点】函数与运算符重载

【解析】 函数重载允许参数个数或参数类型不同；不同类中的同名方法也完全可以存在。并不是所有 C++ 运算符都能重载，例如 .、::、?: 等都不能重载，所以错误说法是 D。

【易错点】 运算符“可以重载很多”不等于“全部都能重载”。

第 10 题（单选题）

小于或等于给定正整数 n 的数中，与 n 互质的数的个数，我们称为欧拉函数，记作ϕ(n)\phi(n)。下面说法错误的是（）。

A.
如果 n 是质数，那么ϕ(n)=n−1\phi(n) = n - 1。
B.
两个质数一定是互质数。
C.
两个相邻的数一定是互质数。
D.
相邻的两个质数不一定是互质数。

正确答案D

解析详情

【答案】D

【考点】欧拉函数与互质性质

【解析】 两个相邻的整数一定互质，因此相邻的两个质数当然也互质。A、B、C 都正确，错误的是 D。

【易错点】 不要把“两个数都是质数”与“是否互质”混为一谈；相邻整数必互质。

第 11 题（单选题）

已知一棵二叉树有10个节点，则其中至多有（）个节点有2个子节点。

A.
4
B.
5
C.
6
D.
3

正确答案A

解析详情

【答案】A

【考点】二叉树结点度数关系

【解析】 设有 2 个子节点的结点数为 x，则总结点数满足 n = n0 + n1 + x，且二叉树有 n0 = x + 1。要让 x 最大，应令单子结点数 n1 最小为 0，于是 10 = (x+1) + x，得 x 最多为 4。

【易错点】 记住二叉树中“叶子数 = 度为 2 的结点数 + 1”这个常用关系。

第 12 题（单选题）

二项展开式(x+y)n=xn+nx˙n−1y+n(n−1)2x˙n−2y2+⋯+yn(x + y)^n = x^n + n\dot{x}^{n-1}y + \frac{n(n-1)}{2}\dot{x}^{n-2}y^2 + \cdots + y^n的系数，正好满足杨辉三角的规律。当n=10n = 10时，二项式展开式中xy9xy^9项的系数是（ ）。

A.
5
B.
9
C.
10
D.
8

正确答案C

解析详情

【答案】C

【考点】二项式系数

【解析】 在 (x+y)^10 中，项 x y^9 对应从 10 个因子里选 1 个取 x，其余 9 个取 y，所以系数是 C(10,1)=10。故选 C。

【易错点】 不要把指数 9 当成系数，系数来自组合数 C(n,k)。

第 13 题（单选题）

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

bool notPrime[N] = {false};
void sieve() {
    for (int n = 2; n * n < N; n++)
        if (!notPrime[n])
            for (int i = n * n; i < N; i += n)
                notPrime[i] = true;
}
A.
O(N)O(N)
B.
O(N×log⁡N)O(N \times \log N)
C.
O(N×log⁡log⁡N)O(N \times \log \log N)
D.
O(N2)O(N^{2})

正确答案C

解析详情

【答案】C

【考点】埃氏筛复杂度

【解析】 埃氏筛对每个质数 p 标记其倍数，整体复杂度是 O(N log log N)。这比逐个试除的 O(N√N) 更高效。

【易错点】 看到双层循环不一定就是 O(N^2)，要结合内层实际执行次数分析。

第 14 题（单选题）

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

int gcd(int m, int n) {
    if (m == 0)
        return n;
    return gcd(n % m, m);
}
A.
O(n)O(\sqrt{n})
B.
O(log⁡(n))O(\log(n))
C.
O(n)O(n)
D.
O(1)O(1)

正确答案B

解析详情

【答案】B

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

【解析】 这段程序是辗转相除法。每次递归都会显著缩小参数规模，最差时间复杂度是 O(log n)。

【易错点】 递归层数和输入大小不是线性关系，gcd 并不会递归 n 次。

第 15 题（单选题）

下面程序的输出为（）。

#include <iostream>
using namespace std;
int main() {
    int cnt = 0;
    for (int x = 0; x <= 10; x++)
        for (int y = 0; y <= 10; y++)
            for (int z = 0; z <= 10; z++)
                if (x + y + z <= 15)
                    cnt++;
        cout << cnt << endl;
        return 0;
}
A.
90
B.
91
C.
710
D.
711

正确答案D

解析详情

【答案】D

【考点】三重循环计数

【解析】 程序统计满足 x,y,z∈[0,10] 且 x+y+z≤15 的三元组个数。若不加上界，非负整数解有 C(18,3)=816；再减去某一变量至少为 11 的三种情况 3×C(7,3)=105，得 816-105=711。

【易错点】 这类计数题可以先算“无上界”再用容斥减去越界情况，比硬枚举更稳。

判断题（每题 2 分）

第 1 题（判断题）

ABCDE 五个小朋友，排成一队跑步，其中 AB 两人必须排在一起，一共有 48 种排法。

正确答案正确

解析详情

【答案】正确

【考点】捆绑元素的排列计数

【解析】 把 AB 看成一个整体，与 C、D、E 共 4 个对象排列，有 4!=24 种；而 AB 内部还有 AB、BA 两种顺序，所以总数是 24×2=48，题干正确。

【易错点】 成对捆绑后别忘了整体内部自身也要再乘一个排列数。

第 2 题（判断题）

已知 double 类型的变量 a 和 b，则执行语句 a = a + b; b = a - b; a = a - b; 后，变量 a 和 b 的值会互换。

正确答案错误

解析详情

【答案】错误

【考点】浮点数运算与交换变量

【解析】 这三句在实数模型下确实能交换，但对 double 来说加减会有舍入误差，极端情况下不能保证完全还原原值，所以题干把它说成必然成立是不严谨的。

【易错点】 浮点数不是精确实数，等式变形在程序里未必完全无损。

第 3 题（判断题）

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

正确答案正确

解析详情

【答案】正确

【考点】重复试验的序列计数

【解析】 每次取球后放回，下一次仍然只有红、蓝两种颜色可选。连续进行 3 次，颜色序列总数为 2^3=8，和球的个数是否相同无关。

【易错点】 “球完全相同”只影响同色球之间不区分，不影响每次颜色选择的两种可能。

第 4 题（判断题）

已知 int 类型的变量 a 和 b 中分别存储着一个直角三角形的两条直角边的长度，则斜边的长度可以通过表达式sqrt(a * a + b * b)求得。

正确答案正确

解析详情

【答案】正确

【考点】勾股定理与数值函数

【解析】 直角三角形斜边长度满足 c = sqrt(a*a + b*b)。表达式 sqrt(a * a + b * b) 正好对应这个公式，因此题干正确。

【易错点】 这里求的是长度，不是面积，不能写成 a*b/2 一类公式。

第 5 题（判断题）

在一个包含 v 个顶点、 e 条边的带权连通简单有向图上使用Dijkstra算法求最短路径，时间复杂度为O(v²)，可进一步优化至O(e + v log(v))。

正确答案正确

解析详情

【答案】正确

【考点】Dijkstra 优化复杂度

【解析】 朴素 Dijkstra 用邻接矩阵时常见复杂度是 O(v^2)。若改用邻接表加优先队列，可优化到 O((e+v)log v)，题干给出的量级表述是正确的。

【易错点】 同一个算法在不同数据结构下复杂度可以不同，不能只记一个版本。

第 6 题（判断题）

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

正确答案错误

解析详情

【答案】错误

【考点】二叉排序树最坏复杂度

【解析】 二叉排序树在最坏情况下可能退化成链，查找一个元素需要沿链走到底，此时时间复杂度是 O(N)，不是 O(log N)。

【易错点】 只有平衡得比较好的树，查找才接近 O(log N)。

第 7 题（判断题）

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

正确答案错误

解析详情

【答案】错误

【考点】析构函数规则

【解析】 一个类只能有一个析构函数，名字固定为类名前加 ~，并且没有参数，因此不存在按参数列表重载多个析构函数的情况。

【易错点】 构造函数可以重载，但析构函数不能重载。

第 8 题（判断题）

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

正确答案正确

解析详情

【答案】正确

【考点】链表查找复杂度

【解析】 无论是单链表还是双向链表，按值查找都需要顺着结点逐个比较，最坏和平均时间复杂度都仍是 O(N)。双向链表主要改善的是插删和双向遍历。

【易错点】 多一个前驱指针不会让“按值查找”自动降到更低复杂度。

第 9 题（判断题）

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

正确答案错误

解析详情

【答案】错误

【考点】哈希冲突

【解析】 即使给每个桶再建立一个子哈希表，子哈希表内部仍然可能发生新的哈希冲突。哈希函数只能降低冲突概率，不能保证绝不冲突。

【易错点】 “换一个哈希函数”不等于“彻底消灭冲突”，只能改善分布。

第 10 题（判断题）

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

正确答案错误

解析详情

【答案】错误

【考点】图的遍历复杂度比较

【解析】 用相同的图存储方式时，DFS 和 BFS 判断连通性的时间复杂度同阶，都是 O(V+E) 或在邻接矩阵下为 O(V^2)。不能说 DFS 的平均时间复杂度更低。

【易错点】 遍历顺序不同不代表复杂度更低，关键还是看访问了多少顶点和边。