📚 A-Level CIE Computer Science: Data Structures Revision Guide | A-Level CIE 计算机：数据结构 考点精讲
Data structures form the backbone of efficient algorithm design and are a core part of the CIE A-Level Computer Science syllabus (9618). Understanding how to choose, implement, and manipulate structures such as arrays, linked lists, stacks, queues, trees, and hash tables is essential for success in both Paper 3 and Paper 4. This revision guide breaks down every key concept, compares performance, and highlights common exam pitfalls to help you score top marks.
数据结构是高效算法设计的基石，也是 CIE A-Level 计算机科学 (9618) 课程的核心内容。理解如何选择、实现和操作数组、链表、栈、队列、树、哈希表等结构，对于在 Paper 3 和 Paper 4 中取得高分至关重要。本考点精讲逐一剖析关键概念，对比性能表现，并指出常见考试误区，助你稳夺高分。
1. Abstract Data Types (ADTs) | 抽象数据类型
An abstract data type (ADT) is a logical model that defines a collection of data and the operations that can be performed on it, completely independent of any implementation details. Examples include Stack, Queue, List, and Dictionary. In CIE exams, you must be able to describe an ADT’s behaviour, state its operations (e.g., push, pop, isEmpty for a Stack), and outline how it might be implemented using arrays or linked lists. The separation of interface from implementation is a fundamental design principle that allows the same ADT to be realised in different ways without changing the program that uses it.
抽象数据类型 (ADT) 是一个逻辑模型，它定义了一组数据以及可对这些数据执行的操作，完全独立于任何实现细节。常见的 ADT 有栈 (Stack)、队列 (Queue)、列表 (List) 和字典 (Dictionary)。在 CIE 考试中，你需要能够描述 ADT 的行为，列出其操作（例如栈的 push、pop、isEmpty），并概述如何用数组或链表来实现它。接口与实现分离是基本的设计原则，使得同一个 ADT 能够以不同方式实现而无需修改调用它的程序。
When answering exam questions, always distinguish between the logical ADT and its physical representation. For example, a Stack ADT requires LIFO (Last In, First Out) behaviour; it can be implemented with a static array (with a top pointer) or a dynamic linked list. The ADT concept also appears in the context of user-defined types and file organisation in the syllabus, so you must be comfortable defining operations and explaining the advantages of abstraction.
在答题时，一定要区分逻辑上的 ADT 和它的物理表示。例如，栈 ADT 要求后进先出 (LIFO) 行为；它可以用静态数组（配合一个 top 指针）或动态链表来实现。ADT 概念还出现在考纲的用户自定义类型和文件组织中，因此你必须能够定义操作并解释抽象的优势。
2. Arrays – Static and Dynamic | 数组 – 静态与动态
An array is a contiguous block of memory that stores elements of the same data type, accessed via an index. The key strength is that index-based access runs in constant time, O(1), making arrays ideal for situations where random access is frequent. However, static arrays have a fixed size determined at compile time; dynamic arrays can be resized at runtime by allocating new memory and copying elements, but this incurs O(n) cost. In CIE pseudocode, arrays are declared using keywords like DECLARE and indices start from 1 or 0 depending on the question’s convention.
数组是一块连续的内存区域，存储相同数据类型的元素，并通过索引访问。其核心优势是基于索引的访问可在常数时间 O(1) 内完成，非常适合需要频繁随机访问的场景。但是，静态数组的大小在编译时确定且不可改变；动态数组可以在运行时通过分配新内存并拷贝元素来调整大小，但这一操作代价为 O(n)。在 CIE 伪代码中，数组使用 DECLARE 等关键字声明，索引起始值视题目约定可能为 1 或 0。
Two-dimensional arrays (matrices) are used to represent grids, tables, or pixels. They are stored in row-major or column-major order in memory. Inserting or deleting an element in the middle of an array requires shifting all subsequent elements, resulting in O(n) time. Hence arrays are poor choices when frequent insertions/deletions are needed. You may be asked to trace or write algorithms that process 1D and 2D arrays, so practise nested loops and boundary checks carefully.
二维数组（矩阵）用于表示网格、表格或像素。它们在内存中按行优先或列优先的方式存储。在数组中间插入或删除一个元素需要移动后续的所有元素，时间复杂度为 O(n)。因此，当需要频繁插入/删除时，数组是不良选择。考试中可能要求你追踪或编写处理一维和二维数组的算法，请仔细练习嵌套循环和边界检查。
3. Linked Lists | 链表
A linked list is a dynamic data structure in which each node contains a data field and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory, allowing efficient O(1) insertion and deletion once the position is known. However, random access is not possible; to reach the k-th element you must traverse from the head node, taking O(k) time. CIE frequently tests your ability to draw nodes, update pointers, and write algorithms for singly, doubly, and circular linked lists.
链表是一种动态数据结构，每个节点包含一个数据域和一个指向下一节点的指针。与数组不同，链表不需要连续的内存空间，一旦知道插入/删除的位置，就能以 O(1) 时间完成操作。然而，链表不支持随机访问；要访问第 k 个元素，必须从头节点开始遍历，耗时 O(k)。CIE 考试经常考查绘制节点、更新指针以及编写单向、双向和循环链表的算法。
Singly linked lists hold one pointer per node; they are simple to implement but only allow forward traversal. Doubly linked lists add a previous pointer, enabling backward traversal at the cost of extra memory. Circular linked lists join the last node back to the head, useful for scheduling tasks. A common exam task is inserting or deleting a node at the start, end, or middle of a list — you must carefully manage the head pointer and avoid memory leaks.
单向链表每个节点仅有一个指针，实现简单但只能正向遍历。双向链表增加了一个指向前驱的指针，可以反向遍历，但需要更多内存。循环链表将最后一个节点指向头节点，常用于任务调度。考试中常见的任务是在链表头部、尾部或中间插入/删除节点——你必须小心管理头指针并避免内存泄漏。
| Feature / 特性 | Array | Linked List |
|---|---|---|
| Memory allocation | Static (or dynamic resizing) | Dynamic, non-contiguous |
| Random access | O(1) | O(n) |
| Insertion/deletion | O(n) (shifting needed) | O(1) (if position known) |
| Memory overhead | Low — only data | Higher — stores pointers |
4. Stacks – LIFO Data Structure | 栈 – 后进先出数据结构
A stack is an ADT that follows the Last In, First Out principle. The essential operations are push (add to top), pop (remove from top), and peek (or top, which returns the top item without removing it). Stacks can be implemented with an array (adding a top index) or a linked list (adding/removing at the head). In CIE exams, you will be asked to trace stack operations, write algorithms for converting infix to postfix expressions, or describe how a call stack manages subroutine return addresses.
栈是一种遵循后进先出 (LIFO) 原则的 ADT。基本操作包括 push（压入栈顶）、pop（弹出栈顶）和 peek（或 top，返回栈顶元素但不移除）。栈可以用数组（维护一个 top 索引）或链表（在头部添加/删除）实现。CIE 考试会要求你追踪栈操作、编写中缀表达式转后缀表达式的算法，或描述调用栈如何管理子程序的返回地址。
An important application is expression evaluation. For example, using a stack to evaluate a postfix expression: scan tokens; when encountering an operand, push it; when encountering an operator, pop the required number of operands, apply the operator, and push the result. Stack overflow and underflow conditions must be checked — overflow occurs when pushing to a full array-based stack; underflow when popping from an empty stack. Always initialise the top pointer to -1 (or 0, depending on convention) and update it correctly.
一个重要的应用是表达式求值。例如，用栈计算后缀表达式：扫描记号；遇到操作数则压栈；遇到运算符则弹出所需数量的操作数，进行运算，再压入结果。必须检查栈溢出和下溢——向满的数组栈压入时发生溢出，从空栈弹出时发生下溢。务必初始化 top 指针为 -1（或 0，视约定而定）并正确更新。
5. Queues – FIFO and Variations | 队列 – 先进先出及其变体
A queue is an ADT based on First In, First Out (FIFO). Operations include enqueue (add to rear) and dequeue (remove from front). A linear queue implemented with an array suffers from the problem of unusable space at the front after dequeue operations. The circular queue overcomes this by wrapping the rear pointer around using modulo arithmetic, making it the preferred array-based implementation. You must be able to draw circular queues and calculate the number of items using (rear – front + maxSize) mod maxSize.
队列是一种基于先进先出 (FIFO) 的 ADT。操作包括 enqueue（入队，加入队尾）和 dequeue（出队，移除队首）。用数组实现的线性队列在出队后会产生无法使用的队首空间。循环队列通过使用取模运算让队尾指针折回，克服了该问题，因此是首选的数组实现方式。你必须能够画出循环队列并利用公式 (rear – front + maxSize) mod maxSize 计算元素个数。
Priority queues assign a priority to each element; the highest-priority item is dequeued first, regardless of insertion order. They are typically implemented using a heap, but CIE may present simple array-based priority queues where insertion maintains sorted order. Queues are widely used in simulations, print spooling, and breadth-first traversal of graphs. When tracing or coding, pay attention to empty and full conditions: a circular queue is empty when front = rear, and full when the next position of rear equals front.
优先队列为每个元素赋予优先级；无论插入顺序如何，优先级最高的元素先出队。它们通常用堆实现，但 CIE 考试中可能给出简单的基于数组的优先队列，其插入操作会保持有序。队列广泛应用于模拟、打印缓冲和图广度优先遍历。在追踪或编程时，注意空和满的条件：循环队列空时为 front = rear，满时 rear 的下一个位置等于 front。
6. Trees – Binary Trees and Binary Search Trees | 树 – 二叉树与二叉搜索树
A tree is a hierarchical ADT consisting of nodes connected by edges, with a single root. In a binary tree, each node has at most two children: left and right. Important terminology: degree (number of children), leaf (node with no children), depth (distance from root), and height (maximum depth). A binary search tree (BST) is an ordered binary tree where, for any node, all values in the left subtree are smaller and all values in the right subtree are greater. BSTs support search, insert, and delete operations in O(log n) average time, though worst case is O(n) if the tree becomes unbalanced.
树是一种分层 ADT，由节点和连接它们的边组成，有唯一的根节点。在二叉树中，每个节点最多有两个孩子：左子和右子。重要术语：度（孩子数）、叶节点（无孩子的节点）、深度（到根的距离）和高度（最大深度）。二叉搜索树 (BST) 是一种有序二叉树，对于任意节点，其左子树的所有值均小于该节点，右子树的所有值均大于该节点。BST 支持搜索、插入和删除操作，平均时间复杂度为 O(log n)，但如果树变得不平衡，最坏情况为 O(n)。
Tree traversal is essential for processing all nodes. The three depth-first traversals are: pre-order (visit root, left, right), in-order (left, root, right), and post-order (left, right, root). For a BST, in-order traversal visits nodes in ascending order. CIE questions may ask you to write recursive or iterative pseudo-code for these traversals, or to reconstruct a tree from given traversal sequences. A simple recursive pseudo-code for in-order: procedure IN(node) if node != null then IN(node.left) OUTPUT node.data IN(node.right) end procedure.
遍历是处理所有节点的关键。三种深度优先遍历为：先序（根-左-右）、中序（左-根-右）和后序（左-右-根）。对于 BST，中序遍历将按升序访问节点。CIE 考题可能要求你编写这些遍历的递归或迭代伪代码，或者根据给定的遍历序列重建二叉树。一个简单的中序递归伪代码为：process IN(node) if node != null then IN(node.left) 输出 node.data IN(node.right) end process。
7. Hash Tables | 哈希表
A hash table is a data structure that maps keys to values for extremely fast average-case O(1) lookups. It uses a hash function to compute an index into an array of buckets. A good hash function distributes keys uniformly to minimise collisions. Collision resolution strategies tested in CIE include open addressing (e.g., linear probing, where the next free slot is used) and closed addressing (chaining, where each bucket holds a linked list of items). You must be able to simulate insertion with linear probing and explain the impact of clustering.
哈希表是一种将键映射到值的数据结构，可实现极快的平均 O(1) 查找。它使用哈希函数计算一个索引，对应存储桶数组中的位置。一个好的哈希函数能均匀分布键以最小化冲突。CIE 考查的冲突解决策略包括开放定址法（如线性探测，即使用下一个空闲槽）和封闭定址法（链接法，每个桶持有一个链表）。你必须能够模拟带线性探测的插入并解释聚集现象的影响。
Load factor (number of items / table size) directly affects performance: a high load factor increases collisions and reduces efficiency. Rehashing involves creating a larger table and re-inserting all items, often triggered when the load factor exceeds a threshold (e.g., 0.7). Hash tables are ideal for implementing dictionaries, symbol tables, and database indexing. When answering exam questions, always state the hash function explicitly, show the index calculation, and update the table carefully step by step.
装载因子（元素数 / 表大小）直接影响性能：高装载因子会增加冲突并降低效率。再哈希会创建一个更大的表并重新插入所有元素，通常在装载因子超过阈值（如 0.7）时触发。哈希表非常适合实现字典、符号表和数据库索引。答题时，务必明确给出哈希函数，显示索引计算过程，并逐步仔细更新表格。
8. Graphs – Basic Concepts and Representations | 图 – 基本概念与表示
A graph is an ADT consisting of a set of vertices (nodes) and edges (connections). Graphs can be directed (edges have a direction) or undirected, weighted (edges carry a value) or unweighted. In CIE A-Level, understanding graph representation is crucial for solving problems like shortest path and network routing. The two standard representations are adjacency matrix and adjacency list. An adjacency matrix is a 2D array where cell [i][j] = 1 (or weight) if an edge exists; it offers O(1) edge query but uses O(V²) space. An adjacency list stores a list of neighbours per vertex; it uses less memory for sparse graphs and performs faster iteration over neighbours.
图是一种由顶点集和边集组成的 ADT。图可以是有向的（边有方向）或无向的，加权的（边带有权值）或非加权的。在 CIE A-Level 中，理解图的表示对于解决最短路径和网络路由等问题至关重要。两种标准表示法是邻接矩阵和邻接表。邻接矩阵是一个二维数组，若有边则 cell [i][j] = 1（或权值）；它支持 O(1) 的边查询，但空间复杂度为 O(V²)。邻接表为每个顶点存储一个邻居列表；稀疏图更节省内存，且邻居迭代速度更快。
Traversal algorithms, while studied more deeply in algorithm topics, are often linked to graph representation. A stack can be used for depth-first traversal (DFS) and a queue for breadth-first traversal (BFS). Examiners may ask you to draw a graph from a description, represent it with a given method, and then discuss the trade-offs. Make sure you can convert between matrix and list representations and explain the impact on searching for all neighbours of a node.
遍历算法虽在算法专题中深入讨论，但常与图的表示相关联。深度优先遍历 (DFS) 可用栈实现，广度优先遍历 (BFS) 可用队列实现。考官可能要求你根据描述画出图、用给定方法表示它，并讨论权衡。务必确保能够转换矩阵和列表表示法，并解释其对搜索节点所有邻居的影响。
9. Choosing the Right Data Structure | 选择合适的数据结构
Selecting an appropriate data structure is a skill that CIE explicitly tests. The decision depends on the required operations, frequency of accesses, memory constraints, and whether the data size is known in advance. For frequent search by key with no ordering required, a hash table is preferred. For ordered traversal and range queries, a balanced BST is better. If the application demands frequent insertions/deletions at both ends, a doubly linked list or deque may suit. When memory is critical and data is essentially static, arrays are the most space-efficient.
选择合适的数据结构是 CIE 明确考查的一项技能。决策取决于所需操作、访问频率、内存限制以及数据规模是否预先已知。若需按键频繁查找且不要求排序，首选哈希表。对于需要有序遍历和范围查询的场景，平衡 BST 更佳。如果应用要求在两端频繁插入/删除，双向链表或双端队列可能适合。当内存紧张且数据基本静态时，数组最为节省空间。
In extended response questions, you must justify your choice with reference to time complexity. For example, a stack is suitable for undo functionality because it provides LIFO behaviour and operates in O(1) push/pop. A queue is suitable for a printer buffer as it maintains FIFO order. Recognising the limitations — such as the fixed size of a static array or the O(n) search in an unsorted array — is equally important. Use the table below to compare typical scenarios.
在拓展回答题中，你必须结合时间复杂度来论证你的选择。例如，栈适合撤销功能，因为它提供 LIFO 行为且 push/pop 为 O(1)。队列适合打印缓冲，因为它保持 FIFO 顺序。同样重要的是认识到局限性——例如静态数组的大小固定，或者未排序数组的 O(n) 搜索。使用下表比较典型场景。
| Requirement / 需求 | Recommended Structure | Reason |
|---|---|---|
| Fast look-up by key, no order | Hash Table | Average O(1) search |
| Maintain items in sorted order | Binary Search Tree | O(log n) search and ordered traversal |
| Process items in arrival order | Queue | FIFO O(1) enqueue/dequeue |
| Reverse order processing | Stack | LIFO O(1) push/pop |
| Frequent insert/delete at ends | Doubly Linked List | O(1) if reference known |
10. Examination Tips and Common Pitfalls | 考试技巧与常见误区
First, always read the question carefully to distinguish between an ADT and its implementation. If asked to give operations of a stack ADT, list push, pop, isEmpty, etc., without referring to arrays or pointers. Second, when updating linked list pointers in pseudocode, draw a diagram before writing any code — this dramatically reduces errors. Remember to handle boundary cases: empty list, single-node list, head/tail operations. Third, in hash table questions, show all steps of the hashing process, including collision resolution, and state the final table clearly. Misplacing an item due to a missed probe is a common mistake.
第一，仔细读题以区分 ADT 与其实现。如果要求给出栈 ADT 的操作，列出 push、pop、isEmpty 等，而不要提及数组或指针。第二，在编写链表指针更新的伪代码前，先画图——这将极大减少错误。务必处理边界情况：空链表、单节点链表、头部/尾部操作。第三，在哈希表题目中，显示哈希全过程的所有步骤，包括冲突解决，并清晰地给出最终表格。因遗漏探测而导致元素放置错误是常见失分点。
Fourth, for trees, practise writing recursive algorithms elegantly. The base case (null node) must be handled first. In-order traversal is the most frequently examined. Fifth, when comparing data structures, always link your justification to the properties of the application (e.g., ‘a linked list is chosen because the number of records is unknown and insertions are frequent’). Avoid vague statements like ‘it is faster’ — be specific: ‘array access is O(1), whereas linked list access is O(n) for arbitrary positions.’ Finally, never forget to initialise variables and pointers; uninitialised pointers cause run-time errors and cost marks in desk-checking tasks.
第四，对于树，练习优雅地编写递归算法。必须先处理递归基（空节点）。中序遍历是最常考的。第五，在比较数据结构时，务必将论证与应用特性联系起来（例如，“选择链表是因为记录数量未知且插入频繁”）。避免诸如“它更快”这样模糊的陈述——要具体：“数组访问为 O(1)，而链表访问任意位置为 O(n)”。最后，永远不要忘记初始化变量和指针；未初始化的指针会导致运行时错误，并在桌面检查任务中扣分。
Pseudocode adherence to CIE style is marked — use keywords in uppercase (DECLARE, IF…THEN…ENDIF, FOR…NEXT, WHILE…ENDWHILE, PROCEDURE…ENDPROCEDURE) and maintain consistent indentation. When desk-checking, create a clear table with columns for variables and update them line by line. These small efforts make a significant difference to your grade.
遵循 CIE 风格的伪代码是被评分的——使用大写的关键字（DECLARE, IF…THEN…ENDIF, FOR…NEXT, WHILE…ENDWHILE, PROCEDURE…ENDPROCEDURE），并保持一致的缩进。桌面检查时，创建一个清晰的变量列表面板，逐行更新。这些细节上的努力将对你的成绩产生显著影响。
Published
Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导