Data Structures for IGCSE OCR Computer Science | IGCSE OCR 计算机：数据结构考点精讲

📚 Data Structures for IGCSE OCR Computer Science | IGCSE OCR 计算机：数据结构考点精讲

Data structures are the building blocks that allow programs to store, organise, and manipulate data efficiently. In the IGCSE OCR Computer Science course, you are expected to understand how arrays, records, lists, stacks, and queues work, and to be able to choose the most appropriate structure for a given scenario. This article breaks down each topic with clear explanations, examples, and comparisons to help you master the content for your exam.

数据结构是让程序能高效地存储、组织与操作数据的构建块。在 IGCSE OCR 计算机科学课程中，你需要理解数组、记录、列表、堆栈和队列的工作原理，并能为给定的场景选择最合适的数据结构。本文将通过清晰的解释、示例与对比，帮助你逐一掌握这些内容，轻松应对考试。

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

A data structure is a specialised format for organising, processing, retrieving, and storing data. It defines the relationship between data items and the operations that can be performed on them. Choosing the right data structure can make a program faster and more memory efficient.

数据结构是一种用于组织、处理、检索和存储数据的专用格式。它定义了数据项之间的关系以及可以在其上执行的操作。选择正确的数据结构可以使程序更快、更节省内存。

In IGCSE OCR, we focus on static and dynamic structures: some have a fixed size (static), like arrays, while others can grow or shrink as needed (dynamic), like lists. Understanding the strengths and limitations of each is key to writing good code and answering exam questions correctly.

在 IGCSE OCR 中，我们关注静态结构和动态结构：有些具有固定大小（静态），例如数组；而另一些可以根据需要增长或缩小（动态），例如列表。理解每种结构的优点和局限性是编写好代码和正确回答考试问题的关键。

2. Variables, Constants, and Data Types | 变量、常量与数据类型

Before diving into data structures, it is worth recalling the basic building blocks: a variable is a named storage location that can hold a value that may change during execution. A constant is similar but its value cannot be changed once assigned. Both must have a data type, such as Integer, Real, Boolean, Char, or String.

在深入数据结构之前，有必要回顾一下基本构建块：变量是一个命名的存储位置，可以保存在执行过程中可能改变的值。常量类似，但一旦赋值之后其值就不能再改变。两者都必须有一个数据类型，比如整型、实型、布尔型、字符或字符串。

Data structures are essentially collections of variables and constants organised in a particular way. For example, an array is a collection of elements all of the same data type, whereas a record is a collection of fields that may have different data types.

数据结构本质上就是以特定方式组织起来的变量和常量的集合。例如，数组是同一数据类型元素的集合，而记录是可能具有不同数据类型的字段的集合。

3. One-Dimensional Arrays | 一维数组

An array is a static data structure that holds a fixed number of elements of the same data type. Each element can be accessed directly using its index (position). Indices typically start at 0. The size of the array is declared upfront and cannot be changed during execution.

数组是一种静态数据结构，用于保存固定数量的、同一数据类型的元素。每个元素都可以通过其索引（位置）直接访问。索引通常从0开始。数组的大小在声明时就已确定，且在执行期间不能改变。

Declaration in pseudocode: ARRAY scores[5] OF INTEGER
中文说明： 伪代码声明：ARRAY scores[5] OF INTEGER
Access: scores[0] ← 95
中文说明： 访问：scores[0] ← 95

Common operations include traversing (visiting every element using a loop), inserting (if there is space), deleting (shifting elements left), and searching (linear search or binary search if sorted). Arrays are very fast at reading elements by index but are inefficient when inserting or deleting elements in the middle because all subsequent elements must be shifted.

常见操作包括遍历（使用循环访问每个元素）、插入（如果有空间）、删除（向左移动元素）和搜索（线性搜索或二分搜索（如果已排序））。数组通过索引读取元素的速度非常快，但在中间插入或删除元素时效率低下，因为后续所有元素都必须移动。

Example: scores = [83, 91, 78, 89, 94]

4. Two-Dimensional Arrays | 二维数组

A two-dimensional array can be thought of as a table with rows and columns. It is still static and all elements must be of the same data type. Each element is identified by two indices: row and column, for example grid[2][3].

二维数组可以看作是一个具有行和列的表格。它依然是静态的，且所有元素必须具有相同的数据类型。每个元素由两个索引标识：行和列，例如 grid[2][3]。

Typical use cases include representing a chessboard, a spreadsheet, or pixel data in an image. In the exam, you may be asked to write pseudocode that iterates through every element using nested loops, or to read from and write to specific cells.

典型的应用场景包括表示棋盘、电子表格或图像中的像素数据。在考试中，你可能需要编写伪代码，使用嵌套循环遍历每个元素，或者读取和写入特定的单元格。

grid[row][column] ← value

Be careful with indices: OCR pseudocode often uses 0-based indexing, but some questions may refer to the first element as position 1. Always read the question carefully.

注意索引：OCR 伪代码通常使用基于0的索引，但有些题目可能将第一个元素称为位置1。一定要仔细审题。

5. Records | 记录

A record is a data structure that groups related items of possibly different data types into a single unit. Each item in a record is called a field. Unlike an array, a record can store an integer, a string, and a boolean together, each with its own field name.

记录是一种数据结构，它将可能属于不同数据类型的相关项目组合成一个单元。记录中的每个项目称为一个字段。与数组不同，记录可以将整数、字符串和布尔值存储在一起，每个值都有各自的字段名称。

Records are often used to represent real-world entities, such as a student or a book. In pseudocode, you define a record type and then declare variables of that type.

记录通常用于表示现实世界中的实体，例如学生或书籍。在伪代码中，你需要先定义一个记录类型，然后声明该类型的变量。

TYPE Student
    name AS STRING
    age AS INTEGER
    enrolled AS BOOLEAN
END TYPE

DECLARE pupil AS Student
pupil.name ← "Alice"
pupil.age ← 15
pupil.enrolled ← TRUE

Accessing a field uses dot notation. Arrays of records are very common, for example an array of Student records to hold a class register.

访问字段使用点号表示法。记录数组非常常见，例如用一个 Student 记录数组来存放班级名单。

6. Lists (Dynamic Arrays) | 列表（动态数组）

In many programming languages, a list (or dynamic array) is similar to an array but its size can change at runtime. Elements can be added or removed without needing to declare a maximum size upfront. Most lists also provide built-in methods like append(), remove(), insert(), sort().

在许多编程语言中，列表（或动态数组）类似于数组，但其大小可以在运行时改变。可以添加或删除元素，而无需事先声明最大大小。大多数列表还提供了内置的方法，例如 append()、remove()、insert()、sort()。

OCR often asks about the difference between an array and a list. Remember: arrays are static (fixed size), lists are dynamic (resizable). Lists are more flexible for situations where the number of data items is not known in advance, but they may use slightly more memory due to the overhead of managing resizing.

OCR 经常考查数组和列表之间的区别。请记住：数组是静态的（固定大小），列表是动态的（可调整大小）。列表对于数据项数量不确定的情况更灵活，但由于管理调整大小的开销，它们可能会占用稍多一点的内存。

In pseudocode, lists often appear with commands like myList.add(item) or myList[2]. Iterating is done with a FOR loop, just like with arrays.

在伪代码中，列表常以 myList.add(item) 或 myList[2] 这样的命令出现。遍历使用 FOR 循环完成，与数组类似。

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

A stack is an abstract data structure that follows the Last In, First Out (LIFO) principle. Imagine a stack of plates: you can only add a new plate to the top, and you can only take the top plate off. The two fundamental operations are push (add an item to the top) and pop (remove the top item).

堆栈是一种遵循后进先出（LIFO）原则的抽象数据结构。想象一叠盘子：你只能把新盘子放在最上面，也只能从最上面取走盘子。两个基本操作是 push（将项目添加到顶部）和 pop（移除顶部项目）。

Stacks are used in real programs for backtracking (e.g., undo feature in a word processor), managing function calls (call stack), and reversing data (like reversing a string). You must know how to show the state of a stack after a series of push and pop operations, and identify errors like underflow (popping from an empty stack) and overflow (pushing to a full stack).

堆栈在真实程序中被用于回溯（例如文字处理软件中的撤销功能）、管理函数调用（调用栈）以及反转数据（如反转字符串）。你必须能够展示一系列 push 和 pop 操作后堆栈的状态，并识别错误，例如下溢（从空栈中 pop）和上溢（向满栈中 push）。

Top item = stack.peek() (without removing it)

A stack can be implemented using an array and a pointer (top of stack). When a pop occurs, the pointer is decreased; no data actually needs to be erased, but it is overwritten when a new push happens.

堆栈可以用数组和指针（栈顶指针）来实现。当执行 pop 时，指针减小；实际上不需要擦除数据，但会在新的 push 发生时覆盖。

8. Queues (FIFO) | 队列（先进先出）

A queue is an abstract data structure that operates on a First In, First Out (FIFO) basis. Just like a queue of people at a bus stop, the first person to join the queue is the first one to be served. The two main operations are enqueue (add an item to the rear) and dequeue (remove an item from the front).

队列是一种基于先进先出（FIFO）原则运行的抽象数据结构。就像公交车站排队的人群一样，最早加入队列的人最早得到服务。两个主要操作是 enqueue（将一个项目添加到队尾）和 dequeue（将项目从队头移除）。

Queues are used in operating system job scheduling, printer spooling, and keyboard buffers. Exam questions often ask you to trace a sequence of enqueue and dequeue operations on a circular queue. A circular queue reuses empty spaces at the front of the array to avoid wasted memory.

队列被用于操作系统作业调度、打印机后台处理和键盘缓冲区。试题通常会要求你追踪循环队列上一系列 enqueue 和 dequeue 操作。循环队列可以重用数组前端的空余空间，以避免内存浪费。

When implementing a queue, you need two pointers: front and rear. After a dequeue, the front pointer moves forward. In a circular queue, you wrap around using modulo arithmetic: rear ← (rear + 1) MOD size.

实现队列时，你需要两个指针：front 和 rear。dequeue 后，front 指针向前移动。在循环队列中，使用模运算实现环绕：rear ← (rear + 1) MOD size。

9. Comparing Stacks and Queues | 堆栈与队列的比较

Property	Stack	Queue
Order	LIFO	FIFO
Insert	push (top)	enqueue (rear)
Remove	pop (top)	dequeue (front)
Pointers	1 (top)	2 (front, rear)
Use cases	Undo, backtracking, call stack	Print queue, scheduling, buffers

Both stacks and queues are commonly tested with trace table questions. You must be able to update pointers and array contents accurately. Remember: in a stack, pushing increments the top pointer, popping decrements it. In a linear queue, enqueue increments rear, dequeue increments front.

堆栈和队列都常以追踪表的形式考查。你必须能够准确地更新指针和数组内容。请记住：在堆栈中，push 会使 top 指针加1，pop 则使其减1。在顺序队列中，enqueue 使 rear 加1，dequeue 使 front 加1。

10. Choosing the Right Data Structure | 选择正确的数据结构

Exam questions frequently ask you to justify why a particular data structure is suitable for a given problem. Here is a summary to guide your reasoning:

试题经常要求你论证为什么特定的数据结构适用于给定的问题。以下是一份总结，帮助你进行推理：

Array (1D/2D): Use when you need fast index-based access to a fixed-size collection of identical data types, such as storing daily temperatures for a month or a grid in a game.
数组（一维/二维）： 当你需要对固定大小的同类型数据集进行基于索引的快速访问时使用，例如存储一个月的每日温度或游戏中的网格。
Record: Use to group mixed-type data that belong to a single entity, like a customer’s name, ID, and balance.
记录： 用于对属于单个实体的混合类型数据进行分组，例如客户的姓名、编号和余额。
List: Use when the number of items is unknown or changes dynamically, and you still need ordered, indexed access.
列表： 当项目数量未知或动态变化，并且你仍然需要有序、带索引的访问时使用。
Stack: Use for LIFO behaviour, especially where you need to reverse order or manage nested operations (like evaluating expressions or parsing parentheses).
堆栈： 用于需要 LIFO 行为的场景，特别是需要反转顺序或管理嵌套操作（如计算表达式或解析括号）时。
Queue: Use for FIFO behaviour, especially to preserve the order of arrival, like processing print jobs or customer service requests.
队列： 用于需要 FIFO 行为的场景，特别是需要保持到达顺序时，如处理打印作业或客服请求。

11. Common Exam Pitfalls | 常见考试陷阱

1. Confusing static and dynamic structures: saying an array can grow is incorrect in OCR contexts unless you specify a list.

1. 混淆静态和动态结构：在 OCR 上下文中，说数组可以增长是不正确的，除非你明确说明是列表。

2. Forgetting to check for overflow or underflow: always mention these conditions when describing stack and queue operations.

2. 忘记检查上溢或下溢：在描述堆栈和队列操作时，始终要提到这些条件。

3. Index out of bounds: in pseudocode, trying to access array[5] when indices are 0..4 will cause an error. Carefully consider that an array of size 5 has indices 0, 1, 2, 3, 4.

3. 索引越界：在伪代码中，当索引范围是 0..4 时尝试访问 array[5] 会导致错误。请仔细考虑：大小为5的数组的合法索引为 0, 1, 2, 3, 4。

4. Pointer mismanagement in queues: forgetting to wrap around (circular) or incrementing both front and rear during enqueue.

4. 队列中的指针管理错误：忘记环绕（循环队列）或在 enqueue 时同时增加 front 和 rear。

5. Record vs array: writing that a record can only hold one data type — records can hold mixed types; arrays (by definition) hold the same type.

5. 记录与数组混淆：认为记录只能保存一种数据类型——记录可以保存混合类型；数组（根据定义）保存相同类型。

12. Summary and Key Takeaways | 总结与关键要点

Mastering data structures in IGCSE OCR Computer Science means you can confidently read, write, and trace pseudocode for arrays, records, lists, stacks, and queues. Always match the structure to the problem’s needs and be precise with pointer updates and boundary checks. With consistent practice, these concepts become second nature.

掌握 IGCSE OCR 计算机科学中的数据结构意味着你能够自信地阅读、编写和追踪数组、记录、列表、堆栈和队列的伪代码。始终将数据结构与问题的需求相匹配，并精确地进行指针更新和边界检查。通过持续练习，这些概念将成为你的第二天性。

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

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

Data Structures for IGCSE OCR Computer Science | IGCSE OCR 计算机：数据结构 考点精讲