📚 A-Level Computer Science: Mastering Data Structures | A-Level 计算机：数据结构 考点精讲
Data structures are fundamental to efficient programming and algorithmic problem-solving. In A-Level Computer Science, understanding data structures such as arrays, linked lists, stacks, queues, trees and hash tables is essential for both theoretical exams and practical programming tasks. This guide provides a focused revision of key concepts, operations, time complexities and typical exam scenarios.
数据结构是高效编程和算法问题解决的基础。在A-Level计算机科学中，理解数组、链表、栈、队列、树和哈希表等数据结构对理论考试和编程实践都至关重要。本指南将重点复习关键概念、操作、时间复杂度和典型考试情境。
1. Abstract Data Types and Data Structures | 抽象数据类型与数据结构
An abstract data type (ADT) defines a logical model for a data structure, specifying what operations can be performed but not how they are implemented. For example, a stack ADT provides push, pop and peek operations without dictating whether the underlying storage is an array or linked list.
抽象数据类型定义了数据结构的逻辑模型，指定了可以执行哪些操作，但不指定实现方式。例如，栈ADT提供压入、弹出和查看栈顶操作，而不规定底层存储是数组还是链表。
A data structure is the concrete implementation of an ADT, making choices about memory layout and algorithms. In A-Level exams, you must differentiate between the logical view (ADT) and the physical implementation.
数据结构是ADT的具体实现，需要选择内存布局和算法。在A-Level考试中，必须区分逻辑视图（ADT）与物理实现。
Common ADTs include lists, stacks, queues and dictionaries. Each can be implemented using various data structures — for instance, a list ADT can be implemented using an array or a linked list.
常见的ADT有列表、栈、队列和字典。每一个都可以用不同的数据结构来实现——例如，列表ADT可以用数组或链表来实现。
2. Static and Dynamic Data Structures | 静态与动态数据结构
Static data structures, such as arrays, have a fixed size determined at compile time. They offer fast access but cannot grow once memory is allocated. Memory is allocated as a single contiguous block.
静态数据结构（如数组）在编译时确定固定大小。它们访问速度快，但一旦分配内存就无法扩展。内存被分配为单个连续块。
Dynamic data structures, like linked lists, can change size during program execution by allocating and deallocating memory at runtime. They are more flexible but may have overhead due to pointers and memory allocation. The trade-off between static and dynamic structures is a recurring exam theme.
动态数据结构（如链表）可以在程序运行期间通过运行时分配和释放内存来改变大小。它们更灵活，但可能因指针和内存分配产生额外开销。静态与动态结构之间的权衡是反复出现的考试主题。
Static structures risk overflow if underestimated; dynamic structures can cause memory fragmentation. In practice, the choice depends on the requirement for predictable speed versus flexible size.
静态结构如果低估容量可能导致溢出；动态结构可能引起内存碎片。在实践中，选择取决于对可预测速度还是灵活大小的需求。
3. Arrays | 数组
An array stores a collection of elements of the same data type in contiguous memory locations. Each element is accessed by an integer index, typically starting at 0. The main advantage is O(1) random access to any element using its index.
数组将相同数据类型的元素集合存储在连续的内存位置中。每个元素通过整数索引访问，通常从0开始。主要优点是使用索引对任何元素进行O(1)随机访问。
Inserting or deleting an element in the middle of an array requires shifting subsequent elements, leading to O(n) time complexity. Multi-dimensional arrays (e.g., 2D arrays) are used to represent matrices and grids.
在数组中间插入或删除元素需要移动后续元素，导致O(n)时间复杂度。多维数组（例如二维数组）用于表示矩阵和网格。
Arrays are used when the maximum number of elements is known in advance and fast random access is needed. Exam questions often test arithmetic on index calculations and traversal algorithms.
数组适用于预先知道最大元素数量且需要快速随机访问的场景。考试题目常考查索引计算和遍历算法。
4. Linked Lists | 链表
A linked list consists of nodes, each containing data and a pointer to the next node. Singly linked lists allow forward traversal only; doubly linked lists have both next and previous pointers, enabling bidirectional traversal.
链表由节点组成，每个节点包含数据和指向下一个节点的指针。单链表只允许向前遍历；双向链表具有next和previous指针，支持双向遍历。
Insertion and deletion at the beginning of a linked list are O(1). However, searching for an element requires O(n) as we must follow pointers from the head. Linked lists do not provide random access.
在链表头插入和删除是O(1)的。然而，搜索元素需要O(n)，因为必须从头跟随指针遍历。链表不提供随机访问。
Key operations: insert at head, insert at tail, delete node, search. Diagrams of pointer manipulation, such as reassigning 'next' pointers, are common in exams. Be careful to update pointers in the correct order to avoid losing nodes.
关键操作：在头部插入，在尾部插入，删除节点，搜索。考试中常出现指针操作的图表，例如重新分配“next”指针。注意按正确顺序更新指针，避免丢失节点。
Linked lists form the basis for implementing other dynamic structures like stacks and queues, where size changes frequently.
链表为其他动态结构（如频繁改变大小的栈和队列）的实现提供了基础。
5. Stacks | 栈
A stack is a Last-In-First-Out (LIFO) data structure where elements are added and removed from the same end, called the top. Essential operations: push (add) and pop (remove). A peek operation returns the top element without removing it.
栈是一种后进先出（LIFO）数据结构，元素在称为栈顶的同一端添加和移除。基本操作：push（压入）和pop（弹出）。peek操作返回栈顶元素而不移除。
Stacks can be implemented using arrays (with a top index) or linked lists. They are used in function call stacks, undo mechanisms, and expression evaluation (e.g., converting infix to postfix).
栈可以用数组（设置栈顶索引）或链表来实现。它们用于函数调用栈、撤销机制和表达式求值（例如中缀转后缀）。
Stack Operations: push(x), pop(), peek() — all O(1)
栈操作：push(x), pop(), peek() —— 均为 O(1)
Overflow occurs if pushing to a full array-based stack; underflow when popping from an empty stack. Exams often test trace tables of stack operations.
使用基于数组的栈时，若向已满的栈压入会发生溢出；从空栈弹出则发生下溢。考试常通过跟踪表测试栈操作。
6. Queues | 队列
A queue is a First-In-First-Out (FIFO) structure: elements are added at the rear and removed from the front. Primary operations: enqueue (add) and dequeue (remove).
队列是一种先进先出（FIFO）结构：元素在队尾添加，在队头移除。主要操作：enqueue（入队）和dequeue（出队）。
Linear queues implemented with arrays suffer from wasted space when elements are dequeued. Circular queues overcome this by reusing vacated slots using modulo arithmetic. Priority queues remove the highest-priority element first, regardless of insertion order.
使用数组实现的线性队列在元素出队时会浪费空间。循环队列通过使用取模运算重用空出的槽位来克服此问题。优先级队列首先移除最高优先级元素，而不考虑插入顺序。
ueue at rear: rear = (rear + 1) mod size; Dequeue from front: front = (front + 1) mod size
入队尾部：rear = (rear + 1) mod size；出队头部：front = (front + 1) mod size
Applications include printer spoolers, CPU scheduling, and breadth-first search. All basic operations in a standard queue are O(1) when implemented efficiently.
应用包括打印队列、CPU调度和广度优先搜索。标准队列中所有基本操作在高效实现时均为O(1)。
7. Binary Trees | 二叉树
A tree is a hierarchical data structure consisting of nodes connected by edges. A binary tree has at most two children per node: left and right. The top node is the root; nodes with no children are leaves.
树是由边连接的节点组成的层次数据结构。二叉树每个节点最多有两个子节点：左子节点和右子节点。顶部节点是根节点；没有子节点的节点是叶节点。
Binary search trees (BSTs) maintain an ordered property: left subtree values < node value < right subtree values. This allows O(log n) average search time if the tree is balanced. Tree traversals: pre-order (node, left, right), in-order (left, node, right), post-order (left, right, node).
二叉搜索树维护有序性质：左子树值 < 节点值 < 右子树值。如果树保持平衡，可实现O(log n)平均搜索时间。树的遍历：前序（节点、左、右）、中序（左、节点、右）、后序（左、右、节点）。
Examiners frequently ask to reconstruct a binary tree from given traversal sequences or to output the sequence for a specific traversal. Remember that in-order traversal of a BST visits nodes in ascending order.
考官经常要求根据给定的遍历序列重构二叉树，或输出特定遍历的序列。请记住，BST的中序遍历按升序访问节点。
Use cases include expression trees for compilers and hierarchical file systems. Deletion in a BST can be complex — particularly when removing a node with two children, requiring an inorder successor replacement.
用例包括编译器的表达式树和层次文件系统。BST中的删除操作可能很复杂——特别是当移除有两个子节点的节点时，需要中序后继替换。
8. Hash Tables | 哈希表
A hash table stores key-value pairs. A hash function maps a key to an integer index in an array. Ideally, the hash function distributes keys uniformly to minimise collisions.
哈希表存储键值对。哈希函数将键映射到数组中的整数索引。理想情况下，哈希函数均匀分布键以最小化冲突。
Load factor α = n ÷ m, where n = number of entries, m = table size
装载因子 α = n ÷ m，其中 n = 条目数，m = 表大小
sion resolution strategies: open addressing (e.g., linear probing: check slots h(k,i) = (h' ollided items). When α exceeds a threshold (often 0.7), resizing and rehashing are needed.
冲突解决策略：开放定址法（例如线性探测：检查槽位 h(k,i) = (h'(k) + i) mod m）和链地址法（
Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图