GCSE CCEA Computer Science: Data Structures Key Points Review | GCSE CCEA 计算机：数据结构考点精讲

📚 GCSE CCEA Computer Science: Data Structures Key Points Review | GCSE CCEA 计算机：数据结构考点精讲

Data structures are fundamental building blocks in computer science, allowing programmers to organise, manage, and store data efficiently. For CCEA GCSE Computer Science, understanding how and when to use different data structures is essential for tackling both theory questions and practical programming tasks. This guide will walk you through the core data structures you need to know: arrays, lists, stacks, queues, trees, graphs, and hash tables. Each concept is explained with clear English and Chinese explanations, along with tips for the exam.

数据结构是计算机科学的基本组成部分，它使程序员能够高效地组织、管理和存储数据。在 CCEA GCSE 计算机科学考试中，理解如何以及何时使用不同的数据结构，对于应对理论题和实践编程任务都至关重要。本指南将带你梳理需要掌握的核心数据结构：数组、列表、栈、队列、树、图以及哈希表。每个概念都配有清晰的英文和中文解释，并提供备考建议。

1. What Are Data Structures? | 什么是数据结构？

A data structure is a specialised format for organising, processing, and storing data so that it can be accessed and modified efficiently. Choosing the right data structure can make your program faster and simpler. At GCSE level, you are expected to recognise common data structures and understand their strengths and weaknesses.

数据结构是一种用于组织、处理和存储数据的专用格式，以便能够高效地访问和修改数据。选择合适的数据结构可以使你的程序更快、更简单。在 GCSE 级别，你应当能够识别常见的数据结构，并理解它们的优缺点。

Think of a data structure like a container in real life: an array is like a row of numbered lockers, a stack is like a pile of plates, and a queue is like a line at a shop. Each container has rules for adding and removing items, and those rules affect performance.

可以把数据结构想象成现实生活中的容器：数组就像一排编号的储物柜，栈就像一摞盘子，队列就像商店里的排队。每个容器都有添加和移除元素的规则，这些规则会影响性能。

2. Arrays | 数组

An array is a collection of elements, each identified by an index or a key. Arrays store items of the same data type in contiguous memory locations. In most programming languages, the index starts at 0, so an array with 5 elements has indices 0 to 4.

数组是一组元素的集合，每个元素通过一个索引或键来标识。数组将相同数据类型的元素存储在连续的内存位置中。在大多数编程语言中，索引从 0 开始，因此包含 5 个元素的数组，其索引范围是 0 到 4。

Key characteristics:

Fixed size (in static arrays) – the size must be declared in advance.
Direct access – you can instantly read or write any element using its index (O(1) time complexity).
Cache-friendly – because elements are stored together, arrays can be faster for sequential processing.

主要特征：

固定大小（静态数组）—— 必须在声明时指定大小。
直接访问 —— 可以使用索引迅速读取或写入任何元素（时间复杂度为 O(1)）。
缓存友好 —— 由于元素连续存放，数组在顺序处理时速度更快。

However, inserting or deleting an element in the middle requires shifting elements, which is slow (O(n)). You will often see arrays used to store lists of student marks, temperatures, or character grids in exam questions.

然而，在数组中间插入或删除元素需要移动后续元素，速度较慢（时间复杂度为 O(n)）。在考试题目中，你经常会看到数组用于存储学生成绩列表、温度数据或字符网格。

3. Lists (Dynamic Arrays / Linked Lists) | 列表（动态数组 / 链表）

CCEA distinguishes between static data structures and dynamic data structures. A list often refers to a dynamic array (like Python’s list) that can grow and shrink automatically, or a linked list where nodes are connected by pointers.

CCEA 课程区分了静态数据结构和动态数据结构。列表通常指可以自动扩缩容的动态数组（如 Python 的列表），或者通过指针连接的节点的链表。

Dynamic array: when the array becomes full, a larger block of memory is allocated, and existing elements are copied over. This gives flexibility at the cost of occasional resizing overhead.

动态数组： 当数组填满时，系统会分配一块更大的内存空间，并将原有元素复制过去。这种方式提供了灵活性，但偶尔会因扩容而带来额外开销。

Linked list: each node contains data and a pointer to the next node. Insertion and deletion are efficient because only the pointers need to change, but you cannot directly access an element by index – you must start from the head and follow the pointers (O(n)).

链表： 每个节点包含数据和指向下一个节点的指针。插入和删除操作效率很高，因为只需修改指针；但你无法通过索引直接访问元素，必须从头节点开始沿着指针逐个查找（时间复杂度为 O(n)）。

For the exam, be able to compare arrays and linked lists in terms of memory usage, speed of access, insertion, and deletion. Remember that a list can be implemented using either an array or a linked structure.

在考试中，要能够比较数组和链表在内存使用、访问速度、插入和删除方面的差异。要记住，列表既可以用数组实现，也可以用链式结构实现。

4. Stacks (LIFO) | 栈（后进先出）

A stack is a Last-In, First-Out (LIFO) structure. You can only add (push) or remove (pop) an item from the top. Think of a stack of plates: you can only take the plate from the top, and you can only add a new plate to the top.

栈是一种后进先出（LIFO）的数据结构。你只能在顶部添加（压栈）或移除（弹栈）元素。想象一摞盘子：你只能从最上面拿取盘子，也只能把新盘子放在最上面。

Common operations:

push(item) – adds an item to the top.
pop() – removes and returns the item at the top.
peek() or top() – returns the top item without removing it.
isEmpty() – checks if the stack is empty.

常见操作：

push(item) —— 将元素添加到栈顶。
pop() —— 移除并返回栈顶元素。
peek() 或 top() —— 返回栈顶元素但不移除。
isEmpty() —— 检查栈是否为空。

Stacks are used for managing function calls (call stack), undo/redo features in software, and evaluating expressions (bracket matching, postfix evaluation). In exam trace tables, you will often be asked to show the state of a stack after a sequence of pushes and pops.

栈常用于管理函数调用（调用栈）、实现软件的撤销/重做功能，以及计算表达式（括号匹配、后缀表达式求值）。在考试的跟踪表中，你常常需要展示一系列 push 和 pop 操作后栈的状态。

5. Queues (FIFO) | 队列（先进先出）

A queue is a First-In, First-Out (FIFO) structure. Items are added at the rear (enqueue) and removed from the front (dequeue). Just like a queue of people waiting for a bus – the first person to join the line is the first to leave.

队列是一种先进先出（FIFO）的数据结构。元素在队尾加入（入队），从队首移除（出队）。就像排队等公交车的人群一样 —— 最先排队的人最先上车。

Key operations:

enqueue(item) – adds an item to the rear.
dequeue() – removes and returns the item at the front.
peekFront() – returns the front item without removal.
isEmpty() and isFull() (for bounded queues).

关键操作：

enqueue(item) —— 将元素添加到队尾。
dequeue() —— 移除并返回队首元素。
peekFront() —— 返回队首元素但不移除。
isEmpty() 和 isFull()（用于有界队列）。

CCEA often asks about linear queues and circular queues. In a linear queue, space at the front becomes unusable once items are removed; a circular queue reuses that space by wrapping around, making better use of a fixed-size array. Be prepared to draw or trace circular queue pointers (front and rear).

CCEA 考题经常涉及线性队列和循环队列。在线性队列中，一旦元素被移除，队首前面的空间就无法再使用；循环队列通过环绕来重用这些空间，能更有效地利用固定大小的数组。要准备好画出或跟踪循环队列的指针（队首和队尾）。

Applications include printer spooling, keyboard buffers, and simulation of real-world queues.

队列的应用场景包括打印缓冲、键盘缓冲区以及现实世界排队的模拟。

6. Trees (Binary Trees) | 树（二叉树）

A tree is a hierarchical data structure consisting of nodes connected by edges. The topmost node is the root, and each node can have child nodes. A binary tree is a special tree where each node has at most two children: left and right.

树是一种层次化的数据结构，由通过边连接的节点构成。最顶端的节点称为根，每个节点可以拥有子节点。二叉树是一种特殊的树，其中每个节点最多拥有两个子节点：左子节点和右子节点。

For GCSE, focus on the binary tree and its traversal methods:

Pre-order: visit root, then left subtree, then right subtree.
In-order: visit left subtree, then root, then right subtree.
Post-order: visit left subtree, then right subtree, then root.

在 GCSE 阶段，重点掌握二叉树及其遍历方法：

前序遍历： 先访问根，再访问左子树，最后访问右子树。
中序遍历： 先访问左子树，再访问根，最后访问右子树。
后序遍历： 先访问左子树，再访问右子树，最后访问根。

A binary search tree (BST) is a binary tree where the left child contains a value smaller than its parent, and the right child contains a value larger. This property makes searching efficient – on average O(log n). You should be able to insert a value into a BST by comparing with nodes and deciding left or right.

二叉搜索树（BST）是一种特殊的二叉树，其中左子节点的值小于父节点，右子节点的值大于父节点。这一特性使得搜索效率较高 —— 平均时间复杂度为 O(log n)。你应当能够通过比较节点值，决定向左或向右，从而在 BST 中插入一个值。

Trees are used in file systems, expression parsing (binary expression trees), and network routing algorithms. CCEA may ask you to draw a tree from a given sequence or to list nodes visited in a particular traversal order.

树被应用于文件系统、表达式解析（二叉表达式树）以及网络路由算法中。CCEA 可能会要求你根据给定序列画出树，或列出某种遍历顺序下访问的节点。

7. Graphs | 图

A graph is a collection of vertices (nodes) connected by edges. Edges can be directed (one-way) or undirected (two-way), and can carry weights representing costs, distances, or capacities. Graphs are powerful for modelling networks, maps, and social connections.

图是由顶点（节点）和连接它们的边构成的集合。边可以是有向的（单向）或无向的（双向），并且可以带有权重，表示成本、距离或容量。图非常适用于对网络、地图和社交关系进行建模。

Representation in computers:

Adjacency matrix: a 2D array where cell [i][j] indicates whether an edge exists (or its weight). It is fast for checking connections but uses a lot of memory for sparse graphs.
Adjacency list: an array of lists, where each vertex has a list of its neighbours. More memory-efficient for sparse graphs.

在计算机中的表示方法：

邻接矩阵： 一个二维数组，其中单元格 [i][j] 表示是否存在边（或边的权重）。其优点是检查连接快速，但在稀疏图中会占用大量内存。
邻接表： 一个列表的数组，其中每个顶点都有一个邻居列表。对于稀疏图，这种方式更省内存。

For GCSE, you should understand graph concepts such as path, cycle, connected graph, and complete graph. You might also encounter simple graph traversal: depth-first search (DFS) uses a stack, breadth-first search (BFS) uses a queue.

在 GCSE 阶段，你应当理解图的相关概念，如路径、环路、连通图和完全图。你还可能遇到简单的图遍历算法：深度优先搜索（DFS）使用栈，广度优先搜索（BFS）使用队列。

8. Hash Tables | 哈希表

A hash table is a data structure that maps keys to values using a hash function. The hash function computes an index (hash code) from the key, and the value is stored at that index in an array. This enables very fast lookup, insertion, and deletion – ideally O(1).

哈希表是一种通过哈希函数将键映射到值的数据结构。哈希函数根据键计算出索引（哈希码），然后将值存储在数组的该索引位置。这使得查找、插入和删除操作都极快 —— 理想情况下时间复杂度为 O(1)。

A challenge is collision – when two different keys produce the same index. Two common collision resolution methods are:

Chaining: each array slot holds a linked list of all entries that hash to that index.
Open addressing (e.g., linear probing): if a slot is occupied, try the next slot, then the next, until an empty one is found.

哈希表面临的一个挑战是碰撞 —— 两个不同的键可能产生相同的索引。两种常见的碰撞解决方法如下：

链地址法： 每个数组槽位包含一个链表，用于存储所有映射到该索引的条目。
开放寻址法（如线性探测）： 如果槽位已被占用，则尝试下一个槽位，依此类推，直到找到空槽。

Hash tables are used to implement dictionaries, database indexes, and caches. In CCEA questions, you might be asked to insert values into a hash table given a simple hash function (e.g., key mod 10) and show the state after collision handling.

哈希表用于实现字典、数据库索引和缓存。在 CCEA 考题中，你可能会被要求根据一个简单的哈希函数（例如 key mod 10）将值插入哈希表，并展示碰撞处理后的哈希表状态。

9. Comparing Data Structures | 数据结构的比较

In the exam, you need to justify your choice of data structure for a given scenario. Here is a summary comparison:

在考试中，你需要为自己的数据结构选择提供理由。以下是一个简要的比较：

Data Structure	Access	Insert/Delete	Usage
Array	O(1) by index	O(n) mid	Fixed-size, fast random access
Linked List	O(n)	O(1) at head	Dynamic, frequent inserts/deletes
Stack	Top only O(1)	Top only O(1)	LIFO, undo, parsing
Queue	Front only O(1)	Rear O(1)	FIFO, buffers, scheduling
Binary Search Tree	Avg O(log n)	Avg O(log n)	Sorted data, search-heavy
Hash Table	Avg O(1)	Avg O(1)	Key-value lookups, no order

Use this table to quickly recall which structure is best when asked to store a queue of print jobs (queue), reverse a string (stack), or implement a phone book (hash table or BST).

利用这张表，你可以快速回忆起什么场景适用什么结构：存储打印作业队列适合用队列，反转字符串适合用栈，实现电话号码簿则适合用哈希表或二叉搜索树。

10. Exam Tips for CCEA | CCEA 考试技巧

CCEA GCSE Computer Science questions on data structures often combine theory with practical application. Here are some tips to maximise your marks:

CCEA GCSE 计算机科学关于数据结构的考题通常将理论与实践应用相结合。以下是一些最大限度提高分数的技巧：

Read pseudocode carefully: many questions provide algorithms that use data structures. Underline operations like push, pop, enqueue, dequeue, and track variables step by step in a trace table.
Practice drawing: be ready to draw arrays, linked list diagrams, tree structures, and queue circular buffers. Neat diagrams earn marks.
Understand the vocabulary: know the difference between a static data structure (fixed size, fast but inflexible) and a dynamic structure (can grow, more overhead).
Choose wisely: when asked which structure to use, always give a reason, e.g., “A stack because we need to reverse the order” or “A queue because it is first-come-first-served”.
Collision handling: for hash tables, show clear steps if using linear probing – don’t skip the probing sequence.
Traversal order: for binary trees, use a standard method and be consistent. Label your steps if asked to list the order.

中文考试技巧：

仔细阅读伪代码： 许多题目会提供使用数据结构的算法。划出 push、pop、enqueue、dequeue 等操作，并在跟踪表里逐步记录变量值。
练习绘图： 准备好绘制数组、链表图、树结构以及循环队列缓冲区。整洁的图表能为你赢得分数。
理解术语： 清楚静态数据结构（大小固定，快速但不灵活）与动态数据结构（可增长，但开销更大）之间的区别。
明智选择： 当被问及选择哪种结构时，务必给出理由，例如“栈，因为我们需要反转顺序”或“队列，因为它遵循先来先服务的原则”。
碰撞处理： 对于哈希表，如果使用线性探测，要清晰地展示步骤 —— 不要跳过探测序列。
遍历顺序： 对于二叉树，使用标准方法并保持前后一致。如果需要列出访问顺序，请标注你的步骤。

11. Summary | 总结

Mastering data structures is about knowing how data is stored, how it can be manipulated, and when each structure is appropriate. For the CCEA GCSE exam, ensure you can:

掌握数据结构，就是要了解数据如何存储、如何操作，以及每种结构在什么情况下适用。针对 CCEA GCSE 考试，请确保你能做到以下几点：

Define and give examples of arrays, lists, stacks, queues, trees, graphs, and hash tables.
Trace algorithms that use these structures and update their contents correctly.
Compare static vs. dynamic structures and explain the impact on memory and speed.
Choose the most efficient structure for a given problem and justify your choice.

中文总结：

能定义并举例说明数组、列表、栈、队列、树、图和哈希表。
能追踪使用这些结构的算法，并正确更新其内容。
能比较静态与动态结构，并解释其对内存和速度的影响。
能为给定的问题选择最有效的结构，并说明理由。

With practice, you will find that data structures are logical and consistent. Use flashcards, draw diagrams, and write short programs to implement them yourself – this deepens understanding.

通过练习，你会发现数据结构既符合逻辑又具有一致性。多用闪卡、画图，并亲自编写小程序来实现它们 —— 这将加深你的理解。

Published by TutorHao | GCSE CCEA Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

GCSE CCEA Computer Science: Data Structures Key Points Review | GCSE CCEA 计算机：数据结构 考点精讲