在考研的道路上，数据结构是计算机科学与技术专业考生必须掌握的核心知识之一。数据结构不仅考察了考生对基本概念的理解，还考验了他们运用这些概念解决实际问题的能力。以下是一些常见的数据结构真题，帮助考生更好地准备考研挑战。
1. 线性表
真题示例：
题目： 编写一个函数，实现一个循环链表，并实现以下功能：插入节点、删除节点、查找节点。
代码示例：
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def insert(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.head.next = self.head
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
def delete(self, data):
if not self.head:
return
current = self.head
prev = None
while current.next != self.head:
prev = current
current = current.next
if current.data == data:
if current == self.head:
self.head = self.head.next
prev.next = current.next
return
def search(self, data):
current = self.head
while current.next != self.head:
if current.data == data:
return True
current = current.next
return False
2. 栈和队列
真题示例：
题目： 实现一个栈，支持入栈、出栈、判断栈空、获取栈顶元素。
代码示例：
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
3. 树和图
真题示例：
题目： 实现一个二叉搜索树，支持插入、删除、查找、中序遍历。
代码示例：
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, data):
if not self.root:
self.root = TreeNode(data)
else:
self._insert_recursive(self.root, data)
def _insert_recursive(self, node, data):
if data < node.data:
if not node.left:
node.left = TreeNode(data)
else:
self._insert_recursive(node.left, data)
else:
if not node.right:
node.right = TreeNode(data)
else:
self._insert_recursive(node.right, data)
def delete(self, data):
self.root = self._delete_recursive(self.root, data)
def _delete_recursive(self, node, data):
if not node:
return node
if data < node.data:
node.left = self._delete_recursive(node.left, data)
elif data > node.data:
node.right = self._delete_recursive(node.right, data)
else:
if not node.left:
return node.right
elif not node.right:
return node.left
min_larger_node = self._find_min(node.right)
node.data = min_larger_node.data
node.right = self._delete_recursive(node.right, min_larger_node.data)
return node
def _find_min(self, node):
while node.left:
node = node.left
return node
def search(self, data):
return self._search_recursive(self.root, data)
def _search_recursive(self, node, data):
if not node:
return False
if data == node.data:
return True
elif data < node.data:
return self._search_recursive(node.left, data)
else:
return self._search_recursive(node.right, data)
def inorder_traversal(self):
result = []
self._inorder_recursive(self.root, result)
return result
def _inorder_recursive(self, node, result):
if node:
self._inorder_recursive(node.left, result)
result.append(node.data)
self._inorder_recursive(node.right, result)
4. 动态规划
真题示例：
题目： 给定一个整数数组，找出所有相加和为特定值的不重复子序列。
代码示例：
def find_subsequences(nums, target):
def backtrack(start, path, target):
if target == 0:
result.append(path)
return
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
backtrack(i + 1, path + [nums[i]], target - nums[i])
result = []
nums.sort()
backtrack(0, [], target)
return result
通过以上真题的练习，相信考生在考研中能够更好地应对数据结构部分的挑战。加油！