📚 Year 12 CCEA Computer Science: Formula and Theorem Quick Reference | Year 12 CCEA 计算机：公式定理速查手册
Welcome to your essential quick-reference guide for CCEA AS-Level Computer Science. This handbook consolidates the key formulas, theorems, and rules you’ll need to recall for examinations, from binary manipulation and Boolean algebra to big-O notation and data structures. Keep it handy as a last-minute revision aid.
欢迎使用 CCEA AS-Level 计算机科学的必备速查手册。本手册汇总了考试中需要记忆的关键公式、定理和规则，涵盖二进制运算、布尔代数、大O表示法以及数据结构等内容。请随身携带，作为考前冲刺的复习助手。
1. Binary Representation and Bitwise Operations | 二进制表示与位运算
Understand how integers and fractions are stored in fixed-width registers, and master the two’s complement system and logical shifts.
理解整数和小数如何在固定宽度寄存器中存储，并掌握二进制补码系统和逻辑移位。
For an n-bit register, the range for unsigned integers is 0 to 2ⁿ – 1.
对于n位寄存器，无符号整数的范围是 0 到 2ⁿ – 1。
For two’s complement signed integers, the range is –2ⁿ⁻¹ to 2ⁿ⁻¹ – 1.
二进制补码有符号整数的范围是 –2ⁿ⁻¹ 到 2ⁿ⁻¹ – 1。
A left arithmetic shift multiplies by 2; a right arithmetic shift divides by 2, preserving sign.
算术左移相当于乘以2；算术右移相当于除以2，并保留符号位。
To negate a two’s complement number: invert all bits (one’s complement) and add 1.
求二进制补码的负数：将所有位取反（反码）后加 1。
–X = NOT(X) + 1
Fixed-point fractional representation: For a binary point placed after k bits, the value is integer value × 2⁻ᵏ.
定点小数表示：若二进制小数点置于 k 位之后，其值为整数值 × 2⁻ᵏ。
- Logical (unsigned) shift: fills vacant bits with 0.
- 算术（有符号）移位：右移时空出位用符号位填充。
2. Floating Point Normalisation | 浮点数规范化
A normalised floating-point representation stores a number as mantissa × 2^exponent, ensuring the mantissa’s most significant bit differs from the sign bit.
规范化浮点数表示将数字存储为 尾数 × 2^指数，确保尾数的最高有效位与符号位不同。
In normalised form, a positive mantissa must begin with 01, and a negative mantissa with 10 (in two’s complement).
在规范化形式中，正尾数必须以 01 开头，负尾数以 10 开头（二进制补码）。
To convert a denary number to normalised binary floating point, repeatedly multiply or divide by 2 until the mantissa satisfies the normalisation condition, adjusting the exponent accordingly.
将十进制数转换为规范化二进制浮点数时，反复乘以或除以2，直到尾数满足规范化条件，并相应调整指数。
Value = Mantissa × 2^(Exponent)
3. Boolean Algebra and Logic Gates | 布尔代数与逻辑门
Boolean algebra governs the design and simplification of digital circuits. Know the identities and laws by heart.
布尔代数支配着数字电路的设计与化简。请牢记这些恒等式和定律。
Fundamental identities:
基本恒等式：
- A + 0 = A | A · 1 = A
- A + 1 = 1 | A · 0 = 0
- A + A = A | A · A = A
- A + ¬A = 1 | A · ¬A = 0
- ¬(¬A) = A (Double negation / 双重否定)
Laws of Boolean algebra:
布尔代数定律：
| Commutative / 交换律 | A + B = B + A · A · B = B · A |
| Associative / 结合律 | (A + B) + C = A + (B + C) · (A · B) · C = A · (B · C) |
| Distributive / 分配律 | A · (B + C) = A·B + A·C / A + (B·C) = (A+B)·(A+C) |
| Absorption / 吸收律 | A + (A·B) = A / A · (A+B) = A |
De Morgan’s Theorems:
德·摩根定理：
¬(A · B) = ¬A + ¬B
¬(A + B) = ¬A · ¬B
Logic gates correspond 1:1 to Boolean operators: AND (·), OR (+), NOT (¬), NAND (¬(·)), NOR (¬(+)), XOR (⊕). XOR is true when inputs differ: A⊕B = A·¬B + ¬A·B.
逻辑门与布尔运算符一一对应：与门 (·)、或门 (+)、非门 (¬)、与非门 (¬(·))、或非门 (¬(+))、异或门 (⊕)。异或门在输入不同时为真：A⊕B = A·¬B + ¬A·B。
4. Combinational Circuit Simplification | 组合电路化简
Simplification is often tested using Karnaugh maps (K-maps) for up to four variables. The aim is to minimise the sum-of-products expression.
化简通常使用最多四个变量的卡诺图进行考查，目的是最小化与-或表达式。
To fill a K-map for F(A,B,C,D), mark cells where F=1. Group adjacent 1s in powers of two (1,2,4,8) to form prime implicants. Overlapping groups are allowed. Remember the map wraps around edges.
填写函数 F(A,B,C,D) 的卡诺图时，标记 F=1 的单元格。将相邻的 1 以 2 的幂次方 (1,2,4,8) 分组，形成质蕴含项。分组可以重叠。注意卡诺图的边缘是循环连通的。
The simplified expression = sum of the product terms derived from each group, dropping variables that change within the group.
简化后的表达式 = 从每个分组得到的乘积项之和，舍弃组内发生变化的变量。
5. Propositional Logic and Proof | 命题逻辑与证明
Propositional logic uses connectives: ¬ (not), ∧ (and), ∨ (or), → (implies), ↔ (equivalence). Truth tables define the meaning of each.
命题逻辑使用连接词：¬（非）、∧（与）、∨（或）、→（蕴含）、↔（等价）。真值表定义了每个连接词的含义。
Implication equivalence: P → Q ≡ ¬P ∨ Q
蕴含等价式：P → Q ≡ ¬P ∨ Q
A tautology is a statement true under all interpretations; a contradiction is always false.
重言式是在所有解释下均为真的命题；矛盾式则是始终为假。
Logical arguments can be tested using truth tables or natural deduction rules. Modus ponens: from P → Q and P, infer Q. Modus tollens: from P → Q and ¬Q, infer ¬P.
逻辑论证可使用真值表或自然演绎规则验证。肯定前件：由 P → Q 和 P，推出 Q。否定后件：由 P → Q 和 ¬Q，推出 ¬P。
6. Big-O Notation and Algorithmic Complexity | 大O表示法与算法复杂度
Big-O provides an upper bound on the growth rate of a function, used to classify algorithms by their worst-case running time or space usage.
大O表示法给出了函数增长速率的上界，用于根据最坏情况下的运行时间或空间使用对算法进行分类。
Common orders:
- O(1) – constant time (例如数组访问)
- O(log n) – logarithmic time (二分查找)
- O(n) – linear time (线性查找)
- O(n log n) – linearithmic time (归并排序, 快速排序平均情况)
- O(n²) – quadratic time (冒泡排序, 插入排序)
- O(2ⁿ) – exponential time (某些递归问题)
For a linear search of n items, worst-case comparisons = n (O(n)). For a binary search, worst-case comparisons ≈ log₂(n) (O(log n)).
在 n 个元素中线性查找，最坏情况下比较次数 = n (O(n))。二分查找，最坏情况比较次数 ≈ log₂(n) (O(log n))。
To determine Big-O from code, count the dominant term of the number of operations as input size grows; ignore constants and lower-order terms.
根据代码确定大O：随着输入规模增长，计算操作数量的主导项；忽略常数项和低阶项。
7. Hash Tables and Addressing | 哈希表与地址计算
Hashing maps a key to an index in an array. A good hash function distributes keys uniformly to minimise collisions.
哈希将键映射为数组中的索引。好的哈希函数能均匀分布键以最小化冲突。
Modulo hashing formula:
取模哈希公式：
index = key mod tableSize
For collision resolution, open addressing (linear probing) uses: index = (hash(key) + i) mod tableSize, where i is the probe number (0,1,2,…).
冲突解决中，开放定址法（线性探测）使用：index = (hash(key) + i) mod tableSize，其中 i 为探测次数 (0,1,2,…)。
Load factor = number of entries / table size. Performance degrades when load factor exceeds 0.7; rehashing increases table size.
负载因子 = 条目数 / 表大小。当负载因子超过 0.7 时性能下降；再哈希会增大表的大小。
8. Data Compression Calculations | 数据压缩计算
Understand run-length encoding (RLE) and dictionary-based methods. Calculate compression ratios.
理解游程编码 (RLE) 和基于字典的方法。计算压缩比。
Compression ratio:
压缩比：
Ratio = uncompressed size / compressed size
For RLE, a repeating character is stored as (count, character). The compressed size depends on the encoding convention, e.g., 1 byte for count + 1 byte for the character.
对于 RLE，重复字符被存储为 （计数，字符）。压缩后的大小取决于编码约定，例如计数1字节加字符1字节。
Huffman coding creates variable-length codes based on symbol frequencies. The weighted path length = Σ(frequency × code length) gives the average bits per symbol.
霍夫曼编码根据符号频率创建变长编码。加权路径长度 = Σ(频率 × 码长) 给出每个符号的平均比特数。
9. Processor Performance Metrics | 处理器性能指标
Key formulas relate clock speed, performance, and program execution time.
关键公式关联时钟速度、性能和程序执行时间。
Execution Time = (Number of instructions × CPI) / Clock frequency
Where CPI = average clock cycles per instruction.
其中 CPI = 每条指令的平均时钟周期数。
Clock frequency (Hz) = 1 / Clock period
MIPS (Million Instructions Per Second) = (instruction count / execution time) × 10⁻⁶.
MIPS（每秒百万条指令）=（指令数 / 执行时间）× 10⁻⁶。
Amdahl’s Law gives the theoretical speedup when only part of a program is improved:
阿姆达尔定律给出程序只有一部分得到改进时的理论加速比：
Speedup = 1 / ((1 – fraction_enhanced) + (fraction_enhanced / speedup_enhanced))
10. Numerical Methods: Bisection and Newton-Raphson | 数值方法：二分法与牛顿-拉弗森法
These root-finding algorithms are applied to equation f(x)=0. Know the recurrence formulas and convergence conditions.
这些求根算法应用于方程 f(x)=0。掌握递推公式和收敛条件。
Bisection method: Given interval [a,b] with f(a)·f(b) < 0, the midpoint c = (a+b)/2. Replace a or b with c depending on sign of f(c). The error bound after n iterations is |b-a|/2ⁿ.
二分法：给定区间 [a,b] 满足 f(a)·f(b) < 0，中点 c = (a+b)/2。根据 f(c) 的符号用 c 替换 a 或 b。n 次迭代后的误差界限为 |b-a|/2ⁿ。
Newton-Raphson formula:
牛顿-拉弗森公式：
xₙ₊₁ = xₙ – f(xₙ) / f'(xₙ)
Requires a starting guess x₀. Converges quadratically near the root if f'(x) ≠ 0.
需要一个初始猜测 x₀。在根附近若 f'(x) ≠ 0，则具有二次收敛速度。
11. Sorting and Searching Algorithm Complexity | 排序与搜索算法复杂度
Recall the time complexities of standard algorithms, as they often appear in multiple-choice or short-answer questions.
回忆标准算法的时间复杂度，因为它们经常出现在选择题或简答题中。
| Algorithm / 算法 | Best / 最好 | Average / 平均 | Worst / 最坏 |
| Bubble Sort 冒泡排序 | O(n) | O(n²) | O(n²) |
| Insertion 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²) |
| Linear Search 线性查找 | O(1) | O(n) | O(n) |
| Binary Search 二分查找 | O(1) | O(log n) | O(log n) |
Merge sort is stable; quick sort is not. Binary search requires a sorted array.
归并排序是稳定的；快速排序不是。二分查找要求数组已排序。
12. Number Systems Conversion Formulas | 数制转换公式
Quick reference for converting between binary, denary, hexadecimal, and BCD.
二进制、十进制、十六进制和 BCD 之间的转换速查。
- Binary to Denary: Sum of each bit × 2^position (starting 0 from right). 二进制转十进制：每位比特 × 2^位值 之和（从右起位值0）。
- Denary to Binary: Repeated division by 2, read remainders bottom-to-top. 十进制转二进制：反复除以2，从下向上读取余数。
- Binary to Hex: Group bits in fours starting from right; each group maps to 0–F. 二进制转十六进制：从右起四位一组；每组映射到 0–F。
- BCD: Each denary digit (0-9) coded as its 4-bit binary equivalent. 每个十进制数字（0-9）编码为对应的4位二进制数。
One hexadecimal digit corresponds to 4 binary bits. Two hex digits represent one byte.
一个十六进制数字对应 4 个二进制位。两个十六进制数字表示一个字节。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导