CCF GESP Python六级 2026年3月真题详细解析

---

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

GESP考级免费刷题小程序

📋 内容概览

本文包含2026年3月GESP Python六级考试全部15道单选题、10道判断题、2道编程题的详细解析，精准匹配考点，附解题技巧与代码实现，助力考生掌握核心知识点。

🎯 试题解析

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

📖 题目

以下关于Python类继承的代码，执行后输出结果是？（）

classAnimal:
def__init__(self,name):
self.name=name
defspeak(self):
return"动物叫声"
classDog(Animal):
defspeak(self):
returnf"{self.name}：汪汪汪"
classCat(Animal):
def__init__(self,name,color):
super().__init__(name)
self.color=color
defspeak(self):
returnf"{self.name}（{self.color}）：喵喵喵"
dog=Dog("旺财")
cat=Cat("咪宝","橘色")
print(dog.speak(),cat.speak())

A. 动物叫声 动物叫声
B. 旺财：汪汪汪 咪宝：喵喵喵
C. 旺财：汪汪汪 咪宝（橘色）：喵喵喵
D. 动物叫声 咪宝（橘色）：喵喵喵

📌 大纲对应知识点：Python类的继承与多态
🎯 考查目标：掌握子类重写父类方法、super调用父类构造函数的用法

📋 选项详解

⭐ 答案：C
📌 知识点：类继承、方法重写、super函数

💡 解题小贴士：子类重写父类方法后，调用时优先执行子类实现；super()用于调用父类的方法，常用于构造函数初始化。

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

📖 题目

下列代码中，s1.draw() 和 s2.draw() 能正确运行并输出不同结果的主要原因是（ ）。

classShape:
defdraw(self):
print("绘制图形")
classCircle(Shape):
defdraw(self):
print("绘制圆形")
classRectangle(Shape):
defdraw(self):
print("绘制矩形")
if__name__=="__main__":
s1=Circle()
s2=Rectangle()
s1.draw()
s2.draw()

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

📌 大纲对应知识点：Python多态实现原理
🎯 考查目标：理解Python动态绑定的多态特性

📋 选项详解

⭐ 答案：C
📌 知识点：多态、动态绑定

💡 解题小贴士：Python默认支持动态多态，只要子类重写了父类的同名方法，调用时就会执行子类的实现，无需显式声明虚函数。

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

📖 题目

下面的代码在主程序 if __name__ == "__main__": 中有没有一行会导致运行错误，如果有请找出错误行（）

classPet:
def__init__(self,n,a):
self._name=n
self._age=a
defget_name(self):
returnself._name
defbirthday(self):
self._age+=1
if__name__=="__main__":
cat=Pet("奶茶",2)
print(cat.get_name())# ①  
cat.birthday()# ②  
cat._name="大橘"# ③  
print(cat.get_name())# ④

A. 第 ① 行
B. 第 ② 行
C. 第 ③ 行
D. 无错误行

📌 大纲对应知识点：Python类的访问控制
🎯 考查目标：理解Python单下划线成员的访问特性

📋 选项详解

⭐ 答案：D
📌 知识点：类成员访问控制、保护成员

💡 解题小贴士：Python中没有严格的私有成员，单下划线只是约定俗成的保护标识，双下划线会进行名称修饰，但也可通过特殊方式访问。

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

📖 题目

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

MAX=5
queue=[None]*MAX
front=0
rear=0
defenqueue(x):
globalrear,queue
queue[rear]=x
rear=(rear+1)%MAX
defdequeue():
globalfront
front=(front+1)%MAX
if__name__=="__main__":
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)

dequeue()
dequeue()

enqueue(5)
enqueue(6)

print("队列数组：",queue)
print("front 下标位置：",front)
print("rear 下标位置：",rear)

A. 已满，rear = 1
B. 未满，rear = 1
C. 已满，rear = 2
D. 未满，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的父节点。

📌 大纲对应知识点：二叉搜索树的遍历与结构
🎯 考查目标：掌握BST的中序有序性，以及先序+中序推导树结构的方法

📋 选项详解

⭐ 答案：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 A
B. H I D B E J F G C A
C. I H D E B J F G C A
D. 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. 58
B. 60
C. 62
D. 64

📌 大纲对应知识点：哈夫曼树与哈夫曼编码
🎯 考查目标：掌握哈夫曼树的构造方法与WPL计算

📋 选项详解

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

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

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

📖 题目

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

📌 大纲对应知识点：哈夫曼树的性质
🎯 考查目标：掌握哈夫曼树的节点数与叶子节点数的关系

📋 选项详解

⭐ 答案：B
📌 知识点：哈夫曼树性质、节点数计算

💡 解题小贴士：记住哈夫曼树核心公式：总节点数=2*叶子节点数-1，叶子节点数就是待编码的符号数。

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

📖 题目

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

📌 大纲对应知识点：格雷编码的特性
🎯 考查目标：掌握格雷编码的核心性质与应用

📋 选项详解

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

💡 解题小贴士：格雷码的核心特点是相邻码只有1位不同，可降低状态切换时的错误率，常用于数码管、通信等场景。

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

📖 题目

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

classTreeNode:
def__init__(self,x):
self.val=x
self.left=None
self.right=None
defrightSideView(root):
rightmost_value_at_depth={}
max_depth=-1
node_queue=[]
depth_queue=[]
node_queue.append(root)
depth_queue.append(0)
whilenode_queue:
node=node_queue.pop(0)
depth=depth_queue.pop(0)
ifnodeisnotNone:
max_depth=max(max_depth,depth)
rightmost_value_at_depth[depth]=node.val
node_queue.append(node.left)
node_queue.append(node.right)
# (1) 
depth_queue.append(__________)
depth_queue.append(__________)
right_view=[]
# (2) 补全
fordepthinrange(____________):
right_view.append(rightmost_value_at_depth[depth])

returnright_view
if__name__=="__main__":
root=TreeNode(1)
root.left=TreeNode(2)
root.right=TreeNode(3)
root.left.right=TreeNode(5)
root.right.right=TreeNode(4)
print(rightSideView(root))

A. （1）depth, depth; （2）0, max_depth
B. （1）depth + 1, depth + 1; （2）0, max_depth + 1
C. （1）depth + 1, depth + 1; （2）1, max_depth + 1
D. （1）depth, depth; （2）1, max_depth

📌 大纲对应知识点：二叉树的广度优先搜索
🎯 考查目标：掌握层序遍历的实现与右视图的求解方法

📋 选项详解

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

💡 解题小贴士：层序遍历记录每个节点的深度，最后每层保留最后一个访问的节点，就是右视图的结果。

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

📖 题目

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

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

📋 选项详解

⭐ 答案：C
📌 知识点：DFS、栈、递归

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

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

📖 题目

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

defvisit(nums):
ifnotnums:
return0

size=len(nums)
ifsize==1:
returnnums[0]

dp=[0]*size
dp[0]=nums[0]
dp[1]=max(nums[0],nums[1])

foriinrange(2,size):
__________________________

returndp[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
📌 知识点：动态规划、爬楼梯问题

💡 解题小贴士：斐波那契型递推通常对应计数类问题，比如走法数、方案数等。

二、判断题（每题2分，共20分）

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

📖 题目

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

classPoint:
def__init__(self,px,py):
self.x=px
self.y=py

defprint(self):
print(f"({self.x}, {self.y})")
if__name__=="__main__":
a=Point(3.0,4.0)# ①  
# ②  
b=Point()
a.print()

📌 大纲对应知识点：Python类的构造函数
🎯 考查目标：掌握Python构造函数的特性

📋 解析

❌ 错误。Python中如果自定义了带参数的__init__方法，不会自动生成无参构造函数，调用Point()会缺少参数报错，程序无法正常运行。

💡 解题小贴士：Python构造函数参数必须严格匹配，若要支持无参实例化，需要给__init__的参数设置默认值。

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

📖 题目

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

📌 大纲对应知识点：Python继承与访问控制
🎯 考查目标：理解Python私有成员的访问规则

📋 解析

✅ 正确。Python支持单继承和多继承，双下划线开头的私有成员会进行名称修饰，子类无法直接访问，只能通过父类提供的公共方法访问。

💡 解题小贴士：Python私有成员只是名称被修改为_父类名__成员名，并非完全不可访问，但不建议直接访问。

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

📖 题目

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

        1
       / \
      2   3
     / \
    4   5

classNode:
def__init__(self,v):
self.val=v
self.left=None
self.right=None
deftravel(root):
ifnotroot:
return
stack=[]
stack.append(root)

whilestack:
cur=stack.pop()
print(cur.val,end=" ")
ifcur.right:
stack.append(cur.right)
ifcur.left:
stack.append(cur.left)
if__name__=="__main__":
root=Node(1)
root.left=Node(2)
root.right=Node(3)
root.left.left=Node(4)
root.left.right=Node(5)
travel(root)

📌 大纲对应知识点：二叉树非递归前序遍历
🎯 考查目标：掌握栈实现前序遍历的顺序

📋 解析

❌ 错误。栈是后进先出，先压右孩子再压左孩子，弹出顺序是根→左→右，实际输出是1 2 4 5 3，不是1 2 3 4 5。

💡 解题小贴士：非递归前序遍历，入栈顺序是右孩子先入、左孩子后入，保证弹出时左孩子先处理。

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

📖 题目

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

📌 大纲对应知识点：哈夫曼树的性质
🎯 考查目标：理解哈夫曼树的构造规则

📋 解析

❌ 错误。当字符数是2^k时会得到完全二叉树，否则不是。比如4个字符频率相同，构造的哈夫曼树是完全二叉树；3个字符频率相同，构造的哈夫曼树不是完全二叉树。

💡 解题小贴士：哈夫曼树只要求是最优二叉树，不一定是完全二叉树，和频率分布无关。

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

📖 题目

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

📌 大纲对应知识点：哈夫曼编码的特性
🎯 考查目标：理解前缀编码的含义

📋 解析

✅ 正确。前缀编码的定义是任何一个编码都不是另一个编码的前缀，对应哈夫曼树中所有字符都是叶子节点，没有嵌套关系，解码时可以唯一匹配。

💡 解题小贴士：前缀编码保证了解码的唯一性，不需要分隔符，哈夫曼编码是最优的前缀编码。

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

📖 题目

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

📌 大纲对应知识点：完全二叉树的顺序存储
🎯 考查目标：掌握顺序存储二叉树的下标计算

📋 解析

✅ 正确。根在0下标时，左孩子下标是2i+1，右孩子下标是2i+2，父节点下标是(i-1)//2，这是顺序存储二叉树的标准规则。

💡 解题小贴士：注意根下标是0还是1，根在1时右孩子是2i+1，不要混淆。

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

📖 题目

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

📌 大纲对应知识点：非递归前序遍历
🎯 考查目标：掌握栈实现前序遍历的入栈顺序

📋 解析

❌ 错误。栈是后进先出，要保证左孩子先被处理，应该先压右孩子，再压左孩子，这样弹出时左孩子先出。

💡 解题小贴士：前序遍历非递归入栈顺序：右→左，弹出顺序就是左→右，符合根左右的要求。

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

📖 题目

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

classTreeNode:
def__init__(self,x):
self.val=x
self.left=None
self.right=None
defpreorder(root,res):
ifrootisNone:
return
res.append(root.val)
preorder(root.left,res)
preorder(root.right,res)
defpreorderTraversal(root):
res=[]
preorder(root,res)
returnres

📌 大纲对应知识点：二叉树遍历的复杂度
🎯 考查目标：掌握递归遍历的时间和空间复杂度

📋 解析

✅ 正确。每个节点只访问一次，时间复杂度O(n)；递归栈的深度最坏是n（链式二叉树），空间复杂度O(n)。

💡 解题小贴士：二叉树递归遍历的时间复杂度都是O(n)，空间复杂度最坏O(n)，平均O(logn)。

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

📖 题目

以下代码实现了0-1背包问题的一维动态规划解法，内层循环采用经典的逆序遍历方式。若将内层循环改为正序遍历（即 for j in range(w[i], W + 1):），仍能得到正确答案。

defknapsack_01():
W=5
w=[2,3,4]
v=[10,1,1]
n=3
dp=[0]*(W+1)
foriinrange(n):
forjinrange(W,w[i]-1,-1):
dp[j]=max(dp[j],dp[j-w[i]]+v[i])

print(dp[W])
knapsack_01()

📌 大纲对应知识点：0-1背包的动态规划实现
🎯 考查目标：理解0-1背包逆序遍历的原因

📋 解析

❌ 错误。0-1背包每个物品只能选一次，逆序遍历是为了避免重复选择同一物品；正序遍历会变成完全背包，物品可多次选择，结果错误。

💡 解题小贴士：0-1背包一维DP内层逆序，完全背包内层正序，这是核心区别。

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

📖 题目

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

📌 大纲对应知识点：动态规划的实现方式
🎯 考查目标：理解递推和记忆化搜索的复杂度

📋 解析

✅ 正确。两种方式都是每个状态只计算一次，没有重复计算时，时间复杂度都是状态数乘以每个状态的转移成本，结果相同。

💡 解题小贴士：递推是自底向上，记忆化搜索是自顶向下，只要没有重复计算，时间复杂度一致。

三、编程题（每题25分，共50分）

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

📖 题目描述

给定两个包含n个整数的数组a与b。你需要指定若干下标i（1≤i≤n）使得以下条件成立：
1. 若选中下标i，则所有满足 i < j ≤ i + b[i] 的下标j都不能被选中；
2. 你需要在满足以上条件的前提下最大化∑a[i]，也即最大化数组a对应下标的整数之和。

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

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

样例输入1：

4
1234
3311

样例输出1：

7

样例输入2：

6
114514
123210

样例输出2：

11

数据范围：
对于100%的测试点，保证1≤n≤1e5，0≤a[i]≤1e9，0≤b[i]≤n。

📌 大纲对应知识点：动态规划、线性DP
🎯 考查目标：掌握区间约束下的最大和问题的DP解法

📋 解题思路

定义f[i]表示前i个下标中，满足条件的最大和，且最后一个选中的下标不超过i。状态转移：
1. 不选第i个元素：f[i] = max(f[i], f[i-1])
2. 选第i个元素：则i+1到i+b[i]都不能选，所以f[i + b[i]] = max(f[i + b[i]], f[i] + a[i])
遍历过程中记录最大值即可，时间复杂度O(n)，适用于n=1e5的范围。

📋 参考代码

n=int(input())
a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))

f=[0]*(n+5)
ans=0

foriinrange(1,n+1):
# 选i的情况，更新最大值
ans=max(ans,f[i]+a[i])
# 更新i + b[i]位置的f值
ifi+b[i]<=n:
f[i+b[i]]=max(f[i+b[i]],f[i]+a[i])
# 不选i的情况，传递f值到i+1
f[i+1]=max(f[i+1],f[i])

print(ans)

💡 解题小贴士：这类带区间禁止选择的DP问题，通常可以通过状态传递的方式线性处理，避免区间DP的高复杂度。

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

📖 题目描述

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

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

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

样例输入1：

4
23
40
00
00

样例输出1：

4

样例输入2：

4
23
00
40
00

样例输出2：

3

数据范围：
对于100%的测试点，保证1≤n≤1e5。

📌 大纲对应知识点：二叉树遍历、完全二叉树判定
🎯 考查目标：掌握后序遍历判定子树属性的方法

📋 解题思路

完全二叉树的判定条件（子树）：
1. 左右子树都是完全二叉树；
2. 左子树的最小叶子深度 ≥ 右子树的最大深度（保证右子树不会比左子树深，且左边满）；
3. 整棵子树的最小叶子深度 ≥ 最大深度 - 1（保证最后一层的叶子都靠左）。

通过后序遍历，递归计算每个子树的最大深度、最小叶子深度，以及是否为完全二叉树，统计符合条件的数量，时间复杂度O(n)。

📋 参考代码

n=int(input())
l=[0]*(n+1)
r=[0]*(n+1)
mn=[0]*(n+1)# 子树的最小叶子深度
mx=[0]*(n+1)# 子树的最大深度
chk=[0]*(n+1)# 是否为完全二叉树
ans=0

foriinrange(1,n+1):
li,ri=map(int,input().split())
l[i]=li
r[i]=ri

defdfs(u):
globalans
chk[u]=1
ifu==0:
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]]
# 最小深度 >= 最大深度 - 1
chk[u]&=mn[u]>=mx[u]-1
# 统计答案
ans+=chk[u]

dfs(1)
print(ans)

💡 解题小贴士：子树属性判定通常用后序遍历，先处理左右子树，再合并结果到当前节点，效率最高。

📝 学习建议

1. 面向对象
   ：重点掌握Python类的继承、多态、访问控制，特别是super函数的使用和私有成员的特性。
2. 数据结构
   ：熟练掌握栈、队列、二叉树、哈夫曼树的性质与操作，遍历序列推导、循环队列判满等是高频考点。
3. 算法
   ：动态规划是六级核心考点，需掌握爬楼梯、打家劫舍、背包问题等经典模型，理解递推和记忆化搜索的区别。
4. 编程题
   ：多练习树的遍历、线性DP类题目，掌握O(n)复杂度的解法，应对1e5的数据范围。

💪 更多GESP真题练习、模考功能，欢迎使用「GESP练题小程序艾墨舟编程小先锋」，一站式备考高效提分！