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

第 1 题 面向对象的编程思想主要包括（ ）原则。

{{ select(1) }}

• 贪心、动态规划、回溯
• 并发、并行、异步
• 递归、循环、分治
• 封装、继承、多态

第 2 题 运行下列代码，屏幕上输出（ ）。

{{ select(2) }}

• 1 1 1
• 1 2 3
• 1 1 2
• 1 2 2

第 3 题 运行下列代码，屏幕上输出（ ）。

{{ select(3) }}

• rectangle area: triangle area:
• parent class area: parent class area:
• 运行时报错
• 编译时报错

第 4 题 向一个栈顶为hs的链式栈中插入一个指针为s的结点时，应执行（ ）。

{{ select(4) }}

• hs->next = s;
• s->next = hs; hs = s;
• s->next = hs->next; hs->next = s;
• s->next = hs; hs = hs->next;

第 5 题 在栈数据结构中，元素的添加和删除是按照什么原则进行的？

{{ select(5) }}

• 先进先出
• 先进后出
• 最小值先出
• 随机顺序

第 6 题 要实现将一个输入的十进制正整数转化为二进制表示，下面横线上应填入的代码为（ ）。

{{ select(6) }}

• cout << bin.top(); bin.pop();
• bin.pop(); cout << bin.top();
• cout << bin.back(); bin.pop();
• cout << bin.front(); bin.pop();

第 7 题 下面定义了一个循环队列的类，请补全判断队列是否满的函数，横向上应填写（ ）

{{ select(7) }}

• return (rear + 1) % capacity == front;
• return rear % capacity == front;
• return rear == front;
• return (rear + 1) == front;

第 8 题 对“classmycls”使用哈夫曼（Huffman）编码，最少需要（ ）比特。

{{ select(8) }}

• 10
• 20
• 25
• 30

第 9 题 二叉树的（ ）第一个访问的节点是根节点。

{{ select(9) }}

• 先序遍历
• 中序遍历
• 后序遍历
• 以上都是

第 10 题 一棵5层的满二叉树中节点数为（ ）。

{{ select(10) }}

• 31
• 32
• 33
• 16

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

{{ select(11) }}

• 重叠子问题
• 分治法
• 贪心策略
• 回溯算法

第 12 题 青蛙每次能跳1或2步，下面代码计算青蛙跳到第n步台阶有多少种不同跳法。则下列说法，错误的是( )。

{{ select(12) }}

• 函数jump_recur()采用递归方式。
• 函数jump_dp()采用动态规划方法。
• 当n较大时，函数jump_recur()存在大量重复计算，执行效率低。
• 函数jump_recur()代码量小，执行效率高。

第 13 题 阅读以下二叉树的广度优先搜索代码:

使用以上算法，在以下这棵树搜索数值20时，可能的输出是( )。

{{ select(13) }}

• 5 2 -4 3 17 9
• -4 2 3 5 9 17
• 5 2 17 -4 3 9
• 以上都不对

第 14 题 同上题中的二叉树，阅读以下二叉树的深度优先搜索代码:

使用以上算法，在二叉树搜索数值20时，可能的输出是( )。

{{ select(14) }}

• 5 2 -4 3 17 9
• -4 2 3 5 9 17
• 5 2 17 -4 3 9
• 以上都不对

第 15 题 在上题的树中搜索数值 时，采用深度优先搜索一共比较的节点数为（ ）。

{{ select(15) }}

• 2
• 3
• 4
• 5

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

第 1 题 哈夫曼编码本质上是一种贪心策略。

{{ select(16) }}

• 正确√
• 错误×

第 2 题 创建一个对象时，会自动调用该对象所属类的构造函数。如果没有定义构造函数，编译器会自动生成一个默认的构造函数。

{{ select(17) }}

• 正确√
• 错误×

第 3 题 定义一个类时，必须手动定义一个析构函数，用于释放对象所占用的资源。

{{ select(18) }}

• 正确√
• 错误×

第 4 题 C++中类内部可以嵌套定义类。

{{ select(19) }}

• 正确√
• 错误×

第 5 题 000, 001, 011, 010, 110, 111, 101, 100是一组格雷码。

{{ select(20) }}

• 正确√
• 错误×

第 6 题 n个节点的双向循环链表，在其中查找某个节点的平均时间复杂度是$O(log(n))$。

{{ select(21) }}

• 正确√
• 错误×

第 7 题 完全二叉树可以用数组存储数据。

{{ select(22) }}

• 正确√
• 错误×

第 8 题 在C++中，静态成员函数只能访问静态成员变量。

{{ select(23) }}

• 正确√
• 错误×

第 9 题 在深度优先搜索中，通常使用队列来辅助实现。

{{ select(24) }}

• 正确√
• 错误×

第 10 题 对0-1背包问题，贪心算法一定能获得最优解。

{{ select(25) }}

• 正确√
• 错误×