试卷总分：100分
选择题 15题 30分
判断题 10题 20分
编程题 2题 50分
执行如下代码，会输出 钢琴：叮咚叮咚 和 吉他：咚咚当当 。这体现了面向对象编程的（ ）特性。
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 < 3; ++i) { delete instruments[i]; } return 0; }
关于以下代码，说法正确的是（ ）。
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 < 3; ++i) { delete instruments[i]; } return 0; }
以下函数 check() 用于判断一棵二叉树是否为（ ）。
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; }
以下代码实现了二叉树的（ ）。
void traverse(TreeNode* root) { if (!root) return; traverse(root->left); traverse(root->right); cout << root->val << " "; }
下面代码实现了哈夫曼编码，则横线处应填写的代码是（ ）。
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; }
以下函数实现了二叉排序树（BST）的（ ）操作。
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; }
下列代码实现了树的深度优先遍历，则横线处应填入（ ）。
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); ________________________ } }
给定一棵普通二叉树（节点值没有大小规律），下面代码判断是否存在值为 x 的结点，则横线处应填入（ ）。
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; }
在二叉排序树（Binary Search Tree, BST）中，假设节点值互不相同。给定如下搜索函数，以下说法一定正确的是（ ）。
bool find(Node* root, int x) { while (root) { if (root->val == x) return true; root = (x < root->val) ? root->left : root->right; } return false; }
0/1 背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是（ ）。
for each item (w, v): for (int j = W; j >= w; --j) dp[j] = max(dp[j], dp[j-w] + v);
以下代码中，构造函数被调用的次数是1次。
class Test { public: Test() { cout << "T "; } }; int main() { Test a; Test b = a; }
以下代码能够正确统计二叉树中叶子结点的数量。
int countLeaf(TreeNode* root) { if (!root) return 0; if (!root->left && !root->right) return 1; return countLeaf(root->left) + countLeaf(root->right); }
下面的函数能正确判断一棵树是不是二叉排序树（左边的数字要比当前数字小，右边的数字要比当前数字大）。
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); }