2025年編程基礎(chǔ)算法題庫及答案一、排序算法1.冒泡排序題目：實現(xiàn)冒泡排序算法，對給定的整數(shù)數(shù)組進行升序排序。代碼實現(xiàn)（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)```復(fù)雜度分析：時間復(fù)雜度：$O(n^2)$，其中$n$是數(shù)組的長度。因為有兩層嵌套循環(huán)?？臻g復(fù)雜度：$O(1)$，只使用了常數(shù)級的額外空間。2.選擇排序題目：實現(xiàn)選擇排序算法，對給定的整數(shù)數(shù)組進行升序排序。代碼實現(xiàn)（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)```復(fù)雜度分析：時間復(fù)雜度：$O(n^2)$，同樣有兩層嵌套循環(huán)?？臻g復(fù)雜度：$O(1)$，只使用了常數(shù)級的額外空間。3.插入排序題目：實現(xiàn)插入排序算法，對給定的整數(shù)數(shù)組進行升序排序。代碼實現(xiàn)（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)```復(fù)雜度分析：時間復(fù)雜度：平均和最壞情況下為$O(n^2)$，最好情況下為$O(n)$（數(shù)組已經(jīng)有序）。空間復(fù)雜度：$O(1)$，只使用了常數(shù)級的額外空間。4.快速排序題目：實現(xiàn)快速排序算法，對給定的整數(shù)數(shù)組進行升序排序。代碼實現(xiàn)（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)```復(fù)雜度分析：時間復(fù)雜度：平均情況下為$O(nlogn)$，最壞情況下為$O(n^2)$（例如數(shù)組已經(jīng)有序）。空間復(fù)雜度：平均情況下為$O(logn)$，最壞情況下為$O(n)$。5.歸并排序題目：實現(xiàn)歸并排序算法，對給定的整數(shù)數(shù)組進行升序排序。代碼實現(xiàn)（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)```復(fù)雜度分析：時間復(fù)雜度：$O(nlogn)$，無論數(shù)組初始狀態(tài)如何?？臻g復(fù)雜度：$O(n)$，主要用于合并過程中的臨時數(shù)組。二、搜索算法1.線性搜索題目：實現(xiàn)線性搜索算法，在給定的整數(shù)數(shù)組中查找目標(biāo)值的索引，如果未找到則返回-1。代碼實現(xiàn)（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)```復(fù)雜度分析：時間復(fù)雜度：$O(n)$，其中$n$是數(shù)組的長度。空間復(fù)雜度：$O(1)$，只使用了常數(shù)級的額外空間。2.二分搜索題目：實現(xiàn)二分搜索算法，在一個有序的整數(shù)數(shù)組中查找目標(biāo)值的索引，如果未找到則返回-1。代碼實現(xiàn)（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)```復(fù)雜度分析：時間復(fù)雜度：$O(logn)$，每次迭代將搜索范圍縮小一半?？臻g復(fù)雜度：$O(1)$，只使用了常數(shù)級的額外空間。三、遞歸算法1.斐波那契數(shù)列題目：實現(xiàn)遞歸函數(shù)計算斐波那契數(shù)列的第$n$項。代碼實現(xiàn)（Python）：```pythondeffibonacci(n):ifn<=1:returnnreturnfibonacci(n1)+fibonacci(n2)測試n=10result=fibonacci(n)print(result)```復(fù)雜度分析：時間復(fù)雜度：$O(2^n)$，因為存在大量的重復(fù)計算?？臻g復(fù)雜度：$O(n)$，遞歸棧的深度為$n$。2.階乘題目：實現(xiàn)遞歸函數(shù)計算$n$的階乘。代碼實現(xiàn)（Python）：```pythondeffactorial(n):ifn==0orn==1:return1returnnfactorial(n1)測試n=5result=factorial(n)print(result)```復(fù)雜度分析：時間復(fù)雜度：$O(n)$，遞歸調(diào)用$n$次?？臻g復(fù)雜度：$O(n)$，遞歸棧的深度為$n$。四、圖算法1.廣度優(yōu)先搜索（BFS）題目：實現(xiàn)廣度優(yōu)先搜索算法，在一個圖中從給定的起始節(jié)點開始遍歷圖。代碼實現(xiàn)（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)```復(fù)雜度分析：時間復(fù)雜度：$O(V+E)$，其中$V$是頂點數(shù)，$E$是邊數(shù)?？臻g復(fù)雜度：$O(V)$，主要用于存儲訪問標(biāo)記和隊列。2.深度優(yōu)先搜索（DFS）題目：實現(xiàn)深度優(yōu)先搜索算法，在一個圖中從給定的起始節(jié)點開始遍歷圖。代碼實現(xiàn)（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)```復(fù)雜度分析：時間復(fù)雜度：$O(V+E)$，其中$V$是頂點數(shù)，$E$是邊數(shù)?？臻g復(fù)雜度：$O(V)$，主要用于遞歸棧和訪問標(biāo)記。五、動態(tài)規(guī)劃1.爬樓梯問題題目：假設(shè)你正在爬樓梯。需要$n$階你才能到達(dá)樓頂。每次你可以爬1或2個臺階。你有多少種不同的方法可以爬到樓頂呢？代碼實現(xiàn)（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)```復(fù)雜度分析：時間復(fù)雜度：$O(n)$，只需要遍歷一次數(shù)組?？臻g復(fù)雜度：$O(n)$，使用了一個長度為$n+1$的數(shù)組。2.