1. 在构建哈夫曼树时，每次应该选择（ ）合并。

A. 最小权值的节点

B. 最大权值的节点

C. 随机节点

D. 深度最深的节点

【答案】A

【考纲知识点】哈夫曼树

【解析】①初始状态下有 n 个结点（结点的权值分别是给定的n个数），将他们视作n棵只有一个结点的树 ②合并其中根结点权值最小的两棵树，生成两棵树根结点的父节点，权值为这两个根结点的权值之和，这样树的数量就减少了一个 ③重复操作 2，直到只剩下一棵树为止，这棵树就是哈夫曼树。

2. 面向对象的编程思想主要包括以下哪些原则（ ）？

A. 贪心、动态规划、回溯

B. 并发、并行、异步

C. 递归、循环、分治

D. 封装、继承、多态

【答案】D

【考纲知识点】面向对象编程

【解析】面向对象是一种编程思想，包括三大特性和六大原则，其中，三大特性指的是封装、继承和多态；六大原则指的是单一职责原则、开闭式原则、迪米特原则、里氏替换原则、依赖倒置原则以及接口隔离原则

3. 队列中，元素的添加和删除是按照（ ）原则进行的。

A. 先进先出

B. 先进后出

C. 最小值先出

D. 随机进出

【答案】A

【考纲知识点】队列

【解析】队列（Queue）是一种数据结构，是一种先进先出的线性数据结构。它只允许在列表的一端进行插入操作（入队），在另一端进行删除操作（出队），即队头进行删除操作，队尾进行插入操作。

4. 给定⼀个简单的类定义如下，（ ）语句在类的外部正确地创建了⼀个 Circle 对象并调用了 getArea 函数？

class Circle {
private:
  double radius;
public:
  Circle(double r) : radius(r) {}
  double getArea() {
    return 3.14 * radius * radius;
  }
};

A. Circle c = Circle(5.0); c.getArea(c);

B. Circle c(5.0); getArea(c);

C. Circle c = new Circle(5.0); c.getArea();

D. Circle c(5.0); c.getArea();

【答案】D

【考纲知识点】类的定义&使用

【解析】

题目要求调用 getArea函数，因为该函数是公开且不是静态的，所以需要属于对应的某个对象，在对应的选项对象定义的过程，A中Circle c = Circle(5.0)、B、D中是正确的Circle c(5.0)，C中使用了new Circle那么会返回一个Circle的指针；那么调用函数的时候，前面必须要有对象，所以要使用c.getArea()。

5. 以下代码希望能在一棵二叉排序树中搜索特定的值，请在横线处填入（ ），使其能正确实现相应功能。

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);
  }
}

A. target < root->left

B. target < root->val

C. target > root->val

D. target > root->left

【答案】B

【考纲知识点】二叉排序树搜索

【解析】 因为二叉排序树是可以看作是一个有序表，所以其查找过程和折半查找类似。算法思想： 首先将待查关键字key与根节点关键字t进行比较： a.如果key = t, 则返回根节点指针。 b.如果key < t,则进一步查找左子树。 c.如果key > t,则进一步查找右子树。

因为题目判断条件成立进入左子树，所以当前的target就是小于当前节点，那么就是target < root->val

6. 3 位格雷编码的正确顺序是（ ）。

A. 000, 001, 010, 011, 100, 101, 110, 111

B. 000, 001, 011, 010, 110, 111, 101, 100

C. 000, 010, 001, 011, 100, 110, 101, 111

D. 000, 010, 110, 100, 111, 101, 011, 001

【答案】B

【考纲知识点】格雷编码

【解析】格雷码是一种二进制编码方式，它的主要特点是在两个相邻的二进制数之间仅有一位数值的改变，且顺序在某种意义上是有规律的。三位码编码顺序：000，001，011，010，110，111，101，100。

7. 以下动态规划算法的含义与目的是（ ）。

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];
}

A. 计算数组 nums 中的所有元素的和

B. 计算数组 nums 中相邻元素的最大和

C. 计算数组 nums 中不相邻元素的最大和

D. 计算数组 nums 中的最小元素

【答案】C

【考纲知识点】动态规划

【解析】根据题目给出的代码，第9行和第11行中，可以明确求解的是最大值，不是去计算所有元素的和，并且这里计算的是不相邻元素的最大和

8. 阅读以下广度优先搜索的代码：

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);
        }
    }
 }

使用以上算法遍历以下这棵树，可能的输出是（ ）。

A. 1 2 8 9 4 5 3 6 7 10 11

B. 1 2 3 4 5 6 7 8 9 10 11

C. 1 2 3 8 9 6 4 5 7 10 11

D. 1 2 3 8 9 4 5 6 7 10 11

【答案】C

【考纲知识点】广度优先搜索

【解析】 题目是广度优先搜索（BFS）的代码，BFS类似于树的层次遍历过程,从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。那么最后的结果就是1 2 3 8 9 6 4 5 7 10 11

9. 给定一个空栈，执行以下操作序列：

操作序列： push(1), push(2), push(3), pop(), pop(), push(4), push(5), pop()

最终栈中的元素是（ ）。

A. 1, 2

B. 1, 4, 5

C. 1, 2, 5

D. 1, 4

【答案】D

【考纲知识点】栈

【解析】入栈和出栈遵从先进后出的原则，那么按照进栈顺序就是1、2、3，之后两次出栈操作，先出栈的是3，之后是2，栈中还存在1，之后4、5入栈，进行出栈操作时，5出栈，那么此时栈内的元素就是1，4

10. 一个有 124 个叶子节点的完全二叉树，最多有（ ）个结点。

A. 247

B. 248

C. 249

D. 250

【答案】B

【考纲知识点】完全二叉树

【解析】叶子结点124的话二叉树最少八层，前七层一共$2^7$-1=127个结点，第七层$2^{7-1}$=64个节点中应该有3个或4个叶子结点，第八层叶子结点应该是121或120个，一共就是最多127+121 = 248。

11. 在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和（ ）。

A. 重叠子问题

B. 分治法

C. 贪心策略

D. 回溯算法

【答案】A

【考纲知识点】动态规划

【解析】动态规划算法所具备的两个重要性质：最优子结构性质和重叠子问题，利用了这种子问题的重叠性质，对每个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，只是简单地用常数时间查看下结果。

12. 若一棵二叉树的先序遍历为：A, B, D, E, C, F、中序遍历为：D, B, E, A, F, C，它的后序遍历为（ ）。

A. D, E, B, F, C, A

B. E, D, B, F, C, A

C. D, E, B, C, F, A

D. E, D, B, C, F, A

【答案】A

【考纲知识点】二叉树遍历

【解析】二叉树的遍历分成三种，按照根节点的访问先后分为： 先序遍历（先根遍历）：先访问根节点，然后访问左子树， 最后访问右子树。 中序遍历（中根遍历）：先访问左子树，然后访问根节点， 最后访问右子树。 后序遍历（后根遍历）：先访问左子树，然后访问右子树， 最后访问根节点。 通过先序和中序，我们可以推导出整体的二叉树，那么就可以很轻松的知道后序遍历的结果为 D, E, B, F, C, A

13. 线性筛法与埃氏筛法相比的优势是（ ）。

A. 更容易实现

B. 更节省内存

C. 更快速

D. 更准确

【答案】C

【考纲知识点】线性筛法与埃氏筛法

【解析】埃式筛法是用素数来筛掉合数,但是这样也会重复计算多次，比如2 * 10 = 20, 5 * 4 = 20，当数据量较大的时候，重复计算的次数也会过多；线性筛法的核心是每个合数只会被它的最小质因数筛掉，这样就会避免重复计算、节约时间，也就能更加快速。

14. 以下代码使用了辗转相除法求解最大公因数，请在横线处填入（ ），使其能正确实现相应功能。

int gcd(int a, int b) {
  while (b != 0) {
    ______________________
  }
  return a;
}

A. int temp = b; b = a / b; a = temp;

B. int temp = a; a = b / a; b = temp;

C. int temp = b; b = a % b; a = temp;

D. b = a % b; a = b;

【答案】C

【考纲知识点】辗转相除法

【解析】辗转相除法对于任意两个自然数a和b，如果q和r是a除以b的商和余数，那么a和b的最大公因数等于b和r的最大公因数。如果想要实现辗转相除法，需要实现 a = b，b = a % b，题目中通过temp作为中间变量保存了b的值，赋值给a，就实现了a = b的效果，之后b = a % b，这里注意D选项，前后的顺序颠倒之后，循环一次之后，a和b的值是相同的

15. 下面的代码片段用于反转单链表，请进行（ ）修改，使其能正确实现相应功能。

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;
}

A. current->next = next; 应该改为 current->next = prev;

B. ListNode* next = current->next; 应该改为 ListNode* next = prev->next;

C. current != nullptr 应该改为 current->next != nullptr

D. ListNode* prev = nullptr; 应该改为 ListNode* prev = head;

【答案】A

【考纲知识点】链表

【解析】

题目进行反转列表，就是在当前链表的基础上直接反转，那么就需要明确反转之后prev是下一个节点，但是在原链表中是上一个节点，那么在第6行，我们需要将next值反转，就需要将 current->next = prev