2023年12月 GESP C++ 7级认证考试真题（含编程操作题部分）
选 单选题（共 15 题，每题 2 分）
定义变量 double x，如果下面代码输入为 $100$，输出最接近( )。
对于下面动态规划方法实现的函数，以下选项中最适合表达其状态转移函数的为( )。
下面代码可以用来求最长上升子序列（LIS）的长度，如果输入是：$5$ $1$ $7$ $3$ $5$ $9$，则输出是( )。
C++ 语言中，下列关于关键字 static 的描述不正确的是( )。
$G$ 是一个非连通无向图，共有 $28$ 条边，则该图至少有( )个顶点。
哈希表长 $31$，按照下面的程序依次输入 $4$ $17$ $28$ $30$ $4$，则最后的 $4$ 存入哪个位置？（ ）
某二叉树 $T$ 的先序遍历序列为：{A B D F C E G H}，中序遍历序列为：{B F D A G E H C}，则下列说法中正确的是( )。
下面代码段可以求两个字符串 $s1$ 和 $s2$ 的最长公共子串（LCS），下列相关描述不正确的是（ ）。
图的广度优先搜索中既要维护一个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历？( )
对关键字序列 {$44$，$36$，$23$，$35$，$52$，$73$，$90$，$58$} 建立哈希表，哈希函数为 $h(k) = k % 7$，执行下面的 Insert 函数，则等概率情况下的平均成功查找长度（即查找成功时的关键字比较次数的均值）为( )。
学生在读期间所上的某些课程中需要先上其他的课程，所有课程和课程间的先修关系构成一个有向图 $G$，有向边 $<U, V>$ 表示课程 $U$ 是课程 $V$ 的先修课，则要找到某门课程 $C$ 的全部先修课下面哪种方法不可行？( )
一棵完全二叉树有 $2023$ 个结点，则叶结点有多少个？( )
用下面的邻接表结构保存一个有向图 $G$ ， InfoType 和 VertexType 是定义好的类。设 $G$ 有 $n$ 个顶点、 $e$ 条弧，则求图 $G$ 中某个顶点 $u$ （其顶点序号为 $k$ ）的度的算法复杂度是( )。
给定一个简单有向图 $G$ ，判断其中是否存在环路的下列说法哪个最准确？( )
从顶点 $v_1$ 开始遍历下图 $G$ 得到顶点访问序列，在下面所给的 $4$ 个序列中符合广度优先的序列有几个？( )
{$v_1$ $v_2$ $v_3$ $v_4$ $v_5$} ，{$v_1$ $v_2$ $v_4$ $v_3$ $v_5$}，{$v_1$ $v_4$ $v_2$ $v_3$ $v_5$}，{$v_1$ $v_2$ $v_4$ $v_5$ $v_3$}
判 判断题（共 10 题，每题 2 分）
小杨这学期准备参加 GESP 的 7 级考试，其中有关于三角函数的内容，他能够通过下面的代码找到结束循环的角度值。( )
小杨在开发画笔刷小程序（applet），操作之一是选中黄颜色，然后在下面的左图的中间区域双击后，就变成了右图。这个操作可以用图的泛洪算法来实现。( )
假设一棵完全二叉树共有 $N$ 个节点，则树的深度为 $\lfloor \log_2 N \rfloor + 1$。( )
给定一个数字序列 $A_1$，$A_2$，$A_3$，...，$A_n$，要求 $i$ 和 $j$（$1 \leq i \leq j \leq n$），使 $A_i + \dots + A_j$ 最大，可以使用动态规划方法来求解。( )
若变量 $x$ 为 double 类型正数，则 log(exp(x)) > log10(x)。( )
简单有向图有 $n$ 个顶点和 $e$ 条弧，可以用邻接矩阵或邻接表来存储，二者求节点 $u$ 的度的时间复杂度一样。( )
某个哈希表键值 $x$ 为整数，为其定义哈希函数 $H(x) = x % p$，则 $p$ 选择素数时不会产生冲突。( )
动态规划只要推导出状态转移方程，就可以写出递归程序来求出最优解。( )
广度优先搜索（BFS）能够判断图是否连通。( )
在 C++ 中，如果定义了构造函数，则创建对象时先执行完缺省的构造函数，再执行这个定义的构造函数。()
编 编程操作题（共 2 题，共 50 分）
试题名称：商品交易
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
市场上共有 $N$ 种商品，编号从 $0$ 至 $N-1$ ，其中，第 $i$ 种商品价值 $v_i$ 元。
现在共有 $M$ 个商人，编号从 $0$ 至 $M-1$ 。在第 $j$ 个商人这，你可以使用你手上的第 $x_j$ 种商品交换商人手上的第 $y_j$ 种商品。每个商人都会按照商品价值进行交易，具体来说，如果 $v_{x_j}>v_{y_j}$，他将会付给你 $v_{x_j}-v_{y_j}$元钱；否则，那么你需要付给商人 $v_{y_j}-v_{x_j}$ 元钱。除此之外，每次交易商人还会收取 $1$ 元作为手续费，不论交易商品的价值孰高孰低。
你现在拥有商品 $a$ ，并希望通过一些交换来获得商品 $b$ 。请问你至少要花费多少钱？（当然，这个最小花费也可能是负数，这表示你可以在完成目标的同时赚取一些钱。）
输入格式
第一行四个整数 $N , M , a , b$，分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证 $0 \le a,b < N$ ，保证 $a \ne b$。
第二行 $N$ 个用单个空格隔开的正整数 $v_0,v_1,…,v_{N-1}$ ，依次表示每种商品的价值。保证 $1≤v_i≤10^9$。
接下来 $M$ 行，每行两个整数 $x_j,y_j$ ，表示在第 $j$ 个商人这，你可以使用第 $x_j$ 种商品交换第 $y_j$ 种商品。保证 $0≤x_j,y_j<N$，保证 $x_j≠y_j$ 。
输出格式
输出一行一个整数，表示最少的花费。特别地，如果无法通过交换换取商品 $b$ ，请输出 No solution。
样例输入 #1
3 5 0 2
1 2 4
1 0
2 0
0 1
2 1
1 2
样例输出 #1
5
样例输入 #2
3 3 0 2
100 2 4
0 1
1 2
0 2
样例输出 #2
-95
样例输入 #3
4 4 3 0
1 2 3 4
1 0
0 1
3 2
2 3
样例输出 #3
No solution
说明/提示
数据范围
对于 30% 的测试点，保证 $N ≤ 10$，$M ≤ 20$。
对于 70% 的测试点，保证 $N ≤10^3$，$M≤10^4$。
对于 100% 的测试点，保证 $N≤10^5$，$M≤2×10^5$。
试题名称：纸牌游戏
时间限制：1.0 s | 内存限制：512.0 MB
题目描述
你和小杨在玩一个纸牌游戏。
你和小杨各有 $3$ 张牌，分别是 $0、1、2$。你们要进行 $N$ 轮游戏，每轮游戏双方都要出一张牌，并按 $1$ 战胜 $0$，$2$ 战胜 $1$，$0$ 战胜 $2$ 的规则决出胜负。第 $i$ 轮的胜者可以获得 $2 \times a_i$ 分，败者不得分，如果双方出牌相同，则算平局，二人都可获得 $a_i$ 分 $(i=1,2,\cdots,N)$。
玩了一会后，你们觉得这样太过于单调，于是双方给自己制定了不同的新规则。小杨会在整局游戏开始前确定自己全部 $n$ 轮的出牌，并将他的全部计划告诉你；而你从第 $2$ 轮开始，要么继续出上一轮出的牌，要么记一次“换牌”。游戏结束时，你换了 $t$ 次牌，就要额外扣 $b_1+\cdots+b_t$ 分。
请计算出你最多能获得多少分。
输入格式
第一行一个整数 $N$，表示游戏轮数。
第二行 $N$ 个用单个空格隔开的非负整数 $a_1,\cdots,a_N$，意义见题目描述。
第三行 $N-1$ 个用单个空格隔开的非负整数 $b_1,\cdots,b_{N-1}$，表示换牌的罚分，具体含义见题目描述。由于游戏进行 $N$ 轮，所以你至多可以换 $N-1$ 次牌。
第四行 $N$ 个用单个空格隔开的整数 $c_1,\cdots,c_N$，依次表示小杨从第 $1$ 轮至第 $N$ 轮出的牌。保证 $c
_i\in{0,1,2}$。
输出格式
一行一个整数，表示你最多获得的分数。
样例输入 #1
4
1 2 10 100
1 100 1
1 1 2 0
样例输出 #1
219
样例输入 #2
6
3 7 2 8 9 4
1 3 9 27 81
0 1 2 1 2 0
样例输出 #2
56
说明/提示
样例解释 1
你可以第 $1$ 轮出 $0$，并在第 $2,3$ 轮保持不变，如此输掉第 $1,2$ 轮，但在第 $3$ 轮中取胜，获得 $2×10=20$ 分；
随后，你可以在第 $4$ 轮中以扣 $1$ 分为代价改出 $1$ ，并在第 $4$ 轮中取得胜利，获得 $2×100=200$ 分。
如此，你可以获得最高的总分 $20+200-1=219$。
数据范围
对于 $30%$ 的测试点，保证 $N\le15$。
对于 $60%$ 的测试点，保证 $N\le100$。
对于所有测试点，保证 $N \le 1,000$；保证 $0 \le a_i,b_i \le 10^6$。