GESP C++六级 2026年3月真题详细解析

💪「艾墨舟编程小先锋」专为GESP考生打造的免费题库小程序。涵盖图形化/Python/C++全真题，支持真题模考、考前预测、错题整理与学习统计，一站式攻克客观题。

📋 内容概览

本文包含2026年3月GESP C++六级考试全部题型的详细解析：15道单选题、10道判断题、2道编程题，每道题匹配考纲知识点，提供解题思路与易错点提示。

🎯 试题解析

───── ✨ 第1题 ✨ ─────

📖 题目

下列关于 C++ 中类的描述，正确的是（ ）。A. 如果类没有用户声明的构造函数，那么编译器会隐式声明一个默认构造函数B. 类的析构函数可以被重载，一个类可以有多个析构函数C. 类中的所有成员都必须声明为 publicD. 类和结构体在 C++ 中没有区别，包括默认访问权限也相同

📌 大纲对应知识点：面向对象（类的创建和初始化、类的特性）🎯 考查目标：掌握C++类的构造函数、析构函数、访问权限及与结构体的区别。

📋 选项详解

⭐ 答案：A📌 知识点：类的基本特性、构造函数、析构函数

💡 解题小贴士：牢记类与结构体的核心区别是默认访问权限，析构函数不可重载，无自定义构造时编译器自动生成默认构造。

───── ✨ 第2题 ✨ ─────

📖 题目

下列代码中，s1->draw(); 和 s2->draw();输出不同结果的主要原因是（ ）。

class Shape {public:    virtual void draw() {        cout << "绘制图形" << endl;    }    virtual ~Shape() {}};class Circle : public Shape {public:    void draw() override {        cout << "绘制圆形" << endl;    }};class Rectangle : public Shape {public:    void draw() override {        cout << "绘制矩形" << endl;    }};int main() {    Shape* s1 = new Circle();    Shape* s2 = new Rectangle();    s1->draw();    s2->draw();    delete s1;    delete s2;    return 0;}

A. draw() 是普通成员函数B. Shape 中的 draw() 被声明为虚函数C. Circle 和 Rectangle 中使用了 public 继承D. 指针变量名不同

📌 大纲对应知识点：面向对象（类的特性：多态）🎯 考查目标：理解C++多态的实现原理，掌握虚函数的作用。

📋 选项详解

⭐ 答案：B📌 知识点：虚函数、多态

💡 解题小贴士：C++运行时多态的两个必要条件：基类函数声明为virtual，子类重写该函数，通过基类指针/引用调用。

───── ✨ 第3题 ✨ ─────

📖 题目

下面的代码在 main() 中有一行会导致编译错误，请找出来。

class Pet {public:    Pet(string n, int a) : name(n), age(a) {}    string getName()  { return name; }    void   birthday() { age++; }       private:    string name;    int    age;};int main() {    Pet cat("奶茶", 2);    cout << cat.getName();    // ①    cat.birthday();           // ②    cat.name = "大橘";         // ③    cout << cat.getName();    // ④}

A. 第 ① 行B. 第 ② 行C. 第 ③ 行D. 第 ④ 行

📌 大纲对应知识点：面向对象（类的特性：封装）🎯 考查目标：掌握类成员访问权限的规则，理解private成员的访问限制。

📋 选项详解

⭐ 答案：C📌 知识点：类访问权限、封装

💡 解题小贴士：private成员只能在类内部访问，类外必须通过public成员函数（getter/setter）操作。

───── ✨ 第4题 ✨ ─────

📖 题目

游乐园的过山车每次限坐4人，用循环队列管理排队（容量 MAX=5 ，空一格判满）。下面代码执行后，循环队列是否已满？ rear 的值是多少？

const int MAX = 5;int queue[MAX];int front = 0, rear = 0;// 入队void enqueue(int x) {    queue[rear] = x;    rear = (rear + 1) % MAX;}// 出队void dequeue() {    front = (front + 1) % MAX;}int main() {    enqueue(1); enqueue(2); enqueue(3); enqueue(4);    dequeue(); dequeue();    enqueue(5); enqueue(6);}

A. 已满，rear = 1B. 未满，rear = 1C. 已满，rear = 2D. 未满，rear = 4

📌 大纲对应知识点：栈和队列（循环队列）🎯 考查目标：掌握循环队列的入队、出队操作，以及判满规则。

📋 选项详解

⭐ 答案：A📌 知识点：循环队列操作、判满规则

💡 解题小贴士：空一格判满的循环队列，判满公式为 (rear + 1) % 容量 == front，元素个数为 (rear - front + 容量) % 容量。

───── ✨ 第5题 ✨ ─────

📖 题目

在以下计算机系统应用场景中，最适合使用循环队列的是（ ）。A. 函数调用过程中，保存局部变量和返回地址B. 表达式求值中的运算符优先级处理C. 操作系统中的进程优先级调度（高优先级先执行）D. 生产者和消费者问题中的共享缓冲区

📌 大纲对应知识点：栈和队列（循环队列）🎯 考查目标：理解循环队列的特性与适用场景，区分栈、队列、优先队列的应用。

📋 选项详解

⭐ 答案：D📌 知识点：队列应用场景

💡 解题小贴士：栈适合后进先出场景（函数调用、表达式求值），队列适合先进先出场景（缓冲区、排队），优先队列适合按优先级调度场景。

───── ✨ 第6题 ✨ ─────

📖 题目

在二叉搜索树（BST）中，若中序遍历的序列为{1, 2, 3, 4, 5}，且先序遍历的第一个序列元素为3，则下列说法正确的是（ ）。A. 该树一定是一棵完全二叉树。B. 元素4和5不可能是兄弟节点。C. 元素1所在节点的深度可能大于3（根节点深度为1）。D. 元素2一定是元素1的父节点。

📌 大纲对应知识点：树（二叉排序树、完全二叉树）🎯 考查目标：掌握二叉搜索树的特性，以及遍历序列与树结构的关系。

📋 选项详解

⭐ 答案：B📌 知识点：二叉搜索树、遍历序列

💡 解题小贴士：二叉搜索树的中序遍历是升序序列，先序遍历第一个元素是根节点，可据此划分左右子树。

───── ✨ 第7题 ✨ ─────

📖 题目

某二叉树共有10个结点，记为A~J，已知它的先序遍历序列为：A B D H I E C F J G，中序遍历序列为：H D I B E A F J C G，则该二叉树的后序遍历序列是（ ）。A. H I D E B J F G C AB. H I D B E J F G C AC. I H D E B J F G C AD. H I D E B F J G C A

📌 大纲对应知识点：树（树的构造与遍历）🎯 考查目标：掌握根据先序和中序遍历序列重建二叉树，并推导后序遍历序列。

📋 选项详解

⭐ 答案：A📌 知识点：二叉树遍历、树的重建

💡 解题小贴士：先序找根，中序分左右，递归构建树，后序遍历顺序为左子树→右子树→根节点。

───── ✨ 第8题 ✨ ─────

📖 题目

下列关于树的遍历的说法中，正确的一项是（ ）。A. 对任意一棵树进行深度优先遍历，所得序列一定唯一。B. 已知一棵二叉树的先序遍历和后序遍历序列，可以唯一确定这棵二叉树。C. 已知一棵二叉树的先序遍历和中序遍历序列，可以唯一确定这棵二叉树。D. 已知一棵二叉树的先序遍历序列，可以唯一确定这棵二叉树。

📌 大纲对应知识点：树（树的构造与遍历）🎯 考查目标：掌握二叉树遍历序列与树结构的对应关系。

📋 选项详解

⭐ 答案：C📌 知识点：二叉树遍历与树的重建

💡 解题小贴士：唯一确定二叉树需要中序遍历序列加另外一种遍历序列（先序/后序/层序）。

───── ✨ 第9题 ✨ ─────

📖 题目

有6个字符，它们出现的次数分别为：{2, 3, 3, 4, 6, 8}，现在用哈夫曼编码为这些字符编码，最小加权路径长度 WPL （每个字符的出现次数乘以它的编码长度，再把每个字符结果加起来）的值为（ ）。A. 58B. 60C. 62D. 64

📌 大纲对应知识点：树（哈夫曼树）🎯 考查目标：掌握哈夫曼树的构造方法，以及加权路径长度WPL的计算。

📋 选项详解

⭐ 答案：D📌 知识点：哈夫曼树、WPL计算

💡 解题小贴士：哈夫曼树构造每次选两个最小权值节点合并，WPL等于所有非叶子节点权值之和，可快速计算。

───── ✨ 第10题 ✨ ─────

📖 题目

对n个不同符号的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是（）。A. 60B. 58C. 57D. 56

📌 大纲对应知识点：树（哈夫曼树）🎯 考查目标：掌握哈夫曼树的结点数特性。

📋 选项详解

⭐ 答案：B📌 知识点：哈夫曼树性质

💡 解题小贴士：哈夫曼树是正则二叉树，没有度为1的结点，结点总数公式：总节点数 = 2 * 叶子节点数 - 1。

───── ✨ 第11题 ✨ ─────

📖 题目

关于格雷编码（ Gray Code ），下列说法正确的是（ ）。A. 格雷编码中，编码位数越多，相邻编码之间变化的位数也越多B. 格雷编码中，相邻两个编码的二进制位恰好有一位不同C. 格雷编码就是把普通二进制编码按位取反后得到的结果D. 格雷编码不能用于数字电路和状态转换的设计中

📌 大纲对应知识点：基于树的编码（格雷编码）🎯 考查目标：掌握格雷编码的基本特性与应用场景。

📋 选项详解

⭐ 答案：B📌 知识点：格雷编码特性

💡 解题小贴士：牢记格雷编码核心特性：相邻编码仅有一位不同，广泛应用于数字电路、通信等领域。

───── ✨ 第12题 ✨ ─────

📖 题目

给定一棵二叉树，采用广度优先搜索 (BFS) 算法，返回右视图所有节点的值。其中右视图定义为：二叉树的右视图是从树的右侧看过去时可见的节点集合，即右视图中的每个节点都是某一层中最右侧的节点。

struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}};vector<int> rightSideView(TreeNode* root) {    unordered_map<int, int> rightmostValueAtDepth;    int max_depth = -1;    queue<TreeNode*> nodeQueue;    queue<int> depthQueue;    nodeQueue.push(root);    depthQueue.push(0);    while (!nodeQueue.empty()) {        TreeNode* node = nodeQueue.front(); nodeQueue.pop();        int depth = depthQueue.front(); depthQueue.pop();        if (node != NULL) {            max_depth = max(max_depth, depth);            rightmostValueAtDepth[depth] = node->val;            nodeQueue.push(node->left);            nodeQueue.push(node->right);            depthQueue.push(________);            depthQueue.push(________);        }    }    vector<int> rightView;    for (int depth = 0; ________; ++depth) {        rightView.push_back(rightmostValueAtDepth[depth]);    }    return rightView;};

A. 第一个空填depth，第二个空填depth，第三个空填depth < max_depthB. 第一个空填depth+1，第二个空填depth+1，第三个空填depth <= max_depthC. 第一个空填depth+1，第二个空填depth+1，第三个空填depth < max_depthD. 第一个空填depth，第二个空填depth，第三个空填depth <= max_depth

📌 大纲对应知识点：搜索算法（宽度优先搜索BFS）🎯 考查目标：掌握二叉树BFS层序遍历的实现，以及右视图的求解逻辑。

📋 选项详解

⭐ 答案：B📌 知识点：BFS、二叉树右视图

💡 解题小贴士：BFS层序遍历时，子节点深度为父节点深度加1，右视图只需记录每层最后一个访问的节点值。

───── ✨ 第13题 ✨ ─────

📖 题目

下列关于树的深度优先搜索（ DFS ）的说法中，正确的是（ ）。A. 对树进行 DFS 时，一定是按层从上到下依次访问结点B. 对任意一棵树进行 DFS ，得到的遍历序列唯一C. 对一棵树进行 DFS 时，常借助递归或栈实现D. DFS 只能用于二叉树，不能用于普通树

📌 大纲对应知识点：搜索算法（深度优先搜索DFS）🎯 考查目标：掌握DFS的实现方式与特性。

📋 选项详解

⭐ 答案：C📌 知识点：DFS特性与实现

💡 解题小贴士：DFS用递归/栈，BFS用队列，二者都适用于所有树和图结构。

───── ✨ 第14题 ✨ ─────

📖 题目

小朋友们去邻里拜年，每个家里有不同数量的糖果。规则是：不能连续进入两个相邻的房子（即不能同时取相邻两家的糖果）。目标是拿到最多糖果。以下是代码实现，请补全横线。

int visit(vector<int>& nums) {    if (nums.empty()) {        return 0;    }    int size = nums.size();    if (size == 1) {        return nums[0];    }    vector<int> dp = vector<int>(size, 0);    dp[0] = nums[0];    dp[1] = max(nums[0], nums[1]);    for (int i = 2; i < size; i++) {        dp[i] = ______;  // 在此处填写代码    }    return dp[size - 1];}

A. dp[i] = dp[i - 1] + nums[i];B. dp[i] = max(dp[i - 1], dp[i - 2] * nums[i]);C. dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);D. dp[i] = dp[i - 2] + nums[i];

📌 大纲对应知识点：简单动态规划（一维动态规划）🎯 考查目标：掌握打家劫舍类一维动态规划问题的状态转移方程。

📋 选项详解

⭐ 答案：C📌 知识点：一维动态规划、打家劫舍问题

💡 解题小贴士：打家劫舍类问题核心是两种选择：取当前元素则加前前个状态，不取则继承前一个状态，取最大值。

───── ✨ 第15题 ✨ ─────

📖 题目

元宵节晚上，小朋友沿着一条发光石板路前进，每次可向前走 1 块或 2 块石板。动态规划定义如下：dp[i] = dp[i - 1] + dp[i - 2]，下面关于 dp[i] 的含义最合适的是（ ）。A. 走到第 i 块石板的不同走法数量B. 走到第 i 块石板时，已经走过的石板总数C. 从第 i 块石板走回起点的最少步数D. 从第 i 块石板走回起点的最大步数

📌 大纲对应知识点：简单动态规划（一维动态规划）🎯 考查目标：理解爬楼梯类动态规划问题的状态含义。

📋 选项详解

⭐ 答案：A📌 知识点：一维动态规划、爬楼梯问题

💡 解题小贴士：每次走1或2步的路径计数问题是经典的斐波那契数列应用，dp[i]表示到达第i个位置的方法数。

判断题部分

───── ✨ 判断题第1题 ✨ ─────

📖 题目

下面定义了一个表示二维坐标点的类 Point，并提供了一个带参数的构造函数，但第 ② 行 Point b; 会调用编译器自动生成的默认构造函数，将b.x 和 b.y 被初始化为 0.0 ，程序可以正常编译运行。

class Point {public:    double x, y;    Point(double px, double py) : x(px), y(py) {}    void print() {        cout << "(" << x << ", " << y << ")";    }};int main() {    Point a(3.0, 4.0);   // ①    Point b;             // ②      a.print();}

📌 大纲对应知识点：面向对象（类的创建和初始化）🎯 考查目标：掌握默认构造函数的生成规则。

⭐ 答案：错误

💡 解析：当类中定义了带参数的构造函数时，编译器不会自动生成默认无参构造函数，第②行Point b;会编译报错。

───── ✨ 判断题第2题 ✨ ─────

📖 题目

C++ 中的继承支持单继承和多继承，但子类无法直接访问父类的私有成员。

📌 大纲对应知识点：面向对象（类的特性：继承）🎯 考查目标：掌握继承的访问权限规则。

⭐ 答案：正确

💡 解析：C++支持单继承和多继承，父类的private成员只能在父类内部访问，子类无法直接访问，需要通过父类的public/protected成员函数访问。

───── ✨ 判断题第3题 ✨ ─────

📖 题目

对如下结构的树，执行travel函数，输出结果是 1 2 3 4 5。

        1       / \      2   3     / \    4   5

struct Node {    int val;    Node *left, *right;    Node(int v) : val(v), left(nullptr), right(nullptr) {}};void travel(Node* root) {    if (!root) return;    stack<Node*> s;    s.push(root);    while (!s.empty()) {        Node* cur = s.top(); s.pop();        cout << cur->val << " ";        if (cur->right) s.push(cur->right);        if (cur->left)  s.push(cur->left);    }}

📌 大纲对应知识点：搜索算法（深度优先搜索DFS）🎯 考查目标：掌握二叉树非递归前序遍历的实现。

⭐ 答案：正确

💡 解析：该函数是前序遍历的非递归实现，栈是后进先出，先压右孩子再压左孩子，保证左孩子先访问，遍历顺序为1 2 4 5 3，哦不对，等下实际输出是1 2 4 5 3？不对哦仔细看：弹出1，压右3再压左2；弹出2，压右5再压左4；弹出4，无孩子；弹出5，无孩子；弹出3，无孩子。输出是1 2 4 5 3，所以题目说输出1 2 3 4 5是错误的？哦对，我刚才看错了，所以答案是错误。更正：⭐ 答案：错误💡 解析：该前序遍历非递归实现的输出为1 2 4 5 3，与题目描述的1 2 3 4 5不符。

───── ✨ 判断题第4题 ✨ ─────

📖 题目

若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。

📌 大纲对应知识点：树（哈夫曼树）🎯 考查目标：掌握哈夫曼树的构造特性。

⭐ 答案：正确

💡 解析：所有字符频率相同时，哈夫曼树的构造会得到完全二叉树，所有叶子节点深度差不超过1。

───── ✨ 判断题第5题 ✨ ─────

📖 题目

哈夫曼编码是一种变长的前缀编码，在解码时不需要额外的分隔符就能唯一还原，这是因为在哈夫曼树中，任何一个字符的叶子结点都不会成为另一个字符结点的祖先。

📌 大纲对应知识点：基于树的编码（哈夫曼编码）🎯 考查目标：掌握哈夫曼编码的前缀特性。

⭐ 答案：正确

💡 解析：哈夫曼编码是前缀编码，任何一个编码都不是另一个编码的前缀，对应哈夫曼树中字符都在叶子节点，不会成为其他字符的祖先，因此解码时无需分隔符。

───── ✨ 判断题第6题 ✨ ─────

📖 题目

在 C++ 中使用一维数组 vector tree 存储按层序遍历的完全二叉树时，若根节点存储在 tree[0]，则对于任意非空节点 tree[i]，其右孩子（如果存在）必然位于 tree[2 * i + 2]。

📌 大纲对应知识点：树（完全二叉树）🎯 考查目标：掌握完全二叉树的数组存储规则。

⭐ 答案：正确

💡 解析：根节点下标为0时，左孩子下标为2*i+1，右孩子下标为2*i+2，符合完全二叉树的数组存储规则。

───── ✨ 判断题第7题 ✨ ─────

📖 题目

在 C++ 中使用栈来非递归地实现二叉树的前序遍历时，为了保证遍历顺序正确，在处理完当前结点后，应该先将该结点的左孩子压入栈中，然后再将右孩子压入栈中。

📌 大纲对应知识点：搜索算法（深度优先搜索DFS）🎯 考查目标：掌握二叉树非递归前序遍历的实现细节。

⭐ 答案：错误

💡 解析：栈是后进先出，为了保证左孩子先访问，应该先压右孩子，再压左孩子，这样弹出时左孩子先出。

───── ✨ 判断题第8题 ✨ ─────

📖 题目

设二叉树共有n个结点，函数preorderTraversal以下代码的时间复杂度为O(n)，空间复杂度为O(n)。

struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}};void preorder(TreeNode *root, vector<int> &res) {    if (root == nullptr) {        return;    }    res.push_back(root->val);    preorder(root->left, res);    preorder(root->right, res);}vector<int> preorderTraversal(TreeNode *root) {    vector<int> res;    preorder(root, res);    return res;};

📌 大纲对应知识点：算法复杂度分析🎯 考查目标：掌握二叉树遍历的时间与空间复杂度分析。

⭐ 答案：正确

💡 解析：每个节点访问一次，时间复杂度O(n)；递归栈最坏情况（单支树）为O(n)，平均为O(logn)，最坏空间复杂度O(n)。

───── ✨ 判断题第9题 ✨ ─────

📖 题目

下列代码实现了一个 0-1 背包的一维动态规划代码，内层循环是经典的逆序写法。若将内层循环改成正序遍历（即 for (int j = w[i]; j <= W; j++)），仍能得到正确答案。

int main() {    int W = 5;    int w[] = {2, 3, 4};    int v[] = {10, 1, 1};    int n   = 3;    int dp[6] = {0};       for (int i = 0; i < n; i++) {        for (int j = W; j >= w[i]; j--) {            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);        }    }    cout << dp[W];  }

📌 大纲对应知识点：简单动态规划（简单背包问题）🎯 考查目标：掌握0-1背包一维DP的实现原理。

⭐ 答案：错误

💡 解析：0-1背包一维DP逆序遍历是为了保证每个物品只被选一次，正序遍历会变成完全背包（物品可多次选），无法得到正确的0-1背包结果。

───── ✨ 判断题第10题 ✨ ─────

📖 题目

在动态规划问题中，状态空间相同且没有重复计算的情况下， “ 状态转移方程 + 递推 ” 与 “ 递归 + 记忆化搜索 ” 的时间复杂度通常相同。

📌 大纲对应知识点：简单动态规划🎯 考查目标：理解动态规划两种实现方式的复杂度差异。

⭐ 答案：正确

💡 解析：两种方式都会访问每个状态一次，没有重复计算时时间复杂度相同，均为状态空间大小乘以每个状态的转移代价。

编程题部分

───── ✨ 编程题1：选数 ✨ ─────

📖 题目描述

给定两个包含n个整数的数组a与b。你需要指定若干下标i（1≤i≤n）使得以下条件成立：（1）若选了下标i，则下一个可选下标≥i + b[i]；（2）最大化Σa[i]，也即最大化数组a对应下标的整数之和。

输入格式第一行，一个正整数n，表示数组长度。第二行，n个非负整数，表示数组a。第三行，n个非负整数，表示数组b。

输出格式一行，一个整数，表示满足条件的前提下，数组a对应下标的整数之和的最大值。

样例输入1

41 2 3 43 3 1 1

样例输出1

7

数据范围对于所有测试点，保证1≤n≤1e5，0≤a[i]≤1e4，0≤b[i]≤n。

📌 大纲对应知识点：简单动态规划（一维动态规划）🎯 考查目标：掌握线性动态规划的状态设计与转移，以及O(n)复杂度的优化。

📋 解题思路

1. 状态定义
   ：f[i]表示前i个位置中，能获得的最大和。
2. 状态转移
   ：
3. 不选第i个元素：f[i+1] = max(f[i+1], f[i])
4. 选第i个元素：f[i + b[i]] = max(f[i + b[i]], f[i] + a[i])，同时更新全局最大值ans。
5. 初始化
   ：f[0] = 0，ans = 0。
6. 复杂度
   ：O(n)，适合n≤1e5的数据范围。

💻 参考代码

#include <cstdio>#include <algorithm>using namespace std;const int N = 1e5 + 5;int n;int a[N], b[N];long long f[N], ans;int main() {    scanf("%d", &n);    for (int i = 1; i <= n; i++)        scanf("%d", &a[i]);    for (int i = 1; i <= n; i++)        scanf("%d", &b[i]);    for (int i = 1; i <= n; i++) {        ans = max(ans, f[i] + a[i]);        if (i + b[i] <= n)            f[i + b[i]] = max(f[i + b[i]], f[i] + a[i]);        f[i + 1] = max(f[i + 1], f[i]);    }    printf("%lld\n", ans);    return 0;}

💡 解题小贴士：本题是跳跃游戏与打家劫舍的结合，通过维护f数组记录到每个位置的最大和，线性遍历即可完成转移，避免了O(n²)的暴力DP。

───── ✨ 编程题2：完全二叉树 ✨ ─────

📖 题目描述

给定一棵包含n个结点的有根二叉树，结点依次以1~n编号，根结点编号为1。对于结点i，其左儿子的编号记为l[i]，右儿子编号记为r[i]。特别地，如果左儿子不存在则l[i]=0，如果右儿子不存在则r[i]=0。树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有n棵子树中，有多少棵子树是完全二叉树。

输入格式第一行，一个正整数n，表示有根二叉树结点数量。接下来n行，每行两个正整数，表示结点i的左儿子编号和右儿子编号。

输出格式输出一行，一个整数，表示所有子树中完全二叉树的数量。

样例输入1

42 34 00 00 0

样例输出1

4

数据范围对于所有测试点，保证1≤n≤1e5。

📌 大纲对应知识点：树（完全二叉树、深度优先搜索DFS）🎯 考查目标：掌握完全二叉树的判定条件，以及后序遍历统计子树信息的方法。

📋 解题思路

1. 完全二叉树判定条件
   ：
2. 左右子树都是完全二叉树；
3. 左子树的最小高度 ≥ 右子树的最大高度；
4. 整棵树的最小高度 ≥ 最大高度 - 1（即左右子树高度差不超过1）。
5. DFS后序遍历
   ：对于每个节点，递归计算左右子树的最小高度、最大高度，以及是否为完全二叉树，统计符合条件的节点数量。
6. 复杂度
   ：O(n)，每个节点访问一次，适合n≤1e5的数据范围。

💻 参考代码

#include <cstdio>#include <algorithm>using namespace std;const int N = 1e5 + 5;int n;int l[N], r[N];int mn[N], mx[N], chk[N];int ans;void dfs(int u) {    chk[u] = 1;    if (!u)        return;    dfs(l[u]);    dfs(r[u]);    chk[u] &= chk[l[u]] & chk[r[u]];    mn[u] = 1 + min(mn[l[u]], mn[r[u]]);    mx[u] = 1 + max(mx[l[u]], mx[r[u]]);    chk[u] &= mn[l[u]] >= mx[r[u]];    chk[u] &= mn[u] >= mx[u] - 1;    ans += chk[u];}int main() {    scanf("%d", &n);    for (int i = 1; i <= n; i++)        scanf("%d%d", &l[i], &r[i]);    dfs(1);    printf("%d\n", ans);    return 0;}

💡 解题小贴士：完全二叉树的判定核心是层序遍历除最后一层外都是满的，最后一层节点靠左，通过左右子树的高度关系可以高效判定，后序遍历可一次性获取子树的所有必要信息。

📝 学习建议

本次六级考试核心考点集中在面向对象特性、树的遍历与应用、搜索算法（DFS/BFS）、动态规划（一维DP、背包问题） 四大模块，与考纲要求完全匹配。复习建议：1. 面向对象部分重点掌握构造函数、析构函数、虚函数、多态、继承的访问权限等核心特性，多做代码阅读题。2. 树部分需熟练掌握二叉树三种遍历、树的重建、哈夫曼树、完全二叉树的判定，以及BFS/DFS在树中的应用。3. 动态规划部分重点掌握一维DP的常见模型（打家劫舍、爬楼梯、背包问题），理解状态定义与转移的推导方法。4. 编程题注意时间复杂度优化，本次两道编程题均为O(n)复杂度，需掌握线性DP和DFS后序遍历的高效实现。

💪 更多GESP真题训练、模拟考试、薄弱点诊断，欢迎使用「GESP练题小程序」，助你高效备考，顺利通关！

📚 学而不思则罔，思而不学则殆。 —— 孔子