GESP 2026年9月 C++ 七级真题,答案与知识点解析

答案：C

知识点解析

本题考查按位与、按位或运算。将 5 写成二进制 101，3 写成 011：按位与得 001（即 1），按位或得 111（即 7），输出为 1 + 7 = 8。这里用到了恒等式 a + b = (a & b) + (a | b)：与运算是“公共部分只算一次”，或运算是“合并部分都算一次”，两者相加恰好等于 a + b = 8。选项 B（7）只是 a|b 的中间结果，选项 A（6）恰为 a^b = 101^011 = 110 的值，均不是最终答案。

答案：D

知识点解析

本题考查 cmath 数学库函数的参数含义与返回值类型。pow(2, 3) 和 sqrt(4) 的返回值类型都是 double 而非 int，故 A、C 错误；sin、cos 等三角函数的参数是弧度而不是角度，传入 30 表示 30 弧度，B 错误；log 是自然对数，log(1) = ln 1 = 0.0，且所有浮点函数返回值类型均为 double，D 正确。

答案：C

知识点解析

本题考查哈夫曼树的构造过程。哈夫曼树每次取出权值（出现次数）最小的两棵树合并：先合并 1 和 2 得 3，再合并 3 和 3 得 6，最后合并 6 和 4 得 10。出现次数为 1 的字符在第一次合并时就与权 2 的字符结合，位于树的最深层，从根到它的路径经过 3 条边，所以编码长度为 3。规律是：越早被合并（权值越小）的叶子越深，编码越长。

答案：B

知识点解析

本题考查组合计数的网格路径模型。4 × 5 个点构成的网格，从左上角走到右下角需要向下 3 步、向右 4 步，共 7 步。路径由这 7 步的排列顺序决定，只需在 7 步中选出哪 3 步向下（其余向右），共有 C(7, 3) = 35 条。选项 C 的 70 = C(8, 4)、D 的 126 = C(9, 4) 分别对应更大的点阵，是把步数算多后的结果。

答案：A

知识点解析

本题考查二叉排序树（BST）的查找效率分析。当树形比较平衡（接近完全二叉树）时，每次比较都能排除一半结点，平均查找长度为 O(log n)；但当插入顺序不当（例如按有序序列依次插入）时，树会退化成一条链，深度为 n − 1，最坏查找需要 O(n)。注意 BST 不像平衡树那样自带平衡机制，所以最坏情形无法保证 O(log n)。

答案：B

知识点解析

本题考查区间 DP 思想（石子合并问题），只能合并相邻两堆。每合并一次，代价为两堆之和，等价于每堆石子在每次包含它的合并中都被累加一次，因此让“大堆”尽量晚参与合并更优。最优方案：先并 1、2（代价 3），得 3, 3, 4；再并 3、3（代价 6），得 6, 4；最后并 6、4（代价 10），总代价 3 + 6 + 10 = 19。若先合并 3、4（代价 7），总代价为 7 + 3 + 10 = 20（选项 C）。要注意“相邻最小”的贪心只是在本题数据下恰好取得最优解，石子合并的一般情形仍需用区间 DP 求解。

答案：A

知识点解析

本题考查 BFS 在无权图最短路中的应用。BFS 借助队列按“层”扩展：先访问距起点 1 条边的结点，再访问 2 条边的结点……因此每个结点第一次被访问（标记 vis）时，对应的 dist[v] 就是起点到 v 的最少边数。选项 B 的度数、D 的连通块大小与遍历顺序无关，选项 C 涉及“最大边权”，而本图是无权图，边权概念不存在。

答案：D

知识点解析

本题考查搜索的非递归实现。递归 DFS 的“层次”保存在系统调用栈上，网格很大时递归深度可达格子总数，容易栈溢出。改用显式队列（BFS）或显式栈（模拟 DFS），把待访问格子存放在堆上的数据结构中，即可避免递归层数过深的问题。选项 A、B、C 与防止递归过深没有任何关系，属于无关干扰项。

答案：C

知识点解析

本题考查哈希表的冲突处理方法。开放定址法的特点是：所有元素都存放在表内，发生冲突时按探测序列（线性探测、平方探测等）在表内继续寻找下一个可用位置，C 正确。A 错误：无论哈希函数多好，只要 key 的取值空间大于表长，冲突就不可避免；B 错误：链地址法中同一槽位链表过长时查找退化为 O(链长)；D 错误：元素越多装填因子越大，冲突越频繁，查找速度越慢。

答案：B

知识点解析

本题考查引用传参。void inc(int &x) 中的 x 是实参 a 的别名（引用），函数内 x++ 直接修改的就是 main 中的 a，因此调用后 a = 4。如果把参数写成值传递 int x，则函数内修改的是副本，输出仍为 3。选项 D 错误：引用传参是合法的 C++ 语法，不会编译错误。

答案：A

知识点解析

本题考查最长公共子序列（LCS）的状态转移方程。当两序列末位字符相等（a₁[i−1] == a₂[j−1]）时，这对字符可以直接配成 LCS 的最后一个字符，于是 dp[i][j] = dp[i−1][j−1] + 1。选项 B 的 max(dp[i−1][j], dp[i][j−1]) 是字符不相等时的转移；选项 C、D 的转移只消去一个序列的一个字符，没有把相等字符“配对”，会漏掉最优解。

答案：D

知识点解析

本题考查 0/1 背包的一维（滚动数组）优化，核心是容量循环必须倒序。程序中只有一个物品，重量 w = 3、价值 v = 5，背包容量 W = 8。c 从 8 递减到 3：当 c = 8 时，dp[8] = max(dp[8], dp[5] + 5) = 5（此时 dp[5] 还是 0，对应“只放这一个物品”）。倒序枚举保证 dp[c − w] 还是上一行（未考虑本物品）的值，物品不会被重复选取；若正序枚举则变成完全背包，同一物品可放多次。

答案：D

知识点解析

本题考查排序算法的稳定性。稳定排序要求排序后相等元素的相对顺序保持不变：冒泡排序相邻交换时遇到相等元素不交换；插入排序把元素插到相等元素之后；归并排序合并时优先取左半部分元素——三者都是稳定的。快速排序的划分（Partition）过程依赖远距离交换，相等元素可能被交换到彼此之前，因此是不稳定的，最不适宜用于本题要求。

答案：B

知识点解析

本题考查嵌套循环的复杂度分析（调和级数求和）。内层循环 j 从 1 每次 += i，执行次数约为 ⌈n / i⌉，总次数为 n/1 + n/2 + … + n/n = n(1 + 1/2 + … + 1/n)。括号内是调和级数，其和约为 ln n，所以总时间复杂度为 O(n log n)。选项 C 的 O(n²) 是把内层误当作每次都跑满 n 次，选项 D 的 O(n√n) 是另一种常见的错误估计。

答案：C

知识点解析

本题考查指针算术。p = a + 1 使 p 指向 a[1]（值为 3），指针加法按元素个数移动：p + 3 指向 a[1 + 3] = a[4]，其值为 9。容易混淆的是 a[3]（值为 7，选项 B），那是把 p 当作 a 起点算的；实际上 p 已经偏移了 1 个元素。选项 A（5）和 D（11）分别是 a[2] 和 a[5] 的值。

答案：√

知识点解析

本题考查指数函数 exp 的求值与返回类型。exp(x) 计算 e^x，而 e⁰ = 1，所以 exp(0) 的值为 1.0；cmath 中的浮点函数统一返回 double 类型。该说法正确。

答案：×

知识点解析

本题考查开放定址法的删除操作。开放定址法中，后续元素的查找依赖探测序列：若把某位置直接置空，探测遇到空位就会提前判定“元素不存在”，从而截断探测链，导致存放在其后的同义词无法被找到。正确做法是惰性删除——给该位置打上“已删除”标记，查找时跳过但不终止探测。

答案：×

知识点解析

本题考查哈夫曼树的性质。哈夫曼树只保证“频率高的叶子深度不超过频率低的叶子”，即深度与频率成反序关系，但不保证严格更小。反例：四个字符频率为 2、2、3、3 时，合并 2+2 = 4、3+3 = 6、4+6 = 10，四个叶子深度都是 2，频率 3 的叶子并不比频率 2 的更浅。

答案：√

知识点解析

本题考查有向图的度数性质。每条有向边恰好从一个顶点出发（贡献 1 个出度）、进入一个顶点（贡献 1 个入度），因此所有顶点的入度之和与出度之和都等于图的边数 m，二者必然相等。

答案：√

知识点解析

本题考查两种图遍历的实现方式。BFS 要求“先发现的先扩展”，队列的先进先出特性恰好满足；DFS 要求“一条路走到黑再回溯”，递归调用（隐式使用系统栈）或显式栈的后进先出特性恰好满足。该说法正确。

答案：×

知识点解析

本题考查快速排序的复杂度。快排的平均时间复杂度确实是 O(n log n)，但在最坏情形下（如序列已有序而每次又固定取首元素为基准），每次划分只能切出一个元素，递归深度达 n，退化为 O(n²)。正确说法是：最坏时间复杂度为 O(n²)。

答案：√

知识点解析

本题考查 0/1 背包一维优化的枚举方向。二维转移 dp[i][c] 依赖的是第 i − 1 行的 dp[i−1][c − w]，一维化后必须保证更新 dp[c] 时 dp[c − w] 还是“上一行”的旧值。容量从大到小枚举时，dp[c − w] 尚未被本轮更新，正确；若从小到大枚举，同一物品可能被重复选取，就变成完全背包了。

答案：×

知识点解析

本题考查邻接表与邻接矩阵的遍历效率。邻接表只为每个顶点存放其实际拥有的邻边，遍历某顶点全部邻边的时间与该顶点的度数成正比，总遍历为 O(n + m)。与顶点数成正比（O(n)）的是邻接矩阵：即使某顶点只有一条邻边，也要扫描一整行。

答案：√

知识点解析

本题考查完全二叉树的编号性质。层序从 1 开始编号时，结点 i 的左孩子为 2i、右孩子为 2i + 1，反推可知其父结点编号为 ⌊i/2⌋（奇数 i 时为 (i−1)/2，偶数 i 时为 i/2）。这一性质正是二叉堆可以直接用数组存储、通过下标运算访问父子结点的基础。

答案：×

知识点解析

本题考查数组名与指针的区别。虽然两者的数值（地址）相同，但类型不同：arr 是 int[10] 类型（表达式中退化为 int*），而 &arr[0] 是 int*；取 &arr 得到的是 int(*)[10]。实际差异可以体现出来：sizeof(arr) 为 40（整个数组大小），sizeof(&arr[0]) 为 8（一个指针）；且 arr + 1 前进 4 字节，而 (&arr) + 1 前进 40 字节。因此说“总是等价”是错误的。

必经之路

括号序列