📚 Data Structures in WJEC A-Level Computer Science | 数据结构考点精讲
Data structures form the backbone of efficient algorithm design and are a core topic in the WJEC A-Level Computer Science specification. Understanding how data is organised, stored, and manipulated within a computer’s memory is essential for solving complex problems and scoring well on both theory and practical papers. This guide breaks down every structure you need to master, from simple arrays to graphs, with clear explanations and exam-focused insights.
数据结构是高效算法设计的基石，也是 WJEC 计算机科学 A-Level 考纲中的核心主题。理解数据在计算机内存中的组织、存储与操作方式，对于解决复杂问题以及在理论与实操试卷中取得高分至关重要。本篇指南将逐一拆解你需要掌握的每种结构，从简单的数组到图，提供清晰的解释和紧扣考试的解析。
1. Introduction to Data Structures | 数据结构简介
A data structure is a specialised format for organising, processing, retrieving and storing data. The WJEC syllabus expects you to know the difference between static and dynamic structures, linear and non-linear organisations, and how the choice of structure impacts memory usage and execution speed. In Component 1, you might be asked to justify your choice of a structure in a pseudocode solution; in Component 2, questions focus on theoretical behaviour and trade-offs.
数据结构是一种专门用于组织、处理、检索和存储数据的格式。WJEC 考纲要求你了解静态与动态结构、线性与非线性组织方式的区别，以及结构的选择如何影响内存使用和执行速度。在 Component 1 中，你可能需要为伪代码解决方案中的结构选择说明理由；在 Component 2 中，题目则侧重于理论行为与权衡。
2. Arrays: The Foundation of Data Storage | 数组：数据存储的基础
An array is a static, contiguous block of memory holding elements of the same data type. Each element is accessed via an index, which in most programming languages starts at 0. The key operations are traversal, insertion, deletion, and searching. Since an array’s size is fixed at creation, you must be able to explain how inefficient insertion and deletion can be — shifting elements in the worst case takes O(n) time. WJEC often asks you to write pseudocode that iterates over an array or implements a linear search.
数组是存储同类型元素的一块静态、连续的内存区域。每个元素通过索引访问，在大多数编程语言中索引从 0 开始。关键操作包括遍历、插入、删除和搜索。由于数组的大小在创建时便固定，你必须能够解释插入和删除为何可能低效 —— 最坏情况下移动元素需要 O(n) 时间。WJEC 经常要求你编写遍历数组或实现线性搜索的伪代码。
Static arrays offer O(1) read access, making them ideal for applications like lookup tables where the size is known in advance. Multidimensional arrays (2D arrays) are used to represent grids, matrices, and game boards. In an exam, always mention that going out of bounds results in a runtime error, and that dynamic arrays (such as those in Python lists under the hood) overcome the fixed-size limit but are not in the core WJEC pseudocode set.
静态数组提供 O(1) 的读取访问，这使它们非常适合预先知道大小的查找表等应用。多维数组（二维数组）用于表示网格、矩阵和游戏棋盘。在考试中，要始终提及越界会导致运行时错误，而动态数组（如 Python 列表底层使用的）克服了固定大小的限制，但它们不属于 WJEC 核心伪代码集合。
3. Linked Lists: Dynamic Memory Management | 链表：动态内存管理
A linked list consists of nodes, each containing data and a pointer (or reference) to the next node. Unlike arrays, linked lists are dynamic: nodes can be scattered in memory, and the list grows or shrinks by updating pointers. WJEC expects you to understand singly linked lists, doubly linked lists, and circular linked lists. You must be able to draw diagrams showing how pointers are updated during insertion and deletion — a frequent exam task.
链表由节点组成，每个节点包含数据和指向下一个节点的指针（或引用）。与数组不同，链表是动态的：节点在内存中可以分散存储，列表通过更新指针来增长或缩小。WJEC 希望你理解单向链表、双向链表和循环链表。你必须能够绘制图示，展示插入和删除过程中指针如何更新 —— 这是一项常见的考试任务。
Insertion at the head is O(1) because no traversal is needed; insertion at the tail or in the middle requires traversing to the point of insertion, giving O(n). Doubly linked lists allow backward traversal at the cost of an extra pointer per node. The WJEC mark scheme rewards precise terminology: ‘start pointer’, ‘next pointer’ and ‘null pointer’. Avoid confusing a linked list’s pointer-based traversal with array indexing — access is sequential, not random.
在头部插入是 O(1)，因为无需遍历；在尾部或中间插入则需要遍历到插入点，因此为 O(n)。双向链表允许反向遍历，代价是每个节点多出一个指针。WJEC 的评分方案奖励准确的术语：’start pointer’、’next pointer’ 和 ‘null pointer’。要避免将链表的指针遍历与数组索引混淆 —— 访问是顺序的，而非随机的。
4. Stacks: LIFO and Its Applications | 栈：LIFO 及其应用
A stack is a linear data structure that follows Last In, First Out (LIFO) discipline. Elements are added (pushed) and removed (popped) from the same end, called the top. The WJEC syllabus wants you to implement a stack using either an array and a top-of-stack pointer or a linked list. You must know the operations push, pop, peek (or top), and isEmpty, and be able to trace their effect on memory.
栈是一种遵循后进先出（LIFO）规则的线性数据结构。元素从同一端（称为栈顶）添加（压入）和移除（弹出）。WJEC 考纲要求你能够使用数组加栈顶指针或链表来实现栈。你必须知道 push、pop、peek（或 top）和 isEmpty 操作，并且能够追踪它们对内存的影响。
Stacks are indispensable in recursion, expression evaluation (infix to postfix conversion), undo mechanisms, and backtracking algorithms such as depth-first search. In Component 2, you may be given a sequence of push and pop instructions and asked to show the stack contents after each step. Watch out for stack overflow (when pushing onto a full static stack) and stack underflow (popping from an empty stack) — both are common pitfalls that WJEC examiners test.
栈在递归、表达式求值（中缀转后缀）、撤销机制以及深度优先搜索等回溯算法中不可或缺。在 Component 2 中，你可能会得到一系列 push 和 pop 指令，并被要求展示每一步后的栈内容。要留意栈溢出（向已满的静态栈压入）和栈下溢（从空栈中弹出）—— 两者都是 WJEC 考官常考的常见陷阱。
5. Queues: FIFO and Variants | 队列：FIFO 及其变体
A queue implements First In, First Out (FIFO) behaviour. Elements enter at the rear and leave from the front. You must be able to describe linear queues, circular queues (which reuse spaces in a static array), and priority queues where elements are dequeued based on priority rather than arrival order. WJEC often asks you to compare a linear queue with a circular queue in terms of memory utilisation.
队列实现先进先出（FIFO）行为。元素从队尾进入，从队首离开。你必须能够描述线性队列、循环队列（在静态数组中复用空间）以及优先级队列（元素根据优先级而非到达顺序出队）。WJEC 经常要求你比较线性队列与循环队列在内存利用率上的差异。
A circular queue uses a fixed-size array and two pointers, front and rear, that wrap around when they reach the end. This avoids the ‘drifting’ problem where the queue appears full even when spaces at the front are free. In pseudocode, you need to handle the condition (rear + 1) mod size = front to detect a full queue. Exam questions often ask for a trace table showing how front and rear update through enqueue and dequeue operations.
循环队列使用固定大小的数组和两个指针（front 和 rear），当它们到达末端时会回绕。这避免了即使队首有空位队列也显得已满的“漂移”问题。在伪代码中，你需要处理条件 (rear + 1) mod size = front 来检测满队列。考题常常要求提供一个跟踪表，展示 enqueue 和 dequeue 操作过程中 front 和 rear 是如何更新的。
6. Trees: Hierarchical Organisation | 树：层次式组织
Trees are non-linear structures consisting of nodes connected by edges, with a root node and child nodes forming a hierarchy. The WJEC specification focuses on binary trees, where each node has at most two children (left and right), and their special case: binary search trees (BSTs). In a BST, the left subtree contains values less than the parent, and the right subtree contains values greater — a property that allows efficient searching in O(log n) on average.
树是由节点和边组成的非线性结构，具有根节点和子节点，形成层次。WJEC 考纲重点关注二叉树（每个节点至多有两个子节点：左和右）及其特例：二叉搜索树（BST）。在 BST 中，左子树包含小于父节点的值，右子树包含大于父节点的值 —— 这一性质使得平均搜索效率达到 O(log n)。
You must be able to perform and trace tree traversals: pre-order (root, left, right), in-order (left, root, right), and post-order (left, right, root). In-order traversal of a BST yields the values in ascending order. WJEC questions may provide a tree diagram and ask for the output sequence of a given traversal, or ask you to construct a BST from a list of numbers and state the first three values visited in pre-order. Practice drawing the tree step by step.
你必须能够执行并追踪树的遍历：前序（根、左、右）、中序（左、根、右）和后序（左、右、根）。对 BST 的中序遍历会按键值升序产生值序列。WJEC 的题目可能提供一棵树的图示，要求写出特定遍历的输出序列，或者要求你从一列数字构建 BST，并说明前序遍历访问的前三个值。要多练习逐步画出树的过程。
7. Graphs: Modelling Complex Relationships | 图：建模复杂关系
A graph consists of vertices (nodes) and edges that connect them. Graphs can be directed or undirected, weighted or unweighted. Representation methods — adjacency matrix and adjacency list — are explicitly examined. An adjacency matrix is a 2D array where cell [i][j] stores the weight or a 1/0 indicator; an adjacency list uses an array of linked lists (or dynamic lists). You must compare their space complexity: O(V²) versus O(V+E).
图由顶点（节点）和连接它们的边组成。图可以是有向或无向的，加权或非加权的。表示方法 —— 邻接矩阵和邻接表 —— 是明确的考点。邻接矩阵是一个二维数组，其中单元格 [i][j] 存储权重或 1/0 指示符；邻接表使用一个由链表（或动态列表）构成的数组。你必须比较它们的空间复杂度：O(V²) 与 O(V+E)。
WJEC expects familiarity with basic graph traversals: depth-first search (DFS) using a stack, and breadth-first search (BFS) using a queue. While you won’t be asked to code full Dijkstra’s algorithm from scratch, you may be given a graph and required to manually apply Dijkstra to find the shortest path, filling in a table of distances and previous vertices. Always show your working clearly in the answer booklet.
WJEC 期望你熟悉基本的图遍历：使用栈的深度优先搜索（DFS）和使用队列的广度优先搜索（BFS）。虽然不会要求你从零开始编写完整的迪杰斯特拉算法，但可能会给你一个图，要求你手动应用迪杰斯特拉算法寻找最短路径，并填写距离和前驱顶点表。要在答题册上清晰地展示每一步过程。
8. Hash Tables: Constant-Time Lookup | 哈希表：常量时间查找
A hash table uses a hash function to map a key to an index in an array, aiming for O(1) average time for insertion, deletion, and search. The WJEC syllabus requires you to understand how collisions occur (when two keys hash to the same index) and the two main resolution strategies: open addressing (linear probing) and closed addressing (chaining with linked lists). You must be able to insert a series of keys into a table and show the final state.
哈希表使用哈希函数将键映射到数组中的索引，旨在实现平均 O(1) 的插入、删除和搜索时间。WJEC 考纲要求你理解冲突是如何发生的（当两个键哈希到相同的索引时）以及两种主要的解决策略：开放寻址（线性探测）和封闭寻址（使用链表的链地址法）。你必须能够将一系列键插入表中并展示最终状态。
Linear probing searches sequentially for the next empty slot, which can lead to primary clustering. Chaining avoids clustering but uses extra memory for pointers. WJEC questions may ask you to calculate the load factor (number of items / table size) and explain its impact on performance. A high load factor degrades performance, typically triggering a rehash with a larger array. Using a good hash function that distributes keys uniformly is crucial.
线性探测顺序搜索下一个空槽，这可能导致一次聚集。链地址法避免了聚集，但会为指针使用额外内存。WJEC 的题目可能要求你计算负载因子（元素数量 / 表大小）并解释其对性能的影响。高负载因子会降低性能，通常会触发使用更大数组的再哈希。使用能均匀分布键的优秀哈希函数至关重要。
9. Choosing and Comparing Data Structures | 数据结构的选择与比较
Every WJEC data structure question implicitly tests your ability to select the right tool for the job. Consider these trade-offs: static arrays offer speed but inflexibility; linked lists allow easy insertion/deletion but waste memory on pointers and have no random access. Stacks and queues are constrained interfaces that simplify control flow. Trees enable hierarchical searches, while graphs handle interconnected data. Hash tables are unbeatable for key-value lookups when collisions are managed.
每一道 WJEC 数据结构题都隐含地考察你为任务选择合适工具的能力。考虑如下权衡：静态数组提供速度但缺乏灵活性；链表允许轻松插入/删除，但浪费在指针上的内存且不支持随机访问。栈和队列是受约束的接口，能简化控制流。树支持层次化搜索，而图处理相互连接的数据。哈希表在冲突得到管理时，是键值查找的无敌之选。
A common exam prompt gives a scenario — for example, a printer spooler or a web browser’s back button — and asks you to name and justify the data structure. Practise these: printer queue (queue, FIFO), back button (stack, LIFO), a music playlist (array or linked list), and a telephone directory (hash table or sorted array for binary search). Always link the structure’s properties to the real-world requirement.
一种常见考题是给出一个场景 —— 例如，打印机后台处理程序或网页浏览器的后退按钮 —— 然后要求你命名数据结构并说明理由。多练习这些场景：打印队列（队列，FIFO），后退按钮（栈，LIFO），音乐播放列表（数组或链表），以及电话簿（哈希表或用于二分查找的已排序数组）。要始终将结构的特性与现实需求联系起来。
10. Exam Technique and Common Pitfalls | 考试技巧与常见错误
The WJEC Data Structures topic appears in both Component 1 (programming/pseudocode) and Component 2 (theory). In Component 1, you may need to write pseudocode to manipulate an array of records or traverse a binary tree. Use consistent syntax from the WJEC pseudocode guide: meaningful variable names, indentation, and explicit loop conditions. Do not use programming language-specific features like Python’s append() unless you translate them into equivalent pseudocode steps.
WJEC 数据结构主题出现在 Component 1（编程/伪代码）和 Component 2（理论）中。在 Component 1 中，你可能需要编写伪代码来操作一个记录数组或遍历二叉树。要使用 WJEC 伪代码指南中一致的语法：有意义的变量名、缩进以及明确的循环条件。除非将 Python 的 append() 这类编程语言特有功能转写为等效的伪代码步骤，否则不要使用它们。
When answering long-form questions, keywords are everything. Use phrases like ‘dynamic memory allocation’ for linked lists, ‘contiguous memory’ for arrays, and ‘pointer dereferencing’ when describing traversal. In traces, neatly draw updated diagrams or tables. If asked to analyse time complexity, state the condition (worst-case, average) and give the Big O notation: O(1), O(log n), O(n), O(n²). Never leave a comparison question without discussing space complexity as well.
在回答长篇问题时，关键词就是一切。对链表使用“动态内存分配”，对数组使用“连续内存”，在描述遍历时使用“指针解引用”。在进行跟踪时，要整洁地画出更新后的示意图或表格。如果要求分析时间复杂度，要说明条件（最坏情况、平均情况）并给出大 O 表示法：O(1)、O(log n)、O(n)、O(n²)。在回答比较题时，决不能不讨论空间复杂度。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导