单选题（每题 2 分，共 30 分）
第 1 题 面向对象的编程思想主要包括（ ）原则。
{{ select(1) }}
- 贪心、动态规划、回溯
- 并发、并行、异步
- 递归、循环、分治
- 封装、继承、多态
第 2 题 运行下列代码，屏幕上输出 （ ）。
1 #include <iostream>
2 using namespace std;
3
4 class my_class {
5 public:
6 static int count;
7 my_class() {
8 count++;
9 }
10 ~my_class() {
11 count--;
12 }
13 static void print_count() {
14 cout << count << " ";
15 }
16 };
17 int my_class::count = 0;
18 int main() {
19 my_class obj1;
20 my_class::print_count();
21 my_class obj2;
22 obj2.print_count();
23 my_class obj3;
24 obj3.print_count();
25 return 0;
26 }
{{ select(2) }}
1 1 11 2 31 1 21 2 2
第 3 题 运行下列代码，屏幕上输出（ ）。
1 #include <iostream>
2 using namespace std;
3
4 class shape {
5 protected:
6 int width, height;
7 public:
8 shape(int a = 0, int b = 0) {
9 width = a;
10 height = b;
11 }
12 virtual int area() {
13 cout << "parent class area: " <<endl;
14 return 0;
15 }
16 };
17
18 class rectangle: public shape {
19 public:
20 rectangle(int a = 0, int b = 0) : shape(a, b) { }
21
22 int area () {
23 cout << "rectangle area: ";
24 return (width * height);
25 }
26 };
27
28 class triangle: public shape {
29 public:
30 triangle(int a = 0, int b = 0) : shape(a, b) { }
31
32 int area () {
33 cout << "triangle area: ";
34 return (width * height / 2);
35 }
36 };
37
38 int main() {
39 shape *pshape;
40 rectangle rec(10, 7);
41 triangle tri(10, 5);
42 pshape = &rec;
43 pshape->area();
44 pshape = &tri;
45 pshape->area();
46 return 0;
47 }
{{ 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 题 要实现将一个输入的十进制正整数转化为二进制表示，下面横线上应填入的代码为（ ）。
1 #include <iostream>
2 using namespace std;
3 stack<int> ten2bin(int n) {
4 stack<int> st;
5 int r, m;
6 r = n % 2;
7 m = n / 2;
8 st.push(r);
9 while (m != 1) {
10 r = m % 2;
11 st.push(r);
12 m = m / 2;
13 }
14 st.push(m);
15 return st;
16 }
17 int main() {
18 int n;
19 cin >> n;
20 stack<int> bin;
21 bin = ten2bin(n);
22 while (!bin.empty()) {
23 _____________________ // 在此处填入代码
24 }
25 return 0;
26 }
{{ select(6) }}
cout << bin.top(); bin.pop();bin.pop(); cout << bin.top();cout << bin.back(); bin.pop();cout << bin.front(); bin.pop();
第 7 题 下面定义了一个循环队列的类，请补全判断队列是否满的函数，横向上应填写（ ）。
1 #include <iostream>
2 using namespace std;
3
4 class circular_queue {
5 private:
6 int *arr; // 数组用于存储队列元素
7 int capacity; // 队列容量
8 int front; // 队头指针
9 int rear; // 队尾指针
10
11 public:
12 circular_queue(int size) {
13 capacity = size + 1; // 为了避免队列满时与队列空时指针相等的情况，多预留一个空间
14 arr = new int[capacity];
15 front = 0;
16 rear = 0;
17 }
18
19 ~circular_queue() {
20 delete[] arr;
21 }
22
23 bool is_empty() {
24 return front == rear;
25 }
26
27 bool is_full() {
28 ________________ // 在此处填入代码
29 }
30
31 void en_queue(int data) {
32 if (is_full()) {
33 cout << "队列已满，无法入队！" << endl;
34 return -1;
35 }
36 arr[rear] = data;
37 rear = (rear + 1) % capacity;
38 return 1;
39 }
40 int de_queue() {
41 if (is_empty()) {
42 cout << "队列为空，无法出队！" << endl;
43 return -1; // 出队失败，返回一个特殊值
44 }
45 int data = arr[front];
46 front = (front + 1) % capacity;
47 return data;
48 }
49 };
{{ select(7) }}
return (rear + 1) % capacity == front;return rear % capacity == front;return rear == front;return (rear + 1) == front;
第 8 题 对 "classmycls" 使用哈夫曼（Huffman）编码，最少需要（ ）比特。
{{ select(8) }}
第 9 题 二叉树的（ ）第一个访问的节点是根节点。
{{ select(9) }}
- 先序遍历
- 中序遍历
- 后序遍历
- 以上都是
第 10 题 一棵 层的满二叉树中节点数为（ ）。
{{ select(10) }}
第 11 题 在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和( )。
{{ select(11) }}
- 重叠子问题
- 分治法
- 贪心策略
- 回溯算法
第 12 题 青蛙每次能跳1或2步，下面代码计算青蛙跳到第n步台阶有多少种不同跳法。则下列说法，错误的是（ ）。
1 int jump_recur(int n) {
2 if (n == 1) return 1;
3 if (n == 2) return 2;
4 return jump_recur(n - 1) + jump_recur(n - 2);
5 }
6
7 int jump_dp(int n) {
8 vector<int> dp(n + 1); // 创建一个动态规划数组，用于保存已计算的值
9 // 初始化前两个数
10 dp[1] = 1;
11 dp[2] = 2;
12 // 从第三个数开始计算斐波那契数列
13 for (int i = 3; i <= n; ++i) {
14 dp[i] = dp[i - 1] + dp[i - 2];
15 }
16 return dp[n];
17 }
{{ select(12) }}
函数jump_recur()采用递归方式。函数jump_dp()采用动态规划方法。当n较大时，函数jump_recur()存在大量重复计算，执行效率低。函数jump_recur()代码量小，执行效率高。
第 13 题 阅读以下二叉树的广度优先搜索代码:
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 // 二叉树节点的定义
5 struct TreeNode {
6 int val;
7 TreeNode* left;
8 TreeNode* right;
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 };
11 // 宽度优先搜索（BFS）迭代实现
12 TreeNode* bfs(TreeNode* root, int a) {
13 if (root == nullptr) return nullptr;
14 queue<TreeNode*> q;
15 q.push(root);
16 while (!q.empty()) {
17 TreeNode* node = q.front();
18 q.pop();
19 if (node->val == a)
20 return node;
21 cout << node->val << " "; // 先访问当前节点
22 if (node->left) q.push(node->left); // 将左子节点入队
23 if (node->right) q.push(node->right); // 将右子节点入队
24 }
25 return nullptr;
26 }
使用以上算法，在以下这棵树搜索数值时，可能的输出是( )。
{{ select(13) }}
5 2 -4 3 17 9-4 2 3 5 9 175 2 17 -4 3 9以上都不对
第 14 题 同上题中的二叉树，阅读以下二叉树的深度优先搜索代码
1 #include <iostream>
2 #include <stack>
3 using namespace std;
4 // 非递归深度优先搜索（DFS）
5 TreeNode* dfs(TreeNode* root, int a) {
6 if (root == nullptr) return nullptr;
7 stack<TreeNode*> stk;
8 stk.push(root);
9 while (!stk.empty()) {
10 TreeNode* node = stk.top();
11 stk.pop();
12 if (node->val == a)
13 return node;
14 cout << node->val << " "; // 访问当前节点
15 if (node->right) stk.push(node->right); // 先压入右子节点
16 if (node->left) stk.push(node->left); // 再压入左子节点
17 }
18 return nullptr;
19 }
使用以上算法，在二叉树搜索数值时，可能的输出是
{{ select(14) }}
5 2 -4 3 17 9-4 2 3 5 9 175 2 17 -4 3 9以上都不对
第 15 题 在上题的树中搜索数值 时，采用深度优先搜索一共比较的节点数为
{{ select(15) }}