2025年12月GESP认证Python六级真题(含答案和解析)

2025年12月GESP认证Python六级真题(含答案和解析)一、单选题（每题2分，共30分）。1.在Python的面向对象编程中，下列关于“动态绑定（等效于虚函数）”的描述中，错误的是（）。A.动态绑定用于支持运行时多态。B.通过基类变量调用方法时，会根据对象实际类型决定调用版本。C.构造函数（__init__）可以通过动态绑定实现多态以支持灵活初始化。D.基类析构函数（__del__）常保证子类调用其实现，以避免资源泄漏析构函数常声明为虚函数以避免资源泄漏。答案：C。解析：在Python中，构造函数（__init__）本身并不是通过动态绑定来实现多态的，创建对象时是直接调用对应类的__init__。2.执行如下代码，将输出钢琴：叮咚叮咚和吉他：咚咚当当而不是两行乐器在演奏声音，这体现了面向对象编程的（）特性。classInstrument:"""基类：乐器"""。defplay(self):print("乐器在演奏声音")def__del__(self):passclassPiano(Instrument):"""子类：钢琴"""。defplay(self):print("钢琴：叮咚叮咚")classGuitar(Instrument):defplay(self):print("吉他：咚咚当当")if__name__=="__main__":instruments=[Piano(),Guitar()]forinstininstruments:inst.play()A.继承B.封装C.多态D.链接答案：C。解析：代码中基类Instrument定义了play方法，子类Piano和Guitar重写了该方法。当通过基类变量（列表中的元素）调用play方法时，实际调用的是子类重写后的方法，因此输出子类特定的内容，体现了运行时多态。3.执行下面代码，将输出（）。classInstrument:defplay(self):print("乐器在演奏声音")def__del__(self):passclassPiano(Instrument):defplay(self):print("钢琴：叮咚叮咚")classGuitar(Instrument):defplay(self):print("吉他：咚咚当当")if__name__=="__main__":instruments=[Piano(),Guitar()]forinstininstruments:Instrument.play(inst)A.钢琴：叮咚叮咚吉他：咚咚当当B.乐器在演奏声音乐器在演奏声音C.编译错误D.运行错误答案：B。解析：在Python中，通过类名直接调用方法（如Instrument.play(inst)）属于静态绑定，此时传递的实例inst作为self参数传入，但方法体使用的是Instrument类中定义的play方法，而不是子类重写的方法。因此，无论inst是Piano还是Guitar实例，都会执行Instrument.play，输出两行“乐器在演奏声音”。4.某文本编辑器把用户输入的字符依次压入栈S。用户依次输入A,B,C,D后，用户按了两次撤销（每次撤销，弹出栈顶一个字符）。此时栈从栈底到栈顶的内容是：（）。A.ABB.ABCC.ABDD.BC答案：A。解析：输入顺序为A,B,C,D，栈顶为D。第一次撤销弹出D，栈中剩余A,B,C；第二次撤销弹出C，栈中剩余A,B。因此栈底到栈顶为AB。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。入队×3：rear依次变为2,3,4。出队×1：front变为2。入队×2：rear依次变为5,0（模6）。最终：front=2,rear=0。6.以下函数check()用于判断一棵二叉树是否为（）。classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightfromcollectionsimportdequedefcheck(root):ifnotroot:returnTrueq=deque()q.append(root)has_null=Falsewhileq:cur=q.popleft()ifnotcur:has_null=Trueelse:ifhas_null:returnFalseq.append(cur.left)q.append(cur.right)returnTrueA.满二叉树B.完全二叉树C.二叉搜索树D.平衡二叉树答案：B。解析：该函数通过层序遍历判断二叉树是否为完全二叉树：若在遇到空节点之后又遇到非空节点，则不是完全二叉树。完全二叉树要求最后一层节点从左到右连续排列。7.以下代码实现了二叉树的（）。classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeftraverse(root):ifnotroot:returntraverse(root.left)traverse(root.right)print(root.val,end="")if__name__=="__main__":root=TreeNode(1)root.right=TreeNode(2)root.right.left=TreeNode(3)print("后序遍历结果：",end="")traverse(root)A.前序遍历B.中序遍历C.后序遍历D.层序遍历答案：C。解析：遍历顺序为：左子树→右子树→根节点，符合后序遍历的定义。8.下面代码实现了哈夫曼编码，则横线处应填写的代码是（）。classSymbol:def__init__(self,ch='',freq=0,code=''):self.ch=chself.freq=freqself.code=codeclassNode:def__init__(self,w=0,l=-1,r=-1,sym=-1):self.w=wself.l=lself.r=rself.sym=symdefpop_min_node(nodes,leaf_idx,n,pA,internal_idx,pB):ifpA[0]<nand(pB[0]>=len(internal_idx)ornodes[leaf_idx[pA[0]]].w<=nodes[internal_idx[pB[0]]].w):res=leaf_idx[pA[0]]pA[0]+=1returnreselse:res=internal_idx[pB[0]]pB[0]+=1returnresdefdfs_build_codes(u,nodes,sym_list,path):ifu==-1:returnifnodes[u].sym!=-1:sym_list[nodes[u].sym].code=''.join(path)returnpath.append('0')dfs_build_codes(nodes[u].l,nodes,sym_list,path)path.pop()path.append('1')dfs_build_codes(nodes[u].r,nodes,sym_list,path)path.pop()defbuild_huffman_codes(sym_list):n=len(sym_list)forsyminsym_list:sym.code=''ifn<=0:return-1ifn==1:sym_list[0].code='0'return0nodes=[]leaf_idx=[]foriinrange(n):leaf_idx.append(len(nodes))nodes.append(Node(sym_list[i].freq,-1,-1,i))leaf_idx.sort(key=lambdax:(nodes[x].w,nodes[x].sym))internal_idx=[]pA=[0]pB=[0]forkinrange(1,n):x=pop_min_node(nodes,leaf_idx,n,pA,internal_idx,pB)y=pop_min_node(nodes,leaf_idx,n,pA,internal_idx,pB)z=len(nodes)______________________________root=internal_idx[-1]ifinternal_idxelse-1path=[]dfs_build_codes(root,nodes,sym_list,path)returnrootif__name__=="__main__":syms=[Symbol('A',5),Symbol('B',9),Symbol('C',12),Symbol('D',13),Symbol('E',16),Symbol('F',45)]root=build_huffman_codes(syms)print(f"哈夫曼树根节点下标：{root}")forsyminsyms:print(f"字符'{sym.ch}'(频率{sym.freq})：编码{sym.code}")A.nodes.append(Node(nodes[x].w+nodes[y].w,x,y,-1))internal_idx.append(z)B.nodes.append(Node(nodes[x].w+nodes[y].w,x,y,1))internal_idx.append(z)C.nodes.append(Node(nodes[x-1].w+nodes[y].w,x,y,1))internal_idx.append(z)D.nodes.append(Node(nodes[x+1].w+nodes[y].w,x,y,1))internal_idx.append(z)答案：A。解析：哈夫曼树构建过程中，合并两个节点生成新节点，其权值为两子节点权值之和，左右孩子分别为x和y，新节点应加入内部节点队列internal_idx。9.以下关于哈夫曼编码的说法，正确的是（）。A.哈夫曼编码是定长编码B.哈夫曼编码中，没有任何一个字符的编码是另一个字符编码的前缀。C.哈夫曼编码一定唯一D.哈夫曼编码不能用于数据压缩答案：B。解析：哈夫曼编码是一种变长前缀编码，任一字符的编码都不是另一字符编码的前缀，因此解码时不会产生歧义。编码结果不唯一（合并顺序可调），但均为最优前缀码。10.以下函数实现了二叉排序树（BST）的（）操作。classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefop(root,x):ifnotroot:returnTreeNode(x)ifx<root.val:root.left=op(root.left,x)else:root.right=op(root.right,x)returnrootA.查找B.插入C.删除D.遍历答案：B。解析：函数在二叉排序树中查找插入位置，若当前节点为空则创建新节点并返回，否则根据值大小递归插入左子树或右子树，最终返回根节点，符合插入操作的逻辑。11.下列代码实现了树的深度优先遍历，则横线处应填入（）。classTreeNode:def__init__(self,x):self.val=xself.left=Noneself.right=Nonedefdfs1(root):ifnotroot:returntemp=[]temp.append(root)whiletemp:node=temp[-1]temp.pop()print(node.val,end="")ifnode.right:temp.append(node.right)ifnode.left:temp.append(node.left)defdfs2(root):ifnotroot:returnst=[]st.append(root)whilest:node=st[-1]st.pop()print(node.val,end="")ifnode.right:st.append(node.right)________________A.ifnode.left:st.append(node.left)B.ifnode.right:st.append(node.left)C.ifnode.left:st.append(node.right)D.ifnode.right:st.append(node.right)答案：A。解析：本题考查二叉树的迭代式深度优先遍历(DFS)，为了实现遍历顺序是根→左→右，想要左子树优先于右子树被处理，就必须让左子节点后入栈、右子节点先入栈。这样出栈顺序是左孩子先于右孩子，符合前序遍历。12.给定一棵普通二叉树（节点值没有大小规律），下面代码判断是否存在值为x的结点，则横线处应填入（）。classTreeNode:def__init__(self,x):self.val=xself.left=Noneself.right=Nonefromcollectionsimportdequedefbfs_find(root,x):ifnotroot:returnNoneq=deque()q.append(root)whileq:cur=q.popleft()ifcur.val==x:returncur______________________returnNoneA.q.append(cur.left)B.q.append(cur.right)C.ifcur.left:q.append(cur.left)ifcur.right:q.append(cur.right)D.ifcur.right:q.append(cur.left)ifcur.left:q.append(cur.right)答案：C。解析：BFS遍历二叉树时，应将当前节点的左孩子和右孩子（若存在）依次入队，以保证层序访问所有节点。注意，需要先判断孩子节点是否存在，再入队。13.在二叉排序树（BinarySearchTree,BST）中，假设节点值互不相同。给定如下搜索函数，以下说法一定正确的是（）。classNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeffind(root,x):whileroot:ifroot.val==x:returnTrueifx<root.val:root=root.leftelse:root=root.rightreturnFalseA.最坏情况下，访问结点数是O(logn)。B.最坏情况下，访问结点数是O(n)。C.无论如何，访问结点数都不超过树高的一半。D.一定比在普通二叉树中搜索快答案：B。解析：BST查找的平均时间复杂度为O(logn)，但在最坏情况下（树退化为链表），时间复杂度为O(n)。因此选项B正确。14.题0/1背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。遍历的方向无所谓，则下面说法正确的是（）。defzero_one_knapsack(items,W):dp=[0]*(W+1)forw,vinitems:forjinrange(W,w-1,-1):dp[j]=max(dp[j],dp[j-w]+v)returndp[W]A.内层j必须从小到大，否则会漏解。B.内层j必须从大到小，否则同一件物品会被用多次。C.j从大到小或从小到大都一样D.只要dp初始为0，方向无所谓。答案：B。解析：0/1背包中，物品只能选一次。若j从小到大遍历，则dp[j-w]可能已经包含当前物品，导致物品被重复使用，相当于完全背包。因此必须从大到小遍历。15.以下关于动态规划的说法中，错误的是（）。A.动态规划方法通常能够列出递推公式。B.动态规划方法的时间复杂度通常为状态的个数。C.动态规划方法有递推和递归两种实现形式。D.在使用动态规划思想（即避免重复子问题）的前提下，递推实现与递归实现（记忆化搜索）的时间复杂度通常是相当的。答案：B。解析：动态规划的时间复杂度不仅与状态个数有关，还与状态转移的复杂度有关。例如，状态数为O(n)，每个状态转移需要O(m)时间，则总复杂度为O(n˙m)，不一定等于状态个数。二、判断题（每题2分，共20分）。16.以下代码中，构造函数被调用的次数是1次。（）。classTest:init_count=0def__init__(self):Test.init_count+=1print("T",end="")def__copy__(self):print("（拷贝构造，不触发__init__）",end="")new_obj=Test.__new__(Test)returnnew_objif__name__=="__main__":a=Test()importcopyb=copy.copy(a)答案：错误。解析：在Python中，__new__：构造方法（创建对象），__init__：初始化方法（初始化对象）；代码中__new__调用2次（创建a和b），__init__调用1次。这里构造方法（__new__）被调用了两次。因此，该说法错误。17.面向对象编程中，封装是指将数据和操作数据的方法绑定在一起，并对外隐藏实现细节。（）。答案：正确。解析：封装是面向对象三大特性之一，指将数据（属性）和操作数据的方法（函数）封装在类中，通过访问控制（public、private、protected）隐藏内部实现。18.以下代码能够正确统计二叉树中叶子结点的数量。（）。classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefcount_leaf(root):ifnotroot:return0ifnotroot.leftandnotroot.right:return1returncount_leaf(root.left)+count_leaf(root.right)if__name__=="__main__":root1=TreeNode(1)root1.left=TreeNode(2)root1.right=TreeNode(3)root1.left.left=TreeNode(4)root1.left.right=TreeNode(5)root1.right.right=TreeNode(6)print(f"二叉树1的叶子节点数：{count_leaf(root1)}")root2=TreeNode(1)print(f"二叉树2的叶子节点数：{count_leaf(root2)}")1root3=Noneprint(f"空树的叶子节点数：{count_leaf(root3)}")答案：正确。解析：函数递归判断：若节点为空返回0；若节点左右孩子均为空则为叶子节点返回1；否则递归统计左右子树的叶子节点数。19.广度优先遍历二叉树可用栈来实现。（）。答案：错误。解析：BFS使用队列实现（先进先出），以保证按层遍历；DFS才使用栈（先进后出）实现深度优先。因此该说法错误。20.函数调用管理可用栈来管理。（）。答案：正确。解析：函数调用栈（callstack）用于存储函数调用信息（返回地址、局部变量等），支持函数调用与返回的“后进先出”顺序。21.在二叉排序树（BST）中，若某结点的左子树为空，则该结点一定是整棵树中的最小值结点。（）。答案：错误。解析：若某节点左子树为空，不一定是整棵树的最小值。整棵树的最小值应从根节点一直向左遍历至叶子节点。22.下面的函数能正确判断一棵树是不是二叉排序树（左边的数字要比当前数字小，右边的数字要比当前数字大）。（）。classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_bst(root,min_val=float('-inf'),max_val=float('inf')):ifnotroot:returnTrueifroot.val<=min_valorroot.val>=max_val:returnFalsereturnis_bst(root.left,min_val,root.val)andis_bst(root.right,root.val,max_val)答案：正确。解析：函数通过传入当前节点值的上下界（min_val,max_val）递归判断左右子树是否满足BST性质：左子树所有节点值应小于当前值，右子树所有节点值应大于当前值。23.格雷编码相邻两个编码之间必须有多位不同，以避免数据传输错误。（）。答案：错误。解析：格雷编码的核心特性是相邻两个编码之间仅有一位不同，这有助于减少在数字电路或通信中因多位同时变化而产生的错误。24.小杨在玩一个闯关游戏，从第1关走到第4关。每一关的体力消耗如下（下标表示关卡编号）：cost=[0,3,5,2,4]，其中cost[i]表示到达第i关需要消耗的体力，cost[0]=0表示在开始状态，体力消耗为0。小杨每次可以从当前关卡前进1步或2步。按照上述规则，从第1关到第4关所需消耗的最小体力为7。（）。答案：错误。解析：设dp[i]表示到达第i关的最小体力消耗，则。dp[1]=cost[1]=3。dp[2]=min(dp[1]+cost[2],cost[2])=min(3+5,5)=5。dp[3]=min(dp[2]+cost[3],dp[1]+cost[3])=min(5+2,3+2)=5。dp[4]=min(dp[3]+cost[4],dp[2]+cost[4])=min(5+4,5+4)=9。因此最小体力为9，不是7。25.假定只有一个根节点的树的深度为1，则一棵有n个节点的完全二叉树，则树的深度为[log2(n)]+1。（）。答案：正确。解析：完全二叉树的深度（高度）公式为：h=[log2(n)]+1（根节点深度为1），该公式成立。三、编程题（每题25分，共50分）。26.试题名称：路径覆盖。时间限制：3.0s。内存限制：512.0MB。题目描述：给定一棵有n个结点的有根树T，结点依次以1,2…n编号，根结点编号为1。方便起见，编号为i的结点称为结点i。初始时T中的结点均为白色。你需要将T中的若干个结点染为黑色，使得所有叶子到根的路径上至少有一个黑色结点。将结点i染为黑色需要代价ci，你需要在满足以上条件的情况下，最小化染色代价之和。叶子是指T中没有子结点的结点。输入格式：第一行，一个正整数n，表示结点数量。第二行，n-1个正整数f2,f3…fn，其中fi表示结点i的父结点的编号，保证fi<i。第三行，n个正整数c1,c2…cn，其中ci表示将结点i染为黑色所需的代价。输出格式：一行，一个整数，表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下，染色代价之和的最小值。输入样例1。输出样例1。输入样例2。输出样例2。数据范围：对于40%的测试点，保证2≤n≤16。对于另外20%的测试点，保证fi=i-1。对于所有测试点，保证2≤n≤105，1≤ci≤109。参考程序。getint=lambda:map(int,input().split())getints=lambda:list(getint())#获取节点数。n=int(input())#各个节点的根节点。f=[0,0]+getints()#各个节点涂黑的成本。c=[0]+getints()#cnt[i]表示节点i有多少子节点。cnt=[0]*(n+1)#ans[i]表示以节点i为根节点的子树，需要多少成本才能让所有叶子结点到根节点都有涂黑的节点。ans=[0]*(n+1)#统计一个节点有多少子节点。foriinrange(2,n+1):cnt[f[i]]+=1#遍历每一个节点，因为一个节点的父节点编号肯定这个节点，所以大编号的一定更深。foriinrange(n,0,-1):#如果一个节点没有子节点，那么显然ans[i]=c[i]就是把自己涂黑。ifcnt[i]==0:ans[i]=c[i]#一个节点当前已经找到的答案等于。