GESP 客观题评测系统

2024-03-Level-7

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

单选题（每题 2 分）

第 1 题（单选题）

下列关于排序的说法，正确的是()。

冒泡排序是最快的排序算法之一。

快速排序通常是不稳定的。

最差情况，N个元素做归并排序的时间复杂度为O(N)。

以上均不正确。

正确答案B

解析详情

【答案】B

【考点】排序算法性质

【解析】快速排序按基准值分区时会把相等元素交换到两侧，通常不稳定，所以 B 正确。归并排序最差仍是 O(N log N)，冒泡排序也不是“最快”算法之一。

【易错点】把“平均速度快”和“稳定性”混为一谈，容易误判快速排序。

第 2 题（单选题）

下面的程序属于哪种算法()。

int pos[8];
void queen(int n) {
    for (int i = 0; i < 8; i++) {
        pos[n] = i;
        bool attacked = false;
        for (int j = 0; j < n; j++)
            if (pos[n] == pos[j] || pos[n] + n == pos[j] + j || pos[n] - n == pos[j] - j) {
            attacked = true;
            break;
        }
        if (attacked)
            continue;
        if (n == 7) {
            return;
        } else {
            queen(n + 1);
        }
    }
}

贪心算法

动态规划

深度优先搜索

广度优先搜索

正确答案C

解析详情

【答案】C

【考点】回溯与深度优先搜索

【解析】代码按行依次给 8 个皇后试列号，若不冲突就递归处理下一行 `queen(n + 1)`，冲突则回退继续试别的位置。这是沿一条分支不断深入、失败再回退的典型 DFS/回溯。

【易错点】看到“逐个尝试”就选贪心，但这里并没有局部最优决策。

第 3 题（单选题）

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

C++类对象销毁时，会执行析构函数。

C++类可以通过定义构造函数实现自动类型转换。

C++类可以通过重载[]运算符实现通过给定下标访问数组成员的元素。

C++类可以包含任意类型的成员变量。

正确答案D

解析详情

【答案】D

【考点】C++ 类与运算符重载

【解析】 A、B、C 都是 C++ 类的常见能力；D 说“任意类型”过于绝对，例如成员不能是 `void` 类型，也不能直接声明函数类型成员，因此 D 错误。

【易错点】题目问的是“错误的是”，不要因为前三项都熟悉就忽略 D 中的绝对化表述。

第 4 题（单选题）

一个连通的简单无向图，共有28条边，则该图至少有( )个顶点。

正确答案C

解析详情

【答案】C

【考点】简单图边数上界

【解析】有 n 个顶点的简单无向图最多有 n(n-1)/2 条边。要容纳 28 条边，需满足 n(n-1)/2 >= 28；7 个点最多 21 条，8 个点最多 28 条，所以至少要 8 个顶点。

【易错点】 “连通”只给下界，不会让最多边数超过简单图公式。

第 5 题（单选题）

以下哪个方案不能合理解决或缓解哈希表冲突（）。

在每个哈希表项处，使用单链表管理该表项的冲突元素。

建立额外的单链表，用来管理所有发生冲突的元素。

使用不同的哈希函数再建立一个哈希表，用来管理所有发生冲突的元素。

用新元素覆盖发生冲突的哈希表项。

正确答案D

解析详情

【答案】D

【考点】哈希冲突处理

【解析】冲突时直接用新元素覆盖旧元素，会把原有键值对丢失，既不能查回旧元素，也不是合法的冲突解决策略。拉链法、溢出区或再次哈希都属于常见缓解方案。

【易错点】把“能插进去”当成“解决冲突”，忽略了原数据是否被保留。

第 6 题（单选题）

已知一颗二叉树的中序遍历序列为： $\{CFBAEDG\}$ ，后序遍历序列为： $\{FCBEGDA\}$ ，则下列说法中正确的是()。

该树是平衡二叉树。

该树的高为4。

该树有4个叶节点。

以上说法都不对。

正确答案B

解析详情

【答案】B

【考点】二叉树重建与性质判断

【解析】后序最后一个 A 是根；由中序 `CFBAEDG` 可分成左子树 `CFB` 和右子树 `EDG`。继续重建得左边是 B-C-F 的链，右边是以 D 为根、左右儿子为 E 和 G，所以最长根到叶路径有 4 个结点，树高为 4。

【易错点】只靠遍历序列“目测”形状，容易误把这棵树当成平衡树或数错叶子数。

第 7 题（单选题）

以下关于二叉排序树的说法，正确的是（）。

二叉排序树的中序遍历序列一定是有序的。

在含 n 个节点的二叉排序树中查找元素，最差情况的时间复杂度为

O(\log(n))

。

二叉排序树一定是二叉平衡树。

以上说法都不对。

正确答案A

解析详情

【答案】A

【考点】二叉排序树性质

【解析】二叉排序树满足“左 < 根 < 右”，因此中序遍历结果一定递增有序。它不一定平衡，极端情况下会退化成链表，此时查找最坏是 O(n)，所以只有 A 正确。

【易错点】把“查找通常较快”误写成“最坏一定是对数复杂度”。

第 8 题（单选题）

已知 x 为 double 类型的变量，且值大于0，则下列表达式的值一定大于0的是()。

sin(x) / x

exp(x) - x

log(x) - x

x * x - x

正确答案B

解析详情

【答案】B

【考点】常见数学函数性质

【解析】对任意 x > 0，都有 e^x > 1 + x > x，因此 `exp(x) - x > 0` 恒成立。A 在 x = π 时为 0，C 在 x = 1 时为 -1，D 在 0 < x < 1 时为负。

【易错点】只代入一个熟悉数值判断，忽略题目要求是“值一定大于 0”。

第 9 题（单选题）

一个简单有向图有10个结点、30条边。再增加多少条边可以成为完全图。（）

正确答案A

解析详情

【答案】A

【考点】完全有向图边数

【解析】 10 个结点的简单完全有向图中，每对不同顶点有两个方向，共 10 × 9 = 90 条边。现有 30 条，还需补 90 - 30 = 60 条。

【易错点】把有向图按无向图计算成 10 × 9 / 2，结果会少一半。

第 10 题（单选题）

下列选项中，哪个可能是下图的深度优先遍历序列（）。

8, 6, 1, 5, 3, 4, 2, 10, 7, 12, 11, 9

7, 8, 6, 4, 2, 1, 5, 3, 12, 9, 11, 10。

8, 10, 12, 9, 11, 4, 5, 3, 2, 1, 6, 7

7, 8, 10, 9, 11, 12, 4, 5, 1, 2, 3, 6。

正确答案C

解析详情

【答案】C

【考点】深度优先遍历序列判断

【解析】深度优先遍历要求先沿一条可行分支走到底，再回溯到最近仍有未访问邻点的结点。结合图中的连边关系，C 可以形成“8 → 10 → 12 → … → 4 → 5 → …”这样的连续深入过程；其余序列都在某处提前跳到尚未回溯到的分支上，需结合图片确认。

【易错点】把“访问过所有点”当成 DFS 充分条件，忽略了回溯顺序也必须合法。

第 11 题（单选题）

下面 schedule 函数的时间复杂度为()。

#include <algorithm>
using namespace std;
struct activity {
    int id, start, end;
};
bool compare(activity a, activity b) {
    return a.end < b.end;
}
int schedule(int n, activity *p) {
    sort(p, p + n, compare);
    int cnt = 0, end = 0;
    for (int i = 0; i < n; i++) {
        if (p[i].start >= end) {
            end = p[i].end;
            cnt++;
        }
    }
    return cnt;
}

O(n)

O(\log(n))

O(n \log(n))

O(n^{2})

正确答案C

解析详情

【答案】C

【考点】时间复杂度分析

【解析】函数先调用 `sort(p, p + n, compare)` 排序，复杂度是 O(n log n)，随后只线性扫描一次活动数组，复杂度 O(n)。总复杂度由排序主导，为 O(n log n)。

【易错点】只看 `for` 循环就选 O(n)，漏掉前面的排序。

第 12 题（单选题）

下面 search 函数的平均时间复杂度为()。

int search(int n, int * p, int target) {
    int low = 0, high = n;
    while (low <= high) {
        int middle = (low + high) / 2;
        if (target == p[middle]) {
            return middle;
        } else if (target > p[middle]) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }
    return -1;
}

O(n)

O(\log(n))

O(1)

可能无法返回

正确答案B

解析详情

【答案】B

【考点】二分查找

【解析】每次循环都把搜索区间缩小到原来的一半左右，比较次数约为 log2(n)，因此平均时间复杂度是 O(log n)。这是典型的二分查找，而不是顺序扫描。

【易错点】看到 `while` 循环就按 O(n) 估计，没有抓住“区间减半”这个关键信息。

第 13 题（单选题）

下面 count_triple 函数的时间复杂度为()。

int count_triple(int n) {
    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++;
    }
}

O(N)

O(N^{2})

O(N^{3})

O(N^{4})

正确答案C

解析详情

【答案】C

【考点】多重循环复杂度

【解析】外层 `a`、中层 `b`、内层 `c` 都在 1 到 n 的量级内变化，最坏情况下三层循环各跑 O(n) 次。判断语句是 O(1)，所以总复杂度为 O(n^3)。

【易错点】把条件 `a + b + c <= n` 当成会少掉一个数量级，其实仍是三重枚举。

第 14 题（单选题）

下面程序的输出为（）。

#include <iostream>
using namespace std;
int down(int n) {
    if (n <= 1)
        return n;
    return down(n - 1) + down(n - 2) + down(n - 3);
}
int main() {
    cout << down(6) << endl;
    return 0;
}

无法正常结束。

正确答案A

解析详情

【答案】A

【考点】递归求值

【解析】由定义可算：down(0)=0，down(1)=1，down(2)=1+0-1=0，down(3)=1，down(4)=2，down(5)=3，down(6)=6。程序能结束，因为参数每次都减小并最终满足 `n <= 1`。

【易错点】很多人默认这是斐波那契变形，忽略了 `down(-1)` 也会直接返回 -1。

第 15 题（单选题）

下面的程序使用邻接矩阵表达的带权无向图，则从顶点0到顶点3的最短距离为（）。

int weight[4][4] = {
    {0, 2, 5, 8},
    {2, 0, 1, 7},
    {5, 1, 0, 4},
    {8, 7, 4, 0}};

正确答案B

解析详情

【答案】B

【考点】最短路径基础

【解析】直接从 0 到 3 的边权是 8；若走 0 → 2 → 3，距离是 5 + 4 = 9；走 0 → 1 → 3，距离是 2 + 7 = 9。最短的是 0 → 1 → 2 → 3，距离 2 + 1 + 4 = 7。

【易错点】看到有直连边就直接选它，没有继续比较经过中间点的路径。

判断题（每题 2 分）

第 1 题（判断题）

祖冲之是南北朝时期杰出的数学家、天文学家，其主要贡献在数学、天文历法和机械制造三方面。他首次将“周率”精算到小数第七位，即在3.1415926和3.1415927之间。

正确答案正确

解析详情

【答案】正确

【考点】信息学史常识

【解析】祖冲之确实把圆周率精确到 3.1415926 和 3.1415927 之间，这是南北朝时期数学成就的代表之一，因此该说法正确。

【易错点】把“祖冲之求圆周率”记成笼统结论，却记不住精确到的小数位数。

第 2 题（判断题）

C++语言中，表达式 2^3 的结果类型为 int、值为 8。（）

正确答案错误

解析详情

【答案】错误

【考点】C++ 运算符含义

【解析】在 C++ 中 `^` 是按位异或，不是乘方运算，所以 `2 ^ 3` 的结果是 1，而不是 8；两个操作数都是整型时结果类型仍是 int。

【易错点】把数学中的幂记号直接套到 C++ 运算符上。

第 3 题（判断题）

一棵有N个节点的完全二叉树，则树的深度为 $\lfloor \log_2(N) \rfloor + 1$ 。（）

正确答案正确

解析详情

【答案】正确

【考点】完全二叉树深度公式

【解析】完全二叉树按层从上到下、从左到右编号后，最深层编号范围对应 2^(h-1) 到 2^h - 1，因此有 N 个结点时深度 h = floor(log2 N) + 1。

【易错点】容易把节点数公式和深度公式混淆，漏掉最后的 `+1`。

第 4 题（判断题）

能用动态规划解决的问题，一般也可以用贪心法解决，但动态规划的效率更高。（）

正确答案错误

解析详情

【答案】错误

【考点】动态规划与贪心比较

【解析】动态规划能解决的问题并不一定满足贪心选择性质，所以很多 DP 问题根本不能用贪心正确求解。即便两者都可用，效率高低也要看具体问题，不能一概而论。

【易错点】把“都在优化问题里常见”误当成两种方法可以互相替代。

第 5 题（判断题）

使用 math.h 或 cmath 头文件中的正弦函数，表达式 $\sin(30)$ 的结果类型为 double、值约为 0.5。（）

正确答案错误

解析详情

【答案】错误

【考点】数学函数与返回值

【解析】 `sin` 的返回类型通常是 double，这部分没问题；但 `sin(30)` 的值这里30是弧度,而不是角度。

【易错点】看到三角函数的参数是弧度单位

第 6 题（判断题）

要求出简单有向图中从顶点 A 到顶点 B 的最短路径，在深度优先搜索和广度优先搜索中选择，广度优先更适合。（）

正确答案正确

解析详情

【答案】正确

【考点】图遍历与最短路

【解析】在无权图中，广度优先搜索按路径长度一层层扩展，第一次到达 B 时得到的就是最少边数路径；深度优先搜索不保证先找到最短路径，所以 BFS 更适合。

【易错点】把 DFS 的“能搜到答案”和 BFS 的“先搜到最短答案”混为一谈。

第 7 题（判断题）

某 N 个表项的哈希表，在发生哈希函数冲突时采用向后寻找空位的方法解决冲突。其查找操作的平均时间复杂度为 $O(1)$ ，即使当该哈希表的每个表项都有元素时，查找操作的平均时间复杂度仍为 $O(1)$ 。（）

正确答案错误

解析详情

【答案】错误

【考点】开放寻址哈希复杂度

【解析】向后找空位属于开放寻址法，装载因子较低时平均查找可近似看作 O(1)。但当表几乎满甚至每个表项都有元素时，探测序列会很长，失败查找最坏可退化到 O(N)，不可能仍保持 O(1)。

【易错点】记住了哈希表“平均 O(1)”这句话，却忽略它依赖装载因子不能过高。

第 8 题（判断题）

动态规划有递推实现和递归实现，有时两种实现的时间复杂度不同。（）

正确答案正确

解析详情

【答案】正确

【考点】动态规划实现方式

【解析】递推版通常按状态表顺序计算；递归版如果没有记忆化，会反复计算重叠子问题，复杂度可能更高。是否相同取决于具体实现，所以“有时不同”是对的。

【易错点】把“状态转移方程相同”误认为两种写法的运行代价一定相同。

第 9 题（判断题）

围棋游戏中，判断落下一枚棋子后是否会提掉对方的子，可以使用泛洪算法来实现。（）

正确答案正确

解析详情

【答案】正确

【考点】泛洪算法应用

【解析】围棋里判断一块棋是否被提掉，本质上是找与该棋连通的同色棋块并检查是否还有气。泛洪/DFS/BFS 都能遍历这片连通块，因此可以用于判断提子。

【易错点】只把泛洪算法用于“染色填充”，忽略它处理连通块的本质。

第 10 题（判断题）

类 B 继承了抽象类 A，但未实现类 A 中的纯虚函数 f，则类 B 不能直接实例化。（）

正确答案正确

解析详情

【答案】正确

【考点】抽象类与继承

【解析】如果 B 继承了抽象类 A，却没有实现纯虚函数 `f`，那么 B 仍然是抽象类。抽象类不能直接创建对象，所以该说法正确。

【易错点】误以为“已经继承”就自动获得了纯虚函数的具体实现。