Data Representation, Structures and Management | 数据表示、结构与管理考点梳理

📚 Data Representation, Structures and Management | 数据表示、结构与管理考点梳理

This article provides a comprehensive revision guide for the CIE A-Level Computer Science topic of Data Representation, Structures and Management. We focus on the key concepts you need to master for examinations, from binary arithmetic to complex data structures and file management.

本文为CIE A-Level计算机科学中“数据表示、结构与管理”考点的系统复习指南。我们聚焦考试中的核心概念，从二进制算术到复杂的数据结构与文件管理，逐一梳理。

1. Number Systems and Binary Arithmetic | 数制与二进制运算

Understanding denary, binary and hexadecimal number systems is fundamental. You must be able to convert between these bases fluently. Binary uses base 2 with digits 0 and 1; hexadecimal uses base 16 with digits 0-9 and A-F.

理解十进制、二进制和十六进制数制是基础。你必须能够熟练地在这些进制之间转换。二进制使用基数为2的0和1数字；十六进制使用基数为16的0-9和A-F数字。

Binary to denary: 1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 8 + 0 + 2 + 1 = 11₁₀

For hexadecimal conversion, group binary digits in sets of four. For example, 1011 1101₂ = BD₁₆. Each hexadecimal digit corresponds to exactly one nibble (4 bits) of binary.

十六进制转换时，将二进制数字按四位一组分组。例如，1011 1101₂ = BD₁₆。每个十六进制数字恰好对应二进制的四位（一个nibble）。

Denary to binary: repeated division by 2, recording remainders
Denary to hexadecimal: repeated division by 16, or convert via binary
Binary addition: carry rules apply when 1+1=10₂

十进制转二进制：反复除以2，记录余数
十进制转十六进制：反复除以16，或通过二进制中转
二进制加法：1+1=10₂时产生进位

2. Two’s Complement Representation | 二进制补码表示

Signed integers in A-Level Computer Science are typically represented using two’s complement. In an n-bit system, the most significant bit (MSB) holds the sign: 0 for positive, 1 for negative.

A-Level计算机科学中的有符号整数通常使用二进制补码表示。在n位系统中，最高有效位（MSB）表示符号：0为正，1为负。

Range of n-bit two’s complement: -2ⁿ⁻¹ to +2ⁿ⁻¹ – 1

To find the two’s complement of a negative number, invert all bits and add 1. For example, to represent -5 in 8 bits: 00000101 → 11111010 + 1 = 11111011.

求一个负数的二进制补码的方法是：将所有位取反然后加1。例如，用8位表示-5：00000101 → 11111010 + 1 = 11111011。

Subtraction is performed by adding the two’s complement of the subtrahend. This eliminates the need for a separate subtraction circuit.

减法运算通过加上减数的二进制补码来实现。这消除了对独立减法电路的需求。

3. Binary Addition and Overflow | 二进制加法与溢出

Binary addition follows simple rules: 0+0=0, 0+1=1, 1+1=0 carry 1, 1+1+1=1 carry 1. You must be able to add multiple binary numbers and detect overflow errors.

二进制加法遵循简单规则：0+0=0，0+1=1，1+1=0进位1，1+1+1=1进位1。你必须能够计算多个二进制数相加并检测溢出错误。

Overflow occurs when the result of an arithmetic operation exceeds the maximum value that can be stored in the given number of bits. For example, adding 01111111 and 00000001 in 8-bit two’s complement produces 10000000, which represents -128, an incorrect result.

当算术运算的结果超过给定位数能存储的最大值时，就会发生溢出。例如，8位补码中01111111加00000001得到10000000，表示-128，这是错误结果。

Operation	Binary	Decimal
A	01100110	102
B	00101010	42
A+B	10010000	144 (overflow in signed 8-bit)

In the table above, adding 102 and 42 in signed 8-bit gives 144, which exceeds 127, causing overflow. In unsigned interpretation, the same bit pattern correctly represents 144.

上表中，带符号8位相加102+42得到144，超过127，导致溢出。在无符号解释下，这一位模式正确地表示为144。

4. ASCII and Unicode Character Sets | ASCII与Unicode字符集

Characters are encoded as binary patterns. ASCII (American Standard Code for Information Interchange) uses 7 bits and can represent 128 characters. Extended ASCII uses 8 bits for 256 characters.

字符以二进制模式编码。ASCII（美国信息交换标准代码）使用7位，能表示128个字符。扩展ASCII使用8位，表示256个字符。

Unicode is a more comprehensive standard that supports virtually all writing systems worldwide. UTF-8 uses variable-length encoding: 1 to 4 bytes per character. ASCII is a subset of UTF-8, so ASCII-encoded text is valid UTF-8.

Unicode是一个更全面的标准，支持世界上几乎所有书写系统。UTF-8使用可变长度编码：每个字符1到4个字节。ASCII是UTF-8的子集，因此ASCII编码的文本也是合法的UTF-8。

ASCII ‘A’ = 65₁₀ = 01000001₂ | Unicode ‘A’ = U+0041

The primary advantage of Unicode over ASCII is its ability to represent characters from multiple languages and symbols (mathematical, emoji, etc.) in a single consistent standard.

Unicode相对于ASCII的主要优势在于它能在统一标准下表示多种语言的字符和符号（数学、表情符号等）。

5. Bitmap and Vector Graphics | 位图与矢量图形

Bitmap images store pixel data as binary values. Key parameters include resolution (width × height in pixels) and colour depth (bits per pixel). File size in bits = resolution × colour depth.

位图图像以二进制值存储像素数据。关键参数包括分辨率（宽×高，单位为像素）和颜色深度（每像素位数）。文件大小（位）= 分辨率 × 颜色深度。

File size (bits) = Width × Height × Colour Depth

Vector graphics store images as mathematical descriptions: coordinates, lines, curves and shapes. They are resolution-independent, so scaling does not cause quality loss. Vector files are typically smaller for simple geometric images.

矢量图形以数学描述方式存储图像：坐标、线条、曲线和形状。它们是分辨率无关的，缩放不会损失质量。对于简单几何图形，矢量文件通常更小。

Bitmap: detailed photographs, complex images; each pixel individually defined
Vector: logos, diagrams, text; resolution-independent scaling
Colour depth: 1 bit (monochrome), 8 bits (256 colours), 24 bits (true colour, 16.7M colours)

位图：细节丰富的照片、复杂图像；每个像素单独定义
矢量：标志、图表、文字；缩放与分辨率无关
颜色深度：1位（单色）、8位（256色）、24位（真彩色，1670万色）

6. Sound Representation | 声音的表示

Digital sound is created by sampling an analogue audio signal at regular intervals. The two critical parameters are sampling rate and bit depth.

数字声音通过对模拟音频信号进行定期采样而产生。两个关键参数是采样率和位深度。

Sampling rate is the number of samples taken per second, measured in hertz (Hz). Higher sampling rates capture higher frequencies accurately — the Nyquist theorem states the sampling rate must be at least twice the maximum frequency.

采样率是每秒采集的样本数，以赫兹（Hz）为单位。更高的采样率能准确捕获更高的频率——奈奎斯特定理指出采样率必须至少是最高频率的两倍。

Bit depth determines the number of possible amplitude levels per sample. With 16-bit depth, there are 2¹⁶ = 65,536 possible amplitude values. Increasing bit depth reduces quantisation error (noise).

位深度决定每个样本可能的振幅级别数。使用16位深度时，有2¹⁶ = 65,536种可能的振幅值。增加位深度可减少量化误差（噪声）。

File size (bits) = Sampling Rate × Bit Depth × Duration (seconds) × Channels

7. Data Compression Techniques | 数据压缩技术

Compression reduces file sizes for efficient storage and transmission. There are two main categories: lossless and lossy compression.

压缩减少文件大小以便高效存储和传输。主要有两类：无损压缩和有损压缩。

Lossless compression preserves all original data — the decompressed file is identical to the original. Run-Length Encoding (RLE) replaces repeated consecutive values with a count and value pair. For example, “AAAAABBBCC” becomes “5A3B2C”.

无损压缩保留所有原始数据——解压缩后的文件与原始文件完全相同。行程长度编码（RLE）用计数值对替换重复的连续值。例如，”AAAAABBBCC”变为”5A3B2C”。

Huffman coding assigns shorter codes to frequent characters and longer codes to rare characters. It constructs a binary tree where leaf nodes represent characters, with code lengths proportional to frequency.

哈夫曼编码为高频字符分配较短的编码，为低频字符分配较长的编码。它构建一棵二叉树，叶节点代表字符，编码长度与频率成正比。

Character	Frequency	Huffman Code
A	6	0
B	2	11
C	1	101

Lossy compression permanently removes some data deemed less important. It is commonly used for images (JPEG), audio (MP3) and video (MPEG). The trade-off is reduced quality in exchange for significantly smaller file sizes.

有损压缩永久性地删除一些被认为不太重要的数据。它常用于图像（JPEG）、音频（MP3）和视频（MPEG）。代价是质量降低，但换来的文件大小显著变小。

8. Arrays and Records | 数组与记录

An array is a collection of elements of the same data type stored in contiguous memory locations. In A-Level, you must understand 1D and 2D arrays and their indexing.

数组是相同数据类型的元素集合，存储在连续的内存位置中。在A-Level中，你必须理解一维和二维数组及其索引方式。

A 1D array of n elements has indices 0 to n-1 (zero-indexed) or 1 to n (one-indexed), depending on the programming language. A 2D array is essentially an array of arrays, often visualised as a table with rows and columns.

一维数组有n个元素，索引为0到n-1（从零开始）或1到n（从一开始），具体取决于编程语言。二维数组本质上是数组的数组，通常可视化为具有行和列的表。

Accessing element at row i, column j in 2D array: array[i][j]

A record is a composite data structure that groups related data of potentially different types under one name. Each individual piece of data in a record is called a field.

记录是一种复合数据结构，将可能不同类型的相关数据按一个名称组合在一起。记录中每一条独立数据称为字段。

Unlike arrays, records can hold heterogeneous data types — for example, a student record with a name (string), age (integer) and exam score (real).

与数组不同，记录可以包含异构数据类型——例如，一个学生记录包含姓名（字符串）、年龄（整数）和考试分数（实数）。

9. Linked Lists and Stacks | 链表与栈

A linked list is a dynamic data structure consisting of nodes, where each node contains data and a pointer/reference to the next node. The list is accessed via a head pointer, and the last node points to null.

链表是一种动态数据结构，由节点组成，每个节点包含数据以及指向下一个节点的指针/引用。通过头指针访问链表，最后一个节点指向null。

Linked list operations include adding a new node, removing a node, and traversing the list. To insert a node, adjust the pointer of the previous node to point at the new node, and set the new node’s pointer to the original next node.

链表操作包括添加节点、删除节点和遍历链表。插入节点时，将前一个节点的指针调整到指向新节点，并将新节点的指针设置为原下一个节点。

A stack is a Last-In-First-Out (LIFO) data structure. Primary operations are PUSH (add to top), POP (remove from top) and PEEK/TOP (inspect top without removing).

栈是一种后进先出（LIFO）数据结构。主要操作包括PUSH（压入顶部）、POP（从顶部弹出）和PEEK/TOP（查看顶部但不移除）。

Stacks are used for function call management, expression evaluation, undo operations and backtracking algorithms. A stack can be implemented using an array (with a pointer tracking the top index) or a linked list.

栈用于函数调用管理、表达式求值、撤销操作和回溯算法。栈可以通过数组（用指针跟踪栈顶索引）或链表实现。

10. Queues and Trees | 队列与树

A queue is a First-In-First-Out (FIFO) data structure, akin to a waiting line. Elements are added at the rear and removed from the front. Operations include ENQUEUE and DEQUEUE.

队列是先进先出（FIFO）的数据结构，类似排队等候。元素在队尾添加，从队头移除。操作包括入队（ENQUEUE）和出队（DEQUEUE）。

Circular queues overcome the problem of wasted space in linear array-based queue implementations by wrapping around. A front and rear pointer are maintained, and incrementing past the last index wraps to index 0.

环形队列通过回绕方式克服线性数组实现中空间浪费的问题。维护front和rear指针，超过最后索引时回绕到索引0。

A binary tree is a hierarchical structure where each node has at most two children: left and right. The root is the topmost node. Binary search trees (BSTs) maintain ordering: all left subtree values are less than the node, all right subtree values are greater.

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

Tree traversal methods include preorder (root-left-right), inorder (left-root-right) and postorder (left-right-root). In a BST, inorder traversal yields values in ascending order.

树的遍历方法包括前序（根-左-右）、中序（左-根-右）和后序（左-右-根）。在BST中，中序遍历按升序输出所有值。

11. File Management and Databases | 文件管理与数据库

File management in Computer Science involves organising data for efficient storage, retrieval and update. The two main file organisations are serial and sequential access.

计算机科学中的文件管理涉及为高效存储、检索和更新而组织数据。两种主要文件组织方式为串行访问和顺序访问。

Serial access files store records consecutively without any ordering. To find a record, the file is searched from the beginning — appropriate when processing all records is required.

串行访问文件不按顺序存储记录。要找到一条记录，需从头搜索文件——适用于需要处理所有记录的场景。

Sequential access files use keys to store records in a logical order. Records can be accessed in sorted order, but inserting or deleting records may require rewriting the entire file.

顺序访问文件使用键按逻辑顺序存储记录。记录可以按排序顺序访问，但插入或删除记录可能需要重写整个文件。

Databases use a structured approach with tables, records (rows) and fields (columns). SQL (Structured Query Language) is the standard language for querying and managing relational databases.

数据库使用结构化方法，包括表、记录（行）和字段（列）。SQL（结构化查询语言）是查询和管理关系数据库的标准语言。

Key SQL statements include SELECT (retrieve data), INSERT (add rows), UPDATE (modify rows), DELETE (remove rows) and CREATE TABLE (define structure). A primary key uniquely identifies each row; a foreign key links tables by referencing a primary key in another table.

关键SQL语句包括SELECT（检索数据）、INSERT（添加行）、UPDATE（修改行）、DELETE（删除行）和CREATE TABLE（定义结构）。主键唯一标识每一行；外键通过引用另一表中的主键来连接表。

12. Master Tips for Examinations | 考试致胜技巧

When working through data representation problems, always state units clearly: bits versus bytes. Read questions carefully to determine whether the context is signed or unsigned, and identify the word length (e.g. 8-bit, 16-bit).

解答数据表示问题时，始终明确单位：位（bit）还是字节（byte）。仔细阅读题目以判断是有符号还是无符号情景，并确认字长（如8位、16位）。

Always convert binary addition results back to denary to verify correctness
When calculating file sizes, convert all values to the same unit first
For Huffman questions, check that prefix-free property holds
In linked list exam questions, trace pointer changes step by step
For SQL questions, be careful with WHERE conditions for range queries

将二进制加法结果转换回十进制以验证正确性
计算文件大小时，先将所有值转换为相同单位
哈夫曼题目中，检查前缀无关性是否成立
链表考题中，逐步追踪指针变化
SQL题目中，注意范围查询的WHERE条件

Finally, practise past-paper questions under timed conditions. The ability to perform base conversions quickly and write correct SQL statements under pressure is what separates top-scoring candidates.

最后，在限时条件下练习历年真题。快速进行进制转换的能力和在压力下写出正确SQL语句的能力，是高分考生与普通考生的分水岭。

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

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

Data Representation, Structures and Management | 数据表示、结构与管理考点梳理