2025年编程基础算法题库及答案

2025年编程基础算法题库及答案一、排序算法1.冒泡排序题目：实现冒泡排序算法，对给定的整数数组进行升序排序。代码实现（Python）：```pythondefbubble_sort(arr):n=len(arr)foriinrange(n):forjinrange(0,ni1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]returnarr测试arr=[64,34,25,12,22,11,90]sorted_arr=bubble_sort(arr)print(sorted_arr)```复杂度分析：时间复杂度：$O(n^2)$，其中$n$是数组的长度。因为有两层嵌套循环。空间复杂度：$O(1)$，只使用了常数级的额外空间。2.选择排序题目：实现选择排序算法，对给定的整数数组进行升序排序。代码实现（Python）：```pythondefselection_sort(arr):n=len(arr)foriinrange(n):min_idx=iforjinrange(i+1,n):ifarr[j]<arr[min_idx]:min_idx=jarr[i],arr[min_idx]=arr[min_idx],arr[i]returnarr测试arr=[64,25,12,22,11]sorted_arr=selection_sort(arr)print(sorted_arr)```复杂度分析：时间复杂度：$O(n^2)$，同样有两层嵌套循环。空间复杂度：$O(1)$，只使用了常数级的额外空间。3.插入排序题目：实现插入排序算法，对给定的整数数组进行升序排序。代码实现（Python）：```pythondefinsertion_sort(arr):foriinrange(1,len(arr)):key=arr[i]j=i1whilej>=0andkey<arr[j]:arr[j+1]=arr[j]j-=1arr[j+1]=keyreturnarr测试arr=[12,11,13,5,6]sorted_arr=insertion_sort(arr)print(sorted_arr)```复杂度分析：时间复杂度：平均和最坏情况下为$O(n^2)$，最好情况下为$O(n)$（数组已经有序）。空间复杂度：$O(1)$，只使用了常数级的额外空间。4.快速排序题目：实现快速排序算法，对给定的整数数组进行升序排序。代码实现（Python）：```pythondefquick_sort(arr):iflen(arr)<=1:returnarrelse:pivot=arr[0]left=[xforxinarr[1:]ifx<=pivot]right=[xforxinarr[1:]ifx>pivot]returnquick_sort(left)+[pivot]+quick_sort(right)测试arr=[3,6,8,10,1,2,1]sorted_arr=quick_sort(arr)print(sorted_arr)```复杂度分析：时间复杂度：平均情况下为$O(nlogn)$，最坏情况下为$O(n^2)$（例如数组已经有序）。空间复杂度：平均情况下为$O(logn)$，最坏情况下为$O(n)$。5.归并排序题目：实现归并排序算法，对给定的整数数组进行升序排序。代码实现（Python）：```pythondefmerge_sort(arr):iflen(arr)<=1:returnarrmid=len(arr)//2left=merge_sort(arr[:mid])right=merge_sort(arr[mid:])returnmerge(left,right)defmerge(left,right):result=[]i=j=0whilei<len(left)andj<len(right):ifleft[i]<right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1result.extend(left[i:])result.extend(right[j:])returnresult测试arr=[38,27,43,3,9,82,10]sorted_arr=merge_sort(arr)print(sorted_arr)```复杂度分析：时间复杂度：$O(nlogn)$，无论数组初始状态如何。空间复杂度：$O(n)$，主要用于合并过程中的临时数组。二、搜索算法1.线性搜索题目：实现线性搜索算法，在给定的整数数组中查找目标值的索引，如果未找到则返回-1。代码实现（Python）：```pythondeflinear_search(arr,target):foriinrange(len(arr)):ifarr[i]==target:returnireturn-1测试arr=[10,20,80,30,60,50,110,100,130,170]target=110index=linear_search(arr,target)print(index)```复杂度分析：时间复杂度：$O(n)$，其中$n$是数组的长度。空间复杂度：$O(1)$，只使用了常数级的额外空间。2.二分搜索题目：实现二分搜索算法，在一个有序的整数数组中查找目标值的索引，如果未找到则返回-1。代码实现（Python）：```pythondefbinary_search(arr,target):left,right=0,len(arr)1whileleft<=right:mid=(left+right)//2ifarr[mid]==target:returnmidelifarr[mid]<target:left=mid+1else:right=mid1return-1测试arr=[2,3,4,10,40]target=10index=binary_search(arr,target)print(index)```复杂度分析：时间复杂度：$O(logn)$，每次迭代将搜索范围缩小一半。空间复杂度：$O(1)$，只使用了常数级的额外空间。三、递归算法1.斐波那契数列题目：实现递归函数计算斐波那契数列的第$n$项。代码实现（Python）：```pythondeffibonacci(n):ifn<=1:returnnreturnfibonacci(n1)+fibonacci(n2)测试n=10result=fibonacci(n)print(result)```复杂度分析：时间复杂度：$O(2^n)$，因为存在大量的重复计算。空间复杂度：$O(n)$，递归栈的深度为$n$。2.阶乘题目：实现递归函数计算$n$的阶乘。代码实现（Python）：```pythondeffactorial(n):ifn==0orn==1:return1returnnfactorial(n1)测试n=5result=factorial(n)print(result)```复杂度分析：时间复杂度：$O(n)$，递归调用$n$次。空间复杂度：$O(n)$，递归栈的深度为$n$。四、图算法1.广度优先搜索（BFS）题目：实现广度优先搜索算法，在一个图中从给定的起始节点开始遍历图。代码实现（Python）：```pythonfromcollectionsimportdequedefbfs(graph,start):visited=set()queue=deque([start])visited.add(start)result=[]whilequeue:vertex=queue.popleft()result.append(vertex)forneighboringraph[vertex]:ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)returnresult测试graph={'A':['B','C'],'B':['A','D','E'],'C':['A','F'],'D':['B'],'E':['B','F'],'F':['C','E']}start='A'traversal=bfs(graph,start)print(traversal)```复杂度分析：时间复杂度：$O(V+E)$，其中$V$是顶点数，$E$是边数。空间复杂度：$O(V)$，主要用于存储访问标记和队列。2.深度优先搜索（DFS）题目：实现深度优先搜索算法，在一个图中从给定的起始节点开始遍历图。代码实现（Python）：```pythondefdfs(graph,start,visited=None):ifvisitedisNone:visited=set()ifstartnotinvisited:print(start,end='')visited.add(start)forneighboringraph[start]:dfs(graph,neighbor,visited)测试graph={'A':['B','C'],'B':['A','D','E'],'C':['A','F'],'D':['B'],'E':['B','F'],'F':['C','E']}start='A'dfs(graph,start)```复杂度分析：时间复杂度：$O(V+E)$，其中$V$是顶点数，$E$是边数。空间复杂度：$O(V)$，主要用于递归栈和访问标记。五、动态规划1.爬楼梯问题题目：假设你正在爬楼梯。需要$n$阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？代码实现（Python）：```pythondefclimb_stairs(n):ifn<=2:returnndp=[0](n+1)dp[1]=1dp[2]=2foriinrange(3,n+1):dp[i]=dp[i1]+dp[i2]returndp[n]测试n=5result=climb_stairs(n)print(result)```复杂度分析：时间复杂度：$O(n)$，只需要遍历一次数组。空间复杂度：$O(n)$，使用了一个长度为$n+1$的数组。2.