2025年信息奥赛题库及答案

2025年信息奥赛题库及答案题目1：数字排序题目描述给定一个整数数组，要求将数组中的数字按照从小到大的顺序进行排序。输入格式第一行包含一个整数n（1≤n≤1000），表示数组的长度。第二行包含n个整数，每个整数的范围是-10000到10000。输出格式输出排序后的数组，数字之间用一个空格分隔。示例输入```531415```示例输出```11345```代码实现（Python）```pythonn=int(input())nums=list(map(int,input().split()))nums.sort()print("".join(map(str,nums)))```代码解释首先读取数组的长度n，然后读取数组元素并存储在列表nums中。使用Python内置的sort()方法对列表进行排序，最后将排序后的列表元素转换为字符串并用空格连接起来输出。题目2：最大子数组和题目描述给定一个整数数组，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。输入格式第一行包含一个整数n（1≤n≤1000），表示数组的长度。第二行包含n个整数，每个整数的范围是-10000到10000。输出格式输出最大子数组的和。示例输入```5-21-34-1```示例输出```4```代码实现（Python）```pythonn=int(input())nums=list(map(int,input().split()))max_sum=float('-inf')current_sum=0fornuminnums:current_sum=max(num,current_sum+num)max_sum=max(max_sum,current_sum)print(max_sum)```代码解释使用动态规划的思想，维护两个变量：current_sum表示以当前元素结尾的最大子数组和，max_sum表示全局最大子数组和。遍历数组，对于每个元素，更新current_sum为当前元素和current_sum加上当前元素的较大值，同时更新max_sum为max_sum和current_sum的较大值。题目3：字符串反转题目描述给定一个字符串，将其反转后输出。输入格式一行字符串，长度不超过1000。输出格式反转后的字符串。示例输入```hello```示例输出```olleh```代码实现（Python）```pythons=input()print(s[::-1])```代码解释使用Python的切片操作[::-1]可以方便地实现字符串的反转。题目4：斐波那契数列题目描述斐波那契数列是指这样一个数列：0、1、1、2、3、5、8、13、21、34、……。在数学上，斐波那契数列以如下递推的方法定义：$F(0)=0$，$F(1)=1$,$F(n)=F(n1)+F(n2)$（$n≥2$，$n∈N$）。给定一个整数n，求斐波那契数列的第n项。输入格式一个整数n（0≤n≤30）。输出格式斐波那契数列的第n项。示例输入```5```示例输出```5```代码实现（Python）```pythonn=int(input())ifn==0:print(0)elifn==1:print(1)else:a,b=0,1foriinrange(2,n+1):a,b=b,a+bprint(b)```代码解释使用迭代的方法计算斐波那契数列的第n项。初始化前两项a=0和b=1，然后通过循环不断更新a和b的值，直到计算出第n项。题目5：二叉树的遍历题目描述给定一棵二叉树，实现其前序、中序和后序遍历。输入格式第一行包含一个整数n（1≤n≤100），表示二叉树的节点数。接下来n行，每行包含三个整数，分别表示当前节点的编号、左子节点的编号和右子节点的编号。如果左子节点或右子节点不存在，则用-1表示。输出格式三行，分别表示前序、中序和后序遍历的结果，节点编号之间用一个空格分隔。示例输入```31232-1-13-1-1```示例输出```123213231```代码实现（Python）```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightn=int(input())nodes=[None](n+1)foriinrange(1,n+1):val,left,right=map(int,input().split())ifnotnodes[i]:nodes[i]=TreeNode(val)ifleft!=-1:ifnotnodes[left]:nodes[left]=TreeNode(left)nodes[i].left=nodes[left]ifright!=-1:ifnotnodes[right]:nodes[right]=TreeNode(right)nodes[i].right=nodes[right]defpreorder(root):ifroot:return[root.val]+preorder(root.left)+preorder(root.right)return[]definorder(root):ifroot:returninorder(root.left)+[root.val]+inorder(root.right)return[]defpostorder(root):ifroot:returnpostorder(root.left)+postorder(root.right)+[root.val]return[]pre=preorder(nodes[1])ino=inorder(nodes[1])post=postorder(nodes[1])print("".join(map(str,pre)))print("".join(map(str,ino)))print("".join(map(str,post)))```代码解释首先定义二叉树的节点类TreeNode。根据输入构建二叉树，然后分别实现前序、中序和后序遍历的递归函数。最后调用这些函数并输出遍历结果。题目6：二分查找题目描述给定一个有序数组和一个目标值，在数组中查找目标值，如果存在则返回其索引，否则返回-1。输入格式第一行包含一个整数n（1≤n≤1000），表示数组的长度。第二行包含n个整数，每个整数的范围是-10000到10000，数组按升序排列。第三行包含一个整数target，表示目标值。输出格式目标值在数组中的索引，如果不存在则输出-1。示例输入```5123453```示例输出```2```代码实现（Python）```pythonn=int(input())nums=list(map(int,input().split()))target=int(input())left,right=0,n1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:print(mid)breakelifnums[mid]<target:left=mid+1else:right=mid1else:print(-1)```代码解释使用二分查找的方法，维护左右指针left和right，每次取中间位置mid，比较中间元素和目标值的大小，根据比较结果更新左右指针，直到找到目标值或左右指针交叉。题目7：爬楼梯题目描述假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？输入格式一个整数n（1≤n≤45）。输出格式不同的爬楼梯方法数。示例输入```3```示例输出```3```代码实现（Python）```pythonn=int(input())ifn==1:print(1)elifn==2:print(2)else:a,b=1,2foriinrange(3,n+1):a,b=b,a+bprint(b)```代码解释这是一个经典的动态规划问题，类似于斐波那契数列。到达第n阶楼梯的方法数等于到达第n1阶楼梯的方法数加上到达第n2阶楼梯的方法数。题目8：有效的括号题目描述给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。有效字符串需满足：1.左括号必须用相同类型的右括号闭合。2.左括号必须以正确的顺序闭合。输入格式一行字符串，长度不超过1000。输出格式如果字符串有效，输出"True"，否则输出"False"。示例输入```()[]{}```示例输出```True```代码实现（Python）```pythons=input()stack=[]mapping={")":"(","]":"[","}":"{"}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse''ifmapping[char]!=top_element:print("False")breakelse:stack.append(char)else:ifnotstack:print("True")else:print("False")```代码解释使用栈来解决这个问题。遍历字符串，遇到左括号就将其压入栈中，遇到右括号就从栈中弹出一个左括号进行匹配。如果匹配失败或栈为空，则字符串无效。最后检查栈是否为空，如果为空则字符串有效。题目9：两数之和题目描述给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。输入格式第一行包含一个整数n（2≤n≤1000），表示数组的长度。第二行包含n个整数，每个整数的范围是-10000到10000。第三行包含一个整数target，表示目标值。输出格式两个整数，表示和为目标值的两个整数的下标，下标从小到大输出，用一个空格分隔。示例输入```42711159```示例输出```01```代码实现（Python）```pythonn=int(input())nums=list(map(int,input().split()))target=int(input())num_dict={}fori,numinenumerate(nums):complement=targetnumifcomplementinnum_dict:print(num_dict[complement],i)breaknum_dict[num]=i```代码解释使用哈希表来解决这个问题。遍历数组，对于每个元素，计算其补数（目标值减去当前元素），检查补数是否在哈希表中，如果在则返回两个元素的下标，否则将当前元素及其下标存入哈希表中。题目10：岛屿数量题目描述给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。输入格式第一行包含两个整数m和n（1≤m,n≤