测验 · 佛大附属信奥 OJ

1. 在面向对象编程中，下列关于**虚函数**的描述中，错误的是（）。

A. 虚函数用于支持运行时多态 B. 通过基类指针调用虚函数时，会根据对象实际类型决定调用版本 C. 构造函数可以声明为虚函数以支持多态 D. 基类析构函数常声明为虚函数以避免资源泄漏

2. 执行如下代码，会输出"钢琴：叮咚叮咚"和"吉他：咚咚当当"。这体现了面向对象编程的（）特性。 ```cpp class Instrument { public: virtual void play() { cout << "乐器在演奏声音" << endl; } virtual ~Instrument() {} }; class Piano : public Instrument { public: void play() override { cout << "钢琴：叮咚叮咚" << endl; } }; class Guitar : public Instrument { public: void play() override { cout << "吉他：咚咚当当" << endl; } }; int main() { Instrument* instruments[2]; instruments[0] = new Piano(); instruments[1] = new Guitar(); for (int i = 0; i < 2; ++i) { instruments[i]->play(); } for (int i = 0; i < 2; ++i) { delete instruments[i]; } return 0; } ```

A. 继承 B. 封装 C. 多态 D. 链接

3. 关于以下代码，说法正确的是（）。 ```cpp class Instrument { public: void play() { cout << "乐器在演奏声音" << endl; } virtual ~Instrument() {} }; class Piano : public Instrument { public: void play() override { cout << "钢琴：叮咚叮咚" << endl; } }; class Guitar : public Instrument { public: void play() override { cout << "吉他：咚咚当当" << endl; } }; int main() { Instrument* instruments[2]; instruments[0] = new Piano(); instruments[1] = new Guitar(); for (int i = 0; i < 2; ++i) { instruments[i]->play(); } for (int i = 0; i < 2; ++i) { delete instruments[i]; } return 0; } ```

A. 执行代码会输出两行，内容分别为：钢琴：叮咚叮咚和吉他：咚咚当当 B. 执行代码会输出两行，内容分别为：乐器在演奏声音和乐器在演奏声音 C. 代码编译出现错误 D. 代码运行出现错误

4. 某文本编辑器把用户输入的字符依次压入栈 $S$。用户依次输入 A, B, C, D 后，用户按了两次撤销（每次撤销，弹出栈顶一个字符）。此时栈从栈底到栈顶的内容是：（）。

A. A B B. A B C C. A B D D. B C

5. 假设循环队列数组长度为 $N$，其中队空判断条件为：`front == rear`，队满判断条件为：`(rear + 1) % N == front`，出队对应的操作为：`front = (front + 1) % N`，入队对应的操作为：`rear = (rear + 1) % N`。循环队列长度 $N = 6$，初始 $front = 1, rear = 1$，执行操作序列为：入队, 入队, 入队, 出队, 入队, 入队，则最终 $(front, rear)$ 的值是（）。

A. $(2, 5)$ B. $(2, 0)$ C. $(3, 5)$ D. $(3, 0)$

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) { hasNull = true; } else { if (hasNull) return false; q.push(cur->left); q.push(cur->right); } } return true; } ```

A. 满二叉树 B. 完全二叉树 C. 二叉搜索树 D. 平衡二叉树

7. 以下代码实现了二叉树的（）。 ```cpp void traverse(TreeNode* root) { if (!root) return; traverse(root->left); traverse(root->right); cout << root->val << " "; } ```

A. 前序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历

8. 下面代码实现了哈夫曼编码，则横线处应填写的代码是（）。 ```cpp struct Symbol { char ch; //字符 long long freq; //频率 string code; //哈夫曼编码 }; struct Node { long long w; //权值 int l, r; //左右孩子（节点下标），-1 表示空 int sym; // 叶子对应符号下标；内部节点为 -1 Node(long long _w=0, int _l=-1, int _r=-1, int _sym=-1) : w(_w), l(_l), r(_r), sym(_sym) {} }; // 从 A(leafIdx) 和 B(internalIdx) 的队首取最小的一个节点下标 static int PopMinNode(const vector<Node>& nodes, const vector<int>& leafIdx, int n, int& pA, const vector<int>& internalIdx, int& pB) { if (pA < n && (pB >= (int)internalIdx.size() || nodes[leafIdx[pA]].w <= nodes[internalIdx[pB]].w)) { return leafIdx[pA++]; } else { return internalIdx[pB++]; } } // DFS 生成编码（左 0，右 1） static void DFSBuildCodes(int u, const vector<Node>& nodes, Symbol sym[], string& path) { if (u == -1) return; if (nodes[u].sym != -1) { // 叶子 sym[nodes[u].sym].code = path; return; } path.push_back('0'); DFSBuildCodes(nodes[u].l, nodes, sym, path); path.pop_back(); path.push_back('1'); DFSBuildCodes(nodes[u].r, nodes, sym, path); path.pop_back(); } int BuildHuffmanCodes(Symbol sym[], int n) { for (int i = 0; i < n; i++) sym[i].code.clear(); if (n <= 0) return -1; // 只有一个字符：约定编码为 "0" if (n == 1) { sym[0].code = "0"; return 0; } vector<Node> nodes; nodes.reserve(2 * n); // 1) 建立叶子节点 vector<int> leafIdx(n); for (int i = 0; i < n; i++) { leafIdx[i] = (int)nodes.size(); nodes.push_back(Node(sym[i].freq, -1, -1, i)); } // 2) 叶子按权值排序（A 队列） sort(leafIdx.begin(), leafIdx.end(), [&](int a, int b) { if (nodes[a].w != nodes[b].w) return nodes[a].w < nodes[b].w; return nodes[a].sym < nodes[b].sym; // 稳定一下 }); // B 队列（内部节点下标队列） vector<int> internalIdx; internalIdx.reserve(n); int pA = 0, pB = 0; // 3) 合并 n-1 次 for (int k = 1; k < n; k++) { int x = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB); int y = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB); int z = (int)nodes.size(); ________________________ // 在此处填写代码 } int root = internalIdx.back(); // 4) DFS 生成编码 string path; DFSBuildCodes(root, nodes, sym, path); return root; } ```

A. ```cpp nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1)); internalIdx.push_back(z); ``` B. ```cpp nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1)); leafIdx.push_back(z); ``` C. ```cpp internalIdx.push_back(z); nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y)); ``` D. ```cpp nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y)); leafIdx.push_back(z); ```

9. 以下关于哈夫曼编码的说法，正确的是（）。

A. 哈夫曼编码是定长编码 B. 哈夫曼编码中，没有任何一个字符的编码是另一个字符编码的前缀 C. 哈夫曼编码一定唯一 D. 哈夫曼编码不能用于数据压缩

10. 以下函数实现了二叉排序树（BST）的（）操作。 ```cpp TreeNode* op(TreeNode* root, int x) { if (!root) return new TreeNode(x); if (x < root->val) root->left = op(root->left, x); else root->right = op(root->right, x); return root; } ```

A. 查找 B. 插入 C. 删除 D. 遍历

11. 下列代码实现了树的深度优先遍历，则横线处应填入（）。 ```cpp struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x): val(x), left(nullptr), right(nullptr) {} }; void dfs(TreeNode* root) { if (!root) return; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); cout << node->val << " "; if (node->right) st.push(node->right); ________________________ } } ```

A. `if (node->left) st.push(node->left);` B. `if (node->left) st.pop(node->left);` C. `if (node->left) st.front(node->left);` D. `if (node->left) st.push(node->right);`

12. 给定一棵普通二叉树（节点值没有大小规律），下面代码判断是否存在值为 $x$ 的结点，则横线处应填入（）。 ```cpp struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x): val(x), left(nullptr), right(nullptr) {} }; TreeNode* bfsFind(TreeNode* root, int x) { if (!root) return nullptr; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* cur = q.front(); q.pop(); if (cur->val == x) return cur; ________________________ } return nullptr; } ```

A. `q.push(cur);` B. `if (cur->right) q.push(cur->right);` C. ```cpp if (cur->left) q.push(cur->left); if (cur->right) q.push(cur->right); ``` D. ```cpp q.push(cur->left); q.push(cur->right); ```

13. 在二叉排序树（Binary Search Tree, BST）中，假设节点值互不相同。给定如下搜索函数，以下说法一定正确的是（）。 ```cpp bool find(Node* root, int x) { while (root) { if (root->val == x) return true; root = (x < root->val) ? root->left : root->right; } return false; } ```

A. 最坏情况下，访问结点数是 $O(\log n)$ B. 最坏情况下，访问结点数是 $O(n)$ C. 无论如何，访问结点数都不超过树高的一半 D. 一定比在普通二叉树中搜索快

14. $0/1$ 背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是（）。 ```cpp for each item (w, v): for (int j = W; j >= w; --j) dp[j] = max(dp[j], dp[j-w] + v); ```

A. 内层 $j$ 必须从小到大，否则会漏解 B. 内层 $j$ 必须从大到小，否则同一件物品会被用多次 C. $j$ 从大到小或从小到大都一样 D. 只要 $dp$ 初始为 $0$，方向无所谓

15. 以下关于动态规划的说法中，错误的是（）。

A. 动态规划方法通常能够列出递推公式。 B. 动态规划方法的时间复杂度通常为$O(状态的个数)$。 C. 动态规划方法有递推和递归两种实现形式。 D. 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

1. 以下代码中，构造函数被调用的次数是1次。 ```cpp class Test { public: Test() { cout << "T "; } }; int main() { Test a; Test b = a; } ``` ( )

对错

2. 面向对象编程中，封装是指将数据和操作数据的方法绑定在一起，并对外隐藏实现细节。 ( )

对错

3. 以下代码能够正确统计二叉树中叶子结点的数量。 ```cpp int countLeaf(TreeNode* root) { if (!root) return 0; if (!root->left && !root->right) return 1; return countLeaf(root->left) + countLeaf(root->right); } ``` ( )

对错

4. 广度优先遍历二叉树可用栈来实现。 ( )

对错

5. 函数调用管理可用栈来管理。 ( )

对错

6. 在二叉排序树（BST）中，若某结点的左子树为空，则该结点一定是整棵树中的最小值结点。 ( )

对错

7. 下面的函数能正确判断一棵树是不是二叉排序树（左边的数字要比当前数字小，右边的数字要比当前数字大）。 ```cpp bool isBST(TreeNode* root, int minVal, int maxVal) { if (!root) return true; if (root->val <= minVal || root->val >= maxVal) return false; return isBST(root->left, minVal, root->val) && isBST(root->right, root->val, maxVal); } ``` ( )

对错

8. 格雷编码相邻两个编码之间必须有多位不同，以避免数据传输错误。 ( )

对错

9. 小杨在玩一个闯关游戏，从第1关走到第4关。每一关的体力消耗如下（下标表示关卡编号）：$cost = [0, 3, 5, 2, 4]$，其中 $cost[i]$ 表示到达第 $i$ 关需要消耗的体力，$cost[0]=0$ 表示在开始状态，体力消耗为 $0$。小杨每次可以从当前关卡前进 $1$ 步或 $2$ 步。按照上述规则，从第 $1$ 关到第 $4$ 关所需消耗的最小体力为 $7$。 ( )

对错

10. 假定只有一个根节点的树的深度为 $1$，则一棵有 $n$ 个节点的完全二叉树，则树的深度为 $\lfloor \log_2 n \rfloor + 1$。 ( )

对错

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

一、单选题(每题 2 分)

二、判断题(每题 2 分)