Description
**一.单选题(每题2分，共30分)**
1. ⾯向对象编程(OOP)是⼀种特殊的程序设计⽅法。下⾯( )不是重要的OOP特性。
- 抽象
- 封装
- 继承
- 模块化
2. 以下关于C++中类的说法，哪⼀项是正确的？
- 类中定义的所有成员变量和成员函数默认是public 访问权限。
- 类的构造函数必须显式声明返回类型为void 。
- 在C++中，类的数据⼀般设置为私有，其公有成员函数提供访问私有数据的唯⼀途径。
- 同⼀个类的实例有各⾃的成员数据和成员函数。
3. 以下C++代码段中存在语法错误或逻辑错误，（ ）是正确的。
``` cpp
#include
using namespace std;
class MyClass {
public:
MyClass() {
cout << "Constructor called!" << endl;
}
void display() {
cout << "Display function called!" <display();
return 0;
}
```
- NULL 在C++中⽆法⽤于指针初始化，应使⽤ nullptr 。
- obj 的定义应该是 MyClass obj; ⽽不是指针类型。
- obj->display() 语句存在空指针访问错误， obj 应该初始化为⼀个有效的对象。
- obj->display() 语句会调⽤ display() 函数，但它没有输出任何内容。
4. 阅读以下代码，下⾯哪⼀项是正确的？
```cpp
void processData() {
stack s;
queue q;
for (int i = 1; i <= 5; ++i) {
s.push(i);
q.push(i);
}
while (!s.empty()) {
cout << "Stack pop: " << s.top() << endl;
s.pop();
}
while (!q.empty()) {
cout << "Queue pop: " << q.front() << endl;
q.pop();
}
}
```
- 栈s的输出顺序是1 2 3 4 5，队列q的输出顺序是5 4 3 2 1。
- 栈s的输出顺序是5 4 3 2 1，队列q的输出顺序是1 2 3 4 5。
- 栈s的输出顺序是1 2 3 4 5，队列q的输出顺序是1 2 3 4 5。
- 栈s 的输出顺序是1 2 3 4 5，队列q的输出顺序是 1 2 3 4 5，程序不会正常执⾏。
5. N个节点的双向循环链，在其中查找某个节点的平均时间复杂度是( )。
- O(1)
- O(N)
- O(logN)
- $O(N^3)$
6. 以下关于树的说法，（ ）是正确的。
- 在⼀棵⼆叉树中，叶⼦结点的度⼀定是2。
- 满⼆叉树中每⼀层的结点数等于$O(2^{层数-1})$
- 在⼀棵树中，所有结点的度之和等于所有叶⼦结点的度之和。
- ⼀棵⼆叉树的先序遍历结果和中序遍历结果⼀定相同。
7. 已知字符集 {A, B, C, D} 的出现频率如下表所⽰：
根据哈夫曼编码法，下⾯（ ）是正确的哈夫曼树。
- 
- 
- 
- 
8. 上⼀题中各字符的哈夫曼编码是（ ）。
- A: 0, B: 10, C: 110, D: 111
- A: 0, B: 10, C: 11, D: 10
- A: 0, B: 101, C: 100, D: 11
- A: 11, B: 10, C: 01, D: 00
9. ( )是位格雷编码。
- 000 001 011 010 110 111 101 100
- 000 001 010 011 100 101 110 111
- 000 001 100 101 011 010 111 110
- 000 010 001 011 100 110 101 111
10. 根据下⾯⼆叉树和给定的代码，
```cpp
#include
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* search(TreeNode* root, int val) {
cout <val <val == val) return root;
if (val val)
return search(root->left, val);
else
return search(root->right, val);
}
```
给定以下⼆叉搜索树，调⽤函数 search(root,7) 时，输出的结果是（ ）。
- 5 3 7
- 5 7
- 2 3 4 5 6 7
- 8 7
11. 阅读以下⼆叉树的深度优先搜索算法，横线上应填写
```cpp
void dfs(TreeNode* root) {
if (root == nullptr)
return;
stack s;
s.push(root);
while (!s.empty()) {
———————————————————————— // 在此处填入代码
cout <value <right) s.push(node->right);
if (node->left) s.push(node->left);
}
}
```
- `TreeNode* node = s.top();`
- `TreeNode* node = s.top(); s.pop();`
- `TreeNode* node = s.front();`
- `TreeNode* node = s.front(); s.pop();`
12. 阅读以下⼆叉树的⼴度优先搜索的代码，横线上应填写
```cpp
#include
void bfs(TreeNode* root) {
if (root == NULL) return;
queue q;
q.push(root);
while (!q.empty()) {
———————————————————————— // 在此处填入代码
cout <val <left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}
```
- `TreeNode* node = q.top();`
- `TreeNode* node = q.top(); q.pop();`
- `TreeNode* node = q.front();`
- `TreeNode* node = q.front(); q.pop();`
13. 使⽤上题中的宽度优先搜索算法遍历以下这棵树，可能的输出是( )。
- 1 2 8 9 4 5 3 6 7
- 1 2 3 4 5 6 6 8 9
- 1 2 3 8 9 6 4 5 7
- 8 4 5 9 2 1 3 6 7
14. 以下关于动态规划的描述，（ ）是正确的。
- 动态规划适⽤于没有重叠⼦问题的优化问题。
- 动态规划要求问题具有最优⼦结构和⽆后效性。
- 动态规划通常通过递归来实现。
- 动态规划与贪⼼算法不同，贪⼼算法不适⽤于有重叠⼦问题的问题。
15. 假设背包的最⼤容量W=8kg，共有有4个物品可供选择，4个物品的重量分别为weights=[2,3,5,7]，对应 的价值分别为values=[30,40,60,80] ，则该0/1背包问题中，背包的最⼤价值为（ ）。
- $70$
- $90$
- $100$
- $120$
**二.判断题(每题2分，共20分)**
16. 构造函数是⼀种特殊的类成员函数，构造函数的名称和类名相同。但通过函数重载，可以创建多个同名的构 造函数，条件是每个构造函数的参数列表不同。
- 正确
- 错误
17. 类的静态成员函数既能访问类的静态数据成员，也能访问⾮静态数据成员。
- 正确
- 错误
18. 栈中元素的插⼊和删除操作都在栈的顶端进⾏，所以⽅便⽤单向链表实现。
- 正确
- 错误
19. 下⾯代码构建的树⼀定是完全⼆叉树：
```cpp
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;
};
TreeNode* buildCompleteBinaryTree() {
TreeNode* root = new TreeNode{1};
root->left = new TreeNode{2};
root->right = new TreeNode{3};
root->left->left = new TreeNode{4};
root->left->right = new TreeNode{5};
root->right->left = new TreeNode{6};
return root;
}
```
- 正确
- 错误
20. 在⼆叉排序树中，左⼦树所有节点的值都⼤于根节点的值，右⼦树所有节点的值都⼩于根节点的值。
- 正确
- 错误
21. 在⽣成⼀个派⽣类的对象时，只调⽤派⽣类的构造函数。
- 正确
- 错误
22. 下⾯的代码实现了⼆叉树的前序遍历，它通过递归⽅法访问每个节点并打印节点值。
```cpp
void preorder(TreeNode* root) {
if (root == NULL) return;
cout <val <left);
preorder(root->right);
}
```
- 正确
- 错误
23. 宽度优先搜索算法（BFS）保证了每个节点在最短路径的情况下被访问。
- 正确
- 错误
24. 在解决简单背包问题时，动态规划的状态转移⽅程如下：
```
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
```
该⽅程表⽰：在考虑第 i 个物品时，当前背包容量为 w，如果不放物品 i，则最⼤价值是 放⼊物品 i，则最⼤价值是 `dp[i-1][w] `；如果 `dp[i-1][w - weights[i-1]] + values[i-1]` ，其中数组 weights 和 values 分 别表⽰所有物品的重量和价值，数组下标从0开始。
- 正确
- 错误
25. 栈中元素的插⼊和删除操作都在栈的顶端进⾏，所以⽅便⽤双向链表⽐单向链表更合适表实现。
- 正确
- 错误
Source
GESP真题
