Ch14 数据结构与算法 · 阶段测试题 (25 题)¶

测试目标: 全面考察 Ch14 六节内容: 基础(§00) / 数组哈希(§01) / 链表栈队(§02) / 树(§03) / 图(§04) / 排序搜索(§05) 难度分布: ★ 基础 / ★★ 中等 / ★★★ 拔高 / ⭐⭐⭐⭐ 竞赛

Part A 选择题 (10 题, 每题 3 分)¶

A1 (★★)¶

题目: 二分查找时间复杂度? - A) \(O(1)\) - B) \(O(\log n)\) - C) \(O(n)\) - D) \(O(n \log n)\)

答案: B

A2 (★★★)¶

题目: 哈希表最坏查找复杂度? - A) \(O(1)\) - B) \(O(\log n)\) - C) \(O(n)\) - D) \(O(n^2)\)

答案: C (冲突严重时)

A3 (★★)¶

题目: 快速排序最坏时间复杂度? - A) \(O(n)\) - B) \(O(n \log n)\) - C) \(O(n^2)\) - D) \(O(2^n)\)

答案: C (pivot 极端)

A4 (★★★)¶

题目: Dijkstra 不适用什么图? - A) 无权图 - B) 有负权图 - C) 有环图 - D) 完全图

答案: B

A5 (★★)¶

题目: BFS 用什么数据结构? - A) 栈 - B) 队列 - C) 堆 - D) 链表

答案: B

A6 (★★★)¶

题目: BST 中序遍历结果是? - A) 层序 - B) 有序 - C) 逆序 - D) 随机

答案: B

A7 (★★)¶

题目: 堆插入时间复杂度? - A) \(O(1)\) - B) \(O(\log n)\) - C) \(O(n)\) - D) \(O(n \log n)\)

答案: B

A8 (★★★)¶

题目: Union-Find 经路径压缩 + 按秩合并后? - A) \(O(\log n)\) - B) \(O(n)\) - C) \(O(\alpha(n))\), 几乎 \(O(1)\) - D) \(O(1)\) 严格

答案: C

A9 (★★)¶

题目: Python list 是数组还是链表? - A) 静态数组 - B) 动态数组 - C) 链表 - D) 树

答案: B

A10 (★★★)¶

题目: AVL 树与红黑树差别? - A) 完全相同 - B) AVL 严格平衡, 红黑近似 - C) 红黑严格平衡, AVL 近似 - D) AVL 用链表, 红黑用数组

答案: B

Part B 简答题 (8 题, 每题 5 分)¶

B1 (★★★)¶

题目: 解释大 O 记号, 给出 \(O(n)\), \(O(n \log n)\), \(O(n^2)\) 各一个算法例子。

要点: - 上界定义 - \(O(n)\): 线性扫描 - \(O(n \log n)\): 归并排序 - \(O(n^2)\): 冒泡

B2 (★★★)¶

题目: 数组 vs 链表的取舍。

要点: - 数组访问 \(O(1)\), 插入 \(O(n)\) - 链表访问 \(O(n)\), 插入 \(O(1)\) - 数组缓存友好

B3 (★★★)¶

题目: 哈希冲突的解决方法及优劣。

要点: - 链地址: 简单, 浪费指针 - 开放定址: 节省空间, 但易聚集

B4 (★★★)¶

题目: BFS 和 DFS 的对比。

要点: - BFS 队列, 最短路 (无权) - DFS 栈 / 递归, 拓扑 / 回溯

B5 (★★★)¶

题目: Dijkstra 算法步骤。

要点: - 优先队列 - 松弛邻居 - 不适用负权

B6 (★★★)¶

题目: LRU Cache 实现思路。

要点: - 双向链表 + 哈希表 - 访问移到头, 淘汰尾

B7 (★★★)¶

题目: 比较主要排序算法的稳定性。

要点: - 稳定: 归并 / 插入 / 冒泡 / Tim / 计数 - 不稳定: 快排 / 堆排 / 选择 / 希尔

B8 (★★★)¶

题目: Trie 应用场景。

要点: - 前缀匹配 (BPE / 自动补全) - 拼写检查 - IP 路由

Part C 编程题 (5 题, 每题 10 分)¶

C1 (★★★)¶

题目: 实现 LRU Cache。

要点: - 双向链表 + dict - get / put \(O(1)\) - LeetCode 146

from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()
    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key)
        return self.cache[key]
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

C2 (★★★)¶

题目: 实现 Dijkstra 最短路。

要点: - 邻接表 + 优先队列 - 返回 dist 字典

import heapq
def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

C3 (★★★)¶

题目: 实现快速排序。

要点: - 分治, 选 pivot, 递归 - 期望 \(O(n \log n)\)

def quicksort(arr):
    if len(arr) <= 1: return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + mid + quicksort(right)

C4 (★★★)¶

题目: 实现 Union-Find。

要点: - 路径压缩 + 按秩合并 - \(O(\alpha(n))\) 几乎常数

class UF:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
        return True

C5 (★★★)¶

题目: 实现 Trie (前缀树)。

要点: - 节点存 children dict 和 is_end 标志 - insert / search / startsWith \(O(L)\), L 是词长

class Trie:
    def __init__(self):
        self.root = {}
        self.is_end = False
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node: node[ch] = {}
            node = node[ch]
        node['#'] = True
    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node: return False
            node = node[ch]
        return '#' in node

Part D 综合题 (2 题, 每题 15 分)¶

D1 (⭐⭐⭐⭐)¶

题目: 用 LRU + 哈希表设计一个分布式 KV 存储的缓存层, 写出关键组件。

参考架构: 1. 一致性哈希分片 2. 每分片 LRU 缓存 3. 布隆过滤器减少误读 4. 异步写回

D2 (⭐⭐⭐⭐)¶

题目: 用 Dijkstra 实现 A* 算法, 用启发式加速, 给出伪代码。

要点: - \(f(n) = g(n) + h(n)\) - \(g\) 实际代价, \(h\) 启发式 - \(h\) 可采纳 (< 真实) 保证最优

评分标准¶

题型	题数	总分
选择	10	30
简答	8	40
编程	5	50
综合	2	30
合计	25	150

自测建议¶

目标	分数	行动
及格	75	复习 §00-§01, 默写哈希 + 数组
良好	100	复习 §03-§04, 跑通编程 C1-C3
优秀	120	复习 §05 排序, 完成综合 D1-D2