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

2025年12月GESP认证Python五级真题(含答案和解析)一、单选题（每题2分，共30分）。1.对如下定义的循环单链表，横线处填写（）。classNode:def__init__(self,data):self.data=dataself.next=Nonedefcreate_list(value):head=Node(value)head.next=headreturnheaddefinsert_tail(head,value):p=headwhilep.next!=head:p=p.nextnode=Node(value)node.next=headp.next=nodedefprint_list(head):_______________________________whileTrue:print(p.data,end="")p=p.nextifp==head:breakprint()A.ifheadisNone:returnp.next=headB.ifheadisNone:returnp=head.nextC.ifheadisNone:returnp=headD.ifhead.nextisNone:returnp=head答案：C。解析：本题考察循环链表的遍历。（1）判空处理：首先需要判断链表是否为空，如果head为None，则直接返回，避免后续访问报错。（2）指针初始化：遍历应该从头节点开始，因此需要将辅助指针p指向head。（3）循环结构：代码中使用whileTrue配合break模拟了do-while循环（先打印后移动，直到回到头节点）。若p初始化为head.next（选项B），则会漏打头节点；若p.next=head（选项A）则是赋值操作而非初始化，且语法错误；选项D的判空条件不完整（单节点链表会被错误拦截）。综上，选项C正确。2.区块链技术是比特币的基础。在区块链中，每个区块指向前一个区块，构成链式列表，新区块只能接在链尾，不允许在中间插入或删除。下面代码实现插入区块添加函数，则横线处填写（）。classBlock:def__init__(self,idx,data,prev_block):self.index=idxself.data=dataself.prev=prev_blockclassBlockchain:def__init__(self):self.tail=Nonedefinit(self):genesis_block=Block(0,"GenesisBlock",None)self.tail=genesis_blockdefadd_block(self,data):____________________________________defclear(self):cur=self.tailwhilecurisnotNone:prev_block=cur.prevcur.prev=Nonecur=prev_blockself.tail=Nonedefprint_chain(self):cur=self.tailchain=[]whilecurisnotNone:chain.append(f"Block{cur.index}:{cur.data}")cur=cur.prevforblock_infoinreversed(chain):print(block_info)A.new_block=Block(self.tail.index,data,self.data)B.new_block=Block(self.tail.index+1,data,self.tail)self.tail=new_blockC.new_block=Block(self.tail.index,data+1,self.data)self.tail=new_blockD.new_block=Block(self.tail.index,data,self.tail)self.tail.data=new_block答案：B。解析：本题考察链表的尾部插入操作。（1）新节点属性：新区块的索引index应当是前一个区块（当前尾节点）的索引加1，即self.tail.index+1。（2）前驱指针：新区块的prev指针应当指向当前的尾节点self.tail。（3）更新尾指针：新区块生成后，链表的tail引用需要更新为指向这个新区块。选项B完整实现了上述逻辑。A选项未更新tail且索引错误；C选项data+1逻辑不明；D选项错误地修改了原尾节点的data。3.下面关于单链表和双链表的描述中，正确的是（）。classDNode:def__init__(self,data):self.data=dataself.prev=Noneself.next=Nonedefdelete_dnode(node):ifnode.prev:node.prev.next=node.nextifnode.next:node.next.prev=node.prevnode.prev=Nonenode.next=NoneclassSNode:def__init__(self,data):self.data=dataself.next=Nonedefdelete_snode(head,node):ifheadisNoneornodeisNone:returnprev=headwhileprev.next!=node:prev=prev.nextprev.next=node.nextnode.next=NoneA.双链表删除指定节点是O(1)，单链表是O(1)。B.双链表删除指定节点是O(n)，单链表是O(1)。C.双链表删除指定节点是O(1)，单链表是O(n)。D.双链表删除指定节点是O(n)，单链表是O(n)。答案：C。解析：本题考察链表操作的时间复杂度。双链表：给定要删除的节点node，可以直接通过node.prev访问前驱节点，修改指针即可完成删除，时间复杂度为。单链表：给定要删除的节点node，无法直接获取前驱节点，必须从头遍历链表寻找node的前一个节点，最坏情况需要遍历整个链表，时间复杂度为。故选C。4.假设我们有两个数a=38和n=14，它们对模m同余，即a≡b(modm)。以下哪个值不可能是m？（）。A.3B.4C.6D.9答案：D。解析：a≡b(modm)等价于a-b是m的倍数。38-14=24。m必须是24的约数。24的约数有：1,2,3,4,6,8,12,24。9不是24的约数，故选D。5.下面代码实现了欧几里得算法，下面有关说法，错误的是（）。defgcd1(a:int,b:int)->int:returnaifb==0elsegcd1(b,a%b)defgcd2(a:int,b:int)->int:whileb!=0:temp=bb=a%ba=tempreturnaA.gcd1()实现为递归方式。B.gcd2()实现为迭代方式。C.当a较大时，gcd1()实现会多次调用自身，需要较多额外的辅助空间。D.当a较大时，gcd1()的实现比gcd2()执行效率更高。答案：D。解析：A、B正确：gcd1递归，gcd2迭代。C正确：递归深度大时消耗栈空间。D错误：Python中函数调用开销大且无尾递归优化，递归版效率通常低于或等于迭代版，不会“显著更高”。6.唯一分解定理描述的内容是（）。A.任何正整数都可以表示为两个素数的和。B.任何大于1的合数都可以唯一分解为有限个质数的乘积。C.两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积。D.所有素数都是奇数。答案：B。解析：唯一分解定理（算术基本定理）指出：任何大于1的整数，要么本身是质数，要么可以唯一地分解为有限个质数的乘积。选项B符合定义。A是哥德巴赫猜想；C是GCD与LCM的关系公式，不是唯一分解定理；D是错误的（2是偶素数）。故选B。7.下述代码实现素数表的线性筛法，筛选出所有小于等于n的素数，则横线上应填的代码是（）。deflinear_sieve(n):ifn<2:return[]is_prime=[True]*(n+1)is_prime[0]=is_prime[1]=Falseprimes=[]foriinrange(2,n+1):ifis_prime[i]:primes.append(i)forjinrange(len(primes)):p=primes[j]ifi*p>n:break__________________________ifi%p==0:breakreturnprimesA.is_prime[i*p]=FalseB.is_prime[i]=FalseC.is_prime[i*p]=TrueD.is_prime[i+p]=False答案：A。解析：线性筛法中，当前数i与已找到的素数p相乘得到合数i*p，需要将其标记为非素数。故填is_prime[i*p]=False。8.下列关于排序的说法，正确的是（）。A.快速排序是稳定排序B.归并排序通常是稳定的C.插入排序是不稳定排序D.冒泡排序不是原地排序答案：B。解析：A错：快速排序不稳定。B对：归并排序在合并时遇到相等元素优先取左侧，保持相对位置，是稳定的。C错：插入排序是稳定的。D错：冒泡排序是原地排序。9.下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是（）。defmerge(arr,temp,l,mid,r):i=lj=mid+1k=lwhilei<=midandj<=r:ifarr[i]<=arr[j]:temp[k]=arr[i]i+=1else:temp[k]=arr[j]j+=1k+=1whilei<=mid:temp[k]=arr[i]i+=1k+=1whilej<=r:temp[k]=arr[j]j+=1k+=1forpinrange(l,r+1):arr[p]=temp[p]defmerge_sort(arr,temp,l,r):ifl>=r:returnmid=l+(r-l)//2merge_sort(arr,temp,l,mid)merge_sort(arr,temp,mid+1,r)merge(arr,temp,l,mid,r)defmerge_sort_wrapper(arr):ifnotarr:return[]temp=[0]*len(arr)merge_sort(arr,temp,0,len(arr)-1)returnarrA.归并排序的的平均复杂度是O(nlogn)。B.归并排序需要O(n)的额外空间。C.归并排序在最坏情况的时间复杂度是O(n2)。D.归并排序适合大规模数据。答案：C。解析：归并排序的性能稳定，最好、最坏、平均时间复杂度均为O(nlogn)，不会退化为O(n2)。C说法错误。10.下述python代码实现了快速排序算法，最差情况时间复杂度是（）。defpartition(arr,low,high):i=lowj=highpivot=arr[low]whilei<j:whilei<jandarr[j]>=pivot:j-=1whilei<jandarr[i]<=pivot:i+=1ifi<j:arr[i],arr[j]=arr[j],arr[i]arr[i],arr[low]=arr[low],arr[i]returnidefquick_sort(arr,low,high):iflow>=high:returnp=partition(arr,low,high)quick_sort(arr,low,p-1)quick_sort(arr,p+1,high)defquick_sort_wrapper(arr):ifnotarr:return[]quick_sort(arr,0,len(arr)-1)returnarrA.O(n)B.O(logn)C.O(n2)D.O(nlogn)答案：C。解析：快速排序若每次选取的基准值都是当前最大或最小值（如数组已有序且选首元素为基准），递归深度为n，复杂度退化为O(n2)。11.下面代码尝试在有序数组中查找第一个大于等于x的元素位置。如果没有大于等于x的元素，返回arr.size()。以下说法正确的是（）。deflower_bound(arr,x):l=0r=len(arr)whilel<r:mid=l+(r-l)//2ifarr[mid]>=x:r=midelse:l=mid+1returnlA.上述代码逻辑正确B.上述代码逻辑错误，while循环条件应该用l<=r。C.上述代码逻辑错误，mid计算错误。D.上述代码逻辑错误，边界条件不对。答案：A。解析：lower_bound模板：左闭右开区间[0,len)。当arr[mid]>=x时，答案可能是mid或更左，r=mid；否则l=mid+1。逻辑完全正确。12.小杨要把一根长度为L的木头切成K段，使得每段长度小于等于x。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小x（x为正整数），则横线处应填写（）。defcheck(L,K,x):cuts=(L-1)//xreturncuts<=Kdefbinary_cut(L,K):l=1r=Lwhilel<r:___________________returnlif__name__=="__main__":L=10K=2result=binary_cut(L,K)print(result)A.mid=l+(r-l)//2ifcheck(L,K,mid):r=midelse:l=mid+1B.mid=l+(r)//2ifcheck(L,K,mid+1):r=midelse:l=mid+1C.mid=l+(r-l)//2ifcheck(L+1,K,mid):r=midelse:l=mid+1D.mid=l+(r-l)//2ifcheck(L+1,K,mid):r=midelse:l=mid答案：A。解析：求满足条件的最小值。若check(mid)为真，说明可行，答案可能是mid或更小，收缩右边界r=mid；若不可行，说明太小，l=mid+1。选A。13.根据下面代码，以下说法正确的是（）。deffactorial1(n):ifn<=1:return1returnn*factorial1(n-1)deffactorial2(n):result=1whilen>1:result*=nn-=1returnresultA.上面两种实现方式的时间复杂度相同，都为O(n)。B.上面两种实现方式空间复杂度相同，都为O(1)。C.函数factorial1()的时间复杂度为O(2n)，函数factorial2()的时间复杂度为O(n)。D.上面两种实现方式空间复杂度相同，都为O(n)。答案：A。解析：两种方式都执行n次乘法，时间复杂度均为O(n)。空间上递归为O(n)（栈），迭代为O(1)。A选项描述正确。14.给定有n个任务，每个任务有截止时间和利润，每个任务耗时1个时间单位、必须在截止时间前完成，且每个时间槽最多做1个任务。为了在规定时间内获得最大利润，可以采用贪心策略，即按利润从高到低排序，尽量安排，则横线处应填写（）。classTask:def__init__(self,deadline,profit):self.deadline=deadlinefit=profitdefsort_by_profit(tasks):tasks.sort(key=lambdax:fit,reverse=True)defmax_profit(tasks):sort_by_profit(tasks)max_time=0fortaskintasks:iftask.deadline>max_time:max_time=task.deadlineslot=[False]*(max_time+1)total_profit=0fortaskintasks:t=task.deadlinewhilet>=1:ifnotslot[t]:___________________________t-=1returntotal_profitA.slot[t]=Truetotal_profit+=fitbreakB.slot[t]=Truetotal_profit+=fitC.slot[t]=Falsetotal_profit+=fitbreakD.slot[t]=Truetotal_profit-=fit答案：A。解析：贪心策略：找到符合条件的空闲时间槽后，标记占用slot[t]=True，累加利润，并必须立即停止为该任务寻找槽位break，转而处理下一个任务。15.下面代码实现了对两个数组表示的正整数的高精度加法（数组低位在前），则横线上应填写（）。defadd(a,b):c=[]carry=0i=0whilei<len(a)ori<len(b):ifi<len(a):carry+=a[i]ifi<len(b):carry+=b[i]____________________i+=1ifcarry:c.append(carry)returncA.c.append(carry%10)B.c.append(carry%10)carry=carry//10C.carry=carry//10D.c.append(carry//10)carry=carry%10答案：B。解析：高精度加法进位逻辑：当前位保留carry%10，进位carry更新为carry//10传入下一轮。二、判断题（每题2分，共20分）。16.数组和链表都是线性表。链表的优点是插入删除不需要移动元素，并且能随机查找。（）。答案：错误。解析：链表不支持随机查找，访问第k个元素需要O(n)遍历。17.假设函数gcd()函数能正确求两个正整数的最大公约数，则下面的lcm(a，b)函数能正确找到两个正整数a和b的最小公倍数。（）。importmathdeflcm(a,b):ifa==0orb==0:return0returnabs(a)//math.gcd(abs(a),abs(b))*abs(b)答案：正确。解析：最小公倍数公式lcm(a,b)=|a·b|/gcd(a,b)正确。18.在Python实现的单链表中，已知引用p指向要删除的节点（该节点不是尾节点），若想在O(1)时间复杂度内删除这个节点，可行的做法是：用p的后继节点p.next的值覆盖p自身的值，再用p的后继节点的next引用覆盖p的next引用，最后断开p的后继节点的引用以辅助垃圾回收（）。答案：正确。解析：通过复制后继节点的值和指针覆盖当前节点，可实现O(1)删除非尾节点（逻辑上删除了当前节点数据）。19.在求解所有不大于n的素数时，线性筛法（欧拉筛）都应当优先于埃氏筛法使用，因为线性筛法的时间复杂度为O(n)，低于埃氏筛法的O(nloglogn)。（）。答案：错误。解析：在Python中，埃氏筛配合切片操作常数极小，对于中等范围数据往往比纯Python实现的线性筛更快，不能一概而论。20.二分查找仅适用于有序数据。若输入数据无序，当仅进行一次查找时，为了使用二分而排序通常不划算。（）。答案：正确。解析：单次查找：线性查找O(n)，排序+二分O(nlogn)。只查一次不值得排序。21.通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴（比较基准），快速排序算法可降低落入最坏情况的概率。（）。答案：正确。解析：三数取中法选择基准，可避免有序或逆序输入的O(n2)最坏情况。22.贪心算法在每一步都做出当前看来最优的局部选择，并且一旦做出选择就不再回溯；而分治算法将问题分解为若干子问题分别求解，再将子问题的解合并得到原问题的解。（）。答案：正确。解析：描述正确。贪心是局部最优不回溯，分治是分解子问题合并。23.以下fib函数计算第n项斐波那契数（fib(0)=0,fib(1)=1），其时间复杂度为O(n)。（）。deffib(n):ifn<=1:returnnreturnfib(n-1)+fib(n-2)答案：错误。解析：该实现是朴素递归版本的斐波那契数计算。每次调用fib(n)会递归计算fib(n-1)和fib(n-2)，而这些子问题又会重复计算大量相同的子结果。递归调用树的规模呈指数增长，时间复杂度O(φn)，其中φ≈1.618（即黄金分割比），而不是O(n)。若要达到O(n)的时间复杂度，需要使用循环或带记忆化的递归。因此题中说法错误，答案为错误。24.递归函数一定要有终止条件，否则可能会造成栈溢出。（）。答案：正确。解析：无终止条件的递归会无限进行，导致栈溢出。25.使用贪心算法解决问题时，通过对每一步求局部最优解，最终一定能找到全局最优解。（）。答案：错误。解析：贪心算法仅对满足贪心选择性质和最优子结构的问题有效，并不保证对所有问题都能得到全局最优解（如背包问题）。三、编程题（每题25分，共50分）。26.试题名称：数字移动。时间限制：3.0s。内存限制：512.0MB。题目描述：小A有一个包含N个正整数的序列A={A1,A2…AN}，序列A恰好包含N/2对不同的正整数。形式化地，对于任意1≤i≤N，存在唯一一个j满足1≤j≤N,i≠j,Ai=Aj。小A希望每对相同的数字在序列中相邻，为了实现这一目的，小A每次操作会选择任意i（1≤i≤N），将当前序列的第i个数字移动到任意位置，并花费对应数字的体力。例如，假设序列A={1,2,1,3,2,3}，小A可以选择i=2，将A2移动到A3的后面，此时序列变为A={1,1,2,3,2,3}，耗费2点体力。小A也可以选择i=3，将A3=1移动到A2=2的前面，此时序列变为A={1,1,2,3,2,3}，花费1点体力。小A可以执行任意次操作，但他希望自己每次花费的体力尽可能小。小A希望你能帮他计算出一个最小的x，使得他能够在每次花费的体力均不超过x的情况下令每对相同的数字在序列中相邻。输入格式：第一行一个正整数N，代表序列长度，保证N为偶数。第二行包含N个正整数A1,A2…AN，代表序列A。且对于任意1≤i≤N，存在唯一一个j满足1≤j≤N,i≠j,Ai=Aj。数据保证小A至少需要执行一次操作。输出格式：输出一行，代表满足要求的x的最小值。输入样例。输出样例。数据范围：对于40%的测试点，保证1≤N,Ai≤100。对于所有测试点，保证1≤N,Ai≤105。参考程序。#输入n和a数组。n=int(input())a=[]whilelen(a)<n:a.extend(map(int,input().split()))#答案的上下界。left,right=0,1000000ans=1000000#二分搜索。whileleft<=right:#考虑mid的力气能否完成任务。mid=(left+right)//2#筛选出所有大于mid的数字。b=[xforxinaifx>mid]#先假设能够完成任务。possible=Trueforiinrange(0,len(b),2):#如果两个相同且大于mid的数字，中间还有其它的大于mid的数字，则本任务无法完成。#以(121323)为例，两个3之间存在一个2。假设最大只能挪动1，则不论如何两个3之间的2不会被挪动，最终无法完成任务。ifb[i]!=b[i+1]:possible=Falsebreak#如果能够成功，则尝试更小的mid。ifpossible:ans=midright=mid-1else:left=mid+1print(ans)解析：题目大意：给定N/2对正整数组成的序列，保证数对不重复，可以移动任意数到任意位置，最终使得相同的正整数都相邻，希望求出一个最小的移动数上限，在只移动不超过上限的情况下达成目标。解法：40%部分分可以采用枚举+验证的方法，枚举上限ans，验证该上限时能否达成目标；时间复杂度为O(N.max(Ai))。验证的逻辑：当力气上限是ans时，所有≤ans的数都可以任意移动，因此这些数必然可以相邻。验证的关键在于＞ans的数，这些数的位置是固定不能移动的。对于初始位置不相邻的>ans的一组数对，其之间所有≤ans的数都可以移走，但是如果有其他>ans的数不能移走，就证明力气上限ans无法达成，需要将ans变大，重新验证。例：(1323)，两个3之间存在一个2。假设最大只能挪动1，则不论如何，两个3之间的2不会被挪动，最终无法完成任务。实现方法为先用列表b按顺序存储所有大于上限的数，遍历列表b，如果相邻两项(b[i],b[i+1])不是相同的数，表明其中间有其他无法移动的数，判断任务失败；遍历完成没有提前终止循环，则证明任务成功。100%满分做法可以发现，上限ans越大，可以移动的数越大，当上限=ans可以完成任务时，上限>ans一定也可以完成任务；反之，上限=ans不可以完成任务时，上限<ans一定也不可以完成任务，存在单调性，因此可以使用二分枚举上限ans，时间复杂度优化为O(N·log(max(ai)))。27.试题名称：相等序列。时间限制：3.0s。内存限制：512.0MB。题目描述：小A有一个包含N个正整数的序列A={A1,A2…AN}。小A每次可以花费1个金币执行以下任意一种操作。（1）选择序列中一个正整数Ai(1≤i≤N)，将Ai变为Ai×P，P为任意质数。（2）选择序列中一个正整数Ai(1≤i≤N)，将Ai变为Ai÷P，P为任意质数，要求Ai能整除P。小A想请你帮他计算出令序列中所有整数都相同，最少需要花费多少金币。输入格式：第一行一个正整数N，含义如题面所示。第二行包含N个正整数A1,A2…AN，代表序列A。输出格式：输出一行，代表最少需要花费的金币数量。输入样例。输出样例。数据范围：对于60%的测试点，保证1≤N,Ai≤100。对于所有测试点，保证1≤N,Ai≤105。参考程序。tokens=[]defget_val():whilenottokens:tokens.extend(input().split())returnint(tokens.pop(0))#一共有多少数。n=get_val()#key：质数。#value：一个列表，num[2][3]表示有多少数质因数分解后可以包含2^3。#因为一个数最大就到10^5，相当于是10w，所以列表最多包含20个数肯定