📚 IB AQA Computer Science: Data Structures Exam Focus | IB AQA 计算机：数据结构考点精讲
Data structures form the backbone of efficient algorithms and are central to the IB AQA Computer Science syllabus. This guide breaks down every core abstract data type, their implementations, and the scenarios where each excels, with exact time complexities and exam-focused comparisons. Mastering this content equips you to tackle paper-based tracing questions and design solutions with confidence.
数据结构是高效算法的基石，也是 IB AQA 计算机科学课程的核心。本指南将逐一拆解所有核心抽象数据类型、实现方式以及各自擅长的场景，并给出精确的时间复杂度与面向考试的对比。掌握这些内容能让你从容应对纸笔代码追踪题，并自信地设计解决方案。
1. Abstract Data Types vs Data Structures | 抽象数据类型与数据结构之分
An abstract data type (ADT) is a conceptual model that specifies the operations and their behaviour without defining implementation details. A data structure is the concrete realisation of an ADT in a programming language, including memory layout and algorithms.
抽象数据类型（ADT）是一种概念模型，它规定了操作及其行为，但不定义实现细节。而数据结构是 ADT 在编程语言中的具体实现，包括内存布局和算法。在思维层面，我们先用 ADT 推理，再用数据结构落地。
Key ADTs examined in the course include stacks, queues, lists, trees, and graphs. Their behaviour is described purely by interfaces — for example, push(item) and pop() for a stack — while the underlying data structure could be an array or a linked list. Understanding this separation helps in choosing the most appropriate concrete structure for a given performance requirement.
课程中考查的关键 ADT 包括栈、队列、列表、树和图。其行为完全由接口描述，例如栈的 push(item) 和 pop()，而底层数据结构可以是数组或链表。理解这种分离有助于根据性能需求选择最合适的具体结构。
2. Arrays: Static and Dynamic | 数组：静态与动态
An array stores elements of the same type in contiguous memory, offering O(1) random access via an index. Static arrays have a fixed size determined at compile time, while dynamic arrays (such as Python lists or Java ArrayLists) can grow by allocating a larger block and copying elements, typically doubling capacity to achieve amortised O(1) append.
数组将同类型元素存储在连续内存中，通过索引提供 O(1) 的随机访问。静态数组的大小在编译时确定，而动态数组（如 Python 列表或 Java ArrayList）可以通过分配更大的内存块并复制元素来增长，通常采用容量翻倍策略，实现摊销 O(1) 的末尾插入。
Insertion and deletion anywhere except the end require shifting elements, which is O(n) in the average and worst case. Two-dimensional arrays model matrices and grids, with row-major or column-major layout impacting cache performance but not algorithmic complexity. You must be able to trace multi-dimensional array access in exam pseudocode.
除末尾外的插入和删除都需要移动元素，平均和最坏情况均为 O(n)。二维数组用于建模矩阵和网格，行主序或列主序布局会影响缓存性能，但不影响算法复杂度。你必须在考试伪代码中能追踪多维数组的访问。
| Operation | Static Array | Dynamic Array |
|---|---|---|
| Access by index | O(1) | O(1) |
| Insert/delete at end | N/A | amortised O(1) |
| Insert/delete at arbitrary position | O(n) | O(n) |
| Search (unsorted) | O(n) | O(n) |
3. Linked Lists: Singly and Doubly | 链表：单向与双向
A linked list consists of nodes where each node holds data and a reference (pointer) to the next node. A singly linked list only allows forward traversal; a doubly linked list also keeps a pointer to the previous node, enabling backward traversal and easier deletion. Head and tail pointers are often maintained for quick access to ends.
链表由节点组成，每个节点存储数据以及指向下一个节点的引用（指针）。单向链表只允许正向遍历；双向链表还保存指向前驱节点的指针，支持反向遍历且删除更容易。通常维护头指针和尾指针以便快速访问两端。
Because nodes are not stored contiguously, linked lists allow O(1) insertion and deletion at the head (and tail, with a tail pointer) once the target position is known. However, accessing an element by index requires traversing from the head, taking O(n) time. This contrasts sharply with arrays and is a favourite examiner question.
由于节点非连续存储，一旦知道目标位置，链表可以在头（以及尾，有尾指针时）实现 O(1) 插入和删除。但按索引访问需要从头遍历，需耗费 O(n) 时间。这与数组形成鲜明对比，是考官最喜欢提问的知识点。
Memory overhead is higher than arrays because each node stores one or two references. Despite this, linked lists are the foundation of many dynamic data structures, including stacks, queues, and adjacency list representations of graphs.
链表的内存开销高于数组，因为每个节点存储一或两个引用。尽管如此，链表仍是许多动态数据结构的基础，包括栈、队列以及图的邻接表表示。
4. Stacks: LIFO with Exam Tracing | 栈：后进先出与考试追踪
A stack is a linear ADT that follows Last In, First Out (LIFO) order. The essential operations are push (add to top) and pop (remove from top), with an optional peek to view the top element without removal. Stacks can be implemented using arrays or linked lists — both give O(1) push and pop when the top is tracked.
栈是一种遵循后进先出（LIFO）顺序的线性 ADT。基本操作是 push（添加到栈顶）和 pop（从栈顶移除），可选 peek 查看栈顶元素而不移除。栈可用数组或链表实现——只要跟踪栈顶，两者都能提供 O(1) 的 push 和 pop。
Exam questions frequently ask you to trace the state of a stack after a sequence of operations, or to use a stack to convert infix expressions to postfix, evaluate postfix expressions, or check balanced parentheses. You must confidently draw stack frames showing the content after each step.
考试题常要求你追踪一系列操作后栈的状态，或利用栈将中缀表达式转换为后缀、计算后缀表达式，或用栈检查括号匹配。你必须能自信地绘制栈帧，显示每一步后的内容。
Subroutine calls utilise a call stack to store return addresses and local variables. Understanding this mechanism is crucial for explaining recursion and handling stack overflow exceptions in recursive algorithms that exceed the available stack space.
子程序调用利用调用栈保存返回地址和局部变量。理解该机制对于解释递归以及处理递归算法超出可用栈空间导致的栈溢出异常至关重要。
5. Queues: Circular and Priority | 队列：循环和优先级
A queue is a First In, First Out (FIFO) ADT. It supports enqueue (add to rear) and dequeue (remove from front). Simple implementations with an array suffer from O(n) shifts unless circular buffer logic is employed, where front and rear pointers wrap around, maintaining O(1) enqueue and dequeue.
队列是一种先进先出（FIFO）的 ADT。它支持 enqueue（入列，添加到队尾）和 dequeue（出列，从队首移除）。若用数组简单实现，每次出列需 O(n) 的移动开销，除非采用循环缓冲区逻辑，让队首和队尾指针回绕，从而保持 O(1) 的入列和出列。
A priority queue extends the idea by associating a priority with each element. The highest-priority element is dequeued first, regardless of insertion order. Heaps are the standard underlying data structure because they provide O(log n) insertion and O(log n) removal of the highest-priority element.
优先队列通过为每个元素分配优先级来扩展这一理念。最高优先级的元素最先出列，不论插入顺序。堆是标准的底层数据结构，因为它们提供 O(log n) 的插入和 O(log n) 的最高优先级元素删除。
In exam scenarios, you might be given a sequence of enqueue and dequeue operations and asked to show the final queue state. For circular queues, you need to calculate pointer positions modulo the array size and recognise the condition for full and empty queues.
在考试场景中，你可能会拿到一系列入列出列操作，要求展示最终队列状态。对于循环队列，你需要计算指针位置取模数组大小，并识别队列满和空的判定条件。
6. Trees: Binary Trees and BSTs | 树：二叉树和二叉搜索树
A tree is a hierarchical ADT consisting of nodes connected by edges. A binary tree restricts each node to perform at most two children. Key terminology includes root, leaf, parent, child, depth, and height. Binary trees can be traversed in pre-order (root-left-right), in-order (left-root-right), and post-order (left-right-root).
树是由节点和边连接的层次化 ADT。二叉树限制每个节点至多有两个子节点。关键术语包括根、叶、父节点、子节点、深度和高度。二叉树可进行前序（根-左-右）、中序（左-根-右）和后序（左-右-根）遍历。
A Binary Search Tree (BST) adds the ordering property: for any node, all values in its left subtree are smaller and all values in its right subtree are larger (or equal on one side, depending on convention). This enables efficient search, insertion, and deletion with average-case complexity O(log n), though a degenerate (skewed) tree degrades to O(n).
二叉搜索树（BST）增加了排序性质：对任意节点，左子树所有值更小，右子树所有值更大（或根据约定一边可相等）。这使平均搜索、插入和删除复杂度为 O(log n)，但退化的（倾斜的）树会恶化到 O(n)。
AQA exams expect you to construct a BST from a given sequence, perform and identify traversal outputs, and explain how the structure of the tree affects performance. Self-balancing trees like AVL are mentioned conceptually, but the emphasis is on basic BST operations.
AQA 考试期望你根据给定序列构建 BST，执行并识别遍历输出，并解释树的结构如何影响性能。像 AVL 这样的自平衡树在概念上被提及，但重点放在基本 BST 操作上。
7. Graphs: Directed, Undirected and Weighted | 图：有向、无向和加权
A graph G = (V, E) consists of a set of vertices V and a set of edges E. Edges can be directed (ordered pairs) or undirected (unordered pairs). A weighted graph associates a numerical weight with each edge, used to model distances, costs, or capacities.
图 G = (V, E) 由顶点集 V 和边集 E 组成。边可以是有向的（有序对）或无向的（无序对）。加权图为每条边关联一个数值权重，用于建模距离、成本或容量。
Two common representations are the adjacency matrix and the adjacency list. An adjacency matrix is a 2D array where cell [i][j] stores 1 (or the weight) if an edge exists, yielding O(1) edge queries but O(|V|²) space. An adjacency list stores for each vertex a list of neighbouring vertices, saving space for sparse graphs and enabling efficient traversal.
两种常见表示是邻接矩阵和邻接表。邻接矩阵是二维数组，若存在边则单元格 [i][j] 存储 1（或权重），提供 O(1) 的边查询但 O(|V|²) 空间。邻接表为每个顶点存储一个邻居顶点列表，能节省稀疏图的空间并支持高效遍历。
You must be able to convert between representations, trace breadth-first search (BFS) using a queue and depth-first search (DFS) using a stack or recursion, and describe their applications, such as shortest path in unweighted graphs (BFS) or topological sorting (DFS).
你必须能在表示法之间转换，使用队列追踪广度优先搜索（BFS）和使用栈或递归追踪深度优先搜索（DFS），并描述其应用，例如无权图的最短路径（BFS）或拓扑排序（DFS）。
8. Hash Tables: Hashing and Collision Resolution | 哈希表：哈希与冲突解决
A hash table provides average O(1) insertion, deletion, and lookup by computing an index from a key using a hash function. A good hash function distributes keys uniformly across the table. Because collisions are inevitable when the array size is finite and smaller than the key domain, collision resolution strategies are essential.
哈希表用哈希函数根据键计算索引，提供平均 O(1) 的插入、删除和查找。好的哈希函数会将键均匀分布到表中。由于数组大小有限且小于键的值域，冲突不可避免，因此冲突解决策略至关重要。
The two main approaches are open addressing (linear probing, quadratic probing) where alternative slots are sought within the table, and separate chaining where each table slot points to a linked list (or bucket) of entries hashing to the same index. Each has implications for load factor, clustering, and worst-case complexity.
两大主要方法是开放定址法（线性探测、二次探测），即在表内寻找替代槽位；以及分离链接法，即每个表槽位指向一个链表（或桶），存放散列到同一索引的条目。每种方法对负载因子、聚集现象和最坏情况复杂度都有不同影响。
Examiners like to test tracing of linear probing with a given hash function, including what happens when the table fills up and the need for rehashing. You should also understand that the load factor (α = n / size) is critical: keeping α below 0.7 is typical for open addressing to maintain good performance.
考官喜欢测试给定哈希函数下线性探测的追踪过程，包括表满时发生的情况以及重哈希的必要性。你还应理解负载因子（α = n / 大小）是关键：对开放定址法，通常将 α 保持在 0.7 以下以维持良好性能。
9. Recursive Data Structures and Their Traversal | 递归数据结构及其遍历
Many ADTs are naturally recursive: a tree node contains references to child nodes, each of which is itself the root of a subtree; a linked list node points to the rest of the list. Traversal algorithms on these structures are elegantly expressed using recursion, with the base case often being a null node or empty list.
许多 ADT 天生是递归的：树节点包含子节点的引用，每个子节点本身又是一个子树的根；链表节点指向列表余下部分。这些结构的遍历算法用递归表达非常优雅，基线条件通常为遇到空节点或空列表。
When tracing recursive tree functions, draw the tree and mark the order of visits according to the recurrence. For example, a recursive function to compute the height of a binary tree can be defined as: height(node) = 1 + max(height(left), height(right)), with height(null) = -1 or 0 depending on convention.
在追踪递归树函数时，画出树并根据递推关系标记访问顺序。例如，计算二叉树高度的递归函数可定义为：height(node) = 1 + max(height(left), height(right))，height(null) 根据约定取 -1 或 0。
Recursion depth must not exceed the available call stack. Iterative equivalents using an explicit stack can avoid this limitation, which is an important consideration when processing large or unbalanced structures. You may be asked to convert a recursive algorithm into an iterative one.
递归深度不得超过可用的调用栈。使用显式栈的迭代等效算法可以避免这一限制，这是处理大型或不平衡结构时的重要考量。你可能会被要求将递归算法转换为迭代算法。
10. Choosing the Right Data Structure | 选择正确的数据结构
Selecting an appropriate data structure depends on the operations you need to support and their frequency. If random access and memory efficiency are paramount, arrays are unbeatable. When frequent insertion and deletion at arbitrary positions dominate, linked lists become attractive despite their memory overhead.
选择合适的数据结构取决于你需要支持的操作及其频率。若随机访问和内存效率至关重要，数组是无敌的。当频繁在任意位置插入和删除占主导时，链表尽管有内存开销但更具吸引力。
For order-sensitive processing, stacks (LIFO) and queues (FIFO) offer simple, fast interfaces. When hierarchical relationships must be modelled, trees are natural choices. For networks, routing, and social connections, graphs provide the most expressive model. The following table summarises common use cases and complexities across the main structures.
对于顺序敏感的处理，栈（LIFO）和队列（FIFO）提供了简单快速的接口。当必须建模层次关系时，树是自然选择。对于网络、路由和社交连接，图提供了最具表现力的模型。下表总结了主要结构的常见用例和复杂度。
| Data Structure | Access/Find | Insert (typical) | Delete (typical) | Key Usage |
|---|---|---|---|---|
| Array | O(1) by index | O(n) | O(n) | Look-up tables, matrices |
| Linked List | O(n) by index | O(1) at head | O(1) at head | Dynamic storage, queues implementation |
| Stack | O(n) search | O(1) push | O(1) pop | Undo, parentheses, recursion |
| Queue | O(n) search | O(1) enqueue | O(1) dequeue | Scheduling, BFS |
| Binary Search Tree | O(log n) avg | O(log n) avg | O(log n) avg | Sorted data, symbol tables |
| Hash Table | O(1) avg | O(1) avg | O(1) avg | Databases, caches, dictionaries |
Remember that degenerate cases (e.g., a skewed BST becoming a linked list, or a poorly hashed table with many collisions) can change these figures dramatically. Always mention the assumptions behind the average performance in exam explanations.
请记住，退化情况（例如倾斜 BST 变成链表，或哈希函数不佳导致大量冲突的哈希表）会显著改变这些数据。考试解释时一定要说明平均性能背后的假设。
11. Memory and Space Complexity Considerations | 内存与空间复杂度考量
Time complexity is not the only metric; space efficiency matters, especially in constrained environments. Arrays store the data compactly without per-element overhead, whereas linked lists need extra references. Hash tables typically allocate extra capacity to minimise collisions, creating a space–time trade-off.
时间复杂度并非唯一指标；空间效率同样重要，尤其是在资源受限的环境中。数组紧凑地存储数据，没有逐元素开销，而链表需要额外引用。哈希表为减少冲突通常会分配额外容量，形成空间-时间权衡。
Recursive algorithms consume stack space proportional to recursion depth, which can become problematic for deep trees or long lists. Iterative approaches using an explicit data structure can control memory usage more predictably. AQA questions may ask you to compare memory footprints of alternative implementations for the same ADT.
递归算法消耗的栈空间与递归深度成正比，对于深树或长链表会成为问题。使用显式数据结构的迭代方法可以更可控地管理内存。AQA 考题可能会要求你比较同一 ADT 不同实现的内存占用。
Always consider whether a structure is static (fixed size, allocated once) or dynamic (can grow). Over-provisioning a static array wastes space, while constant resizing of a dynamic array incurs a cumulative O(n) overhead that may be unacceptable in real-time systems.
务必考虑结构是静态（固定大小，一次性分配）还是动态（可增长）。静态数组超配会浪费空间，而动态数组不断调整大小会产生累计 O(n) 的开销，在实时系统中可能不可接受。
12. Typical Exam Questions and How to Approach Them | 典型考题及解题方法
1) Tracing: You are given a series of operations (push, pop, enqueue, dequeue, insert, delete) and an initial state. Draw each step. Always update pointers explicitly and annotate changes to avoid confusion, especially in linked lists and circular queues.
1) 追踪题：给出一系列操作（push、pop、enqueue、dequeue、insert、delete）和初始状态。画出每一步。务必显式更新指针并标注变化以避免混淆，尤其在链表和循环队列中。
2) Comparison: Discuss advantages and disadvantages of two structures for a given scenario. Use precise vocabulary (e.g., ‘contiguous memory’, ‘dynamic resizing’, ‘cache locality’) and cite complexity figures to support your argument.
2) 比较题：讨论在给定场景下两种结构的优缺点。使用精确术语（如“连续内存”、“动态调整大小”、“缓存局部性”），并引用复杂度数值来支持论点。
3) Implementation: Write pseudocode or code snippets for a specific operation on a given structure. Focus on edge cases: empty structure, single element, full structure. For BSTs, articulate the three deletion cases (leaf, one child, two children) clearly.
3) 实现题：编写给定结构上特定操作的伪代码或代码片段。关注边界情况：空结构、单元素、满结构。对于 BST，清晰阐述三种删除情况（叶节点、单子节点、双子节点）。
4) Diagram interpretation: Given a diagram showing nodes and pointers, determine the state after certain code runs. Regularly practice drawing linked structures by hand to build fluency.
4) 示意图解读：给出显示节点和指针的示意图，判断执行某段代码后的状态。定期手绘链式结构以培养熟练度。
A methodical, step-by-step approach is essential: read the question twice, identify the structure and its invariants, trace carefully, and review your answer against the expected constraints (e.g., no cycles in a tree, no overflowing array bounds).
有条理、逐步进行的解题方法至关重要：阅读问题两次，识别结构及其不变条件，仔细追踪，并根据预期约束（如树无环、不溢出数组边界）检查答案。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导