一、单选题（共15题，每题2分，共30分）
题号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
答案 | C | C | D | A | D | B | A | C | D | B | B | B | C | C | A |
【第1 题】以下关于Python 类继承的代码，执行后输出结果是？（）。
☐ A. 动物叫声 动物叫声
☐ B. 旺财：汪汪汪 咪宝：喵喵喵
☐ C. 旺财：汪汪汪 咪宝（橘色）：喵喵喵
☐ D. 动物叫声 咪宝（橘色）：喵喵喵
【答案】C
【考纲知识点】面向对象编程（继承、方法重写与super的使用）【详细解析】
Dog继承自 Animal，并重写了speak()，因此dog.speak() 输出“旺财：汪汪汪”。Cat同样重写了speak()，并在__init__ 中通过super().__init__(name)调用父类构造方法，再额外保存color，所以cat.speak()输出“咪宝（橘色）：喵喵喵”。因此两部分拼接后的结果对应选项C。
【第2 题】下列代码中，s1.draw()和 s2.draw()能正确运行并输出不同结果的主要原因是（ ）。
☐ A. draw() 是普通成员函数
☐ B. Shape 中的draw() 被声明为虚函数
☐ C. Circle 和Rectangle 中使用了公有继承
☐ D. 对象变量名不同
【答案】C
【考纲知识点】面向对象编程（继承与方法重写）【详细解析】在Python 中没有C++ 那样显式的virtual关键字，但子类继承父类后可以直接重写同名方法。Circle和 Rectangle都继承自Shape，并分别重写了draw()，所以调用s1.draw() 和s2.draw()时会执行各自类中的实现。在给出的四个选项里，最贴近原因的是“使用了继承并进行了重写”，因此选C。
【第3 题】下面的代码在主程序if __name__ == "__main__":中有没有一行会导致运行错误，如果有请找出错误行（）。
☐ A. 第 ① 行
☐ B. 第 ② 行
☐ C. 第 ③ 行
☐ D. 无错误行
【答案】D
【考纲知识点】面向对象编程（属性访问约定与实例成员）【详细解析】代码中的_name 和_age只是以单下划线开头，表示“约定上的受保护成员”，并不是Python语法层面真正不可访问的私有成员。因此第①行获取名字没有问题，第②行生日后年龄加一也没有问题，第③行直接修改cat._name在语法上同样合法，第④行再次输出也能正常执行，所以不存在运行错误。
【第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 和6 后，rear先变为 0，再变为1。此时front = 2，rear = 1，满足 (rear + 1) % 5 = 2 = front，所以队列已满，答案为A。
【第5题】在以下计算机系统应用场景中，最适合使用循环队列的是（ ）。
☐ A. 函数调用过程中，保存局部变量和返回地址
☐ B. 表达式求值中的运算符优先级处理
☐ C. 操作系统中的进程优先级调度（高优先级先执行）
☐ D. 生产者和消费者问题中的共享缓冲区
【答案】D
【考纲知识点】数据结构（队列的应用场景）【详细解析】函数调用和表达式求值通常更适合用栈；高优先级调度更常用优先队列；而生产者和消费者问题中的共享缓冲区需要按照先进先出顺序反复读写，并且会循环复用存储空间，最适合使用循环队列。
【第6 题】在二叉搜索树（BST）中，若中序遍历的序列为{1, 2, 3, 4, 5}，且先序遍历的第一个序列元素为3，则下列说法正确的是（ ）。
☐ A. 该树一定是一棵完全二叉树。
☐ B. 元素4 和5 不可能是兄弟节点。
☐ C. 元素1 所在节点的深度可能大于3（根节点深度为1）。
☐ D. 元素2 一定是元素1 的父节点。
【答案】B
【考纲知识点】数据结构（二叉搜索树的遍历性质）【详细解析】
BST的中序遍历有序，因此根节点3 左边只能是1、2，右边只能是4、5。右子树要么以4 为根、5为其右孩子；要么以5 为根、4为其左孩子，因此4 和5 不会成为兄弟节点，所以B 正确。A不一定成立；C也不可能，因为只有两个更小的数；D也不一定，因为左子树既可能是2 为根，也可能是1 为根。
【第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 D I B E，右子树为F J C G。继续递归划分后，可得左子树后序为H I D E B，右子树后序为J F G C。最后加上根A，整棵树的后序遍历为H I D E B J F G C A，因此选A。
【第8 题】下列关于树的遍历的说法中，正确的一项是（ ）。
☐ A. 对任意一棵树进行深度优先遍历，所得序列一定唯一。
☐ B. 已知一棵二叉树的先序遍历和后序遍历序列，可以唯一确定这棵二叉树。
☐ C.若一棵二叉树的先序遍历序列与中序遍历序列相同，则该二叉树一定为只有右子树的链式结构。
☐ D. 已知一棵二叉树的先序遍历序列，即可唯一地确定该二叉树的结构。
【答案】C
【考纲知识点】数据结构（二叉树遍历性质）【详细解析】若先序遍历与中序遍历完全相同，说明每次访问根之后，左子树部分都为空，否则中序中一定会先出现左子树结点。因此整棵树只能不断向右延伸，形成“只有右子树”的链式结构。A、B、D都不成立：DFS序列与孩子访问顺序有关；仅有先序+后序一般无法唯一确定；仅有先序更无法唯一确定结构。
【第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，因此选D。
【第10 题】对n 个不同符号的符号进行哈夫曼编码。若生成的哈夫曼树共有115 个结点，则n 的值是（）。
☐ A. 60
☐ B. 58
☐ C. 57
☐ D. 56
【答案】B
【考纲知识点】数据结构（哈夫曼树结点数公式）【详细解析】对n 个不同符号构造哈夫曼树时，叶子结点数为n，内部结点数为n-1，因此总结点数为2n-1。由2n-1=115，解得n=58，所以选B。
【第11 题】关于格雷编码（Gray Code），下列说法正确的是（ ）。
☐ A. 格雷编码中，编码位数越多，相邻编码之间变化的位数也越多
☐ B. 格雷编码中，相邻两个编码的二进制位恰好有一位不同
☐ C. 格雷编码就是把普通二进制编码按位取反后得到的结果
☐ D. 格雷编码不能用于数字电路和状态转换的设计中
【答案】B
【考纲知识点】编码理论（格雷编码的性质）【详细解析】格雷编码的核心特点是相邻两个编码只有1 位发生变化，这样可以减少多位同时跳变带来的误差，因此B 正确。A、C、D都与格雷编码的定义和应用不符。
【第12题】给定一棵二叉树，采用广度优先搜索（BFS）算法，返回右视图所有节点的值。其中右视图定义为：二叉树的右视图是从树的右侧看过去时可见的节点集合，即右视图中的每个节点都是某一层中最右侧的节点。
☐ A. （1）depth, depth；（2）0, max_depth
☐ B. （1）depth + 1, depth + 1；（2）0, max_depth + 1
☐ C. （1）depth + 1, depth + 1；（2）1, max_depth + 1
☐ D. （1）depth, depth；（2）1, max_depth
【答案】B
【考纲知识点】数据结构（BFS与二叉树右视图）【详细解析】当前结点位于depth层，它的左右孩子都位于下一层，因此两个入队深度都应为depth + 1。又因为最终需要按层从0 一直到max_depth 依次取出答案，Python中 range的右端不包含，所以应写成range(0, max_depth + 1)。因此选B。
【第13题】下列关于树的深度优先搜索（DFS）的说法中，正确的是（ ）。
☐ A. 对树进行DFS 时，一定是按层从上到下依次访问结点
☐ B. 对任意一棵树进行DFS，得到的遍历序列唯一
☐ C. 对一棵树进行DFS 时，常借助递归或栈实现
☐ D. DFS 只能用于二叉树，不能用于普通树
【答案】C
【考纲知识点】数据结构（深度优先搜索）【详细解析】
DFS的本质是“先一路深入，再回溯”，常见实现方式就是递归或显式栈，因此C 正确。A描述的是层序遍历的特点；B不成立，因为遍历顺序受孩子访问顺序影响；D也不对，DFS可以用于普通树、图等多种结构。
【第14题】小朋友们去邻里拜年，每个家里有不同数量的糖果。规则是：不能连续进入两个相邻的房子（即不能同时取相邻两家的糖果）。目标是拿到最多糖果。以下是代码实现，请补全横线。
☐A. dp[i] = dp[i - 1] + nums[i]
☐ B. dp[i] = max(dp[i - 1], dp[i - 2] * nums[i])
☐ C. dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
☐ D. dp[i] = dp[i - 2] + nums[i]
【答案】C
【考纲知识点】动态规划（线性DP）【详细解析】处理到位置i 时，只有两种选择：不选第i 家，此时收益为dp[i-1]；选第i 家，则上一家不能选，收益为dp[i-2] + nums[i]。因此状态转移应为dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])，选C。
【第15 题】元宵节晚上，小朋友沿着一条发光石板路前进，每次可以向前走1 块或2 块石板。若dp[i] = dp[i - 1] + dp[i - 2]，下面关于dp[i] 的含义最合适的是（ ）。
☐ A. 走到第i 块石板的不同走法数量
☐ B. 走到第i 块石板时，已经走过的石板总数
☐ C. 从第i 块石板走回起点的最少步数
☐ D. 从第i 块石板走回起点的最大步数
【答案】A
【考纲知识点】动态规划（递推状态含义）【详细解析】若到达第i 块石板时只能从第i-1 块走1 步过来，或者从第i-2 块走2 步过来，那么到达第i 块的方案数就是前两项方案数之和，所以dp[i] 表示“走到第i 块石板的不同走法数量”，应选A。
二、判断题（共10题，每题2分，共20分）
题号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
答案 | × | × | × | × | √ | √ | × | √ | × | √ |
【第1 题】下面定义了一个表示二维坐标点的类Point，并提供了一个带参数的构造函数，但第 ② 行Point b；会调用编译器自动生成的默认构造函数，将b.x 和 b.y初始化为 0.0，程序可以正常编译运行。
【答案】错误【考纲知识点】面向对象编程（构造函数）【详细解析】
Python不会像某些语言那样在你自定义了带参__init__ 后，再自动补一个可无参调用的“默认构造函数”。这里Point.__init__ 需要两个参数px 和 py，因此执行Point() 会抛出TypeError，而不会把x 和 y自动初始化为 0.0。
【第2 题】Python中的继承支持单继承和多继承，但子类无法直接访问父类的私有成员。
【答案】正确【考纲知识点】面向对象编程（继承与封装）【详细解析】
Python同时支持单继承和多继承。对于以双下划线开头的私有成员，解释器会进行名称重整，子类不能直接用原名字访问，因此这句话按通常教材语境理解是正确的。
【第3 题】对如下结构的树，执行travel 函数，输出结果是1 2 3 4 5。
【答案】错误【考纲知识点】数据结构（二叉树前序遍历）【详细解析】
栈实现前序遍历时，当前结点出栈后先压右孩子、再压左孩子，这样下一个被处理的是左孩子。因此该代码遍历顺序为1 2 4 5 3，而不是1 2 3 4 5。
【第4 题】若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。
【答案】错误【考纲知识点】数据结构（哈夫曼树）【详细解析】字符频率相同只说明合并时会出现多种等价选择，并不保证最终得到的哈夫曼树一定是完全二叉树。不同的合并顺序可能得到不同形态的最优前缀码树，因此该说法错误。
【第5题】哈夫曼编码是一种变长的前缀编码，在解码时不需要额外的分隔符就能唯一还原，这是因为在哈夫曼树中，任何一个字符的叶子结点都不会成为另一个字符结点的祖先。
【答案】正确
【考纲知识点】数据结构（前缀编码）
【详细解析】
哈夫曼编码满足“前缀码”性质，即任意一个字符的编码都不会是另一个字符编码的前缀。对应到哈夫曼树上，就是任一字符都位于叶子结点，叶子结点不会成为其他字符结点的祖先，所以可以无歧义解码。
【第6题】在Python 中使用列表存储按层序遍历的完全二叉树时，若根节点存储在tree[0]，则对于任意非空节点tree[i]，其右孩子（如果存在）必然位于tree[2 * i + 2]。
【答案】正确【考纲知识点】数据结构（完全二叉树的顺序存储）【详细解析】
对于从0 开始编号的顺序存储完全二叉树，结点i 的左孩子下标是2*i+1，右孩子下标是2*i+2，这是标准性质，因此题目说法正确。
【第7题】在Python中使用列表模拟栈来非递归地实现二叉树的前序遍历，为了保证遍历顺序正确，在处理完当前结点后，应该先将该结点的左孩子压入栈中，然后再将右孩子压入栈中。
【答案】错误【考纲知识点】数据结构（前序遍历的栈实现）【详细解析】
由于栈是后进先出，若想实现“根-> 左 ->右”的前序遍历，就必须先压入右孩子，再压入左孩子。这样左孩子会先出栈、先被访问。所以题干中的压栈顺序说反了。
【第8题】设二叉树共有n 个结点，函数preorderTraversal 的时间复杂度为O(n)，空间复杂度为O(n)。
【答案】正确【考纲知识点】数据结构（二叉树递归遍历复杂度）【详细解析】
每个结点都恰好访问一次，因此时间复杂度是O(n)。结果数组res 需要存储全部n 个结点值，递归调用栈在最坏情况下也可能达到O(n)，所以空间复杂度记为O(n) 是正确的。
【第9 题】以下代码实现了0-1背包问题的一维动态规划解法，内层循环采用经典的逆序遍历方式。若将内层循环改为正序遍历（即for j in range(w[i], W + 1):），仍能得到正确答案。
【答案】错误【考纲知识点】动态规划（0/1背包）
【详细解析】
0/1背包要求每件物品至多使用一次，所以在一维优化时必须让容量j 从大到小枚举。若改成从小到大，就可能在同一轮中重复使用当前物品，转化成“完全背包”的效果，结果就不再正确。
【第10 题】在动态规划问题中，状态空间相同且没有重复计算的情况下，“状态转移方程+ 递推”与“递归+ 记忆化搜索”的时间复杂度通常相同。
【答案】正确【考纲知识点】动态规划（递推与记忆化搜索）【详细解析】
只要两种写法访问到的是同一批状态，并且每个状态都只计算一次，那么总的状态数与每个状态的转移代价是一样的，因此时间复杂度通常相同。它们主要区别在实现风格、递归开销和常数因子。
三、编程题
3.1 编程题1
试题名称：选数
时间限制：1.0 s
内存限制：512.0 MB
3.1.1 题目描述
给定两个包含n个整数的数组a=[a1,...,an]与b=b1,...,bn]。你需要指定若干下标p1<...〈pk(1≤k≤n)使得以下条件成⽴：
1≤pi≤n (1≤i≤k);
Pi+1≥pi+bpi(1≤i<k)。
你需要在满⾜以上条件的前提下最⼤化
，也即最⼤化数组a对应下标的整数之和。
3.1.2 输入格式
第一行，一个正整数n，表示数组长度。
第二行，n个非负整数a1, a2, ..., an，表示数组a。
第三行，n个非负整数b1, b2, ..., bn，表示数组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 ≤ 103。
对于所有测试点，保证2 ≤ n ≤ 105，0 ≤ ai≤ 109，0 ≤ bi≤ 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)。
【参考程序】
