Description
**一.单选题(每题2分，共30分)**
1. 以下（ ） 没有涉及 C++ 语⾔的⾯向对象特性⽀持。
- C++ 中构造⼀个 class 或 struct
- C++ 中调⽤ printf 函数
- C++ 中调⽤⽤户定义的类成员函数
- C++ 中构造来源于同⼀基类的多个派⽣类
2. 关于以下C++代码， （ ） ⾏代码会引起编译错误。
```cpp
#include
using namespace std;
class Base {
private:
int a;
protected:
int b;
public:
int c;
Base() : a(1), b(2), c(3) {}
};
class Derived : public Base {
public:
void show() {
cout << a << endl; // Line 1
cout << b << endl; // Line 2
cout << c << endl; // Line 3
}
};
```
- Line 1
- Line 2
- Line 3
- 没有编译错误
3. 有6个元素， 按照 6,5,4,3,2,1 的顺序进⼊栈S， 下列（ ） 的出栈序列是不能出现的（ ） 。
- `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. 采⽤如下代码实现检查输⼊的字符串括号是否匹配， 横线上应填⼊的代码为
```cpp
#include
#include
#include
using namespace std;
bool is_valid(string s) {
stack st;
char top;
for (char& ch : s) {
if (ch == '(' || ch == '{' || ch == '[') {
st.push(ch); // 左括号入栈
}
else
{
if (st.empty())
return false;
———————————————————————— // 在此处填入代码
if ((ch == ')' && top != '(') ||
(ch == '}' && top != '{') ||
(ch == ']' && top != '[')) {
return false;
}
}
}
return st.empty(); // 栈为空则说明所有括号匹配成功
}
```
- `top = st.top(); st.pop(); `
- `st.pop(); top = st.top(); `
- `st.pop(); top = st.front(); `
- `top = st.front(); st.pop(); `
5. 下⾯代码判断队列的第⼀个元素是否等于 ， 并删除该元素， 横向上应填写
```cpp
#include
#include
using namespace std;
bool is_front_equal(std::queue& q, int a) {
bool is_equal = false;
if (!q.empty()) {
———————————————————————— // 在此处填入代码
}
return is_equal;
}
```
- `is_equal = (q.front() == a); `
- `is_equal = (q.front() == a); `
- `q.pop(); is_equal = (q.front() == a); `
- `q.pop(); is_equal = (q.front() == a); `
6. 假设字母表 {a,b,c,d,e} 在字符串出现的频率分别为 10%， 15%， 30%， 16%， 29%。 若使⽤哈夫曼编码⽅
式对字母进⾏⼆进制编码， 则字符 abcdef 分别对应的⼀组哈夫曼编码的长度分别为
- `4, 4, 1, 3, 2 `
- `4, 4, 1, 3, 2 `
- `3, 3, 1, 2, 1 `
- `4, 4, 1, 2, 2 `
7. 以下C++代码实现 位的格雷码， 则横线上应填写 （ ）。
```cpp
#include
#include
#include
using namespace std;
// 生成 n 位的格雷码
vector generate_graycode(int n) {
vector graycode_list;
if (n <= 0) {
return graycode_list;
}
// 初始1位格雷码
graycode_list.push_back("0");
graycode_list.push_back("1");
// 迭代生成 n 位的格雷码
for (int i = 2; i = 0; j--) {
graycode_list.push_back("1" + graycode_list[j]);
}
for (int j = 0; j left);
int right_depth = max_depth(root->right);
———————————————————————— // 在此处填入代码
}
```
- `return left_depth + right_depth; `
- `return max(left_depth, right_depth); `
- `return max(left_depth, right_depth); `
- `return left_depth + right_depth + 1; `
11. 上⼀题的⼆叉树深度计算还可以采⽤⼆叉树的⼴度优先搜索来实现。 以下基于⼆叉树的⼴度优先搜索实现
的深度计算函数中横线上应填写
```cpp
#include
int max_depth_bfs(tree_node* root) {
if (root == nullptr) {
return 0; // 如果树为空， 深度为 0
}
queue q;
q.push(root);
int depth = 0;
// 使用队列进行层序遍历
while (!q.empty()) {
———————————————————————— // 在此处填入代码
for (int i = 0; i left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}
return depth;
}
```
- `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. ⼆叉搜索树中的每个结点， 其左⼦树的所有结点值都⼩于该结点值， 右⼦树的所有结点值都⼤于该结点值。 以下代码对给定的整数数组(假设数组中没有数值相等的元素)， 构造⼀个对应的⼆叉搜索树， 横线上应填写
```cpp
/ 定义二叉树的结点结构
struct tree_node {
int val;
tree_node* left;
tree_node* right;
tree_node(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 插入结点到二叉搜索树中
tree_node* insert(tree_node* root, int val) {
if (root == nullptr) {
return new tree_node(val);
}
———————————————————————— // 在此处填入代码
return root;
}
// 根据给定数组构造二叉搜索树
tree_node* constructBST(const int arr[], int size) {
tree_node* root = nullptr;
for (int i = 0; i < size; ++i) {
root = insert(root, arr[i]);
}
return root;
}
```
- ```cpp
if (val val)
root->left = insert(root->left, val);
else
root->right = insert(root->right, val);
- ```cpp
if (val > root->val)
root->left = insert(root->left, val);
else
root->right = insert(root->right, val);
- ```cpp
if (val val)
root->left = insert(root, val);
else
root->right = insert(root, val);
- ```cpp
if (val > root->val)
root->left = insert(root, val);
else
root->right = insert(root, val);
13. 对上题中的⼆叉搜素树， 当输⼊数组为 时， 构建⼆叉搜索树， 并采⽤如下代码实现的遍历⽅式， 得到
的输出是
```cpp
#
include
using namespace std;
// 遍历二叉搜索树， 输出结点值
void traversal(tree_node* root) {
if (root == nullptr) {
return;
}
traversal(root->left);
cout <val <right);
}
- `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. 动态规划通常⽤于解决
- ⽆法分解的问题
- 可以分解成相互依赖的⼦问题的问题
- 可以通过贪⼼算法解决的问题
- 只能通过递归解决的问题
15. 阅读以下⽤动态规划解决的0-1背包问题的函数， 假设背包的W容量 是10kg， 假设输⼊4个物品的重量weights分别为1,3,4,6 （单位为kg） ， 每个物品对应的价值values分别为20,30,50,60 ， 则函数的输出为
```cpp
#include
#include
using namespace std;
// 0/1背包问题
int knapsack(int W, const vector& weights, const vector& values, int n) {
vector<vector> dp(n + 1, vector(W + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int w = 0; w <= W; ++w) {
if (weights[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] +values[i - 1]);
}
else
{
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
```
- $90$
- $100$
- $110$
- $140$
**二.判断题(每题2分，共20分)**
16. C++、 Python和JAVA等都是⾯向对象的编程语⾔。
- 正确
- 错误
17. 在C++中， 类的静态成员变量只能被该类对象的成员函数访问。
- 正确
- 错误
18. 栈是⼀种线性结构， 可通过数组或链表来实现。 ⼆者相⽐， 数组实现占⽤的内存较少， 链表实现的⼊队和出队操作的时间复杂度较低。
- 正确
- 错误
19. 运⾏以下C++代码， 屏幕将输出“derived class”。
```cpp
#include
using namespace std;
class base {
public:
virtual void show() {
cout << "base class" << endl;
}
};
class derived : public base {
public:
void show() override {
cout << "derived class" <show();
return 0;
}
```
- 正确
- 错误
20. 如下列代码所⽰的基类（base） 及其派⽣类（derived） ， 则⽣成⼀个派⽣类的对象时， 只调⽤派⽣类的构造函数
```cpp
#include
using namespace std;
class base {
public:
base() {
cout << "base constructor" << endl;
}
~base() {
cout << "base destructor" << endl;
}
};
class derived : public base {
public:
derived() {
cout << "derived constructor" << endl;
}
~derived() {
cout << "derived destructor" << endl;
}
};
```
- 正确
- 错误
21. 哈夫曼编码本质上是⼀种贪⼼策略。
- 正确
- 错误
22. 如果根结点的深度记为1， 则⼀棵恰有2024个叶结点的⼆叉树的深度最少是12 。
- 正确
- 错误
23. 在⾮递归实现的树的⼴度优先搜索中， 通常使⽤栈来辅助实现。
- 正确
- 错误
24. 状态转移⽅程是动态规划的核⼼， 可以通过递推⽅式表⽰问题状态的变化。
- 正确
- 错误
25. 应⽤动态规划算法时， 识别并存储重叠⼦问题的解是必须的。
- 正确
- 错误
Source
GESP真题
