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

1. 以下（ ）没有涉及 C++ 语⾔的面向对象特性支持。 {{ select(1) }}

• C++ 中构造⼀个class 或 struct
• C++ 中调用printf 函数
• C++ 中调用用户定义的类成员函数
• C++ 中构造来源于同⼀基类的多个派⽣类

2. 关于以下C++代码，（ ）行代码会引起编译错误。

{{ select(2) }}

• Line 1
• Line 2
• Line 3
• 没有编译错误

3. 有6个元素，按照 6,5,4,3,2,1 的顺序进⼊栈S，下列（ ）的出栈序列是不能出现的（ ）。

{{ select(3) }}

• 5,4,3,6,1,2
• 4,5,3,1,2,6
• 3,4,6,5,2,1
• 2,3,4,1,5,6

4. 采⽤如下代码实现检查输⼊的字符串括号是否匹配，横线上应填⼊的代码为（ ）。

   

{{ select(4) }}

• top = st.top(); st.pop();
• st.pop(); top = st.top();
• st.pop(); top = st.front();
• top = st.front(); st.pop();

5. 下⾯代码判断队列的第⼀个元素是否等于a，并删除该元素，横向上应填写（ ）。

{{ select(5) }}

• is_equal = (q.front() == a);
• is_equal = (q.front() == a); q.pop();
• q.pop(); is_equal = (q.front() == a);
• q.pop(); is_equal = (q.top() == a);

6. 假设字母表{a,b,c,d,e} 在字符串出现的频率分别为 10%，15%，30%，16%，29%。若使⽤哈夫曼编码⽅式对字母进⾏⼆进制编码，则字符abcdef 分别对应的⼀组哈夫曼编码的长度分别为（ ）。

{{ select(6) }}

• 4, 4, 1, 3, 2
• 3, 3, 2, 2, 2
• 3, 3, 1, 2, 1
• 4, 4, 1, 2, 2

7. 以下C++代码实现 n 位的格雷码，则横线上应填写（ ）。

{{ select(7) }}

• graycode_list.push_back("0" + graycode_list[j]);
• graycode_list[j] = "0" + graycode_list[j];
• graycode_list.push_back("1" + graycode_list[j]);
• graycode_list[j] = "1" + graycode_list[j];

8. 给定⼀棵⼆叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG，则这棵树的正确后序遍历结果是（ ）。

{{ select(8) }}

• EDBGFCA
• EDGBFCA
• DEBGFCA
• DBEGFCA

9. ⼀棵有n个结点的完全⼆叉树⽤数组进⾏存储与表⽰，已知根结点存储在数组的第1个位置。若存储在数组第9个位置的结点存在兄弟结点和两个⼦结点，则它的兄弟结点和右⼦结点的位置分别是（ ）。

{{ select(9) }}

• 8, 18
• 10, 18
• 8, 19
• 10, 19

10. ⼆叉树的深度定义为从根结点到叶结点的最长路径上的结点数，则以下基于⼆叉树的深度优先搜索实现的深度计算函数中横线上应填写（ ）。

{{ select(10) }}

• return left_depth + right_depth;
• return max(left_depth, right_depth);
• return max(left_depth, right_depth) + 1;
• return left_depth + right_depth + 1;

11. 上⼀题的⼆叉树深度计算还可以采⽤⼆叉树的⼴度优先搜索来实现。以下基于⼆叉树的⼴度优先搜索实现的深度计算函数中横线上应填写（ ）。

{{ select(11) }}

• int level_size = q.size(); depth++;
• int level_size = 2; depth++;
• int level_size = q.size(); depth += level_size;
• int level_size = 2; depth += level_size;

12. ⼆叉搜索树中的每个结点，其左⼦树的所有结点值都⼩于该结点值，右⼦树的所有结点值都⼤于该结点值。以下代码对给定的整数数组(假设数组中没有数值相等的元素)，构造⼀个对应的⼆叉搜索树，横线上应填写（ ）:

{{ select(12) }}

• 
• 
• 
• 

13. 对上题中的⼆叉搜素树，当输⼊数组为[5,3,7,2,4,6,8]时，构建⼆叉搜索树，并采⽤如下代码实现的遍历⽅式，得到的输出是（ ）。

{{ select(13) }}

• 5 3 7 2 4 6 8
• 2 3 4 5 6 7 8
• 2 4 3 6 8 7 5
• 2 4 3 5 6 7 8

14. 动态规划通常用于解决（ ）。

{{ select(14) }}

• 无法分解的问题
• 可以分解成相互依赖的子问题的问题
• 可以通过贪心算法解决的问题
• 只能通过递归解决的问题

15. 阅读以下用动态规划解决的0-1背包问题的函数，假设背包的容量 W是10kg，假设输⼊4个物品的重量weights分别为1，3，4，6（单位为kg），每个物品对应的价值 walues分别为20，30，50，60，则函数的输出为（ ）。

{{ select(15) }}

• 90
• 100
• 110
• 140

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

1. C++、Python和JAVA等都是面向对象的编程语言。 {{ select(16) }}

• 对
• 错

2. 在C++中，类的静态成员变量只能被该类对象的成员函数访问。

{{ select(17) }}

• 对
• 错

3. 栈是⼀种线性结构，可通过数组或链表来实现。⼆者相比，数组实现占⽤的内存较少，链表实现的⼊队和出队操作的时间复杂度较低。

{{ select(18) }}

• 对
• 错

4. 运行以下C++代码，屏幕将输出“derived class”。

{{ select(19) }}

• 对
• 错

5. 如下列代码所⽰的基类（base）及其派⽣类（derived），则⽣成⼀个派⽣类的对象时，只调用派⽣类的构造函数。

{{ select(20) }}

• 对
• 错

6. 哈夫曼编码本质上是⼀种贪心策略。 {{ select(21) }}

• 对
• 错

7. 如果根结点的深度记为1，则⼀棵恰有2024个叶结点的⼆叉树的深度最少是12。

   {{ select(22) }}

• 对
• 错

8. 在非递归实现的树的⼴度优先搜索中，通常使用栈来辅助实现。

{{ select(23) }}

• 对
• 错

9. 状态转移方程是动态规划的核心，可以通过递推方式表示问题状态的变化。 {{ select(24) }}

• 对
• 错

10. 应用动态规划算法时，识别并存储重叠子问题的解是必须的。

{{ select(25) }}

• 对
• 错