Data Structures for IB & Edexcel Computer Science | IB Edexcel 计算机：数据结构考点精讲

📚 Data Structures for IB & Edexcel Computer Science | IB Edexcel 计算机：数据结构考点精讲

Data structures are fundamental building blocks in computer science, organising and storing data in memory for efficient access and modification. For IB and Edexcel Computer Science students, mastering key data structures such as arrays, linked lists, stacks, queues, trees, hash tables, and graphs is essential for solving algorithmic problems and understanding abstract data types. This revision guide covers core concepts, operations, typical applications, and common exam pitfalls.

数据结构是计算机科学中的基本构建模块，在内存中组织和存储数据以实现高效访问和修改。对于IB和Edexcel计算机科学学生来说，掌握数组、链表、栈、队列、树、哈希表和图形等关键数据结构，对于解决算法问题和理解抽象数据类型至关重要。本复习指南涵盖核心概念、操作、典型应用以及常见考试易错点。

1. What is a Data Structure? | 什么是数据结构？

A data structure is a systematic way of organising and storing data in memory to enable efficient operations such as insertion, deletion, searching, and traversal. The choice of data structure directly impacts an algorithm’s performance.

数据结构是在内存中组织和存储数据的系统方法，以实现插入、删除、搜索和遍历等高效操作。数据结构的选择直接影响算法的性能。

An Abstract Data Type (ADT) provides a logical description of the data and the operations allowed, hiding the implementation details. For example, a Stack ADT defines push and pop operations, but the underlying implementation could use an array or a linked list.

抽象数据类型（ADT）提供了对数据和允许操作的逻辑描述，隐藏实现细节。例如，栈ADT定义了push和pop操作，但底层实现可以使用数组或链表。

Common data structures tested in IB and Edexcel syllabi include arrays, linked lists, stacks, queues, trees, hash tables, and graphs. Understanding how they work and when to use them is crucial for problem-solving.

IB和Edexcel课程中考查的常见数据结构包括数组、链表、栈、队列、树、哈希表和图形。理解它们如何工作以及何时使用对于解决问题至关重要。

2. Static vs Dynamic Data Structures | 静态与动态数据结构

Static data structures have a fixed size allocated at compile time. An example is an array, whose capacity is defined when it is created and cannot be easily changed during execution.

静态数据结构在编译时分配固定大小。例如数组，其容量在创建时定义，并且在执行期间不能轻易更改。

Dynamic data structures can grow or shrink at runtime, allocating memory as needed. Linked lists are classic dynamic structures, where nodes are created and linked together without needing a pre-defined maximum size.

动态数据结构可以在运行时增长或收缩，根据需要分配内存。链表是典型的动态结构，其中节点被创建并链接在一起，不需要预先定义的最大大小。

A comparison: static structures offer fast access to elements (e.g., O(1) for array indexing) but waste memory if allocated size is larger than needed; dynamic structures use memory efficiently but have overhead for storing pointers and may exhibit slower access due to non-contiguous memory.

比较：静态结构提供对元素的快速访问（例如，数组索引的O(1)），但如果分配的大小大于所需则会浪费内存；动态结构有效利用内存，但存储指针有开销，并且由于非连续内存可能访问速度较慢。

3. Arrays and Their Operations | 数组及其操作

An array stores elements of the same data type in contiguous memory locations. Each element can be accessed directly via its index in O(1) time, making arrays ideal for random access.

数组在连续的内存位置存储相同数据类型的元素。每个元素可以通过其索引在O(1)时间内直接访问，这使得数组非常适合随机访问。

Common operations: insertion at a specific position requires shifting subsequent elements, taking O(n) time in the worst case. Deletion also takes O(n) because of shifting. Appending at the end is O(1) if there is space.

常见操作：在特定位置插入需要移动后续元素，最坏情况下需要O(n)时间。删除也需要O(n)时间因为需要移动。如果还有空间，在末尾追加是O(1)。

Arrays are commonly used to implement other data structures like stacks and queues. Multidimensional arrays (e.g., 2D arrays) are useful for representing matrices, grids, or game boards.

数组通常用于实现其他数据结构，如栈和队列。多维数组（例如二维数组）用于表示矩阵、网格或游戏棋盘。

4. Linked Lists: Singly and Doubly | 链表：单链表与双向链表

A linked list consists of nodes, each containing data and a pointer (or reference) to the next node. In a singly linked list, traversal is only forward; in a doubly linked list, each node also has a pointer to the previous node, allowing bidirectional traversal.

链表由节点组成，每个节点包含数据和一个指向下一个节点的指针（或引用）。在单链表中，遍历只能是向前的；在双向链表中，每个节点还有一个指向前一个节点的指针，允许双向遍历。

Insertion and deletion at the head of a linked list are O(1) operations, as they only require changing pointers. However, accessing an element by position requires O(n) time because the list must be traversed from the head.

在链表头部插入和删除是O(1)操作，因为它们只需要改变指针。但是，按位置访问元素需要O(n)时间，因为必须从头遍历链表。

Linked lists use memory more flexibly than arrays, but they have higher memory overhead due to storing pointers and are less cache-friendly. They are often used to implement stacks, queues, and dynamic memory allocation.

链表比数组更灵活地使用内存，但由于存储指针而具有更高的内存开销，并且缓存友好性较差。它们通常用于实现栈、队列和动态内存分配。

5. Stacks (LIFO) | 栈（后进先出）

A stack is a Last-In-First-Out (LIFO) data structure. The main operations are push (add an item to the top) and pop (remove the item from the top). Peek returns the top element without removing it.

栈是一种后进先出（LIFO）数据结构。主要操作是push（将项添加到顶部）和pop（从顶部移除项）。Peek返回顶部

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

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