Data Structures for GCSE Edexcel Computer Science | GCSE Edexcel 计算机：数据结构考点精讲

📚 Data Structures for GCSE Edexcel Computer Science | GCSE Edexcel 计算机：数据结构考点精讲

Data structures are the building blocks that allow programs to store, organise, and manipulate data efficiently. In GCSE Edexcel Computer Science, you are expected to understand how common structures like arrays, lists, stacks, queues, trees, and records work, along with their typical operations, advantages, and limitations. This article covers the essential exam topics, presents example scenarios, and clarifies key distinctions to help you score high marks.

数据结构是程序高效存储、组织和操作数据的基石。在 GCSE Edexcel 计算机科学中，你需要理解数组、列表、栈、队列、树、记录等常见结构的工作原理，以及它们的基本操作、优点和局限。本文梳理了必考主题，通过示例和对比帮你理清概念，从而在考试中拿到高分。

1. What Is a Data Structure? | 什么是数据结构？

A data structure is a particular way of organising data in a computer so that it can be used effectively. The choice of structure affects how quickly data can be accessed, updated, inserted, or deleted. For example, an array stores elements in contiguous memory locations, allowing fast indexed access, while a linked list stores elements with pointers, making insertions and deletions simpler without shifting large blocks of memory.

数据结构是在计算机中组织数据的一种特定方式，目的是提高使用效率。选择不同的结构会影响数据的访问、更新、插入和删除速度。比如，数组在连续内存中存储元素，支持通过索引快速访问；而链表通过指针连接元素，插入和删除更方便，无需移动大块内存。

2. Arrays: Static and Dynamic | 数组：静态与动态

An array is a collection of elements, all of the same data type, stored contiguously in memory. Static arrays have a fixed size declared at compile time; dynamic arrays can resize during execution (e.g. using built‑in list types in Python). Arrays allow random access via an index (0‑based), which takes O(1) time. However, inserting or deleting an element in the middle requires shifting subsequent elements, which is O(n) in the worst case. In Edexcel exams, you should be able to trace array operations, declare arrays in pseudocode, and explain why indexing starts at 0.

数组是相同数据类型的元素集合，在内存中连续存储。静态数组在编译时声明固定大小；动态数组可以在运行时调整大小（例如 Python 内置的列表）。数组允许通过索引（从 0 开始）随机访问，时间复杂度为 O(1)。但在数组中间插入或删除元素需要移动后续元素，最坏情况为 O(n)。Edexcel 考试要求你能跟踪数组操作、用伪代码声明数组，并解释索引为何从 0 开始。

Static array in pseudocode: DECLARE scores : ARRAY[0:9] OF INTEGER (10 elements).
静态数组伪代码： DECLARE scores : ARRAY[0:9] OF INTEGER (10 个整数)。

Address of element i = base_address + i × element_size

元素 i 的地址 = 基地址 + i × 元素大小

3. Lists and Linked Structures | 列表与链式结构

In GCSE Edexcel, “list” often refers to a linked list: a dynamic collection of nodes where each node contains data and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory. Insertion and deletion at the beginning are O(1) if you have a head pointer; searching for an arbitrary element is O(n). You should know how to traverse a linked list, add a node at the start or end, and remove a node by updating pointers. Pseudocode will often use a class or record to represent a node.

在 GCSE Edexcel 考试中，“列表”通常指链表：一种由节点组成的动态集合，每个节点包含数据和一个指向下一个节点的指针。与数组不同，链表不需要连续内存。如果有头指针，在头部插入和删除时间复杂度为 O(1)；查找任意元素为 O(n)。你需要掌握如何遍历链表、在开头或末尾添加节点，以及通过更新指针删除节点。伪代码中通常用类或记录表示节点。

TYPE Node
    data : STRING
    next : INTEGER  // pointer to index of next node
ENDTYPE

4. Stacks: LIFO Principle | 栈：后进先出

A stack is a Last‑In‑First‑Out data structure. The main operations are push (add an item to the top) and pop (remove the item from the top). Some specifications also include peek (or top) to examine the top element without removal. Stacks can be implemented using arrays or linked lists. A common application is managing function calls (call stack) or checking balanced parentheses in an expression. In pseudocode, you may see a stack as an array with a top pointer that increments and decrements. Be ready to trace push and pop operations and identify stack underflow (popping from an empty stack) or overflow (pushing onto a full array).

栈是一种后进先出的数据结构。主要操作是 push（向栈顶添加元素）和 pop（移除栈顶元素）。某些大纲还包括 peek（或 top）以查看栈顶元素而不移除。栈可以用数组或链表实现。其常见应用包括管理函数调用（调用栈）或检查表达式中的括号匹配。在伪代码中，栈通常是一个数组，配有不断增减的栈顶指针。你需要能跟踪 push 和 pop 操作，并能判断栈下溢（对空栈 pop）或上溢（向已满的数组 push）。

Push: top ← top + 1 → stack[top] ← new_item

推入：栈顶指针 + 1 → stack[top] ← 新元素

5. Queues: FIFO Principle | 队列：先进先出

A queue follows the First‑In‑First‑Out rule. Operations are enqueue (add to the rear) and dequeue (remove from the front). Just like stacks, queues may be implemented with arrays (often circular to reuse space) or linked lists. Common exam questions ask you to draw the front and rear pointers after a series of operations, or to explain how a circular queue avoids wasted space. The concept of priority queues, where items are dequeued based on priority rather than arrival order, is also part of some Edexcel specifications.

队列遵循先进先出规则。操作包括 enqueue（加入队尾）和 dequeue（从队首移除）。与栈类似，队列可以用数组（常采用循环数组以节省空间）或链表实现。常见的考题要求你画出一系列操作后的队首和队尾指针，或解释循环队列如何避免空间浪费。某些 Edexcel 大纲还包括优先队列，元素按优先级出队而非按到达顺序。

Linear queue with array: front and rear pointers move forward; after dequeues, space at the front becomes unusable.
线性队列：队首和队尾指针向前移动；出队后队首之前的空间无法使用。
Circular queue: pointers wrap around using modulo arithmetic, e.g. rear ← (rear + 1) MOD size.
循环队列：利用取模运算让指针环绕，如 rear ← (rear + 1) MOD 容量。

6. Trees and Binary Search Trees | 树与二叉搜索树

A tree is a hierarchical structure consisting of nodes connected by edges. The top node is the root; nodes with no children are leaves. A binary tree restricts each node to at most two children. A binary search tree (BST) maintains the property: left child ≤ parent ≤ right child (or strict ordering depending on specification). BSTs support efficient searching, insertion, and deletion – in a balanced tree, these operations take O(log n) time. Edexcel may test your understanding of tree traversal: pre‑order (root, left, right), in‑order (left, root, right – which yields sorted output for a BST), and post‑order (left, right, root). Be able to construct a BST from a sequence of inserted values and to recognise how an unbalanced BST degrades to O(n) search time.

树是一种由节点和边组成的层次结构。最上方的节点是根；没有子节点的节点是叶子。二叉树的每个节点最多有两个子节点。二叉搜索树 (BST) 保持着：左子节点 ≤ 父节点 ≤ 右子节点的特性（具体视大纲而定）。BST 支持高效的查找、插入和删除——在平衡树中，这些操作的时间复杂度为 O(log n)。Edexcel 可能考查你对遍历的理解：先序（根左右）、中序（左根右——对于 BST 会输出排序序列）和后序（左右根）。你应能根据插入序列构建 BST，并认识到非平衡 BST 的搜索时间会退化为 O(n)。

// Insert 8, 3, 10, 1, 6 into a BST
    8
   / \
  3  10
 / \
1   6

7. Records and Structs | 记录与结构体

A record (sometimes called a struct) groups related data items of possibly different types under a single name. For example, a student record might have fields: name (STRING), age (INTEGER), grade (CHAR). Records are the foundation of databases and file processing. In pseudocode, you define a record type and then declare variables of that type. Access to fields uses dot notation, e.g. student1.name. Edexcel often asks students to read/write records from/to a file, or to use arrays of records to solve a problem.

记录（有时称为结构体）将可能不同类型的数据项组合在一个名字下。例如，学生记录可能包含字段：姓名 (STRING)、年龄 (INTEGER)、成绩 (CHAR)。记录是数据库和文件处理的基础。在伪代码中，你先定义记录类型，再声明该类型的变量。用点号访问字段，如 student1.name。Edexcel 常要求学生从文件读取或向文件写入记录，或使用记录数组解决问题。

TYPE Student
    name : STRING
    year : INTEGER
    average : REAL
ENDTYPE
DECLARE pupil : Student
pupil.name ← "Alice"

8. Hash Tables and Key‑Value Storage | 哈希表与键值存储

A hash table uses a hash function to map a key to an index in an underlying array, enabling fast lookups (average O(1)). Collisions occur when two keys produce the same index, and must be handled by techniques such as chaining (each array cell points to a linked list) or open addressing (probing for the next free slot). In GCSE Edexcel, you may be asked to insert items using a given hash function, show the state of the table after collisions, or explain why a good hash function distributes keys uniformly.

哈希表通过哈希函数将键映射为底层数组的索引，从而实现快速查找（平均 O(1)）。当两个键产生相同索引时会发生冲突，必须通过链址法（每个数组单元指向一个链表）或开放寻址法（探查下一个空闲槽）来解决。在 GCSE Edexcel 中，你可能要根据给定的哈希函数插入项、展示冲突后表的状态，或解释为什么好的哈希函数能均匀分布键。

index = hash(key) MOD table_size

索引 = 哈希(键) MOD 表大小

9. Choosing the Right Data Structure | 选择合适的数据结构

The Edexcel exam may present a scenario and ask which data structure is most suitable. Consider the requirements: frequent random access → array; many insertions/deletions at the front → linked list; need to reverse order of processing → stack; need to process items in order of arrival → queue; hierarchical data like file system → tree; fast key‑based retrieval → hash table; grouping mixed data → record. Being able to justify your choice with reference to efficiency and operations is essential for high‑level answers.

Edexcel 考试会给出场景，问你哪种数据结构最合适。需要考量的因素包括：频繁的随机访问 → 数组；在开头大量插入/删除 → 链表；需要反序处理 → 栈；按到达顺序处理 → 队列；文件系统等层次数据 → 树；快速按键检索 → 哈希表；混合数据组合 → 记录。能够结合效率和操作来论证你的选择，是高阶答案的关键。

Operation	Array	Linked List	BST (balanced)
Access by index	O(1)	O(n)	N/A
Insert at start	O(n)	O(1)	O(log n)
Search	O(log n) if sorted, else O(n)	O(n)	O(log n)

操作 – 数组、链表、平衡二叉搜索树的时间复杂度对比

10. Tracing and Pseudocode Exam Skills | 跟踪与伪代码应试技巧

Many Edexcel questions involve stepping through pseudocode that manipulates data structures. Practise tracing insertions into a sorted array, reversing a stack using a second temporary stack, or performing breadth‑first traversal using a queue. Pay attention to boundary conditions: empty structures, full arrays, and pointer updates. Use clearly labelled diagrams when asked to draw the state of a structure. Always initialise pointers (top, front, rear, root) and check for overflow/underflow where appropriate. These details separate a pass from a distinction.

许多 Edexcel 题目要求你逐行跟踪操纵数据结构的伪代码。练习跟踪向有序数组插入、使用第二个临时栈反转栈，或使用队列进行广度优先遍历。注意边界条件：空结构、数组满、指针更新。当要求画出结构状态时，使用清晰标记的图示。务必初始化指针（top, front, rear, root），并视情况检查上溢/下溢。这些细节决定你是及格还是拿到优秀。

// Pseudocode to check balanced brackets using a stack
FOR each character c IN expression
    IF c = '(' THEN push()
    ELSE IF c = ')' THEN
        IF stack is empty THEN RETURN FALSE
        ELSE pop()
    ENDIF
ENDFOR
RETURN stack is empty

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

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

Data Structures for GCSE Edexcel Computer Science | GCSE Edexcel 计算机：数据结构 考点精讲