📚 Data Structures in OCR A-Level Computer Science | A-Level OCR 计算机：数据结构 考点精讲
In the A-Level OCR Computer Science specification, data structures form the backbone of efficient algorithm design and problem-solving. Understanding how data is organised, accessed and manipulated is essential for writing programs that are both correct and performant. This article provides a comprehensive revision guide covering the core data structures you need to know, including arrays, linked lists, stacks, queues, trees, graphs, hash tables and heaps, along with their operations, advantages, limitations and typical use cases.
在 A-Level OCR 计算机科学课程中，数据结构是高效算法设计和问题解决的基础。理解数据如何组织、访问和操作，对于编写既正确又高性能的程序至关重要。本文提供一份全面的复习指南，涵盖你需要掌握的核心数据结构，包括数组、链表、栈、队列、树、图、哈希表和堆，以及它们的操作、优势、局限和典型应用场景。
1. Arrays | 数组
An array is a static, contiguous block of memory that stores elements of the same data type. Each element can be accessed directly via its index, typically starting from 0. Arrays offer O(1) random access but have a fixed size; insertion and deletion in the middle require shifting elements, costing O(n) time.
数组是一块静态、连续的内存区域，用于存储相同数据类型的元素。每个元素可以通过索引直接访问，索引通常从 0 开始。数组提供 O(1) 的随机访问，但大小固定；在中间插入或删除元素需要移动其他元素，时间复杂度为 O(n)。
In OCR, you are expected to know how to declare, traverse and manipulate one-dimensional and two-dimensional arrays. Operations such as finding the maximum value, summing elements and linear search are common. You should also understand how arrays can be used to implement other data structures like stacks and queues.
在 OCR 考试中，你需要知道如何声明、遍历和操作一维及二维数组。常考的操作包括寻找最大值、求和以及线性搜索。你还应理解如何用数组实现其他数据结构，如栈和队列。
2. Linked Lists | 链表
A linked list is a dynamic data structure consisting of nodes, where each node contains a data field and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory, allowing efficient insertion and deletion at any position once you have a reference to the preceding node. However, random access is not supported — accessing an element by index takes O(n) time.
链表是一种动态数据结构，由节点组成，每个节点包含数据域和指向下一个节点的指针。与数组不同，链表不需要连续的内存空间，因此只要拥有对前驱节点的引用，就能高效地在任意位置进行插入和删除。但是，链表不支持随机访问——按索引访问元素需要 O(n) 时间。
For OCR, you need to distinguish between singly linked lists, doubly linked lists and circular linked lists. Be prepared to trace or describe algorithms for traversing a list, adding a node at the start/end/middle, and deleting a node. Understanding the use of a null pointer to mark the end of the list is crucial.
针对 OCR 考试，你需要区分单链表、双向链表和循环链表。要能跟踪或描述遍历链表、在头部/尾部/中间添加节点以及删除节点的算法。理解用空指针标记链表尾部至关重要。
3. Stacks | 栈
A stack is a Last-In-First-Out (LIFO) abstract data type. The two primary operations are push (add an item to the top) and pop (remove the item from the top). Access is restricted to the top element only, making it suitable for tasks like managing function calls, undo mechanisms and syntax parsing (bracket matching).
栈是一种后进先出（LIFO）的抽象数据类型。两个主要操作是 push（将元素加入栈顶）和 pop（从栈顶移除元素）。只能访问栈顶元素，这使其适用于管理函数调用、撤销操作和语法分析（括号匹配）等任务。
A stack can be implemented using an array or a linked list. With an array, a stack pointer (top) is needed, and checks for stack overflow (array full) and underflow (pop from empty stack) are essential. In a linked implementation, the top of the stack corresponds to the head of the list, and both push and pop are O(1).
栈可以用数组或链表实现。使用数组时，需要一个栈顶指针，并必须检查栈上溢（数组已满）和下溢（从空栈弹出）。在链式实现中，栈顶即为链表头部，push 和 pop 操作都是 O(1)。
4. Queues | 队列
A queue is a First-In-First-Out (FIFO) abstract data type. Items are added at the rear (enqueue) and removed from the front (dequeue). Queues are used in scheduling, buffering and breadth-first search. A linear queue implemented with an array can suffer from the problem of unusable space if the front index keeps advancing; a circular queue overcomes this by wrapping the rear pointer around to the beginning when it reaches the end.
队列是一种先进先出（FIFO）的抽象数据类型。元素在队尾加入（enqueue），在队头移除（dequeue）。队列用于调度、缓冲和广度优先搜索。用数组实现的线性队列会因队头索引不断后移而出现空间无法再利用的问题；循环队列通过当队尾指针到达数组末端时绕回到开头，解决了这一缺陷。
For OCR, you should know how to implement both linear and circular queues using arrays, including the logic for checking whether the queue is empty or full. Priority queues are sometimes introduced — they dequeue elements based on priority rather than arrival order, often implemented with a heap.
对于 OCR，你应该知道如何用数组实现线性队列和循环队列，包括判断队列为空或已满的逻辑。有时会引入优先队列——它根据优先级而非到达顺序来出队，通常用堆实现。
5. Trees | 树
A tree is a hierarchical, non-linear data structure consisting of nodes connected by edges. A binary tree restricts each node to at most two children (left and right). Trees are widely used to represent hierarchical data such as file systems, organisation charts and expression trees. A binary tree can be traversed in three classical ways: pre-order (root, left, right), in-order (left, root, right) and post-order (left, right, root).
树是一种层次化、非线性的数据结构，由节点和边组成。二叉树限制每个节点最多有两个子节点（左子节点和右子节点）。树广泛用于表示层次化数据，如文件系统、组织结构图和表达式树。二叉树有三种经典的遍历方式：前序遍历（根、左、右）、中序遍历（左、根、右）和后序遍历（左、右、根）。
OCR candidates should be comfortable drawing binary trees from given traversal sequences and vice versa. Understanding recursive traversal algorithms is important, as is the concept of depth, leaf nodes and internal nodes. Binary trees can be implemented using nodes with left and right pointers or using arrays (e.g., representing a complete tree with numbering).
OCR 考生应能根据给定的遍历序列画出二叉树，反之亦然。理解递归遍历算法很重要，同样重要的还有深度、叶节点和内部节点的概念。二叉树可以通过带有左右指针的节点实现，也可以用数组实现（例如，通过编号表示一棵完全树）。
6. Binary Search Trees | 二叉搜索树
A binary search tree (BST) is a binary tree with the ordering property: for any node, all values in the left subtree are smaller, and all values in the right subtree are greater. This property enables efficient search, insertion and deletion with an average complexity of O(log n), provided the tree remains reasonably balanced. However, a degenerate (unbalanced) BST degrades to O(n) performance.
二叉搜索树（BST）是具有排序性质的二叉树：对于任意节点，其左子树中的所有值都小于该节点，右子树中的所有值都大于该节点。这一性质使得搜索、插入和删除的平均时间复杂度为 O(log n)，前提是树保持相对平衡。然而，退化的（不平衡的）BST 性能会降级为 O(n)。
For the exam, you must know how to perform insertion, search and deletion on a BST, including the three cases for deletion (leaf node, node with one child, node with two children). You should also be able to trace algorithms and sketch the resultant tree after a sequence of operations.
考试中，你必须知道如何在 BST 上执行插入、搜索和删除操作，包括删除的三种情形（叶节点、只有一个子节点的节点、有两个子节点的节点）。你还需要能跟踪算法并画出执行一系列操作后的结果树。
7. Graphs | 图
A graph consists of a set of vertices (nodes) connected by edges. Graphs can be directed or undirected, and edges may carry weights. They model networks such as road maps, social connections and the internet. Two fundamental representations are the adjacency matrix (a 2D array where cell [i][j] stores 1 or the weight if an edge exists) and the adjacency list (an array of lists, each holding neighbours of a vertex).
图由一组顶点（节点）及其连接的边组成。图可以是有向或无向的，边可以带权重。它们用于建模网络，如道路地图、社交联系和互联网。两种基本的表示方法是邻接矩阵（一个二维数组，其中单元 [i][j] 存储 1 或权重，表示边存在）和邻接表（一个链表数组，每个存储一个顶点的邻居）。
OCR requires understanding of how to store a graph, and the trade-offs: adjacency matrices use more memory but allow O(1) edge existence check; adjacency lists are more space-efficient for sparse graphs. You may also need to describe or trace graph traversal algorithms such as depth-first search (DFS) and breadth-first search (BFS), typically using a stack and a queue respectively.
OCR 要求理解如何存储图及其权衡：邻接矩阵占用更多内存但允许 O(1) 的边存在性检查；邻接表对稀疏图更节省空间。你可能还需要描述或跟踪图的遍历算法，如深度优先搜索（DFS）和广度优先搜索（BFS），它们通常分别利用栈和队列。
8. Hash Tables | 哈希表
A hash table stores key-value pairs and uses a hash function to compute an index into an array of buckets, from which the desired value can be found. Ideally, this gives O(1) average-case performance for insert, delete and lookup. Collisions occur when two keys map to the same index; the two main collision resolution strategies are chaining (each bucket contains a linked list of entries) and open addressing (probing for the next empty slot).
哈希表存储键值对，并使用哈希函数计算出数组（桶）的索引，从而找到所需的值。理想情况下，这使插入、删除和查找的平均时间复杂度为 O(1)。当两个键映射到同一个索引时会产生冲突；两种主要的冲突解决策略是链地址法（每个桶包含一个条目链表）和开放寻址法（探查下一个空槽）。
In OCR, you need to understand the role of a good hash function that distributes keys uniformly, the concept of load factor (ratio of stored entries to table size), and the need for resizing or rehashing when the load factor becomes too high. You should be able to trace the insertion and retrieval process given a specific hash function and collision handling method.
在 OCR 考试中，你需要理解良好哈希函数的作用——能将键均匀分布，负载因子的概念（已存条目与表大小的比率），以及当负载因子过高时需要进行扩缩容或再哈希。你应该能够根据给定的哈希函数和冲突处理方法，跟踪插入和检索过程。
9. Heaps | 堆
A heap is a specialised tree-based data structure that satisfies the heap property: in a max-heap, every parent node is greater than or equal to its children; in a min-heap, every parent is less than or equal to its children. Heaps are commonly implemented as complete binary trees stored in arrays, enabling O(1) access to the maximum (or minimum) element and O(log n) insertion and deletion.
堆是一种特殊的树形数据结构，满足堆的性质：在最大堆中，每个父节点都大于或等于其子节点；在最小堆中，每个父节点都小于或等于其子节点。堆通常以完全二叉树的形式存储在数组中，从而支持 O(1) 访问最大（或最小）元素，以及 O(log n) 的插入和删除操作。
The heap data structure is used to implement priority queues and the heap sort algorithm. For OCR, you may be required to explain how elements are inserted (adding at the end and then sifting up) and how the root is removed (replacing with the last element and then sifting down), and to trace the construction of a heap from a list of values.
堆数据结构用于实现优先队列和堆排序算法。对于 OCR，你可能需要解释元素如何插入（在末尾添加然后向上筛选），以及如何移除根节点（用最后一个元素替换然后向下筛选），并能跟踪从一个值列表构建堆的过程。
10. Choosing Data Structures | 选择数据结构
Selecting the appropriate data structure depends on the operations you need to perform most frequently and the constraints of memory and time. For example, if constant-time random access is crucial and the size is known in advance, an array is ideal. If frequent insertions and deletions in the middle are needed without random access, a linked list is better. For LIFO behaviour, use a stack; for FIFO, a queue. If you need ordered data with efficient search, a BST or hash table might be appropriate, depending on whether ordering matters.
选择合适的结构取决于你最常需要执行的操作以及内存和时间的限制。例如，如果常数时间的随机访问至关重要且大小预先可知，数组是理想选择；如果需要在中间频繁插入和删除而不需要随机访问，链表更好；需要后进先出行为则用栈；需要先进先出则用队列；如果需要有序数据并进行高效搜索，BST 或哈希表可能合适，这取决于是否需要保持顺序。
OCR exam questions often ask you to justify your choice of data structure for a given scenario. You must balance factors such as implementation simplicity, memory overhead, speed of operations and whether the data is dynamic. A solid understanding of the time complexities covered in the next section will help you make these decisions.
OCR 考试题目常常要求你为给定场景选择数据结构并说明理由。你必须权衡实现的简易性、内存开销、操作速度以及数据是否动态变化等因素。扎实地理解下一节中介绍的时间复杂度将有助于你做出这些选择。
11. Time Complexity and Big O | 时间复杂度与大 O 记法
Big O notation describes the worst-case time complexity of an algorithm or operation in terms of the size of the input, n. Common complexities include O(1) (constant), O(log n) (logarithmic), O(n) (linear), O(n log n), O(n²) (quadratic) and O(2ⁿ) (exponential). In data structures, access by index in an array is O(1); search in an unsorted array is O(n); insertion at the end of an array (if space allows) is O(1), but in the middle it is O(n). For a balanced BST, search, insert and delete are O(log n) on average, while for a hash table they are O(1) average but can degrade to O(n) in worst-case scenarios with many collisions.
大 O 记法根据输入规模 n 来描述算法或操作的最坏情况时间复杂度。常见的复杂度包括 O(1)（常数）、O(log n)（对数）、O(n)（线性）、O(n log n)、O(n²)（平方）和 O(2ⁿ)（指数）。在数据结构中，数组的按索引访问是 O(1)；在无序数组中搜索是 O(n)；在数组末尾插入（若空间足够）是 O(1)，但在中间插入是 O(n)。对于平衡 BST，搜索、插入和删除的平均复杂度为 O(log n)；对于哈希表，平均为 O(1)，但在冲突很多的最坏情况下可能退化为 O(n)。
Being able to compare algorithms using Big O notation is a key skill. In OCR questions, you might be asked to determine the time complexity of given pseudocode or to select the most efficient data structure for a particular task based on complexity analysis.
能够使用大 O 记法比较算法是一项关键技能。在 OCR 试题中，你可能需要确定给定伪代码的时间复杂度，或者基于复杂度分析为特定任务选择最高效的数据结构。
12. Summary of Key Operations | 关键操作总结
The table below summarises the typical time complexities of the main data structures for common operations. Note that these are worst-case unless stated otherwise, and actual performance depends on implementation details and the specific variant of the structure used.
下表总结了主要数据结构常用操作的典型时间复杂度。请注意，除非另有说明，这里的复杂度是最坏情况，实际性能取决于实现细节和所用结构的具体变体。
| Data Structure | Access / Search | Insertion (average) | Deletion (average) |
|---|---|---|---|
| Array (unsorted) | O(1) index / O(n) search | O(1) at end, O(n) elsewhere | O(1) at end, O(n) elsewhere |
| Linked List (singly) | O(n) | O(1) at head, O(n) elsewhere | O(1) at head, O(n) elsewhere |
| Stack (array/linked) | O(1) top only | O(1) push | O(1) pop |
| Queue (circular array) | O(1) front | O(1) enqueue | O(1) dequeue |
| Binary Search Tree (balanced) | O(log n) | O(log n) | O(log n) |
| Hash Table | O(1) average, O(n) worst | O(1) average, O(n) worst | O(1) average, O(n) worst |
| Heap (binary) | O(1) find max/min | O(log n) | O(log n) |
Memorising these approximate complexities and understanding the reasoning behind them will prepare you for both short-answer questions and extended design tasks. Practise tracing algorithms on small examples, and always link the choice of data structure back to the requirements of the problem.
记住这些近似的复杂度并理解其背后的原理，将帮助你应对简答题和扩展设计任务。多在小规模示例上练习跟踪算法，并始终将数据结构的选择与问题需求联系起来。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply