📚 Formula & Theorems Quick Reference Handbook for Pre-U Edexcel Computer Science | 公式定理速查手册
This handbook consolidates essential formulas, laws, and theorems needed for the Pre-U Edexcel Computer Science syllabus. It serves as a rapid revision tool, covering number systems, Boolean logic, algorithm complexity, data structures, and more.
本手册汇集了Pre-U爱德思计算机科学课程所需的基本公式、定律和定理。它可作为快速复习工具，涵盖数制、布尔逻辑、算法复杂度、数据结构等内容。
1. Number Systems & Conversions | 数制与转换
ᵢ × 2ⁱ. Denary to binary conversion uses repeated division by 2, reading remainders bottom‑up. Hexadecimal (base 16) uses digits 0–9 and A–F; each hex digit corresponds to a 4‑bit nibble.
二进制数 bₙ₋₁...b₁b₀ 的十进制值为 Σ bᵢ × 2ⁱ。十进制转二进制采用反复除以 2 取余，从下往上读取余数。十六进制（基数 16）使用数字 0–9 和字母 A–F；每个十六进制位对应一个 4 位半字节。
ex → binary by expanding each hex digit to 4 bits. Octal (base 8) groups 3 bits per digit.
关键转换技巧：二进制转十六进制时，从右开始每 4 位分组；十六进制转二进制则将每个十六进制位展开为 4 位。八进制（基数 8）按每 3 位分组。
complement representation expresses negative integers by inverting all bits and adding 1: –N = (flip bits of N) + 1.
二进制补码表示法通过将所有位取反后加 1 来表示负整数：–N = （将 N 取反） + 1。
2. Boolean Algebra Laws | 布尔代数定律
Boolean algebra governs logic circuits with operators AND (·), OR (+), and NOT (‾). The following laws are essential for simplification.
布尔代数用与 (·)、或 (+) 和非 (‾) 运算描述逻辑电路。以下定律对化简至关重要。
| Law | AND Form | OR Form |
|---|---|---|
| Identity | A · 1 = A | A + 0 = A |
| Annulment | A · 0 = 0 | A + 1 = 1 |
| Idempotent | A · A = A | A + A = A |
| Complement | A · ̄A = 0 | A + ̄A = 1 |
| 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 | ̄(A·B) = ̄A + ̄B | ̄(A+B) = ̄A · ̄B |
These laws enable the minimisation of logic expressions, reducing gate count and circuit cost.
这些定律可以对逻辑表达式进行最小化，从而减少门数量和电路成本。
3. Logic Gates and Truth Tables | 逻辑门与真值表
Basic gates: AND, OR, NOT, NAND, NOR, XOR, XNOR. Truth tables list all input combinations and corresponding outputs.
基本门：与门、或门、非门、与非门、或非门、异或门、同或门。真值表列出所有输入组合及对应输出。
| A | B | AND | OR | NAND | NOR | XOR | XNOR |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
XOR output is 1 when inputs differ; XNOR is its complement. NAND and NOR are universal gates — any circuit can be built using only NAND or only NOR gates.
异或门在输入不同时输出 1；同或门是其互补。与非门和或非门是通用门——任何电路都可以仅用与非门或仅用或非门搭建。
4. Karnaugh Map Simplification | 卡诺图化简
A Karnaugh map (K‑map) re‑arranges truth table values into a grid so that adjacent cells differ by one variable. Group adjacent 1s in powers of two (1,2,4,8...) to obtain minimal sum‑of‑products expressions.
卡诺图将真值表值重新排列成网格，使相邻单元仅有一个变量不同。将相邻的 1 按 2 的幂次（1、2、4、8…）分组，以得到最简与或表达式。
Rules: groups must be rectangular and as large as possible; they can wrap around edges. Each group eliminates variables that change within the group. Overlapping groups are allowed.
规则：分组必须为矩形且尽可能大；可环绕边界。每个分组消除了组内变化的变量。允许分组重叠。
For a 3‑variable map, a group of four 1s removes two literals; a group of two removes one literal. The simplified expression is the OR of the prime implicants.
对于 3 变量卡诺图，四个 1 的分组可消去两个文字；两个 1 的分组消去一个文字。最简表达式是质蕴含项的或运算。
5. Binary Arithmetic: Addition, Subtraction & Overflow | 二进制算术：加减与溢出
+1=0 carry 1. Subtraction is performed by adding the two’s complement of the subtrahend: A – B = A + (–B).
二进制加法法则：0+0=0，0+1=1，1+0=1，1+1=0 进位 1。减法通过加上减数的补码实现：A – B = A + (–B)。
Overflow occurs when the result exceeds the representable range given the bit width. In two’s complement addition, overflow is detected when the carry into the sign bit differs from the carry out of the sign bit. For unsigned numbers, overflow is simply a carry‑out from the most significant bit.
当结果超出给定位宽的表示范围时发生溢出。在补码加法中，当进位进入符号位与离开符号位不同时检测到溢出。对于无符号数，溢出就是最高位的进位输出。
Multiplication can be achieved by repeated shift‑and‑add; division by repeated subtraction or shift‑and‑subtract.
乘法可通过重复移位相加实现；除法可通过重复减法或移位相减实现。
6. Floating‑Point Representation (IEEE 754) | 浮点数表示
A floating‑point number is stored as: Value = (–1)S × (1 + Mantissa) × 2Exponent – Bias. The sign S is 1 bit, Mantissa fraction is normalised with a hidden leading 1, and the Exponent is stored in biased form.
浮点数存储格式为：数值 = (–1)S × (1 + 尾数) × 2阶码 – 偏置。符号 S 占 1 位，尾数小数部分经规格化后隐藏前导 1，阶码以移码形式存储。
In single precision (32 bits): 1 sign, 8 exponent (bias 127), 23 mantissa. Double precision uses 11 exponent bits (bias 1023) and 52 mantissa bits. Special values: exponent all 0s (denormalised, leading bit 0), exponent all 1s (infinity or NaN).
单精度（32 位）：1 位符号，8 位阶码（偏置 127），23 位尾数。双精度使用 11 位阶码（偏置 1023）和 52 位尾数。特殊值：阶码全 0（非规格化，前导位为 0），阶码全 1（无穷大或 NaN）。
Precision limitations cause rounding errors; two floating‑point numbers should not be directly compared for equality.
精度限制导致舍入误差；不应直接对两个浮点数进行相等比较。
7. Big O Notation & Algorithm Efficiency | 大O表示法与算法效率
Big O notation describes the upper bound of an algorithm’s time or space complexity as the input size n grows. Common complexities:
大O表示法描述了随着输入规模 n 增长，算法时间或空间复杂度的上界。常见复杂度：
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing array element |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search |
| O(n log n) | Linearithmic | Merge sort, heap sort |
| O(n²) | Quadratic | Bubble sort, selection sort |
| O(2ⁿ) | Exponential | Recursive Fibonacci |
When evaluating an algorithm, drop constant factors and lower‑order terms; O(3n² + 2n + 5) simplifies to O(n²).
评价算法时，应忽略常数因子和低阶项；O(3n² + 2n + 5) 简化为 O(n²)。
Space complexity follows the same notation, measuring extra memory used besides the input.
空间复杂度采用相同表示法，衡量除输入外额外使用的内存。
8. Searching and Sorting Algorithms | 搜索与排序算法
Linear search examines each element sequentially, O(n) time. Binary search requires sorted data and repeatedly divides the search interval in half, O(log n) time.
线性搜索逐个检查每个元素，时间复杂度 O(n)。二分搜索要求数据有序，并反复将搜索区间减半，时间复杂度 O(log n)。
Bubble sort compares adjacent elements and swaps if out of order, O(n²). Selection sort repeatedly finds the minimum and places it at the front, also O(n²). Insertion sort builds a sorted portion by inserting elements, O(n²) worst case but O(n) best case.
冒泡排序比较相邻元素并在逆序时交换，O(n²)。选择排序反复寻找最小值并将其置于前端，也是 O(n²)。插入排序通过插入元素构建已排序部分，最坏 O(n²)，最好 O(n)。
Merge sort uses divide‑and‑conquer to split and merge sorted halves, O(n log n) in all cases. Quick sort partitions around a pivot, average O(n log n), worst O(n²).
归并排序采用分治法分割并合并已排序的两半，所有情况均为 O(n log n)。快速排序围绕基准进行划分，平均 O(n log n)，最坏 O(n²)。
9. Stacks, Queues, and Trees | 栈、队列和树
Stack follows LIFO (Last‑In‑First‑Out). Operations: push (add), pop (remove). Can be implemented with arrays or linked lists. Used in recursion, expression evaluation, undo functions.
栈遵循后进先出（LIFO）原则。操作：压入（添加）、弹出（移除）。可用数组或链表实现。用于递归、表达式求值、撤销功能。
Queue follows FIFO (First‑In‑First‑Out). Operations: enqueue (add to rear), dequeue (remove from front). Circular queues optimise array usage. Priority queues retrieve based on priority rather than order of arrival.
队列遵循先进先出（FIFO）原则。操作：入队（添加到队尾）、出队（从队首移除）。循环队列优化数组使用。优先级队列根据优先级而不是到达顺序取值。
A binary tree has at most two children per node. A binary search tree (BST) stores left < parent < right, enabling O(log n) average search. Traversals: pre‑order (root‑left‑right), in‑order (left‑root‑right), post‑order (left‑right‑root).
二叉树每个节点最多有两个子节点。二叉搜索树 (BST) 存储左 < 父 < 右，平均搜索时间复杂度 O(log n)。遍历方式：前序（根-左-右）、中序（左-根-右）、后序（左-右-根）。
10. Little Man Computer (LMC) Instruction Set | 小矮人计算机指令集
The LMC is a simplified von Neumann model with 100 memory cells, an accumulator, a program counter, and a simple instruction set. Each instruction is a 3‑digit decimal code: opcode + operand address.
小矮人计算机 (LMC) 是简化的冯·诺依曼模型，拥有 100 个存储单元、累加器、程序计数器和一套简单指令集。每条指令为 3 位十进制代码：操作码 + 操作数地址。
| Mnemonic | Opcode | Description |
|---|---|---|
| ADD | 1xx | 广告 / Sponsored 英文原版 Collins International Lower Secondary Computing 柯林斯国际初… 计算机 备考教辅 · 正版现货 · 与本文同科同级别 查看详情 / View on Taobao参考价 ¥227.0
更多咨询请联系16621398022（同微信） 备考资讯每日更新，关注不错过 考纲变化 · 科目分析 · 学习方法  在微信里长按二维码识别关注 或截图后用「扫一扫 → 相册」选择本图 公众号：tutorhao |