Data Structures Revision for A-Level CCEA Computer Science | A-Level CCEA 计算机：数据结构 考点精讲

📚 Data Structures Revision for A-Level CCEA Computer Science | A-Level CCEA 计算机：数据结构 考点精讲

Data structures are fundamental building blocks in computer science, enabling efficient storage, organisation, and manipulation of data. For the CCEA A-Level specification, a deep understanding of both static and dynamic structures, their implementations, and their typical use cases is essential. This article provides a comprehensive revision guide covering arrays, linked lists, stacks, queues, trees, hash tables, and graphs, with a focus on operations, time complexity, and examination-style reasoning.

数据结构是计算机科学中的基本构建模块，能够实现数据的高效存储、组织与操作。对于 CCEA A-Level 考试大纲，深入理解静态与动态结构、它们的实现方式以及典型应用场景至关重要。本文提供一份全面的复习指南，涵盖数组、链表、栈、队列、树、哈希表与图，重点关注操作、时间复杂度以及考试风格的推理。

1. Static vs Dynamic Data Structures | 静态与动态数据结构

Static data structures, such as arrays, have a fixed size determined at compile time or creation. Memory is allocated contiguously, and the size cannot change during execution. This makes them memory-efficient for predictable workloads, but inflexible when the number of elements varies.

静态数据结构（如数组）在编译时或创建时即确定固定大小。内存连续分配，且在程序执行期间大小不可更改。这使得它们在可预测的工作负载下内存效率高，但当元素数量变化时缺乏灵活性。

Dynamic data structures, like linked lists, can grow and shrink at runtime by allocating memory from the heap. Each node contains data and a reference (pointer) to the next node, allowing flexible memory usage. However, they incur additional overhead due to storing pointers and may suffer from slower access times because elements are not stored contiguously.

动态数据结构（如链表）可在运行时通过从堆中分配内存来扩展和收缩。每个节点包含数据以及指向下一个节点的引用（指针），从而允许灵活使用内存。然而，由于存储指针而带来额外开销，并且因为元素不是连续存储，访问速度可能较慢。

CCEA exam questions often ask you to compare the advantages and disadvantages: arrays provide O(1) random access but O(n) insertion/deletion in the worst case, while linked lists give O(n) access but O(1) insertion/deletion at a known position if a pointer to that node is already available.

CCEA 考试题目常要求你比较其优缺点：数组提供 O(1) 随机访问，但最坏情况下插入/删除为 O(n)；而链表在已知位置且有节点指针时，插入/删除为 O(1)，但访问为 O(n)。

---

2. Arrays: Properties and Operations | 数组：特性与操作

An array is a collection of elements of the same data type stored in contiguous memory locations. Each element can be accessed directly via an index. Arrays can be one-dimensional (a list), two-dimensional (a table/matrix), or multi-dimensional. In CCEA, you need to understand how to perform traversal, insertion, and deletion, considering the shifting of elements required.

数组是同类型元素存储在连续内存位置的集合。每个元素可通过索引直接访问。数组可以是一维（列表）、二维（表格/矩阵）或多维的。在 CCEA 考试中，你需要理解如何执行遍历、插入和删除，并考虑元素所需的移位操作。

Insertion into a full static array is not possible; in a partially filled array, inserting at index k requires shifting elements from k to the last occupied position one place to the right. Similarly, deletion requires left-shifting elements. Both operations have an average time complexity of O(n).

向已满的静态数组中插入数据是不可能的；在未满的数组中，在索引 k 处插入需要将 k 至最后占用位置的元素向右移动一位。类似地，删除需要向左移动元素。这两种操作的平均时间复杂度均为 O(n)。

Binary search on a sorted array is a key algorithmic application, running in O(log n) time. Understanding how index calculations work (low, high, mid) is frequently tested.

在已排序数组上的二分查找是关键算法应用，运行时间为 O(log n)。理解索引计算（low, high, mid）的工作方式常被考查。

---

3. Linked Lists: Singly, Doubly and Circular | 链表：单向、双向与循环

A linked list consists of nodes, each containing a data field and a pointer to the next node. A singly linked list has a head pointer; traversal is unidirectional. A doubly linked list adds a previous pointer, enabling bidirectional traversal. A circular linked list connects the last node back to the first (or head).

链表由节点组成，每个节点包含数据域及指向下一个节点的指针。单向链表有一个头指针，遍历是单向的。双向链表添加了前驱指针，支持双向遍历。循环链表将最后一个节点链接回第一个节点（或头节点）。

Insertion at the head of a singly linked list is O(1): create a new node, set its next to the current head, and update head. Insertion at a given position requires traversal, O(n). Deletion follows similar logic, often needing a trailing pointer to update links.

在单向链表头部插入为 O(1)：创建新节点，将其 next 指向当前头节点，然后更新头节点。在给定位置插入需要遍历，为 O(n)。删除遵循类似逻辑，通常需要尾随指针来更新链接。

Exam questions may ask you to draw node-pointer diagrams or to write pseudocode for operations like ‘insert in order’ or ‘delete a specified value’. Be comfortable managing edge cases (empty list, deleting the head).

考试问题可能要求你绘制节点-指针示意图，或为诸如“按序插入”或“删除指定值”等操作编写伪代码。要熟练掌握边界情况（空链表、删除头节点）的处理。

---

4. Stacks: LIFO Structure and Applications | 栈：后进先出结构及其应用

A stack is an abstract data type (ADT) following Last-In-First-Out (LIFO) principle. Operations include push (add to top), pop (remove from top), and peek/top (inspect top without removal). Stacks can be implemented using arrays (with a top pointer/index) or linked lists (insert/remove at head).

栈是一种遵循后进先出（LIFO）原则的抽象数据类型（ADT）。操作包括 push（入栈，添加到栈顶）、pop（出栈，从栈顶移除）和 peek/top（查看栈顶而不移除）。栈可用数组（配合栈顶指针/索引）或链表（在头部插入/删除）实现。

Key applications include function call management (call stack), undo mechanisms in text editors, expression evaluation (converting infix to postfix using the Shunting Yard algorithm), and backtracking algorithms. CCEA expects you to trace stack states during expression conversion or recursion simulation.

关键应用包括函数调用管理（调用栈）、文本编辑器中的撤销机制、表达式求值（使用调度场算法将中缀转换为后缀），以及回溯算法。CCEA 期望你能在表达式转换或递归模拟中跟踪栈状态。

When implementing with an array, test for stack overflow (full) and underflow (empty). The time complexity for push and pop is O(1).

使用数组实现时，需测试栈溢出（满）和栈下溢（空）。push 和 pop 的时间复杂度为 O(1)。

---

5. Queues: FIFO and Priority Variations | 队列：先进先出及其优先变体

A queue adheres to First-In-First-Out (FIFO). Essential operations: enqueue (add to rear) and dequeue (remove from front). A linear queue implemented with an array can suffer from ‘drifting’ where unused space appears at front; a circular queue solves this by wrapping around indices (rear = (rear+1) mod size).

队列遵循先进先出（FIFO）。基本操作：enqueue（入队，添加到队尾）和 dequeue（出队，从队首移除）。用数组实现的线性队列会出现“漂移”问题，即队首出现未用空间；循环队列通过索引回绕（rear = (rear+1) mod size）解决了该问题。

Priority queues assign a priority to each element; dequeuing removes the highest-priority element. They are often implemented using a heap data structure, but CCEA may focus on conceptual understanding and array-based implementations with insertion order maintained or searching for highest priority.

优先队列为每个元素分配优先级；出队时移除最高优先级的元素。它们通常使用堆数据结构实现，但 CCEA 可能更侧重于概念理解以及基于数组的实现方式（保持插入顺序或搜索最高优先级）。

Applications include print job spooling, operating system process scheduling, and breadth-first search (BFS). Expect to trace queue operations in BFS graph traversal.

应用包括打印作业缓冲池、操作系统进程调度以及广度优先搜索（BFS）。需准备在图的 BFS 遍历中跟踪队列操作。

---

6. Trees: Binary Trees and Traversals | 树：二叉树及其遍历

A tree is a hierarchical data structure with a root node and child nodes forming parent-child relationships. A binary tree has at most two children per node (left and right). A binary search tree (BST) imposes ordering: left subtree values < root < right subtree values.

树是一种层次化数据结构，具有根节点及形成父子关系的子节点。二叉树每个节点最多有两个子节点（左和右）。二叉搜索树（BST）施加排序规则：左子树值 < 根 < 右子树值。

Tree traversal algorithms are critical: pre-order (root, left, right), in-order (left, root, right) – which yields sorted order for a BST – and post-order (left, right, root). You should be able to write or trace recursive procedures and produce traversal sequences from a given tree diagram.

树遍历算法至关重要：前序（根、左、右），中序（左、根、右）——对于 BST 产生有序序列，后序（左、右、根）。你应能编写或跟踪递归过程，并根据给定的树图生成遍历序列。

Insertion into a BST is O(log n) on average (O(n) worst), and searching is similar. Deletion has three cases: leaf node, node with one child, node with two children (replace with in-order successor). CCEA may ask you to draw the tree after successive insertions or deletions.

向 BST 插入平均为 O(log n)（最坏 O(n)），查找类似。删除有三种情况：叶节点、有一个子节点的节点、有两个子节点的节点（用中序后继替换）。CCEA 可能要求你画出连续插入或删除后的树。

---

7. Hash Tables: Hashing and Collision Resolution | 哈希表：哈希与冲突解决

A hash table stores key-value pairs and uses a hash function to compute an index (bucket) for a given key, ideally providing O(1) average case for insert, delete, and search. The hash function should distribute keys uniformly across the array to minimise collisions.

哈希表存储键值对，使用哈希函数为给定键计算索引（桶），理想情况下插入、删除和查找的平均时间复杂度为 O(1)。哈希函数应将键均匀分布到数组中以最小化冲突。

Collisions occur when two distinct keys hash to the same index. Two main resolution methods are: separate chaining (each bucket stores a linked list of entries) and open addressing (linear probing: keep checking next slot until empty; quadratic probing: use quadratic increments).

当两个不同的键散列到相同索引时发生冲突。两种主要解决方法是：分离链接法（每个桶存储一个条目链表）和开放寻址法（线性探测：持续检查下一个槽位直到为空；平方探测：使用平方增量）。

Understand load factor (number of stored elements / table size) and its impact on performance. High load factor increases collisions. Rehashing may be required to resize the table. CCEA questions often involve applying a given hash function, showing the table state after insertions using linear probing or chaining.

理解负载因子（已存元素数 / 表大小）及其对性能的影响。高负载因子会增加冲突。可能需要重新哈希来调整表的大小。CCEA 题目常涉及应用给定哈希函数，展示使用线性探测或链接法插入后的表状态。

---

8. Graphs: Representation and Traversal | 图：表示法与遍历

A graph G = (V, E) consists of vertices (nodes) and edges. Edges can be directed or undirected, weighted or unweighted. Graph representation methods include adjacency matrix (a 2D array where entry [i][j] = 1 or weight) and adjacency list (an array of linked lists, each listing neighbours of a vertex).

图 G = (V, E) 由顶点（节点）和边组成。边可以是有向或无向的，带权或无权。图的表示方法包括邻接矩阵（二维数组，其中 [i][j] = 1 或权重）和邻接表（由链表组成的数组，每个链表列出某顶点的邻居）。

Depth-First Search (DFS) uses a stack (explicitly or via recursion) to explore as far down a branch before backtracking. Breadth-First Search (BFS) uses a queue to explore neighbours level by level. Both traverse connected components and can be used to detect cycles or find paths.

深度优先搜索（DFS）使用栈（显式或通过递归）在回溯前尽可能深地探索分支。广度优先搜索（BFS）使用队列逐层探索邻居。两者均遍历连通分量，并可用于检测环或寻找路径。

For CCEA, you should be able to write adjacency matrices/lists for a given graph, trace DFS/BFS order starting from a specified node, and discuss applications such as shortest path (unweighted via BFS) or topological ordering.

对于 CCEA，你应能为给定图写出邻接矩阵/表，从指定节点开始跟踪 DFS/BFS 顺序，并讨论应用场景，如最短路径（无权图通过 BFS）或拓扑排序。

---

9. Implementing Abstract Data Types (ADTs) with Different Structures | 用不同结构实现抽象数据类型

CCEA papers frequently require you to compare different implementations of the same ADT. For instance, a stack can be implemented by an array (fixed capacity, O(1) operations, memory waste if oversized) or by a dynamic linked list (grows on demand, extra pointer overhead). Similar comparisons apply for queues.

CCEA 试卷常要求比较同一 ADT 的不同实现。例如，栈可用数组实现（固定容量，操作 O(1)，如果过设则浪费内存），或用动态链表实现（按需增长，额外指针开销）。类似的比较也适用于队列。

A dictionary/map ADT can be implemented by an associative array (direct addressing, limited key range), a hash table (fast average O(1), requires good hash function), or a BST (ordered traversal, O(log n) balanced). You should articulate trade-offs in speed, memory, and maintenance (e.g., balancing trees).

字典/映射 ADT 可用关联数组（直接寻址，键范围有限）、哈希表（平均 O(1) 快，需要好的哈希函数）或 BST（有序遍历，平衡时 O(log n)）实现。应能阐述速度、内存和维护（如树的平衡）方面的权衡。

In exam answers, always justify your choice based on the specific requirements of the scenario: expected volume of data, frequency of insertions vs lookups, need for ordering, and memory constraints.

在考试答案中，始终根据场景的具体要求来论证你的选择：预期的数据量、插入与查找的频率、排序需求以及内存限制。

---

10. Algorithm Efficiency and Big O Notation | 算法效率与大 O 表示法

Understanding time and space complexity is vital. Big O notation describes the upper bound of an algorithm’s growth rate as input size n increases. Common complexities: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n^2) quadratic. For data structures, you must recall the average and worst-case complexities of operations.

理解时间与空间复杂度至关重要。大 O 表示法描述了随着输入规模 n 增加，算法增长速率的渐近上界。常见复杂度：O(1) 常数，O(log n) 对数，O(n) 线性，O(n log n) 线性对数，O(n²) 平方。对于数据结构，必须记住操作的平均和最坏情况复杂度。

A summary table can be helpful for revision:

Data Structure	Access	Search	Insertion (avg)	Deletion (avg)
Array	O(1)	O(n)	O(n)	O(n)
Singly Linked List	O(n)	O(n)	O(1)*	O(1)*
Stack (Array-based)	O(1) top	O(n)	O(1)	O(1)
Queue (Circular Array)	O(1) front	O(n)	O(1)	O(1)
Binary Search Tree (balanced)	O(log n)	O(log n)	O(log n)	O(log n)
Hash Table	N/A	O(1) avg	O(1) avg	O(1) avg

*When inserting/deleting at a known position (e.g., with a pointer to the node). *在已知位置（如持有节点指针）时。

You may be asked to analyse pseudocode containing nested loops to determine complexity. Practice identifying dominant terms and ignoring constants.

可能会要求分析包含嵌套循环的伪代码以确定复杂度。练习识别主导项并忽略常数。

---

11. Practical Problem-Solving and Exam Tips | 实践问题解决与应试技巧

Many CCEA questions present a scenario requiring you to select an appropriate data structure and justify your recommendation. For example, a program managing a playlist might benefit from a doubly linked list for easy previous/next navigation. A telephone directory lookup might use a hash table for fast retrieval or a sorted array for range queries.

许多 CCEA 题目会给出一个场景，要求你选择合适的数据结构并说明理由。例如，管理播放列表的程序可能适合用双向链表，因为它便于上一首/下一首导航。电话簿查询可能使用哈希表以实现快速检索，或使用有序数组以支持区间查询。

Practice tracing algorithms on given data. For trees, ensure you can correctly produce pre/in/post order sequences. For graphs, correctly simulate DFS with a stack and BFS with a queue, noting the order of node discovery. Show each step clearly in your answer.

练习在给定数据上跟踪算法。对于树，确保能正确生成前序/中序/后序序列。对于图，用栈正确模拟 DFS，用队列模拟 BFS，并记录节点发现顺序。在答案中清晰显示每一步。

Draw diagrams when helpful. A neat, labelled diagram of a tree or linked list after operations often communicates your understanding more effectively than words alone and can earn marks even if written explanation is incomplete.

适时绘制图表。绘制操作后树或链表的整洁、带标注的示意图，往往比单纯的文字更有效地传达你的理解，即使文字说明不完整也可以得分。

Finally, manage your time: data structure questions may be mixed with other topics. Read carefully to provide exactly what is asked – explanation, trace, pseudocode, or a diagram – and always relate back to the scenario.

最后，管理好时间：数据结构问题可能与其他主题混合。仔细审题，精确作答——要求的是什么：解释、跟踪、伪代码还是图表——并始终联系回给定场景。

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

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