📚 Data Structures Key Concepts for IB & CIE Computer Science | 数据结构考点精讲
Data structures form the backbone of efficient algorithm design and are a central topic in both IB and CIE A-Level / IGCSE Computer Science syllabuses. Mastering the properties, operations, and use cases of arrays, linked lists, stacks, queues, trees, graphs, and hash tables is essential for tackling both theory papers and practical programming tasks. This revision guide distils the key points you need to know, with clear explanations and bilingual support to strengthen your conceptual understanding.
数据结构是高效算法设计的基石，也是 IB 与 CIE A-Level / IGCSE 计算机科学课程的核心主题。掌握数组、链表、栈、队列、树、图、哈希表等结构的特性、操作及应用场景，对于应对理论考卷和编程实践都至关重要。本复习指南提炼了你必须掌握的关键考点，提供清晰说明与双语对照，助你夯实概念理解。
1. Arrays and Their Applications | 数组及其应用
An array is a static, contiguous block of memory that stores elements of the same data type. Elements are accessed via an index, typically starting at 0, allowing O(1) random access. However, insertion and deletion of elements (except at the end) require shifting, resulting in O(n) time complexity. Both syllabuses expect you to understand one-dimensional and two-dimensional arrays, as well as common operations like traversal, searching, and sorting.
数组是一块静态、连续的内存区域，用于存放相同数据类型的元素。元素通过索引访问，通常从 0 开始，可实现 O(1) 的随机访问。但插入和删除元素（末尾除外）需要移动数据，时间复杂度为 O(n)。两个考纲都要求你理解一维与二维数组，以及遍历、搜索、排序等常见操作。
In IB Computer Science, arrays are often examined through pseudocode tracing and algorithm construction. CIE papers frequently test array manipulation using Python, Java, or VB.NET syntax, including the declaration of arrays and iteration using FOR loops.
在 IB 计算机科学中，数组常通过伪代码追踪和算法构建来考查。CIE 试卷则经常使用 Python、Java 或 VB.NET 语法测试数组操作，包括数组声明和用 FOR 循环遍历。
Key formulas and concepts:
- Memory address calculation for 1D array: Address(A[i]) = Base + i × ElementSize
- 2D array (row-major): Address(A[i][j]) = Base + (i × NumCols + j) × ElementSize
关键公式与概念：
- 一维数组内存地址计算：Address(A[i]) = 基地址 + i × 元素大小
- 二维数组（行优先）：Address(A[i][j]) = 基地址 + (i × 列数 + j) × 元素大小
2. Linked Lists: Singly, Doubly, Circular | 链表：单链表、双链表、循环链表
A linked list is a dynamic data structure consisting of nodes, where each node contains data and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory, allowing O(1) insertion and deletion at the head (or at a known position if a reference is held) but O(n) search time. CIE and IB both cover singly linked lists in depth; doubly linked lists and circular linked lists often appear in higher-tier questions.
链表是一种动态数据结构，由节点组成，每个节点包含数据和指向下一节点的指针。与数组不同，链表不需要连续的内存空间，在头部（或在持有引用的已知位置）插入和删除为 O(1)，但搜索需 O(n)。CIE 与 IB 均深入考查单链表；双链表和循环链表常出现在高阶题目中。
Singly linked list nodes store one link, while doubly linked list nodes store two (next and previous), enabling backward traversal. Circular linked lists have the last node pointing back to the first, useful for round-robin scheduling applications. You should be able to draw node-pointer diagrams, write code for insertion/deletion, and trace algorithms.
单链表节点只存储一个链接，而双链表节点存储两个（后继和前驱），支持反向遍历。循环链表的尾节点指向头节点，适用于轮询调度应用。你需要能画出节点-指针示意图，编写插入/删除代码，并追踪算法。
List traversal: current = current.next
链表遍历：current = current.next
3. Stacks: LIFO Principle and Implementations | 栈：后进先出原理与实现
A stack is a Last-In-First-Out (LIFO) abstract data type where elements are added and removed from the same end, called the top. The primary operations are push (insert) and pop (remove), often supplemented by peek (or top) and isEmpty. Stacks can be implemented using arrays or linked lists. Array-based stacks have a fixed capacity and may overflow; linked-list-based stacks are dynamic.
栈是一种后进先出（LIFO）的抽象数据类型，元素在同一端（称为栈顶）添加与移除。主要操作是 push（入栈）和 pop（出栈），常辅以 peek（或 top）和 isEmpty。栈可用数组或链表实现。基于数组的栈有固定容量，可能溢出；基于链表的栈则为动态。
Applications of stacks include function call management (call stack), expression evaluation (converting infix to postfix), undo mechanisms, and backtracking algorithms. Both IB and CIE require you to trace stack operations and implement simple stack-based algorithms.
栈的应用包括函数调用管理（调用栈）、表达式求值（中缀转后缀）、撤销机制和回溯算法。IB 和 CIE 均要求你追踪栈操作并实现基于栈的简单算法。
| Operation | Description |
| push(item) | Adds item to top; top ← top + 1 (array) |
| pop() | Removes and returns top item; top ← top - 1 |
| peek() | Returns top item without removing |
| 操作 | 描述 |
| push(项) | 将项添加到栈顶；top ← top + 1（数组实现） |
| pop() | 移除并返回栈顶项；top ← top - 1 |
| peek() | 返回栈顶项但不移除 |
4. Queues: FIFO, Priority and Circular | 队列：先进先出、优先级与循环队列
A queue is a First-In-First-Out (FIFO) structure. Elements are added at the rear (enqueue) and removed from the front (dequeue). Like stacks, queues can be implemented with arrays or linked lists. Array-based circular queues use modulo arithmetic to reuse empty slots, avoiding the "false overflow" problem. CIE expects you to understand linear queues, circular queues, and priority queues.
队列是一种先进先出（FIFO）结构。元素在队尾添加（enqueue），从队首移除（dequeue）。与栈类似，队列可用数组或链表实现。基于数组的循环队列使用取模运算来复用空闲位置，避免“假溢出”问题。CIE 要求你理解线性队列、循环队列和优先级队列。
Priority queues process elements based on priority rather than arrival order, commonly implemented using heaps. In IB, the focus is on the FIFO principle and basic queue operations; higher-level CIE papers may include trace questions on circular queues and priority queue algorithms.
优先级队列根据优先级而非到达顺序处理元素，常使用堆来实现。IB 侧重于 FIFO 原则与基本队列操作；高阶 CIE 试卷可能包含循环队列追踪和优先级队列算法题。
Circular enqueue: rear = (rear + 1) MOD MaxSize; Queue[rear] = item
循环入队：rear = (rear + 1) MOD 最大容量; Queue[rear] = 项
5. Trees: Binary Trees, BST, Traversals | 树：二叉树、二叉搜索树、遍历
Trees are hierarchical data structures consisting of nodes connected by edges. A binary tree has at most two children per node. A Binary Search Tree (BST) maintains order: left subtree values < node value < right subtree values, allowing efficient O(log n) search on average. Both IB and CIE examine tree construction, traversal (preorder, inorder, postorder), and BST operations.
树是一种由边连接节点的层次数据结构。二叉树每个节点最多有两个子节点。二叉搜索树（BST）保持有序性：左子树数值 < 节点数值 < 右子树数值，平均情况下可实现 O(log n) 的高效搜索。IB 与 CIE 均考查树的构建、遍历（前序、中序、后序）以及 BST 操作。
You must be able to produce traversal sequences from a diagram and reconstruct a tree from given traversals. Recursive algorithms are commonly used for tree operations. The depth of a balanced tree is approximately log₂n, while a degenerate tree behaves like a linked list (O(n) search).
你必须能从图示中得出遍历序列，并根据给定遍历顺序重建树。递归算法常用于树的操作。平衡树的深度约为 log₂n，而退化的树表现如同链表（搜索 O(n)）。
Inorder traversal: left subtree → visit node → right subtree
中序遍历：左子树 → 访问节点 → 右子树
6. Graphs: Representations and Algorithms | 图：表示法与算法
Graphs model networks of vertices (nodes) and edges. They can be directed or undirected, weighted or unweighted. The two primary representations are the adjacency matrix (a 2D array; O(1) edge query, O(V²) space) and the adjacency list (an array of lists; O(degree) edge query, O(V+E) space). CIE frequently tests graph traversal algorithms: Breadth-First Search (BFS) using a queue and Depth-First Search (DFS) using a stack or recursion.
图用于模拟由顶点（节点）和边构成的网络。图可以是有向或无向、加权或非加权的。两种主要表示法是邻接矩阵（二维数组；O(1) 边查询，O(V²) 空间）和邻接表（列表数组；O(degree) 边查询，O(V+E) 空间）。CIE 常考图遍历算法：使用队列的广度优先搜索（BFS）和使用栈或递归的深度优先搜索（DFS）。
IB focuses on understanding graph terminology (paths, cycles, connected components) and applying graphs to real-world scenarios like social networks and transportation. Both boards expect you to trace Dijkstra's shortest path algorithm for weighted graphs.
IB 侧重于理解图术语（路径、环、连通分量）以及将图应用于社交网络、交通等现实场景。两个考局都要求你能够追踪加权图的 Dijkstra 最短路径算法。
jkstra relaxation: if dist[u] + weight(u,v) < dist[v] then dist[v] = dist[u] + weight(u,v)
Dijkstra 松弛操作：若 dist[u] + 权重(u, v) < dist[v] 则更新 dist[v] = dist[u] + 权重(u, v)
7. Hash Tables: Hashing and Collision Resolution | 哈希表：哈希与冲突解决
A hash table maps keys to values using a hash function to compute an index. The average case for search, insertion, and deletion is O(1), making it extremely efficient for dictionary operations. Collisions occur when two keys hash to the same index. Collision resolution methods include chaining (storing a linked list of items at the index) and open addressing (linear probing, quadratic probing, double hashing).
哈希表通过哈希函数计算索引，将键映射到值。搜索、插入和删除的平均时间复杂度为 O(1)，使其在字典操作中极为高效。当两个键哈希到相同索引时发生冲突。冲突解决方法包括链地址法（在索引处存储链表）和开放寻址法（线性探测、二次探测、双重哈希）。
tor (α = n/m, where n = entries, m = table size). A high load factor degrades performance.
IB 和 CIE 均要求对哈希表、哈希算法及冲突解决方法对性能的影响有概念性理解。你需要能够模拟使用给定哈希函数的插入过程，并解释装填因子（α = n/m，n = 条目数，m = 表大小）。装填因子过高会降低性能。
| Method | Description |
| Chaining | Each slot holds a linked list; unlimited capacity |
| Linear probing | Check next slot until empty: h(k, i) = (h'(k) + i) MOD m |
| 方法 | 描述 |
| 链地址法 | 每个槽存放一个链表；容量无限 |
| 线性探测 | 依次检查下一槽直到空位：h(k, i) = (h'(k) + i) MOD m |
8. Abstract Data Types (ADTs) | 抽象数据类型
An abstract data type (ADT) defines a data structure purely by its behavior (operations) from the user's perspective, independent of implementation. Stacks, queues, lists, trees, and dictionaries are all ADTs. IB places strong emphasis on distinguishing between ADTs and their concrete implementations, often asking students to describe the operations of an ADT without reference to how it is coded.
抽象数据类型（ADT）从用户角度仅通过其行为（操作）来定义数据结构，与具体实现无关。栈、队列、列表、树和字典都属于 ADT。IB 特别强调区分 ADT 与其具体实现，常要求学生描述 ADT 的操作，而不涉及编码方式。
For example, a stack ADT specifies push, pop, and peek operations. It can be implemented using an array or a linked list, but the user does not need to know the internal details. This encapsulation is a key concept in modular program design.
例如，栈 ADT 规定了 push、pop 和 peek 操作。它可用数组或链表实现，但用户无需了解内部细节。这种封装是模块化程序设计中的关键概念。
CIE also expects you to recognise ADTs, particularly in the context of generic programming and collection classes available in the examined languages. You should be able to select the most appropriate ADT for a given problem scenario.
CIE 也要求你识别 ADT，特别是在泛型编程与所考语言提供的集合类场景中。你应能为给定问题场景选择最合适的 ADT。
9. Algorithm Complexity and Efficiency | 算法复杂度与效率
Big O notation expresses the upper bound of an algorithm's time or space complexity. Constant O(1), logarithmic O(log n), linear O(n), linearithmic O(n log n), quadratic O(n²), and exponential O(2ⁿ) are the most common classes. Both IB and CIE require comparative analysis of algorithms based on their growth rates.
大 O 记号表示算法时间复杂度或空间复杂度的上界。常见类别包括常数 O(1)、对数 O(log n)、线性 O(n)、线性对数 O(n log n)、平方 O(n²) 和指数 O(2ⁿ)。IB 与 CIE 都要求基于增长速率对算法进行比较分析。
You must be able to derive the complexity of basic operations on data structures (e.g., array access vs. linked list search) and of common algorithms (search and sort). Understanding best-case, worst-case, and average-case scenarios is essential.
你必须能够推导出数据结构基本操作（如数组访问与链表搜索）以及常用算法（搜索与排序）的复杂度。理解最佳情况、最坏情况和平均情况至关重要。
| Data Structure | Access | Search | Insert | Delete |
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) |
| Hash Table | N/A | O(1) avg | O(1) avg | O(1) avg |
10. Comparing Static vs Dynamic Structures | 静态与动态结构比较
A key exam point is contrasting static structures (like arrays) with dynamic structures (like linked lists). Static structures have fixed size determined at compile time; dynamic structures can grow and shrink at runtime using heap memory. The trade-off involves memory waste (static structures may reserve unused space) versus overhead (dynamic structures store pointers). CIE often asks for memory allocation and deallocation considerations.
一个关键的考点是比较静态结构（如数组）与动态结构（如链表）。静态结构在编译时确定固定大小；动态结构可在运行时使用堆内存增长和收缩。权衡在于内存浪费（静态结构可能保留未用空间）与额外开销（动态结构存储指针）。CIE 常问及内存分配与释放的考虑。
IB students should be able to discuss the advantages of dynamic data structures in contexts where the maximum size is unknown. A classic example is a text editor's undo stack: a fixed-size array could overflow, but a linked-list-based stack will never be full while memory is available.
IB 学生应能讨论在最大尺寸未知的情况下动态数据结构的优势。一个经典例子是文本编辑器的撤销栈：固定大小的数组可能溢出，而基于链表的栈只要内存可用就不会满。
11. Recursion and Data Structures | 递归与数据结构
Recursion is a powerful technique where a function calls itself, and it appears naturally with hierarchical data structures like trees and graphs. Preorder, inorder, and postorder traversals are elegantly expressed recursively. IB and CIE both test recursion tracing, base cases, and the stack-based nature of recursive calls (each call creates a new stack frame).
递归是一种函数调用自身的强大技术，在树、图等层次数据结构中自然出现。前序、中序和后序遍历都能以递归方式优雅地表达。IB 与 CIE 都考查递归追踪、基线条件，以及递归调用的栈本质（每次调用创建新的栈帧）。
Problems like computing tree height, counting nodes, and searching a BST are typical recursion questions. You must identify the base case (e.g., if node is null) and the recursive case, ensuring the argument moves toward the base case.
计算树高、统计节点数、搜索 BST 等问题是典型的递归考题。你必须识别基线条件（如节点为空）和递归情况，确保参数向基线条件推进。
root.value then return root; else if key < root.value then search left; else search right.
递归 BST 搜索：若根为空或 key == root.value 则返回 root；否则若 key < root.value 搜索左子树；否则搜索右子树。
12. Exam Question Tactics and Common Pitfalls | 考题策略与常见陷阱
When answering data structure questions, always annotate diagrams clearly and show intermediate steps in algorithm traces. For coding questions, use variable names that reflect their purpose (e.g., head, tail, top) and handle edge cases (empty structure, single element). In IB, pay close attention to pseudocode conventions and the use of constructs like 'loop while', 'if...else', and array indexing.
在回答数据结构问题时，务必清晰标注图示，并在算法追踪中展示中间步骤。对于编码题，使用反映用途的变量名（如 head、tail、top），并处理边界情况（空结构、单元素）。在 IB 中，要特别注意伪代码约定以及诸如 ‘loop while’、‘if...else’ 和数组索引等构造的使用。
A common pitfall is confusing tree traversal orders; remember: inorder gives sorted output for BSTs, preorder visits the root first, and postorder visits children before the root. In queue implementations, forgetting to update front and rear pointers after operations or not handling the circular condition correctly costs marks. Always check for overflow and underflow.
常见陷阱是混淆树的遍历顺序；记住：中序遍历 BST 得到排序输出，前序先访问根，后序在孩子之后访问根。在队列实现中，忘记在操作后更新 front 和 rear 指针，或未正确处理循环条件会失分。务必检查溢出和下溢。
Finally, remember that CIE Python papers often provide built-in list methods; you can use append/pop for stacks, but must demonstrate how to implement the ADT from scratch if asked. Explaining the reasoning behind your chosen data structure (why a hash table over a binary tree, for instance) brings higher marks in extended response questions.
最后，记住 CIE Python 试卷常提供内置列表方法；你可以用 append/pop 实现栈，但若被要求从头实现 ADT，则必须展示其原理。在扩展回答题中，解释选择数据结构的理由（例如为何用哈希表而不用二叉树）能获得高分。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图