在众多考研科目中，数据结构算法是计算机科学与技术专业以及相关领域考研的重要考点。掌握扎实的算法和数据结构知识，对于提高解题能力和考试成绩至关重要。为了帮助考生们更好地准备考研，这里为大家推荐一份精心整理的数据结构算法500题库，助你轻松攻克考研难关。
第一部分：数据结构基础
1. 线性表
线性表是存储在一片连续的存储单元中的线性序列。常见的线性表包括数组、链表、栈和队列。
例题1： 实现一个栈，支持push、pop和peek操作。
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
return None
def peek(self):
if not self.is_empty():
return self.items[-1]
return None
def is_empty(self):
return len(self.items) == 0
2. 栈和队列
栈和队列是两种特殊的线性表，它们分别遵循后进先出（LIFO）和先进先出（FIFO）的原则。
例题2： 实现一个队列，支持enqueue、dequeue和front操作。
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.popleft()
return None
def front(self):
if not self.is_empty():
return self.items[0]
return None
def is_empty(self):
return len(self.items) == 0
3. 链表
链表是一种非线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
例题3： 实现一个单向链表，支持插入、删除和查找操作。
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def insert(self, value):
new_node = ListNode(value)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def delete(self, value):
current = self.head
if current and current.value == value:
self.head = current.next
current = None
return
prev = None
while current and current.value != value:
prev = current
current = current.next
if current is None:
return
prev.next = current.next
current = None
def search(self, value):
current = self.head
while current:
if current.value == value:
return True
current = current.next
return False
第二部分：算法基础
1. 排序算法
排序算法是将一组数据按照一定的顺序排列的算法。常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。
例题4： 实现冒泡排序算法。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
2. 搜索算法
搜索算法是在数据结构中查找特定元素的方法。常见的搜索算法有顺序查找、二分查找、深度优先搜索（DFS）、广度优先搜索（BFS）等。
例题5： 实现二分查找算法。
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
第三部分：高级算法
1. 动态规划
动态规划是一种通过将复杂问题分解为更小、更简单的子问题来求解的方法。
例题6： 实现最长公共子序列（LCS）算法。
def lcs(X, Y):
m = len(X)
n = len(Y)
L = [[None]*(n+1) for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
return L[m][n]
2. 图算法
图算法是处理图中数据的方法，包括最短路径、最小生成树、拓扑排序等。
例题7： 实现迪杰斯特拉（Dijkstra）算法求最短路径。
import heapq
def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
通过以上500题库的练习，相信大家能够熟练掌握数据结构算法，为考研打下坚实的基础。祝大家考研顺利！