📚 IB CCEA Computer Science: Data Structures Key Points Review | IB CCEA 计算机：数据结构 考点精讲
Mastering data structures is essential for success in IB and CCEA Computer Science examinations. They form the backbone of efficient algorithm design and problem-solving, and candidates are expected not only to understand how each structure works but also to analyse their time and space complexities, choose appropriate implementations, and apply them to real-world computational problems. This article provides a comprehensive review of the key data structures covered in the syllabus, from arrays and linked lists to trees, graphs, and hash tables, with clear explanations and exam-focused insights.
掌握数据结构是 IB 和 CCEA 计算机科学考试中取得好成绩的关键。它们是高效算法设计与问题求解的基础，考生不仅要理解每种结构的工作原理，还需分析其时间与空间复杂度、选择合适的实现方式并应用于实际问题。本文系统梳理了考纲中的核心数据结构，包括数组、链表、栈、队列、树、图和哈希表，提供清晰的解释与应试导向的要点。
1. What are Data Structures? | 什么是数据结构？
A data structure is a specialised format for organising, processing, retrieving and storing data. In computer science, the right choice of data structure can dramatically affect the performance of an algorithm. Data structures can be classified as primitive (integers, floats, characters) and non-primitive, which are further divided into linear (arrays, linked lists, stacks, queues) and non-linear (trees, graphs). Understanding the distinction between static and dynamic structures, as well as the concept of Abstract Data Types (ADTs), sets the foundation for all subsequent topics.
数据结构是组织、处理、检索和存储数据的专用格式。在计算机科学中，正确选择数据结构可以显著影响算法的性能。数据结构可分为基本类型（整数、浮点数、字符）和非基本类型，后者进一步分为线性结构（数组、链表、栈、队列）和非线性结构（树、图）。理解静态与动态结构的区别以及抽象数据类型的概念，是学习后续所有主题的基础。
2. Arrays and Their Properties | 数组及其特性
An array is a static, contiguous block of memory that stores elements of the same data type. Each element is accessed directly via an index, allowing constant-time O(1) random access. This makes arrays highly efficient for look-up operations. However, insertion and deletion can be costly O(n) because elements may need to be shifted. In exam scenarios, you must be able to declare arrays, traverse them using loops, and implement basic operations such as searching (linear or binary if sorted) and sorting. Arrays can be one-dimensional or multi-dimensional, and their fixed size is a key limitation when the number of elements is unpredictable.
数组是一块静态、连续的内存区域，用于存储相同数据类型的元素。每个元素通过索引直接访问，可实现常数时间 O(1) 的随机存取，因此查找效率极高。但插入和删除操作可能达到 O(n) 的代价，因为可能需要移动元素。在考试中，你必须能够声明数组、使用循环遍历，并实现搜索（线性或基于排序的二分搜索）和排序等基本操作。数组可以是一维或多维的，其固定大小是当元素数量不可预测时的主要限制。
- Access: O(1)
- Search: O(n) (linear), O(log n) (binary if sorted)
- Insert/Delete at end: O(1) amortised; at arbitrary position: O(n)
访问：O(1)；搜索：O(n)（线性），如已排序则二分搜索为 O(log n)；插入/删除：在末尾为均摊 O(1)，在任意位置为 O(n)。
3. Linked Lists: Singly, Doubly and Circular | 链表：单链表、双链表和循环链表
A linked list is a dynamic data structure consisting of nodes, where each node contains data and a reference (or pointer) to the next node. Unlike arrays, linked lists do not require contiguous memory, and their size can grow or shrink at runtime. Singly linked lists allow forward traversal only; doubly linked lists have pointers to both previous and next nodes, enabling bidirectional traversal. Circular linked lists have the last node pointing back to the first. Key exam topics include node insertion/deletion at head, tail, or given position, searching, and reversing a list. While access is O(n) because you must traverse from the head, insertion and deletion at a known node can be O(1).
链表是一种动态数据结构，由节点组成，每个节点包含数据和指向下一节点的引用（或指针）。与数组不同，链表不需要连续的内存空间，其大小可以在运行时变化。单链表仅允许向前遍历；双链表具有指向前一个和后一个节点的指针，支持双向遍历；循环链表的最后一个节点指向头节点。考试重点包括在头部、尾部或指定位置插入与删除节点、搜索以及反转链表。由于必须从头遍历，访问为 O(n)，但在已知节点处的插入和删除可以是 O(1)。
| Operation | Array | Linked List |
|---|---|---|
| Access | O(1) | O(n) |
| Insert/Delete (known pos) | O(n) | O(1) |
| Memory | Static, contiguous | Dynamic, scattered |
Array vs Linked List comparison. | 数组与链表的对比。
4. Stacks: LIFO Principle | 栈：后进先出原则
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. All additions (push) and removals (pop) happen at the same end, called the top. Stacks can be implemented using arrays or linked lists; both give O(1) time for push and pop operations. Key applications include function call management (call stack), undo mechanisms in software, expression evaluation, and bracket matching. Examiners frequently ask for pseudocode to implement push, pop, peek/top, and isEmpty operations, as well as tracing stack contents after a sequence of commands.
栈是一种遵循后进先出（LIFO）原则的线性数据结构。所有添加（压入）和移除（弹出）操作都在同一端（称为栈顶）进行。栈可以用数组或链表实现；两种实现方式中，压入与弹出操作的时间复杂度均为 O(1)。主要应用包括函数调用管理（调用栈）、软件的撤销机制、表达式求值和括号匹配。考官经常要求编写实现压入、弹出、查看栈顶和判空操作的伪代码，以及跟踪执行一系列命令后栈的内容。
Push(x): top ← top + 1; stack[top] ← x
Pop(): if not empty: data ← stack[top]; top ← top – 1; return data
5. Queues: FIFO and Priority Queues | 队列：先进先出与优先队列
A queue is a linear data structure that operates on a First-In-First-Out (FIFO) basis. Elements are added at the rear (enqueue) and removed from the front (dequeue). Standard queues provide O(1) enqueue and dequeue. Circular queues use a fixed-size array and modulo arithmetic to reuse spaces efficiently. A priority queue extends the concept by associating each element with a priority; the highest-priority element is dequeued first regardless of insertion order. Implementations often use heaps for efficiency. Typical exam tasks include simulating queue operations, differentiating between linear and circular queues, and recognising real-world scenarios such as print spoolers, keyboard buffers, and process scheduling.
队列是一种基于先进先出（FIFO）原则的线性数据结构。元素在队尾入队，从队首出队。标准队列的入队和出队操作均为 O(1)。循环队列使用固定大小的数组和取模运算来高效重用空间。优先队列扩展了这一概念，为每个元素关联一个优先级；无论插入顺序如何，优先级最高的元素最先出队。实现通常使用堆以提高效率。典型考试任务包括模拟队列操作、区分线性队列与循环队列，以及辨别打印缓冲池、键盘缓冲区和进程调度等实际场景。
6. Trees: Binary Trees and Traversals | 树：二叉树与遍历
A tree is a hierarchical, non-linear data structure consisting of nodes connected by edges. Binary trees are a fundamental type where each node has at most two children (left and right). Important tree terminology includes root, leaf, parent, child, depth, and height. Binary search trees (BST) maintain ordering: for any node, left subtree values are smaller, right subtree values are larger, enabling efficient search, insertion, and deletion in O(log n) average time. Balanced trees (e.g., AVL) prevent degenerated O(n) performance. Tree traversals—pre-order, in-order, and post-order—are essential for processing tree data. Candidates must be able to perform these traversals recursively and iteratively, and to use them to output sorted sequences (in-order of BST) or reconstruct trees.
树是一种由节点和边构成的分层、非线性数据结构。二叉树是最基本的类型，每个节点最多有两个子节点（左和右）。重要的树术语包括根、叶、父节点、子节点、深度和高度。二叉搜索树（BST）维护顺序：对于任一节点，左子树的值较小，右子树的值较大，从而实现平均 O(log n) 时间的高效搜索、插入和删除。平衡树（如 AVL 树）防止退化为 O(n) 的性能。树的遍历——前序、中序和后序——是处理树数据的核心。考生必须能够递归和迭代地执行这些遍历，并能利用中序遍历输出有序序列（BST）或重建树结构。
Pre-order: Node → Left → Right
In-order: Left → Node → Right
Post-order: Left → Right → Node
7. Graphs: Representation and Basic Algorithms | 图：表示与基本算法
Graphs model pairwise relationships between objects using vertices (nodes) and edges. They can be directed or undirected, weighted or unweighted. Two primary representations are adjacency matrix (a 2D array where cell [i][j] indicates an edge) and adjacency list (an array of linked lists). Matrix offers O(1) edge queries but uses O(V²) space; lists are more space-efficient for sparse graphs O(V+E). Essential algorithms include breadth-first search (BFS) using a queue and depth-first search (DFS) using a stack or recursion. Both are used to explore connectivity, find paths, and detect cycles. For weighted graphs, Dijkstra’s algorithm finds shortest paths. Exam questions often ask to trace BFS/DFS, identify data structures used internally, and discuss applications such as social networks, routing, and web crawling.
图利用顶点（节点）和边来建模对象之间的成对关系。图可以是有向或无向的，带权或不带权。两种主要表示法是邻接矩阵（二维数组，单元格 [i][j] 指示边）和邻接表（链表的数组）。矩阵提供 O(1) 的边查询，但占用 O(V²) 空间；邻接表对稀疏图更节省空间，为 O(V+E)。核心算法包括使用队列的广度优先搜索（BFS）和使用栈或递归的深度优先搜索（DFS）。两者都用于探索连通性、寻找路径和检测环。对于带权图，Dijkstra 算法查找最短路径。考试题目常要求跟踪 BFS/DFS 的执行，识别内部使用的数据结构，并讨论社交网络、路由和网络爬虫等应用。
8. Hash Tables: Hashing and Collisions | 哈希表：哈希与冲突处理
A hash table (or hash map) stores key-value pairs and provides average-case O(1) insertion, deletion, and lookup. It uses a hash function to compute an index from the key. A good hash function minimises collisions and distributes keys uniformly. Collisions occur when different keys map to the same index; common resolution techniques include chaining (using a linked list at each bucket) and open addressing (probing the next available slot, e.g., linear probing, quadratic probing). Understanding load factor and rehashing is important for maintaining performance. In exam contexts, you may be asked to simulate a series of insertions given a specific hash function and collision strategy, or to evaluate the efficiency of a hash table against other structures for dictionary operations.
哈希表（或哈希映射）存储键值对，并提供平均情况 O(1) 的插入、删除和查找。它使用哈希函数从键计算索引。好的哈希函数能最小化冲突并均匀分布键。冲突发生在不同键映射到同一索引时；常见的解决技术包括链地址法（在每个桶使用链表）和开放寻址法（探测下一个可用槽，如线性探测、二次探测）。理解负载因子和再哈希对于维持性能至关重要。在考试中，可能要求你根据给定的哈希函数和冲突策略模拟一系列插入操作，或评估哈希表相对于其他结构在字典操作上的效率。
9. Abstract Data Types (ADT) and Implementation | 抽象数据类型及其实现
An Abstract Data Type defines a data type by its behaviour (operations) from the point of view of a user, specifically the possible values, the operations on them, and the behaviour of these operations. It is independent of any concrete implementation. For example, a Stack ADT specifies push, pop, top, and isEmpty operations without specifying whether it uses an array or linked list underneath. Understanding ADTs allows programmers to design modular code and swap implementations without changing the interface. In the IB and CCEA curricula, you should be able to differentiate between ADT and data structure, explain encapsulation and information hiding, and provide the operational specifications for common ADTs such as list, stack, queue, tree, and dictionary.
抽象数据类型（ADT）从用户角度通过行为（操作）来定义数据类型，具体包括可能的值、对这些值的操作以及这些操作的行为。它独立于任何具体实现。例如，栈 ADT 规定了 push、pop、top 和 isEmpty 操作，但不指定底层是使用数组还是链表。理解 ADT 使程序员能设计模块化代码，并在不改变接口的情况下交换实现。在 IB 和 CCEA 课程中，你需要区分 ADT 与数据结构，解释封装和信息隐藏，并为常见 ADT（如列表、栈、队列、树和字典）提供操作规范。
10. Choosing and Evaluating Data Structures | 数据结构的选择与评估
Selecting the optimal data structure for a given problem requires a careful analysis of the operations that will be performed most frequently and the resource constraints. Factors include time complexity, memory usage, ease of implementation, and specific requirements like ordering or fast range queries. For instance, an array is ideal for frequent random access and fixed-size collections, while a linked list suits scenarios with frequent insertions/deletions at arbitrary positions. A BST offers fast sorted data operations, but a hash table is preferable when only exact-match lookups are needed. Graphs are irreplaceable for network models. Being able to justify your choice in an exam, comparing at least two alternatives with Big-O notation, demonstrates deep understanding.
为给定问题选择最优数据结构，需要仔细分析最常执行的操作以及资源限制。因素包括时间复杂度、内存使用、实现难易度以及排序或快速范围查询等特殊要求。例如，数组适合频繁的随机访问和固定大小的集合，而链表适合在任意位置频繁插入/删除的场景。二叉搜索树可提供高效的排序数据操作，但若只需要精确匹配查找，哈希表更优。图在网络模型中不可替代。在考试中能够用大 O 符号比较至少两种备选方案并论证你的选择，体现了深刻的理解。
11. Exam Tips and Common Pitfalls | 考试技巧与常见错误
Data structure questions in IB and CCEA exams often involve tracing, pseudocode writing, and situational analysis. Always pay close attention to index boundaries in arrays (off-by-one errors) and pointer manipulation in linked lists (null pointer exceptions). When tracing recursion in tree traversal, label the output sequence clearly. Use diagrams to visualise tricky stack/queue states. Memorise the time complexities for common operations but understand the reasoning, as questions may ask for best/average/worst cases. For ADT questions, separate the interface from the implementation details. Finally, practise past paper questions on collision handling, BST insertion/deletion, and graph traversal to build speed and accuracy.
IB 和 CCEA 考试中的数据结构题目通常涉及跟踪、伪代码编写和场景分析。始终仔细检查数组中的索引边界（差一错误）和链表中的指针操作（空指针异常）。在跟踪树的递归遍历时，清晰地标注输出序列。使用图表可视化棘手的栈/队列状态。记住常见操作的时间复杂度，但要理解其原理，因为问题可能会询问最佳/平均/最坏情况。对于 ADT 问题，将接口与实现细节分开。最后，通过历年真题练习冲突处理、BST 插入/删除和图遍历，以提高速度和准确性。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导