一、单选题（每题 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背包问题的函数，假设背包的容量 是10kg，假设输⼊4个物品的重量 weights 分别为 1、3、4、6（单位为kg），每个物品对应的价值 values 分别为 20、30、40、50，则函数的输出为（ ）。

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

• 对
• 错