客观题
一、单选题（每题 2 分，共 30 分）
- 在构建哈夫曼树时，每次应该选择（ ）合并。
{{ select(1) }}
- 最小权值的节点
- 最大权值的节点
- 随机节点
- 深度最深的节点
- 面向对象的编程思想主要包括以下哪些原则？（ ）
{{ select(2) }}
- 贪心、动态规划、回溯
- 并发、并行、异步
- 递归、循环、分治
- 封装、继承、多态
- 在队列中，元素的添加和删除是按照（ ）原则进行的。
{{ select(3) }}
- 先进先出
- 先进后出
- 最小值先出
- 随机进出
-
给定一个简单的类定义如下，（ ）语句在类的外部正确地创建了一个 对象并调用了 函数？
class Circle { private: double radius; public: Circle(double r) : radius(r) {} double getArea() { return 3.14 * radius * radius; } };
{{ select(4) }}
Circle c = Circle(5.0); c.getArea(c);Circle c(5.0); getArea(c);Circle c = new Circle(5.0); c.getArea();Circle c(5.0); c.getArea();
-
以下代码希望能在一棵二叉排序树中搜索特定的值，请在横线处填入（ ），使其能正确实现相应功能。
TreeNode* search(TreeNode* root, int target) { if (root == NULL || root->val == target) { return root; } if (_______________) { return search(root->left, target); } else { return search(root->right, target); } }
{{ select(5) }}
target < root->lefttarget < root->valtarget > root->valtarget > root->left
- 位格雷编码的正确顺序是（ ）。
{{ select(6) }}
-
以下动态规划算法的含义与目的是（ ）。
int function(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; if (n == 1) return nums[0]; vector<int> dp(n, 0); dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for (int i = 2; i < n; ++i) { dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]); } return dp[n - 1]; }
{{ select(7) }}
- 计算数组 中的所有元素的和
- 计算数组 中相邻元素的最大和
- 计算数组 中不相邻元素的最大和
- 计算数组 中的最小元素
-
阅读以下广度优先搜索的代码：
void bfs(TreeNode* root) { if (root == NULL) { return; } queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* current = q.front(); q.pop(); cout << current->val << " "; if (current->left) { q.push(current->left); } if (current->right) { q.push(current->right); } } }使用以上算法遍历以下这棵树，可能的输出是（ ）。
1 / \ 2 3 / \ \ 8 9 6 / \ \ 4 5 7 / \ 10 11
{{ select(8) }}
- $1\ \ 2\ \ 8\ \ 9\ \ 4\ \ 5\ \ 3\ \ 6\ \ 7\ \ 10\ \ 11$
- $1\ \ 2\ \ 3\ \ 4\ \ 5\ \ 6\ \ 7\ \ 8\ \ 9\ \ 10\ \ 11$
- $1\ \ 2\ \ 3\ \ 8\ \ 9\ \ 6\ \ 4\ \ 5\ \ 7\ \ 10\ \ 11$
- $1\ \ 2\ \ 3\ \ 8\ \ 9\ \ 4\ \ 5\ \ 6\ \ 7\ \ 10\ \ 11$
-
给定一个空栈，执行以下操作序列：
操作序列：$\tt push(1),\ push(2),\ push(3),\ pop(),\ pop(),\ push(4),\ push(5),\ pop()$
最终栈中的元素是（ ）。
{{ select(9) }}
- 一个有 个叶子节点的完全二叉树，最多有（ ）个结点。
{{ select(10) }}
- 在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和（ ）。
{{ select(11) }}
- 重叠子问题
- 分治法
- 贪心策略
- 回溯算法
- 若一棵二叉树的先序遍历为：、中序遍历为：，它的后序遍历为（ ）。
{{ select(12) }}
- 线性筛法与埃氏筛法相比的优势是（ ）。
{{ select(13) }}
- 更容易实现
- 更节省内存
- 更快速
- 更准确
-
以下代码使用了辗转相除法求解最大公因数，请在横线处填入（ ），使其能正确实现相应功能。
int gcd(int a, int b) { while (b != 0) { ______________________ } return a; }
{{ select(14) }}
int temp = b; b = a / b; a = temp;int temp = a; a = b / a; b = temp;int temp = b; b = a % b; a = temp;b = a % b; a = b;
-
下面的代码片段用于反转单链表，请进行（ ）修改，使其能正确实现相应功能。
ListNode* reverseLinkedList(ListNode* head) { ListNode* prev = nullptr; ListNode* current = head; while (current != nullptr) { ListNode* next = current->next; current->next = next; prev = current; current = next; } return prev; }
{{ select(15) }}
current->next = next;应该改为current->next = prev;ListNode* next = current->next;应该改为ListNode* next = prev->next;current != nullptr应该改为current->next != nullptrListNode* prev = nullptr;应该改为ListNode* prev = head;
二、判断题（每题 2 分，共 20 分）
- 哈夫曼树是一种二叉树。（ ）
{{ select(16) }}
- 正确
- 错误
- 在动态规划中，状态转移方程的作用是定义状态之间的关系。（ ）
{{ select(17) }}
- 正确
- 错误
- 继承是将已有类的属性和方法引入新类的过程。（ ）
{{ select(18) }}
- 正确
- 错误
- 完全二叉树的任意一层都可以不满。（ ）
{{ select(19) }}
- 正确
- 错误
- 删除单向链表中的节点，只需知道待删除节点的地址即可，无需访问前一个节点。（ ）
{{ select(20) }}
- 正确
- 错误
- 在宽度优先搜索中，通常使用队列来辅助实现。（ ）
{{ select(21) }}
- 正确
- 错误
- 哈夫曼编码的主要应用领域是有损数据压缩。（ ）
{{ select(22) }}
- 正确
- 错误
- 二叉搜索树的查找操作的时间复杂度是 。（ ）
{{ select(23) }}
- 正确
- 错误
- 栈的基本操作包括入栈（）和出栈（）。（ ）
{{ select(24) }}
- 正确
- 错误
- 使用哈夫曼编码对一些字符进行编码，如果两个字符的频率差异最大，则它们的编码可能出现相同的前缀。（ ）
{{ select(25) }}
- 正确
- 错误
