📚 IGCSE Edexcel Computer Science: Data Structures Key Points | IGCSE Edexcel 计算机：数据结构 考点精讲
Data structures are fundamental to organising and storing data efficiently in computer memory. In the IGCSE Edexcel Computer Science syllabus, you are expected to understand the properties, operations, and practical applications of a range of data structures, from simple arrays and records to dynamic structures like stacks, queues, and binary trees. This article provides a comprehensive revision guide, covering key concepts, traversal methods, algorithms, and common exam pitfalls to help you achieve top marks.
数据结构是计算机内存中高效组织和存储数据的基础。在 IGCSE Edexcel 计算机科学课程中，你需要理解从简单的数组和记录到栈、队列和二叉树等动态结构的一系列数据结构的特性、操作和实际应用。本文提供一份全面的复习指南，涵盖关键概念、遍历方法、算法和常见考试易错点，帮助你取得高分。
1. Arrays: Static Linear Collections | 数组：静态线性集合
An array is a finite, ordered collection of elements of the same data type, stored in contiguous memory locations. Each element can be accessed directly using an index, which usually starts from 0. Arrays are static, meaning their size must be defined at the time of declaration and cannot be changed during execution.
数组是相同数据类型的元素的有限、有序集合，存储在连续的内存位置。每个元素可以通过索引直接访问，索引通常从 0 开始。数组是静态的，意味着它们的大小必须在声明时定义，并且在执行期间不能改变。
In pseudocode, a one‑dimensional array might be declared as DECLARE scores : ARRAY[1:10] OF INTEGER. Two‑dimensional arrays are declared with two index ranges, such as DECLARE grid : ARRAY[1:5,1:5] OF CHAR. Accessing an element is O(1) constant time, making arrays very fast for reading and writing individual items.
在伪代码中，一维数组可以声明为 DECLARE scores : ARRAY[1:10] OF INTEGER。二维数组使用两个索引范围声明，例如 DECLARE grid : ARRAY[1:5,1:5] OF CHAR。访问一个元素的时间复杂度为 O(1) 常数时间，因此数组对于读取和写入单个元素非常快。
However, insertion and deletion of elements (other than at the end) require shifting subsequent elements, which makes these operations O(n). Examiners often ask you to write algorithms to perform insertion or deletion in an array while maintaining order. Remember to loop backwards when inserting to avoid overwriting values.
然而，插入和删除元素（除了在末尾）需要移动后续元素，这使得这些操作的时间复杂度为 O(n)。考官经常要求你编写算法，在数组中执行插入或删除操作，同时保持顺序。请记住，在插入时要向后循环，以避免覆盖数值。
2. Records: Grouping Related Fields | 记录：相关字段的组合
A record is a data structure that groups a fixed number of related fields of possibly different data types. Unlike an array, each field in a record is identified by a field name rather than an index. Records form the basis of databases and file structures. In pseudocode, a record type is defined first, then variables of that type are declared.
记录是一种数据结构，它将固定数量的可能不同类型的相关字段组合在一起。与数组不同，记录中的每个字段由字段名而不是索引来标识。记录是数据库和文件结构的基础。在伪代码中，先定义记录类型，然后声明该类型的变量。
For example: TYPE Student DECLARE name : STRING, age : INTEGER, grade : CHAR ENDTYPE. Then DECLARE pupil : Student. Accessing a field uses dot notation: pupil.name ← 'Alice'. A common exam task is to work with an array of records, such as storing details of multiple students and performing searches or sorts on a particular field.
例如：TYPE Student DECLARE name : STRING, age : INTEGER, grade : CHAR ENDTYPE。然后 DECLARE pupil : Student。访问字段使用点标记法：pupil.name ← 'Alice'。一个常见的考试任务是处理记录数组，例如存储多个学生的详细信息，并对某个字段进行搜索或排序。
3. Files: Persistent Storage Structures | 文件：持久性存储结构
A file is a data structure stored on a secondary storage device that persists after the program terminates. In the Edexcel syllabus, you need to understand the differences between serial, sequential, and random (direct) access files. Serial files store records in the order they arrive, sequential files maintain a logical order based on a key field, and random files allow direct access to any record using a hashing algorithm or index.
文件是存储在辅助存储设备上的数据结构，在程序终止后仍然存在。在 Edexcel 大纲中，你需要理解串行文件、顺序文件和随机（直接）访问文件之间的区别。串行文件按记录到达的顺序存储，顺序文件根据键字段保持逻辑顺序，随机文件允许使用哈希算法或索引直接访问任何记录。
Key file operations include OPEN, READ, WRITE, and CLOSE. When processing a sequential file, you typically loop until the end‑of‑file marker is reached. A common exam algorithm is to merge two sorted sequential files into a new file while preserving the order. You must handle the case where one file runs out of records first.
关键的文件操作包括 OPEN、READ、WRITE 和 CLOSE。处理顺序文件时，通常会循环直到到达文件结束标记。一个常见的考试算法是将两个已排序的顺序文件合并到一个新文件中，同时保持顺序。你必须处理一个文件先耗尽记录的情况。
4. Linked Lists: Dynamic Linear Structures | 链表：动态线性结构
A linked list is a dynamic data structure where each node contains data and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory, so their size can grow or shrink during program execution. The start of the list is marked by a head pointer; the last node points to a null value (often represented by NIL or None).
链表是一种动态数据结构，每个节点包含数据和一个指向下一个节点的指针。与数组不同，链表不需要连续的内存，因此它们的大小可以在程序执行期间增长或缩小。链表的开头由一个头指针标记；最后一个节点指向一个空值（通常用 NIL 或 None 表示）。
Traversing a linked list requires following pointers sequentially, so random access is not directly possible (O(n)). Insertion and deletion, however, can be O(1) if you have a pointer to the relevant position, as only the links need updating. You may be asked to draw a diagram showing how pointers change during insertion or to write pseudocode for these operations.
遍历链表需要顺序地跟随指针，因此不能直接进行随机访问（O(n)）。然而，如果你有指向相关位置的指针，插入和删除操作可以是 O(1) 的，因为只需更新链接。可能会要求你画出图表，显示插入过程中指针的变化，或者为这些操作编写伪代码。
5. Stacks: LIFO Abstract Data Type | 栈：后进先出抽象数据类型
A stack is an abstract data type (ADT) that follows the Last In, First Out (LIFO) principle. Elements are added (pushed) and removed (popped) only from the top. Stacks can be implemented using arrays or linked lists. The key operations are push(item), pop(), and peek() (or top()) which returns the top element without removing it.
栈是一种遵循后进先出（LIFO）原则的抽象数据类型（ADT）。元素只能在栈顶添加（push）和移除（pop）。栈可以用数组或链表实现。关键操作有 push(item)、pop() 和 peek()（或 top()），后者返回栈顶元素但不移除它。
Examiners often ask you to trace stack operations given a sequence of pushes and pops. Be careful with the state of the stack pointer when the stack is empty or full (overflow/underflow). Practical applications include managing subroutine calls, undo features in software, and evaluating reverse Polish notation (RPN) expressions.
考官经常要求你在给定一系列入栈和出栈操作的情况下跟踪栈的状态。当栈为空或满（上溢/下溢）时，要注意栈指针的状态。实际应用包括管理子程序调用、软件中的撤销功能，以及计算逆波兰表达式（RPN）。
An RPN evaluation algorithm uses a stack: scan the expression left to right; if a number is encountered, push it; if an operator is encountered, pop the required number of operands, apply the operator, and push the result. This tests both your understanding of stacks and your ability to write clear pseudocode.
逆波兰表达式求值算法使用栈：从左到右扫描表达式；如果遇到数字，将其压入栈中；如果遇到运算符，弹出所需数量的操作数，应用该运算符，然后将结果压入栈中。这一方面考验你对栈的理解，也考验你编写清晰伪代码的能力。
6. Queues: FIFO Abstract Data Type | 队列：先进先出抽象数据类型
A queue is an ADT that follows the First In, First Out (FIFO) principle. Items are added at the rear (enqueue) and removed from the front (dequeue). As with stacks, queues can be implemented with arrays (circular queues are often used to utilise space efficiently) or linked lists. Operations include enqueue(item), dequeue(), and checking if the queue is empty or full.
队列是一种遵循先进先出（FIFO）原则的抽象数据类型。元素在队尾添加（enqueue），在队头移除（dequeue）。与栈一样，队列可以用数组（通常使用循环队列来高效利用空间）或链表实现。操作包括 enqueue(item)、dequeue()，以及检查队列是否为空或已满。
In a circular queue, two pointers (front and rear) move around the array. When the pointer reaches the end, it wraps around to the beginning. The condition for a full queue requires careful handling to distinguish it from an empty queue. A common approach is to leave one slot unused. You might need to calculate the number of elements based on pointer positions.
在循环队列中，两个指针（队头和队尾）在数组中移动。当指针到达数组末尾时，它会绕回到开头。满队列的条件需要仔细处理，以区别于空队列。一种常见的方法是留一个未使用的槽。你可能需要根据指针位置计算队列中元素的数量。
Typical applications of queues include print spooling, keyboard buffers, and breadth‑first traversal of graphs. The syllabus may ask you to simulate a queue using an array and write code for enqueue and dequeue, ensuring correct updates of front and rear indices.
队列的典型应用包括打印后台处理、键盘缓冲区和图的广度优先遍历。大纲可能会要求你使用数组模拟队列，并编写入队和出队的代码，确保正确更新队头和队尾的索引。
7. Trees and Binary Trees: Hierarchical Structures | 树与二叉树：层次结构
A tree is a hierarchical data structure consisting of nodes connected by edges. The topmost node is the root; nodes with no children are leaves. A binary tree is a tree where each node has at most two children: a left child and a right child. Binary trees are used to represent expressions, implement search trees, and manage hierarchical data like file systems.
树是一种层次数据结构，由通过边连接的节点组成。最顶层的节点是根节点；没有孩子的节点是叶节点。二叉树是一种每个节点最多有两个孩子的树：左孩子和右孩子。二叉树用于表示表达式、实现搜索树以及管理像文件系统这样的层次数据。
A binary search tree (BST) is an ordered binary tree where for any node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater. This property enables efficient searching, insertion, and deletion (O(log n) on average). You must be able to construct a BST from a given list of values and perform an in‑order traversal to retrieve the values in ascending order.
二叉搜索树（BST）是一种有序的二叉树，对于任何一个节点，其左子树中的所有值都小于该节点的值，右子树中的所有值都大于该节点的值。这一特性使得搜索、插入和删除操作在平均情况下高效（O(log n)）。你必须能够根据给定的列表构建二叉搜索树，并进行中序遍历，从而按升序检索这些值。
8. Binary Tree Traversals: Pre‑order, In‑order, Post‑order | 二叉树遍历：前序、中序、后序
Traversing a binary tree means visiting each node exactly once in a systematic way. The three depth‑first traversal methods differ in the order in which the root, left subtree, and right subtree are visited. The Edexcel syllabus expects you to state the output of a traversal and to construct a tree given two traversal sequences (usually in‑order and pre‑order).
遍历二叉树意味着以系统的方式恰好访问每个节点一次。三种深度优先遍历方法的不同之处在于访问根节点、左子树和右子树的顺序。Edexcel 大纲要求你能够说出遍历的输出，并能根据两个遍历序列（通常是中序和前序）构建树。
Pre‑order traversal: Visit root, then traverse left subtree, then traverse right subtree. This is useful for producing a prefix (Polish) notation of an expression tree.
前序遍历：访问根节点，然后遍历左子树，然后遍历右子树。这有助于生成表达式树的前缀（波兰）表示法。
In‑order traversal: Traverse left subtree, visit root, traverse right subtree. For a BST, this yields the values in sorted order.
中序遍历：遍历左子树，访问根节点，遍历右子树。对于二叉搜索树，这会产生按顺序排列的值。
Post‑order traversal: Traverse left subtree, traverse right subtree, visit root. This is used to produce postfix (Reverse Polish) notation.
后序遍历：遍历左子树，遍历右子树，访问根节点。这用于生成后缀（逆波兰）表示法。
Be prepared to draw a tree and label the traversal order with dashed arrows, or to complete a traversal algorithm in pseudocode using recursion. A typical algorithm: PROCEDURE InOrder(node) calls itself first on the left child, then outputs the node’s data, then calls itself on the right child.
准备好画出树并用虚线箭头标记遍历顺序，或者用递归伪代码完成遍历算法。典型的算法：PROCEDURE InOrder(node) 首先在左孩子上调用自身，然后输出节点的数据，再在右孩子上调用自身。
9. Graphs: Networks of Nodes and Edges | 图：节点和边的网络
A graph is a data structure consisting of vertices (nodes) and edges (connections). Graphs can be directed or undirected, weighted or unweighted. In IGCSE, you are not required to implement graph algorithms in depth, but you should recognise graph representations such as adjacency matrices and adjacency lists, and understand their space efficiency trade‑offs.
图是一种由顶点（节点）和边（连接）组成的数据结构。图可以是有向或无向的，带权或不带权的。在 IGCSE 中，你不需要深入实现图算法，但应能识别图的表示方式，如邻接矩阵和邻接表，并理解它们空间效率的权衡。
An adjacency matrix is a 2D array where element [i,j] is 1 (or the weight) if an edge exists from vertex i to vertex j. This gives O(1) edge existence check but uses O(V²) space. An adjacency list stores a list of neighbours for each vertex, using less space for sparse graphs. Exam questions may give a diagram and ask you to complete the corresponding matrix or list.
邻接矩阵是一个二维数组，如果从顶点 i 到顶点 j 存在一条边，则元素 [i,j] 为 1（或对应权重）。这使得边的存在性检查为 O(1) 时间，但占用 O(V²) 空间。邻接表为每个顶点存储一个邻居列表，对于稀疏图占用更少空间。考试题目可能会给出一张图，要求你完成相应的矩阵或表。
10. Hash Tables: Fast Key‑based Retrieval | 哈希表：基于键的快速检索
A hash table is a data structure that maps keys to values using a hash function, which computes an index into an array of buckets. The goal is to achieve O(1) average‑case lookup, insertion, and deletion. The Edexcel syllabus touches on the concept of hashing as a method for direct file access, but understanding hash tables helps you grasp random file organisation.
哈希表是一种使用哈希函数将键映射到值的数据结构，该函数计算出一个对应桶数组的索引。其目标是实现平均情况 O(1) 的查找、插入和删除。Edexcel 大纲将哈希概念作为直接文件访问的一种方法提及，但理解哈希表有助于你掌握随机文件组织。
A collision occurs when two different keys hash to the same index. Common collision resolution strategies include open addressing (probing) and chaining (using a linked list at each bucket). In a file context, a hashing algorithm applied to a primary key yields a physical address, enabling direct record retrieval without an index.
当两个不同的键哈希到同一个索引时，就会发生冲突。常见的冲突解决策略包括开放寻址（探查）和链地址法（在每个桶中使用链表）。在文件上下文中，应用于主键的哈希算法会生成一个物理地址，从而无需索引即可直接检索记录。
11. Choosing the Right Data Structure: Exam Scenarios | 选择正确的数据结构：考试场景
Marks are often awarded for justifying your choice of data structure in a given scenario. Consider: is the size fixed or dynamic? Do you need random access or sequential processing? Is memory usage a concern? For example, if you need frequent insertions/deletions in the middle of a collection, a linked list may be better than an array. If you need a last‑in‑first‑out history, a stack is appropriate.
在给定的场景中，往往需要为选择数据结构的合理性打分。请考虑：数据大小是固定还是动态？你需要随机访问还是顺序处理？内存使用是否令人担忧？例如，如果需要在集合中间频繁插入/删除数据，链表可能比数组更合适。如果需要后进先出的历史记录，栈就很合适。
Be ready to compare structures in terms of speed (Big O notation) and memory overhead. A table comparing arrays, linked lists, stacks, and queues can be a useful revision tool. The syllabus also expects you to select and justify the use of records for storing mixed data types and to decide between serial and sequential files based on the need for ordered processing.
准备好在速度（大 O 表示法）和内存开销方面比较数据结构。比较数组、链表、栈和队列的表格是一个有用的复习工具。大纲还希望你能够为存储混合数据类型选择并证明记录的使用，以及根据有序处理的需要在串行文件和顺序文件之间做出选择。
12. Common Pitfalls and Top Exam Tips | 常见错误与高分考试技巧
Many students lose marks by forgetting to initialise pointers (e.g. setting head to NIL for an empty linked list), mishandling boundary conditions (e.g. popping from an empty stack), or using incorrect indexing in array operations (off‑by‑one errors). Practise tracing algorithms with small data sets to build confidence.
许多学生因忘记初始化指针（例如将空链表的表头设为 NIL）、错误处理边界条件（例如从空栈中弹出元素）或在数组操作中使用错误的索引（差一错误）而丢分。通过小数据集跟踪算法来练习，以建立信心。
When writing pseudocode for data structure operations, keep it simple and use meaningful variable names. For tree traversals, clearly state the recursive calls and base case (when node is null). For file algorithms, always include OPEN and CLOSE statements, and check for end‑of‑file. Finally, in evaluation questions, always link the properties of the chosen structure to the specific requirements of the problem.
在为数据结构操作编写伪代码时，请保持简单，使用有意义的变量名。对于树遍历，请清楚说明递归调用和基本情况（当节点为空时）。对于文件算法，务必包含 OPEN 和 CLOSE 语句，并检查文件结束。最后，在评价性问题中，务必将所选结构的特性与问题的具体要求联系起来。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导