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

第 1 题 在面向对象编程中，下列关于虚函数的描述中，错误的是 ( )

{{ select(1) }}

• 虚函数用于支持运行时多态
• 通过基类指针调用虚函数时，会根据对象实际类型决定调用版本
• 构造函数可以声明为虚函数以支持多态
• 基类析构函数常声明为虚函数以避免资源泄漏

第 2 题 执行如下代码，会输出 钢琴:叮咚叮咚和 吉他:咚咚当当。这体现了面向对象编程的( )特性。

01 class Instrument {
02 public:
03     virtual void play() {
04         cout << "乐器在演奏声音" << endl;
05     }
06
07     virtual ~Instrument() {}
08 };
09
10 class Piano : public Instrument {
11 public:
12     void play() override {
13         cout << "钢琴：叮咚叮咚" << endl;
14     }
15 };
16
17 class Guitar : public Instrument {
18 public:
19     void play() override {
20         cout << "吉他：咚咚当当" << endl;
21     }
22 };
23 
24 int main() {
25     Instrument* instruments[2];
26     instruments[0] = new Piano();
27     instruments[1] = new Guitar();
28
29     for (int i = 0; i < 2; ++i) {
30         instruments[i]->play();
31     }
32
33     for (int i = 0; i < 3; ++i) {
34         delete instruments[i];
35     }
36     return 0;
37 }

{{ select(2) }}

• 继承
• 封装
• 多态
• 链接

第 3 题 关于以下代码，说法正确的是 ( )

01 class Instrument {
02 public:
03     void play() {
04         cout << "乐器在演奏声音" << endl;
05     }
06 
07     virtual ~Instrument() {}
08 };
09 
10 class Piano : public Instrument {
11 public:
12     void play() override {
13         cout << "钢琴：叮咚叮咚" << endl;
14     }
15 };
16 
17 class Guitar : public Instrument {
18 public:
19     void play() override {
20         cout << "吉他：咚咚当当" << endl;
21     }
22 };
23
24 int main() {
25     Instrument* instruments[2];
26     instruments[0] = new Piano();
27     instruments[1] = new Guitar();
28 
29     for (int i = 0; i < 2; ++i) {
30         instruments[i]->play();   
31     }
32
33     for (int i = 0; i < 3; ++i) {
34         delete instruments[i];    
35     }
36     return 0;
37 }

{{ select(3) }}

• 执行代码会输出两行，内容分别为:钢琴:叮咚叮咚 和 吉他:咚咚当当
• 执行代码会输出两行，内容分别为:乐器在演奏声音 和 乐器在演奏声音
• 代码编译出现错误
• 代码运行出现错误

第 4 题 某文本编辑器把用户输入的字符依次压入栈 $S$。用户依次输入 A，B，C，D 后，用户按了两次撤销(每次撤销，弹出栈顶一个字符)。此时栈从栈底到栈顶的内容是:( )。

{{ select(4) }}

• A B
• A B C
• A B D
• B C

第 5 题 假设循环队列数组长度为 $N$，其中队空判断条件为: front== rear，队满判断条件为:(rean+1)%N == front，出队对应的操作为: front =(front+1)% N，入队对于的操作为: rear =(rear+1)%N。循环队列长度N=6，初始 front =1，rear =1，执行操作序列为:入队,入队,入队,出队,入队，入队， 则最终 (front,rear) 的值是 ( )。

{{ select(5) }}

• (2, 5)
• (2, 0)
• (3, 5)
• (3, 0)

第 6 题 以下函数 check() 用于判断一棵二叉树是否为 ( )

01 bool check(TreeNode* root) {
02     if (!root) return true;
03 
04     queue<TreeNode*> q;
05     q.push(root);
06     bool hasNull = false;
07     while (!q.empty()) {
08         TreeNode* cur = q.front(); q.pop();
09         if (!cur) {
10             hasNull = true;
11         } else {
12             if (hasNull) return false;
13             q.push(cur->left);
14             q.push(cur->right);
15         }
16     }
17     return true;
18 }

{{ select(6) }}

• 满二叉树
• 完全二叉树
• 二叉搜索树
• 平衡二叉树

第 7 题 以下代码实现了二叉树的 ( )

01 void traverse(TreeNode* root) {
02     if (!root) return;
03     traverse(root->left);
04     traverse(root->right);
05     cout << root->val << " ";
06 }

{{ select(7) }}

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

第 8 题 下面代码实现了哈夫曼编码，则横线处应填写的代码是 ( )

01 struct Symbol {
02     char ch;            //字符
03     long long freq;     //频率
04     string code;        //哈夫曼编码
05 };
06 
07 struct Node {
08     long long w;        //权值
09     int l, r;           //左右孩子（节点下标），-1 表示空
10     int sym;            // 叶子对应符号下标；内部节点为 -1
11     Node(long long _w=0, int _l=-1, int _r=-1, int _sym=-1)
12         : w(_w), l(_l), r(_r), sym(_sym) {}
13 };
14 
15 // 从 A(leafIdx) 和 B(internalIdx) 的队首取最小的一个节点下标
16 static int PopMinNode(const vector<Node>& nodes,
17                       const vector<int>& leafIdx, int n, int& pA,
18                       const vector<int>& internalIdx, int& pB) {
19     if (pA < n && (pB >= (int)internalIdx.size() ||
20                    nodes[leafIdx[pA]].w <= nodes[internalIdx[pB]].w)) {
21         return leafIdx[pA++];
22     }
23     else {
24         return internalIdx[pB++];
25     }
26 }
27 
28 // DFS 生成编码（左 0，右 1）
29 static void DFSBuildCodes(int u, const vector<Node>& nodes, Symbol sym[], string& path) {
30     if (u == -1) return;
31
32     if (nodes[u].sym != -1) {               // 叶子
33        sym[nodes[u].sym].code = path;
34         return;
35     }
36 
37     path.push_back('0');
38     DFSBuildCodes(nodes[u].l, nodes, sym, path);
39     path.pop_back();
40 
41     path.push_back('1');
42     DFSBuildCodes(nodes[u].r, nodes, sym, path);
43     path.pop_back();
44 }
45
46 int BuildHuffmanCodes(Symbol sym[], int n) {
47     for (int i = 0; i < n; i++) sym[i].code.clear();
48     if (n <= 0) return -1;
49 
50     // 只有一个字符：约定编码为 "0"
51     if (n == 1) {
52         sym[0].code = "0";
53         return 0;
54     }
55 
56     vector<Node> nodes;
57     nodes.reserve(2 * n);
58 
59     // 1) 建立叶子节点
60     vector<int> leafIdx(n);
61     for (int i = 0; i < n; i++) {
62         leafIdx[i] = (int)nodes.size();        
63         nodes.push_back(Node(sym[i].freq, -1, -1, i));
64     }
65 
66     // 2) 叶子按权值排序（A 队列）
67     sort(leafIdx.begin(), leafIdx.end(),
68          [&](int a, int b) {
69             if (nodes[a].w != nodes[b].w) return nodes[a].w < nodes[b].w;
70             return nodes[a].sym < nodes[b].sym; // 稳定一下
71         });
72 
73     // B 队列（内部节点下标队列）
74     vector<int> internalIdx;
75     internalIdx.reserve(n);
76 
77     int pA = 0, pB = 0;
78 
79     // 3) 合并 n-1 次
80     for (int k = 1; k < n; k++) {
81         int x = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
82         int y = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
83 
84         int z = (int)nodes.size();
85         ________________________ // 在此处填写代码    
86 }
87 
88     int root = internalIdx.back();
89 
90     // 4) DFS 生成编码
91     string path;
92     DFSBuildCodes(root, nodes, sym, path);
93     return root;
94 }

{{ select(8) }}

• 01 nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1));
  02 internalIdx.push_back(z);
  

• 01 nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1));
  02 leafIdx.push_back(z);
  

• 01 internalIdx.push_back(z);
  02 nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y));
  

• 01 nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y));
  02 leafIdx.push_back(z);
  

第 9 题 以下关于哈夫曼编码的说法，正确的是 ( )

{{ select(9) }}

• 哈夫曼编码是定长编码
• 哈夫曼编码中，没有任何一个字符的编码是另一个字符编码的前缀
• 哈夫曼编码一定唯一
• 哈夫曼编码不能用于数据压缩

第 10 题 以下函数实现了二叉排序树($BST$)的 ( ) 操作。

01 TreeNode* op(TreeNode* root, int x) {
02     if (!root) return new TreeNode(x);
03     if (x < root->val)
04         root->left = op(root->left, x);
05     else
06         root->right = op(root->right, x);
07     return root;
08 }

{{ select(10) }}

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

第 11 题 下列代码实现了树的深度优先遍历，则横线处应填入 ( )。

01 struct TreeNode {
02     int val;
03     TreeNode* left;
04     TreeNode* right;
05     TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06 };
07 
08 void dfs(TreeNode* root) {
09     if (!root) return;
10     stack<TreeNode*> st;
11     st.push(root);
12     while (!st.empty()) {
13         TreeNode* node = st.top(); st.pop();
14         cout << node->val << " ";
15         if (node->right) st.push(node->right);
16         ________________________
17     }
18 }

{{ select(11) }}

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

第 12 题 给定一棵普通二叉树(节点值没有大小规律)，下面代码判断是否存在值为 x 的结点，则横线处应填入 ( )

01 struct TreeNode {
02     int val;
03     TreeNode* left;
04     TreeNode* right;
05     TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06 };
07 
08 TreeNode* bfsFind(TreeNode* root, int x) {
09     if (!root) return nullptr;
10 
11     queue<TreeNode*> q;
12     q.push(root);
13 
14     while (!q.empty()) {
15         TreeNode* cur = q.front(); q.pop();
16         if (cur->val == x) return cur;
17         ________________________
18     }
19     return nullptr;
20 }

{{ select(12) }}

• q.push(cur);
• if (cur->right) q.push(cur->right);

• 01 if (cur->left)
  02     q.push(cur->left);
  03 if (cur->right)
  04     q.push(cur->right);
  

• 01 q.push(cur->left);
  02 q.push(cur->right);
  

第 13 题 在二叉排序树(Binary Search Tree, BST)中，假设节点值互不相同。给定如下搜索函数，以下说法一定正确的是 ( )。

01 bool find(Node* root, int x) {
02     while (root) {
03         if (root->val == x) return true;
04         root = (x < root->val) ? root->left : root->right;
05     }
06     return false;
07 }

{{ select(13) }}

• 最坏情况下，访问结点数是 $O(logn)$
• 最坏情况下，访问结点数是 $O(n)$
• 无论如何，访问结点数都不超过树高的一半
• 一定比在普通二叉树中搜索快

第 14 题 01背包(每件物品最多选一次)问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是 ( )

01 for each item (w, v):
02     for (int j = W; j >= w; --j)
03         dp[j] = max(dp[j], dp[j-w] + v);

{{ select(14) }}

• 内层 j 必须从小到大，否则会漏解
• 内层 j 必须从大到小，否则同一件物品会被用多次
• j 从大到小或从小到大都一样
• 只要 dp 初始为 0，方向无所谓

第 15 题 以下关于动态规划的说法中，错误的是 ( )

{{ select(15) }}

• 动态规划方法通常能够列出递推公式。
• 动态规划方法的时间复杂度通常为状态的个数。
• 动态规划方法有递推和递归两种实现形式。
• 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

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

第 1 题 以下代码中，构造函数被调用的次数是 $1$ 次。

01 class Test {
02 public:
03     Test() { cout << "T "; }
04 };
05 
06 int main() {
07     Test a;
08     Test b = a;
09 }

{{ select(16) }}

• 正确
• 错误

第 2 题 面向对象编程中，封装是指将数据和操作数据的方法绑定在一起，并对外隐藏实现细节。

{{ select(17) }}

• 正确
• 错误

第 3 题 以下代码能够正确统计二叉树中叶子结点的数量。

01 int countLeaf(TreeNode* root) {
02     if (!root) return 0;
03     if (!root->left && !root->right) return 1;
04     return countLeaf(root->left) + countLeaf(root->right);
05 }

{{ select(18) }}

• 正确
• 错误

第 4 题 广度优先遍历二叉树可用栈来实现。

{{ select(19) }}

• 正确
• 错误

第 5 题 函数调用管理可用栈来管理。

{{ select(20) }}

• 正确
• 错误

第 6 题 在二叉排序树 (BST) 中，若某结点的左子树为空，则该结点一定是整棵树中的最小值结点。

{{ select(21) }}

• 正确
• 错误

第 7 题 下面的函数能正确判断一棵树是不是二叉排序树(左边的数字要比当前数字小，右边的数字要比当前数字大)

01 bool isBST(TreeNode* root, int minVal, int maxVal) {
02     if (!root) return true;
03     if (root->val <= minVal || root->val >= maxVal)
04         return false;
05     return isBST(root->left, minVal, root->val) &&
06            isBST(root->right, root->val, maxVal);
07 }

{{ select(22) }}

• 正确
• 错误

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

{{ select(23) }}

• 正确
• 错误

第 9 题 小杨在玩一个闯关游戏，从第 1 关走到第 4 关。每一关的体力消耗如下(下标表示关卡编号):cost=[0，3,5,2,4 ]，其中 cost[i] 表示到达第 i 关需要消耗的体力，cost[0]=0 表示在开始状态，体力消耗为 0。小杨每次可以从当前关卡前进 1 步或 2 步。按照上述规则，从第 1 关到第 4 关所需消耗的最小体力为 7。

{{ select(24) }}

• 正确
• 错误

第 10 题 假定只有一个根节点的树的深度为 1，则一棵有 n 个节点的完全二叉树，则树的深度为 $\lfloor 1og_2(n) \rfloor + 1$。

{{ select(25) }}

• 正确
• 错误