2025年IOI竞赛模拟试卷：编程算法与问题解决能力提升

2025年IOI竞赛模拟试卷：编程算法与问题解决能力提升一、算法设计要求：本部分主要考查学生对于常见算法的设计和实现能力，包括排序算法、查找算法和递归算法等。1.编写一个函数，实现一个冒泡排序算法，输入一个整数数组，返回排序后的数组。```pythondefbubble_sort(arr):#在此处编写代码```2.编写一个函数，实现一个二分查找算法，输入一个整数数组和一个目标值，返回目标值在数组中的索引。```pythondefbinary_search(arr,target):#在此处编写代码```3.编写一个递归函数，实现计算斐波那契数列的第n项。```pythondeffibonacci(n):#在此处编写代码```4.编写一个函数，实现一个快速排序算法，输入一个整数数组，返回排序后的数组。```pythondefquick_sort(arr):#在此处编写代码```5.编写一个函数，实现一个哈希表，支持插入、删除和查找操作。```pythonclassHashTable:def__init__(self):#在此处编写代码definsert(self,key,value):#在此处编写代码defdelete(self,key):#在此处编写代码defsearch(self,key):#在此处编写代码```二、问题解决能力要求：本部分主要考查学生对于实际问题解决能力的提升，包括逻辑思维、数学思维和编程能力等。1.编写一个函数，实现一个汉诺塔问题解决算法，输入一个整数n，表示盘子的个数，打印出将盘子从A塔移动到C塔的步骤。```pythondefhanoi(n):#在此处编写代码```2.编写一个函数，实现一个最长公共子序列算法，输入两个字符串，返回两个字符串的最长公共子序列。```pythondeflongest_common_subsequence(str1,str2):#在此处编写代码```3.编写一个函数，实现一个最小生成树算法，输入一个加权无向图，返回最小生成树。```pythondefmin_spanning_tree(graph):#在此处编写代码```4.编写一个函数，实现一个背包问题解决算法，输入一个物品列表和背包容量，返回背包中物品的最大价值。```pythondefknapsack(items,capacity):#在此处编写代码```5.编写一个函数，实现一个迷宫问题解决算法，输入一个迷宫的二维数组，返回从起点到终点的路径。```pythondefmaze_solver(maze):#在此处编写代码```四、数据结构应用要求：本部分主要考查学生对于常见数据结构的应用能力，包括栈、队列、链表和树等。1.编写一个栈的实现，支持入栈、出栈、获取栈顶元素和判断栈是否为空的操作。```pythonclassStack:def__init__(self):#在此处编写代码defpush(self,item):#在此处编写代码defpop(self):#在此处编写代码defpeek(self):#在此处编写代码defis_empty(self):#在此处编写代码```2.实现一个队列，支持入队、出队、获取队首元素和判断队列是否为空的操作。```pythonclassQueue:def__init__(self):#在此处编写代码defenqueue(self,item):#在此处编写代码defdequeue(self):#在此处编写代码deffront(self):#在此处编写代码defis_empty(self):#在此处编写代码```3.编写一个链表，支持插入、删除、查找和遍历的操作。```pythonclassListNode:def__init__(self,value=0,next=None):#在此处编写代码classLinkedList:def__init__(self):#在此处编写代码definsert(self,value):#在此处编写代码defdelete(self,value):#在此处编写代码defsearch(self,value):#在此处编写代码deftraverse(self):#在此处编写代码```4.实现一个二叉树，支持插入、删除、查找和遍历的操作。```pythonclassTreeNode:def__init__(self,value=0,left=None,right=None):#在此处编写代码classBinaryTree:def__init__(self):#在此处编写代码definsert(self,value):#在此处编写代码defdelete(self,value):#在此处编写代码defsearch(self,value):#在此处编写代码deftraverse(self):#在此处编写代码```五、动态规划要求：本部分主要考查学生对于动态规划算法的理解和应用能力。1.编写一个动态规划算法，计算一个整数数组中的最长递增子序列的长度。```pythondeflongest_increasing_subsequence_length(nums):#在此处编写代码```2.实现一个动态规划算法，计算一个整数数组的最小子数组和。```pythondefmin_subarray_sum(nums):#在此处编写代码```3.编写一个动态规划算法，解决0-1背包问题，返回背包中物品的最大价值。```pythondefknapsack_dp(weights,values,capacity):#在此处编写代码```4.实现一个动态规划算法，解决矩阵链乘问题，返回最小乘法次数。```pythondefmatrix_chain_multiplication(p):#在此处编写代码```5.编写一个动态规划算法，解决编辑距离问题，返回将一个字符串转换为另一个字符串所需的最小编辑操作数。```pythondefedit_distance(s1,s2):#在此处编写代码```六、图论问题要求：本部分主要考查学生对于图论问题的理解和解决能力。1.实现一个深度优先搜索（DFS）算法，用于遍历一个无向图的所有顶点。```pythondefdfs(graph,start):#在此处编写代码```2.编写一个广度优先搜索（BFS）算法，用于遍历一个无向图的所有顶点。```pythondefbfs(graph,start):#在此处编写代码```3.实现一个拓扑排序算法，对于有向无环图（DAG），返回一个顶点的拓扑排序序列。```pythondeftopological_sort(graph):#在此处编写代码```4.编写一个最小生成树算法（如克鲁斯卡尔算法），输入一个加权无向图，返回最小生成树。```pythondefkruskal(graph):#在此处编写代码```5.实现一个最大流算法（如最大匹配算法），输入一个有向图和源点、汇点，返回从源点到汇点的最大流量。本次试卷答案如下：一、算法设计1.冒泡排序算法：```pythondefbubble_sort(arr):n=len(arr)foriinrange(n):forjinrange(0,n-i-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]returnarr```解析思路：冒泡排序是一种简单的排序算法，它重复地遍历待排序的数组，比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。遍历数组的工作是重复地进行直到没有再需要交换，也就是说该数组已经排序完成。2.二分查找算法：```pythondefbinary_search(arr,target):low=0high=len(arr)-1whilelow<=high:mid=(low+high)//2ifarr[mid]<target:low=mid+1elifarr[mid]>target:high=mid-1else:returnmidreturn-1```解析思路：二分查找是一种在有序数组中查找特定元素的搜索算法。它通过将搜索区间分成两半，然后根据目标值与区间中点的比较结果来决定新的搜索区间，从而逐步缩小搜索范围。3.斐波那契数列递归函数：```pythondeffibonacci(n):ifn<=1:returnnelse:returnfibonacci(n-1)+fibonacci(n-2)```解析思路：斐波那契数列是一个著名的数列，每一项都是前两项的和。递归函数通过重复调用自身来计算数列的每一项。二、问题解决能力1.汉诺塔问题解决算法：```pythondefhanoi(n):ifn==1:print("Movedisk1fromrodAtorodC")returnhanoi(n-1)print(f"Movedisk{n}fromrodAtorodC")hanoi(n-1)```解析思路：汉诺塔问题是一个经典的递归问题。递归解决思路是将问题分解为更小的子问题，对于每个盘子，将其从源塔移动到目标塔需要经过辅助塔。2.最长公共子序列算法：```pythondeflongest_common_subsequence(str1,str2):m,n=len(str1),len(str2)dp=[[0]*(n+1)for_inrange(m+1)]foriinrange(1,m+1):forjinrange(1,n+1):ifstr1[i-1]==str2[j-1]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])returndp[m][n]```解析思路：最长公共子序列问题可以通过动态规划来解决。通过构建一个二维数组来记录子问题的解，最终得到最长公共子序列的长度。3.最小生成树算法（克鲁斯卡尔算法）：```pythondefkruskal(graph):deffind(parent,i):ifparent[i]==i:returnireturnfind(parent,parent[i])defunion(parent,rank,x,y):rootX=find(parent,x)rootY=find(parent,y)ifrank[rootX]<rank[rootY]:parent[rootX]=rootYelifrank[rootX]>rank[rootY]:parent[rootY]=rootXelse:parent[rootY]=rootXrank[rootX]+=1edges=sorted(graph,key=lambdaitem:item[2])parent=[]rank=[]fornodeinrange(len(graph)):parent.append(node)rank.append(0)mst=[]foredgeinedges:x,y,w=edgeiffind(parent,x)!=find(parent,y):union(parent,rank,x,y)mst.append(edge)returnmst```解析思路：克鲁斯卡尔算法是一种用于找到加权无向图的最小生成树的算法。它通过排序边的权重，然后逐步将边添加到最小生成树中，同时确保不会形成环。三、数据结构应用1.栈的实现：```pythonclassStack:def__init__(self):self.items=[]defpush(self,item):self.items.append(item)defpop(self):returnself.items.pop()defpeek(self):returnself.items[-1]defis_empty(self):returnlen(self.items)==0```解析思路：栈是一种后进先出（LIFO）的数据结构。它支持push（添加元素）和pop（移除元素）操作。2.队列的实现：```pythonclassQueue:def__init__(self):self.items=[]defenqueue(self,item):self.items.insert(0,item)defdequeue(self):returnself.items.pop()deffront(self):returnself.items[-1]defis_empty(self):returnlen(self.items)==0```解析思路：队列是一种先进先出（FIFO）的数据结构。它支持enqueue（添加元素）和dequeue（移除元素）操作。3.链表的实现：```pythonclassListNode:def__init__(self,value=0,next=None):self.value=valueself.next=nextclassLinkedList:def__init__(self):self.head=Nonedefinsert(self,value):new_node=ListNode(value)new_node.next=self.headself.head=new_nodedefdelete(self,value):current=self.headifcurrentandcurrent.value==value:self.head=current.nextcurrent=Nonereturnprev=Nonewhilecurrentandcurrent.value!=value:prev=currentcurrent=current.nextifcurrentisNone:returnprev.next=current.nextcurrent=Nonedefsearch(self,value):current=self.headwhilecurrent:ifcurrent.value==value:returncurrentcurrent=current.nextreturnNonedeftraverse(self):current=self.headwhilecurrent:print(current.value,end='')current=current.nextprint()```解析思路：链表是一种由节点组成的序列，每个节点包含数据和指向下一个节点的指针。它支持插入、删除、查找和遍历操作。4.二叉树的实现：```pythonclassTreeNode:def__init__(self,value=0,left=None,right=None):self.value=valueself.left=leftself.right=rightclassBinaryTree:def__init__(self):self.root=Nonedefinsert(self,value):ifself.rootisNone:self.root=TreeNode(value)else:self._insert_recursive(self.root,value)def_insert_recursive(self,current,value):ifvalue<current.value:ifcurrent.leftisNone:current.left=TreeNode(value)else:self._insert_recursive(current.left,value)else:ifcurrent.rightisNone:current.right=TreeNode(value)else:self._insert_recursive(current.right,value)defdelete(self,value):self.root=self._delete_recursive(self.root,value)def_delete_recursive(self,current,value):ifcurrentisNone:returnNoneifvalue<current.value:current.left=self._delete_recursive(current.left,value)elifvalue>current.value:current.right=self._delete_recursive(current.right,value)else:ifcurrent.leftisNone:returncurrent.rightelifcurrent.rightisNone:returncurrent.leftelse:min_larger_node=self._find_min(current.right)current.value=min_larger_node.valuecurrent.right=self._delete_recursive(current.right,min_larger_node.value)returncurrentdef_find_min(self,current):whilecurrent.leftisnotNone:current=current.leftreturncurrentdefsearch(self,value):returnself._search_recursive(self.root,value)def_search_recursive(self,current,value):ifcurrentisNone:returnNoneifvalue==current.value:returncurrentelifvalue<current.value:returnself._search_recursive(current.left,value)else:returnself._search_recursive(current.right,value)deftraverse(self):self._inorder_traverse(self.root)def_inorder_traverse(self,current):ifcurrentisnotNone:self._inorder_traverse(current.left)print(current.value,end='')self._inorder_traverse(current.right)```解析思路：二叉树是一种特殊的树，每个节点最多有两个子节点。它支持插入、删除、查找和遍历操作。四、动态规划1.最长递增子序列长度：```pythondeflongest_increasing_subsequence_length(nums):ifnotnums:return0dp=[1]*len(nums)foriinrange(1,len(nums)):forjinrange(0,i):ifnums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1)returnmax(dp)```解析思路：最长递增子序列问题可以通过动态规划来解决。通过构建一个一维数组来记录以每个元素结尾的最长递增子序列的长度，然后找到最大的值。2.最小子数组和：```pythondefmin_subarray_sum(nums):min_sum=float('inf')current_sum=0fornuminnums:current_sum+=nummin_sum=min(min_sum,current_sum)ifcurrent_sum>0:current_sum=0returnmin_sum```解析思路：最小子数组和问题可以通过一次遍历数组来解决。通过维护一个当前子数组的和，如果当前和大于0，则重置为0，并更新最小和。3.0-1背包问题：```pythondefknapsack_dp(weights,values,capacity):n=len(weights)dp=[[0]*(capacity+1)for_inrange(n+1)]foriinrange(1,n+1):forwinrange(1,capacity+1):ifweights[i-1]<=w:dp[i][w]=max(values[i-1]+dp[i-1][w-weights[i-1]],dp[i-1][w])else:dp[i][w]=dp[i-1][w]returndp[n][capacity]```解析思路：0-1背包问题可以通过动态规划来解决。通过构建一个二维数组来记录子问题的解，最终得到背包中物品的最大价值。4.矩阵链乘问题：```pythondefmatrix_chain_multiplication(p):n=len(p)-1m=[[0]*nfor_inrange(n)]s=[[0]*nfor_inrange(n)]foriinrange(1,n):forjinrange(1,n-i+1):k=0min_cost=float('inf')forlinrange(k,j):cost=m[j][l]+m[l+1][j]+p[l]*p[l+1]*p[j+1]ifcost<min_cost:min_cost=costk=lm[j][i]=min_costs[j][i]=kreturnm[1][n-1]```解析思路：矩阵链乘问题可以通过动态规划来解决。通过构建一个二维数组来记录子问题的解，最终得到最小乘法次数。5.编辑距离问题：```pythondefedit_distance(s1,s2):m,n=len(s1),len(s2)dp=[[0]*(n+1)for_inrange(m+1)]foriinrange(m+1):forjinrange(n+1):ifi==0:dp[i][j]=jelifj==0:dp[i][j]=ielifs1[i-1]==s2[j-1]:dp[i][j]=dp[i-1][j-1]else:dp[i][j]=1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])returndp[m][n]```解析思路：编辑距离问题可以通过动态规划来解决。通过构建一个二维数组来记录子问题的解，最终得到将一个字符串转换为另一个字符串所需的最小编辑操作数。五、图论问题1.深度优先搜索（DFS）算法：```pythondefdfs(graph,start):visited=set()stack=[start]whilestack:vertex=stack.pop()ifvertexnotinvisited:visited.add(vertex)print(vertex,end='')forneighboringraph[vertex]:ifneighbornotinvisited:stack.append(neighbor)```解析思路：深度优先搜索是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着一条路径一直走到底，然后回溯并沿着另一条路径继续。2.广度优先搜索（BFS）算法：```pythondefbfs(graph,start):visited=set()queue=[start]whilequeue:vertex=queue.pop(0)ifvertexnotinvisited:visited.add(vertex)print(vertex,end='')forneighboringraph[vertex]:ifneighbornotinvisited:queue.append(neighbor)```解析思路：广度优先搜索是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着一条路径一直走到底，然后扩展到下一层，再沿着另一条路径继续。3.拓扑排序算法：```pythondeftopological_sort(graph):in_degree={vertex:0forve