A-Level Computer Science: Core Points of Data Types and Data Structures | A-Level计算机：数据类型与数据结构核心考点

📚 A-Level Computer Science: Core Points of Data Types and Data Structures | A-Level计算机：数据类型与数据结构核心考点

In the CIE A-Level Computer Science syllabus, a thorough understanding of data types and data structures is essential for success in Paper 2 and Paper 4. This article consolidates the core knowledge points, including primitive data types, composite data structures, abstract data types (ADTs), and typical examination techniques.

在 CIE A-Level 计算机科学考纲中，数据类型与数据结构是 Paper 2 和 Paper 4 的核心考查内容。本文系统归纳了基本数据类型、复合数据结构、抽象数据类型（ADT）以及典型考点，帮助考生高效复习、精准答题。

1. Primitive Data Types | 基本数据类型

Primitive data types are the most fundamental building blocks of a program, directly supported by the hardware or the programming language. In A-Level Computer Science, candidates must know integer, real, char, Boolean, and string.

基本数据类型是程序中最基础的构造单元，由硬件或编程语言直接支持。在 A-Level 计算机课程中，考生必须掌握整数、实数、字符、布尔和字符串。

Integer: A whole number that can be positive, negative, or zero. In Python, integers can be of arbitrary precision, while Java and C have fixed-size integers (e.g., int is usually 32-bit).

整数：可以是正数、负数或零的整数。Python 中整数精度不受限，而 Java 和 C 中的整数有固定长度（如 int 通常为 32 位）。
Real / Float: A number with a fractional component, often stored using IEEE 754 standard. Real numbers cannot represent all values exactly due to finite mantissa bits.

实数 / 浮点数：带小数部分的数，常用 IEEE 754 标准存储。由于尾数位数有限，实数无法精确表示所有数值。
Char: A single character enclosed in single quotes, e.g., ‘A’, ‘9’, ‘\n’. It is stored as a code in a character set such as ASCII or Unicode.

字符：用单引号括起来的单个字符，如 ‘A’、’9’、’\n’。字符以 ASCII 或 Unicode 字符集中的编码形式存储。
Boolean: A logical type that can only be TRUE or FALSE, often used in conditions and loops.

布尔：逻辑类型，只能为 TRUE 或 FALSE，常用于条件判断和循环。布尔运算包括 AND、OR、NOT。
String: A sequence of zero or more characters. In some languages, string is a primitive type; in others, it is a class. In this course, strings are usually treated as an ADT with operations such as length, concatenation, substring, and comparison.

字符串：零个或多个字符组成的序列。在某些语言中是基本类型，在其他语言中是类。在本课程中，字符串通常作为抽象数据类型，支持长度、拼接、子串和比较等操作。

2. Type Conversion and Casting | 类型转换与强制类型转换

Type conversion is the process of converting a value from one data type to another. It can be automatic (implicit) or explicit (casting). CIE examinations often test the outcomes of conversions, especially with division and rounding.

类型转换是将一个值从一种数据类型转换为另一种数据类型的过程。转换可以是自动的（隐式），也可以是显式的（强制类型转换）。CIE 考试常考查转换结果，尤其是除法与取整。

Implicit: int → float → complex (in Python)
显式：int(x)、float(x)、str(x)、chr(x)、ord(x)

For example, in Python, 7 / 2 returns 3.5 (float), while 7 // 2 returns 3 (integer division). In Java, 7 / 2 returns 3 because both are integers; to obtain a floating-point result, one operand must be cast to double.

例如，在 Python 中，7 / 2 返回 3.5（浮点数），而 7 // 2 返回 3（整除）。在 Java 中，7 / 2 返回 3，因为两个操作数均为整数；若要得到浮点数结果，需要将其中一个操作数显式转换为 double。

int(‘101’, 2) converts a binary string to integer 5.

int(‘101’, 2) 将二进制字符串转换为整数 5。
round(3.7) gives 4; int(3.7) truncates to 3 (towards zero).

round(3.7) 等于 4；int(3.7) 直接舍去小数部分得到 3（向零取整）。

3. Binary, Hexadecimal and Two’s Complement | 二进制、十六进制与补码

Candidates must be able to convert between binary, denary, and hexadecimal, and understand how negative integers are stored using two’s complement.

考生必须能够在二进制、十进制和十六进制之间相互转换，并理解负整数如何用二进制补码存储。

One hex digit = 4 binary bits
1 个十六进制位 = 4 个二进制位

Denary 45 → Binary 00101101 → Hex 0x2D

十进制 45 → 二进制 00101101 → 十六进制 0x2D
To find the two’s complement of −5 in 8 bits: start with 00000101, invert → 11111010, add 1 → 11111011.

求 8 位二进制补码表示 −5：先写出 00000101，取反得 11111010，再加 1 得 11111011。
The most significant bit (MSB) is the sign bit: 0 for positive, 1 for negative.

最高有效位（MSB）是符号位：0 表示正数，1 表示负数。

4. Floating-Point Representation | 浮点数表示

Floating-point numbers in A-Level CIE are represented using mantissa and exponent, in binary. The general form is:

A-Level CIE 中，浮点数使用尾数（mantissa）和指数（exponent）以二进制形式表示，一般形式为：

value = mantissa × 2^exponent
数值 = 尾数 × 2^指数

For example, in a system with 8-bit mantissa and 4-bit exponent, the binary string 0.1011000 0011 represents 0.1011₂ × 2³ = 101.1₂ = 5.5₁₀.

例如，在一个 8 位尾数、4 位指数的系统中，二进制串 0.1011000 0011 表示 0.1011₂ × 2³ = 101.1₂ = 5.5₁₀。

Normalisation: To maximise precision, the mantissa should start with 0.1 for positive numbers or 1.0 for negative numbers.

规格化：为最大化精度，正数尾数应以 0.1 开头，负数尾数应以 1.0 开头。
Overflow and underflow: using too many bits or too few bits for the exponent can cause overflow or loss of precision.

上溢与下溢：指数位数过多或过少都会导致溢出或精度损失。

5. Arrays | 数组

An array is a composite data structure that stores multiple elements of the same data type under one name, accessible by index. Arrays have a fixed size after creation in most languages.

数组是一种复合数据结构，在同一个名称下存储多个相同数据类型的元素，通过下标访问。在大多数语言中，创建后数组大小固定。

Operations on one-dimensional arrays include initialisation, input, output, searching (linear search, binary search), and sorting (bubble sort, insertion sort). For two-dimensional arrays such as matrices, index (i, j) refers to row i and column j.

一维数组的操作包括初始化、输入、输出、查找（线性查找、二分查找）和排序（冒泡排序、插入排序）。对于二维数组（如矩阵），下标 (i, j) 表示第 i 行第 j 列。

Language / 语言	Declaration / 声明	Access / 访问
Python	num = [0] * 10	num[3]
Java	int[] num = new int[10];	num[3]

6. Records and Tuples | 记录与元组

A record is a data structure that stores multiple fields of possibly different data types as a single logical unit. In SQL, a record corresponds to a row in a table. In Python, a namedtuple or a class can be used. In Java, a class with private fields and public methods acts as a record.

记录是一种数据结构，将多个可能不同类型的字段作为一个逻辑单元存储。在 SQL 中，一条记录对应表的一行。在 Python 中，可用 namedtuple 或类实现；在 Java 中，带私有字段和公有方法的类可作为记录。

A tuple is an ordered, immutable collection of items. Python tuples are written with parentheses, e.g., point = (3, 4). Records support field access by name, while tuples use index positions.

元组是有序、不可变的元素集合。Python 元组用圆括号表示，如 point = (3, 4)。记录通过字段名访问，元组则通过下标位置访问。

7. Sets and Dictionaries | 集合与字典

A set is an unordered collection of unique elements. Standard operations include union, intersection, difference, and membership testing. In Python, sets are created using curly braces: my_set = {1, 2, 3}.

集合是无序且元素唯一的集合。标准操作包括并集、交集、差集和成员测试。在 Python 中，用花括号创建集合：my_set = {1, 2, 3}。

A dictionary stores key-value pairs. Each key is unique and maps to a value. Dictionaries support fast lookup, insertion and deletion. In Python: student = {‘name’: ‘Ali’, ‘score’: 95}.

字典存储键值对。每个键唯一，并映射到一个值。字典支持快速查找、插入和删除。在 Python 中：student = {‘name’: ‘Ali’, ‘score’: 95}。

Structure / 结构	Ordered / 有序	Duplicates / 去重	Access / 访问
Set	No	Yes (unique)	Membership
Dictionary	Insertion order in Python 3.7+	Keys unique, values not	By key

8. Abstract Data Types (ADTs) | 抽象数据类型

An abstract data type (ADT) is a mathematical model for data types, defined by its behaviour (operations) rather than by its implementation. Common ADTs include stack, queue, linked list, and binary tree.

抽象数据类型（ADT）是一种数据类型的数学模型，由其行为（操作）而非具体实现来定义。常见 ADT 包括栈、队列、链表和二叉树。

The key idea is encapsulation: users interact with the ADT through a public interface, while the internal representation can change without affecting users.

其核心思想是封装：用户通过公共接口与 ADT 交互，而内部表示可以更改而不影响使用者。

9. Stacks | 栈

A stack is a LIFO (Last In, First Out) ADT. Items are added and removed at one end, called the top. Core operations: push(item), pop(), peek() or top(), and isEmpty().

栈是一种后进先出（LIFO）的抽象数据类型。元素的添加和移除都在同一端（栈顶）进行。核心操作：push（压栈）、pop（出栈）、peek / top（查看栈顶）和 isEmpty（是否为空）。

Applications include function call stacks, expression evaluation (e.g., converting infix to postfix), undo operations in editors, and backtracking in search algorithms.

应用场景包括函数调用栈、表达式求值（如中缀转后缀）、编辑器中的撤销操作以及搜索算法中的回溯。

Example: push 5 → push 2 → pop → top → stack contains [5]
示例：压入 5 → 压入 2 → 弹出 → 访问栈顶 → 栈中剩余 [5]

10. Queues | 队列

A queue is a FIFO (First In, First Out) ADT. Items are added at the rear and removed from the front. Operations: enqueue(item), dequeue(), front(), isEmpty().

队列是一种先进先出（FIFO）的抽象数据类型。元素从队尾加入，从队首移除。操作：入队 enqueue、出队 dequeue、查看队首 front、判空 isEmpty。

There are two common implementations: linear queue and circular queue. A linear queue can cause a “queue full” state even when there is space, due to rear reaching the array end. A circular queue solves this by using (rear + 1) mod size.

常见实现有两种：线性队列和循环队列。线性队列在数组尾部已用完但整体仍有空位时会出现”假溢出”；循环队列通过 (rear + 1) mod 大小来解决。

Priority queue: each element has a priority; the element with the highest priority is dequeued first.

优先队列：每个元素带有优先级，出队时优先处理优先级最高的元素。
Applications: task scheduling, print spooling, breadth-first search (BFS).

应用场景：任务调度、打印缓冲、广度优先搜索（BFS）。

11. Linked Lists | 链表

A linked list is a dynamic data structure consisting of nodes, where each node stores data and a pointer/reference to the next node. It can be singly linked, doubly linked, or circular.

链表是由节点组成的动态数据结构，每个节点存储数据以及指向下一个节点的指针/引用。链表可分为单向链表、双向链表和循环链表。

Compared with arrays, linked lists allow efficient insertion and deletion at arbitrary positions (provided you have the pointer), but they do not support random access and require extra memory for pointers.

与数组相比，链表在已知指针位置时插入和删除效率较高，但不支持随机访问，且需要额外内存存储指针。

Feature / 特性	Array / 数组	Linked List / 链表
Memory allocation / 内存分配	Contiguous / 连续	Scattered nodes / 分散节点
Access time / 访问时间	O(1) by index / 按下标 O(1)	O(n) sequential / 顺序 O(n)
Insertion at head / 表头插入	O(n) shift / O(n) 移位	O(1) with pointer / 有指针 O(1)

12. Binary Trees and Traversals | 二叉树与遍历

A binary tree is a hierarchical structure in which each node has at most two children: left and right. A binary search tree (BST) maintains the property: left subtree less than node, right subtree greater than node.

二叉树是一种层次结构，每个节点最多有两个子节点：左子节点和右子节点。二叉搜索树（BST）满足：左子树所有值小于根节点，右子树所有值大于根节点。

Three core traversals:

三种核心遍历方式：

Preorder (root, left, right): 50, 30, 20, 40, 70, 60, 80

前序遍历（根、左、右）：50, 30, 20, 40, 70, 60, 80
Inorder (left, root, right): 20, 30, 40, 50, 60, 70, 80 (sorted order for BST)

中序遍历（左、根、右）：20, 30, 40, 50, 60, 70, 80（对 BST 而言即为升序）
Postorder (left, right, root): 20, 40, 30, 60, 80, 70, 50

后序遍历（左、右、根）：20, 40, 30, 60, 80, 70, 50

In CIE exams, you may be asked to implement a binary tree using pointers or arrays, to search for a value, and to insert or delete a node. Depth-first search uses a stack, while breadth-first search uses a queue.

在 CIE 考试中，可能要求用指针或数组实现二叉树、查找某个值、插入或删除节点。深度优先搜索使用栈，广度优先搜索使用队列。

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

Examination questions often present a scenario and ask you to justify a data structure. The key is to map requirements to properties: if frequent insertion and deletion at both ends are needed, choose a linked list; if fast access by index is needed, choose an array; if LIFO processing is needed, choose a stack; if FIFO scheduling is needed, choose a queue; if hierarchical data such as a directory is involved, choose a tree.

考试常给出场景，要求你说明选择某种数据结构的原因。关键在于将需求映射到特性：若需要频繁在两端插入删除，选链表；若需要按下标快速访问，选数组；若需要后进先出处理，选栈；若需要先进先出调度，选队列；若处理目录等层次结构数据，选树。

Scenario / 场景	Best Choice / 最佳选择	Reason / 理由
Implementation of function call history / 函数调用历史	Stack	LIFO nature / 后进先出特性
Print job scheduling / 打印任务调度	Queue	FIFO fairness / 先进先出公平性
Lookup by student ID / 按学号查找	Dictionary / Hash table	O(1) average lookup / 平均 O(1) 查找

14. Common Pitfalls and Revision Tips | 常见误区与复习建议

Students frequently lose marks because they confuse ADT and implementation, forget to handle null pointers, or draw a tree traversal incorrectly. To avoid these, practise drawing pointer diagrams and trace through small examples step by step.

学生常因混淆 ADT 与其实现、忘记处理空指针、或画错遍历序列而失分。为避免这些问题，应反复练习指针图，并一步一步追踪小例子。

Always state whether your structure is static or dynamic, and explain the memory consequences.

务必说明结构是静态还是动态，并解释其内存影响。
When asked for an algorithm, use clear pseudocode or structured English; do not skip initialisation or boundary checks.

写算法时使用清晰的伪代码或结构化英语；不要跳过初始化或边界检查。
Practise converting between denary, binary, and hexadecimal every day; speed and accuracy matter.

每天练习十进制、二进制和十六进制转换；速度和准确度都很重要。
Master at least one implementation (array-based and pointer-based) for stack and queue.

对于栈和队列，至少掌握一种基于数组和一种基于指针的实现。

15. Summary | 总结

Data types and data structures form the foundation of every algorithm. A strong grasp of primitive types, arrays, records, sets, dictionaries, stacks, queues, linked lists, and binary trees will allow you to solve problem-solving and programming questions with confidence. Remember to always justify your choice of data structure in exam answers.

数据类型与数据结构是所有算法的基础。牢固掌握基本类型、数组、记录、集合、字典、栈、队列、链表和二叉树，将帮助你在问题求解与程序设计题目中游刃有余。答题时切记说明选择数据结构的原因，以体现分析能力。

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

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

A-Level Computer Science: Core Points of Data Types and Data Structures | A-Level计算机：数据类型与数据结构核心考点