试卷解析 · 理解每一步

2024-12-Level-7

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

单选题

第 1 题（单选题，2 分）

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

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

正确答案D

解析详情

答案 Dchar 类型提升

思路与推导

'b' 的 ASCII 码是 98，表达式 a + 1 会先把 char 提升为 int，再做加法得到 99。`cout` 此时输出的是整数 99，不是字符 c。

第 2 题（单选题，2 分）

已知 a 为 int 类型变量，p 为 int * 类型变量，下列赋值语句不符合语法的是（）。

+a = *p;

*p = +a;

a = *(p + a);

*(p + a) = a;

正确答案A

解析详情

答案 A左值与右值

思路与推导

`+a` 是对变量 `a` 做一元正号运算，结果是一个临时右值，不能出现在赋值号左边。`*p`、`a`、`*(p+a)` 都表示可写入的存储位置，所以其余三项语法合法。

第 3 题（单选题，2 分）

已知数组 a 的定义 int a[10] = {0};，下列说法不正确的是（）。

语句 a[-1] = 0; 会产生编译错误。

数组 a 的所有元素均被初始化为 0。

数组 a 至少占用 10 个 int 大小的内存，一般为 40 个字节。

语句 a[13] = 0; 不会产生编译错误，但会导致难以预测的运行结果。

正确答案A

解析详情

答案 A数组越界与未定义行为

思路与推导

`a[-1]` 在语法上能通过编译，它等价于对数组首地址之前的内存做访问，只是运行结果未定义。C++ 默认不检查下标是否落在 `0..9`，所以 A 把“越界”误说成“编译错误”。

第 4 题（单选题，2 分）

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

构造函数不能声明为虚函数，但析构函数可以。

函数参数如声明为类的引用类型，调用时不会调用该类的复制构造函数。

静态方法属于类、不属于对象，因此不能使用对象.方法(…)的形式调用静态方法。

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

正确答案C

解析详情

答案 C静态成员函数

思路与推导

静态方法属于类，但 C++ 语法仍允许用 `对象.静态方法()` 调用，本质上还是按类成员函数处理。A、B、D 都是正确表述，所以错误项是 C。

第 5 题（单选题，2 分）

下列关于有向图的说法，错误的是()。

n个顶点的弱连通有向图，最少有n-1条边。

n个顶点的强连通有向图，最少有n条边。

n个顶点的有向图，最多有

n \times (n-1)

条边。

n个顶点的有向完全图，有

n \times (n-1)

条边。

正确答案C

解析详情

答案 C有向图边数上界

思路与推导

题目中的“有向图”未限定为简单有向图时，可以允许自环，此时每个顶点都能连向包括自己在内的 `n` 个顶点，最多是 `n^2` 条边。`n(n-1)` 对应的是无自环的有向完全图，所以 C 错、D 对。

第 6 题（单选题，2 分）

一棵二叉树的每个结点均满足：结点的左子树和右子树，要么同时存在，要么同时不存在。该树有197个结点，则其叶结点有多少个？()

不存在这样的树。

无法确定叶结点数量。

正确答案B

解析详情

答案 B真二叉树性质

思路与推导

每个结点要么有 2 个孩子，要么没有孩子，所以这是典型真二叉树。设内部结点数为 `I`、叶结点数为 `L`，有 `L=I+1`，再由 `L+I=197` 得 `2I+1=197`，所以 `I=98，L=99`。

第 7 题（单选题，2 分）

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

二叉排序树的中序遍历顺序与元素排序的顺序是相同的。

n 个元素的二叉排序树，其高一定为

\lfloor \log_2 n \rfloor

。

自平衡二叉查找树（AVL树）是一种二叉排序树。

任意的森林，都可以映射为一颗二叉树进行表达和存储。

正确答案B

解析详情

答案 B二叉排序树高度

思路与推导

二叉排序树的高度与插入顺序有关：若按有序序列插入，树会退化成链，高度可达 `n-1`，并不固定是 `⌊log2 n⌋`。只有 AVL、红黑树这类平衡搜索树才把高度控制在对数量级。

第 8 题（单选题，2 分）

一个简单无向图有10个结点、6条边。在最差情况，至少增加多少条边可以使其连通？（）

正确答案C

解析详情

答案 C无向图连通分量

思路与推导

要让后续补边数最多，就要先让现有 6 条边尽量“浪费”在少数点上。6 条边正好可以构成 4 个点的完全图 `K4`，其余 6 个点都是孤立点，于是共有 7 个连通分量；把 7 个分量连成一个连通图至少还要 `7-1=6` 条边。

第 9 题（单选题，2 分）

一个哈希表，包括n个位置（分别编号0~∼(n-1)），每个位置最多仅能存储一个元素。该哈希表只有插入元素和查询两种操作，没有删除或修改元素的操作。以下说法错误的是（）。

如果哈希函数取值范围为0~∼(n-1)，且当发生哈希函数碰撞时循环向后寻找空位，则查询操作的最差时间复杂度为O(n)。（“循环向后”指：0向后一位为1，1向后一位为2，……，(n-2)向后一位为(n-1)，(n-1)向后一位为0）

如果哈希函数取值范围为0~∼(n-1)，且当发生哈希函数碰撞时仅循环向后一个位置寻找空位，则查询操作的最差时间复杂度为O(1)。

如果哈希函数取值范围为0~∼(m-1)（m<n），且当发生哈希函数碰撞时仅在m~∼(n-1)的范围内寻找空位，则查询操作的最差时间复杂度为O(n-m)。

查询操作时，如果发现查询元素经哈希函数对应的位置为空位，该查询元素仍可能出现在哈希表内。

正确答案D

解析详情

答案 D开放寻址哈希查询

思路与推导

题目明确只有插入和查询，没有删除；开放寻址插入时一旦遇到空位就会停下并存入，因此探查链不会跨过空位。查询某元素时，如果它的哈希起点位置就是空位，就说明这条探查链根本没开始，该元素不可能已经在表中，所以 D 错。

第 10 题（单选题，2 分）

以下关于动态规划的说法中，错误的是（）。

动态规划方法将原问题分解为一个或多个相似的子问题。

动态规划方法通常能够列出递推公式。

动态规划方法有递推和递归两种实现形式。

递推实现动态规划方法的时间复杂度总是不低于递归实现。

正确答案D

解析详情

答案 D动态规划实现方式

思路与推导

动态规划常见实现有自顶向下记忆化搜索和自底向上递推，两者都可能成立。递推并不一定比递归慢；有时递推少了函数调用开销，有时记忆化只计算被访问到的状态，所以“总是不低于”这个绝对化表述错误。

第 11 题（单选题，2 分）

下面程序的输出为（）。

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

100

无法通过编译。

正确答案B

解析详情

答案 B`exp` 函数与类型转换

思路与推导

`exp(2)` 计算的是 `e^2`，数值约为 `7.389...`，再强制转换成 `int` 时会直接截去小数部分，结果变成 `7`。程序能正常编译，所以输出是 7。

第 12 题（单选题，2 分）

下面程序的输出为（）。

#include <iostream>
#define N 10
using namespace std;
int h[N];
int main() {
    h[0] = h[1] = 1;
    for (int n = 2; n < N; n++)
        for (int j = 0; j < n; j++)
            h[n] += h[j] * h[n - j - 1];
        cout << h[6] << endl;
        return 0;
}

132

1430

16796

结果是随机的。

正确答案A

解析详情

答案 A卡特兰数递推

思路与推导

`h` 是全局数组，未赋值部分会先被初始化为 0。递推式 `h[n] += h[j] * h[n-j-1]` 正是卡特兰数，依次可得 `h2=2，h3=5，h4=14，h5=42，h6=132`，所以输出 132。

第 13 题（单选题，2 分）

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

O(N)

O(N \log N)

O(N^{3/2})

O(N^{2})

正确答案D

解析详情

答案 D双重循环复杂度

思路与推导

外层 `n` 取 `2..N-1`，内层每次执行 `n` 次，因此总次数是 `2+3+...+(N-1)`。这个和约为 `N(N-1)/2`，数量级是 `O(N^2)`。

第 14 题（单选题，2 分）

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

int sieve[MAX_N];
void init_sieve(int n) {
    for (int i = 1; i <= n; i++)
        sieve[i] = i;
    for (int i = 2; i <= n; i++)
        for (int j = i; j <= n; j += i)
            sieve[j] --;
}

O(n)

O(n \log n)

O(n^{2})

无法正常结束。

正确答案B

解析详情

答案 B调和级数复杂度

思路与推导

第一层初始化是 `O(n)`。第二重循环里，固定 `i` 时，`j` 依次取 `i, 2i, 3i...`，大约执行 `n/i` 次，所以总工作量为 `n(1/2+1/3+...+1/n)`，即 `O(n log n)`。

第 15 题（单选题，2 分）

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

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

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

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

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

正确答案A

解析详情

答案 A深度优先遍历

思路与推导

按 A 的前半段可走出 `1→2→3→5→7→8`。但图中从 8 出发只有到 5、9 的边，5 已访问后若继续 DFS，下一步只能到 9，不可能直接跳到 6；若回溯到 3 再去 6，也必须先把 8 的未访问邻点 9 处理完，所以 A 不可能出现。

若两个城市之间既有高铁又有航班，就会对应同一对顶点之间的多条有向边；而简单有向图不允许重边。交通网络当然可以用图表示，但更自然的是一般有向图或带重边的图，不一定是简单有向图。