一、单选题（共15题，每题2分，共30分）

第1题 下列关于 C++中类的描述，正确的是（ ）。

☐ A.如果类没有用户声明的构造函数，那么编译器会隐式声明一个默认构造函数

☐ B.类的析构函数可以被重载，一个类可以有多个析构函数

☐ C.类中的所有成员都必须声明为public

☐ D.类和结构体在C++中没有区别，包括默认访问权限也相同

【答案】A【考纲知识点】面向对象编程（类、构造函数、析构函数与访问控制）【详细解析】若类中没有用户声明的构造函数，编译器会隐式声明一个默认构造函数，因此A正确。析构函数不能重载，一个类只能有一个析构函数；类成员可以是public、private或protected；class和struct的主要区别之一是默认访问权限不同：class默认private，struct默认public。

第2题 下列代码中，s1->draw();和s2->draw();输出不同结果的主要原因是（ ）。

☐ A. draw() 是普通成员函数

☐ B. Shape 中的draw()被声明为虚函数

☐ C. Circle 和Rectangle中使用了public继承

☐ D.指针变量名不同

【答案】B【考纲知识点】面向对象编程（虚函数与运行时多态）【详细解析】基类Shape中的draw()被声明为virtual，派生类对其进行了重写。通过基类指针调用draw()时，会根据对象的实际类型在运行时决定调用Circle还是Rectangle类，这正是多态产生的关键原因。

第3题 下面的代码在 main()中有一行会导致编译错误，请找出来。

☐ A.第 ① 行

☐ B.第 ② 行

☐ C.第 ③ 行

☐ D.第 ④ 行

【答案】C【考纲知识点】面向对象编程（封装与访问控制）【详细解析】name被声明在private访问区，只能在类的成员函数内部访问，不能在main()中直接写cat.name = "大橘";。第 ①、②、④ 行调用的是 public成员函数，因此不会因为访问权限而报错。

第4题 游乐园的过山车每次限坐 4人，用循环队列管理排队（容量MAX=5，空一格判满）。下面代码执行后，循环队列是否已满？rear的值是多少？

☐ A.已满，rear = 1

☐ B.未满，rear = 1

☐ C.已满，rear = 2

☐ D.未满，rear = 4

【答案】A【考纲知识点】数据结构（循环队列）【详细解析】初始front=0，rear=0。入队4次后rear依次变为1、2、3、4；出队2次后front变为2；再入队5后rear变为0，入队6后rear变为1。此时front=2，rear=1，满足(rear + 1) % MAX = front，即(1+1)%5=2，所以队列已满。

第5题 在以下计算机系统应用场景中，最适合使用循环队列的是（ ）。

☐ A.函数调用过程中，保存局部变量和返回地址

☐ B.表达式求值中的运算符优先级处理

☐ C.操作系统中的进程优先级调度（高优先级先执行）

☐ D.生产者和消费者问题中的共享缓冲区

【答案】D【考纲知识点】数据结构（队列的典型应用）【详细解析】循环队列非常适合固定容量、反复入队出队的缓冲区场景，例如生产者-消费者模型中的共享缓冲区。A和B常用栈处理；C更适合优先队列，而不是普通循环队列。

第6题 在二叉搜索树（BST）中，若中序遍历的序列为{1, 2, 3, 4, 5}，且先序遍历的第一个元素为3，则下列说法正确的是（ ）。

☐ A.该树一定是一棵完全二叉树。

☐ B.元素4和5不可能是兄弟节点。

☐ C.元素1所在节点的深度可能大于3（根节点深度为1）。

☐ D.元素2一定是元素1的父节点。

【答案】B【考纲知识点】数据结构（二叉搜索树的遍历性质）【详细解析】先序第一个元素为3，说明根节点是3；由中序序列可知左子树是{1,2}，右子树是{4,5}。右子树只有两个结点，必然是一个根加一个孩子，因此4和5不可能同为某个节点的左右孩子，所以不可能是兄弟节点。A、C、D都不一定成立。

第7题 某二叉树共有 10个结点，记为A~J，已知它的先序遍历序列为：A B D H I E C F J G，中序遍历序列为：H D I B E A F J C G，则该二叉树的后序遍历序列是（ ）。

☐ A.H I D E B J F G C A

☐ B.H I D B E J F G C A

☐ C.I H D E B J F G C A

☐ D.H I D E B F J G C A

【答案】A【考纲知识点】数据结构（二叉树遍历的还原）【详细解析】由先序可知根为A；结合中序序列可把整棵树拆成左、右子树，再递归还原结构。最终得到左子树后序为H I D E B，右子树后序为J F G C，整棵树的后序遍历为H I D E B J F G C A。

第8题 下列关于树的遍历的说法中，正确的一项是（ ）。

☐ A.对任意一棵树进行深度优先遍历，所得序列一定唯一。

☐ B.已知一棵二叉树的先序遍历和后序遍历序列，可以唯一确定这棵二叉树。

☐ C.已知一棵二叉树的先序遍历和中序遍历序列，可以唯一确定这棵二叉树。

☐ D.已知一棵二叉树的先序遍历序列，可以唯一确定这棵二叉树。

【答案】C【考纲知识点】数据结构（二叉树的遍历与重建）【详细解析】先序遍历给出根结点顺序，中序遍历给出左右子树的划分，两者结合可以唯一确定一棵二叉树。仅有先序与后序时一般不能唯一确定；仅有先序更不能唯一确定。

第9题 有 6个字符，它们出现的次数分别为{2, 3, 3, 4, 6, 8}，现在用哈夫曼编码为这些字符编码，最小加权路径长度WPL的值为（ ）。

☐ A.58

☐ B.60

☐ C.62

☐ D.64

【答案】D【考纲知识点】数据结构（哈夫曼树与WPL）【详细解析】按哈夫曼构造过程依次合并最小的两个权值：2+3=5，3+4=7，5+6=11，7+8=15，11+15=26。哈夫曼树的最小加权路径长度等于每次合并权值之和，因此WPL = 5 + 7 + 11 + 15 + 26 = 64。

第10题 对 n个不同符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是（ ）。

☐ A.60

☐ B.58

☐ C.57

☐ D.56

【答案】B【考纲知识点】数据结构（哈夫曼树结点数）【详细解析】哈夫曼树是一棵满二叉树，若有n个叶子结点，则总结点数为2n-1。由2n-1=115得n=58。

第11题 关于格雷编码（Gray Code），下列说法正确的是（ ）。

☐ A.格雷编码中，编码位数越多，相邻编码之间变化的位数也越多

☐ B.格雷编码中，相邻两个编码的二进制位恰好有一位不同

☐ C.格雷编码就是把普通二进制编码按位取反后得到的结果

☐ D.格雷编码不能用于数字电路和状态转换的设计中

【答案】B【考纲知识点】编码理论（格雷编码）【详细解析】格雷编码的核心性质是相邻两个编码恰好只有1位不同。

第12题 给定一棵二叉树，采用广度优先搜索（BFS）算法，返回右视图所有节点的值。其中右视图定义为：⼆叉树的右视图是从树的右侧看过去时可见的节点集合，即右视图中的每个节点都是某⼀层中最右侧的节点。

☐ A.

☐ B.

☐ C.☐D.

【答案】B【考纲知识点】数据结构（BFS分层遍历）【详细解析】左右孩子都位于当前结点的下一层，因此两个入队的深度都应为depth+1。最终收集答案时，深度从0一直到max_depth，都要被遍历到，所以循环条件应为depth <= max_depth。

第13题 下列关于树的深度优先搜索（DFS）的说法中，正确的是（ ）。

☐ A.对树进行DFS时，一定是按层从上到下依次访问结点

☐ B.对任意一棵树进行DFS，得到的遍历序列唯一

☐ C.对一棵树进行DFS时，常借助递归或栈实现

☐ D.DFS 只能用于二叉树，不能用于普通树

【答案】C【考纲知识点】数据结构（深度优先搜索）【详细解析】DFS的实现方式通常有两种：递归或栈。A描述的是BFS的特点；B不正确，因为访问孩子的先后顺序不同，DFS序列也可能不同；D也不正确，DFS同样适用于普通树和图。

第14题小朋友们去邻里拜年，每个家里有不同数量的糖果。规则是:不能连续进入两个相邻的房子（即不能取相邻两家的糖果)。目标是拿到最多糖果。以下是代码实现，请补全横线。

☐ A.

☐ B.

☐ C.

☐ D.

【答案】C【考纲知识点】动态规划【详细解析】设dp[i]表示考虑前i个房子时能拿到的最多糖果。到第i个房子时有两种选择：不拿它，则答案是dp[i-1]；拿它，则上一个房子不能拿，答案是dp[i-2]+nums[i]。因此转移为dp[i]=max(dp[i-1], dp[i-2]+nums[i])。

第15题 元宵节晚上，小朋友沿着一条发光石板路前进，每次可向前走1块或2块石板。若动态规划定义为dp[i] = dp[i - 1] + dp[i - 2]，则dp[i]最合适的含义是（ ）。

☐ A.走到第i块石板的不同走法数量

☐ B.走到第i块石板时，已经走过的石板总数

☐ C.从第i块石板走回起点的最少步数

☐ D.从第i块石板走回起点的最大步数

【答案】A【考纲知识点】动态规划【详细解析】若每次只能走1步或2步，则到达第i块石板的方案数等于“先到第i-1块再走1步”的方案数与“先到第i-2块再走2步”的方案数之和，因此dp[i]表示到达第i块石板的不同走法数量。

二、判断题（共10题，每题2分，共20分）

第1题 下面定义了一个表示二维坐标点的类Point，并提供了一个带参数的构造函数，但第 ② 行 Point b; 会调用编译器自动生成的默认构造函数，将b.x和b.y初始化为0.0，程序可以正常编译运行。

【答案】错误【考纲知识点】面向对象编程（构造函数）【详细解析】一旦类中已经声明了带参数构造函数，编译器就不会再自动生成无参默认构造函数。代码中的Point b; 需要调用无参构造函数，但类中没有提供，所以程序会编译失败，更不会把b.x和b.y自动初始化为0.0。

第2题C++中的继承支持单继承和多继承，但子类无法直接访问父类的私有成员。

【答案】正确【考纲知识点】面向对象编程（继承与访问权限）【详细解析】C++既支持单继承，也支持多继承。父类的private成员属于封装内容，子类对象不能直接访问，只能通过父类提供的公有或受保护接口间接使用。

第3题 对如下结构的树，执行travel函数，输出结果是1 2 3 4 5。

【答案】错误【考纲知识点】数据结构（二叉树的前序遍历）【详细解析】栈是后进先出。代码先压右孩子、再压左孩子，所以左孩子会先弹出，遍历顺序为“根-左-右”，即1 2 4 5 3，而不是1 2 3 4 5。

第4题 若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。

【答案】错误【考纲知识点】数据结构（哈夫曼树）【详细解析】频率相同只能说明合并时有多种合法选择，但不能保证构造出来的哈夫曼树一定是完全二叉树。哈夫曼树一定是满二叉树（内部结点都有两个孩子），但不一定满足完全二叉树的层次结构要求。

第5题 哈夫曼编码是一种变长的前缀编码，在解码时不需要额外的分隔符就能唯一还原，这是因为在哈夫曼树中，任何一个字符的叶子结点都不会成为另一个字符结点的祖先。

【答案】正确【考纲知识点】数据结构（哈夫曼编码的前缀性质）【详细解析】哈夫曼编码满足“任一码字都不是另一码字的前缀”。在树上看，所有字符对应叶子结点，叶子不可能成为其他叶子的祖先，因此编码串可以从前到后唯一划分和解码。

第6题 在 C++中使用一维数组vector<int> tree 存储按层序遍历的完全二叉树时，若根节点存储在tree[0]，则对于任意非空节点tree[i]，其右孩子（如果存在）必然位于tree[2 * i + 2]。

【答案】正确【考纲知识点】数据结构（完全二叉树的顺序存储）【详细解析】完全二叉树按层序从0开始存储时，结点i的左孩子下标是2*i+1，右孩子下标是2*i+2。这是顺序存储完全二叉树的基本性质。

第7题 在 C++中使用栈来非递归地实现二叉树的前序遍历时，为了保证遍历顺序正确，在处理完当前结点后，应该先将该结点的左孩子压入栈中，然后再将右孩子压入栈中。

【答案】错误【考纲知识点】数据结构（前序遍历的非递归实现）【详细解析】前序遍历顺序是“根-左-右”。由于栈后进先出，想让左孩子先被处理，就必须先压入右孩子，再压入左孩子；若先压左再压右，则右孩子会先出栈，顺序就错了。

第8题 设二叉树共有 n个结点，函数preorderTraversal以下代码的时间复杂度为O(n)，空间复杂度为O(n)。

【答案】正确【考纲知识点】数据结构（二叉树遍历复杂度）【详细解析】每个结点只会被访问一次，因此时间复杂度为O(n)。空间方面，结果数组res需要保存n个结点值，递归栈最坏也可达到O(n)，所以整体写成O(n)是正确的。

第9题 下列代码实现了一个0-1背包的一维动态规划代码，内层循环是经典的逆序写法。若将内层循环改成正序遍历（即for(int j = w[i];j <= W; j++)），仍能得到正确答案。

【答案】错误【考纲知识点】动态规划（0/1背包的一维优化）【详细解析】0/1背包要求每件物品最多使用一次，因此一维优化时容量j必须逆序遍历。若改成正序，dp[j-w[i]]可能已经包含当前物品，等价于允许同一件物品被重复选取，会把问题错误地变成完全背包。

第10题 在动态规划问题中，状态空间相同且没有重复计算的情况下，“状态转移方程+递推”与“递归+记忆化搜索”的时间复杂度通常相同。

【答案】正确【考纲知识点】动态规划（递推与记忆化搜索）【详细解析】当两种写法访问到的状态集合相同、且每个状态只计算一次时，它们完成的状态转移总次数通常一致，因此时间复杂度通常相同。差别主要体现在实现形式、常数开销和调用栈使用上。

三、编程题（每题25分，共50分）

3.1 编程题1

试题名称：选数

时间限制：1.0 s

内存限制：512.0 MB

3.1.1 题目描述

给定两个包含n个整数的数组a=[a₁,...,a_n]与b=b₁,...,b_n]。你需要指定若干下标p₁<...〈p_k(1≤k≤n)使得以下条件成⽴：

1≤p_i≤n (1≤i≤k);

P_i+1≥p_i+b_p(1≤i<k)。

你需要在满⾜以上条件的前提下最⼤化，也即最⼤化数组a对应下标的整数之和。

3.1.2 输入格式

第一行，一个正整数n，表示数组长度。

第二行，n个非负整数a₁, a₂, ..., a_n，表示数组a。

第三行，n个非负整数b₁, b₂, ..., b_n，表示数组b。

3.1.3 输出格式

一行，一个整数，表⽰在满⾜下标条件的前提下，数组a对应下标的整数之和的最⼤值。

3.1.4 样例

3.1.4.1 输入样例1

3.1.4.2 输出样例1

3.1.4.3 输入样例2

3.1.4.4 输出样例2

3.1.5  数据范围

对于40%的测试点，保证2 ≤ n ≤ 10³。

对于所有测试点，保证2 ≤ n ≤ 10⁵，0 ≤ a_i≤ 10⁹，0 ≤ b_i≤ n。

【题目大意】

把每个位置i看成一个“可选点”：若选择了i，就能获得收益a[i]，同时下一个可选位置必须至少到i + b[i]。因此本题本质上是一个按下标从左到右转移的动态规划问题。

【考纲知识点】

动态规划（线性DP / 带跳转的最优选择）

【解题思路】

1.状态定义：设f[i]表示“处理到位置i时，当前能够从位置i继续决策”时的最大收益。

2.跳过当前位置：如果不选i，那么可以直接转移到下一位置，f[i+1] = max(f[i+1], f[i])。

3.选择当前位置：如果选i，则先把a[i]加入答案，之后下一个允许继续选择的位置至少是i + b[i]，于是可转移到f[i + b[i]]。

4.答案更新：在扫描到位置i时，f[i] + a[i] 就表示“最后一个选择是i”的一种合法方案，因此用它更新全局最大值。

5.复杂度分析：每个位置只做常数次转移，总时间复杂度O(n)，空间复杂度O(n)。

3.2 编程题2

试题名称：完全二叉树

时间限制：1.0 s

内存限制：512.0 MB

3.2.1 题目描述

给定一棵包含n个结点的有根二叉树，结点依次以1,2,...,n编号，根结点编号为1。

对于结点i，其左儿子的编号记为l_i，右儿子编号为r_i。特别地，如果左儿子不存在则l_i=0，如果右儿子不存在则r_i=0。树中每个结点都对应一棵以它为根的子树。

树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有n棵子树中，有多少棵子树是完全二叉树。

3.2.2 输入格式

第一行，一个正整数n，表示有根二叉树的结点数量。

接下来n行，每行两个整数l_i, r_i，表示结点i的左儿子编号和右儿子编号。

3.2.3 输出格式

输出一行，一个整数，表示所有子树中完全二叉树的数量。

3.2.4 样例

3.2.4.1 输入样例1

3.2.4.2 输出样例1

3.2.4.3 输入样例2

3.2.4.4 输出样例2

3.2.5 数据范围

对于40%的测试点，保证1 ≤ n ≤ 500。

对于所有测试点，保证1 ≤ n ≤ 10⁵。

【题目大意】

需要对每个结点作为根的子树分别判断是否为完全二叉树。如果每次单独判断会很慢，因此应在一次DFS中自底向上汇总信息，顺便完成所有子树的判断。

【考纲知识点】

树形动态规划、深度优先搜索、完全二叉树判定

【解题思路】

1.观察性质：一棵子树是完全二叉树，当且仅当它的左右子树本身也满足要求，并且所有叶子只会出现在最后两层，同时最后一层的结点尽量靠左。

2.状态设计：对每个结点u，维护chk[u]表示以u为根的子树是否为完全二叉树；mn[u]表示该子树叶子最小深度；mx[u]表示该子树叶子最大深度。

3.先递归处理左右子树，再合并当前结点的信息。若左右子树有任意一个不是完全二叉树，则当前子树也不是。

4.对于完全二叉树，左子树的“最浅叶子深度”不能小于右子树的“最深叶子深度”，否则说明右边出现得比左边更深，不符合“从左到右填充”的规则。

5.同时整棵子树中的最深叶和最浅叶深度之差不能超过1，即mn[u] >= mx[u] - 1。满足以上条件时，chk[u]为真，可将答案加一。

6.复杂度分析：每个结点只会被DFS访问一次，时间复杂度O(n)，空间复杂度O(n)。

【参考程序】

【关于GESP第14次认证】