📚 SQA Computing Formulas and Theorems Quick Reference | SQA 计算机公式定理速查手册
This quick reference guide compiles essential formulas, theorems, and conversion methods for SQA Year 11 Computing Science. Each section presents a key topic with clear English explanations followed by Chinese translations, helping bilingual learners grasp the material efficiently. All mathematical expressions use standard Unicode symbols so that they display correctly on any device.
这份速查手册汇集了 SQA 十一年级计算机科学中的核心公式、定理和转换方法。每一节都以清晰的英文解释开头，并配有中文翻译，帮助双语学习者高效掌握知识。所有数学表达式均使用标准 Unicode 符号，确保在任何设备上都能正常显示。
1. Binary and Decimal Conversion | 二进制与十进制转换
To convert a binary number to decimal, multiply each bit by 2 raised to the power of its position (starting from 0 on the right) and sum the results. For example, 1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 11₁₀.
将二进制数转换为十进制时，将每一位数字乘以 2 的对应位权次幂（从右边开始，最低位权为 0），然后求和。例如，1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 11₁₀。
To convert a decimal integer to binary, repeatedly divide by 2 and record the remainders; the binary representation is the sequence of remainders read from bottom to top. For fractional parts, multiply by 2 and record the integer parts.
将十进制整数转换为二进制时，反复除以 2 并记录余数；二进制表示为从下往上读取余数序列。对于小数部分，则不断乘以 2 并记录整数部分。
Decimal = Σ (bitᵢ × 2ⁱ) , i starting from 0 at LSB
十进制 = Σ (位ᵢ × 2ⁱ) , i 从最低有效位的 0 开始
2. Hexadecimal and Binary Conversion | 十六进制与二进制转换
Each hexadecimal digit corresponds exactly to 4 binary digits (a nibble). To convert hex to binary, replace each hex digit with its 4-bit equivalent (0 → 0000, 1 → 0001, …, A → 1010, F → 1111). Conversely, group binary digits in sets of four from the right, and replace each group with the corresponding hex digit.
每个十六进制数字恰好对应 4 个二进制位（一个半字节）。将十六进制转换为二进制时，将每个十六进制数字替换为对应的 4 位二进制（0 → 0000，1 → 0001，…，A → 1010，F → 1111）。反之，从右边开始将二进制数字四个一组分组，然后将每组替换为相应的十六进制数字。
Denary (decimal) to hex conversion is done either via repeated division by 16 (taking remainders as hex digits) or by first converting to binary and then grouping into nibbles.
十进制转十六进制可通过反复除以 16（将余数作为十六进制数字），或先转换为二进制再分组为半字节来实现。
3. Boolean Algebra Basic Laws | 布尔代数基本定律
Boolean algebra operates on variables that can be TRUE (1) or FALSE (0). The basic operations are AND (∧), OR (∨), and NOT (¬ or ‘ ). Several fundamental laws simplify logic expressions.
布尔代数处理的变量只能为真（1）或假（0）。基本运算为与（∧）、或（∨）和非（¬ 或 ‘ ）。以下基本定律可用于化简逻辑表达式。
- Commutative Laws | 交换律: A ∧ B = B ∧ A ; A ∨ B = B ∨ A
- Associative Laws | 结合律: (A ∧ B) ∧ C = A ∧ (B ∧ C) ; (A ∨ B) ∨ C = A ∨ (B ∨ C)
- Distributive Laws | 分配律: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) ; A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
- Identity Laws | 同一律: A ∧ 1 = A ; A ∨ 0 = A
- Annihilator Laws | 零一律: A ∧ 0 = 0 ; A ∨ 1 = 1
- Idempotent Laws | 幂等律: A ∧ A = A ; A ∨ A = A
- Complement Laws | 补余律: A ∧ ¬A = 0 ; A ∨ ¬A = 1
- Double Negation | 双重否定: ¬(¬A) = A
4. De Morgan’s Theorems | 德摩根定理
De Morgan’s theorems are essential for simplifying inverted AND and OR expressions and for converting between NAND/NOR gates. They state:
德摩根定理对于化简取反后的与、或表达式以及转换与非门、或非门至关重要。定理表述为：
¬(A ∧ B) = ¬A ∨ ¬B
¬(A ∨ B) = ¬A ∧ ¬B
In words: the negation of a conjunction is the disjunction of the negations, and the negation of a disjunction is the conjunction of the negations. These are widely used in circuit simplification and logic design.
换句话说：与运算的否定等于各否定的或；或运算的否定等于各否定的与。这两条定理广泛应用于电路简化和逻辑设计中。
5. Logic Gate Truth Tables | 逻辑门真值表
The standard logic gates (AND, OR, NOT, NAND, NOR, XOR, XNOR) have well-defined behaviours. The truth table below summarises their outputs for inputs A and B.
标准逻辑门（与、或、非、与非、或非、异或、同或）具有确定的行为。下表总结了输入 A 和 B 时各门的输出。
| 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 |
The NOT gate simply inverts the input: output = ¬A.
非门简单地将输入取反：输出 = ¬A。
6. Bitmap Image File Size | 位图图像文件大小
The file size of an uncompressed bitmap image depends on the image dimensions, colour depth, and resolution. The basic formula is:
未压缩位图图像的文件大小取决于图像尺寸、颜色深度和分辨率。基本公式为：
File size (bits) = Width (px) × Height (px) × Colour depth (bpp)
文件大小（比特） = 宽度（像素） × 高度（像素） × 颜色深度（位/像素）
To obtain the size in bytes, divide by 8. If the image is saved with metadata or in a compressed format, the actual file size will differ, but this formula gives the raw data size.
要得到以字节为单位的大小，请除以 8。如果图像保存时带有元数据或采用压缩格式，实际文件大小会有所不同，但此公式给出了原始数据量。
7. Sound File Size | 声音文件大小
For uncompressed digital audio, the file size is determined by the sample rate, bit depth, number of channels, and duration. The calculation is:
对于未压缩的数字音频，文件大小取决于采样率、位深度、声道数和时长。计算公式为：
File size (bits) = Sample rate (Hz) × Bit depth × Channels × Duration (s)
文件大小（比特） = 采样率（Hz） × 位深度 × 声道数 × 时长（秒）
For example, a stereo CD-quality recording (44 100 Hz, 16 bits, 2 channels, 60 seconds) requires 44 100 × 16 × 2 × 60 = 84 672 000 bits, or approximately 10.1 MB.
例如，一张立体声 CD 音质的录音（44 100 Hz，16 位，2 声道，60 秒）需要 44 100 × 16 × 2 × 60 = 84 672 000 比特，约 10.1 MB。
8. Text Encoding Sizes | 文本编码大小
Character encoding standards determine how many bits/bytes represent each character. Common systems include:
字符编码标准决定了每个字符用多少比特/字节表示。常见编码包括：
- ASCII: 7 bits per character (often stored as 1 byte with a leading 0).
- Extended ASCII: 8 bits (1 byte) per character.
- UTF‑8: variable length, 1 to 4 bytes per character (ASCII characters remain 1 byte).
- UTF‑16: 2 or 4 bytes per character.
- ASCII：每个字符 7 比特（通常存储为 1 字节，高位填 0）。
- 扩展 ASCII：每个字符 8 比特（1 字节）。
- UTF‑8：变长编码，每个字符 1 到 4 字节（ASCII 字符仍为 1 字节）。
- UTF‑16：每个字符 2 或 4 字节。
To estimate plain text file size: Size (bytes) ≈ Number of characters × Bytes per character (depending on encoding).
估算纯文本文件大小：大小（字节） ≈ 字符数 × 每字符字节数（取决于编码）。
9. Network Transmission Time | 网络传输时间
The time required to transfer data over a network is found by dividing the file size by the effective transmission rate. It’s important to use consistent units (bits or bytes).
通过网络传输数据所需时间等于文件大小除以有效传输速率。使用一致的单位（比特或字节）至关重要。
Time (s) = File size (bits) / Bandwidth (bps)
时间（秒） = 文件大小（比特） / 带宽（比特每秒）
For example, transferring a 100 Mbit file over a 25 Mbps connection takes 100 / 25 = 4 seconds. Remember that protocol overheads may increase the actual transfer time.
例如，以 25 Mbps 的连接传输一个 100 Mbit 的文件需要 100 / 25 = 4 秒。请注意，协议开销可能会增加实际传输时间。
10. Algorithm Efficiency: Time Complexity | 算法效率：时间复杂度
Time complexity describes how the execution time of an algorithm grows with the size of the input (n). Big‑O notation is used to express the upper bound. Common complexities include:
时间复杂度描述了算法执行时间随输入规模（n）增长的趋势。大 O 表示法用于表示上界。常见的复杂度包括：
- O(1) – constant time: execution time does not depend on n.
- O(log n) – logarithmic time: typical for binary search.
- O(n) – linear time: typical for simple loops scanning an array.
- O(n log n) – linearithmic time: typical for efficient sorting (merge sort, quicksort average).
- O(n²) – quadratic time: typical for nested loops, bubble sort, insertion sort.
- O(1) – 常数时间：执行时间不依赖于 n。
- O(log n) – 对数时间：典型如二分查找。
- O(n) – 线性时间：典型如遍历数组的简单循环。
- O(n log n) – 线性对数时间：典型如高效排序（归并排序、快速排序平均情况）。
- O(n²) – 平方时间：典型如嵌套循环、冒泡排序、插入排序。
When analysing algorithms, focus on the dominant term and ignore constant factors.
分析算法时，关注主导项并忽略常数因子。
11. Data Structures: Arrays and Indexing | 数据结构：数组与索引
An array stores elements contiguously in memory. The address of an element is computed by the base address plus an offset. For a one‑dimensional array:
数组在内存中连续存储元素。元素的地址由基地址加上偏移量计算得出。对于一维数组：
Address of A[i] = Base + (i − Lower Bound) × Element size
地址 A[i] = 基地址 + (i − 下界) × 元素大小
In languages with zero‑based indexing (like Python, C++), the lower bound is 0, so the formula simplifies to Base + i × size. For 2D arrays stored in row‑major order:
在采用基于零的索引的语言中（如 Python、C++），下界为 0，因此公式简化为基地址 + i × 元素大小。对于按行主序存储的二维数组：
Address of A[i][j] = Base + ((i × columns) + j) × Element size
地址 A[i][j] = 基地址 + ((i × 列数) + j) × 元素大小
Understanding these calculations is helpful for revising low‑level memory operations and data structure design.
理解这些计算有助于复习底层内存操作和数据结构设计。
12. Comparison of Basic Sorting Algorithms | 基本排序算法比较
The table below summarises the time and space complexity of common sorting algorithms, as well as their stability (whether they preserve the relative order of equal elements).
下表总结了常见排序算法的时间复杂度和空间复杂度，以及它们的稳定性（是否保持相等元素的相对顺序）。
| Algorithm | 算法 | Best | 最佳 | Average | 平均 | Worst | 最差 | Space | 空间 | Stable | 稳定 |
|---|---|---|---|---|---|
| Bubble Sort | 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | 插入排序 | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | No |
| Merge Sort | 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
Bubble and insertion sorts perform well on nearly sorted data. Merge sort guarantees O(n log n) time but requires extra memory, whereas quicksort is often faster in practice despite its O(n²) worst case.
冒泡排序和插入排序在数据接近有序时表现良好。归并排序保证 O(n log n) 时间但需要额外内存，而快速排序尽管最差情况为 O(n²)，但在实践中通常更快。
Published by TutorHao | Computing Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply