GESP C++ 六级 · 2024 年 12 月认证理论卷

1. 面向对象编程(OOP)是一种特殊的程序设计方法。下面（ ）不是重要的OOP特性。

2. 以下关于C++中类的说法，哪一项是正确的？

3. 以下C++代码段中存在语法错误或逻辑错误，（ ）是正确的。 ```cpp #include <iostream> using namespace std; class MyClass { public: MyClass() { cout << "Constructor called!" << endl; } void display() { cout << "Display function called!" << endl; } }; int main() { MyClass* obj = NULL; obj->display(); return 0; } ```

4. 阅读以下代码，下面哪一项是正确的？ ```cpp void processData() { stack<int> s; queue<int> 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(); } } ```

5. $n$ 个节点的双向循环链表，在其中查找某个节点的平均时间复杂度是（ ）。

6. 以下关于树的说法，（ ）是正确的。

7. 已知字符集 $\{A, B, C, D\}$ 的出现频率如下表所示： | 字符 | 频率 | | :--- | :--- | | A | 8 | | B | 3 | | C | 1 | | D | 6 | 根据哈夫曼编码法，下面（ ）是正确的哈夫曼树。

8. 上一题中各字符的哈夫曼编码是（ ）。

9. （ ）是3位格雷编码。

10. 根据下面二叉树和给定的代码， ```cpp #include <iostream> 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 << root->val << " "; if (root == NULL || root->val == val) return root; if (val < root->val) return search(root->left, val); else return search(root->right, val); } ``` 给定以下二叉搜索树，调用函数 `search(root,7)` 时，输出的结果是（ ）。 ``` 5 / \ 3 7 / \ / \ 2 4 6 8 ```

11. 阅读以下二叉树的深度优先搜索算法，横线上应填写（ ）。 ```cpp void dfs(TreeNode* root) { if (root == nullptr) return; stack<TreeNode*> s; s.push(root); while (!s.empty()) { ________________________________ // 在此处填入代码 cout << node->value << " "; if (node->right) s.push(node->right); if (node->left) s.push(node->left); } } ```

12. 阅读以下二叉树的广度优先搜索的代码，横线上应填写（ ）。 ```cpp #include <queue> void bfs(TreeNode* root) { if (root == NULL) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { ________________________________ // 在此处填入代码 cout << node->val << " "; if (node->left) { q.push(node->left); } if (node->right) { q.push(node->right); } } } ```

13. 使用上题中的宽度优先搜索算法遍历以下这棵树，可能的输出是（ ）。 ``` 1 / \ 2 3 / \ \ 8 9 6 / \ \ 4 5 7 ```

14. 以下关于动态规划的描述，（ ）是正确的。

15. 假设背包的最大容量为 $W = 8kg$，共有4个物品可供选择，4个物品的重量分别为 $weights = [2, 3, 5, 7]$，对应的价值分别为 $values = [30, 40, 60, 80]$，则该0/1背包问题中，背包的最大价值为（ ）。

1. 构造函数是一种特殊的类成员函数，构造函数的名称和类名相同。但通过函数重载，可以创建多个同名的构造函数，条件是每个构造函数的参数列表不同。 ( )

2. 类的静态成员函数既能访问类的静态数据成员，也能访问非静态数据成员。 ( )

3. 栈中元素的插入和删除操作都在栈的顶端进行，所以方便用单向链表实现。 ( )

4. 下面代码构建的树一定是完全二叉树： ```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; } ``` ( )

5. 在二叉排序树中，左子树所有节点的值都大于根节点的值，右子树所有节点的值都小于根节点的值。 ( )

6. 在生成一个派生类的对象时，只调用派生类的构造函数。 ( )

7. 下面的代码实现了二叉树的前序遍历，它通过递归方法访问每个节点并打印节点值。 ```cpp void preorder(TreeNode* root) { if (root == NULL) return; cout << root->val << " "; preorder(root->left); preorder(root->right); } ``` ( )

8. 宽度优先搜索算法（BFS）保证了每个节点在最短路径的情况下被访问。 ( )

9. 在解决简单背包问题时，动态规划的状态转移方程如下： ```cpp dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]); ``` 该方程表示：在考虑第 $i$ 个物品时，当前背包容量为 $w$，如果不放物品 $i$，则最大价值是 `dp[i-1][w]`；如果放入物品 $i$，则最大价值是 `dp[i-1][w - weights[i-1]] + values[i-1]`，其中数组 `weights` 和 `values` 分别表示所有物品的重量和价值，数组下标从0开始。 ( )

10. 栈中元素的插入和删除操作都在栈的顶端进行，所以方便用双向链表比单向链表更合适来实现。 ( )