试卷解析 · 理解每一步

2024-09-Level-7

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

单选题

第 1 题（单选题，2 分）

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

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

正确答案B

解析详情

答案 BASCII 码与字符运算

思路与推导

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

第 2 题（单选题，2 分）

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

&a + 3

+a & 3

a -- 4

a++3

正确答案D

解析详情

答案 D运算符语法

思路与推导

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

第 3 题（单选题，2 分）

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

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

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

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

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

正确答案C

解析详情

答案 C指针与自引用结构

思路与推导

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

第 4 题（单选题，2 分）

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

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

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

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

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

正确答案C

解析详情

答案 C构造函数与对象初始化

思路与推导

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

第 5 题（单选题，2 分）

某二叉树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 题（单选题，2 分）

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

176

215

216

255

正确答案C

解析详情

答案 C完全二叉树结点统计

思路与推导

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

第 7 题（单选题，2 分）

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

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

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

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

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

正确答案A

解析详情

答案 A树的遍历与基本定义

思路与推导

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

第 8 题（单选题，2 分）

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

正确答案B

解析详情

答案 B完全图边数公式

思路与推导

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

第 9 题（单选题，2 分）

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

丢弃发生冲突的新元素。

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

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

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

正确答案D

解析详情

答案 D哈希冲突解决

思路与推导

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

第 10 题（单选题，2 分）

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

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

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

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

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

正确答案D

解析详情

答案 D图搜索与连通性

思路与推导

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

第 11 题（单选题，2 分）

下面程序的输出为（）。

#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。

第 12 题（单选题，2 分）

下面程序的输出为（）。

#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。

第 13 题（单选题，2 分）

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

O(1)

O(N)

O(N \log N)

O(N^{2})

正确答案D

解析详情

答案 D循环复杂度分析

思路与推导

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

第 14 题（单选题，2 分）

下面 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 题（单选题，2 分）

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

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 结果。
其余选项把更深层结点提前，或与图中的可达方向不符，所以不可能。

判断题

第 1 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误位运算与字符类型

思路与推导

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

第 2 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误函数定义规则

思路与推导

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

第 3 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确排序稳定性

思路与推导

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

第 4 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确筛法复杂度

思路与推导

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

第 5 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误三角函数返回值

思路与推导

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

第 6 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误完全二叉树与满二叉树

思路与推导

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

第 7 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确图遍历

思路与推导

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

第 8 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误哈希函数设计

思路与推导

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

第 9 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确链表队列实现

思路与推导

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

第 10 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确图的建模

思路与推导

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