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

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

Data structures are the building blocks that define how data is organised, stored, and accessed in computer memory. Choosing the correct structure directly affects the efficiency of an algorithm. In IGCSE Computer Science, you are expected to understand arrays, records, linked lists, stacks, queues, and binary trees, as well as their operations, applications, and trade-offs.

数据结构是定义数据在计算机内存中如何组织、存储和访问的基本构件。选择正确的结构直接影响算法的效率。在 IGCSE 计算机科学中，你需要理解数组、记录、链表、栈、队列和二叉树，以及它们的操作、应用和权衡。

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

A data structure is a specialised format for organising and storing data so that it can be accessed and modified efficiently. Data structures can be static (fixed size, e.g. arrays) or dynamic (size can change, e.g. linked lists). They form the foundation of algorithm design.

数据结构是用于组织和存储数据的专门格式，以便高效地访问和修改数据。数据结构可以是静态的（固定大小，例如数组）或动态的（大小可变，例如链表）。它们构成了算法设计的基础。

Key considerations when choosing a data structure include memory usage, speed of access, ease of insertion/deletion, and whether the data needs to maintain a particular order. In exams, you will often be asked to justify why one structure is better than another for a given scenario.

选择数据结构时的关键考虑因素包括内存使用、访问速度、插入/删除的难易程度，以及数据是否需要保持特定顺序。在考试中，经常会被要求说明在特定场景下为什么某种结构比另一种更好。

2. Arrays – One-Dimensional (1D) | 数组 —— 一维数组

A one-dimensional array is a fixed-size collection of elements of the same data type stored in contiguous memory locations. Each element can be accessed directly using its index, which typically starts at 0. This direct access gives O(1) time complexity for reading or writing an element.

一维数组是固定大小的相同数据类型元素的集合，存储在连续的内存单元中。每个元素可以通过索引直接访问，索引通常从 0 开始。这种直接访问使得读取或写入一个元素的时间复杂度为 O(1)。

However, inserting or deleting an element in the middle requires shifting subsequent elements, which is O(n). Arrays are therefore ideal when the number of elements is known in advance and frequent random access is needed, such as storing daily temperatures for a month.

然而，在数组中间插入或删除元素需要移动后续元素，时间复杂度为 O(n)。因此，当元素数量事先已知并且需要频繁随机访问时，数组是理想的选择，例如存储一个月内的每日温度。

Declaration in pseudocode: DECLARE temperature : ARRAY[1:7] OF REAL

伪代码声明：DECLARE temperature : ARRAY[1:7] OF REAL

Common operations: traversing with a FOR loop, linear search, and calculating totals. Remember bounds! Attempting to access an index outside the declared range causes an index out of bounds error.

常见操作：使用 FOR 循环遍历、线性搜索和计算总和。注意边界！尝试访问声明范围之外的索引会导致索引越界错误。

3. Two-Dimensional Arrays | 二维数组

A two-dimensional array can be visualised as a table with rows and columns. It is declared with two index ranges. For example, DECLARE grid : ARRAY[1:3, 1:4] OF INTEGER creates a 3×4 grid. Each cell is identified by a pair of indices like grid[2,3].

二维数组可以可视化为具有行和列的表格。它使用两个索引范围声明。例如，DECLARE grid : ARRAY[1:3, 1:4] OF INTEGER 创建了一个 3×4 的网格。每个单元格由一对索引标识，如 grid[2,3]。

Iterating through a 2D array requires nested loops – an outer loop for rows and an inner loop for columns. This structure is perfect for representing a chess board, a spreadsheet, or pixel data in an image.

遍历二维数组需要使用嵌套循环——外层循环用于行，内层循环用于列。这种结构非常适合表示棋盘、电子表格或图像中的像素数据。

In memory, a 2D array is still stored linearly, either row by row (row-major order) or column by column. But at IGCSE level, you mainly work with the logical table concept.

在内存中，二维数组仍然线性存储，要么逐行（行优先顺序）或逐列。但在 IGCSE 级别，你主要使用逻辑表的概念。

4. Records – User-Defined Data Types | 记录 —— 用户自定义数据类型

A record is a data structure that groups related fields of possibly different data types under a single name. Each field has an identifier and a data type. Unlike an array, fields are accessed by name, not by numeric index.

记录是一种数据结构，将可能不同数据类型的相关字段归组在一个名称下。每个字段都有一个标识符和数据类型。与数组不同，字段通过名称访问，而不是通过数字索引。

For instance, a Student record might contain fields: name (STRING), age (INTEGER), grade (CHAR). Declaration in pseudocode: TYPE StudentRecord … ENDTYPE

例如，一个 Student 记录可能包含字段：name (STRING), age (INTEGER), grade (CHAR)。伪代码声明：TYPE StudentRecord … ENDTYPE

Records are the foundation of databases and are used extensively when dealing with structured data. In programming, they are similar to structures in some languages.

记录是数据库的基础，在处理结构化数据时被广泛使用。在编程中，它们类似于某些语言中的结构体。

5. Linked Lists – Dynamic Data Chains | 链表 —— 动态数据链

A linked list consists of a sequence of nodes, where each node contains data and a pointer (or link) to the next node in the sequence. The first node is called the head; the last node points to null, indicating the end. Unlike arrays, a linked list does not require contiguous memory; nodes can be stored anywhere, and the list can grow or shrink dynamically.

链表由一系列节点组成，每个节点包含数据和指向序列中下一个节点的指针（或链接）。第一个节点称为头节点；最后一个节点指向 null，表示结尾。与数组不同，链表不需要连续的内存；节点可以存储在任何地方，并且链表可以动态地增长或收缩。

Inserting or deleting a node at the beginning is very efficient, O(1), because only the head pointer needs updating. However, to access the 10th element, you must start at the head and follow 9 links – sequential access, O(n). This makes searching slow unless extra structures are used.

在开头插入或删除节点非常高效，为 O(1)，因为只需要更新头指针。但是，要访问第 10 个元素，必须从头开始跟踪 9 个链接——顺序访问，O(n)。这使得搜索速度较慢，除非使用额外的结构。

Typical applications: implementing stacks and queues dynamically, managing free memory blocks, or representing polynomials.

典型应用：动态实现栈和队列、管理空闲内存块或表示多项式。

A key exam point: be able to draw a diagram showing nodes and arrows, and describe the steps for inserting or deleting a node without breaking the chain.

一个关键的考试要点：能够绘制显示节点和箭头的图表，并描述在不破坏链的情况下插入或删除节点的步骤。

6. Stacks – Last In, First Out (LIFO) | 栈 —— 后进先出

A stack is a linear data structure that follows the Last In, First Out principle. Elements are added (pushed) and removed (popped) from the same end, called the top. A stack has a limited set of operations: push(item), pop(), peek() (or top), and isEmpty()/isFull().

栈是一种遵循后进先出原则的线性数据结构。元素从同一端（称为栈顶）添加（压入）和移除（弹出）。栈有一组有限的操作：push(item)、pop()、peek()（或 top）、以及 isEmpty()/isFull()。

When implementing a stack using an array, a stack pointer (or top index) tracks the current top position. Underflow occurs when trying to pop from an empty stack; overflow occurs when pushing to a full stack. A dynamic stack using a linked list avoids overflow unless memory is exhausted.

当使用数组实现栈时，栈指针（或顶部索引）跟踪当前栈顶位置。当尝试从空栈弹出时发生下溢；当尝试向满栈压入时发生上溢。使用链表的动态栈避免了上溢，除非内存耗尽。

Stacks are used in reverse polish notation evaluation, managing function calls (call stack), undo operations in software, and checking balanced parentheses in expressions.

栈用于逆波兰表示法求值、管理函数调用（调用栈）、软件中的撤销操作以及检查表达式中的括号匹配。

In the exam, expect to trace algorithm given a sequence of push and pop operations, or to write pseudocode for simple stack operations.

在考试中，可能会要求你追踪给定一系列压入和弹出操作后的算法，或者为简单的栈操作编写伪代码。

7. Queues – First In, First Out (FIFO) | 队列 —— 先进先出

A queue is another linear data structure, but it works on a First In, First Out basis. New items are added at the rear (enqueue), and existing items are removed from the front (dequeue). Like a line of people waiting for a bus, the first person to join is the first to leave.

队列是另一种线性数据结构，但它基于先进先出的原则工作。新项在队尾添加（入队），已有项从队首移除（出队）。就像排队等公交车的人一样，最先加入的人最先离开。

Basic operations: enqueue(item), dequeue(), isEmpty(), isFull(). When implemented with an array, we often use a circular queue to reuse empty spaces left by dequeued elements, managed by two pointers (front and rear).

基本操作：enqueue(item)、dequeue()、isEmpty()、isFull()。当用数组实现时，我们经常使用循环队列来重用出队元素留下的空位，由两个指针（front 和 rear）管理。

Queues are widely used in scheduling (CPU task scheduling), buffering (keyboard buffer, print spooler), and breadth-first search algorithms.

队列广泛用于调度（CPU 任务调度）、缓冲（键盘缓冲区、打印后台处理程序）和广度优先搜索算法。

Exam tip: Understand the difference between linear and circular queues, and how to update front and rear pointers after each operation. Linked-list queue avoids shifting problems entirely.

考试提示：理解线性队列和循环队列的区别，以及每次操作后如何更新 front 和 rear 指针。链表队列完全避免了移位问题。

8. Binary Trees – Hierarchical Branching | 二叉树 —— 层次分支

A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. The topmost node is the root. A node with no children is a leaf. Trees represent hierarchical relationships like file systems, organisation charts, or expression trees.

二叉树是一种层次化的数据结构，其中每个节点最多有两个子节点，称为左子节点和右子节点。最顶层的节点是根。没有子节点的节点是叶节点。树结构表示像文件系统、组织结构图或表达式树之类的层次关系。

A binary search tree (BST) adds an ordering property: for any node, all values in the left subtree are smaller, and all values in the right subtree are larger. This allows efficient searching, insertion, and deletion in O(log n) time on average for balanced trees.

二叉搜索树（BST）增加了一个排序属性：对于任意节点，左子树中的所有值都较小，右子树中的所有值都较大。这使得在平衡树中搜索、插入和删除的平均时间复杂度为 O(log n)。

Traversal methods are essential: pre-order (root, left, right), in-order (left, root, right – gives sorted order in BST), and post-order (left, right, root). You need to be able to write traversal results for a given tree.

遍历方法至关重要：前序（根、左、右）、中序（左、根、右——在 BST 中给出排序顺序）和后序（左、右、根）。你需要能够写出给定树的遍历结果。

IGCSE often asks about using a binary tree to represent an arithmetic expression: internal nodes are operators, leaf nodes are operands. Post-order traversal yields the postfix (reverse polish) form.

IGCSE 经常要求使用二叉树表示算术表达式：内部节点是运算符，叶节点是操作数。后序遍历产生后缀（逆波兰）形式。

9. Hashing and Hash Tables (Overview) | 哈希与哈希表（概述）

Hashing is a technique that maps data of arbitrary size to fixed-size values using a hash function. A hash table (or hash map) stores key-value pairs and provides very fast search, insert, and delete operations – ideally O(1).

哈希是一种使用哈希函数将任意大小的数据映射为固定大小值的技术。哈希表（或哈希映射）存储键值对，并提供非常快速的搜索、插入和删除操作——理想情况下为 O(1)。

Collisions occur when two different keys produce the same hash. Common collision resolution methods are chaining (storing multiple items in a linked list at that index) and open addressing (finding another empty slot). Understanding basic hashing helps appreciate fast database indexing.

当两个不同的键产生相同的哈希值时，就会发生冲突。常见的冲突解决方法有链地址法（在该索引处的链表中存储多个项）和开放寻址法（寻找另一个空槽）。理解基本的哈希有助于理解快速的数据库索引。

While hashing may not be a core IGCSE requirement in all syllabi, its concept appears in modern applications and is sometimes introduced as an extension.

虽然哈希可能不是所有 IGCSE 大纲的核心要求，但其概念在现代应用程序中出现，有时会作为扩展内容引入。

10. Comparing Structures: Static vs Dynamic | 比较结构：静态与动态

Static data structures (like arrays) have a fixed size determined at compile time. They are fast for random access but waste memory if not fully utilised and cannot grow once full. Dynamic structures (like linked lists) allocate memory at runtime, provide flexibility, but introduce overheads of storing pointers and slower sequential access.

静态数据结构（如数组）在编译时确定固定大小。它们随机访问速度快，但如果没有完全利用会浪费内存，并且一旦满了就无法增长。动态结构（如链表）在运行时分配内存，提供灵活性，但会带来存储指针的开销和较慢的顺序访问。

Choose an array when the data size is known and fast index-based lookup is needed; choose a linked list when frequent insertions/deletions occur and the maximum size is unpredictable.

当数据大小已知且需要基于索引的快速查找时选择数组；当频繁发生插入/删除且最大大小不可预测时选择链表。

Criterion / 标准	Array / 数组	Linked List / 链表
Memory allocation / 内存分配	Static, contiguous / 静态，连续	Dynamic, non-contiguous / 动态，不连续
Access / 访问	Random, O(1) / 随机，O(1)	Sequential, O(n) / 顺序，O(n)
Insert/Delete at head / 头部插入/删除	O(n) (shift needed) / O(n)（需要移位）	O(1) / O(1)

11. Common Exam Pitfalls and Tips | 常见考试陷阱与技巧

Many students lose marks by confusing arrays and lists, forgetting to initialise counters, or mismanaging pointers in stack/queue diagrams. Always label your diagrams clearly: show the top pointer for a stack, front/rear pointers for a queue, and arrows pointing to the next node in a linked list.

许多学生因混淆数组和列表、忘记初始化计数器或在栈/队列图中错误管理指针而失分。务必清晰地标注你的图表：显示栈的顶部指针、队列的 front/rear 指针，以及链表中指向下一节点的箭头。

When tracing an algorithm involving a stack, work step by step. Record the state of the stack after each push or pop. For binary tree traversal, physically trace the route with your finger on the exam paper: pre-order visits a node the first time you pass it; in-order the second time; post-order the last time.

在追踪涉及栈的算法时，逐步进行。记录每次压入或弹出后栈的状态。对于二叉树的遍历，在试卷上用手指实际追踪路径：前序在你第一次经过节点时访问它；中序在第二次；后序在最后一次。

Never assume an array index starts at 1 – check the pseudocode convention used; most IGCSE syllabi use 1-based indexing for array declarations but some algorithms may use 0-based. Read the question carefully.

绝不要假设数组索引从 1 开始——检查所使用的伪代码约定；大多数 IGCSE 大纲在数组声明中使用基于 1 的索引，但一些算法可能使用基于 0 的。仔细阅读题目。

12. Summary and Revision Checklist | 总结与复习清单

To master the Data Structures topic, ensure you can:

要掌握数据结构这一专题，请确保你能：

Define and give examples of 1D and 2D arrays, records, linked lists, stacks, queues, and binary trees. / 定义并举例说明一维和二维数组、记录、链表、栈、队列和二叉树。
State the main operations for each structure and their typical time complexities. / 陈述每种结构的主要操作及其典型的时间复杂度。
Draw diagrams showing the state of a data structure after a series of operations. / 绘制图表，展示一系列操作后数据结构的状态。
Compare static and dynamic structures, identifying appropriate use cases. / 比较静态和动态结构，确定合适的用例。
Trace and write simple algorithms involving arrays and stacks/queues in pseudocode. / 追踪并编写涉及数组和栈/队列的简单伪代码算法。
Perform pre-order, in-order, and post-order traversals on a binary tree, and construct an expression tree from an expression. / 在二叉树上执行前序、中序和后序遍历，并根据表达式构建表达式树。

Solid understanding of these structures will not only secure marks in the theory paper but also improve your problem-solving skills in the programming paper.

扎实理解这些结构不仅能在理论试卷中确保得分，还能提高你在编程试卷中解决问题的能力。

Published by TutorHao | IGCSE Computer Science Revision Series | aleveler.com

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

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