GESP 客观题评测系统
导航
注册

试卷解析 · 理解每一步

2024-06-Level-8

2024-06-Level-8

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

单选题

第 1 题（单选题，2 分）

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

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

正确答案B

解析详情
答案 B限制排列
思路与推导

  1. 先安排队首，A 不能在此位置，故有 4 种选择。

  2. 队伍只有 3 人；确定队首后，第二位从剩余 4 人中选，第三位从剩余 3 人中选，共 4×4×3=484×4×3=48 种，选 B。

第 2 题（单选题，2 分）

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

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

正确答案A

解析详情
答案 A进制转换
思路与推导

  1. 先按位权展开七进制数：2357=2×49+3×7+5=124235_7=2×49+3×7+5=124。

  2. 再拆成三进制位权：124=81+27+9+2×3+1124=81+27+9+2×3+1，依次得到数字 1、1、1、2、1，即 11121311121_3，选 A。

第 3 题（单选题，2 分）

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

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

正确答案D

解析详情
答案 D无重复数字计数
思路与推导

  1. 百位不能为 0，所以有 1 到 5 共 5 种选择。确定百位后，十位可以用剩下的任意数字，包括 0，共 5 种。

  2. 个位再从剩下的 4 个数字中选择，因此总数为 5×5×4=1005×5×4=100，选 D。

第 4 题（单选题，2 分）

有 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

解析详情
答案 CDFS 时间复杂度
思路与推导

  1. 以邻接表存储时，DFS 给每个顶点做一次访问标记，并扫描每条边对应的邻接项。

  2. 顶点部分为 O(V)O(V)，边部分为 O(E)O(E)，相加得到 O(V+E)O(V+E)，选 C。无向边虽扫描两次，也只是常数倍。

第 5 题（单选题，2 分）

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

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

正确答案C

解析详情
答案 C条件概率
思路与推导

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

第 6 题（单选题，2 分）

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

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

正确答案A

解析详情
答案 A补集计数
思路与推导

  1. 先统计 000 到 999：三个位置不出现 6 时各有 9 种选择，共 93=7299^3=729 个；因此含 6 的有 1000−729=2711000-729=271 个。

  2. 1000 到 1999 的千位为 1，后三位同理有 271 个。2000 到 2024 中只有 2006、2016 含 6，共 2 个。

  3. 合计 271+271+2=544271+271+2=544，选 A；000 不含 6，不影响所求范围。

第 7 题（单选题，2 分）

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

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

正确答案B

解析详情
答案 B二进制小数
思路与推导

  1. 二进制小数点左边的位权是 1、2、4，右边依次是 1/2、1/4、1/8。

  2. 100.0012=1×4+1×18=4.125100.001_2=1×4+1×\frac18=4.125，选 B。

第 8 题（单选题，2 分）

以下函数声明，哪个是符合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二维数组形参
思路与推导

  1. 二维数组访问一行后要能计算下一行的起始地址，因此形参中必须指定第二维长度。

  2. char a[][20] 保留每行 20 个 char 的信息，第一维可省略，故 B 正确。a[][] 和 a[10][] 均缺少必要的列数；char[,] 也不是 C++ 数组声明语法。

第 9 题（单选题，2 分）

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

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

正确答案D

解析详情
答案 D运算符重载
思路与推导

  1. 函数可以通过参数个数或参数类型区分重载，不同类中也可定义同名成员函数。

  2. 但 C++ 并非所有运算符都能重载，例如 .、::、?: 和 sizeof 不能重载，所以 D 错误。

第 10 题（单选题，2 分）

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

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

正确答案D

解析详情
答案 D互质与质数
思路与推导

  1. 两个不同质数的正因数各只有 1 和自身，所以最大公约数必为 1。相邻的两个质数一定不同，因此一定互质，D 错误。

  2. 对于质数 n，1 到 n−1 都与它互质，故 ϕ(n)=n−1\phi(n)=n-1。相邻整数的公因数必须整除它们的差 1，也必互质。

  3. B 按通常题意指两个不同的质数；若允许两数相同，则需额外说明。

第 11 题（单选题，2 分）

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

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

正确答案A

解析详情
答案 A二叉树度数关系
思路与推导

  1. 设有两个孩子的结点数为 k，每个这样的结点贡献两条向下的边。10 个结点的树一共只有 9 条边，所以 2k≤92k≤9，得到 k≤4。

  2. 该上界可以实现：4 个双孩子结点、1 个单孩子结点、5 个叶结点共有 10 个结点，因此最多为 4，选 A。

第 12 题（单选题，2 分）

二项展开式(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二项式系数
思路与推导

  1. (x+y)10(x+y)^{10} 可看作 10 个 (x+y) 相乘。要得到 xy9xy^9，必须恰好从一个因子取 x，其余九个都取 y。

  2. 选择这个因子有 (101)=10\binom{10}{1}=10 种，因此系数为 10，选 C。

第 13 题（单选题，2 分）

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

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埃拉托斯特尼筛法
思路与推导

  1. 只有 n 为质数时，才从 n² 开始按 n 的步长标记合数。质数 p 产生的标记次数至多为 N/p。

  2. 对各质数求和，工作量为 N∑p≤N1/p=O(Nlog⁡log⁡N)N\sum_{p≤\sqrt N}1/p=O(N\log\log N)，选 C。从 p² 开始是因为更小倍数已有较小质因子标记。

第 14 题（单选题，2 分）

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

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递归欧几里得算法
思路与推导

  1. 每次把 (m,n) 变为 (n%m,m)，利用 gcd⁡(m,n)=gcd⁡(n mod m,m)\gcd(m,n)=\gcd(n\bmod m,m)，直到第一个参数为 0。

  2. 余数不断减小，至多每两轮至少缩小一半，递归深度为对数级。按正整数输入和常数时间取模的惯例，选择 O(log⁡n)O(\log n)，即 B。

第 15 题（单选题，2 分）

下面程序的输出为（）。

#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对称计数
思路与推导

  1. 所有三元组共有 113=133111^3=1331 个。将 (x,y,z) 映射为 (10−x,10−y,10−z)，总和 s 对应 30−s，所以总和小于 15 与大于 15 的数量相同。

  2. 总和恰为 15 的方案数为 (172)−3(62)=136−45=91\binom{17}{2}-3\binom{6}{2}=136-45=91。

  3. 因此总和不超过 15 的方案数为 (1331+91)/2=711(1331+91)/2=711，选 D。

判断题

第 1 题（判断题，2 分）

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

正确答案正确

解析详情
答案 正确相邻排列捆绑法
思路与推导

  1. 先把 A、B 看成一个整体，与 C、D、E 共四个单位，排列有 4!=244!=24 种。

  2. 整体内部可排 AB 或 BA，另有 2 种选择，总数为 24×2=4824×2=48，所以正确。

第 2 题（判断题，2 分）

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

正确答案错误

解析详情
答案 错误浮点数精度
思路与推导

  1. 在精确实数运算中，三次加减可实现交换，但 double 的有效精度有限，a+b 可能发生舍入。

  2. 例如 a=1e20、b=1 时，a+b 可能仍被存为 1e20；后续计算会使 a 变为 0，无法恢复原来 b 的值 1。

  3. 因此不能保证交换成功，应使用临时变量或 swap。

第 3 题（判断题，2 分）

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

正确答案正确

解析详情
答案 正确有放回的乘法原理
思路与推导

  1. 取后放回意味着每一步红、蓝都仍可能出现，不存在球数耗尽。

  2. 三次分别有 2 种颜色选择，共 23=82^3=8 种，判断正确。各种序列出现的概率未必相同，但都可能出现。

第 4 题（判断题，2 分）

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

正确答案正确

解析详情
答案 正确勾股定理
思路与推导

  1. 两条直角边为 a、b 时，斜边 c 满足 c2=a2+b2c^2=a^2+b^2。长度取非负值，所以 c=a2+b2c=\sqrt{a^2+b^2}，对应题中表达式。

  2. 例如 a=3、b=4，结果为 5。实际编码还需防止 int 乘法溢出，可先转换为 double 或更宽整数。

第 5 题（判断题，2 分）

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

正确答案正确

解析详情
答案 正确Dijkstra 实现复杂度
思路与推导

  1. 在边权非负的适用前提下，朴素 Dijkstra 每轮扫描 v 个顶点选最小距离，共 v 轮，耗时 O(v2)O(v^2)。

  2. 利用支持高效 decrease-key 的 Fibonacci 堆，可将摊还复杂度改进为 O(e+vlog⁡v)O(e+v\log v)，因此题目所述优化可以实现。普通二叉堆通常是 O((v+e)log⁡v)O((v+e)\log v)。

第 6 题（判断题，2 分）

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

正确答案错误

解析详情
答案 错误二叉排序树退化
思路与推导

  1. 若依次插入 1、2、3、…、N，普通二叉排序树会形成只有右孩子的一条链。

  2. 查找最大值 N 需沿链比较 N 次，因此最坏为 O(N)O(N)，题目所说 O(log⁡N)O(\log N) 错误。

第 7 题（判断题，2 分）

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

正确答案错误

解析详情
答案 错误析构函数
思路与推导

  1. 在本题采用的常规 C++ 类模型中，析构函数名为

  2. 类名，不接收参数，也不能通过不同参数列表重载。

  3. 例如同一类同时定义两个

  4. A() 会重复定义，所以题目说可以定义多个析构函数错误。

第 8 题（判断题，2 分）

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

正确答案正确

解析详情
答案 正确链表顺序查找
思路与推导

  1. 单链表和双向链表都不能按下标常数时间随机访问。查找指定值时，都可能逐个比较到链尾。

  2. 因此两者通常的最坏查找复杂度均为 O(n)O(n)。双向链表便于反向移动或删除已知结点，但不改变普通查找的数量级。

第 9 题（判断题，2 分）

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

正确答案错误

解析详情
答案 错误二级哈希冲突
思路与推导

  1. 把发生冲突的元素再分配到子哈希表，只是又进行了一次哈希，不自动保证新映射互不冲突。

  2. 例如两个不同关键字在第二层仍可能得到同一余数。只有进一步选择、验证合适的函数及容量，才能构造无冲突子表，所以“一定不会”错误。

第 10 题（判断题，2 分）

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

正确答案错误

解析详情
答案 错误DFS 与 BFS 复杂度
思路与推导

  1. 在相同邻接表存储下，DFS 和 BFS 都要访问顶点并扫描相邻边，完整遍历的复杂度均为 O(V+E)O(V+E)。

  2. 二者访问顺序和辅助空间组织不同：DFS 使用栈，BFS 使用队列，但不能据此断言 DFS 的平均时间复杂度更低。