单选题（每题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），每个物品对应的价值$values$分别为$20,30,50,60$，则函数的输出为（ ） {{ select(15) }}

• 90
• 100
• 110
• 140