2024年9月 GESP C++ 7级

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

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

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

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

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

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

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

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

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

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

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

下面程序的输出为（ ）。

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

下面程序的输出为（ ）。

#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;
}

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

下面 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);
}

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

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

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

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

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

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

一颗 $n$ 层的完全二叉树，一定有 2n−12^n - 12n−1 个结点。

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

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

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

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

试题名称：小杨寻宝

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

小杨有一棵包含 $n$ 个节点的树，树上的一些节点放置有宝物。

小杨可以任意选择一个节点作为起点并在树上移动，但是小杨只能经过每条边至多一次，当小杨经过一条边后，这条边就会消失。小杨每经过一个放置有宝物的节点就会取得该宝物。

小杨想请你帮他判断自己能否成功取得所有宝物。

输入格式

本题单个测试点内有多组测试数据。输入第一行包含一个正整数 $t$，代表测试用例组数。
接下来是 $t$ 组测试用例。对于每组测试用例，一共 $n+1$ 行。

第一行包含一个正整数 $n$，代表树的节点数。
第二行包含 $n$ 个非负整数 a1,a2,…ana_1, a_2, \dots a_na1​,a2​,…an​，其中如果 ai=1a_i = 1ai​=1，则节点 $i$ 放置有宝物；若 ai=0a_i = 0ai​=0，则节点 $i$ 没有宝物。
之后 $n-1$ 行，每行包含两个正整数 xi,yix_i, y_ixi​,yi​，代表存在一条连接节点 xix_ixi​ 和 yiy_iyi​ 的边。

输出格式

对于每组测试数据，如果小杨能成功取得所有宝物，输出 Yes，否则输出 No。

样例输入 #1

2
5
0 1 0 1 0
1 2
1 3
3 4
3 5
5
1 1 1 1 1
1 2
1 3
3 4
3 5

样例输出 #1

Yes
No

说明/提示

样例 1 解释

对于第一组测试用例，小杨从节点 $2$ 出发，按照 $2-1-3-4$ 的顺序即可成功取得所有宝物。

数据规模与约定

对全部的测试点，保证 $1\le t\le 10$，1≤n≤1051 \leq n \leq 10^51≤n≤105，0≤ai≤10 \leq a_i \leq 10≤ai​≤1，且保证树上至少有一个点放置有宝物。

试题名称：矩阵移动

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

小杨有一个 $n\times m$ 的矩阵，仅包含 01? 三种字符。矩阵的行从上到下编号依次为 $1,2,\dots ,n$，列从左到右编号依次为 $1,2,\dots ,m$。小杨开始在矩阵的左上角 $(1,1)$，小杨只能向下或者向右移动，最终到达右下角 $(n,m)$ 时停止，在移动的过程中每经过一个字符 1 得分会增加一分（包括起点和终点），经过其它字符则分数不变。小杨的初始分数为 $0$ 分。

小杨可以将矩阵中不超过 $x$ 个字符 ? 变为字符 1。小杨在修改矩阵后，会以最优的策略从左上角移动到右下角。他想知道自己最多能获得多少分。

输入格式

第一行包含一个正整数 $t$，代表测试用例组数，接下来是 $t$ 组测试用例。对于每组测试用例，一共 $n+1$ 行。

第一行包含三个正整数 $n,m,x$，含义如题面所示。
之后 $n$ 行，每行一个长度为 $m$ 的仅含 01? 的字符串。

输出格式

对于每组测试用例，输出一行一个整数，代表最优策略下小杨的得分最多是多少。

样例输入 #1

2
3 3 1
000
111
01?
3 3 1
000
?0?
01?

样例输出 #1

4
2

说明/提示

样例 1 解释

对于第二组测试用例，将 $(2,1)$ 或者 $(3,3)$ 变为 $1$ 均是最优策略。

数据规模与约定

对全部的测试数据，保证 $1\le t\le 10$，$1\le n,m\le 500$，$1\le x\le 300$，保证所有测试用例 $n\times m$ 的总和不超过 2.5×1052.5 \times 10^52.5×105。