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

第 1 题 下列关于类的说法，错误的是( )。

{{ select(1) }}

• 构造函数不能声明为虚函数，但析构函数可以。
• 函数参数如声明为类的引用类型，调用时不会调用该类的复制构造函数
• 静态方法属于类而不是某个具体对象，因此推荐用 类名::方法(...) 调用。
• 不管基类的析构函数是否是虚函数，都可以通过基类指针/引用正确删除派生类对象。

第 2 题 假设变量 veh 是类 Car 的一个实例，我们可以调用 veh.move() ，是因为面向对象编程有（ ）性质。

{{ select(2) }}

• 继承 (Inheritance)
• 封装 (Encapsulation)
• 多态 (Polymorphism)
• 链接 (Linking)

第 3 题 下面代码中 v1 和 v2 调用了相同接口 move() ，但输出结果不同，这体现了面向对象编程的（ ）特性。

{{ select(3) }}

• 继承 (Inheritance)
• 封装 (Encapsulation)
• 多态 (Polymorphism)
• 链接 (Linking)

第 4 题 栈的操作特点是（ ）。

{{ select(4) }}

• 先进先出
• 先进后出
• 随机访问
• 双端进出

第 5 题 循环队列常用于实现数据缓冲。假设一个循环队列容量为 5 （即最多存放 4 个元素，留一个位置区分空与满），依次进行操作：入队数据1，2，3，出队1个数据，再入队数据4和5，此时队首到队尾的元素顺序是（ ）。

{{ select(5) }}

• [2, 3, 4, 5]
• [1, 2, 3, 4]
• [3, 4, 5, 2]
• [2, 3, 5, 4]

第 6 题 以下函数 createTree() 构造的树是什么类型？

{{ select(6) }}

• 满二叉树
• 完全二叉树
• 二叉排序树
• 其他都不对

第 7 题 已知二叉树的 中序遍历 是 [D, B, E, A, F, C]，先序遍历 是 [A, B, D, E, C, F]。请问该二叉树的后序遍历结果是（ ）。

{{ select(7) }}

• [D, E, B, F, C, A]
• [D, B, E, F, C, A]
• [D, E, B, C, F, A]
• [B, D, E, F, C, A]

第 8 题 完全二叉树可以用数组连续高效存储，如果节点从 1 开始编号，则对有两个孩子节点的节点 i ，（ ）。

{{ select(8) }}

• 左孩子位于 2i ，右孩子位于 2i+1
• 完全二叉树的叶子节点可以出现在最后一层的任意位置
• 所有节点都有两个孩子
• 左孩子位于 2i+1 ，右孩子位于 2i+2

第 9 题 设有字符集 {a, b, c, d, e, f} ，其出现频率分别为 {5, 9, 12, 13, 16, 45} 。哈夫曼算法构造最优前缀编码，以下哪一组可能是对应的哈夫曼编码？（非叶子节点左边分支记作 0，右边分支记作 1，左右互换不影响正确性）。

{{ select(9) }}

• a: 00；b: 01；c: 10；d: 110；e: 111；f: 0
• a: 1100；b: 1101；c: 100；d: 101；e: 111；f: 0
• a: 000；b: 001；c: 01；d: 10；e: 110；f: 111
• a: 10；b: 01；c: 100；d: 101；e: 111；f: 0

第 10 题 下面代码生成格雷编码，则横线上应填写（ ）。

{{ select(10) }}

• int i = 0; i < prev.size(); i++
• int i = prev.size()-1; i >= 0; i--
• auto s : prev
• int i = prev.size()/2; i < prev.size(); i++

第 11 题 请将下列树的深度优先遍历代码补充完整，横线处应填入（ ）。

{{ select(11) }}

• vector
• list
• queue
• stack

第 12 题 令 是树的节点数目，下列代码实现了树的广度优先遍历，其时间复杂度是（ ）。

{{ select(12) }}

• $O(n)$
• $O(log n)$
• $O(n^2)$
• $O(2^n)$

第 13 题 在二叉排序树（Binary Search Tree, BST）中查找元素 50 ，从根节点开始：若根值为 60 ，则下一步应去搜索：

{{ select(13) }}

• 左子树
• 右子树
• 随机
• 根节点

第 14 题 删除二叉排序树中的节点时，如果节点有两个孩子，则横线处应填入（ ），其中 findMax 和 findMin 分别为寻找树的最大值和最小值的函数。

{{ select(14) }}

• root->left
• root->right
• findMin(root->right)
• findMax(root->left)

第 15 题 给定 n 个物品和一个最大承重为W 的背包，每个物品有一个重量wt[i]和价值val[i]，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 W，则横线上应填写（ ）。

{{ select(15) }}

• dp[w] = max(dp[w], dp[w] + val[i]);
• dp[w] = dp[w - wt[i]] + val[i];
• dp[w] = max(dp[w - 1], dp[w - wt[i]] + val[i]);
• dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

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

第 1 题 当基类可能被多态使用，其析构函数应该声明为虚函数。

{{ select(16) }}

• 对
• 错

第 2 题 哈夫曼编码是最优前缀码，且编码结果唯一。

{{ select(17) }}

• 对
• 错

第 3 题 一个含有100个节点的完全二叉树，高度为8。

{{ select(18) }}

• 对
• 错

第 4 题 在 C++ STL 中，栈（ std::stack ）的 pop 操作返回栈顶元素并移除它。

{{ select(19) }}

• 对
• 错

第 5 题 循环队列通过模运算循环使用空间。

{{ select(20) }}

• 对
• 错

第 6 题 一棵有 n 个节点的二叉树一定有 n-1 条边。

{{ select(21) }}

• 对
• 错

第 7 题 以下代码实现了二叉树的中序遍历。输入以下二叉树，中序遍历结果是 4 2 5 1 3 6 。

{{ select(22) }}

• 对
• 错

第 8 题 下面代码实现的二叉排序树的查找操作时间复杂度是，其中 为树高。

{{ select(23) }}

• 对
• 错

第 9 题 下面代码实现了动态规划版本的斐波那契数列计算，其时间复杂度是。

{{ select(24) }}

• 对
• 错

第 10 题 有一排香蕉，每个香蕉有不同的甜度值。小猴子想吃香蕉，但不能吃相邻的香蕉。以下代码能找到小猴子吃到最甜的香蕉组合。

{{ select(25) }}

• 对
• 错