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

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

Data structures are the building blocks of programs, allowing us to organise and store data efficiently. Understanding how to use arrays, linked lists, stacks, queues, trees, and hash tables will help you write better code and ace the IGCSE AQA Computer Science exam.

数据结构是程序的构建模块，让我们能高效地组织和存储数据。理解如何使用数组、链表、栈、队列、树和哈希表，将帮助你写出更好的代码，并在 IGCSE AQA 计算机科学考试中取得高分。

1. Introduction to Data Structures | 数据结构简介

A data structure is a specialised format for organising, processing, and storing data. The choice of data structure directly affects the performance of algorithms – the same task can be solved much faster when the right structure is used. Static structures like arrays have a fixed size, while dynamic structures like linked lists can grow and shrink during execution.

数据结构是用于组织、处理和存储数据的专用格式。数据结构的选取直接影响到算法的性能——使用正确的结构，同一个任务可以快得多地完成。静态结构（如数组）具有固定的大小，而动态结构（如链表）可在执行过程中增长和收缩。

2. Arrays | 数组

An array is a collection of elements of the same data type, stored in contiguous memory locations. Each element is accessed by an index, starting at 0. Array size must be declared in advance, making it a static data structure. Accessing an element by its index takes constant time, O(1).

数组是一组相同数据类型的元素的集合，存储在连续的内存位置中。每个元素通过索引访问，索引从 0 开始。数组的大小必须预先声明，因此它是一种静态数据结构。通过索引访问元素耗费常数时间 O(1)。

Example:
Declaring an array in pseudocode: DECLARE scores : ARRAY[0:4] OF INTEGER creates space for 5 integers.
Assigning values: scores ← [85, 90, 78, 92, 88]
Reading the third score: OUTPUT scores[2] (outputs 78).

示例：
用伪代码声明数组：DECLARE scores : ARRAY[0:4] OF INTEGER 为 5 个整数创建空间。
赋值：scores ← [85, 90, 78, 92, 88]
读取第三个分数：OUTPUT scores[2]（输出 78）。

Arrays are ideal when the number of items is known and random access is required. However, inserting or deleting elements requires shifting all subsequent elements, which is inefficient (O(n)).

当项目数量已知且需要随机访问时，数组非常理想。但插入或删除元素需要移动所有后续元素，效率较低（O(n)）。

3. Two-Dimensional Arrays | 二维数组

A two-dimensional (2D) array can be thought of as a table with rows and columns. It is declared with two dimensions, e.g. DECLARE grid : ARRAY[0:2, 0:3] OF CHAR creates a 3×4 grid. Access uses both row and column indices: grid[1,2].

二维数组可以想象成具有行和列的表格。它用两个维度声明，例如 DECLARE grid : ARRAY[0:2, 0:3] OF CHAR 创建一个 3 行 4 列的网格。访问时同时使用行索引和列索引：grid[1,2]。

2D arrays are commonly used to represent pixel grids, game boards (like chess), or spreadsheets. Traversal often requires nested loops – one for rows and one for columns.

二维数组常用于表示像素网格、游戏棋盘（如国际象棋）或电子表格。遍历通常需要嵌套循环——一个循环控制行，另一个控制列。

4. Records | 记录

A record is a data structure that groups related data items of possibly different types into a single entity. Each part is called a field. For example, a student record might have fields for name (string), age (integer), and grade (char).

记录是一种数据结构，它将可能属于不同类型的相关数据项组合成一个整体。每个部分称为一个字段。例如，一个学生记录可能包含姓名（字符串）、年龄（整数）和成绩（字符）等字段。

In pseudocode, a record type is defined: TYPE StudentRecord DECLARE name : STRING DECLARE age : INTEGER DECLARE grade : CHAR ENDTYPE. You then declare a variable: DECLARE pupil : StudentRecord and assign values: pupil.name ← 'Alice'.

在伪代码中，定义记录类型：TYPE StudentRecord DECLARE name : STRING DECLARE age : INTEGER DECLARE grade : CHAR ENDTYPE。然后声明变量：DECLARE pupil : StudentRecord，并赋值：pupil.name ← 'Alice'。

Records are fundamental in database systems and when dealing with multiple attributes of an entity. Unlike an array, fields inside a record can be of different data types.

记录在数据库系统以及处理实体的多个属性时是基础。与数组不同，记录内的字段可以是不同的数据类型。

5. Linked Lists | 链表

A linked list is a dynamic data structure where each element (node) contains data and a pointer to the next node. The first node is the head; the last points to null. Because nodes are not stored contiguously, insertion and deletion are efficient (O(1)) if the position is known, but accessing an element requires sequential traversal (O(n)).

链表是一种动态数据结构，其中每个元素（节点）包含数据和一个指向下一个节点的指针。第一个节点是头节点，最后一个节点指向空。由于节点不是连续存储的，如果在已知位置进行插入和删除操作则效率很高（O(1)），但访问元素需要顺序遍历（O(n)）。

Operation	Array	Linked List
Access	O(1)	O(n)
Insert (beginning)	O(n)	O(1)
Delete (known node)	O(n)	O(1)
Memory	Fixed, contiguous	Dynamic, non-contiguous

表：数组与链表的常见操作复杂度对比（大 O 表示法）——访问数组快，插入/删除链表快。

In AQA pseudocode, you may manipulate linked lists with pointers: newNode.next ← currentNode.next to insert, or update head pointers.

在 AQA 伪代码中，你可以用指针操作链表：newNode.next ← currentNode.next 进行插入，或更新头指针。

6. Stacks | 栈

A stack is a Last-In-First-Out (LIFO) structure. You can only add (push) or remove (pop) from the top. Think of a stack of plates – you can only take the top plate. Stacks are widely used in recursion, undo mechanisms, and expression evaluation.

栈是一种后进先出（LIFO）的结构。你只能从顶部添加（压入）或移除（弹出）。想象一摞盘子——你只能拿最顶上的盘子。栈广泛用于递归、撤销机制和表达式求值。

Basic operations: PUSH(stack, item) adds an item, POP(stack) removes and returns the top item, PEEK(stack) returns the top without removing. Underflow occurs if you pop from an empty stack; overflow can occur if a fixed-size stack is full.

基本操作：PUSH(stack, item) 添加元素，POP(stack) 移除并返回栈顶元素，PEEK(stack) 返回栈顶元素但不移除。从空栈弹出会导致下溢；如果固定大小的栈已满，则可能发生上溢。

A stack can be implemented using an array and a pointer to the top index. AQA requires understanding of stack frames in subroutine calls.

栈可以用数组和指向顶部索引的指针来实现。AQA 要求理解子程序调用中的栈帧。

7. Queues | 队列

A queue is a First-In-First-Out (FIFO) structure. Items are added at the rear (enqueue) and removed from the front (dequeue). Real-world examples include print queues and keyboard buffers. Circular queues reuse vacant spaces by wrapping the rear pointer to the start.

队列是一种先进先出（FIFO）的结构。元素在队尾加入（入队），从队头移除（出队）。现实世界的例子包括打印队列和键盘缓冲区。循环队列通过将队尾指针绕回开头来复用空出的空间。

A linear queue may suffer from “false overflow” where the rear reaches the end, even though spaces at the front are empty. A circular queue solves this by wrapping: if rear = maxSize-1 then rear ← 0 else rear ← rear + 1.

线性队列可能会出现“假溢出”，即队尾到达末端，即使队头有空白空间。循环队列通过绕回解决此问题：if rear = maxSize-1 then rear ← 0 else rear ← rear + 1。

Priority queues are an advanced concept where each item has a priority; highest is dequeued first – not directly examined but useful context.

优先队列是一种高级概念，每个项目都有优先级；优先级最高的首先出队——不直接考查，但有助于理解背景。

8. Binary Trees | 二叉树

A binary tree is a hierarchical structure where each node has at most two children: left and right. It is especially useful for searching (binary search tree, BST) and for representing expressions (expression trees). In a BST, for any node, all left descendants are smaller, all right are larger.

二叉树是一种分层结构，每个节点最多有两个子节点：左子节点和右子节点。它对于搜索（二叉搜索树，BST）和表示表达式（表达式树）特别有用。在二叉搜索树中，对任意节点，左子树的所有后代都小于该节点，右子树的所有后代都大于该节点。

Traversal methods: pre-order (root, left, right), in-order (left, root, right) – gives sorted output for a BST, and post-order (left, right, root). AQA expects you to be able to trace these traversals.

遍历方式：前序（根、左、右），中序（左、根、右）——对 BST 可产生有序输出，以及后序（左、右、根）。AQA 期望你能够跟踪这些遍历过程。

Binary trees can be implemented using nodes with left/right pointers. They are dynamic and support efficient insertion and search in O(log n) if balanced.

二叉树可使用带有左/右指针的节点来实现。它们是动态的，并且在平衡时支持 O(log n) 的高效插入和搜索。

9. Hash Tables | 哈希表

A hash table stores key-value pairs and uses a hash function to compute an index (bucket) where a value should be stored or found. Under ideal conditions, insertion, deletion, and lookup are O(1). A good hash function distributes keys uniformly.

哈希表存储键值对，并使用哈希函数计算出一个索引（桶），值应存储或查找于该处。在理想条件下，插入、删除和查找的时间复杂度为 O(1)。一个好的哈希函数能将键均匀分布。

Collisions occur when two different keys produce the same index. AQA covers two collision resolution strategies: open addressing (linear probing) where the next free slot is used, and chaining where each bucket contains a linked list of entries.

当两个不同的键产生相同的索引时，就会发生冲突。AQA 涵盖两种冲突解决策略：开放地址法（线性探测），即使用下一个空闲槽位；以及链地址法，每个桶包含一个条目链表。

Linear probing: while table[index] ≠ null and table[index].key ≠ searchKey index ← (index + 1) MOD tableSize. A disadvantage is clustering, which slows down retrieval.

线性探测：while table[index] ≠ null and table[index].key ≠ searchKey index ← (index + 1) MOD tableSize。其缺点是聚集，这会减慢检索速度。

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

Choosing the most suitable data structure depends on the operations you perform most often and the constraints of memory and speed. There is no single best data structure – it is all about trade-offs.

选择最合适的数据结构取决于你最常执行的操作以及内存和速度的约束。没有一个绝对最好的数据结构——一切在于权衡。

Requirement	Recommended Structure
Frequent random access (known index)	Array
Frequent insert/delete at ends only	Stack or Queue
Requires sorted order, fast search	Binary Search Tree
Key-value pairs with ultra-fast lookup	Hash Table
Unknown size, many insert/delete anywhere	Linked List

要求与推荐结构的对照表：频繁随机访问选数组；只在两端频繁增删选栈或队列；需要有序且快速搜索选二叉搜索树；键值对超快查找选哈希表；大小未知且任意位置频繁增删选链表。

11. Common Algorithms Involving Data Structures | 数据结构常见算法

The AQA specification expects you to understand how data structures underpin searching and sorting. A binary search requires a sorted array and repeatedly halves the search interval – O(log n). A linear search on an array or linked list simply iterates – O(n). Bubble sort uses nested loops over an array and is O(n²).

AQA 大纲期望你理解数据结构是如何支撑搜索和排序的。二分搜索需要一个已排序的数组，并反复将搜索区间减半——O(log n)。对数组或链表的线性搜索则只是迭代——O(n)。冒泡排序使用嵌套循环遍历数组，复杂度为 O(n²)。

When implementing a queue using an array with two pointers (front and rear), enqueue and dequeue are O(1) each, but a linear queue may waste space. A circular queue maintains O(1) and avoids false overflow.

当用数组和两个指针（队头和队尾）实现队列时，入队和出队各自为 O(1)，但线性队列可能浪费空间。循环队列维持 O(1) 并避免了假溢出。

Traversing a binary tree uses recursion or a stack to follow paths, and hash table insertion uses a hash function plus collision handling. Understanding these algorithms helps in writing efficient pseudocode.

遍历二叉树可使用递归或栈来跟踪路径，而哈希表插入使用哈希函数加上冲突处理。理解这些算法有助于编写高效的伪代码。

12. Summary and Exam Tips | 总结与考试技巧

Data structures are a core topic in IGCSE AQA Computer Science. Be prepared to compare static vs dynamic, trace stack and queue operations, draw binary tree traversals, and explain hash table collision resolution. Practise writing pseudocode for array manipulation, linked list insertion, and stack/queue operations.

数据结构是 IGCSE AQA 计算机科学的核心主题。准备好比较静态与动态结构、跟踪栈和队列操作、画出二叉树遍历过程，以及解释哈希表的冲突解决。练习编写数组操作、链表插入以及栈/队列操作的伪代码。

In the exam, you may be asked to choose an appropriate structure for a scenario and justify your choice. Use precise terminology: “LIFO”, “FIFO”, “dynamic”, “contiguous”, “collision”. Always link properties of the structure to the scenario requirements.

在考试中，你可能需要为某个场景选择合适的数据结构并说明理由。请使用精确的术语：“LIFO”、“FIFO”、“动态”、“连续”、“冲突”。始终将结构的特性与场景需求联系起来。

Review the differences between a record and an array: a record groups different data types about one entity, an array stores the same data type about many entities. Both can be combined in the design of a program.

复习记录与数组的区别：记录将关于一个实体的不同数据类型组合在一起，数组则存储关于许多实体的相同数据类型。这两者可以在程序设计中结合使用。

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

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

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