📚 IB OCR Computer Science: Data Structures Essentials | IB OCR 计算机：数据结构 考点精讲
Data structures form the backbone of efficient programming, enabling us to organise and manage data for optimal access and modification. In IB and OCR Computer Science syllabi, you are expected not only to understand how these structures work but also to evaluate their time and space complexity using Big O notation. This article unpacks the most important concepts—from arrays to graphs—and provides clear explanations, comparisons, and practical insights to help you confidently tackle exam questions.
数据结构是高效编程的基石，它们让我们能够以最佳方式组织和操作数据。在 IB 和 OCR 计算机科学大纲中，你不仅需要理解这些结构的工作原理，还要能用大 O 表示法评估其时间与空间复杂度。本文梳理了从数组到图的最重要概念，提供清晰的解释、对比和实用洞见，帮助你自信应对考试中的相关问题。
1. Static Arrays | 静态数组
wever, insertion and deletion (except at the end) require shifting subsequent elements, giving O(n) time complexity. Static arrays are simple and offer cache-friendly performance, but their size cannot change at runtime.
静态数组是一块连续的内存空间，存放固定数量且类型相同的元素。通过索引访问元素的时间复杂度为 O(1)，因为可以直接计算内存地址：基地址 + (索引 × 元素大小)。但在非末尾位置插入或删除元素时，需要移动后续元素，时间复杂度为 O(n)。静态数组结构简单，缓存性能良好，但大小在运行时不可改变。
- Fixed size allocated at compile time / 编译时分配固定大小
- Random access O(1) / 随机访问 O(1)
- Insertion/Deletion O(n) / 插入/删除 O(n)
- Used when the number of elements is known in advance / 适用于元素个数提前已知的场景
2. Dynamic Arrays (Array Lists) | 动态数组（数组列表）
Dynamic arrays, like Python's list or Java's ArrayList, abstract away fixed-size limitations by automatically resizing. Internally they use a static array, and when the capacity is exceeded, a larger array is allocated and elements are copied over. Amortised analysis shows that appending an element is O(1) on average, though a single append may trigger an O(n) resizing step. Random access remains O(1), which makes dynamic arrays a popular choice for general-purpose collections.
动态数组（例如 Python 的 list 或 Java 的 ArrayList）通过自动扩展抽象掉了固定大小的限制。其内部仍使用一个静态数组，当容量不足时会分配更大的数组并复制原有元素。摊还分析表明，追加一个元素平均只需 O(1) 时间，尽管某一次追加可能触发 O(n) 的扩容操作。随机访问依然是 O(1)，这使动态数组成为通用集合的流行选择。
Key operations:
| Operation | Complexity | 操作 | 复杂度 |
|---|---|---|---|
| Access by index | O(1) | 按索引访问 | O(1) |
| Append (amortised) | O(1) | 追加（摊还） | O(1) |
| Insert/Delete at index | O(n) | 在指定位置插入/删除 | O(n) |
| Search (unsorted) | O(n) | 搜索（无序） | O(n) |
3. Linked Lists | 链表
A linked list consists of nodes, each containing data and a pointer to the next node (singly linked) or to both next and previous nodes (doubly linked). Unlike arrays, elements are not stored contiguously, so accessing an element by position takes O(n) time because you must traverse from the head. However, insertion and deletion at known positions (especially at the head) can be done in O(1) by adjusting pointers, assuming you already have a reference to the node.
链表由节点组成，每个节点包含数据以及指向下一个节点（单向链表）或同时指向上一个和下一个节点的指针（双向链表）。与数组不同，元素不连续存放，因此按位置访问元素需要 O(n) 时间，因为必须从头节点开始遍历。但在已知位置（尤其是头部）进行插入和删除只需调整指针，时间复杂度为 O(1)，前提是你已经持有相关节点的引用。
Comparison with arrays:
- No need for contiguous memory / 不需要连续内存
- Dynamic size, grows without copying overhead / 动态大小，扩展时无复制开销
- Extra memory overhead for pointers / 指针带来额外内存开销
- Poor cache locality compared to arrays / 缓存局部性较数组差
4. Stacks (LIFO) | 栈（后进先出）
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. The two primary operations are push (add an item to the top) and pop (remove the item from the top), both running in O(1) time. A stack can be implemented using an array or a linked list. Typical applications include managing function calls (call stack), undo mechanisms, and expression evaluation (e.g., converting infix to postfix).
栈是一种遵循后进先出（LIFO）原则的线性数据结构。两个主要操作是压入（push，向栈顶添加元素）和弹出（pop，移除栈顶元素），均以 O(1) 时间运行。栈可以用数组或链表实现。典型应用包括管理函数调用（调用栈）、撤销机制，以及表达式求值（例如中缀转后缀）。
Common exam focus:
- Overflow: pushing when stack is full (in array implementation) / 上溢：栈满时压入（数组实现）
- Underflow: popping from an empty stack / 下溢：栈空时弹出
- Trace stacks for recursive algorithms / 追踪递归算法的栈变化
5. Queues (FIFO) | 队列（先进先出）
A queue operates on the First In, First Out (FIFO) principle, with enqueue (add to the rear) and dequeue (remove from the front) both ideally O(1). Circular queues improve space utilisation by wrapping around in an array, avoiding the need to shift elements. Priority queues remove elements based on priority rather than arrival order, often implemented with a heap (binary heap) providing O(log n) for enqueue and dequeue.
队列按先进先出（FIFO）原则运行，入队（enqueue，在尾部添加）和出队（dequeue，从头部移除）的理想时间复杂度均为 O(1)。循环队列通过在数组中循环使用空间来提高利用率，避免元素移动。优先级队列根据优先级而非到达顺序移除元素，通常使用堆（二叉堆）实现，入队和出队需 O(log n) 时间。
Queue implementations:
| Type | Enqueue | Dequeue | Notes |
|---|---|---|---|
| Linear Queue (array) | O(1) | O(1)* but can waste space | * Shifting may be needed |
| Circular Queue | O(1) | O(1) | Uses front and rear pointers |
| Linked Queue | O(1) | O(1) | Dynamic memory, no overflow |
6. Trees and Binary Trees | 树与二叉树
A tree is a hierarchical structure with a root node and child nodes connected by edges. A binary tree restricts each node to at most two children. Traversal methods—pre-order (root, left, right), in-order (left, root, right), and post-order (left, right, root)—are frequently examined. Binary search trees (BST) maintain ordering: left subtree < node < right subtree, enabling search, insert, and delete in O(log n) on average, but O(n) in the worst case (unbalanced).
树是一种分层结构，由根节点和通过边连接的子节点组成。二叉树限制每个节点最多只能有两个子节点。遍历方法——前序（根、左、右）、中序（左、根、右）和后序（左、右、根）——是常见考点。二叉搜索树（BST）维护顺序关系：左子树 < 节点 < 右子树，使得搜索、插入和删除平均可在 O(log n) 时间内完成，但最坏情况下（不平衡）退化为 O(n)。
Exam tips:
- Construct BST from a sequence of insertions / 根据插入序列构造 BST
- Identify valid traversal sequences / 识别合法的遍历序列
- Understand the difference between balanced and unbalanced trees / 理解平衡与不平衡树的区别
7. Graphs: Representations and Traversals | 图：表示与遍历
V²) space, O(1) edge query) and adjacency list (array of lists, O(V+E) space, O(degree) edge query). Depth-first search (DFS) uses a stack (or recursion) and explores as far as possible along branches; breadth-first search (BFS) uses a queue and explores neighbours level by level. Both visit all vertices in O(V+E).
图 G = (V, E) 由顶点和边组成。图可以是有向的或无向的，带权的或不带权的。两种常见的存储表示是邻接矩阵（V×V 矩阵，O(V²) 空间，O(1) 边查询）和邻接表（列表的数组，O(V+E) 空间，O(度数) 边查询）。深度优先搜索（DFS）使用栈（或递归），沿着分支尽可能深入探索；广度优先搜索（BFS）使用队列，逐层探索邻居节点。两者均可在 O(V+E) 时间内访问所有顶点。
Applications to know:
- Shortest path in unweighted graph: BFS / 无权图最短路径：BFS
- Topological sorting: DFS / 拓扑排序：DFS
- Cycle detection / 环检测
- Graph colouring / 图着色
8. Hash Tables | 哈希表
A hash table maps keys to values using a hash function to compute an index into an array of buckets. Ideally, search, insertion, and deletion are O(1) on average. Collisions occur when different keys hash to the same index; common resolution techniques are chaining (storing a linked list at each bucket) and open addressing (probing for the next empty slot, e.g., linear probing). Load factor (number of entries / number of buckets) influences performance: a high load factor increases collision chances.
哈希表通过哈希函数计算键在桶数组中的索引，从而实现键到值的映射。理想情况下，搜索、插入和删除的平均时间复杂度为 O(1)。不同键哈希到同一索引时会发生冲突；常用的解决方法有拉链法（在每个桶中存储一个链表）和开放地址法（探测下一个空槽，例如线性探测）。负载因子（条目数 / 桶数）影响性能：高负载因子会增加冲突概率。
Key concepts:
- Good hash function distributes keys uniformly / 好哈希函数使键均匀分布
- Rehashing: resizing the table when load factor exceeds threshold / 再哈希：负载因子超过阈值时调整表大小
- Use cases: dictionaries, caches, database indexing / 应用场景：字典、缓存、数据库索引
9. Big O Complexity Comparison | 大 O 复杂度对比
Examiners frequently ask you to compare the efficiency of different data structures for a given scenario. The table below summarises average-case time complexities for common operations. Always be prepared to justify your choice based on the required operations—random access favours arrays, frequent insertions at the head favour linked lists, key-value lookups favour hash tables.
考官经常要求你针对特定场景比较不同数据结构的效率。下表总结了常见操作的平均时间复杂度。随时准备好根据所需操作论证你的选择——频繁随机访问倾向于数组，频繁在头部插入倾向于链表，键值查找倾向于哈希表。
| Structure | Access | Search | Insertion | Deletion |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) |
| Stack/Queue | O(n) | O(n) | O(1) | O(1) |
| Binary Search Tree (avg) | O(log n) | O(log n) | O(log n) | O(log n) |
| Hash Table | N/A | O(1) | O(1) | O(1) |
10. Choosing the Right Data Structure | 选择合适的数据结构
A common IB/OCR style question provides a scenario—like an undo feature in a text editor, a printer queue, or a contacts list—and asks which data structure is most appropriate. The decision depends on the primary operations: if you need to recall the most recent action, a stack is ideal; if you must maintain the order of arrival, a queue fits; if you need rapid key-based retrieval, a hash table is best. Always consider memory constraints and whether data size changes dynamically.
IB 和 OCR 常见的一类问题是给出一个场景——比如文本编辑器中的撤销功能、打印机队列或联系人列表——然后询问哪种数据结构最合适。决定取决于主要操作：如果需要回溯最近的操作，栈是理想选择；如果必须保持抵达顺序，队列适用；如果需要基于键的快速检索，哈希表最佳。还要始终考虑内存限制以及数据大小是否会动态变化。
Practice example:
- Browser back button → Stack / 浏览器后退按钮 → 栈
- Print spooler → Queue / 打印缓冲池 → 队列
- Spell checker dictionary → Hash Table / 拼写检查字典 → 哈希表
- File system hierarchy → Tree / 文件系统层次结构 → 树
- Social network friends → Graph / 社交网络好友 → 图
11. Abstract Data Types (ADTs) vs Data Structures | 抽象数据类型与数据结构
An abstract data type defines expected behaviour (operations) without specifying implementation. For example, a Stack ADT defines push, pop, and top, but it can be implemented using an array or a linked list. In exams, distinguishing between ADT (what) and data structure (how) demonstrates deeper understanding. This distinction is particularly emphasised in OCR A-level specifications.
抽象数据类型（ADT）定义了预期的行为（操作）而不规定具体实现。例如，Stack ADT 定义了 push、pop 和 top，但它可以用数组或链表实现。在考试中，区分 ADT（是什么）和数据结构（怎么做）能够体现你对概念的深层理解。OCR A-level 大纲尤其强调这一区别。
Common ADTs and possible implementations:
- Stack: array, linked list / 栈：数组、链表
- Queue: circular array, linked list / 队列：循环数组、链表
- List: array, linked list / 列表：数组、链表
- Dictionary (Map): hash table, BST / 字典（映射）：哈希表、BST
12. Exam Technique and Common Pitfalls | 应试技巧与常见错误
structure questions, always state the complexity class and explain why. For instance, say ' is contiguous, and the address of any element can be calculated with base + index × size.' Avoid vague terms like 'fast' or 'efficient' out for edge cases: empty structures, duplicate keys in BST, and resizing in hash tables.
回答数据结构问题时，务必陈述复杂度等级并解释原因。例如，可以说“数组访问为 O(1)，因为内存连续，可以通过 基地址 + 索引 × 元素大小 计算任意元素的地址”。避免在没有大 O 精确描述的情况下使用“很快”或“高效”等模糊词汇。多练习绘制链表指针操作和树旋转的示意图；这有助于避免在插入/删除算法中出错。同时请留意边界情况：空结构、BST 中的重复键，以及哈希表的扩容。
Revision checklist:
- Can you implement a linked list reversal? / 你能实现链表反转吗？
- Do you understand the difference between linear and circular queues? / 你理解线性队列和循环队列的区别吗？
- Can you trace DFS and BFS on a given graph? / 你能在给定图上追踪 DFS 和 BFS 吗？
- Are you confident explaining hash collision resolution? / 你有信心解释哈希冲突解决方法吗？
- Can you evaluate trade-offs between array and linked list implementations? / 你能评估数组和链表实现的权衡吗？
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图