📚 IGCSE CCEA Computer Science: Data Structures Exam Focus | IGCSE CCEA 计算机：数据结构 考点精讲
Data structures are the building blocks of efficient programs. In CCEA IGCSE Computer Science, you need to understand how to organise, access and manipulate data using arrays, linked lists, stacks, queues, trees and hash tables. This guide breaks down every key concept, common pitfalls and exam-style reasoning to help you score top marks.
数据结构是高效程序的基础构建模块。在 CCEA IGCSE 计算机科学中，你需要理解如何使用数组、链表、栈、队列、树以及哈希表来组织、访问和操作数据。本指南将逐一拆解每个关键概念、常见误区以及考试题型中的推理方式，帮助你取得高分。
1. Data Structures Overview | 数据结构概述
A data structure is a specialised format for organising, storing and retrieving data. The choice of structure affects memory usage, speed of access and ease of modification. Static structures like arrays have a fixed size, while dynamic structures like linked lists can grow or shrink during execution.
数据结构是用于组织、存储和检索数据的专用格式。结构的选择会影响内存使用、访问速度和修改的便利性。静态结构如数组具有固定大小，而动态结构如链表可在运行时增长或缩小。
In CCEA exams, you are often asked to compare data structures in terms of efficiency and appropriate use cases. Remember that no single structure is always best—context matters.
在 CCEA 考试中，常常要求从效率和适用场景的角度比较数据结构。请记住，没有哪种结构永远是最好的——具体情境最重要。
2. Arrays (1D and 2D) | 数组（一维和二维）
An array is a collection of elements, all of the same data type, stored in contiguous memory locations. A one‑dimensional (1D) array is like a simple list; each element is accessed by its index, typically starting from 0. For example, arr[2] retrieves the third element.
数组是相同数据类型元素的集合，存储在连续的内存位置中。一维数组就像一个简单的列表；每个元素通过其索引访问，通常从0开始。例如，arr[2] 获取第三个元素。
A two‑dimensional (2D) array can be thought of as a table or matrix, with rows and columns. It is declared with two indices, e.g. grid[row, col]. This is ideal for representing board games, spreadsheets or pixel grids.
二维数组可以看作是一个表格或矩阵，拥有行和列。它用两个索引声明，例如 grid[row, col]。这非常适合表示棋盘游戏、电子表格或像素网格。
Key properties:
- Direct access in O(1) time.
- Fixed size; resizing requires creating a new array and copying data.
主要特性：
- O(1) 时间复杂度的直接访问。
- 固定大小；调整大小需要创建新数组并复制数据。
Exam tip: when describing array operations, always mention that indexing starts at zero and that an out‑of‑bounds index causes an error.
考试提示：在描述数组操作时，务必提及索引从0开始，超出边界的索引会导致错误。
3. Records (Structures) | 记录（结构体）
A record is a data structure that groups related items of possibly different data types together. Each item is called a field. For example, a student record might contain fields: name (string), age (integer) and grade (char).
记录是一种将可能不同数据类型的相关项目组合在一起的数据结构。每个项目称为一个字段。例如，一个学生记录可能包含以下字段：姓名（字符串）、年龄（整数）和成绩（字符）。
In pseudocode, you might see a record defined as:
TYPE Student
DECLARE name : STRING
DECLARE age : INTEGER
DECLARE grade : CHAR
ENDTYPE
在伪代码中，你可能会看到这样定义记录：
TYPE Student
DECLARE name : STRING
DECLARE age : INTEGER
DECLARE grade : CHAR
ENDTYPE
Records are the foundation of databases and object‑oriented programming. In CCEA papers, you may need to read from or write to a record’s fields using dot notation, like Student.name.
记录是数据库和面向对象编程的基础。在 CCEA 试卷中，你可能需要使用点符号（如 Student.name）读取或写入记录的字段。
4. Lists and Linked Lists | 列表与链表
A list in many high‑level languages is a dynamic, indexed collection. However, in data structure theory, a linked list is a chain of nodes, where each node contains data and a pointer to the next node. The start of the list is marked by a head pointer.
许多高级语言中的列表是一种动态的、带索引的集合。然而，在数据结构理论中，链表是一个节点的链条，每个节点包含数据和指向下一个节点的指针。链表的开头由一个头指针标记。
Linked lists allow efficient insertion and deletion (O(1) if we have a pointer to the location), but searching requires O(n) time because access is sequential. A doubly linked list also holds a pointer to the previous node, enabling backward traversal.
链表允许高效的插入和删除（如果有指向该位置的指针，则为 O(1)），但搜索需要 O(n) 时间，因为访问是顺序的。双向链表还包含指向前一个节点的指针，允许向后遍历。
Common exam comparisons:
| Array | Linked List |
|---|---|
| Fast indexed access | Slower sequential access |
| Fixed size | Dynamic size |
| Memory wasted if not full | Extra memory for pointers |
常见考试对比：
| 数组 | 链表 |
|---|---|
| 快速的索引访问 | 较慢的顺序访问 |
| 固定大小 | 动态大小 |
| 未满时浪费内存 | 指针占用额外内存 |
5. Stacks (LIFO) | 栈（后进先出）
A stack is an abstract data type that follows Last‑In‑First‑Out (LIFO) order. The two main operations are push (add an item) and pop (remove the top item). A pointer usually indicates the top of the stack.
栈是一种遵循后进先出（LIFO）顺序的抽象数据类型。主要操作有两个：push（添加一个项目）和 pop（移除顶部项目）。通常有一个指针指示栈顶。
Stacks can be implemented using arrays (with a top pointer) or linked lists. Common applications include:
- Undo functionality in software
- Backtracking algorithms (e.g. maze solving)
- Call stack in program execution
栈可以用数组（带一个顶指针）或链表实现。常见应用包括：
- 软件中的撤销功能
- 回溯算法（例如迷宫求解）
- 程序执行中的调用栈
When answering exam questions, if you are asked to trace a stack, carefully track the top pointer. Overflow occurs when pushing to a full stack, underflow when popping from an empty one.
回答考试问题时，如果要求跟踪栈，请仔细记录顶指针。向已满的栈推送时发生溢出，从空栈弹出时发生下溢。
6. Queues (FIFO) | 队列（先进先出）
A queue is a First‑In‑First‑Out (FIFO) structure. Items are added at the rear (enqueue) and removed from the front (dequeue). Queues model real‑world waiting lines, print spooling and breadth‑first search.
队列是一种先进先出（FIFO）的结构。项目在尾部添加（入队），从头部移除（出队）。队列模拟了现实世界中的排队、打印缓冲和广度优先搜索。
A linear queue can suffer from the ‘drifting’ problem—as items are dequeued, front moves forward, wasting space at the beginning. A circular queue solves this by wrapping indices around, reusing freed slots. A priority queue orders elements based on a priority value, not just arrival time.
线性队列可能面临’漂移’问题——随着项目出队，前端向前移动，导致开头的空间浪费。循环队列通过回绕索引来解决此问题，重用释放的槽位。优先级队列不仅根据到达时间，还根据优先级值对元素进行排序。
State how you would check if a circular queue is empty (front == rear) or full ((rear + 1) % size == front). These conditions are classic CCEA pseudocode tasks.
说明如何检查循环队列是否为空（front == rear）或已满（(rear + 1) % size == front）。这些条件是经典的 CCEA 伪代码任务。
7. Trees and Binary Trees | 树与二叉树
A tree is a hierarchical data structure consisting of nodes connected by edges. The topmost node is the root. A binary tree restricts each node to at most two children: left and right. In a binary search tree (BST), the left subtree contains values less than the parent, and the right subtree contains values greater.
树是一种由边连接的节点组成的层次化数据结构。最顶层的节点是根。二叉树限制每个节点最多有两个子节点：左子节点和右子节点。在二叉搜索树 (BST) 中，左子树包含的值小于父节点，右子树包含的值大于父节点。
Tree traversal methods are essential for exams:
- Pre‑order: root, left, right
- In‑order: left, root, right (produces sorted output for BST)
- Post‑order: left, right, root
树的遍历方法是考试重点：
- 前序遍历：根，左，右
- 中序遍历：左，根，右（对 BST 产生有序输出）
- 后序遍历：左，右，根
You may be asked to draw a tree from given data or to list the nodes in a specific traversal order. Always work methodically and label your steps.
你可能会被要求根据给定数据画出树，或按特定遍历顺序列出节点。始终有条不紊地进行，并标记你的步骤。
8. Hash Tables (Dictionaries) | 哈希表（字典）
A hash table stores key‑value pairs and provides extremely fast lookup by using a hash function to compute an index. Collisions occur when two keys produce the same index. Two collision resolution methods are:
- Open addressing (linear probing): find the next free slot
- Chaining: maintain a linked list at each index
哈希表存储键值对，并通过使用哈希函数计算索引来提供极快的查找。当两个键产生相同的索引时，发生冲突。两种冲突解决方法：
- 开放寻址（线性探测）：查找下一个空闲槽位
- 链地址法：在每个索引处维护一个链表
A good hash function distributes keys evenly. In CCEA, you might be given a simple hash function (e.g., key MOD tableSize) and asked to trace insertions with linear probing. Remember to show the state of the table after each operation.
一个好的哈希函数会均匀地分布键。在 CCEA 中，你可能会得到一个简单的哈希函数（例如，key MOD tableSize），并要求跟踪使用线性探测的插入过程。请记得在每一步操作后显示表格的状态。
Advantages: average O(1) search time. Disadvantages: inefficient for ordered data, extra memory overhead, performance degrades with high load factor.
优点：平均 O(1) 搜索时间。缺点：对有序数据效率低，额外内存开销，高负载因子时性能下降。
9. Choosing the Right Data Structure | 选择合适的数据结构
Exam questions often ask you to justify a choice. Consider these factors:
- Type and volume of data
- Frequency of insertions/deletions
- Need for ordered access vs random access
- Memory constraints
- Whether the structure is static or dynamic
考试题目常常要求你证明选择的合理性。考虑以下因素：
- 数据的类型和数量
- 插入/删除的频率
- 需要顺序访问还是随机访问
- 内存限制
- 结构是静态还是动态
For example, a phone book app requiring fast alphabetical listing could use a sorted array or a BST; a printer buffer suits a queue; browser history fits a stack.
例如，需要按字母顺序快速列出的电话簿应用程序可以使用有序数组或 BST；打印缓冲区适合队列；浏览器历史记录适合栈。
10. Exam-Style Questions and Tips | 考试题型与技巧
CCEA papers frequently include algorithm tracing, data structure selection with reasoning, and pseudocode for operations like push/pop or inserting into a BST. Always annotate your trace tables clearly.
CCEA 试卷经常出算法跟踪、数据结构选择并说明理由，以及 push/pop 或插入 BST 等操作的伪代码。始终清晰地注释你的跟踪表。
Common mistakes:
- Forgetting to update pointers in a linked list insertion
- Confusing in‑order with pre‑order or post‑order traversal
- Not checking for overflow/underflow in stack operations
- Using array indices incorrectly (off‑by‑one errors)
常见错误：
- 链表中插入时忘记更新指针
- 混淆中序、前序和后序遍历
- 栈操作中未检查溢出/下溢
- 数组索引使用不当（差一错误）
Practice by writing out the state of a data structure after each step of an algorithm. When comparing structures, use concise technical language and refer to time complexity where relevant.
通过写出算法每一步之后数据结构的状态来练习。在比较结构时，使用简洁的专业语言，并在相关处提及时间复杂度。
11. Revision Summary Table | 复习总结表
| Data Structure | Key Feature | Typical Use |
|---|---|---|
| Array | Fixed size, direct access | Exam scores, pixel data |
| Record | Mixed data types | Database rows |
| Linked List | Dynamic, sequential access | Insert‑heavy applications |
| Stack | LIFO | Undo, function calls |
| Queue | FIFO | Print queue, BFS |
| Binary Tree | Hierarchical, sorted (BST) | File systems, dictionaries |
| Hash Table | Key‑value, fast lookup | Caches, indexing |
复习总结表（中文）：
| 数据结构 | 关键特征 | 典型用途 |
|---|---|---|
| 数组 | 固定大小，直接访问 | 考试成绩，像素数据 |
| 记录 | 混合数据类型 | 数据库行 |
| 链表 | 动态，顺序访问 | 插入密集型应用 |
| 栈 | LIFO | 撤销，函数调用 |
| 队列 | FIFO | 打印队列，广度优先搜索 |
| 二叉树 | 层次化，有序 (BST) | 文件系统，字典 |
| 哈希表 | 键值对，快速查找 | 缓存，索引 |
12. Final Exam Advice | 备考建议
When revising, draw diagrams: stacks with pointers, linked lists with nodes, BSTs with values. This visual approach helps you trace algorithms accurately. Practice past paper questions under timed conditions and always double‑check boundary conditions—these are a favourite source of marks in CCEA computer science exams.
复习时，画出示意图：带指针的栈、带节点的链表、带值的二叉搜索树。这种视觉化方法有助于你准确跟踪算法。在计时条件下练习历年真题，并始终仔细检查边界条件——这是 CCEA 计算机科学考试中常见的得分点。
Remember that data structure choices are not just about speed—explain trade‑offs regarding memory and ease of coding to show deeper understanding.
请记住，数据结构的选择不仅仅关乎速度——解释有关内存和编码便利性的权衡，以展示更深入的理解。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导