<think>嗯，用户需要Python数据结构期末考试代码题范例，重点在链表反转和二叉树相关题型。参考引用中，引用[1]提到面试常考二分查找、哈希表、堆、DFS/BFS、动态规划等；引用[2]强调大厂常考算法题；引用[4]描述二叉树结构；引用[5]展示计数排序的步骤。这些和用户需求直接相关。 用户明确提到链表反转和二叉树，这是数据结构的核心考点。需要提供可直接运行的代码范例和清晰注释，同时覆盖高频题型。引用[1]中提到的动态规划、堆等虽重要，但用户当前聚焦链表和二叉树，其他内容可作为扩展。 关于链表反转，需包含迭代和递归两种实现，这是基础考点。二叉树部分要覆盖遍历（前中后序）、求深度、对称性判断，这些在引用[4]的二叉树结构描述中有依据。附加题参考引用[1]的面试套路：排序用二分查找（如快排），无序统计用哈希表（如两数之和），堆用于TopK问题。 最后生成的问题要引导用户深入：链表递归反转的复杂度、二叉树遍历的应用场景、堆与快排的对比——这些在引用[1][2]的面试题分析中都有提及，能帮助用户举一反三。 </think> 以下是Python数据结构期末考试常见代码题范例及解析，涵盖链表反转、二叉树操作等高频考点： ### 一、链表反转（必考） ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverse_list(head: ListNode) -> ListNode: """迭代法反转链表""" prev = None curr = head while curr: next_node = curr.next # 保存下一节点 curr.next = prev # 反转指针 prev = curr # 移动prev curr = next_node # 移动curr return prev # 新头节点 ``` **考点分析**： 1. 指针操作（`curr.next = prev`） 2. 边界处理（空链表/单节点链表） 3. 时间复杂度 $O(n)$，空间复杂度 $O(1)$ ### 二、二叉树遍历（递归/非递归） ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right # 递归前序遍历 def preorder(root: TreeNode) -> list: if not root: return [] return [root.val] + preorder(root.left) + preorder(root.right) # 非递归中序遍历 def inorder(root: TreeNode) -> list: stack, res = [], [] curr = root while curr or stack: while curr: # 深入左子树 stack.append(curr) curr = curr.left curr = stack.pop() # 回溯父节点 res.append(curr.val) curr = curr.right # 转向右子树 return res ``` ### 三、二叉树深度计算 ```python def max_depth(root: TreeNode) -> int: if not root: return 0 left_depth = max_depth(root.left) # 左子树深度 right_depth = max_depth(root.right) # 右子树深度 return max(left_depth, right_depth) + 1 # 当前层深度 ``` ### 四、对称二叉树判断 ```python def is_symmetric(root: TreeNode) -> bool: def check(l, r): if not l and not r: return True if not l or not r: return False return l.val == r.val and check(l.left, r.right) and check(l.right, r.left) return check(root.left, root.right) if root else True ``` ### 五、附加常考题（参考引用[1][5]） 1. **二分查找变体**（旋转数组搜索） 2. **哈希表应用**（两数之和） 3. **堆操作**（Top K 问题） 4. **计数排序**（引用[5]的数组统计思想） > 考试重点提示： > 1. 链表操作必考指针修改顺序，注意断链保护 > 2. 二叉树递归需明确终止条件，非递归掌握栈/队列应用 > 3. 复杂度分析常结合代码提问（如问递归深度空间复杂度） > 4. 实际考题多为基础算法的组合（如：反转链表+快慢指针找中点）