Core Points of Data Structures | 数据结构核心要点

📚 Core Points of Data Structures | 数据结构核心要点

Data structures are the foundation of virtually every computer program. In A-Level Computer Science, you are expected to understand how data can be organised, stored, and manipulated efficiently, and to be able to analyse the trade-offs between different structures. This revision guide distils the core points you must master for your exams, from abstract data types to graphs and sorting algorithms.

数据结构是几乎所有计算机程序的基石。在 A-Level 计算机科学考试中，你不仅需要理解数据如何被高效地组织、存储与操作，还要能够分析不同结构之间的取舍。本复习指南提炼了考试必须掌握的核心要点，从抽象数据类型到图与排序算法，一应俱全。

---

1. Abstract Data Types & Complexity | 抽象数据类型与复杂度

An Abstract Data Type (ADT) is a logical description of how data is viewed and what operations are allowed, without specifying how those operations are implemented. For example, a ‘list’ ADT supports operations such as insert, delete, and search, regardless of whether it is implemented using an array or a linked list.

抽象数据类型（ADT）是对数据如何被看待以及允许哪些操作的一种逻辑描述，它并不规定这些操作具体如何实现。例如，’列表’ ADT 支持插入、删除和查找等操作，而无论它底层是用数组还是链表实现的。

Time complexity, expressed with Big-O notation, describes how the running time of an algorithm grows as the input size n increases. The most common orders you must recognise are: O(1) constant time, O(log n) logarithmic time, O(n) linear time, O(n log n) linearithmic time, and O(n²) quadratic time.

时间复杂度用大 O 记号表示，描述算法运行时间随输入规模 n 增长的趋势。你必须识别的最常见阶次包括：O(1) 常数时间、O(log n) 对数时间、O(n) 线性时间、O(n log n) 线性对数时间，以及 O(n²) 平方时间。

O(1) < O(log n) < O(n) < O(n log n) < O(n²)

To determine Big-O, identify the dominant operation in the algorithm — the one that executes most often — and express its count as a function of n, ignoring constant factors and lower-order terms. For a nested loop that runs n times inside another loop of n iterations, the complexity is O(n²).

要确定大 O 阶次，需要找出算法中的主导操作——即执行次数最多的操作——并将其执行次数表示为 n 的函数，忽略常数因子和低阶项。如果有一个 n 次循环嵌套在另一个 n 次循环内，那么复杂度就是 O(n²)。

---

2. Arrays & Records | 数组与记录

An array is a contiguous block of memory holding elements of the same data type, accessed by an index. Because the base address and element size are fixed, random access is possible in O(1) time: the address of element i is base + i × element_size.

数组是一块连续的内存区域，用于存放相同数据类型、通过下标访问的元素。由于基地址和元素大小固定，可以在 O(1) 时间内实现随机访问：第 i 个元素的地址为 base + i × 元素大小。

However, inserting or deleting an element in the middle of an array requires shifting all subsequent elements, giving a worst-case time complexity of O(n). Arrays also have a fixed size in most languages, which can lead to wasted space or the need to create a larger array and copy contents across.

然而，在数组中间插入或删除一个元素需要移动其后的所有元素，最坏情况下的时间复杂度为 O(n)。在大多数语言中，数组还具有固定大小，这可能导致空间浪费，或者需要创建更大的数组并复制全部内容。

A record is a composite data structure that groups together related data items of possibly different types. In Python, records are often represented by dictionaries or classes; in C, they are represented as ‘struct’ types. Records enable a programmer to model real-world entities with named fields.

记录是一种复合数据结构，将可能不同类型的相关数据项组合在一起。在 Python 中，记录常用字典或类来表示；在 C 语言中，则用 ‘struct’ 类型表示。记录使程序员能够用命名字段来建模现实世界中的实体。

---

3. Linked Lists | 链表

A linked list is a dynamic data structure made up of nodes, each containing data and a pointer (reference) to the next node. The list is accessed via a head pointer; the final node points to null. Because nodes are allocated individually, the list can grow and shrink at runtime without copying existing elements.

链表是一种由节点组成的动态数据结构，每个节点包含数据和一个指向下一节点的指针（引用）。链表通过头指针访问，最后一个节点的指针指向 null。由于每个节点独立分配内存，链表可以在运行时动态增长和缩小，而无需复制已有元素。

In a singly linked list, traversal is only possible in one direction, from head to tail. Searching for an element therefore takes O(n) time. In contrast, a doubly linked list stores both ‘next’ and ‘previous’ pointers, allowing traversal in both directions; however, it uses more memory per node.

在单链表中，只能从头到尾单向遍历，因此查找某个元素需要 O(n) 时间。相比之下，双向链表同时存储 ‘下一个’ 和 ‘上一个’ 指针，允许在两个方向上遍历，但每个节点会占用更多内存。

Insertion and deletion at a known position in a linked list can be performed in O(1) time by updating pointers, which is a major advantage over arrays. However, random access is not supported: reaching the k-th node always requires walking k steps from the head.

在链表中，若已知插入或删除的位置，只需更新指针即可在 O(1) 时间内完成，这是相对数组的一大优势。然而，链表不支持随机访问：要到达第 k 个节点，必须从头节点步行 k 步。

---

4. Stacks & Queues | 栈与队列

A stack is a Last-In-First-Out (LIFO) structure. Items are added (pushed) and removed (popped) only at the top. The two fundamental operations are ‘push’, which adds an item, and ‘pop’, which removes the most recently added item. Both run in O(1) time.

栈是一种后进先出（LIFO）的结构。只能在栈顶添加（压入）和移除（弹出）元素。两个基本操作是 ‘push’（压入）和 ‘pop’（弹出最近添加的元素），两者都运行在 O(1) 时间内。

Common applications of stacks include function call management (the call stack), expression evaluation, undo mechanisms in editors, and backtracking algorithms. When the stack overflows — push attempted on a full stack — a stack overflow error occurs.

栈的常见应用包括函数调用管理（调用栈）、表达式求值、编辑器中的撤销机制以及回溯算法。当尝试向满栈压入元素时，就会发生栈溢出错误。

A queue is a First-In-First-Out (FIFO) structure. Items arrive at the rear (enqueue) and leave from the front (dequeue). A circular queue reuses empty slots by wrapping around, avoiding the need to shift elements. Queues are essential in scheduling tasks, buffering data, and breadth-first search.

队列是一种先进先出（FIFO）的结构。元素从队尾入队（enqueue），从队首出队（dequeue）。循环队列通过回绕方式来复用空位，从而避免移动元素。队列在任务调度、数据缓冲和广度优先搜索中至关重要。

---

5. Trees & Binary Trees | 树与二叉树

A tree is a hierarchical, non-linear data structure. It consists of nodes connected by edges, with a single root node at the top. Every node except the root has exactly one parent; nodes with no children are called leaves. The height of a tree is the maximum number of edges from the root to a leaf.

树是一种层次化的非线性数据结构，由通过边连接的节点组成，顶部有一个唯一的根节点。除根节点外，每个节点有且仅有一个父节点；没有子节点的节点称为叶子节点。树的高度是指从根节点到叶子的最大边数。

A binary tree is a tree in which each node has at most two children, conventionally called the left child and right child. Full trees have every node with either 0 or 2 children; complete trees fill every level fully except possibly the last, which is filled left to right; perfect trees have all leaves at the same level.

二叉树是每个节点至多有两个子节点的树，通常称为左孩子和右孩子。满二叉树中每个节点要么有 0 个要么有 2 个子节点；完全二叉树除最后一层外每一层都被填满，且最后一层从左到右填充；完美二叉树的所有叶子都在同一层。

Traversal algorithms visit every node exactly once. Preorder visits root → left → right; inorder visits left → root → right; postorder visits left → right → root. Inorder traversal of a binary search tree produces sorted output, which is a key exam fact.

遍历算法会恰好访问每个节点一次。先序遍历按 根 → 左 → 右 的顺序访问；中序遍历按 左 → 根 → 右 的顺序访问；后序遍历按 左 → 右 → 根 的顺序访问。对二叉搜索树进行中序遍历会产生有序输出，这是考试中的关键知识点。

---

6. Binary Search Trees & Balanced Trees | 二叉搜索树与平衡树

A binary search tree (BST) maintains the ordering property: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property enables search, insert, and delete operations in O(log n) time on average.

二叉搜索树（BST）维护着一个顺序性质：对于每个节点，其左子树中的所有值都更小，右子树中的所有值都更大。该性质使得查找、插入和删除操作在平均情况下只需 O(log n) 时间。

However, if nodes are inserted in sorted order, the BST degenerates into a linked-list-like structure with height n, and all operations degrade to O(n). To prevent this, balanced trees such as AVL trees automatically rebalance after each insertion or deletion by performing rotations.

然而，如果按有序顺序插入节点，BST 就会退化成类似链表的结构，高度达到 n，所有操作都退化为 O(n)。为防止这种情况，AVL 树等平衡树会在每次插入或删除后自动通过旋转来重新平衡。

An AVL tree guarantees the height difference between the left and right subtrees of every node is at most 1. Four rotation cases — LL, RR, LR, and RL — restore balance when violations occur. This guarantees O(log n) performance for all operations regardless of input order.

AVL 树保证每个节点的左右子树高度差至多为 1。四种旋转情形——LL、RR、LR 和 RL——用于在失衡发生时恢复平衡。这保证了无论输入顺序如何，所有操作都能保持 O(log n) 的性能。

---

7. Heaps & Priority Queues | 堆与优先队列

A heap is a complete binary tree that satisfies the heap property. In a max-heap, every parent node has a value greater than or equal to its children; in a min-heap, every parent has a value smaller than or equal to its children. The largest (or smallest) item is always at the root.

堆是一种满足堆性质的完全二叉树。在最大堆中，每个父节点的值都大于或等于其子节点；在最小堆中，每个父节点的值都小于或等于其子节点。最大（或最小）的元素始终位于根节点。

Heaps are usually implemented as arrays: the children of the node at index i are at indices 2i + 1 and 2i + 2 (for 0-based indexing). Insertion adds the item at the bottom and ‘bubbles up’; deletion of the root swaps the last item to the root and ‘bubbles down’. Both run in O(log n) time.

堆通常用数组实现：对于 0 起始的下标 i，其左孩子和右孩子分别位于 2i + 1 和 2i + 2。插入操作将新项放在底部并向上冒泡；删除根节点时，将最后一个元素换到根位置并向下调整。两者的时间复杂度都是 O(log n)。

A priority queue is an ADT where each element has a priority, and the element with the highest (or lowest) priority is always removed first. A heap provides an efficient implementation of a priority queue. Heaps also power heapsort, which sorts in O(n log n) time.

优先队列是一种 ADT，其中每个元素都带有优先级，具有最高（或最低）优先级的元素总是最先被移除。堆为优先队列提供了一种高效的实现方式。堆还用于堆排序，其排序时间为 O(n log n)。

---

8. Hash Tables | 哈希表

A hash table stores key-value pairs and uses a hash function to map a key to an index in a fixed-size array. A good hash function distributes keys uniformly across the table, minimising collisions. With a perfect hash, search, insertion, and deletion all run in O(1) time on average.

哈希表存储键值对，并使用哈希函数将键映射到固定大小数组中的某个下标。好的哈希函数应将键均匀地分布到表中，从而尽量减少冲突。在理想哈希下，查找、插入和删除的平均时间复杂度都是 O(1)。

Collisions occur when two different keys map to the same index. Two standard resolution strategies are: chaining, where each table slot holds a linked list of collided items; and open addressing, where the algorithm probes subsequent slots until an empty one is found.

当两个不同的键映射到同一个下标时，就会发生冲突。两种标准的解决策略是：链地址法，即每个表槽存一条冲突项的链表；开地址法，即算法依次探测后续槽位直到找到空位。

The load factor α = n / m, where n is the number of keys and m is the table size, directly affects performance. When α becomes too high, the table should be resized and all keys rehashed. Hash tables are widely used in databases, caches, and symbol tables in compilers.

负载因子 α = n / m（n 为键的数量，m 为表的大小）直接影响性能。当 α 过高时，应扩大表并重新哈希所有键。哈希表广泛应用于数据库、缓存以及编译器中的符号表。

---

9. Graphs & Traversals | 图与遍历

A graph is a non-linear structure composed of vertices (nodes) and edges connecting them. Graphs may be directed or undirected, weighted or unweighted. They model networks such as social connections, road maps, and web links.

图是一种由顶点（节点）和连接它们的边组成的非线性结构。图可以是有向或无向的，也可是带权或不带权的。图可用于对社交关系、道路地图和网页链接等网络进行建模。

Two common representations are the adjacency matrix and the adjacency list. An adjacency matrix uses an n × n grid where entry [i][j] = 1 if an edge exists; it supports O(1) edge queries but uses O(n²) space. An adjacency list stores, for each vertex, a list of neighbours, using O(n + e) space where e is the number of edges.

两种常见表示法是邻接矩阵和邻接表。邻接矩阵使用 n × n 的网格，若存在边则第 [i][j] 项为 1；它支持 O(1) 的边查询，但占用 O(n²) 空间。邻接表为每个顶点存储一个邻居列表，占用 O(n + e) 空间，其中 e 是边的数量。

Depth-First Search (DFS) explores as far as possible along each branch before backtracking, often implemented recursively or with a stack. Breadth-First Search (BFS) explores all neighbours at the current depth before moving deeper, implemented with a queue. BFS finds the shortest path in unweighted graphs.

深度优先搜索（DFS）沿每个分支尽可能深入地探索后再回溯，通常用递归或栈实现。广度优先搜索（BFS）先访问当前深度的所有邻居，再继续深入，用队列实现。在无权图中，BFS 可以找到最短路径。

---

10. Sorting & Searching | 排序与查找

Sorting arranges elements in a specified order. Bubble sort repeatedly swaps adjacent out-of-order pairs, running in O(n²) worst-case time. Insertion sort builds the sorted list one element at a time, also O(n²), but efficient for nearly sorted data. Merge sort divides the list in half, sorts each half recursively, and merges — always O(n log n).

排序将元素按指定顺序排列。冒泡排序反复交换相邻的逆序对，最坏情况时间为 O(n²)。插入排序逐个元素构建有序列表，同样是 O(n²)，但对近乎有序的数据效率很高。归并排序将列表二分、递归排序并合并，始终为 O(n log n)。

Algorithm	Best	Average	Worst	Space
Bubble	O(n)	O(n²)	O(n²)	O(1)
Insertion	O(n)	O(n²)	O(n²)	O(1)
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)

Binary search is the cornerstone of efficient searching. It repeatedly divides a sorted array in half, comparing the target with the middle element, and discarding the half that cannot contain it. This gives O(log n) time, far faster than linear search for large data sets.

二分查找是高效查找的基石。它反复将有序列分成两半，将目标值与中间元素比较，并舍弃不可能包含目标值的那一半。其时间复杂度为 O(log n)，对于大规模数据远比线性查找迅速。

Master the exam traps: ensure the array is sorted before applying binary search, identify best/average/worst cases for each sort, and know which structure supports O(1) random access versus O(1) pointer insertion. Sketching data structures in diagrams during revision will greatly strengthen your recall under exam pressure.

注意考试陷阱：使用二分查找前务必确认数组已排序；牢记每种排序的最佳/平均/最坏情况；清楚哪种结构支持 O(1) 随机访问，哪种支持 O(1) 指针插入。复习时用图示描绘数据结构，能大大增强考试压力下的记忆提取能力。

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

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