📚 GCSE Computer Science: Data Structures Revision | GCSE 计算机：数据结构 考点精讲
Data structures are fundamental to how computer programs store, organise and manipulate information. Choosing the right data structure directly affects the efficiency of a program, and GCSE examiners expect you to understand the core structures, their properties and typical operations. This guide walks through arrays, two‑dimensional arrays, records, lists, stacks, queues, trees and graphs, explaining each one with clear English descriptions and Mandarin Chinese translations, so you can feel confident tackling any related question.
数据结构是计算机程序存储、组织和处理信息的基础。选择合适的数据结构直接影响程序的效率，GCSE 考官要求你理解核心数据结构、它们的特性以及典型操作。本指南将逐一讲解数组、二维数组、记录、列表、栈、队列、树和图，用清晰的英文描述和中文翻译解释每一个知识点，让你能自信应对任何相关考题。
1. What Are Data Structures? | 什么是数据结构？
In computing, a data structure is a specialised format for organising and storing data so that it can be accessed and modified efficiently. Think of it as a container with built‑in rules: some containers keep items in a fixed order, others allow quick insertions at either end, and some connect data items like a flowchart. At GCSE level, you need to know the characteristics of static structures (size fixed at creation) and dynamic structures (size can grow or shrink), and recognise common abstract data types such as arrays, stacks, queues, trees and graphs.
在计算机领域，数据结构是一种组织与存储数据的专门格式，以便高效地访问和修改数据。你可以把它看作一个内置规则的容器：有些容器保持固定顺序，有些允许在两端快速插入，有些则像流程图一样连接数据项。在 GCSE 阶段，你需要了解静态结构（创建时大小固定）和动态结构（大小可增长或缩小）的特征，并认识常见的抽象数据类型，如数组、栈、队列、树和图。
2. Arrays | 数组
An array is a collection of elements, all of the same data type, stored in contiguous memory locations. Each element can be accessed directly using an index, typically starting from 0. Because memory addresses are calculated from the base address and the index, accessing any element takes the same amount of time – this is called constant‑time access, written as O(1). However, inserting or deleting an element in the middle of an array usually requires shifting many elements, which can be slow. Arrays are fundamental to almost every program and form the basis for more complex structures like 2D arrays and dynamic arrays.
数组是一组元素集合，所有元素具有相同的数据类型，存储在连续的内存位置中。每个元素可以通过索引直接访问，索引通常从 0 开始。由于内存地址是通过基地址和索引计算得到的，访问任意元素所需的时间相同——这称为常数时间访问，记作 O(1)。然而，在数组中间插入或删除元素通常需要移动大量元素，这可能会很慢。数组几乎是每个程序的基础，并构成二维数组和动态数组等更复杂结构的基础。
3. Two‑Dimensional Arrays | 二维数组
A two‑dimensional (2D) array is often described as an ‘array of arrays’, forming a grid of rows and columns. Visually, it resembles a table or a matrix. Each element is identified by two indices, for example grid[2][1] where 2 represents the row and 1 the column. 2D arrays are extremely useful for representing board games, spreadsheets, pixel grids in images, and any data set that naturally fits a row‑column structure. In memory, a 2D array can be stored either in row‑major order (row by row) or column‑major order, but at GCSE you mainly need to know how to declare, index and traverse them using nested loops.
二维数组通常被描述为“数组的数组”，构成一个行与列的网格。从视觉上看，它类似于一张表格或矩阵。每个元素通过两个索引标识，例如 grid[2][1]，其中 2 表示行，1 表示列。二维数组对于表示棋盘游戏、电子表格、图像中的像素网格以及任何自然适合行列结构的数据集都非常有用。在内存中，二维数组可以按行优先顺序（逐行）或列优先顺序存储，但在 GCSE 阶段你主要需要知道如何声明、索引并使用嵌套循环遍历它们。
4. Records | 记录
A record is a composite data structure that groups together related items of possibly different data types under one name. For example, a student record might contain a string for name, an integer for age and a string for tutor group. Each individual part is called a field. Records are the building blocks of databases and files, and they map naturally to structures (or classes) in programming languages. When comparing with arrays, remember that arrays hold multiple values of the same type, while records can hold different types that logically belong together.
记录是一种复合数据结构，它将可能具有不同数据类型的相关项组合在一个名称下。例如，一个学生记录可以包含一个字符串类型的 姓名、一个整数类型的 年龄 和一个字符串类型的 辅导组。其中的每一部分被称为字段。记录是数据库和文件的构建块，并且很自然地映射到编程语言中的结构体（或类）。与数组比较时，请记住数组存放的是相同类型的多个值，而记录可以存放逻辑上属于一起的不同类型。
5. Lists and Linked Lists | 列表与链表
In GCSE contexts, a ‘list’ often refers to an abstract collection that can hold elements in a given order. Many programming languages implement lists using dynamic arrays behind the scenes. However, exam boards also like to test your understanding of a linked list: a dynamic structure where each element (node) contains data and a pointer to the next node. Linked lists allow efficient insertion and deletion anywhere, as you only need to update pointers rather than shift elements. The trade‑off is that you cannot directly jump to the nth element – you must start at the head and follow pointers sequentially, which takes O(n) time for access.
在 GCSE 的语境下，“列表”通常指一种可以按给定顺序存放元素的抽象集合。许多编程语言在底层使用动态数组来实现列表。然而，考试局也喜欢考查你对链表的理解：一种动态结构，其中每个元素（节点）包含数据和指向下一个节点的指针。链表允许在任何位置高效地插入和删除，因为只需更新指针，无需移动元素。代价是你不能直接跳转到第 n 个元素——必须从头节点开始按顺序跟随指针，这需要 O(n) 的访问时间。
6. Stacks | 栈
A stack is a linear data structure that follows the Last‑In‑First‑Out (LIFO) principle. You can visualise it as a pile of plates: you can only add or remove the top plate. The two fundamental operations are push (add an item to the top) and pop (remove the item from the top). Stacks are used in scenarios like managing function calls (call stack), implementing undo features, and evaluating expressions (e.g. bracket matching). A stack overflow error occurs when you try to push an item onto a full stack with a fixed capacity.
栈是一种遵循后进先出原则的线性数据结构。你可以把它想象成一摞盘子：你只能添加或移除顶部的盘子。两个基本操作是 push（压入，将元素添加到栈顶）和 pop（弹出，将元素从栈顶移除）。栈用于管理函数调用（调用栈）、实现撤销功能以及求值表达式（如括号匹配）等场景。当你试图向固定容量的满栈中压入元素时，就会发生栈溢出错误。
7. Queues | 队列
A queue works on the First‑In‑First‑Out (FIFO) basis, just like people lining up to buy tickets. New items join at the rear, and items are removed from the front. The most common operations are enqueue (add to the rear) and dequeue (remove from the front). Queues are essential in any buffering system: keyboard input buffers, print spooling, and CPU task scheduling. In a circular queue implementation, the rear and front pointers wrap around to reuse vacant spaces, making the queue more memory‑efficient for fixed‑size arrays.
队列按照先进先出的原则工作，就像人们排队买票一样。新元素加入队尾，元素从队首移除。最常见的操作是 enqueue（入队，添加到队尾）和 dequeue（出队，从队首移除）。队列在任何缓冲系统中都至关重要：键盘输入缓冲、打印队列和 CPU 任务调度。在循环队列实现中，队尾和队首指针会回绕以重复利用空闲空间，使固定大小数组的队列内存效率更高。
8. Stack and Queue Comparison | 栈与队列的比较
| Stack | Queue | |
| Principle | LIFO (Last In, First Out) | FIFO (First In, First Out) |
| Main operations | push (add to top), pop (remove from top) | enqueue (add to rear), dequeue (remove from front) |
| Common uses | Call stack, undo, backtracking | Buffers, scheduling, breadth‑first search |
| Analogy | Stack of plates | Queue at a ticket counter |
This table summarises the key differences. Make sure you can quickly decide which structure is appropriate for a given scenario. If a problem mentions ‘most recently added’ or ‘go back’, think of a stack. If it mentions ‘in the order they arrived’ or ‘waiting line’, think of a queue.
这张表格总结了关键区别。确保你能快速判断哪种结构适合给定的场景。如果问题提到“最近添加的”或“返回”，请想到栈。如果提到“按到达的顺序”或“排队等待”，请想到队列。
9. Tree Structures | 树结构
A tree is a hierarchical data structure consisting of nodes connected by edges. The top node is called the root, and nodes with no children are leaves. The most common tree at GCSE is the binary tree, where each node has at most two children – left and right. A binary search tree (BST) introduces an ordering rule: for any node, all values in the left subtree are smaller, and all values in the right subtree are larger. This property allows fast searching, insertion and deletion (O(log n) on average). Tree traversal algorithms (pre‑order, in‑order, post‑order) specify the sequence in which nodes are visited. For a BST, an in‑order traversal will output the values in ascending order.
树是一种由节点和边连接而成的层次化数据结构。最顶部的节点称为根，没有子节点的节点称为叶节点。GCSE 中最常见的树是二叉树，其中每个节点最多有两个子节点——左子节点和右子节点。二叉搜索树引入了一条排序规则：对于任意节点，左子树中的所有值都较小，右子树中的所有值都较大。这一特性使得搜索、插入和删除都很快速（平均 O(log n)）。树的遍历算法（前序、中序、后序）规定了访问节点的顺序。对于二叉搜索树，中序遍历将按升序输出所有值。
10. Graphs | 图
While a tree is a connected graph without cycles, the term ‘graph’ in computer science refers to a more general structure made up of vertices (or nodes) and edges that can be directed or undirected, weighted or unweighted. Graphs are used to model networks such as social media connections, road maps, and the internet. GCSE exams may ask you to represent a graph using an adjacency matrix (a 2D array where cell [i][j] indicates whether there is an edge between vertex i and vertex j) or an adjacency list (a list of neighbours for each vertex). Understanding these representations helps you compare storage efficiency and ease of searching for connections.
虽然树是一种无环的连通图，但计算机科学中的“图”一词指的是一种更通用的结构，由顶点（或节点）和边组成，边可以是有向或无向、带权或不带权。图用于对网络进行建模，如社交媒体连接、道路地图和互联网。GCSE 考试可能会要求你使用邻接矩阵（一个二维数组，其中单元格 [i][j] 表示顶点 i 和顶点 j 之间是否存在边）或邻接表（每个顶点的邻居列表）来表示图。理解这些表示方法有助于比较存储效率和查找连接的难易程度。
11. Static Versus Dynamic Data Structures | 静态与动态数据结构
Data structures can be classified as static or dynamic. Static structures, like a typical array, have a fixed size determined at compile time; they allocate a block of memory once and cannot easily be resized, which can lead to wasted space or overflow. Dynamic structures, such as linked lists and binary trees, can grow and shrink at runtime by allocating and deallocating memory for nodes as needed. This flexibility avoids wasted space but introduces extra overhead for managing pointers. Understanding the trade‑offs is a common GCSE comparison question.
数据结构可分为静态和动态。静态结构（如典型的数组）具有在编译时确定的固定大小；它们一次性分配一块内存，且不易调整大小，这可能导致空间浪费或溢出。动态结构（如链表和二叉树）可以在运行时通过按需为节点分配和释放内存来增长和收缩。这种灵活性避免了空间浪费，但引入了管理指针的额外开销。理解这些权衡是 GCSE 中常见的比较题。
12. Choosing the Right Data Structure | 选择合适的数据结构
When a GCSE question asks you to justify a choice of data structure, think about the operations that will be performed most often. If you need fast random access by index, an array is best. If frequent insertions and deletions at both ends are required, a linked list or deque might be better. For depth‑first exploration, a stack is natural; for level‑by‑level processing, a queue works perfectly. For organised storage that allows quick lookups, a binary search tree is suitable. There is rarely one perfect answer – you must weigh up speed, memory usage and how the data is logically organised.
当 GCSE 考题要求你证选择某种数据结构的理由时，请思考最常执行哪些操作。如果需要通过索引快速随机访问，数组是最佳选择。如果需要在两端频繁插入和删除，链表或双端队列可能更好。进行深度优先探索时，栈很自然；进行逐层处理时，队列非常合适。对于允许快速查找的组织化存储，二叉搜索树很适用。这世上少有完美的答案——你必须权衡速度、内存占用以及数据的逻辑组织方式。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导