Year 12 CCEA Computer Science: Formula and Theorem Quick Reference | Year 12 CCEA 计算机：公式定理速查手册

📚 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 | 浮点数规范化

ating-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.

化简通常使用最多四个变量的卡诺图进行考查，目的是最小化与-或表达式。

owers 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) 分组，形成质蕴含项。分组可以重叠。注意卡诺图的边缘是循环连通的。

he 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.

重言式是在所有解释下均为真的命题；矛盾式则是始终为假。

al 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 (某些递归问题)

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：随着输入规模增长，计算操作数量的主导项；忽略常数项和低阶项。

---

广告 / Sponsored

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

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,…)。

e 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字节。

. 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 | 数值方法：二分法与牛顿-拉弗森法

s are applied to equation f(x)=0. Know the recurrence formulas and convergence conditions.

这些求根算法应用于方程 f(x)=0。掌握递推公式和收敛条件。

Bisection method: /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（同微信）