5300：[GESP202603六级] 客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 一、单选题（每题 2 分，共 30 分）
**第 1 题** 下列关于 `C++` 中类的描述，正确的是 ( )
- 如果类没有用户声明的构造函数，那么编译器会隐式声明一个默认构造函数
- 类的析构函数可以被重载，一个类可以有多个析构函数
- 类中的所有成员都必须声明为 `public`
- 类和结构体在 `C++` 中没有区别，包括默认访问权限也相同
**第 2 题** 下列代码中，`s1->draw();`和 `s2->draw();` 输出不同结果的主要原因是 ( )
```cpp
01 class Shape {
02 public:
03 virtual void draw() {
04 cout << "绘制图形" << endl;
05 }
06
07 virtual ~Shape() {}
08 };
09
10 class Circle : public Shape {
11 public:
12 void draw() override {
13 cout << "绘制圆形" << endl;
14 }
15 };
16
17 class Rectangle : public Shape {
18 public:
19 void draw() override {
20 cout << "绘制矩形" << endl;
21 }
22 };
23
24 int main() {
25 Shape* s1 = new Circle();
26 Shape* s2 = new Rectangle();
27
28 s1->draw();
29 s2->draw();
30
31 delete s1;
32 delete s2;
33 return 0;
34 }
```
- `draw()` 是普通成员函数
- `Shape` 中的 `draw()` 被声明为虚函数
- `Circle` 和 `Rectangle` 中使用了 `public` 继承
- 指针变量名不同
**第 3 题** 下面的代码在 `main()` 中有一行会导致编译错误，请找出来。
```cpp
01 class Pet {
02 public:
03 Pet(string n, int a) : name(n), age(a) {}
04 string getName() { return name; }
05 void
birthday() { age++; }
06 private:
07 string name;
08 int age;
09 };
10
11 int main() {
12 Pet cat("奶茶", 2);
13 cout << cat.getName(); //①
14 cat.birthday(); //②
15 cat.name = "大橘"; //③
16 cout << cat.getName(); //④
17 }
```
- 第 ① 行
- 第 ② 行
- 第 ③ 行
- 第 ④ 行
**第 4 题** 游乐园的过山车每次限坐 $4$ 人，用循环队列管理排队(容量 `MAX=5`，空一格判满)。下面代码执行后，循环队列是否已满? `rear` 的值是多少? ( )
```cpp
01 const int MAX = 5;
02 int queue[MAX];
03 int front = 0, rear = 0;
04
05 // 入队
06 void enqueue(int x) {
07 queue[rear] = x;
08 rear = (rear + 1) % MAX;
09 }
10 // 出队
11 void dequeue() {
12 front = (front + 1) % MAX;
13 }
14
15 int main() {
16 enqueue(1); enqueue(2); enqueue(3); enqueue(4);
17 dequeue(); dequeue();
18 enqueue(5); enqueue(6);
19 }
```
- 已满，`rear = 1`
- 未满，`rear = 1`
- 已满，`rear =2`
- 未满，`rear = 4`
**第 5 题** 在以下计算机系统应用场景中，最适合使用循环队列的是 ( )
- 函数调用过程中，保存局部变量和返回地址
- 表达式求值中的运算符优先级处理
- 操作系统中的进程优先级调度(高优先级先执行)
- 生产者和消费者问题中的共享缓冲区
**第 6 题** 在二叉搜索树 $(BST)$ 中，若中序遍历的序列为 `{1,2,3,4,5}`，且先序遍历的第一个序列元素为 $3$，则下列说法正确的是 ( )
- 该树一定是一棵完全二叉树。
- 元素 $4$ 和 $5$ 不可能是兄弟节点。
- 元素 $1$ 所在节点的深度可能大于 $3$ (根节点深度为 $1$)。
- 元素 $2$ 一定是元素 $1$ 的父节点。
**第 7 题** 某二叉树共有 $10$ 个结点，记为 $A \sim J$，已知它的先序遍历序列为:`A B D H I E C F J G`，中序遍历序列为: `H D I B E A F J C G`，则该二叉树的后序遍历序列是 ( )
- `H I D E B J F G C A`
- `H I D B E J F G C A`
- `I H D E B J F G C A`
- `H I D E B F J G C A`
**第 8 题** 下列关于树的遍历的说法中，正确的一项是 ( )
- 对任意一棵树进行深度优先遍历，所得序列一定唯一。
- 已知一棵二叉树的先序遍历和后序遍历序列，可以唯一确定这棵二叉树。
- 已知一棵二叉树的先序遍历和中序遍历序列，可以唯一确定这棵二叉树。
- 已知一棵二叉树的先序遍历序列，可以唯一确定这棵二叉树。
**第 9 题** 有 $6$ 个字符，它们出现的次数分别为: `{2，3,3，4,6，8}`，现在用哈夫曼编码为这些字符编码，最小加权路径长度 $WPL$ (每个字符的出现次数x它的编码长度，再把每个字符结果加起来)的值为( )
- 58
- 60
- 62
- 64
**第 10 题** 对 $n$ 个不同符号进行哈夫曼编码。若生成的哈夫曼树共有 $115$ 个结点，则 $n$ 的值是 ( )
- $60$
- $58$
- $57$
- $56$
**第 11 题** 关于格雷编码`(GrayCode)`，下列说法正确的是 ( )
- 格雷编码中，编码位数越多，相邻编码之间变化的位数也越多
- 格雷编码中，相邻两个编码的二进制位恰好有一位不同
- 格雷编码就是把普通二进制编码按位取反后得到的结果
- 格雷编码不能用于数字电路和状态转换的设计中
**第 12 题** 给定一棵二叉树，采用广度优先搜索 $(BFS)$ 算法，返回右视图所有节点的值。其中右视图定义为:二叉树的右视图是从树的右侧看过去时可见的节点集合，即右视图中的每个节点都是某一层中最右侧的节点 ( )
```cpp
01 struct TreeNode {
02 int val;
03 TreeNode* left;
04 TreeNode* right;
05 TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06 };
07
08 vector rightSideView(TreeNode* root) {
09 unordered_map rightmostValueAtDepth;
10 int max_depth = -1;
11
12 queue nodeQueue;
13 queue depthQueue;
14 nodeQueue.push(root);
15 depthQueue.push(0);
16
17 while (!nodeQueue.empty()) {
18 TreeNode* node = nodeQueue.front(); nodeQueue.pop();
19 int depth = depthQueue.front(); depthQueue.pop();
20
21 if (node != NULL) {
22 max_depth = max(max_depth, depth);
23
24 rightmostValueAtDepth[depth] = node->val;
25
26 nodeQueue.push(node->left);
27 nodeQueue.push(node->right);
28
29 depthQueue.push(________);
30 depthQueue.push(________);
31 }
32 }
33
34 vector rightView;
35 for (int depth = 0; ________; ++depth) {
36 rightView.push_back(rightmostValueAtDepth[depth]);
37 }
38 return rightView;
39 };
```
- ```cpp
01 depth
02 depth
03 depth < max_depth
```
- ```cpp
01 depth + 1
02 depth + 1
03 depth <= max_depth
```
- ```cpp
01 depth + 1
02 depth + 1
03 depth < max_depth
```
- ```cpp
01 depth
02 depth
03 depth <= max_depth
```
**第 13 题** 下列关于树的深度优先搜索$(DFS)$ 的说法中，正确的是 ( )
- 对树进行 $DFS$ 时，一定是按层从上到下依次访问结点
- 对任意一棵树进行 $DFS$，得到的遍历序列唯一
- 对一棵树进行 $DFS$ 时，常借助递归或栈实现
- $DFS$ 只能用于二叉树，不能用于普通树
**第 14 题** 小朋友们去邻里拜年，每个家里有不同数量的糖果。规则是:不能连续进入两个相邻的房子(即不能同时取相邻两家的糖果)。目标是拿到最多糖果。以下是代码实现，请补全横线。( )
```cpp
01 int visit(vector& nums) {
02 if (nums.empty()) {
03 return 0;
04 }
05 int size = nums.size();
06 if (size == 1) {
07 return nums[0];
08 }
09 vector dp = vector(size, 0);
10 dp[0] = nums[0];
11 dp[1] = max(nums[0], nums[1]);
12
13 for (int i = 2; i < size; i++) {
14 dp[i] = ______; // 在此处填写代码
15 }
16
17 return dp[size - 1];
18 }
```
- `dp[i] = dp[i - 1] + nums[i];`
- `dp[i]= max(dp[i - 1],dp[i - 2] * nums[i]);`
- `dp[i] = max(dp[i - 1],dp[i - 2] + nums[i]);`
- `dp[i] = dp[i - 2] + nums[i];`
**第 15 题** 元宵节晚上，小朋友沿着一条发光石板路前进，每次可向前走 $1$ 块或$2$ 块石板。动态规划定义如下:`dp[i]=dp[i -1]+dp[i -2]`，下面关于 `dp[i]` 的含义最合适的是 ( )
- 走到第 $i$ 块石板的不同走法数量
- 走到第 $i$ 块石板时，已经走过的石板总数
- 从第 $i$ 块石板走回起点的最少步数
- 从第 $i$ 块石板走回起点的最大步数
## 二、判断题（每题 2 分，共 20 分）
**第 1 题** 下面定义了一个表示二维坐标点的类 `Point`，并提供了一个带参数的构造函数，但第 $2$ 行 `Point b`;会调用编译器自动生成的默认构造函数，将 `b.x` 和`b.y` 初始化为 $0.0$，程序可以正常编译运行。
```cpp
01 class Point {
02 public:
03 double x, y;
04 Point(double px, double py) : x(px), y(py) {}
05 void print() {
06 cout << "(" << x << ", " << y << ")";
07 }
08 };
09
10 int main() {
11 Point a(3.0, 4.0); // ①
12 Point b; // ②
13 a.print();
14 }
```
- 正确
- 错误
**第 2 题** `C++` 中的继承支持单继承和多继承，但子类无法直接访问父类的私有成员。
- 正确
- 错误
**第 3 题** 对如下结构的树，执行 `travel` 函数，输出结果是 `1 2 3 4 5`。
```cpp
1
/ \
2 3
/ \
4 5
```
```cpp
01 struct Node {
02 int val;
03 Node *left, *right;
04 Node(int v) : val(v), left(nullptr), right(nullptr) {}
05 };
06
07 void travel(Node* root) {
08 if (!root) return;
09 stack s;
10 s.push(root);
11
12 while (!s.empty()) {
13 Node* cur = s.top(); s.pop();
14 cout << cur->val << " ";
15
16 if (cur->right) s.push(cur->right);
17 if (cur->left) s.push(cur->left);
18 }
19 }
```
- 正确
- 错误
**第 4 题** 若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。
- 正确
- 错误
**第 5 题** 哈夫曼编码是一种变长的前缀编码，在解码时不需要额外的分隔符就能唯一还原，这是因为在哈夫曼树中，任何一个字符的叶子结点都不会成为另一个字符结点的祖先。
- 正确
- 错误
**第 6 题** 在 `C++` 中使用一维数组 `vectortree` 存储按层序遍历的完全二叉树时，若根节点存储在 `tree[0]`，则对于任意非空节点 `tree[i]`，其右孩子(如果存在)必然位于 `tree[2*i+2]`。
- 正确
- 错误
**第 7 题** 在 `C-+` 中使用栈来非递归地实现二叉树的前序遍历时，为了保证遍历顺序正确，在处理完当前结点后，应该先将该结点的左孩子压入栈中，然后再将右孩子压入栈中。
- 正确
- 错误
**第 8 题** 设二叉树共有 $n$ 个结点，函数 `preorderTraversal` 以下代码的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。
```cpp
01 struct TreeNode {
02 int val;
03 TreeNode* left;
04 TreeNode* right;
05 TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06 };
07
08 void preorder(TreeNode *root, vector &res) {
09 if (root == nullptr) {
10 return;
11 }
12 res.push_back(root->val);
13 preorder(root->left, res);
14 preorder(root->right, res);
15 }
16
17 vector preorderTraversal(TreeNode *root) {
18 vector res;
19 preorder(root, res);
20 return res;
21 };
```
- 正确
- 错误
**第 9 题** 下列代码实现了一个 $0-1$ 背包的一维动态规划代码，内层循环是经典的逆序写法。若将内层循环改成正序遍历(即 `for(intj=w[i];j<=W;j++)`)，仍能得到正确答案。
```cpp
01 int main() {
02 int W = 5;
03 int w[] = {2, 3, 4};
04 int v[] = {10, 1, 1};
05 int n = 3;
06 int dp[6] = {0};
07
08 for (int i = 0; i < n; i++) {
09 for (int j = W; j >= w[i]; j--) { // ← 逆序！
10 dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
11 }
12 }
13 cout << dp[W];
14 }
```
- 正确
- 错误
**第 10 题** 在动态规划问题中，状态空间相同且没有重复计算的情况下，“状态转移方程+递推”与“递归+记忆化搜索”的时间复杂度通常相同。
- 正确
- 错误