Data Structure Lesson 1 Checkpoint

Purpose:

用 10–15 分钟检查第一课是否仍能独立判断，而不是重新阅读知识正文。

Coverage:

• Time Complexity
• Array / Linked List
• Stack / Queue / Deque
• Hash Table
• Direct Addressing
• Two Sum

Target:

• Accuracy: >= 12 / 14
• Time: <= 15 min

---

Questions

Q1

下面代码的时间复杂度是多少？

i = 1
while i < n:
    i *= 2

A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)

Q2

下面代码的时间复杂度是多少？

for i in range(n):
    for j in range(i):
        pass

A. O(n)
B. O(n log n)
C. O(n²)
D. O(n³)

Q3

长度为 n 的数组随机访问第 i 个元素，典型时间复杂度是多少？

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Q4

链表在“已经获得待插入位置对应节点”的前提下插入新节点，典型复杂度是多少？

A. O(1)
B. O(log n)
C. O(n)
D. 无法判断

Q5

为什么不能简单说“链表插入永远是 O(1)”？

A. 链表不支持插入
B. 如果需要先遍历定位位置，定位本身可能是 O(n)
C. 指针修改一定是 O(n)
D. 链表只能尾插

Q6

Python 中用于高频 FIFO 出队，更合适的是：

A. list.pop(0)
B. deque.popleft()
C. set.pop()
D. dict.popitem()

Q7

DFS 与 BFS 常见的核心辅助数据结构分别是：

A. Queue / Stack
B. Stack / Queue
C. Set / Map
D. Heap / Stack

Q8

Hash Table 查询为什么通常描述为“平均 O(1)”而不是“永远 O(1)”？

A. Hash Function 必须遍历全部数据
B. 可能发生 Hash Collision
C. Hash Table 不能删除元素
D. 所有 key 都必须排序

Q9

对于 key 范围固定为 0 ~ 999、且非常稠密的布尔状态，通常最直接的结构是：

A. Linked List
B. Direct Address Array / Bitmap
C. BST
D. Queue

Q10

对于巨大、稀疏且可能是字符串的 key，高频存在性查询更适合优先考虑：

A. Direct Address Array
B. Hash Table / Set
C. Queue
D. Stack

Q11

Two Sum 的单次遍历 Hash Map 解法中，遍历当前值 x 时应该查询：

A. target % x
B. target - x 是否已经出现
C. x % target
D. 当前数组最大值

Q12

Two Sum 中若需要返回下标，常见 seen 状态设计是：

A. key = target, value = x
B. key = 已出现的值, value = 下标
C. key = 下标, value = target
D. 只使用 Queue

Q13

长度为 n 的 Hash Set 作为算法额外存储，其额外空间复杂度通常为：

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Q14

动态数组在容量足够时尾部追加通常是 O(1)，偶尔扩容需要搬移大量元素，因此长期平均常描述为：

A. Worst-case O(1)
B. Amortized O(1)
C. O(log n)
D. O(n²)

---

Answers & Fastest Reasoning

Q	Answer	Fastest Reasoning
1	B	每轮规模乘 2，执行次数约为 log₂n
2	C	总次数 0+1+...+(n-1)=O(n²)，不能再额外乘一次外层
3	A	连续存储，可由下标直接计算地址
4	A	已定位后只修改有限个指针
5	B	O(1) 插入的前提是位置已经找到
6	B	list.pop(0) 需要整体移动后续元素；deque 为双端操作设计
7	B	DFS 常用 Stack，BFS 常用 Queue
8	B	碰撞会增加 bucket 内进一步查找成本
9	B	小范围稠密整数 key 适合直接寻址
10	B	Hash 将巨大/复杂 key 映射到有限 bucket
11	B	need = target - x，查询 need 是否出现
12	B	未来通过值查询，命中后需要拿到历史下标
13	C	最坏需要保存与输入规模同阶的元素
14	B	偶发 O(n) 扩容成本摊到多次 append 后为 Amortized O(1)

---

Attempts

Date	Correct	Time	Main Error

出现稳定错误时，不在本文件扩写长解释：

• 概念忘记 → 回到对应知识正文；
• 真实错误模式 → 记录到 05_Mistakes/CS.md。