GCSE CIE Computer Science: Data Structures Revision | GCSE CIE 计算机：数据结构考点精讲

📚 GCSE CIE Computer Science: Data Structures Revision | GCSE CIE 计算机：数据结构考点精讲

Data structures are the organised ways in which data is stored, accessed, and manipulated inside a computer program. For the CIE IGCSE Computer Science examination, you need to understand arrays, records, files, stacks, queues, linked lists, and binary trees, as well as how basic searching and sorting algorithms operate on these structures. This revision guide covers all essential points with clear explanations, diagrams in words, and practical coding-style examples.

数据结构是在计算机程序内部组织、存储、访问和操作数据的方式。在 CIE IGCSE 计算机科学考试中，你需要掌握数组、记录、文件、栈、队列、链表和二叉树等基本结构，还要理解在这些结构上运行的搜索和排序算法。本考点精讲以清晰的解释、文字图表和代码风格示例，覆盖所有核心要点。

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

A data structure is a collection of data values, the relationships among them, and the operations that can be applied to the data. Choosing the right data structure can make a program more efficient and easier to understand. In the exam, you must be able to identify which structure is appropriate for a given scenario.

数据结构是数据值的集合、它们之间的关系以及可应用于这些数据的操作。选择正确的数据结构可以使程序更高效、更易于理解。在考试中，你必须能够判断出哪种结构最适合给定的场景。

Static data structures have a fixed size that cannot change during program execution (e.g. arrays in many languages). Dynamic data structures can grow and shrink as needed (e.g. linked lists, stacks, queues). Understanding this distinction helps when answering questions about memory usage and flexibility.

静态数据结构的大小是固定的，在程序执行期间不能改变（例如许多语言中的数组）。动态数据结构可以根据需要增长和收缩（例如链表、栈、队列）。理解这种区别有助于回答有关内存使用和灵活性方面的问题。

2. Arrays | 数组

An array is a finite, ordered collection of elements of the same data type. Each element can be accessed directly using an index, usually starting at 0. For example, examScores[0] might store 85, examScores[1] 92, and so on. Arrays are static structures in most exam contexts, meaning their size is set when declared.

数组是同类型元素的有穷、有序集合。每个元素可以通过索引直接访问，索引通常从 0 开始。例如，examScores[0] 可能存储 85，examScores[1] 存储 92，依此类推。在多数考试语境中，数组是静态结构，其大小在声明时确定。

Direct access via index: O(1) time complexity to read or write an element.
通过索引直接访问：读取或写入一个元素的时间复杂度为 O(1)。
Arrays are ideal when you know the number of items in advance and need fast random access.
当提前知道项目数量并需要快速随机访问时，数组非常理想。

A two‑dimensional (2D) array can be visualised as a table with rows and columns. For instance, grid[2][3] refers to the element in row 2, column 3. Traversing a 2D array usually requires nested loops.

二维数组可以想象成一个有行和列的表格。例如，grid[2][3] 指的是第 2 行第 3 列的元素。遍历二维数组通常需要嵌套循环。

3. Records | 记录

A record is a data structure that groups together variables of different data types under one name. Each variable is called a field. For example, a student record might contain fields: studentID : Integer, name : String, dateOfBirth : Date. Records are the building blocks of databases and file structures.

记录是一种将不同数据类型的变量组合在一起并赋予一个名称的数据结构。每个变量称为一个字段。例如，一个学生记录可能包含字段：studentID : Integer、name : String、dateOfBirth : Date。记录是数据库和文件结构的基本构件。

In pseudocode, you often see records defined using a TYPE ... ENDTYPE statement. To access a field, you use dot notation, e.g., newStudent.name. The exam may ask you to declare a record type, create an array of records, or write code to read and write fields.

在伪代码中，你常会看到用 TYPE ... ENDTYPE 语句定义记录。要访问一个字段，使用点符号，例如 newStudent.name。考试可能会要求你声明一种记录类型、创建一个记录数组，或者编写读写字段的代码。

4. Files | 文件

A file is a block of data stored on a secondary storage device. From a programming perspective, a file is a sequential or direct-access data structure that must be opened, read from or written to, and then closed. CIE candidates should know the basic file operations: open, read, write, close, and how to test for end-of-file (EOF).

文件是存储在辅助存储设备上的一块数据。从编程的角度看，文件是一种顺序或直接访问的数据结构，必须先打开，然后读取或写入，最后关闭。CIE 考生应了解基本的文件操作：打开、读取、写入、关闭，以及如何检测文件结束（EOF）。

Text files store data as human-readable characters, while binary files store data in the same format as it appears in memory. You may be asked to write pseudocode that processes a text file line by line, counting items or searching for a specific value.

文本文件以人类可读的字符形式存储数据，而二进制文件以数据在内存中的格式存储。你可能会被要求编写伪代码，逐行处理文本文件，计算项目数量或搜索特定值。

5. Stacks | 栈

A stack is a Last-In-First-Out (LIFO) data structure. Items can be added (pushed) onto the top and removed (popped) from the top. You can also peek at the top item without removing it. Stacks are used for managing subroutine calls, undo operations in software, and evaluating expressions.

栈是一种后进先出（LIFO）的数据结构。元素可以添加（压入）到栈顶，并从栈顶移除（弹出）。你还可以查看栈顶元素而不移除它。栈用于管理子程序调用、软件中的撤销操作以及求值表达式。

push(item) – adds an item to the top. If the stack is full, a stack overflow occurs.
push(元素) – 向栈顶添加一个元素。如果栈已满，会发生栈溢出。
pop() – removes and returns the top item. If the stack is empty, a stack underflow occurs.
pop() – 移除并返回栈顶元素。如果栈为空，会发生栈下溢。
peek() – returns the top item without removing it.
peek() – 返回栈顶元素但不移除它。

In the exam, you may need to trace a sequence of push and pop operations or write code using an array to implement a stack. A stack pointer is used to keep track of the index of the top element.

考试中，你可能需要追踪一系列压入和弹出操作，或者用数组实现栈的代码。栈指针用于记录栈顶元素的索引。

6. Queues | 队列

A queue is a First-In-First-Out (FIFO) data structure. Items join at the rear and leave from the front. Queues are used in print spooling, keyboard buffers, and simulation systems. There are two main types: linear queues and circular queues.

队列是一种先进先出（FIFO）的数据结构。元素在队尾加入，从队首离开。队列用于打印假脱机、键盘缓冲区和模拟系统。主要有两种类型：线性队列和循环队列。

enqueue(item) – adds an item to the rear.
enqueue(元素) – 向队尾添加一个元素。
dequeue() – removes and returns the item at the front.
dequeue() – 移除并返回队首元素。
isFull() / isEmpty() – used to avoid overflow or underflow.
isFull() / isEmpty() – 用于避免溢出或下溢。

A circular queue re-uses empty spaces by wrapping around; it uses two pointers, front and rear, and increments them modulo the array size. This overcomes the problem of unused spaces in a linear queue after several dequeue operations.

循环队列通过绕回的方式重复使用空闲空间；它使用两个指针，前指针和后指针，以数组大小为模进行递增。这克服了线性队列在多次出队操作后出现未用空间的问题。

7. Linked Lists | 链表

A linked list is a dynamic data structure in which each element (node) contains data and a pointer to the next node. The start of the list is maintained by an external pointer. The last node points to null. Linked lists can grow and shrink easily, and insertion/deletion does not require shifting elements.

链表是一种动态数据结构，其中每个元素（节点）包含数据和一个指向下一个节点的指针。链表的起始由一个外部指针维护。最后一个节点指向空。链表可以轻松增长和收缩，插入和删除不需要移动元素。

Efficient insertion/deletion at any position: O(1) when the node is already found.
在任意位置高效插入/删除：当已经找到节点时，时间复杂度为 O(1)。
No direct indexing – to locate an item, you must traverse from the head, O(n) in the worst case.
不支持直接索引 – 要定位一个项目，必须从头遍历，最坏情况下为 O(n)。

A doubly linked list has nodes with two pointers: one to the next node and one to the previous node. This allows traversal in both directions. The exam may ask you to draw a linked list after a series of insertions or deletions, or to compare linked lists with arrays.

双向链表的节点有两个指针：一个指向下一个节点，一个指向前一个节点。这允许双向遍历。考试可能会要求你画出进行一系列插入或删除后的链表，或者比较链表与数组。

8. Binary Trees | 二叉树

A binary tree is a hierarchical structure in which each node has at most two children, referred to as the left child and the right child. The topmost node is the root. A binary search tree (BST) has the property that for every node, all values in the left subtree are less than the node’s value, and all in the right subtree are greater. This enables efficient searching.

二叉树是一种分层结构，其中每个节点最多有两个子节点，称为左子节点和右子节点。最顶层的节点是根。二叉搜索树（BST）具有以下性质：对于每个节点，其左子树中的所有值都小于该节点的值，其右子树中的所有值都大于该节点的值。这也使得搜索变得高效。

Inserting in a BST: compare the new value to the root, go left if smaller, right if larger, repeat until an empty slot is found.
在 BST 中插入：将新值与根比较，较小则向左，较大则向右，重复直到找到一个空位。
Traversal methods: pre-order (root, left, right), in-order (left, root, right), post-order (left, right, root). In-order traversal of a BST visits nodes in ascending order.
遍历方法：前序（根、左、右），中序（左、根、右），后序（左、右、根）。中序遍历 BST 会按升序访问节点。

Binary trees are used in expression parsing, decision-making processes, and file systems. You may be required to construct a BST from a list of values or to write pseudocode for tree traversal.

二叉树用于表达式解析、决策过程和文件系统。你可能需要根据一系列值构建 BST，或者编写树遍历的伪代码。

9. Searching Algorithms | 搜索算法

Data structures often need to support searching for a specific element. The two main search methods in the CIE syllabus are linear search and binary search. Linear search works on any list (sorted or unsorted) and checks each element in turn. It is simple but O(n) in the worst case.

数据结构通常需要支持查找特定元素。CIE 大纲中两种主要的搜索方法是线性搜索和二分搜索。线性搜索适用于任何列表（已排序或未排序），逐次检查每个元素。它很简单，但最坏情况为 O(n)。

Binary search is much faster on a sorted array. It repeatedly divides the search interval in half. The middle element is compared with the target. If not equal, the search continues in the left or right half. Time complexity is O(log n). Pseudocode commonly uses low, high, and mid indices:

mid ← (low + high) DIV 2

二分搜索在已排序的数组上快得多。它反复将搜索区间一分为二。将中间元素与目标比较。如果不相等，则在左半部分或右半部分继续搜索。时间复杂度为 O(log n)。伪代码通常使用 low、high 和 mid 索引：

mid ← (low + high) DIV 2

You must be able to trace both algorithms on a given dataset and identify the maximum number of comparisons required for binary search.

你必须能够对给定的数据集追踪这两种算法，并确定二分搜索所需的最大比较次数。

10. Sorting Algorithms | 排序算法

While not purely data structures, sorting algorithms are closely linked to arrays and lists. CIE candidates should know bubble sort, insertion sort, and sometimes selection sort. Bubble sort repeatedly steps through the list, compares adjacent items, and swaps them if they are in the wrong order. After each pass, the largest unsorted element “bubbles up” to its correct position.

虽然排序算法不完全是数据结构，但它们与数组和列表密切相关。CIE 考生需要了解冒泡排序、插入排序，有时还有选择排序。冒泡排序反复遍历列表，比较相邻项，如果顺序错误则交换。每一轮之后，最大的未排序元素会“冒泡”到正确的位置。

Bubble sort worst-case time complexity: O(n²). It is simple but inefficient on large lists.
冒泡排序最坏情况时间复杂度：O(n²)。它简单但在大列表上效率低下。
Insertion sort builds the sorted list one element at a time by taking each new element and inserting it into its correct position among the previously sorted items. It is O(n²) as well but works well with small or partially sorted data.
插入排序通过每次取出一个新元素并将其插入到已排序部分的正确位置，逐步构建有序列表。同样为 O(n²)，但在数据量小或部分有序时效果不错。
Selection sort repeatedly finds the minimum element from the unsorted part and puts it at the beginning. It has O(n²) time complexity but performs fewer swaps than bubble sort.
选择排序反复从未排序部分找到最小元素，将其放到已排序部分的末尾。时间复杂度为 O(n²)，但交换次数少于冒泡排序。

In exams you might be asked to show the state of an array after each pass of a given sort, or to discuss the efficiency of different sorting methods.

考试中可能会要求你展示给定排序每一轮后数组的状态，或者讨论不同排序方法的效率。

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

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

GCSE CIE Computer Science: Data Structures Revision | GCSE CIE 计算机：数据结构 考点精讲