跳到主要内容 CCF-GESP 2025 年 12 月 C++ 六级真题解析 | 极客日志
C++ 算法
CCF-GESP 2025 年 12 月 C++ 六级真题解析 本文解析了 CCF-GESP 2025 年 12 月 C++ 六级认证考试的真题,涵盖单选题、判断题及编程题。内容涉及面向对象编程特性(虚函数、多态)、数据结构(栈、队列、二叉树、哈夫曼编码)及动态规划算法(背包问题、树形 DP)。文章提供了详细的题目解析、代码实现及思路说明,帮助考生理解考点与解题技巧。
墨染流年 发布于 2026/3/29 更新于 2026/4/14 1 浏览1 单选题(每题 2 分,共 30 分)
第 1 题 在面向对象编程中,下列关于虚函数的描述中,错误的是( )。
A. 虚函数用于支持运行时多态
B. 通过基类指针调用虚函数时,会根据对象实际类型决定调用版本
C. 构造函数可以声明为虚函数以支持多态
D. 基类析构函数常声明为虚函数以避免资源泄漏
解析:答案 C。虚函数是实现运行时多态的关键机制,通过基类指针调用时会动态绑定到派生类实现,A 正确。通过基类指针调用虚函数时,会根据对象实际类型决定调用版本是虚函数的核心特性,称为动态绑定或后期绑定,B 正确。构造函数不能声明为虚函数,这是 C++ 标准规定,C 错误。虚析构函数确保派生类资源被正确释放,D 正确。故选 C。
第 2 题 执行如下代码,会输出 钢琴:叮咚叮咚 和 吉他:咚咚当当。这体现了面向对象编程的( )特性。
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 ( i = ; i < ; ++i) {
instruments[i]-> ();
}
( i = ; i < ; ++i) {
instruments[i];
}
;
}
微信扫一扫,关注极客日志 微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
Markdown 转 HTML 将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
HTML 转 Markdown 将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online
int
0
2
play
for
int
0
3
delete
return
0
解析:答案 C。该代码通过多态性实现了不同乐器的特定演奏方式。具体分析如下:基类与派生类:Instrument 是基类,定义了 play() 方法。Piano 和 Guitar 是派生类,分别重写了 play() 方法,输出特定的演奏声。多态性体现:在 main() 函数中,Instrument* instruments[2] 声明了一个基类指针数组。将 Piano 和 Guitar 对象赋值给该数组,但通过基类指针调用 play() 方法。由于 play() 方法被声明为 virtual,实际调用的是派生类的重写方法,输出:钢琴:叮咚叮咚、吉他:咚咚当当。所以是多态。故选 C。
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 ;
}
A. 执行代码会输出两行,内容分别为:钢琴:叮咚叮咚 和 吉他:咚咚当当
B. 执行代码会输出两行,内容分别为:乐器在演奏声音 和 乐器在演奏声音
C. 代码编译出现错误
D. 代码运行出现错误
解析:答案 C。程序代码,在基类 Instrument 中,play 成员函数未被声明为 virtual,因此不具备多态性。派生类 Piano 和 Guitar 中的 play 函数使用了 override 关键字,但基类中不存在可覆盖的虚函数 play,这会导致编译错误。所以 C 正确。故选 C。
第 4 题 某文本编辑器把用户输入的字符依次压入栈 S。用户依次输入 A , B , C , D 后,用户按了两次撤销(每次 撤销,弹出栈顶一个字符)。此时栈从栈底到栈顶的内容是:( )。
A. A B B. A B C C. A B D D. B C
解析:答案 A。根据题目描述,用户依次输入字符 A, B, C, D 后,栈的内容为 A, B, C, D(从栈底到栈顶)。用户按了两次撤销操作,每次撤销会弹出栈顶字符。因此,撤销两次后,栈顶的 D 和 C 被弹出,栈中剩余的字符为 A, B。故选 A。
第 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)
解析:答案 B。根据题目描述的循环队列操作规则,我们逐步分析执行操作序列后的状态变化:初始状态:front = 1, rear = 1;入队:rear = (rear + 1) % 6 = 2;入队:rear = (rear + 1) % 6 = 3;入队:rear = (rear + 1) % 6 = 4;出队:front = (front + 1) % 6 = 2;入队:rear = (rear + 1) % 6 = 5;入队:rear = (rear + 1) % 6 = 0。最终状态:front = 2, rear = 0。故选 B。
第 6 题 以下函数 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 ;
}
A. 满二叉树 B. 完全二叉树 C. 二叉搜索树 D. 平衡二叉树
解析:答案 B。程序代码使用队列,使用广度优先搜索(BFS)遍历二叉树,通过队列记录节点,按层序遍历,遇到空节点后,后续节点必须全为空。若违反此规则,返回 false。该算法判断二叉树是否为完全二叉树。故选 B。
void traverse (TreeNode* root) {
if (!root) return ;
traverse (root->left);
traverse (root->right);
cout << root->val << " " ;
}
A. 前序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历
解析:答案 C。程序代码实现二叉树的后序遍历(左 - 右 - 根),递归访问左子树,递归访问右子树,访问根节点并输出值,无显式栈或队列辅助结构。故选 C。
第 8 题 下面代码实现了哈夫曼编码,则横线处应填写的代码是( )。
struct Symbol {
char ch;
long long freq;
string code;
};
struct Node {
long long w;
int l, r;
int sym;
Node (long long _w=0 , int _l=-1 , int _r=-1 , int _sym=-1 )
: w (_w), l (_l), r (_r), sym (_sym) {}
};
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++];
}
}
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 ;
if (n == 1 ) {
sym[0 ].code = "0" ;
return 0 ;
}
vector<Node> nodes;
nodes.reserve (2 * n);
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));
}
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;
});
vector<int > internalIdx;
internalIdx.reserve (n);
int pA = 0 , pB = 0 ;
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 ();
string path;
DFSBuildCodes (root, nodes, sym, path);
return root;
}
nodes.push_back (Node (nodes[x].w + nodes[y].w, x, y, -1 ));
internalIdx.push_back (z);
nodes.push_back (Node (nodes[x].w + nodes[y].w, x, y, -1 ));
leafIdx.push_back (z);
internalIdx.push_back (z); nodes.push_back (Node (nodes[x].w + nodes[y].w, x, y, x+y));
nodes.push_back (Node (nodes[x].w + nodes[y].w, x, y, x+y));
leafIdx.push_back (z);
解析:答案 A。程序代码创建新节点:合并两个子节点 x 和 y,权值为它们之和,左右孩子分别为 x 和 y,标记为非叶子节点(sym=-1)。内部节点队列添加:新节点加入内部节点队列,用于后续合并。符合哈夫曼树构建规则:每次合并最小权值节点,生成新节点并更新队列,选择 A 选项:符合哈夫曼编码标准实现,确保正确构建最优编码树。故选 A。
第 9 题 以下关于哈夫曼编码的说法,正确的是( )。
A. 哈夫曼编码是定长编码
B. 哈夫曼编码中,没有任何一个字符的编码是另一个字符编码的前缀
C. 哈夫曼编码一定唯一
D. 哈夫曼编码不能用于数据压缩
解析:答案 B。哈夫曼编码是一种无损数据压缩算法,通过为高频字符分配短编码、低频字符分配长编码,实现高效压缩。其核心是构建哈夫曼树,确保编码无前缀冲突,广泛用于文件压缩(如 ZIP)和通信协议。所以 B 正确。故选 B。
第 10 题 以下函数实现了二叉排序树(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;
}
解析:答案 B。程序代码实现二叉搜索树的插入操作:递归查找插入位置,保持 BST 性质:左子树<根<右子树,插入新节点后返回根节点。所以 B 正确。故选 B。
第 11 题 下列代码实现了树的深度优先遍历,则横线处应填入( )。
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);
解析:答案 A。程序代码实现了树的深度优先遍历算法:使用栈结构存储待访问节点,先访问右子节点再访问左子节点(符合深度优先特性),横线处应填入访问左子节点的语句,if (node->left) st.push(node->left); 以正确实现遍历逻辑。所以 A 正确。故选 A。
第 12 题 给定一棵普通二叉树(节点值没有大小规律),下面代码判断是否存在值为 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 ;
}
A. q.push(cur); B. if (cur->right) q.push(cur->right);
if (cur->left)
q.push (cur->left);
if (cur->right)
q.push (cur->right);
q.push (cur->left);
q.push (cur->right);
解析:答案 C。程序代码实现广度优先搜索(BFS)遍历二叉树,使用队列存储待访问节点,检查当前节点值是否等于目标值 x,将非空子节点(左/右)加入队列,适用于普通二叉树(无节点值大小规律)。BFS 遍历原理:广度优先搜索需按层级遍历节点,需将当前节点的非空子节点加入队列。选项 C 通过条件判断确保:左子节点存在时入队(if (cur->left) q.push(cur->left);),右子节点存在时入队(if (cur->right) q.push(cur->right);)。q.push(cur) 会导致当前节点重复入队,形成死循环,A 错误。if (cur->right) q.push(cur->right) 忽略左子树,遍历不完整,B 错误。q.push(cur->left); q.push(cur->right); 未判空,若子节点为空则队列引入非法空指针,引发运行时错误,D 错误。选项 C 严格检查子节点非空后才入队,确保:所有有效节点被遍历,避免空指针访问。故选 C。
第 13 题 在二叉排序树(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 ;
}
A. 最坏情况下,访问结点数是𝑂(log 𝑛)
B. 最坏情况下,访问结点数是𝑂(𝑛)
C. 无论如何,访问结点数都不超过树高的一半
D. 一定比在普通二叉树中搜索快
解析:答案 B。在二叉排序树(BST)中,给定搜索函数的行为和特性如下分析:BST 可能退化:当插入节点按顺序递增或递减时,BST 会退化成单链表(例如根节点为 1,后续插入 2、3、4...)。最坏时间复杂度:此时搜索需遍历所有节点(如查找最大值需访问全部𝑛个节点),时间复杂度为𝑂(𝑛)。𝑂(log 𝑛)仅在平衡 BST(如 AVL 树)中成立,但题目未保证平衡性,A 错误。当 BST 退化为链表时,搜索叶节点需访问𝑛个节点,而树高为𝑛,𝑛 > 𝑛/2,故 C 错误。普通二叉树搜索(如 BFS)最坏也是𝑂(𝑛),且 BST 退化时性能相同,故 D 错误。故选 B。
第 14 题 0/1 背包(每件物品最多选一次)问题通常可用一维动态规划求解,核心代码如下。则下面说法正确的是( )。
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,方向无所谓
解析:答案 B。状态依赖特性:一维 dp[j] 表示容量 j 下的最大价值。更新 dp[j] 时需依赖未更新的 dp[j - w[i]](即前一轮物品的状态)。遍历方向的影响:从大到小遍历(j=m to w[i]):更新 dp[j] 时,dp[j - w[i]] 仍为上一物品状态,确保物品仅使用一次(0/1 背包)。从小到大遍历(j=w[i] to m):p[j - w[i]] 可能已被当前物品更新过,导致同一物品被重复使用(转化为完全背包逻辑)。若从小到大遍历,会重复使用物品(漏解≠重复使用),A 错误。内层 j 必须从大到小,否则同一件物品会被用多次,B 正确。方向不同导致结果不同(0/1 背包≠完全背包),C 错误。初始值无法避免状态依赖错误,D 错误。故选 B。
第 15 题 以下关于动态规划的说法中,错误的是( )。
A. 动态规划方法通常能够列出递推公式。
B. 动态规划方法的时间复杂度通常为状态的个数。
C. 动态规划方法有递推和递归两种实现形式。
D. 对很多问题,递推实现和递归实现动态规划方法的时间复杂度相当。
解析:答案 B。关于动态规划,其核心是定义状态和状态转移方程(递推公式)。对于大多数动态规划问题(如背包问题、斐波那契数列等),递推公式是设计解决方案的基础。所以 A 正确。动态规划的时间复杂度取决于两个因素:状态的个数和每个状态转移所需的时间。如果每个状态转移的时间复杂度为𝑂(1),则总时间复杂度通常与状态个数成正比。然而,在许多问题中,状态转移的时间复杂度不是𝑂(1),例如:在最长回文子序列问题中,状态转移可能涉及复杂的操作,时间复杂度不仅取决于状态个数,所以 B 错误,因为它忽略了状态转移的时间复杂度,仅考虑状态个数是不准确的。动态规划的实现方式包括:自顶向下(递归实现):使用递归加记忆化(memoization)来避免重复计算;自底向上(递推实现):使用迭代方式从基础状态逐步计算到目标状态,两种形式均被广泛使用,所以 C 正确。对于同一动态规划问题,递归实现(带记忆化)和递推实现的时间复杂度在渐近意义下(asymptotically)通常相同,因为记忆化确保每个状态只计算一次。尽管递归实现可能有额外的函数调用开销(常数因子差异),但大 O 表示法下的时间复杂度是相同的,所以 D 正确。故选 B。
2 判断题(每题 2 分,共 20 分) 第 1 题 以下代码中,构造函数被调用的次数是 1 次。
class Test {
public :
Test () { cout << "T " ; }
};
int main () {
Test a;
Test b = a;
}
解析:答案╳(错误)。Test a;:直接初始化对象 a,调用用户定义的默认构造函数 Test(),输出 "T "。这是用户定义构造函数的唯一一次调用。Test b = a;:这是拷贝初始化,调用编译器隐式生成的默认拷贝构造函数(因为用户未定义拷贝构造函数)。隐式拷贝构造函数不会调用用户定义的默认构造函数,且无输出。因此,输出结果仅为 "T "(一次),但构造函数总调用次数为:用户定义的默认构造函数:1 次;隐式拷贝构造函数:1 次(无用户定义行为)。共 2 次。故错误。
第 2 题 面向对象编程中,封装是指将数据和操作数据的方法绑定在一起,并对外隐藏实现细节。
解析:答案√(正确)。在面向对象编程中,封装的核心机制包括:数据与方法的绑定,将数据(属性)和操作这些数据的方法(函数)整合为一个独立的类单元,形成自包含的逻辑实体。对外隐藏实现细节,通过访问控制(如 private 或 protected 修饰符)限制外部直接访问内部数据,仅暴露必要的公共接口(如公共方法)。目的:防止非法修改,降低模块间耦合,提升代码安全性和可维护性。故正确。
第 3 题 以下代码能够正确统计二叉树中叶子结点的数量。
int countLeaf (TreeNode* root) {
if (!root) return 0 ;
if (!root->left && !root->right) return 1 ;
return countLeaf (root->left) + countLeaf (root->right);
}
解析:答案√(正确)。题目中的程序代码递归终止条件:若节点为空(!root),返回 0(空树无叶子节点)。若当前节点为叶子节点(无左、右子节点,即 !root->left && !root->right),返回 1。递归分解问题:对非叶子节点,递归计算左子树和右子树的叶子节点数,并求和:return countLeaf(root->left) + countLeaf(root->right);。故正确。
解析:答案╳(错误)。广度优先遍历二叉树是用队列来实现。故错误。
解析:答案√(正确)。在计算机程序中,函数调用管理确实通过栈来实现,这是现代编程语言的核心机制。函数调用栈的工作原理:函数调用时,当前函数的返回地址、局部变量和参数被压入栈顶(称为'栈帧'),CPU 寄存器状态同时保存(如 x86 架构的 ESP/EBP 寄存器);函数执行中,被调用函数在自己的栈帧内操作数据,嵌套调用时重复步骤,形成栈帧链。函数返回时,弹出当前栈帧,恢复调用方寄存器和栈指针,跳转回保存的返回地址继续执行。故正确。
第 6 题 在二叉排序树(BST)中,若某结点的左子树为空,则该结点一定是整棵树中的最小值结点。
解析:答案╳(错误)。在二叉排序树(BST)中,若某结点的左子树为空,该结点不一定是整棵树的最小值结点。BST 的最小值结点始终是树中最左边的结点(即从根结点开始沿左子树递归下移直到左子树为空的结点)。只有当该结点恰好是整棵树的最左边结点时,其左子树为空才意味着它是最小值结点;否则,可能存在其他结点值更小。故错误。
第 7 题 下面的函数能正确判断一棵树是不是二叉排序树(左边的数字要比当前数字小,右边的数字要比当前数字大)。
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);
}
解析:答案√(正确)。该函数 isBST 旨在判断二叉树是否为二叉排序树(BST),但存在边界值缺陷。二叉排序树的定义要求:对于每个节点,其左子树所有节点值严格小于该节点值,右子树所有节点值严格大于该节点值(通常假设无重复值)。函数使用递归方法,通过 minVal 和 maxVal 参数传递当前节点值的允许范围(开区间 (minVal, maxVal)):若当前节点值超出范围(root->val <= minVal || root->val >= maxVal),返回 false。递归检查左子树时,更新范围 (minVal, root->val);右子树时,更新范围 (root->val, maxVal)。算法逻辑本身正确。边界值问题导致错误:函数使用 int 类型表示范围边界(minVal 和 maxVal)。当二叉树包含极值(如 INT_MIN 或 INT_MAX)时,函数可能错误返回 false。逻辑正确,但未考虑特殊性,除极端情况,正确。
第 8 题 格雷编码相邻两个编码之间必须有多位不同,以避免数据传输错误。
解析:答案╳(错误)。格雷编码(Gray Code)的核心特性是相邻两个编码之间仅有 1 位不同,这是其避免数据传输错误的关键设计。故错误。
第 9 题 小杨在玩一个闯关游戏,从第 1 关走到第 4 关。每一关的体力消耗如下(下标表示关卡编号):cost = [ 0, 3, 5, 2, 4 ],其中 cost[i] 表示到达第 i 关需要消耗的体力,cost[0]=0 表示在开始状态,体力消耗为 0。小杨每次可以从当前关卡前进 1 步或 2 步。按照上述规则,从第 1 关到第 4 关所需消耗的最小体力为 7。
解析:答案╳(错误)。从第 1 关可以走 1 步到第 2 关,消耗 5,如走 2 步到第 3 关消耗 2;再从第 3 关到第 4 关消耗 4,合计 6,不是 7。故错误。
第 10 题 假定只有一个根节点的树的深度为 1,则一棵有𝑛个节点的完全二叉树,则树的深度为⌊log₂𝑛⌋+1。
解析:答案√(正确)。设完全二叉树的深度 (高度) 为 h,则节点数 n 满足:2ʰ⁻¹ ≤ n ≤ 2ʰ-1。
将上述不等式取对数:h-1 <= log₂(n) < h,因此,h = ⌊log₂(n)⌋ + 1。因此,这个结论是正确的。故正确。
3 编程题(每题 25 分,共 50 分)
3.1 编程题 1
试题名称:路径覆盖
时间限制:1.0 s
内存限制:512.0 MB
给定一棵有𝑛个结点的有根树𝑇,结点依次以 1, 2, ..., 𝑛编号,根结点编号为 1。方便起见,编号为𝑖的结点称为结点𝑖。
初始时𝑇中的结点均为白色。你需要将𝑇中的若干个结点染为黑色,使得所有叶子到根的路径上至少有一个黑色结点。将结点𝑖染为黑色需要代价𝑐ᵢ,你需要在满足以上条件的情况下,最小化染色代价之和。
第二行,𝑛-1 个正整数𝑓₂, 𝑓₃, ..., 𝑓ₙ,其中𝑓ᵢ表示结点𝑖的父结点的编号,保证𝑓ᵢ≤𝑖。
第三行,𝑛个正整数𝑐₁, 𝑐₂, ..., 𝑐ₙ,其中𝑐ᵢ表示将结点𝑖染为黑色所需的代价。
一行,一个整数,表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下,染色代价之和的最小值。
7 1 1 2 2 3 3 64 16 15 4 3 2 1
对于所有测试点,保证 2≤𝑛≤10⁵,1≤𝑐ᵢ≤10⁹。
编程思路:这是一个典型的树形 DP 问题,需要在有根树上选择一些节点染黑,使得:
每个叶子节点到根节点的路径上至少有一个黑色节点
最小化染色代价之和
叶子节点:没有子节点的节点
路径要求:每个叶子到根的路径都要被'覆盖'(至少有一个黑点)
代价最小化:每个节点染色有不同代价
dp[i]:以节点 i 为根的子树,满足该子树内所有叶子节点到 i 的路径上至少有一个黑色节点的最小代价。
如果 i 是叶子节点:
路径只有 i 自己,所以必须染色 i,代价
dp[i] = cost[i]
如果 i 不是叶子节点:
染黑当前节点 i,代价为 cost[i]。染黑 i 后,所有经过 i 的路径都满足条件,不需要考虑子树
不染黑当前节点 i,代价为所有子节点的 dp[i) 之和。因为 i 不黑,所以每个子树必须自己保证覆盖
每棵子树的 dp[i] 已经保证了 i 的子树内叶子到 i 的路径有黑点
由于路径是从叶子到 i,且经过各路径,所以这个黑点也覆盖了到 i 的路径
dp[i] = min(c[i], dp[i]) // 其中右边的 dp 为各路径中染黑最小代价和
方法一:根结节为 1,孩子结点编号大于 1。先构造各结点的孩子数,孩子数为 0 即是叶子结点。从叶子结点向上计算染黑最小代码,并加到其父结点,直到根结点 (不含根结点),根结点的 dp 值就是答案。注意𝑐ᵢ≤10⁹,所以𝑐ᵢ的和 dp 要用 long long。
#include <iostream>
using namespace std;
const int N = 100005 ;
int n;
int parentNod[N];
int cost[N];
int childCnt[N];
long long dp[N];
int main () {
cin >> n;
for (int i = 2 ; i <= n; i++) {
cin >> parentNod[i];
childCnt[parentNod[i]]++;
}
for (int i = 1 ; i <= n; i++)
cin >> cost[i];
for (int i = n; i >= 1 ; i--) {
if (childCnt[i] == 0 ) {
dp[i] = cost[i];
}
dp[i] = dp[i] < cost[i] ? dp[i] : cost[i];
if (i != 1 )
dp[parentNod[i]] += dp[i];
}
cout << dp[1 ] << endl;
return 0 ;
}
方法二:根结节为 1,孩子结点编号大于 1。从最大编号结点开始到 2 号结点向上计算染黑最小代码,并加到其父结点,根结点的 dp 值就是答案。注意𝑐ᵢ≤10⁹,所以𝑐ᵢ的和 dp 要用 long long。算法与方法一相同。参考程序代码如下:
#include <iostream>
using namespace std;
const int N = 100005 ;
int n, f[N], c[N], cnt[N];
long long dp[N];
int main () {
cin >> n;
for (int i = 2 ; i <= n; i++) {
cin >> f[i];
cnt[f[i]]++;
}
for (int i = 1 ; i <= n; i++)
cin >> c[i];
for (int i = n; i >= 1 ; i--) {
if (cnt[i] == 0 )
dp[i] = c[i];
dp[i] = dp[i] < c[i] ? dp[i] : c[i];
dp[f[i]] += dp[i];
}
cout << dp[1 ] << endl;
return 0 ;
}
3.2 编程题 2
试题名称:道具商店
时间限制:1.0 s
内存限制:512.0 MB
道具商店里有𝑛件道具可供挑选。第𝑖件道具可为玩家提升𝑎ᵢ点攻击力,需要𝑐ᵢ枚金币才能购买,每件道具只能购买一次。现在你有𝑘枚金币,请问你最多可以提升多少点攻击力?
第一行,两个正整数𝑛, 𝑘,表示道具数量以及你所拥有的金币数量。
接下来𝑛行,每行两个正整数𝑎ᵢ, 𝑐ᵢ,表示道具所提升的攻击力点数,以及购买所需的金币数量。
输出一行,一个整数,表示最多可以提升的攻击力点数。
4 100 10 1 20 11 40 33 100 99
对于 60% 的测试点,保证 1≤𝑘≤500,1≤𝑐ᵢ≤500。
对于所有测试点,保证 1≤𝑛≤500,1≤𝑘≤10⁹,1≤𝑎ᵢ≤500,1≤𝑐ᵢ≤10⁹。
这道题是一道典型的变形 01 背包问题,常规的 01 背包思路会因为金币容量𝑘过大 (最大 10⁹) 而无法直接实现,因此需要转换思考维度来解决。
常规 01 背包会定义 dp[j] 为'花费 j 金币能获得的最大攻击力',但本题中𝑘高达 10⁹,无法开这么大的数组。观察数据范围发现:每件道具的攻击力𝑎ᵢ≤500,道具数量𝑛≤500,因此所有道具的总攻击力最大为 500×500=250000(这个数值很小,完全可以用数组存储)。
因此我们转换背包维度:定义 dp[j] 为'获得 j 点攻击力所需的最少金币数'。通过这个转换,我们只需要处理 j 从 0 到 250000 的情况,最后遍历所有可能的攻击力值,找到满足 dp[j] ≤ k 的最大 j 即可。参考程序代码如下:
#include <iostream>
using namespace std;
int n, k;
int a[505 ];
int c[505 ];
int dp[250005 ];
int pwr = 0 ;
int ans = 0 ;
int main () {
cin >> n >> k;
for (int i = 1 ; i <= n; i++) {
cin >> a[i] >> c[i];
pwr += a[i];
}
for (int i = 1 ; i <= pwr; i++) {
dp[i] = 2e9 ;
}
for (int i = 1 ; i <= n; i++) {
for (int j = pwr; j >= a[i]; j--)
dp[j] = min (dp[j], dp[j - a[i]] + c[i]);
}
for (int i = 1 ; i <= pwr; i++) {
if (dp[i] <= k) ans = i;
}
cout << ans;
return 0 ;
}
这题是 0/1 背包问题变体:将道具视为物品,攻击力视为价值,金币视为背包容量。
目标:在金币限制 (𝑘) 内最大化总攻击力(非传统背包的价值最大化)。
状态定义:f[j] = 获得恰好 j 点攻击力所需的最小金币;
状态转移:f[j] = min(f[j], f[j - a] + c) // 选择 or 不选当前道具
倒序遍历:内层循环 j 从 s 递减到 a(关键!避免同一道具重复使用)
时间复杂度:𝑂(𝑛×𝑠) ≈ 𝑂(250,000n)~10⁸级 (s 为攻击力总和),不会超时
空间复杂度:𝑂(𝑛²)(因数组大小 N²=255,025)
初始化:f[0] = 0 是正确性的前提 (零攻击力零消耗),全局变量默认
倒序更新:正序遍历会导致完全背包问题(物品无限次使用)
#include <iostream>
using namespace std;
const int N = 505 ;
const int oo = 2e9 ;
int n, k;
int f[N * N];
int main () {
cin >> n >> k;
for (int i = 1 ; i < N * N; i++)
f[i] = oo;
int s = 0 ;
for (int i = 1 ; i <= n; i++) {
int a, c;
cin >> a >> c;
s += a;
for (int j = s; j >= a; j--) {
f[j] = f[j] < f[j - a] + c ? f[j] : f[j - a] + c;
}
}
int ans = 0 ;
for (int i = 0 ; i <= s; i++) {
if (f[i] <= k) ans = i;
}
cout << ans;
return 0 ;
}