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

1、在面向对象编程中，类是一种重要的概念。下列关于类的描述中，不正确的是（ ）.

{{ select(1) }}

• 类是一个抽象的概念，用于描述具有相同属性和行为的对象集合。
• 类可以包含属性和方法，属性用于描述对象的状态，方法用于描述对象的行为。
• 类可以被实例化，生成具体的对象。
• 类一旦定义后，其属性和方法不能被修改或扩展。

2、哈夫曼编码是一种数据压缩算法。以下关于哈夫曼编码的描述中，不正确的是（ ）.

{{ select(2) }}

• 哈夫曼编码是一种变长编码，频率高的字符使用较短的编码，频率低的字符使用较长的编码。
• 在构造哈夫曼树时，频率越低的字符离根节点越近，频率越高的字符离根节点越远。
• 哈夫曼编码的生成过程基于贪心算法，每次选择频率最低的两个节点进行合并。
• 哈夫曼编码是一种前缀编码，任何一个字符的编码都不会是另一个字符编码的前缀，因此可以实现唯一解码。

3、以下代码实现了树的哪种遍历方式？（ ）.

{{ select(3) }}

• 前序遍历
• 中序遍历
• 后序遍历
• 层次遍历

4、以下关于完全二叉树的代码描述，正确的是（ ）.

{{ select(4) }}

• 该代码用于判断一棵树是否为满二叉树
• 该代码用于判断一棵树是否为完全二叉树
• 该代码用于判断一棵树是否为二叉搜索树
• 该代码用于计算树的高度

5、以下代码实现了二叉排序树的哪种操作？（ ）.

{{ select(5) }}

• 查找
• 插入
• 删除
• 遍历

6、给定字符集 {A, B, C, D} 的出现频率分别为 {5, 1, 6, 2}，则正确的哈夫曼编码是（ ）.

{{ select(6) }}

• A: 0, B: 100, C: 11, D: 101
• A: 11, B: 100, C: 0, D: 101
• A: 0, B: 101, C: 11, D: 100
• A: 10, B: 101, C: 0, D: 100

7、关于动态规划的描述，正确的是（ ）.

{{ select(7) }}

• 动态规划算法的时间复杂度总是低于贪心算法。
• 动态规划要求问题必须具有最优子结构和重叠子问题两个性质。
• 动态规划通过递归实现时不需要存储中间结果。
• 动态规划的核心思想是将问题分解为互不重叠的子问题。

8、以下代码中，类的构造函数被调用了（ ）次.

{{ select(8) }}

• 1
• 2
• 3
• 0

9、以下代码实现了循环队列的哪种操作？（ ）.

{{ select(9) }}

• 入队
• 出队
• 查看队首元素
• 判断队列是否为空

10、以下代码实现了二叉树的深度优先搜索（DFS），并统计叶子结点的数量，则横线上应填写（ ）.

{{ select(10) }}

• if (node->left) s.push(node->left);
• if (node->left) s.pop(node->left);
• if (node->left) s.front(node->left);
• if (node->left) s.push(node->right);

11、以下代码实现了二叉树的广度优先搜索（BFS），并查找特定值的节点，则横线上应填写（ ）.

{{ select(11) }}

• 
• 
• 
• 

12、以下代码用于生成位格雷编码。横线上应填写（ ）.

{{ select(12) }}

• result.push_back("1" + prev[i]);
• result.push_back("0" + prev[i]);
• result.push_back(prev[i] + "1");
• result.push_back(prev[i] + "0");

13、以下代码实现了 0/1 背包问题的动态规划解法。假设物品重量为 weights[]，价值为 values[]，背包容量为 W，横线上应填写（ ）.

{{ select(13) }}

• dp[i-1][j], values[i-1]
• dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1]
• dp[i][j-1], values[i-1]
• dp[i-1][j - weights[i-1]] + values[i-1], dp[i][j-1]

14、以下代码⽤于检查字符串中的括号是否匹配，横线上应填写（ ）.

{{ select(14) }}

• true
• false
• st.empty()
• !st.empty()

15、关于下面代码，说法错误的是（ ）.

{{ select(15) }}

• 语句 Shape* shapePtr = &circle; 和 shapePtr = &rectangle; 出现编译错误
• Shape 为基类，Circle 和 Rectangle 是派生类
• 通过继承，Circle 和 Rectangle 复用了 Shape 的属性和方法，并扩展了新的功能
• Circle 和 Rectangle 通过重写基类的虚函数 area 和基类指针，实现了运行时多态

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

1、哈夫曼树在构造过程中，每次合并权值最小的两个节点，最终生成的树带权路径长度最小。

{{ select(16) }}

• 对
• 错

2、格雷编码的相邻两个编码之间必须有多位不同，以避免数据传输错误。

{{ select(17) }}

• 对
• 错

3、在树的深度优先搜索（DFS）中，使用队列作为辅助数据结构以实现“先进后出”的访问顺序。

{{ select(18) }}

• 对
• 错

4、以下代码实现的是二叉树的中序遍历。

{{ select(19) }}

• 对
• 错

5、C++ 支持构造函数重载，但默认无参数的构造函数只能有一个。

{{ select(20) }}

• 对
• 错

6、二叉排序树（BST）中，若某节点的左子树为空，则该节点一定是树中的最小值节点。

{{ select(21) }}

• 对
• 错

7、在动态规划解决一维硬币找零问题时，若硬币面额为 [1, 3, 4]，目标金额为 6，则最少需要 2 枚硬币（3+3）。

{{ select(22) }}

• 对
• 错

8、面向对象编程中，封装是指将数据和行为绑定在一起，并对外隐藏实现细节。

{{ select(23) }}

• 对
• 错

9、以下代码创建的树是一棵完全二叉树。

{{ select(24) }}

• 对
• 错

10、栈和队列均可以用双向链表实现，插入和删除操作的时间复杂度为 O(1)。

{{ select(25) }}

• 对
• 错