40 marks · Based on multiple sample exams 40 分 · 基于多套模拟样卷
All three conditions must be satisfied simultaneously to pass the hurdle: 必须同时满足以下三个条件才能通过 hurdle：
An O(2ⁿ) algorithm processes input size 10 in 1 day. A computer 1000× faster — what is the max input size in 1 day? O(2ⁿ) 算法，当前电脑跑 n=10 需要 1 天。快 1000 倍的电脑，最大能跑多大 n？
⚡ Step-by-step: ⚡ 解题步骤：
fnA: recurses (b-a) times with O(1) work each → 递归 (b-a) 次，每次 O(1) → O(n)
fnB: calls fnA O(n) + recurse on n-1 → T(n) = T(n-1) + O(n) → 调用 fnA O(n) + 递归 n-1 个元素 → O(n²)
fnB is Selection Sort — fnA finds the minimum, fnB swaps it to the front each round.fnB 就是选择排序 — fnA 找最小值，fnB 每轮把最小值换到前面。
You have only the executable, no source code. How do you determine which algorithm it uses? 只有可执行文件，没有源代码。如何判断它用的是哪种算法？
✅ Method: Test with a large already-sorted array and time it. ✅ 方法：构造大的已排序数组，计时测试。
Median-of-3 avoids worst-case on sorted arrays by choosing pivot as the median of first/middle/last elements. 三数取中通过取首/中/尾三个元素的中位数作为 pivot，避免了已排序数组的最坏情况。
Check if equal-key elements maintain their original relative order in the output. 检查相同 key 的元素在输出中是否保持了原来的相对顺序。
| Key group | Input order (2nd value) | Output order (2nd value) | Stable? |
|---|---|---|---|
| key = 2 | 8, 9, 7 | 8, 9, 7 | ✓ Yes |
| key = 4 | 7, 3, 4 | 7, 3, 4 | ✓ Yes |
| key = 5 | 1, 6, 9 | 1, 6, 9 | ✓ Yes |
Conclusion:结论： Output preserves original order for all equal-key groups → appears stable. 输出保持了所有相同 key 组的原始顺序 → 表现为稳定。
Confidence: Medium置信度：中等 — only one test case. Can't be 100% certain without testing more inputs. 只有一个测试用例，无法 100% 确定。
Error: dereferencing pointer to incomplete type 'struct graph' at line g->edges[u][v] = true
错误：dereferencing pointer to incomplete type 'struct graph'，出现在 g->edges[u][v] = true
✅ Answer template (3 sentences = 3 marks): ✅ 答题模板（3 句话 = 3 分）：
Graph.h declares struct graph as an opaque type — the internal fields are defined only in Graph.c and intentionally hidden from callers (information hiding / ADT encapsulation).
原因：Graph.h 把 struct graph 声明为 opaque type，内部字段只在 Graph.c 中定义，外部代码无法看到（信息隐藏 / ADT 封装）。
prog.c cannot see the edges field, so the compiler reports "incomplete type".
结果：prog.c 看不到 edges 字段，编译器报告 "incomplete type"。
g->edges directly — use the ADT functions e.g. GraphAddEdge(g, u, v).
修复：不要直接访问 g->edges，改用 ADT 提供的函数，如 GraphAddEdge(g, u, v)。
💡 Keywords to use: opaque type, information hiding, ADT encapsulation, internal structure 💡 关键词：opaque type、information hiding、ADT encapsulation、internal structure
Pre-order: 16, 10, 7, 2, 8, 14, 24, 20, 40, 33
Step 1: Reconstruct tree (pre-order = Root, Left, Right → first element is always root) 第1步：还原树（前序 = 根左右 → 第一个元素永远是根）
Post-order (Left, Right, Root): 2, 8, 7, 14, 10, 20, 33, 40, 24, 16 后序（左右根）：2, 8, 7, 14, 10, 20, 33, 40, 24, 16
Answer: B答案：B
⚠️ Common trap: Option A has "2, 7, 8..." — wrong! 8 is 7's right child, so post-order = 2 (left) → 8 (right) → 7 (root). Never "2, 7, 8". ⚠️ 常见陷阱：选项 A 是 "2, 7, 8..."，错误！8 是 7 的右孩子，后序应该是 2（左）→ 8（右）→ 7（根）。不能是 "2, 7, 8"。
Apply twice from node 20: the right-grandchild of 20 becomes the new root. 20 becomes its left-grandchild. 从节点 20 开始做两次左旋：20 的右孙子变成新的根，20 变成它的左孙子。
| Imbalance Type | Rotation Needed | Memory Trick |
|---|---|---|
| LL (left-left) | Right rotation | Lean left → fix with right |
| RR (right-right) | Left rotation | Lean right → fix with left |
| LR (left-right) | Left then Right | Zig-zag left: straighten first, then fix |
| RL (right-left) | Right then Left | Zig-zag right: straighten first, then fix |
Balance factor平衡因子 = height(left) − height(right). If |balance factor| > 1 at any node → rotation needed.任何节点的 |平衡因子| > 1 → 需要旋转。
Edges added in order: A-E, C-D, E-B, E-C. Which algorithms could produce this MST? 加边顺序：A-E, C-D, E-B, E-C。哪些算法能产生这棵 MST？
| Algorithm | Builds MST? | Could produce this? |
|---|---|---|
| Depth-First Search | ❌ No — just traversal, ignores weights | ❌ Eliminate |
| Dijkstra's Algorithm | ❌ No — finds shortest paths, not MST | ❌ Eliminate |
| Kruskal's Algorithm | ✅ Yes | ✅ Globally selects cheapest edges that don't form a cycle |
| Prim's Algorithm | ✅ Yes | ✅ Expands from one node, always picks nearest unvisited |
✅ Answer: Kruskal and Prim ✅ 答案：Kruskal 和 Prim
💡 What is MST? 💡 什么是 MST？
Minimum Spanning Tree — connect all nodes using n-1 edges with minimum total weight, no cycles. 最小生成树 — 用 n-1 条边连通所有节点，总权重最小，不含环。
11 slots, hash(k) = k % 11, separate chaining (sorted ascending), insert keys 1–100.
11 个槽，hash(k) = k % 11，separate chaining（链内升序），插入 key 1–100。
After N total items, each slot has approximately ⌈N/11⌉ items.
Worst case = searching for a key not in the table, in the longest chain.
N 个元素后，每个槽约有 ⌈N/11⌉ 个元素。
最坏情况 = 搜索不存在的 key，落在最长链中。
Answer: ⌈N/11⌉答案：⌈N/11⌉
Priority Queue with Push, Pop (highest priority), PrintInOrder (all in decreasing order). All three used frequently. Priority Queue 需要支持：Push、Pop（最高优先级）、PrintInOrder（降序打印全部）。三种操作都频繁使用。
| Data Structure | Push | Pop | PrintInOrder | Verdict |
|---|---|---|---|---|
| Ordered Array | O(n) | O(1) | O(n) | ❌ Push too slow |
| Ordered Linked List | O(n) | O(1) | O(n) | ❌ Push too slow |
| AVL Tree | O(log n) | O(log n) | O(n) | ✅ Best overall |
| Hash Table | O(1) | O(n) | O(n log n) | ❌ Pop & Print slow |
| Heap | O(log n) | O(log n) | O(n log n) | ❌ PrintInOrder slow |
✅ Answer: AVL Tree ✅ 答案：AVL Tree
Key argument: PrintInOrder is the deciding factor. A Heap requires repeated Pop → O(n log n). An AVL Tree's in-order traversal is naturally sorted → O(n). Push and Pop are both O(log n), same as Heap. AVL is strictly better. 核心论点：PrintInOrder 是决定性因素。Heap 需要反复 Pop → O(n log n)。AVL 的中序遍历天然有序 → O(n)。Push 和 Pop 都是 O(log n)，与 Heap 相同。AVL 严格更优。
| Algorithm | Best | Average | Worst | Stable? | Memory Trick |
|---|---|---|---|---|---|
| Selection Sort | O(n²) | O(n²) | O(n²) | ❌ No | Always picks the smallest remaining |
| Insertion Sort | O(n) | O(n²) | O(n²) | ✅ Yes | Like sorting playing cards in hand |
| Bubble Sort | O(n) | O(n²) | O(n²) | ✅ Yes | Largest bubbles to the right each pass |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | ✅ Yes | Split in half, sort each, merge back |
| Quicksort | O(n log n) | O(n log n) | O(n²) | ❌ No | Pick pivot, partition left/right |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | ❌ No | Build max-heap, repeatedly extract max |
⚡ Unstable = "Quick Selection Heap" — only Quicksort, Selection Sort, Heap Sort are unstable. All others are stable. ⚡ 不稳定 = "快选堆" — 只有快速排序、选择排序、堆排序是不稳定的。其他全部稳定。
20 questions covering all theory topics — no exam references, pure concept testing. 20 道题覆盖全部理论知识点 — 纯概念测试，无考题信息。
Start Theory Quiz → 开始理论测验 →