一、单选题（每题2 分，共30 分）
题号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
答案 | D | A | B | B | B | B | D | D | A | A | A | D | A | B | C |
1、下列哪一项不是面向对象编程（OOP）的基本特征？
A. 继承(Inheritance)
B. 封装(Encapsulation)
C. 多态(Polymorphism)
D. 链接(Linking)
【答案】D
【考纲知识点】面向对象知识
【详细解析】面向对象编程作为一种主流的编程范式，其基本特征包括封装性、继承性、多态性等，这些特征共同构成了面向对象编程的坚实基础，使得代码更加模块化、可重用和易于维护。
2、为了让Dog类的构造函数能正确地调用其父类Animal的构造⽅法，横线线处应填入（ ）。
A. 
B.
C.
D.
【答案】A
【考纲知识点】类的创建知识
【详细解析】Animal是父类，父类的构造函数里有参数，子类调用的过程中需要传参。
3、代码同上一题，代码animal.speak()执行后输出结果是（ ）。
A. 输出Animal speaks
B. 输出Dog barks
C. 编译错误
D. 程序崩溃
【答案】B
【考纲知识点】类的创建知识
【详细解析】调用dog类的speak方法，输出“Dog barks”。
4、以下Python代码执行后其输出是（ ）。
A. 1 3
B. 3 1
C. 3 3
D. 1 1
【答案】B
【考纲知识点】栈和队列的知识
【详细解析】输出栈顶元素和队首元素。
5、在一个使用列表实现的循环队列中，front表示队头元素的位置（索引），rear表示队尾元素的下一个插入位置（索引），队列的最大容量为maxSize。那么判断队列已满的条件是( )
A. rear == front
B. (rear + 1) % maxSize == front
C. (rear - 1 + maxSize) % maxSize == front
D. (rear - 1) == front
【答案】B
【考纲知识点】队列知识
【详细解析】在循环队列相关知识中，鉴于其具有循环特性，rear和front的值均需对maxSize进行取余运算。当rear的下一个位置与front相等时，则判定该队列已满。
6、在二叉树中，只有最底层的节点未被填满，且最底层节点尽量靠左填充的是（ ）。
A.完美二叉树
B.完全二叉树
C.完满二叉树
D.平衡二叉树
【答案】B
【考纲知识点】树的知识
【详细解析】完全二叉树是指除最后一层外，每一层上的所有节点都有两个子节点，且最后一层上的节点都靠左对齐，只有最底层的节点未被填满，且最底层节点尽量靠左填充。
7、在使用数组表示完全二叉树时，如果一个节点的索引为i（从o开始计数），那么其左子节点的索引通常是( ) 。
A. (i -1)/2
B. i + 1
C. i * 2
D. 2 * i + 1
【答案】D
【考纲知识点】树的知识
【详细解析】此题中完全二叉树的根节点编号是0，其左孩子编号是2i+1，右孩子编号是2i+2，其中i是当前节点的索引。
8、已知一棵二叉树的前序遍历序列为GDAFEMHZ， 中序遍历序列为ADFGEHMZ，则其后序遍历序列为（ ）。
A. ADFGEHMZ
B. ADFGHMEZ
C. AFDGEMZH
D. AFDHZMEG
【答案】D
【考纲知识点】树的知识
【详细解析】已知⼀棵⼆叉树的前序遍历序列为GDAFEMHZ ，中序遍历序列为ADFGEHMZ，则其后序遍历序列为AFDHZMEG。根据前序遍历序列GDAFEMHZ，可知根节点为G；再根据中序遍历序列ADFGEHMZ，可知G的左子树为ADFE，右子树为HMZ。接着，在前序遍历序列中找到ADFE对应的子序列DAFE，可知A为G的左孩子，DAFE为A的右子树。在中序遍历序列中找到A的右子树DFE，可知D为A的右孩子，FE为D的右子树。以此类推，可以得到整棵二叉树的结构，然后对其进行后序遍历，即可得到后序遍历序列为AFDHZMEG。
9、设有字符集{a,b, c, d, e} ，其出现频率分别为{5, 8, 12, 15, 20} ，得到的哈夫曼编码为（ ）。
A. 
B.
C.
D.
【答案】A
【考纲知识点】哈夫曼知识
【详细解析】根据哈夫曼树的构建原则，首先选择出现频率最小的两个字符作为左右子节点构造一个新的节点，其频率为两个子节点频率之和。然后，将新节点与剩余字符节点按照频率从小到大排序，重复上述步骤，直到构造出一棵包含所有字符的哈夫曼树。最后，根据哈夫曼树，从左到右依次遍历每个字符的路径，路径上的左子边记为0，右子边记为1，即可得到每个字符的哈夫曼编码。
10、3位格雷编码中 ，编码 101之后的下一个编码是（ ）。
A. 100
B. 111
C. 110
D. 001
【答案】A
【考纲知识点】格雷码知识
【详细解析】格雷码其显著特点在于相邻的两个码字之间仅有一位二进制位不同。格雷编码可以通过反射法生成。对于n位格雷码，可以从n-1位格雷码推导出来。在3位格雷编码中，编码序列是固定的，且每个连续编码仅有一个位不同。3位格雷编码的完整序列为：000、001、011、010、110、111、101、100。
11、请将下列Python实现的深度优先搜索（DFS）代码补充完整 ，横线处应填入（ ）。
C.
【答案】A
【考纲知识点】树的知识
【详细解析】采用深度优先搜索算法对该树进行遍历。依据该树的定义，每个结点至多拥有左、右两个子结点。可先访问根结点，再依次以递归方式访问其左、右子结点。
12、给定一个二叉树，返回每一层中最大的节点值，结果以数组形式返回，横线处应填入（ ）。
【答案】D
【考纲知识点】树的知识
【详细解析】题目要求返回每层节点的最大值，采用队列来存储节点信息。其处理方法为：首先获取队首节点，随后将该节点出队，接着对所获取的节点信息进行判断。选项D 与上述处理步骤相符。
13、下面代码实现一个二叉排序树的插入函数（没有相同的数值），横线处应填入（ ）。
C.
D.
【答案】A
【考纲知识点】树的知识
【详细解析】二叉排序树插入一个元素的过程是首先比较待插入的节点值与当前节点的值，如果待插入的节点值小于当前节点的值，则将待插入的节点插入到当前节点的左子树中；如果待插入的节点值大于当前节点的值，则将待插入的节点插入到当前节点的右子树中。若当前节点的左子树或右子树为空，则直接将待插入的节点作为当前节点的左孩子或右孩子。选项A的描述与上述插入过程相符。
14、以下关于动态规划算法特性的描述 ，正确的是（ ）。
A.子问题相互独立，不重叠
B.问题包含重叠子问题和最优子结构
C.只能从底至顶迭代求解
D.必须使用递归实现 ，不能使用迭代
【答案】B
【考纲知识点】算法知识
【详细解析】动态规划的特点是问题包含重叠子问题和最优子结构，通常自底向上迭代求解，也可以使用递归加记忆化的方式实现。
15、给定n个物品和一个最大承重W的背包，每个物品有一个重量Wuti和价值valli，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过W。关于下面代码，说法正确的是() 。
A.该算法不能处理背包容量为 0的情况
B.外层循环 i遍历背包容量， 内层遍历物品
C.从大到小遍历 w是为了避免重复使用同一物品
D.这段代码计算的是最小重量而⾮最大价值
【答案】C
【考纲知识点】动态规划知识
【详细解析】01背包问题要求W必须从大到小遍历，避免一个物品多次使用。
二、判断题（每题2分，共20分）
题号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
答案 | × | × | √ | √ | × | √ | √ | × | √ | √ |
1、构造函数只能⾃动不可以被⼿动调用。
【答案】错误
【考纲知识点】面向对象知识
【详细解析】构造函数是可以手动调用的，通常在需要重置对象状态或显式初始化父类时手动调用。
2、给定一组字符及其出现的频率 ，构造出的哈夫曼树是唯一的。
【答案】错误
【考纲知识点】哈夫曼知识
【详细解析】哈夫曼树可能产生不同的树结构，不同的树结构具有相同的带权路径长度。
3、为了实现一个队列 ，使其出队操作（ pop）的时间复杂度为O(1)并且避免数组删除首元素的O(n)问题 ，一种常见且有效的⽅法是使用环形数组 ，通过调整队首和队尾指针来实现。
【答案】正确
【考纲知识点】队列知识
【详细解析】环形数组实现队列，入队和出队的时间复杂度都是O(1)，并且能够有效利用空间，是一种常用的实现方式。
4、对一棵从小到大的二叉排序树进行中序遍历 ，可以得到一个递增的有序序列。
【答案】正确
【考纲知识点】数据结构知识
【详细解析】中序遍历的顺序是先遍历左子树，然后访问根节点，最后遍历右子树。在二叉排序树（也称为二叉搜索树）中，左子树上的所有节点的值都小于根节点的值，而右子树上的所有节点的值都大于根节点的值。因此，按照中序遍历的顺序访问二叉排序树的节点，可以得到一个递增的有序序列。
5、如果二叉搜索树在连续的插入和删除操作后，所有节点都偏向一侧，导致其退化为类似于链表的结构 ，这时其查找、插入、删除操作的时间复杂度会从理想情况下的O(logn)退化到O(nlogn)。
【答案】错误
【考纲知识点】数据结构知识
【详细解析】如果二叉搜索树退化成链表的话，查找、插入、删除操作相当于在一维数组结构中操作，时间复杂度是O(n)。
6、执行下列代码，my_dog.name 的最终值是Charlie。
【答案】正确
【考纲知识点】面向对象知识
【详细解析】可以对name赋值，是正确的。
7、下列python代码可以成功执行，并且子类Child的实例能通过其成员函数访问父类Parent的属性value。
【答案】正确
【考纲知识点】面向对象知识
【详细解析】父类的value能被子类访问。
8、下列代码中的 tree列表，表示的是一棵完全二叉树( -1 代表空节点)按照层序遍历的结果。
【答案】错误
【考纲知识点】树的知识
【详细解析】完全二叉树是指除最后一层外，每一层上的所有节点都有两个子节点，且最后一层上的节点都靠左对齐，只有最底层的节点未被填满，且最底层节点尽量靠左填充。-1不应该在向量的中间。
9、在树的深度优先搜索（DFS）中，可以使用栈作为辅助数据结构以实现“先进后出” 的访问顺序。
【答案】正确
【考纲知识点】树的知识
【详细解析】在树的DFS中，一般用栈存储访问的树的结点。栈的特点是“先进后出”。
10、下面代码采用动态规划求解零钱兑换问题：给定种硬币，第 i 种硬币的面值为coins[i − 1] ，目标金额为 amt ，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量 ；如果不能凑出目标金额，返回 -1。
【答案】正确
【考纲知识点】动态规划知识
【详细解析】n种硬币，每种硬币可以无限使用，是经典的完全背包问题。
三、编程题 （每题25分，共50分）
1、编程题1
试题名称：学习小组
时间限制：3.0 s
内存限制：512.0 MB
题目描述
班主任计划将班级里的n名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。观察发现，如果 一个学习小组中恰好包含k名同学，则该学习小组的讨论积极度为ak。
给定讨论积极度a1, a2,… , an，请你计算将这n名同学划分为学习小组的所有可能方案中，讨论积极度之和的最大值。
输入格式
第一行，一个正整数n，表示班级人数。
第二行，n个⾮负整数a1, a2,… , an，表示不同⼈数学习小组的讨论积极度。
输出格式
输出共一行，一个整数，表示所有划分⽅案中，学习小组讨论积极度之和的最大值。
样例
输入样例1
输出样例1
输入样例2
输出样例2
数据范围
对于40%的测试点 ，保证 1 ≤ n ≤ 10。
对于所有测试点，保证1 ≤ n ≤ 1000 ，0 ≤ ai≤ 104。
【题目大意】将n名学生进行分组，要求每位学生都必须被分配到某个小组中，规定一个由k人组成的小组其积极度为ak，需计算出积极度总和的最大值。
【考纲知识点】动态规划知识
【解题思路】在本题中，参数n兼具两个含义，既表示物品的数量，又代表背包的容量。第k个物品的体积为k，价值为ak。由于每种物品可被选用的次数不受限制，能够被使用无数次，因此该问题属于完全背包问题。 本题的要点是熟悉完全背包类型的动态规划求解。
【参考程序】
2、编程题 2
试题名称：最大因数
时间限制：6.0 s
内存限制：512.0 MB
题目描述
给定一棵有109个结点的有根树，这些结点依次以1 , 2,..., 109 编号，根结点的编号为1。对于编号为k ( 2 ≤ k ≤ 109）的结点，其父结点的编号为k的因数中除k以外最大的因数。
现在有q组询问，第i（1 ≤ i ≤ q）组询问给定xi, yi，请你求出编号分别为xi, yi的两个结点在这棵树上的距离。两个结点之间的距离是连接这两个结点的简单路径所包含的边数。
输入格式
第一行，一个正整数q，表示询问组数。
接下来q行，每行两个正整数xi, yi，表示询问结点的编号。
输出格式
输出共q行，每行一个整数，表示结点xi, yi之间的距离。
样例
输入样例1
输出样例1
输入样例2
输出样例2
数据范围
对于60%的测试点，保证1 ≤ xi, yi≤ 1000。
对于所有测试点，保证1 ≤ q≤ 1000，1 ≤xi, yi≤ 109。
【题目大意】在一棵树上，每个节点的祖先被定义为该节点自身以外的最大因数，现需求解树上任意两点之间的距离。 根据数据范围要求，最大因数不包含此数，最小因数不包含1。
【考纲知识点】数学知识
【解题思路】从小到大找到所有的因数，然后从x起，x除以最小的因数得到了x的父亲节点x’“除x本身外最大的因数”，然后x’再除以第二小的因数得到x’的父亲节点。在此期间，统计因数的个数，相加即可得到结果。注意是多组测试数据。
【参考程序】
10个月宝宝每天需要喝多少奶粉？