GESP 客观题评测系统

2024-09-Level-7

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

单选题（每题 2 分）

第 1 题（单选题）

已知小写字母 b 的 ASCII 码为 98，下列 C++ 代码的输出结果是（）。

#include <iostream>
using namespace std;
int main() {
    char a = 'b';
    a++;
    cout << a;
    return 0;
}

正确答案B

解析详情

【答案】B

【考点】ASCII 码与字符运算

【解析】 char 变量存的是字符编码，'b' 的 ASCII 码是 98，执行 a++ 后变成 99，对应字符就是 'c'。 cout 输出的是字符本身，因此结果为 c，不是 98 或 99。

【易错点】容易把 char 自增后的输出误当成 ASCII 数值。

第 2 题（单选题）

已知 a 为 int 类型变量，下列表表达式不符合语法的是（）。

&a + 3

+a & 3

a -- 4

a++3

正确答案D

解析详情

【答案】D

【考点】运算符语法

【解析】 a++ 是一个完整的后置自增表达式，后面不能直接再接 3 组成 a++3，所以该写法不合法。 A 是取地址后再做偏移，B 可按 (+a) & 3 解析，C 可按 a-- - 4 解析，语法上都能成立。

【易错点】容易把 a++3 误看成 a + +3，而词法分析并不会这样拆分。

第 3 题（单选题）

下列关于C++语言中指针的叙述，不正确的是（）。

指针变量中存储的是内存地址。

指针变量指向的内存地址不一定能够合法访问。

结构类型中的指针成员不能指向该结构类型。

定义指针变量时必须指定其指向的类型。

正确答案C

解析详情

【答案】C

【考点】指针与自引用结构

【解析】结构体成员完全可以是指向本结构体类型的指针，例如链表结点里的 Node* next，这正是常见写法。 A、B、D 都是指针的基本性质，只有 C 否定了这种自引用结构，因此错误。

【易错点】容易把“结构体中不能直接包含自身对象”和“不能包含指向自身的指针”混为一谈。

第 4 题（单选题）

下列关于 C++ 类的说法，错误的是()。

将C++类对象通过值传递给函数参数时，会自动调用复制构造函数。

将一个类的对象赋值给该类的另一个对象时，不会自动调用构造函数。

定义C++类对象时，一定会调用默认构造函数。

构造派生类的对象时，一定会调用基类的构造函数。

正确答案C

解析详情

【答案】C

【考点】构造函数与对象初始化

【解析】定义类对象时不一定调用默认构造函数，也可能调用有参构造函数或复制构造函数，所以 C 错。按值传参会触发复制构造，派生类对象构造前会先构造基类部分，对象赋值也不是重新构造。

【易错点】容易把“定义对象”一律等同于“无参构造”。

第 5 题（单选题）

某二叉树T的先序遍历序列为：{A B D C E G H F}，中序遍历序列为：{D B A H G E C F}，则下列说法中正确的是（）。

T 的高为 5

T 有 4 个叶节点

T 是平衡树

以上说法都不对

正确答案A

解析详情

【答案】A

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

【解析】由先序和中序可还原出最长路径 A-C-E-G-H，共 5 层，所以树高为 5。这棵树的叶子只有 D、H、F 共 3 个，而且右子树形成长链，不是平衡树，因此只有 A 正确。

【易错点】容易只数边数或把“层数”和“高度”定义混用。

第 6 题（单选题）

一棵完全二叉树有431个结点，则叶结点有多少个？()

176

215

216

255

正确答案C

解析详情

【答案】C

【考点】完全二叉树结点统计

【解析】完全二叉树的叶结点数为 ceil(n/2)，也可写成 floor((n+1)/2)。当 n=431 时，叶结点数为 216，所以选 C。

【易错点】容易把“完全二叉树”误按“满二叉树”公式处理。

第 7 题（单选题）

下列关于树的说法，错误的是（）。

二叉树的中序遍历与其深度优先遍历总是相同的。

所有树都可以构造一颗二叉树与之一一对应。

如果树的一个叶结点有两个不同的祖先结点，那么其中一个一定是另一个的祖先结点。

树的结点不能有两个父结点。

正确答案A

解析详情

【答案】A

【考点】树的遍历与基本定义

【解析】深度优先遍历包含先序、中序、后序等多种方式，中序只是其中一种，不可能“总是相同”，所以 A 错。一般树都能通过孩子兄弟表示法转成二叉树；祖先关系在同一路径上具有传递性；树中每个结点都至多有一个父结点。

【易错点】容易把“深度优先”直接等同于“中序遍历”。

第 8 题（单选题）

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

正确答案B

解析详情

【答案】B

【考点】完全图边数公式

【解析】 10 个结点的完全无向图共有 10×9÷2=45 条边。原图已有 30 条边，还需补 45-30=15 条边，所以选 B。

【易错点】容易把无向图边数按 10×9 计算，忘了每条边被重复计数一次。

第 9 题（单选题）

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

丢弃发生冲突的新元素。

用新元素覆盖发生冲突的元素。

用新元素覆盖在冲突位置的下一个位置。

将新元素放置在冲突位置之后的第一个空位。

正确答案D

解析详情

【答案】D

【考点】哈希冲突解决

【解析】发生冲突后继续寻找后面的空位，是开放定址法中的线性探测，能够保留原有元素并插入新元素。直接丢弃或覆盖旧元素都会丢数据，机械地放到“下一个位置”如果仍冲突也不能解决问题。

【易错点】容易把“冲突后换个位置”简化成只移动一格，而忽略继续探测空位。

第 10 题（单选题）

一个迷宫，已知从起点不经过重复结点到达终点的路径有且仅有一条，则下面说法错误的是（）。

可以使用深度优先搜索找到这条路径。

可以使用广度优先搜索找到这条路径。

该迷宫内与起点连通的结点，一定也与终点连通。

该迷宫内与起点连通的结点及它们之间的路径可以抽象为无向无环图。

正确答案D

解析详情

【答案】D

【考点】图搜索与连通性

【解析】从起点到终点只有一条不重复结点的路径，并不等于整个连通部分无环；环完全可能挂在主路径某个点上而不影响起终点间唯一路径。 DFS、BFS 都能找到这条路，而在同一连通块中的结点既然与起点连通，也一定能通过连通块到达终点。

【易错点】容易把“起点到终点路径唯一”误判成“整个图是一棵树”。

第 11 题（单选题）

下面程序的输出为（）。

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    cout << (int)log(8) << endl;
    return 0;
}

无法通过编译。

正确答案A

解析详情

【答案】A

【考点】数学函数与类型转换

【解析】 cmath 中的 log 是自然对数，log(8) 约等于 2.079。强制转换为 int 会截去小数部分，得到 2，因此输出 A。

【易错点】容易把 log 当成以 2 或 10 为底的对数。

第 12 题（单选题）

下面程序的输出为（）。

#include <iostream>
#define N 10
using namespace std;
int path[N][N];
int main() {
    for (int i = 1; i < N; i++)
        path[i][0] = i;
    for (int j = 1; j < N; j++)
        path[0][j] = j;
    for (int i = 1; i < N; i++)
        for (int j = 1; j < N; j++)
            path[i][j] = path[i - 1][j] + path[i][j - 1];
    cout << path[8][4] << endl;
    return 0;
}

495

1012

结果是随机的。

正确答案C

解析详情

【答案】C

【考点】动态规划表递推

【解析】数组是全局变量，初值为 0，再把第一行和第一列分别设成 1 到 9。随后按 path[i][j]=path[i-1][j]+path[i][j-1] 递推，算到 path[8][4] 的结果是 1012，所以选 C。

【易错点】容易忽略全局数组默认初始化为 0，从而误以为结果随机。

第 13 题（单选题）

上题中程序的时间复杂度为（）。

O(1)

O(N)

O(N \log N)

O(N^{2})

正确答案D

解析详情

【答案】D

【考点】循环复杂度分析

【解析】初始化两条边界各是 O(N)，核心部分是两层从 1 到 N-1 的嵌套循环，共执行约 N^2 次。主导项来自双重循环，所以总时间复杂度是 O(N^2)。

【易错点】容易只看到几段顺序循环，漏掉真正主导开销的二维递推。

第 14 题（单选题）

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

int fib_rcd[MAX_N];
int fib(int n) {
    if (n <= 1)
        return 1;
    if (fib_rcd[n] > 0)
        return fib_rcd[n];
    return fib(n - 1) + fib(n - 2);
}

O(n)

O(\phi^{n}), \phi = \frac{\sqrt{5}-1}{2}

O(2^{n})

无法正常结束。

正确答案B

解析详情

【答案】B

【考点】递归复杂度

【解析】代码只检查 fib_rcd[n]，却没有把新算出的结果写回去，所以记忆化实际上没有生效。递推仍近似满足 T(n)=T(n-1)+T(n-2)，时间复杂度是指数级；在给定选项中应选更精确的 B，而不是 D。

【易错点】容易看到记录数组就直接判断成线性复杂度，却没检查是否真的写入缓存。

第 15 题（单选题）

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

1, 3, 5, 7, 4, 2, 6, 8, 9

9, 4, 2, 1, 3, 7, 5, 6, 8

1, 3, 5, 7, 6, 8, 9, 4, 2

9, 4, 7, 2, 1, 3, 5, 6, 8

正确答案A

解析详情

【答案】A

【考点】广度优先遍历

【解析】需结合图片确认。按图中有向边从 1 出发，第一层可以到 3、5；再由 3 扩展出 7、4、2，因此序列 1,3,5,7,4,2,6,8,9 可以作为某种邻接访问顺序下的 BFS 结果。其余选项把更深层结点提前，或与图中的可达方向不符，所以不可能。

【易错点】容易把同层结点的访问先后看成固定不变，或忽略边的方向。

判断题（每题 2 分）

第 1 题（判断题）

表达式 'a' << 1 的结果为 'a'。

正确答案错误

解析详情

【答案】错误

【考点】位运算与字符类型

【解析】字符 'a' 的编码是 97，表达式 'a' << 1 会先按整数参与左移，得到 194，而不是字符 'a'。左移运算改变的是二进制位，不会保持原字符不变。

【易错点】容易把字符字面量当成“只能得到字符”的值，忽略它本质上也能参与整数运算。

第 2 题（判断题）

在 C++ 语言中，函数可以定义在另一个函数定义之内。

正确答案错误

解析详情

【答案】错误

【考点】函数定义规则

【解析】标准 C++ 不允许在一个函数体内部再定义另一个函数。函数可以在类内定义成员函数，也可以声明后在外部实现，但不能写成嵌套函数定义。

【易错点】容易把其他语言支持的局部函数写法套到 C++。

第 3 题（判断题）

选择排序一般是不稳定的。

正确答案正确

解析详情

【答案】正确

【考点】排序稳定性

【解析】选择排序每一趟会把最小值直接交换到前面，这次交换可能让相等元素的相对次序发生改变。因此它一般是不稳定排序。

【易错点】容易把“每轮只选最小值”误以为不会影响相等元素顺序。

第 4 题（判断题）

埃氏筛法和欧拉筛法都是使用筛法思想生成素数表的算法，欧拉筛法的时间复杂度更低。

正确答案正确

解析详情

【答案】正确

【考点】筛法复杂度

【解析】埃氏筛法的复杂度通常记为 O(n log log n)，欧拉筛法能做到线性筛，即 O(n)。两者都用“筛去合数”的思想，但欧拉筛在复杂度上更低。

【易错点】容易只记住两者都是筛法，却忽略了重复标记次数不同。

第 5 题（判断题）

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

正确答案错误

解析详情

【答案】错误

【考点】三角函数返回值

【解析】 sin 函数的返回类型确实是 double，但 sin(3θ) 的数值取决于 θ，不给出 θ 就不能确定约为 0.5。命题把“类型正确”和“具体值固定”绑在一起，因此整体是错的。

【易错点】容易看到 sin 结果范围在 -1 到 1 之间，就草率接受某个具体数值。

第 6 题（判断题）

一颗N层的完全二叉树，一定有 $2^{N}-1$ 个结点。

正确答案错误

解析详情

【答案】错误

【考点】完全二叉树与满二叉树

【解析】 N 层满二叉树才一定有 2^N-1 个结点；完全二叉树只要求除最后一层外全满，最后一层可以不满。所以 N 层完全二叉树的结点数不一定恰好等于 2^N-1。

【易错点】容易把“完全二叉树”和“满二叉树”两个概念混淆。

第 7 题（判断题）

一个图，不管是否连通，都可以使用深度优先搜索算法进行遍历。

正确答案正确

解析详情

【答案】正确

【考点】图遍历

【解析】图不连通时，从某个起点做一次 DFS 只能遍历一个连通块。如果把“遍历整个图”理解为对每个未访问结点再补一次 DFS，那么无论图是否连通都可以完成遍历。

【易错点】容易把“一次 DFS”与“DFS 遍历整张图”混成同一个概念。

第 8 题（判断题）

某个哈希表键值 x 为整数， $H(x) = x \% p$ 是常用的哈希函数之一，要求 p 选择素数是因为这样不会产生冲突。（）

正确答案错误

解析详情

【答案】错误

【考点】哈希函数设计

【解析】选素数 p 是为了让取模分布更均匀、减少某些规律数据带来的聚集，但并不能保证完全没有冲突。只要两个不同整数相差 p 的倍数，取模后仍可能落到同一个槽位。

【易错点】容易把“冲突更少”误说成“绝不会冲突”。

第 9 题（判断题）

使用单链表实现队列时，链表头结点作为队首比链表头结点作为队尾更便于操作。

正确答案正确

解析详情

【答案】正确

【考点】链表队列实现

【解析】单链表只能方便地从头结点往后走，因此把头结点作为队首时，出队可直接删除表头，操作更简单。若把头结点当队尾，想在队首出队就需要找到前驱，效率和实现都会变差。

【易错点】容易只考虑入队方向，忽略单链表删除尾部前驱不易获得。

第 10 题（判断题）

一个图中，每个结点表达一个人，连接两个结点的边表达两个结点对应的人相互认识，则这个图可以用来表达社交网络。

正确答案正确

解析详情

【答案】正确

【考点】图的建模

【解析】把人看作结点、把“互相认识”看作边，正是社交网络最常见的图模型之一。后续还可以在这个图上分析好友关系、连通分量和传播路径等问题。

【易错点】容易把图论模型理解得过窄，忽略现实关系网络本就常用图来表示。