📚 Year 12 CIE Computer Science Quick Reference | CIE 12年级计算机科学公式定理速查手册
Welcome to the essential formula, theorem, and rule handbook for Year 12 CIE Computer Science (9618). This guide covers the key quantitative and conceptual models you will encounter in the AS-Level syllabus—from data representation and transmission to Boolean algebra, processor performance, and algorithm complexity. Each section presents concise English explanations paired with Chinese translations, helping you consolidate knowledge quickly for revision.
欢迎使用 CIE 计算机科学（9618）12 年级必备的公式、定理与规则速查手册。本手册覆盖了 AS 阶段课程中关键的量化模型和概念模型——从数据表示和传输、布尔代数，到处理器性能和算法复杂度。每个小节先提供简明的英文解释，再配以中文翻译，帮助你快速巩固知识，高效备考。
1. Data Representation Calculations | 数据表示计算
File sizes for images, audio, and text can be calculated using straightforward formulas. An uncompressed bitmap image size = width (px) × height (px) × colour depth (bits) / 8 bytes. For audio, file size = sample rate (Hz) × bit depth (bits) × number of channels × duration (seconds) / 8 bytes. Compression ratio = uncompressed size / compressed size, a value greater than 1 indicating space savings.
图像、音频和文本的文件大小可以用简单的公式计算。未压缩位图图像的大小 = 宽度（像素）× 高度（像素）× 色深（位）/ 8 字节。音频文件大小 = 采样率（赫兹）× 位深度（位）× 声道数 × 时长（秒）/ 8 字节。压缩比 = 未压缩大小 / 压缩后大小，比值大于 1 表示节省了空间。
| Formula | 公式 |
|---|---|
| Bitmap Size = W × H × D / 8 B | 位图大小 = 宽 × 高 × 色深 / 8 字节 |
| Audio Size = SR × BD × Ch × s / 8 B | 音频大小 = 采样率 × 位深度 × 声道数 × 秒数 / 8 字节 |
| Compression Ratio = Uncompressed / Compressed | 压缩比 = 未压缩大小 / 压缩后大小 |
2. Network Transmission Formulas | 网络传输公式
Bit rate and baud rate are fundamental. Bit rate (bps) = baud rate × bits per symbol. When a signal uses two levels, bit rate equals baud rate; with four voltage levels, each symbol carries 2 bits, doubling the bit rate. Transmission delay for a packet is size (bits) / bandwidth (bps). Propagation delay = distance / propagation speed.
比特率和波特率是基础。比特率（bps）= 波特率 × 每符号比特数。当信号使用两个电平时，比特率等于波特率；使用四个电平时，每个符号携带 2 个比特，比特率翻倍。数据包的传输时延 = 数据量（比特）/ 带宽（bps）。传播时延 = 距离 / 传播速度。
| Formula | 公式 |
|---|---|
| Bit Rate = Baud Rate × log₂(L) | 比特率 = 波特率 × log₂(电平数) |
| Transmission Delay = Data / Bandwidth | 传输时延 = 数据量 / 带宽 |
| Propagation Delay = Distance / Speed | 传播时延 = 距离 / 速度 |
3. Boolean Algebra Laws | 布尔代数定律
A solid grasp of Boolean identities allows simplification of logic circuits. Key laws include commutativity (A+B = B+A), associativity (A+(B+C) = (A+B)+C), distributivity (A·(B+C) = A·B + A·C), absorption (A + A·B = A), and De Morgan’s theorems: (A·B)’ = A’ + B’ and (A+B)’ = A’ · B’. The complement law states A + A’ = 1 and A · A’ = 0.
牢固掌握布尔恒等式可以简化逻辑电路。关键定律包括交换律（A+B = B+A）、结合律（A+(B+C) = (A+B)+C）、分配律（A·(B+C) = A·B + A·C）、吸收律（A + A·B = A），以及德摩根定理：(A·B)’ = A’ + B’ 和 (A+B)’ = A’·B’。互补律规定 A + A’ = 1，A·A’ = 0。
| Law | 表达式 |
|---|---|
| Identity | A + 0 = A, A·1 = A |
| Domination | A + 1 = 1, A·0 = 0 |
| Idempotent | A + A = A, A·A = A |
| Double Negation | (A’)’ = A |
| De Morgan | (A·B)’ = A’ + B’, (A+B)’ = A’·B’ |
4. Processor Performance Metrics | 处理器性能度量
CPU execution time is the ultimate performance measure. Execution Time = (Instruction Count × CPI) / Clock Rate. CPI (Cycles Per Instruction) is the average number of clock cycles each instruction takes. Clock Rate = 1 / Clock Period. MIPS (Million Instructions Per Second) = Instruction Count / (Execution Time × 10⁶). When comparing processors, a lower CPI or a higher clock rate generally reduces execution time.
CPU 执行时间是最终的性能衡量标准。执行时间 = (指令数 × CPI) / 时钟频率。CPI（每条指令的时钟周期数）是每条指令平均需要的时钟周期数。时钟频率 = 1 / 时钟周期。MIPS（每秒百万条指令）= 指令数 / (执行时间 × 10⁶)。比较处理器时，较低的 CPI 或较高的时钟频率通常能减少执行时间。
| Formula | 公式 |
|---|---|
| Execution Time = IC × CPI × Tclk | 执行时间 = 指令数 × CPI × 时钟周期 |
| Execution Time = (IC × CPI) / f | 执行时间 = (指令数 × CPI) / 频率 |
| MIPS = IC / (ET × 10⁶) | MIPS = 指令数 / (执行时间 × 10⁶) |
5. Algorithm Complexity and Big-O | 算法复杂度与大O表示法
Big-O notation describes the upper bound of an algorithm’s running time or space usage as the input size n grows. O(1) means constant time, O(log n) logarithmic (binary search), O(n) linear (linear search), O(n log n) linearithmic (merge sort), O(n²) quadratic (bubble sort), and O(2ⁿ) exponential (recursive Fibonacci). These abstract growth rates help predict scalability.
大 O 表示法描述了随着输入规模 n 的增长，算法的运行时间或空间占用的上界。O(1) 表示常数时间，O(log n) 对数级（二分查找），O(n) 线性（线性查找），O(n log n) 线性对数级（归并排序），O(n²) 平方级（冒泡排序），O(2ⁿ) 指数级（递归斐波那契）。这些抽象的增长速率有助于判断可扩展性。
| Algorithm | Best / Average / Worst |
|---|---|
| Linear Search | O(1) / O(n) / O(n) |
| Binary Search | O(1) / O(log n) / O(log n) |
| Bubble Sort | O(n) / O(n²) / O(n²) |
| Merge Sort | O(n log n) / O(n log n) / O(n log n) |
| Quick Sort | O(n log n) / O(n log n) / O(n²) |
6. ADT Operations and Tree Properties | 抽象数据类型操作与树的性质
Stack operations push() and pop() are O(1). Queue enqueue() and dequeue() are O(1) for array-based implementations with advancing pointers. A binary search tree lookup is O(log n) when balanced. For a full binary tree of height h, maximum nodes = 2ʰ − 1. A complete binary tree of n nodes has height ⌊log₂ n⌋. Linked list insertion at head is O(1); searching is O(n).
栈的 push() 和 pop() 操作的时间复杂度是 O(1)。基于数组并移动指针的队列，enqueue() 和 dequeue() 是 O(1)。平衡二叉查找树的查找复杂度为 O(log n)。对于高度为 h 的满二叉树，最多节点数 = 2ʰ − 1。具有 n 个节点的完全二叉树，其高度为 ⌊log₂ n⌋。链表头插法为 O(1)；查找为 O(n)。
| Structure | Key Complexity or Property |
|---|---|
| Stack (array/linked) | Push/Pop O(1); Peek O(1) |
| Queue (circular array) | Enqueue/Dequeue O(1) |
| Full Binary Tree | Nodes = 2ʰ − 1 |
| BST (balanced) | Search/Insert/Delete O(log n) |
7. Database Normalisation Rules | 数据库规范化规则
First Normal Form (1NF) requires atomic values and no repeating groups. Second Normal Form (2NF) builds on 1NF by removing partial dependencies: every non-key attribute must depend on the whole primary key. Third Normal Form (3NF) further removes transitive dependencies; a non-key attribute must not depend on another non-key attribute. These rules reduce redundancy and update anomalies.
第一范式（1NF）要求原子值且无重复组。第二范式（2NF）在 1NF 的基础上消除部分依赖：每个非主键属性必须完全依赖于整个主键。第三范式（3NF）进一步消除传递依赖；非主键属性不能依赖于另一个非主键属性。这些规则可以减少冗余和更新异常。
8. Encryption and Hash Functions | 加密与哈希函数
A Caesar cipher shifts each letter by a fixed key k: Enc(x) = (x + k) mod 26 (taking A=0). One-time pad (Vernam cipher) uses a truly random key the same length as the plaintext; encryption is bitwise XOR. RSA is an asymmetric algorithm: choose primes p, q; n = p×q; φ(n) = (p−1)(q−1); select e coprime with φ; compute d = e⁻¹ mod φ. Public key (n, e), private key (d). Hash functions like SHA-256 map arbitrary data to a fixed-size digest with avalanche effect and pre-image resistance.
凯撒密码将每个字母按固定密钥 k 移位：Enc(x) = (x + k) mod 26（A=0）。一次性密钥本（Vernam 密码）使用与明文等长的真随机密钥，加密过程为逐位异或。RSA 是非对称算法：选取素数 p, q；n = p×q；φ(n) = (p−1)(q−1)；选择与 φ 互质的 e；计算 d = e⁻¹ mod φ。公钥为 (n, e)，私钥为 (d)。像 SHA-256 这样的哈希函数将任意数据映射为固定大小的摘要，具有雪崩效应和原像抵抗性。
9. Error Detection and Correction | 错误检测与纠正
Parity bit adds one bit to make the number of 1s even (even parity) or odd. Checksum sums all data blocks (often 16-bit) and appends the complement. Cyclic Redundancy Check (CRC) treats data as a binary polynomial and divides by a generator polynomial; the remainder is appended. Hamming distance is the number of bit positions where two code words differ; a code with minimum distance d can detect up to d−1 errors and correct up to ⌊(d−1)/2⌋ errors.
奇偶校验位添加一个比特，使 1 的个数为偶数（偶校验）或奇数。校验和将所有数据块（通常 16 位）求和并附加其补码。循环冗余校验（CRC）将数据视为二进制多项式，并除以生成多项式；余数被附加到数据后。汉明距离是两个码字不同的比特位数；最小距离为 d 的编码可以检测最多 d−1 个错误，并纠正最多 ⌊(d−1)/2⌋ 个错误。
10. Floating-Point and Measurement Error | 浮点数与测量误差
A floating-point number is represented as ± mantissa × 2^exponent (binary). For AS, the format is often 8-bit mantissa, 4-bit exponent (two’s complement). Normalisation ensures the mantissa has no leading zeros. Absolute error = |approximation − true value|. Relative error = absolute error / true value, often expressed as a percentage. Range and precision are limited by the number of bits allocated.
浮点数表示为 ± 尾数 × 2^指数（二进制）。AS 阶段常使用 8 位尾数、4 位指数（二进制补码）的格式。规格化确保尾数没有前导零。绝对误差 = |近似值 − 真实值|。相对误差 = 绝对误差 / 真实值，常用百分比表示。范围和精度受分配给尾数和指数的位数限制。
Normalised form: mantissa MSB = first non-zero bit (e.g. 0.1xxxxx for positive numbers)
规格化形式：尾数最高位为首个非零位（如正数 0.1xxxxx）
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课程辅导，国外大学本科硕士研究生博士课程论文辅导