📚 Data Structures Revision Guide for AQA A-Level Computer Science | AQA A-Level 计算机数据结构考点精讲
This comprehensive revision guide covers the essential data structures tested in the AQA A-Level Computer Science specification (7517). You will learn about arrays, lists, stacks, queues, graphs, trees, hash tables and more, with emphasis on their properties, operations and typical use cases. Understanding how to choose and implement the right data structure is a key skill for both the written exam and the non-exam assessment (NEA).
本综合复习指南涵盖了AQA A-Level计算机科学（7517）考试中的核心数据结构。你将学习数组、列表、栈、队列、图、树、哈希表等内容，重点掌握它们的特性、操作和典型应用场景。理解如何选择和实现适当的数据结构是笔试和非考试评估（NEA）的关键技能。
1. Introduction to Data Structures | 数据结构简介
A data structure is a specialised format for organising, processing, retrieving and storing data. It defines how data elements relate to one another and what operations can be performed on them. In the AQA course, you must be able to identify static and dynamic structures and work with abstract data types (ADTs) such as stacks and queues, where the interface is separated from the implementation.
数据结构是一种用于组织、处理、检索和存储数据的专用格式。它定义了数据元素之间的关系以及可对其执行的操作。在AQA课程中，你必须能够识别静态和动态结构，并能使用抽象数据类型（ADT），如栈和队列，这些ADT的接口与实现是分离的。
2. Arrays and Lists | 数组与列表
An array is a static, finite collection of elements of the same data type stored in contiguous memory locations. Each element is accessed using an index, typically starting at 0. AQA pseudocode often uses zero-indexed arrays. A two-dimensional array can be visualised as a table with rows and columns.
数组是一种静态的、有限个相同数据类型元素的集合，存储在连续的内存位置上。每个元素通过索引访问，通常从0开始。AQA伪代码常使用零索引数组。二维数组可以看作由行和列组成的表格。
A list is a more flexible collection that can be dynamic. In Python, for example, a list can hold mixed types and can grow or shrink at runtime. In the exam, you need to know that lists support operations like append, insert, delete and search, and that they may be implemented using an underlying array with dynamic resizing or as a linked list.
列表是一种更灵活的集合，可以是动态的。例如在Python中，列表可以容纳混合类型，并能在运行时增减。在考试中你需要知道列表支持追加、插入、删除和查找等操作，并且它们可以通过底层数组动态调整大小实现，也可以使用链表实现。
When an array is full, inserting a new element requires creating a larger array and copying elements, which is O(n) in the worst case. Accessing an element by index is O(1). A list that uses dynamic arrays has similar characteristics.
当数组已满时，插入新元素需要创建更大的数组并复制元素，最坏情况时间复杂度为O(n)。通过索引访问元素则是O(1)。使用动态数组的列表具有类似的特性。
3. Tuples and Records | 元组与记录
A tuple is an immutable ordered sequence of elements. Once created, its values cannot be changed. Tuples are often used to return multiple values from a function. In AQA pseudocode, a tuple can be written as (value1, value2, …).
元组是不可变的有序元素序列。一旦创建，其值就不能更改。元组通常用于从函数返回多个值。在AQA伪代码中，元组可以写为 (value1, value2, …)。
A record (or structure) is a composite data type that groups together fields of potentially different types under a single name. Each field has a field name. Records are used to represent entities, such as a student record containing firstName, lastName, dateOfBirth. In AQA pseudocode you might define a record using TYPE … ENDTYPE.
记录（或结构体）是一种复合数据类型，它将可能不同类型的字段组合在一个名称下。每个字段都有一个字段名。记录用于表示实体，例如包含firstName、lastName、dateOfBirth的学生记录。在AQA伪代码中，你可以使用 TYPE … ENDTYPE 定义记录。
4. Stacks | 栈
A stack is an abstract data type that follows the Last-In-First-Out (LIFO) principle. The element added most recently is the first to be removed. The primary operations are push(item) to add an item to the top and pop() to remove and return the top item. Other useful operations are peek() or top(), which returns the top item without removing it, and checks like isEmpty() and isFull().
栈是一种遵循后进先出（LIFO）原则的抽象数据类型。最近添加的元素最先被移除。主要操作包括push(item)将元素添加到栈顶，pop()移除并返回栈顶元素。其它有用的操作还有peek()或top()（返回栈顶但不移除）以及isEmpty()和isFull()等检查操作。
A stack can be implemented using an array with a pointer (usually called top) that tracks the index of the last added element. When implementing with an array, you must handle overflow when the array is full. An alternative implementation uses a linked list, where each node points to the node below it, and push/pop modify the head of the list.
栈可以使用一个数组加上一个跟踪最后添加元素索引的指针（通常叫做top）来实现。用数组实现时，必须处理数组满时的上溢。另一种实现使用链表，每个节点指向其下方的节点，push和pop操作修改链表头部。
Typical applications of stacks include managing function calls (call stack), undo mechanisms in editors, backtracking in mazes, and evaluating expressions in postfix notation.
栈的典型应用包括管理函数调用（调用栈）、编辑器中的撤销机制、迷宫中的回溯以及后缀表达式求值。
5. Queues | 队列
A queue is an ADT that operates on a First-In-First-Out (FIFO) basis. Items are added at the rear (enqueue) and removed from the front (dequeue). Like stacks, queues support isEmpty(), isFull() and sometimes a peek() at the front element.
队列是一种遵循先进先出（FIFO）原则的ADT。元素在队尾添加（入队），在队首移除（出队）。与栈类似，队列支持isEmpty()、isFull()，有时还有查看队首元素的peek()。
A linear queue implemented with an array suffers from one-way drift: as items are dequeued, the front moves forward, eventually causing overflow even when free space remains. A circular queue overcomes this by treating the array as a ring, using two pointers (front and rear) that wrap around to index 0 when reaching the end.
使用数组实现的线性队列会出现单向漂移：随着元素出队，队首指针前移，最终即使还有空闲空间也可能导致溢出。循环队列通过将数组视为环形来克服这一问题，使用两个指针（front和rear），当到达数组末尾时回绕到索引0。
Priority queues assign a priority to each element; the element with the highest priority is dequeued first. They are commonly implemented with a heap data structure. Queues are used in print spooling, keyboard buffers and breadth-first search in graphs.
优先队列为每个元素分配一个优先级；优先级最高的元素最先出队。通常使用堆数据结构实现。队列用于打印假脱机、键盘缓冲区和图的广度优先搜索。
6. Linked Lists | 链表
A linked list is a dynamic data structure consisting of a sequence of nodes. Each node contains data and a pointer (or link) to the next node. The list is accessed via a head pointer; the last node points to a null value. Because nodes are not stored contiguously, insertion and deletion can be done in O(1) if the position is known, simply by updating pointers.
链表是一种动态数据结构，由一系列节点组成。每个节点包含数据和指向下一个节点的指针（或链接）。链表通过头指针访问；最后一个节点指向空值。由于节点不连续存储，如果已知位置，插入和删除操作只需更新指针，时间复杂度为O(1)。
In a doubly linked list, nodes have both a next and a previous pointer, allowing traversal in both directions. A circular linked list has the last node pointing back to the first node. Linked lists require more memory than arrays due to the storage of pointers, and they do not allow direct (random) access to an element by index – you must traverse from the head, which is O(n).
在双向链表中，节点同时具有next和previous指针，支持双向遍历。循环链表的最后一个节点指向第一个节点。由于需要存储指针，链表比数组需要更多内存，而且不能通过索引直接（随机）访问元素——必须从头遍历，时间复杂度为O(n)。
Comparing arrays and linked lists: arrays provide fast random access and less memory overhead, but insertion and deletion in the middle are expensive. Linked lists excel at frequent insertions and deletions, especially near the head, but search is slow and memory usage is higher.
数组与链表的比较：数组提供快速随机访问，内存开销较小，但在中间插入和删除代价高。链表擅长频繁的插入和删除，特别是在头部附近，但搜索速度慢，内存占用更高。
7. Graphs | 图
A graph consists of a set of vertices (or nodes) connected by edges. Edges can be directed (one-way, shown with an arrow →) or undirected. A weighted graph assigns a numeric weight to each edge, representing cost, distance or capacity.
图由一组通过边连接的顶点（或节点）组成。边可以是有向的（单向，用箭头 → 表示）或无向的。加权图为每条边分配一个数值权重，表示成本、距离或容量。
Graphs can be represented using an adjacency matrix, a 2D array where the cell [i][j] stores 1 (or the weight) if an edge exists, and 0 otherwise. This is memory-intensive for sparse graphs but allows O(1) edge existence check. An adjacency list stores for each vertex a list of its adjacent vertices; it is memory-efficient and more suitable for sparse graphs.
图可以使用邻接矩阵表示，这是一个二维数组，如果存在边，单元格[i][j]存储1（或权重），否则为0。对于稀疏图这种方法内存消耗大，但允许O(1)边存在性检查。邻接表为每个顶点存储一个相邻顶点列表，内存效率高，更适合稀疏图。
Common graph traversals include depth-first search (DFS) using a stack (explicitly or via recursion) and breadth-first search (BFS) using a queue. AQA often tests your ability to trace such algorithms on a given graph.
常见的图遍历包括深度优先搜索（DFS），使用栈（显式或通过递归）实现，以及广度优先搜索（BFS），使用队列实现。AQA经常测试你根据给定图追踪这些算法的能力。
8. Trees | 树
A tree is a connected, undirected graph with no cycles. It consists of a root node, parent-child relationships, and leaf nodes (nodes with no children). A binary tree restricts each node to have at most two children, referred to as left child and right child.
树是一种无环的连通无向图。它由根节点、父子关系和叶节点（无子节点的节点）组成。二叉树限制每个节点最多有两个子节点，分别称为左子和右子。
A binary search tree (BST) maintains an ordering property: for any node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater. This enables efficient searching, insertion and deletion with average time complexity O(log n). However, an unbalanced BST degenerates to O(n) in the worst case.
二叉搜索树（BST）维护一个有序性质：对任意节点，其左子树中的所有值均小于该节点的值，右子树中的所有值均大于该节点的值。这使得高效搜索、插入和删除成为可能，平均时间复杂度为O(log n)。但非平衡的BST在最坏情况下退化为O(n)。
Tree traversals are pre-order (visit root, then left subtree, then right subtree), in-order (left, root, right) and post-order (left, right, root). In-order traversal of a BST yields values in ascending order. Applications of trees include expression trees for arithmetic expressions, file system hierarchies, and trie structures for efficient string searching.
树的遍历方式包括前序（访问根，然后左子树，最后右子树）、中序（左，根，右）和后序（左，右，根）。对BST进行中序遍历可得到升序序列。树的应用包括算术表达式的表达式树、文件系统层次结构，以及用于高效字符串搜索的trie结构。
9. Hash Tables and Dictionaries | 哈希表与字典
A hash table stores key-value pairs and uses a hash function to compute an index (bucket) from the key. An ideal hash function distributes keys uniformly to minimise collisions. The average time complexity for insertion, deletion and lookup is O(1), making hash tables extremely efficient for data retrieval.
哈希表存储键值对，并使用哈希函数根据键计算索引（桶）。理想的哈希函数将键均匀分布，以最小化碰撞。插入、删除和查找的平均时间复杂度为O(1)，使哈希表在数据检索方面极其高效。
Collisions occur when two different keys hash to the same index. AQA expects you to be familiar with two resolution strategies: separate chaining (each bucket holds a linked list of entries that hashed to that index) and open addressing (linear probing, where upon collision the algorithm checks the next available slot).
当两个不同的键哈希到相同索引时会发生碰撞。AQA要求你熟悉两种解决策略：分离链接法（每个桶保存一个散列到该索引的条目链表）和开放寻址法（线性探测，碰撞时算法检查下一个可用槽位）。
A dictionary is an abstract data type that maps keys to values, often implemented using a hash table. In the exam, you may be asked to trace a simple hash table with a given hash function and show insertions with collision handling.
字典是一种将键映射到值的抽象数据类型，通常使用哈希表实现。考试中可能会要求你使用给定的哈希函数跟踪一个简单哈希表，并展示带碰撞处理的插入过程。
10. Static vs Dynamic Data Structures | 静态与动态数据结构
Static data structures such as arrays have a fixed size determined at compile time. Memory is allocated once and cannot be changed. They are simple to implement and offer fast, predictable access, but they waste memory if the allocated size is larger than needed, and they cannot grow beyond their initial capacity.
静态数据结构（如数组）有在编译时确定的固定大小。内存一次性分配且无法更改。实现简单，访问速度快且可预测，但如果分配大小超过需求会浪费内存，且不能超过初始容量。
Dynamic data structures such as linked lists, trees and graphs allocate memory at runtime and can grow or shrink as needed. They are more memory-efficient for varying numbers of elements, but they introduce overhead from pointers and potentially slower access due to non-contiguous memory.
动态数据结构（如链表、树和图）在运行时分配内存，并可按需增长或收缩。对于元素数量变动的情况，内存利用更高效，但因为指针带来额外开销，且可能因内存不连续导致访问速度较慢。
The choice between static and dynamic structures depends on the requirements: if the maximum size is known and random access is crucial, arrays are suitable. If frequent resizing or unpredictable volumes are expected, dynamic structures are preferred.
选择静态还是动态结构取决于需求：如果已知最大尺寸且随机访问至关重要，数组是合适的。如果预期频繁调整大小或数据量不可预测，则优先选择动态结构。
11. Choosing the Right Data Structure | 选择合适的数据结构
Selecting a data structure involves analysing the operations that will be performed most frequently. For quick lookups by key, a hash table or BST is appropriate. For ordered traversal or range queries, a balanced BST is better. If the application requires LIFO behaviour, a stack is the natural choice; for FIFO, a queue.
选择数据结构需要分析最频繁执行的操作。对于按键快速查找，哈希表或BST适用。对于有序遍历或范围查询，平衡BST更好。如果应用需要LIFO行为，栈是自然的选择；对于FIFO，则是队列。
If the data volume is fixed and elements need to be accessed by position, an array is ideal. When elements are frequently added or removed from endpoints, a linked list (or a double-ended queue) can be efficient. Graphs are the go-to structure for modelling networks and relationships.
如果数据量固定且元素需要按位置访问，数组是理想选择。当元素频繁在端点处添加或移除时，链表（或双端队列）效率较高。图是建模网络和关系的首选结构。
Space complexity is also a factor: adjacency matrices for dense graphs are acceptable, but sparse graphs are better represented with adjacency lists. Consider the programming environment and built-in support; for example, Python lists are versatile but may hide implementation details that affect performance.
空间复杂度也是一个因素：稠密图使用邻接矩阵可以接受，但稀疏图用邻接表表示更好。还要考虑编程环境和内置支持；例如，Python的list很通用，但可能隐藏了影响性能的实现细节。
12. Exam Tips and Common Pitfalls | 考试技巧与常见陷阱
In AQA written papers, you may be asked to draw or trace the state of a data structure after a series of operations. Always label pointers clearly (e.g. front, rear, top, head) and show null pointers explicitly. For linked lists, draw boxes for nodes and arrows for pointers; do not leave dangling pointers.
在AQA笔试中，你可能需要绘制或跟踪一系列操作后数据结构的状态。务必清晰地标出指针（如front, rear, top, head），并显式标出空指针。对于链表，为节点画方框，指针画箭头；不要留下悬空指针。
Distinguish between an ADT and its implementation. For example, a stack is defined by its behaviour, not by whether it uses an array or a linked list. The exam may ask you to implement a stack using pseudocode; ensure you handle overflow and underflow errors correctly.
区分ADT及其实现。例如，栈由其行为定义，而非它使用了数组还是链表。考试可能要求你用伪代码实现栈；确保正确处理上溢和下溢错误。
When working with hash tables, practise showing step-by-step insertion using a given hash function and collision method. Check that you calculate the initial bucket index correctly and apply the probing sequence or chain insertion as required. Be careful with the distinction between a hash table and a dictionary ADT.
处理哈希表时，要练习使用给定的哈希函数和碰撞方法逐步展示插入过程。检查是否正确计算了初始桶索引，并按要求应用探测序列或链插入。注意区分哈希表和字典ADT。
Memorise the typical time complexities of basic operations for each data structure, but do not simply regurgitate – be prepared to justify your reasoning in the context of a specific scenario.
记住每种数据结构基本操作的典型时间复杂度，但不要只是机械背诵——要准备好结合具体场景论证你的理由。
Finally, pay attention to the wording of questions: if asked to describe how a data structure works, focus on the principle and operations; if asked to evaluate, compare alternatives using criteria such as speed, memory and ease of implementation.
最后，注意题目措辞：如果要求描述数据结构如何工作，重点说明原理和操作；如果要求评价，则使用速度、内存和实现难易等标准比较替代方案。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导