2025年考研數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)題專項(xiàng)訓(xùn)練試卷：Python代碼實(shí)戰(zhàn)

2025年考研數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)題專項(xiàng)訓(xùn)練試卷：Python代碼實(shí)戰(zhàn)一、排序算法實(shí)現(xiàn)與性能分析要求：實(shí)現(xiàn)以下幾種排序算法，并對(duì)每種算法進(jìn)行性能分析。1.簡單選擇排序(1)實(shí)現(xiàn)簡單選擇排序函數(shù)，輸入為列表，輸出為排序后的列表。(2)編寫測(cè)試代碼，隨機(jī)生成一個(gè)長度為10000的整數(shù)列表，對(duì)列表進(jìn)行排序，并記錄排序過程所用時(shí)間。2.快速排序(1)實(shí)現(xiàn)快速排序函數(shù)，輸入為列表，輸出為排序后的列表。(2)編寫測(cè)試代碼，隨機(jī)生成一個(gè)長度為10000的整數(shù)列表，對(duì)列表進(jìn)行排序，并記錄排序過程所用時(shí)間。3.歸并排序(1)實(shí)現(xiàn)歸并排序函數(shù)，輸入為列表，輸出為排序后的列表。(2)編寫測(cè)試代碼，隨機(jī)生成一個(gè)長度為10000的整數(shù)列表，對(duì)列表進(jìn)行排序，并記錄排序過程所用時(shí)間。二、二叉樹遍歷與搜索要求：實(shí)現(xiàn)以下幾種二叉樹遍歷與搜索方法。1.深度優(yōu)先遍歷(1)實(shí)現(xiàn)深度優(yōu)先遍歷函數(shù)，輸入為二叉樹節(jié)點(diǎn)，輸出為遍歷結(jié)果列表。(2)編寫測(cè)試代碼，構(gòu)建一個(gè)具有100個(gè)節(jié)點(diǎn)的二叉樹，對(duì)樹進(jìn)行深度優(yōu)先遍歷，并輸出遍歷結(jié)果。2.廣度優(yōu)先遍歷(1)實(shí)現(xiàn)廣度優(yōu)先遍歷函數(shù)，輸入為二叉樹節(jié)點(diǎn)，輸出為遍歷結(jié)果列表。(2)編寫測(cè)試代碼，構(gòu)建一個(gè)具有100個(gè)節(jié)點(diǎn)的二叉樹，對(duì)樹進(jìn)行廣度優(yōu)先遍歷，并輸出遍歷結(jié)果。3.搜索二叉樹(1)實(shí)現(xiàn)搜索二叉樹插入函數(shù)，輸入為節(jié)點(diǎn)值，輸出為插入后的二叉樹。(2)實(shí)現(xiàn)搜索二叉樹查找函數(shù)，輸入為節(jié)點(diǎn)值，輸出為查找結(jié)果（查找成功返回節(jié)點(diǎn)，查找失敗返回None）。(3)編寫測(cè)試代碼，構(gòu)建一個(gè)具有50個(gè)節(jié)點(diǎn)的搜索二叉樹，插入一個(gè)新節(jié)點(diǎn)，并查找該節(jié)點(diǎn)。三、圖算法實(shí)現(xiàn)與性能分析要求：實(shí)現(xiàn)以下幾種圖算法，并對(duì)每種算法進(jìn)行性能分析。1.拓?fù)渑判?1)實(shí)現(xiàn)拓?fù)渑判蚝瘮?shù)，輸入為有向圖，輸出為拓?fù)渑判蚪Y(jié)果列表。(2)編寫測(cè)試代碼，構(gòu)建一個(gè)具有100個(gè)節(jié)點(diǎn)的有向圖，對(duì)圖進(jìn)行拓?fù)渑判?，并輸出排序結(jié)果。2.最短路徑算法(1)實(shí)現(xiàn)迪杰斯特拉算法（Dijkstra算法），輸入為有向圖、起點(diǎn)和終點(diǎn)，輸出為最短路徑長度和路徑。(2)編寫測(cè)試代碼，構(gòu)建一個(gè)具有100個(gè)節(jié)點(diǎn)的有向圖，計(jì)算起點(diǎn)到終點(diǎn)的最短路徑，并輸出路徑。3.最小生成樹算法(1)實(shí)現(xiàn)克魯斯卡爾算法（Kruskal算法），輸入為無向圖，輸出為最小生成樹。(2)編寫測(cè)試代碼，構(gòu)建一個(gè)具有100個(gè)節(jié)點(diǎn)的無向圖，對(duì)圖進(jìn)行最小生成樹構(gòu)建，并輸出生成樹。四、動(dòng)態(tài)規(guī)劃解決背包問題要求：(1)實(shí)現(xiàn)一個(gè)動(dòng)態(tài)規(guī)劃函數(shù)，用于解決0/1背包問題。該函數(shù)接收一個(gè)物品重量列表和一個(gè)背包容量，返回一個(gè)表示物品是否被選擇的二維數(shù)組，以及最大價(jià)值。(2)編寫測(cè)試代碼，給定一個(gè)物品重量列表[1,3,4,5]和一個(gè)背包容量為7，調(diào)用動(dòng)態(tài)規(guī)劃函數(shù)，并輸出最優(yōu)解的物品選擇和最大價(jià)值。五、遞歸實(shí)現(xiàn)漢諾塔問題要求：(1)實(shí)現(xiàn)一個(gè)遞歸函數(shù)，用于解決漢諾塔問題。該函數(shù)接收三個(gè)參數(shù)：源柱、目標(biāo)柱和輔助柱，以及盤子的數(shù)量。函數(shù)應(yīng)能夠?qū)⑺斜P子從源柱移動(dòng)到目標(biāo)柱，使用輔助柱作為中間步驟。(2)編寫測(cè)試代碼，調(diào)用遞歸函數(shù)，以3個(gè)盤子為例，輸出移動(dòng)盤子的步驟序列。六、貪心算法求解最小硬幣找零問題要求：(1)實(shí)現(xiàn)一個(gè)貪心算法函數(shù)，用于解決最小硬幣找零問題。該函數(shù)接收一個(gè)正整數(shù)金額和一個(gè)硬幣面額列表，返回一個(gè)表示所需硬幣數(shù)量的列表。(2)編寫測(cè)試代碼，給定金額為17和硬幣面額列表[1,2,5,10,20]，調(diào)用貪心算法函數(shù)，并輸出所需硬幣的最優(yōu)組合。本次試卷答案如下：一、排序算法實(shí)現(xiàn)與性能分析1.簡單選擇排序(1)簡單選擇排序函數(shù)實(shí)現(xiàn)：```pythondefselection_sort(arr):n=len(arr)foriinrange(n):min_idx=iforjinrange(i+1,n):ifarr[min_idx]>arr[j]:min_idx=jarr[i],arr[min_idx]=arr[min_idx],arr[i]returnarr```(2)測(cè)試代碼：```pythonimportrandomimporttimedeftest_sorting_algorithm(sort_func,arr):start_time=time.time()sorted_arr=sort_func(arr.copy())end_time=time.time()returnsorted_arr,end_time-start_timearr=[random.randint(0,100)for_inrange(10000)]sorted_arr,time_taken=test_sorting_algorithm(selection_sort,arr)print(f"Sortedarray:{sorted_arr[:10]}...(last10elements)")print(f"Timetaken:{time_taken:.6f}seconds")```2.快速排序(1)快速排序函數(shù)實(shí)現(xiàn)：```pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)```(2)測(cè)試代碼（同上）。3.歸并排序(1)歸并排序函數(shù)實(shí)現(xiàn)：```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```(2)測(cè)試代碼（同上）。二、二叉樹遍歷與搜索1.深度優(yōu)先遍歷(1)深度優(yōu)先遍歷函數(shù)實(shí)現(xiàn)：```pythondefdfs(node):ifnodeisnotNone:print(node.value,end='')dfs(node.left)dfs(node.right)```(2)測(cè)試代碼（假設(shè)有一個(gè)二叉樹節(jié)點(diǎn)類`TreeNode`）：```pythonclassTreeNode:def__init__(self,value):self.value=valueself.left=Noneself.right=None#構(gòu)建二叉樹root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)#深度優(yōu)先遍歷dfs(root)```2.廣度優(yōu)先遍歷(1)廣度優(yōu)先遍歷函數(shù)實(shí)現(xiàn)：```pythonfromcollectionsimportdequedefbfs(root):ifnotroot:return[]queue=deque([root])result=[]whilequeue:node=queue.popleft()result.append(node.value)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)returnresult```(2)測(cè)試代碼（同上）。3.搜索二叉樹(1)搜索二叉樹插入函數(shù)實(shí)現(xiàn)：```pythondefinsert(root,value):ifrootisNone:returnTreeNode(value)ifvalue<root.value:root.left=insert(root.left,value)else:root.right=insert(root.right,value)returnroot```(2)搜索二叉樹查找函數(shù)實(shí)現(xiàn)：```pythondefsearch(root,value):ifrootisNoneorroot.value==value:returnrootifvalue<root.value:returnsearch(root.left,value)else:returnsearch(root.right,value)```(3)測(cè)試代碼（假設(shè)有一個(gè)搜索二叉樹節(jié)點(diǎn)類`SearchTreeNode`）：```pythonclassSearchTreeNode:def__init__(self,value):self.value=valueself.left=Noneself.right=None#構(gòu)建搜索二叉樹root=SearchTreeNode(5)root=insert(root,3)root=insert(root,7)root=insert(root,2)root=insert(root,4)root=insert(root,6)root=insert(root,8)#查找節(jié)點(diǎn)node=search(root,4)ifnode:print(f"Nodewithvalue4found.")else:print(f"Nodewithvalue4notfound.")```三、圖算法實(shí)現(xiàn)與性能分析1.拓?fù)渑判?1)拓?fù)渑判蚝瘮?shù)實(shí)現(xiàn)：```pythondeftopological_sort(graph):in_degree={node:0fornodeingraph}fornodeingraph:forneighboringraph[node]:in_degree[neighbor]+=1queue=[nodefornodeingraphifin_degree[node]==0]sorted_list=[]whilequeue:node=queue.pop(0)sorted_list.append(node)forneighboringraph[node]:in_degree[neighbor]-=1ifin_degree[neighbor]==0:queue.append(neighbor)returnsorted_list```(2)測(cè)試代碼（假設(shè)有一個(gè)圖節(jié)點(diǎn)類`GraphNode`）：```pythonclassGraphNode:def__init__(self,value):self.value=valueself.neighbors=[]#構(gòu)建有向圖graph={1:[2,3],2:[3],3:[4],4:[]}#拓?fù)渑判騭orted_list=topological_sort(graph)print(sorted_list)```2.最短路徑算法(1)迪杰斯特拉算法實(shí)現(xiàn)：```pythonimportheapqdefdijkstra(graph,start):distances={node:float('infinity')fornodeingraph}distances[start]=0priority_queue=[(0,start)]whilepriority_queue:current_distance,current_node=heapq.heappop(priority_queue)ifcurrent_distance>distances[current_node]:continueforneighbor,weightingraph[current_node]:distance=current_distance+weightifdistance<distances[neighbor]:distances[neighbor]=distanceheapq.heappush(priority_queue,(distance,neighbor))returndistances```(2)測(cè)試代碼（假設(shè)有一個(gè)圖節(jié)點(diǎn)類`GraphNode`）：```python#構(gòu)建有向圖graph={'A':[('B',1),('C',4)],'B':[('C',2),('D',5)],'C':[('D',1)],'D':[]}#迪杰斯特拉算法distances=dijkstra(graph,'A')print(distances)```3.最小生成樹算法(1)克魯斯卡爾算法實(shí)現(xiàn)：```pythonclassUnionFind:def__init__(self,vertices):self.parent={vertex:vertexforvertexinvertices}self.rank={vertex:0forvertexinvertices}deffind(self,vertex):ifself.parent[vertex]!=vertex:self.parent[vertex]=self.find(self.parent[vertex])returnself.parent[vertex]defunion(self,vertex1,vertex2):root1=self.find(vertex1)root2=self.find(vertex2)ifroot1!=root2:ifself.rank[root1]>self.rank[root2]:self.parent[root2]=root1elifself.rank[root1]<self.rank[root2]:self.parent[root1]=root2else:self.parent[root2]=root1self.rank[root1]+=1defkruskal(graph):vertices=set()edges=[]fornodeingraph:vertices.update(graph[node])fornodeingraph:forneighbor,weightingraph[node]:edges.append((weight,node,neighbor))edges.sort()uf=UnionFind(vertices)mst=[]forweight,node1,node2inedges:ifuf.find(node1)!=uf.find(node2):uf.union(node1,node2)mst.append((node1,node2,weight))returnmst```(2)測(cè)試代碼（假設(shè)有一個(gè)圖節(jié)點(diǎn)類`GraphNode`）：```python#構(gòu)建有向圖graph={'A':[('B',1),('C',4)],'B':[('C',2),('D',5)],'C':[('D',1)],'D':[]}#克魯斯卡爾算法mst=kruskal(graph)print(mst)```四、動(dòng)態(tài)規(guī)劃解決背包問題(1)動(dòng)態(tài)規(guī)劃函數(shù)實(shí)現(xiàn)：```pythondefknapsack(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(dp[i-1][w],dp[i-1][w-