GESP C++ 六级 · 2026 年 6 月认证理论卷

1. 下列关于 C++ 中继承和多态的描述中，错误的是（ ）。

2. 下列代码中，`d1->work();` 和 `d2->work();` 输出不同结果的主要原因是（ ）。 ```cpp class Device { public: virtual void work() { cout << "Device is working" << endl; } virtual ~Device() {} }; class Printer : public Device { public: void work() override { cout << "Printer is printing" << endl; } }; class Scanner : public Device { public: void work() override { cout << "Scanner is scanning" << endl; } }; int main() { Device* d1 = new Printer(); Device* d2 = new Scanner(); d1->work(); d2->work(); delete d1; delete d2; return 0; } ```

3. 下⾯代码在 `main()` 中有⼀⾏会导致编译错误，请找出来。 ```cpp class Student { public: Student(string n, int s) : name(n), score(s) {} string getName() { return name; } void setScore(int s) { score = s; } private: string name; int score; }; int main() { Student stu("Tom", 85); cout << stu.getName(); // ① stu.setScore(90); // ② stu.score = 100; // ③ cout << stu.getName(); // ④ return 0; } ```

4. 某⽂本编辑器把⽤户输⼊的字符依次压⼊栈 S。⽤户依次输⼊ X, Y, Z, W 后，连续执⾏两次撤销操作。每次撤销都会弹出栈顶⼀个字符。此时栈从栈底到栈顶的内容是（ ）。

5. 假设循环队列数组长度为 `N = 7`，队空判断条件为 `front == rear`。⼊队和出队操作如下： ```cpp const int N = 7; int q[N]; int front = 3, rear = 3; void enqueue(int x) { q[rear] = x; rear = (rear + 1) % N; } void dequeue() { front = (front + 1) % N; } ``` 依次执⾏： ```cpp enqueue(10); enqueue(20); enqueue(30); dequeue(); enqueue(40); dequeue(); enqueue(50); ``` 最终 `(front, rear)` 的值是（ ）。

6. 以下函数 `check()` ⽤于判断⼀棵⼆叉树是否为（ ）。 ```cpp bool check(TreeNode* root) { if (!root) return true; queue<TreeNode*> q; q.push(root); bool hasNull = false; while (!q.empty()) { TreeNode* cur = q.front(); q.pop(); if (cur == nullptr) { hasNull = true; } else { if (hasNull) return false; q.push(cur->left); q.push(cur->right); } } return true; } ```

7. 以下代码实现了⼆叉树的哪种遍历⽅式？ ```cpp void traverse(TreeNode* root) { if (root == nullptr) return; cout << root->val << " "; traverse(root->left); traverse(root->right); } ```

8. 已知⼀棵⼆叉树的先序遍历序列为：`A B D E H C F G`，中序遍历序列为：`D B H E A F C G`，则该⼆叉树的后序遍历序列是（ ）。

9. 有 6 个字符，它们出现的次数分别为：$\{3, 4, 7, 8, 12, 15\}$，现在⽤哈夫曼编码为这些字符编码，最⼩加权路径长度 `WPL` 的值为（ ）。

10. 对 `n` 个不同符号进⾏哈夫曼编码。若⽣成的哈夫曼树共有 63 个结点，则 `n` 的值是（ ）。

11. 在格雷码中，相邻两个编码只能有⼀位不同。若当前编码为 `110`，则它的下⼀个编码不可能是（ ）。

12. 给定⼀棵⼆叉树，采⽤⼴度优先搜索 BFS 返回其右视图，其中右视图中的每个节点都是该层最右侧的节点。横线处应填写（ ）。 ```cpp vector<int> rightSideView(TreeNode* root) { vector<int> result; if (!root) return result; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int sz = q.size(); for (int i = 0; i < sz; ++i) { TreeNode* node = q.front(); q.pop(); __________________________ if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } return result; } ```

13. 下⾯代码实现⼆叉搜索树的插⼊操作。假设树中不存在重复值，横线处应填写（ ）。 ```cpp TreeNode* insertNode(TreeNode* root, int x) { if (root == nullptr) { return new TreeNode(x); } if (x < root->val) { __________________________ } else { root->right = insertNode(root->right, x); } return root; } ```

14. 给定⼀个整数数组 a，每个元素表⽰⼀个位置上的数值。要求从数组中选择若⼲个元素，使得任意两个被选择的元素在原数组中都不相邻，并且所选元素的总和最⼤。函数 `choose(vector<int>& a)` 返回能够得到的最⼤总和，则横线处应填写（ ）。 ```cpp int choose(vector<int>& a) { if (a.empty()) return 0; int n = a.size(); if (n == 1) return a[0]; vector<int> dp(n, 0); dp[0] = a[0]; dp[1] = max(a[0], a[1]); for (int i = 2; i < n; ++i) { dp[i] = __________________________; } return dp[n - 1]; } ```

15. 下⾯代码实现 0/1 背包的⼀维动态规划。第 i 个物品重量为 `wt[i]`，价值为 `val[i]`，背包容量为 W。横线处应填写（ ）。 ```cpp int knapsack(int W, vector<int>& wt, vector<int>& val) { int n = wt.size(); vector<int> dp(W + 1, 0); for (int i = 0; i < n; ++i) { for (int w = W; w >= wt[i]; --w) { __________________________ } } return dp[W]; } ```

1. C++ 中构造函数可以声明为虚函数，从⽽实现运⾏时多态。

2. 通过指向 Base 的指针删除 Derived 对象时，⼀定会先调⽤ Derived 的析构函数，再调⽤ Base 的析构函数。 ```cpp #include <iostream> using namespace std; class Base { public: ~Base() { cout << "Base destructor" << endl; } }; class Derived : public Base { public: ~Derived() { cout << "Derived destructor" << endl; } }; int main() { Base* p = new Derived(); delete p; return 0; } ```

3. 在 C++ STL 中，`stack` 的 `pop()` 函数会返回栈顶元素并将其删除。

4. 程序运⾏后会输出 2。 ```cpp int main() { queue<int> q; q.push(1); q.push(2); q.push(3); q.pop(); cout << q.front() << endl; return 0; } ```

5. 下列函数试图将整数 x 插⼊到⼀棵⼆叉搜索树中。假设⼆叉搜索树满⾜如下性质：对于任意结点，左⼦树中所有结点的值均⼩于该结点的值，右⼦树中所有结点的值均⼤于或等于该结点的值。判断该函数是否能够在插⼊后保持⼆叉搜索树性质。 ```cpp struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; TreeNode* insertNode(TreeNode* root, int x) { if (root == nullptr) { return new TreeNode(x); } if (x < root->val) { root->right = insertNode(root->right, x); } else { root->left = insertNode(root->left, x); } return root; } ```

6. 哈夫曼编码⼀定唯⼀，只要字符频率相同，得到的编码也⼀定完全相同。

7. 若⽤数组按层序存储完全⼆叉树，且根节点下标为 `0`，则下标为 `i` 的节点左孩⼦下标为 `2 * i + 1`，右孩⼦下标为 `2 * i + 2`。

8. 以下代码可以正确地按层换⾏输出⼆叉树的节点值。 ```cpp void printByLevel(TreeNode* root) { if (!root) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { for (int i = 0; i < q.size(); ++i) { TreeNode* cur = q.front(); q.pop(); cout << cur->val << " "; if (cur->left) q.push(cur->left); if (cur->right) q.push(cur->right); } cout << endl; } } ```

9. 使⽤栈⾮递归实现⼆叉树前序遍历时，若希望先访问左⼦树，通常应先将右孩⼦⼊栈，再将左孩⼦⼊栈。

10. 动态规划问题通常要求具有最优⼦结构，并且常常存在重叠⼦问题。