IB Computer Science Data Structures Key Concepts | IB 计算机：数据结构考点精讲

📚 IB Computer Science Data Structures Key Concepts | IB 计算机：数据结构考点精讲

Data structures are fundamental building blocks in computer science, allowing programs to store, organise, and manipulate data efficiently. For IB Computer Science students, mastering data structures is essential not only for the examination but also for developing algorithmic thinking. This article revisits the core data structures prescribed in the IB syllabus, explains their properties, operations, advantages, and typical use cases, and provides clear comparisons to support your revision.

数据结构是计算机科学的基础构件，它使程序能够高效地存储、组织和处理数据。对于 IB 计算机科学的学生来说，掌握数据结构不仅对考试至关重要，也有助于培养算法思维。本文重温 IB 大纲规定的核心数据结构，解释它们的特性、操作、优势及典型应用场景，并提供清晰的对比，助力你的复习。

1. What Are Data Structures? | 什么是数据结构？

A data structure is a specialised format for organising, processing, retrieving, and storing data. In IB Computer Science, we distinguish between logical data structures (how data is viewed abstractly) and physical data structures (how data is actually stored in memory). Logical structures include arrays, stacks, queues, linked lists, trees, and graphs. Physical structures refer to how these are implemented in memory, such as using contiguous blocks or pointers. Understanding both perspectives helps you design efficient algorithms and manage resources effectively.

数据结构是用于组织、处理、检索和存储数据的专用格式。在 IB 计算机科学中，我们需要区分逻辑数据结构（抽象层面如何看待数据）和物理数据结构（数据实际在内存中的存储方式）。逻辑结构包括数组、栈、队列、链表、树和图。物理结构则指它们在内存中的实现方式，例如使用连续内存块或指针。理解这两个视角有助于设计高效算法并有效管理资源。

2. Arrays and Their Characteristics | 数组及其特性

An array is a collection of elements of the same data type, stored in contiguous memory locations. Each element can be accessed directly using an index, typically starting from 0. Arrays have a fixed size in many languages, and insertion or deletion in the middle requires shifting elements, which is O(n) time complexity. However, random access is O(1), making arrays extremely efficient for read-heavy operations. Multidimensional arrays are used to represent matrices, tables, or grids.

数组是同一种数据类型元素的集合，存储在连续的内存位置中。每个元素可以通过索引直接访问，索引通常从 0 开始。在许多语言中数组大小固定，在中间插入或删除元素需要移动其他元素，时间复杂度为 O(n)。但随机访问复杂度为 O(1)，使数组在读取密集型操作中非常高效。多维数组用于表示矩阵、表格或网格。

Key operations include traversal, insertion, deletion, searching, and updating. In IB exams, you may be asked to trace pseudocode that uses arrays, or to write algorithms to find maximum values, compute sums, or perform linear/binary search. For binary search, the array must be sorted, and the time complexity is O(log n).

关键操作包括遍历、插入、删除、查找和更新。在 IB 考试中，你可能需要跟踪使用数组的伪代码，或编写算法寻找最大值、计算总和或执行线性/二分查找。对于二分查找，数组必须有序，时间复杂度为 O(log n)。

3. Linked Lists | 链表

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, so they can grow and shrink during execution. Insertion and deletion at the beginning of a singly linked list are O(1), but accessing an element by index requires traversing from the head, which is O(n). There are singly linked lists, doubly linked lists (with references to both next and previous), and circular linked lists.

链表是一种动态数据结构，由节点组成，每个节点包含数据和指向下一个节点的引用（或指针）。与数组不同，链表不需要连续内存，因此可以在执行期间增长和收缩。在单链表中，在头部插入和删除的时间复杂度为 O(1)，但通过索引访问元素需要从头遍历，复杂度为 O(n)。链表分单链表、双链表（同时有前驱和后继引用）以及循环链表。

In IB, you are expected to understand the basic operations: creating a linked list, adding a node, deleting a node, and traversing. You should be able to illustrate these operations with diagrams and describe how pointer manipulation works. Linked lists are often compared with arrays in terms of memory usage and performance; linked lists use extra memory for pointers but avoid the cost of resizing an array.

在 IB 中，你需要理解链表的基操作：创建链表、添加节点、删除节点和遍历。你应该能够用图示说明这些操作，并描述指针操作的工作原理。链表常与数组在内存使用和性能方面进行比较；链表需要额外的指针内存，但避免了数组扩容的代价。

4. Stacks | 栈

A stack is a Last-In-First-Out (LIFO) abstract data type. Elements are added (pushed) and removed (popped) only from the top. Stacks can be implemented using arrays or linked lists. Common applications include expression evaluation, backtracking algorithms, undo mechanisms in software, and call stack management in program execution. In IB, you may encounter stack-based trace questions where you need to simulate push and pop operations and show the state of the stack after a series of commands.

栈是一种后进先出（LIFO）的抽象数据类型。元素只能从顶部添加（压入）和移除（弹出）。栈可以用数组或链表实现。常见的应用包括表达式求值、回溯算法、软件中的撤销机制以及程序执行中的调用栈管理。在 IB 中，你可能会遇到基于栈的跟踪题，需要模拟压入和弹出操作，并展示一系列命令后栈的状态。

The stack operations are push(item), pop(), peek() (returns top without removing), and isEmpty(). All basic operations are O(1). Understanding how stacks manage recursive function calls is also important: each call creates a new stack frame holding local variables and return addresses.

栈的操作包括 push(item)、pop()、peek()（返回顶部元素但不移除）和 isEmpty()。所有基本操作的时间复杂度均为 O(1)。理解栈如何管理递归函数调用也很重要：每次调用创建一个新的栈帧，存储局部变量和返回地址。

5. Queues | 队列

A queue is a First-In-First-Out (FIFO) abstract data type. Elements are added at the rear (enqueue) and removed from the front (dequeue). Queues model real-world waiting lines and are used in scheduling, buffering, and breadth-first search algorithms. A priority queue assigns a priority to each element, and the element with the highest priority is dequeued first; this is often implemented using a heap.

队列是一种先进先出（FIFO）的抽象数据类型。元素从队尾添加（入队），从队头移除（出队）。队列模拟现实中的排队，用于调度、缓冲和广度优先搜索算法。优先队列为每个元素分配优先级，优先级最高的元素最先出队；这通常使用堆来实现。

Basic operations include enqueue(item), dequeue(), peek(), isEmpty(), and isFull() for fixed-size implementations. Circular queues overcome the limitation of simple array-based queues where unused space cannot be reused after dequeues. IB may ask you to trace queue operations or implement a queue using arrays with front and rear pointers.

基本操作包括 enqueue(item)、dequeue()、peek()、isEmpty() 以及针对固定大小的 isFull()。循环队列克服了简单数组队列在出队后无法复用未使用空间的局限。IB 可能会要求你跟踪队列操作，或者使用带有 front 和 rear 指针的数组实现一个队列。

6. Trees | 树

A tree is a hierarchical data structure consisting of nodes connected by edges. The topmost node is the root, and each node may have child nodes. A binary tree restricts each node to at most two children. Trees are used to represent hierarchical data such as file systems, organisational charts, and decision processes. In IB, you need to understand tree terminology: root, leaf, parent, child, sibling, depth, height, and subtree.

树是一种由节点和边组成的层次数据结构。最顶端的节点称为根，每个节点可以有子节点。二叉树限制每个节点最多有两个子节点。树用于表示文件系统、组织结构图和决策过程等层次数据。在 IB 中，你需要理解树的相关术语：根、叶、父节点、子节点、兄弟节点、深度、高度和子树。

Tree traversals are essential: pre-order (root, left, right), in-order (left, root, right), and post-order (left, right, root). For binary search trees, in-order traversal yields sorted data. Traversals can be implemented recursively or iteratively using a stack. You should be able to draw a binary tree given a traversal sequence and reconstruct the tree from two sequences.

树的遍历至关重要：前序遍历（根、左、右）、中序（左、根、右）和后序（左、右、根）。对于二叉搜索树，中序遍历会产生有序的数据。遍历可以用递归或使用栈迭代实现。你应该能够根据遍历序列绘制二叉树，并从两个序列重建树。

7. Binary Search Trees | 二叉搜索树

A binary search tree (BST) is a binary tree where for each node, all values in the left subtree are smaller, and all values in the right subtree are greater. This ordering allows efficient searching, insertion, and deletion. On average, these operations take O(log n) time if the tree is balanced, but in the worst case (degenerated to a linked list), they become O(n). Balancing techniques, such as AVL trees or red-black trees, are beyond IB scope but highlight the importance of keeping trees balanced.

二叉搜索树（BST）是一种二叉树，其中对于每个节点，左子树中的所有值均小于该节点，右子树中的所有值均大于该节点。这种排序特性使得搜索、插入和删除操作高效。平均情况下，如果树是平衡的，这些操作的时间复杂度为 O(log n)，但在最坏情况下（退化为链表），时间复杂度为 O(n)。平衡技术如 AVL 树或红黑树超出了 IB 大纲，但它们凸显了保持树平衡的重要性。

Insertion into a BST involves comparing the new value with the current node and recursively moving left or right until an empty spot is found. Deletion has three cases: node with no children (simply remove), node with one child (bypass), and node with two children (replace with in-order successor or predecessor). IB exams often feature questions where you draw the BST after a sequence of insertions and deletions.

在 BST 中插入节点时，将新值与当前节点比较，递归向左或向右移动直到找到空位。删除节点有三种情形：无子节点（直接移除）、有一个子节点（绕过）、有两个子节点（用中序后继或前驱替代）。IB 考试经常出现要求你在序列插入和删除后绘制 BST 的题目。

8. Graphs | 图

A graph is a collection of vertices (nodes) and edges (connections) that can represent networks, maps, social connections, and many other relationships. Graphs can be directed or undirected, weighted or unweighted. IB students should understand representation methods: adjacency matrix (a 2D array where a[i][j] indicates presence/weight of edge) and adjacency list (an array of lists, each storing adjacent vertices). The matrix uses O(V²) space, while the list uses O(V+E), which is more efficient for sparse graphs.

图是顶点（节点）和边（连接）的集合，可以表示网络、地图、社交关系等。图可以分为有向或无向、加权或非加权。IB 学生应理解图的表示方法：邻接矩阵（二维数组，a[i][j] 表示该边是否存在或权值）和邻接表（一个列表数组，每个列表存储邻接顶点）。矩阵占用 O(V²) 空间，而邻接表占用 O(V+E)，对于稀疏图更高效。

Graph traversal algorithms include depth-first search (DFS) and breadth-first search (BFS). DFS uses a stack (either recursively or explicitly) and explores as deep as possible before backtracking. BFS uses a queue and explores neighbours level by level, finding shortest paths in unweighted graphs. In IB, you may be required to perform these traversals on given graphs and list the order of visited nodes.

图的遍历算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。DFS 使用栈（递归或显式）并尽可能深入探索后再回溯。BFS 使用队列，逐层探索邻居，在无权图中寻找最短路径。在 IB 中，你可能需要在给定图上执行这些遍历并列出访问节点的顺序。

9. Hash Tables | 哈希表

A hash table (or hash map) stores key-value pairs and provides average O(1) time for insertion, deletion, and search. It uses a hash function to compute an index into an array of buckets, from which the desired value can be found. Collisions occur when two keys hash to the same index. Collision resolution techniques include chaining (each bucket holds a linked list of entries) and open addressing (linear probing, quadratic probing). A good hash function distributes keys uniformly to minimise collisions.

哈希表（或哈希映射）存储键值对，平均在 O(1) 时间内完成插入、删除和搜索。它使用哈希函数计算数组桶的索引，从而找到所需值。当两个键散列到同一索引时会发生冲突。冲突解决方法包括链地址法（每个桶存放一个条目链表）和开地址法（线性探测、二次探测）。好的哈希函数均匀分布键以尽量减少冲突。

For IB, you need to understand the concept of a hash table, the role of the hash function, and how collisions are handled. You might be asked to trace the insertion of elements into a hash table with a given hash function and collision resolution strategy, or to discuss the impact of the load factor on performance. While not always explicitly labelled ‘hash table’ in every past paper, it is part of the HL topic.

在 IB 中，你需要理解哈希表的概念、哈希函数的作用以及如何处理冲突。你可能会被要求跟踪使用给定哈希函数和冲突解决策略将元素插入哈希表的过程，或讨论负载因子对性能的影响。虽然并非每份真题都明确标记为“哈希表”，但它是 HL 专题的一部分。

10. Choosing the Right Data Structure | 选择合适的数据结构

The choice of data structure significantly affects the efficiency and clarity of a program. Arrays offer fast indexed access but costly insertions; linked lists provide flexible insertions/deletions but slower search. Stacks are ideal for LIFO scenarios, queues for FIFO scenarios. Trees and graphs model hierarchical and networked data, respectively. Hash tables offer near-constant lookup. In IB exam scenario questions, you must justify your choice based on the operations required (e.g., frequent random access, many insertions, key-based retrieval). Analysing time and space complexity is crucial.

数据结构的选择对程序的效率和清晰度有重大影响。数组提供快速的索引访问但插入开销大；链表提供灵活的插入/删除但搜索较慢。栈适用于 LIFO 场景，队列适用于 FIFO 场景。树和图分别用于建模层次数据和网络数据。哈希表提供近乎常数时间的查找。在 IB 考试的情景题中，你必须根据所需操作来论证你的选择（例如频繁随机访问、大量插入、基于键的检索）。分析时间和空间复杂度至关重要。

A comparison table can help summarise core properties:

一个对比表格有助于总结核心特性：

Data Structure	Access	Insertion/Deletion	Use Case
Array	O(1) random	O(n) (middle)	Fixed-size collections, matrices
Linked List	O(n)	O(1) at head	Dynamic data, frequent add/remove
Stack	O(n) (top O(1))	O(1) top	Undo, recursion, backtracking
Queue	O(n) (front O(1))	O(1) rear/front	Scheduling, BFS, buffering
Binary Search Tree	O(log n) avg	O(log n) avg	Sorted data, dictionary
Hash Table	O(1) avg	O(1) avg	Fast key-based lookup

中文翻译：

数据结构	访问	插入/删除	使用场景
数组	O(1) 随机	O(n)（中间）	固定大小集合、矩阵
链表	O(n)	头 O(1)	动态数据、频繁增删
栈	O(n)（顶 O(1)）	顶 O(1)	撤销、递归、回溯
队列	O(n)（头 O(1)）	尾/头 O(1)	调度、BFS、缓冲
二叉搜索树	平均 O(log n)	平均 O(log n)	排序数据、字典
哈希表	平均 O(1)	平均 O(1)	快速键值查找

Finally, practising past paper questions and writing pseudocode for these structures will cement your understanding. Remember to link your answers to the abstract data type (ADT) concept, which separates the logical behaviour from implementation details. With a solid grasp of data structures, you will be well prepared for both Paper 1 and the internal assessment.

最后，练习历年真题并为这些结构编写伪代码将巩固你的理解。记得将你的答案与抽象数据类型（ADT）概念联系起来，它将逻辑行为与实现细节分离。扎实掌握数据结构后，你将为试卷一和内部评估做好充分准备。

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

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

IB Computer Science Data Structures Key Concepts | IB 计算机：数据结构 考点精讲