📚 IB & WJEC Computer Science: Data Structures Key Concepts | IB WJEC 计算机：数据结构 考点精讲
Understanding data structures is fundamental to mastering algorithm design and computational thinking in both IB Computer Science and WJEC A-level specifications. This guide breaks down every essential structure you need to know, focusing on how they store, organise and manipulate data efficiently. We cover arrays, linked lists, stacks, queues, trees, graphs and hash tables, with clear comparisons, real-world analogies and Big O performance analysis. Whether you are tackling Paper 2 for IB or Unit 1/2 for WJEC, these revision points will sharpen your exam technique.
掌握数据结构是精通 IB 计算机科学和 WJEC A-level 课程中算法设计与计算思维的基础。本指南详细分解了你需要了解的每一种核心结构，重点说明它们如何高效地存储、组织与操作数据。我们涵盖数组、链表、栈、队列、树、图和哈希表，并配有清晰的对比、现实世界的类比以及大 O 性能分析。无论你正在备战 IB 的 Paper 2 还是 WJEC 的 Unit 1/2，这些复习要点都将提升你的考试技巧。
1. Overview of Data Structures | 数据结构概述
A data structure is a specialized format for organising, processing and storing data that enables efficient access and modification. The choice of data structure directly impacts the complexity and performance of algorithms. Key characteristics include whether the structure is linear or hierarchical, static or dynamic in size, and whether memory is allocated contiguously or via pointers. Both IB and WJEC syllabi expect you to evaluate trade-offs such as memory overhead, insertion/deletion speed and search efficiency.
数据结构是一种用于组织、处理与存储数据的专用格式，能够实现高效的访问和修改。数据结构的选择直接影响算法的复杂度和性能。关键特征包括该结构是线性的还是分层的、大小是静态的还是动态的，以及内存是连续分配还是通过指针链接。IB 和 WJEC 教学大纲都要求你评估内存开销、插入/删除速度、搜索效率之间的权衡。
- Linear structures: arrays, linked lists, stacks, queues
- Hierarchical structures: trees, binary search trees, heaps
- Network structures: graphs
- Key-based structures: hash tables
- 线性结构：数组、链表、栈、队列
- 分层结构：树、二叉搜索树、堆
- 网络结构：图
- 基于键的结构：哈希表
2. Arrays | 数组
An array is a contiguous block of memory that stores elements of the same data type, identified by an index. Access is random and extremely fast, with time complexity O(1) for reading or writing by index. However, insertion and deletion are expensive because elements may need to be shifted, giving O(n) in the worst case. Arrays can be static (fixed size) or dynamic (resizable, like lists in Python/Java). In IB and WJEC exams, you must be able to trace array operations, calculate memory addresses using base address + index × element size, and apply arrays in sorting and searching algorithms.
数组是一块连续的内存区域，存储相同数据类型的元素，通过索引识别。访问是随机且极其快速的，按索引读取或写入的时间复杂度为 O(1)。然而，插入和删除操作代价很高，因为元素可能需要移位，最坏情况为 O(n)。数组可以是静态的（固定大小）或动态的（可调整大小，如 Python/Java 中的列表）。在 IB 和 WJEC 考试中，你必须能够跟踪数组操作、使用基地址 + 索引 × 元素大小计算内存地址，并将数组应用于排序和搜索算法。
Address of A[i] = base + i × size
数组元素 A[i] 地址 = 基地址 + i × 元素大小
3. Linked Lists | 链表
A linked list is a dynamic data structure consisting of nodes, where each node contains data and a pointer to the next node. There are singly linked lists, doubly linked lists and circular linked lists. The key advantage over arrays is efficient insertion and deletion at any position (once the node before is located), typically O(1) for the pointer rearrangement, but finding the position requires O(n) traversal. Memory allocation is non-contiguous, avoiding the need for large contiguous blocks but introducing overhead for storing pointers. You must be able to draw node diagrams, implement traversal, insert/delete algorithms and discuss the use of a head pointer and (for doubly linked) previous pointers.
链表是一种由节点组成的动态数据结构，每个节点包含数据和指向下一节点的指针。链表有单向链表、双向链表和循环链表。与数组相比，主要优势在于任何位置的插入和删除效率高（一旦找到前驱节点），通常指针重排为 O(1)，但需要 O(n) 遍历找到位置。内存分配不连续，避免了对大块连续内存的需求，但引入了存储指针的开销。你必须能够绘制节点图、实现遍历、插入/删除算法，并讨论头指针以及双向链表中前驱指针的用法。
Singly linked node: [ data | next ] → [ data | next ] → null
单向链表节点：[ 数据 | 下一节点 ] → [ 数据 | 下一节点 ] → 空
4. Stacks | 栈
A stack is a Last-In-First-Out (LIFO) linear structure where elements are added and removed only from the top. Essential operations are push (add), pop (remove) and peek (inspect top without removal). Stacks can be implemented using arrays or linked lists; array-based stacks need a top pointer and a maximum capacity, while linked-list-based stacks grow dynamically. Stacks are fundamental for function call management (call stack), expression evaluation (postfix notation), backtracking (e.g., maze solving) and undo mechanisms. Both IB and WJEC papers often ask you to trace a stack’s content after a sequence of pushes and pops, or to use a stack to reverse a string or check balanced parentheses.
栈是一种后进先出（LIFO）的线性结构，元素仅在栈顶添加和移除。基本操作包括 push（入栈）、pop（出栈）和 peek（查看栈顶而不移除）。栈可以用数组或链表实现；基于数组的栈需要一个栈顶指针和最大容量，而基于链表的栈可以动态增长。栈是函数调用管理（调用栈）、表达式求值（后缀表示法）、回溯（例如迷宫求解）和撤销机制的基础。IB 和 WJEC 试卷经常让你跟踪一系列 push 和 pop 操作后栈的内容，或使用栈来反转字符串、检查括号匹配。
| Operation | Array Implementation | Linked List Implementation |
|---|---|---|
| push | top++; arr[top]=item | new node pointed by top |
| pop | return arr[top]; top– | temp=top; top=top.next; return temp.data |
| 操作 | 数组实现 | 链表实现 |
|---|---|---|
| 入栈 push | top++；arr[top]=元素 | 新节点由 top 指向 |
| 出栈 pop | 返回 arr[top]；top– | temp=top; top=top.next; 返回 temp.data |
5. Queues | 队列
A queue is a First-In-First-Out (FIFO) structure where elements are added at the rear and removed from the front. Standard operations are enqueue (add to rear) and dequeue (remove from front). Linear queues suffer from the problem of unusable empty spaces after dequeuing; this is solved by circular queues that wrap the rear pointer around. Priority queues dequeue elements based on priority rather than arrival order, often implemented using heaps. Exam questions frequently require you to simulate a circular queue using an array with front and rear pointers, compute (rear+1) % max for enqueue and (front+1) % max for dequeue, and recognise applications like print spooling, keyboard buffers and simulation of waiting lines.
队列是一种先进先出（FIFO）结构，元素在队尾添加，在队首移除。标准操作包括 enqueue（入队）和 dequeue（出队）。线性队列在出队后会出现不可用的空位问题；循环队列通过让队尾指针回绕来解决。优先队列根据优先级而非到达顺序让元素出队，通常用堆实现。考试题目经常要求你模拟一个使用数组实现的循环队列，维护 front 和 rear 指针，入队时计算 (rear+1) % max，出队时计算 (front+1) % max，并识别如打印池、键盘缓冲区和排队模拟等应用。
Circular queue empty condition: front = rear
Circular queue full condition: (rear + 1) % max = front
循环队列空条件：front = rear
循环队列满条件：(rear + 1) % max = front
6. Trees | 树
A tree is a hierarchical, non-linear data structure consisting of nodes connected by edges, with a single root node. Each node can have child nodes; nodes with no children are leaves. Binary trees restrict each node to at most two children (left and right). Complete binary trees fill all levels except possibly the last, which is filled left to right. Tree traversal methods are crucial for exams: pre-order (root, left, right), in-order (left, root, right) and post-order (left, right, root). You must be able to construct a binary tree from given traversal sequences and write recursive traversal algorithms. Understanding tree terminology – depth, height, subtree, ancestor, descendant – is fundamental for WJEC and IB.
树是一种分层的非线性数据结构，由节点和边组成，具有唯一的根节点。每个节点可以有子节点；没有子节点的节点称为叶节点。二叉树限制每个节点最多有两个子节点（左子节点和右子节点）。完全二叉树除了最后一层外每一层都是满的，且最后一层从左向右填充。树的遍历方法是考试的关键：前序（根、左、右）、中序（左、根、右）和后序（左、右、根）。你必须能够根据给定的遍历序列构建二叉树，并编写递归遍历算法。理解树的术语——深度、高度、子树、祖先、后代——是 WJEC 和 IB 的基础。
Example: For expression (A+B)×C, the tree yields post-order A B + C × for evaluation using a stack.
示例：对于表达式 (A+B)×C，该树产生后序 A B + C ×，可用于栈求值。
7. Binary Search Trees (BST) | 二叉搜索树
A binary search tree enforces a property: for each node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater. This ordering allows efficient search, insertion and deletion, with average time complexity O(log n) for balanced trees but degrading to O(n) in the worst case (skewed tree). BST operations are central to IB Paper 2 and WJEC data structure questions. You must be able to describe recursive algorithms for search (compare and branch left/right), insertion (traverse to empty leaf position) and deletion (three cases: leaf node, node with one child, node with two children – replace with in-order successor).
二叉搜索树强制维护一个性质：对于每个节点，左子树中所有值小于该节点的值，右子树中所有值大于该节点的值。这种顺序使得搜索、插入和删除高效，平衡树的平均时间复杂度为 O(log n)，但最坏情况（偏斜树）下退化至 O(n)。BST 操作是 IB Paper 2 和 WJEC 数据结构问题的核心。你必须能够描述递归算法：搜索（比较并左/右分支）、插入（遍历到空叶位置）和删除（三种情况：叶节点、有一个子节点的节点、有两个子节点的节点——用中序后继替代）。
Key worst-case time: O(n), average O(log n)
关键最差时间：O(n)，平均 O(log n)
8. Graphs | 图
A graph consists of vertices (nodes) and edges that connect pairs of vertices, possibly directed or weighted. Graphs can be represented using an adjacency matrix (2D array) or adjacency list (array of linked lists). The matrix is O(V²) space, efficient for dense graphs and O(1) edge checking; the list uses O(V+E) space, better for sparse graphs. Traversal algorithms depth-first search (DFS) uses a stack (explicit or recursion) and breadth-first search (BFS) uses a queue. WJEC often asks for simulations of these traversals; IB expects understanding of minimum spanning tree (Prim’s and Kruskal’s) and shortest path (Dijkstra’s) at HL. You need to be able to explain applications like networking, social graphs and web crawling.
图由顶点（节点）和连接顶点对的边组成，边可能是有向的或带权重的。图可以用邻接矩阵（二维数组）或邻接表（链表数组）表示。矩阵的空间复杂度为 O(V²)，适合稠密图，边查询为 O(1)；邻接表使用 O(V+E) 空间，更适合稀疏图。遍历算法中，深度优先搜索（DFS）使用栈（显式或递归），广度优先搜索（BFS）使用队列。WJEC 常要求模拟这些遍历；IB 期望 HL 理解最小生成树（Prim 和 Kruskal）和最短路径（Dijkstra）算法。你需要能解释网络、社交图谱和网页爬虫等应用。
| Representation | Space | Edge query | Add edge |
|---|---|---|---|
| Adjacency Matrix | O(V²) | O(1) | O(1) |
| Adjacency List | O(V+E) | O(degree(v)) | O(1) at head |
| 表示方法 | 空间 | 边查询 | 添加边 |
|---|---|---|---|
| 邻接矩阵 | O(V²) | O(1) | O(1) |
| 邻接表 | O(V+E) | O(degree(v)) | O(1) 头部 |
9. Hash Tables | 哈希表
A hash table maps keys to array indices using a hash function, aiming for O(1) average-case insertion, deletion and lookup. The core challenge is handling collisions, where two keys map to the same index. Common collision resolution techniques include separate chaining (each bucket holds a linked list of entries) and open addressing (linear probing, quadratic probing). The load factor (number of entries / table size) influences performance; when it exceeds a threshold, rehashing (resizing the table) is needed. Both IB and WJEC require you to explain how hashing works, trace simple hash functions (e.g., sum of ASCII values mod table size) and evaluate efficiency under different loads.
哈希表使用哈希函数将键映射为数组索引，旨在实现平均 O(1) 的插入、删除和查找。核心挑战是处理冲突，即两个键映射到同一索引。常见的冲突解决技术包括分离链接法（每个桶存储一个链表）和开放定址法（线性探测、二次探测）。负载因子（条目数 / 表大小）影响性能；当超过阈值时，需要重新哈希（调整表大小）。IB 和 WJEC 都要求你解释哈希的工作原理，跟踪简单的哈希函数（例如，ASCII 值之和 mod 表大小），并评估不同负载下的效率。
Example: keys “A”, “B”, “C” with hash(key) = (ASCII sum) mod 5. For “A”=65 mod 5 = 0.
示例：键 “A”、”B”、”C”，哈希函数 hash(key) = (ASCII 和) mod 5。如 “A”=65 mod 5 = 0。
10. Choosing Data Structures and Efficiency Comparison | 数据结构选择与效率对比
Selecting the right data structure depends on the operations you need to optimise. For frequent random access, arrays are unbeatable. For many insertions/deletions with sequential access, linked lists shine. Stacks and queues are ideal for LIFO/FIFO order processing. Trees (especially balanced BSTs) offer logarithmic search, while graphs model complex relationships. Hash tables deliver near-constant time for key-based operations but use more memory and have no order. In exams, you must justify your choice by stating time complexities and practical constraints, such as memory limits or dynamic resizing needs. The table below summarises common structures.
选择合适的结构取决于你希望优化的操作。对于频繁的随机访问，数组无可匹敌。对于许多顺序访问的插入/删除，链表表现出色。栈和队列非常适合 LIFO/FIFO 顺序处理。树（尤其是平衡 BST）提供对数搜索，而图能模拟复杂关系。哈希表在基于键的操作上提供近乎常数时间，但占用更多内存且无序。在考试中，你必须通过陈述时间复杂度和实际约束（如内存限制或动态调整大小需求）来证明你的选择。下表总结了常见结构。
| Structure | Search | Insert | Delete | Random Access |
|---|---|---|---|---|
| Array | O(1) by index, O(n) by value | O(n) | O(n) | O(1) |
| Linked List | O(n) | O(1) at head | O(1) at head | O(n) |
| Stack/Queue | O(n) search not primary | O(1) | O(1) | N/A |
| BST (balanced) | O(log n) | O(log n) | O(log n) | N/A |
| Hash Table | O(1) avg | O(1) avg | O(1) avg | N/A |
| 结构 | 搜索 | 插入 | 删除 | 随机访问 |
|---|---|---|---|---|
| 数组 | 按索引 O(1)，按值 O(n) | O(n) | O(n) | O(1) |
| 链表 | O(n) | 头部 O(1) | 头部 O(1) | O(n) |
| 栈/队列 | O(n) 非主要 | O(1) | O(1) | 不适用 |
| BST（平衡） | O(log n) | O(log n) | O(log n) | 不适用 |
| 哈希表 | O(1) 平均 | O(1) 平均 | O(1) 平均 | 不适用 |
11. Abstract Data Types (ADT) View | 抽象数据类型视角
An abstract data type defines a set of operations without specifying implementation details. For example, a list ADT supports add, remove, get, size; it can be implemented with arrays or linked lists. Similarly, stacks, queues and dictionaries (maps) are ADTs. Both IB and WJEC emphasise the distinction between logical behaviour and physical implementation. Exam questions may ask you to justify why a particular ADT should be chosen for a scenario (e.g., a dictionary for fast lookups) and then to outline how it could be implemented. Understanding ADTs helps you separate interface from implementation, a key concept in software development.
抽象数据类型定义了一组操作，而不指定实现细节。例如，列表 ADT 支持添加、删除、获取、大小等操作；可以用数组或链表实现。同样，栈、队列和字典（映射）都是 ADT。IB 和 WJEC 都强调区分逻辑行为与物理实现。考题可能会让你解释为何选择某个 ADT 用于特定场景（如使用字典进行快速查找），然后概述其实现方式。理解 ADT 有助于将接口与实现分离，这是软件开发中的关键概念。
12. Exam Tips and Common Pitfalls | 考试技巧与常见误区
Always draw diagrams when tracing tree traversals, linked list changes or stack/queue states – marks are often allocated for clear visualisation. Label pointers clearly (head, tail, top, front, rear). For algorithm writing, use appropriate pseudocode that matches the specification; IB prefers clear structural steps, WJEC also values correct use of loop conditions. Watch out for off-by-one errors in array indexing and forgetting to update size after insertion/deletion. When discussing efficiency, always mention both time and space complexities, and be prepared to explain best, worst and average cases. If you are given a scenario, evaluate the data structure under realistic constraints like memory or need for order.
在跟踪树的遍历、链表的变化或栈/队列状态时，一定要画图——清晰的图示往往能得分。清楚地标出指针（head, tail, top, front, rear）。编写算法时，使用与考纲要求相符的伪代码；IB 偏好清晰的结构化步骤，WJEC 也重视正确使用循环条件。警惕数组索引中的“off-by-one”错误，以及插入/删除后忘记更新大小。讨论效率时，要提到时间和空间复杂度，并准备好解释最好、最坏和平均情况。如果给出一个场景，要在实际约束下（如内存或顺序需求）评估数据结构。
Master these concepts through consistent practice, and you will be well-prepared to tackle any data structure question on the IB or WJEC computer science exam.
通过持续练习掌握这些概念，你将做好充分准备，应对 IB 或 WJEC 计算机科学考试中的任何数据结构问题。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply