📚 Year 12 CAIE Computer Science Formula & Theorem Quick Reference | Year 12 CAIE 计算机公式定理速查手册
This quick-reference handbook brings together the essential formulas, theorems, and conversion rules required for the CAIE AS Computer Science syllabus (9618). It is designed for fast revision and immediate recall of key quantitative and logical relationships that appear frequently in Year 12 exam papers.
本速查手册汇集了 CAIE AS 计算机科学（9618）课程中必备的公式、定理和转换规则，适合快速复习并即时回忆 Year 12 试卷中常见的量化与逻辑关系。
1. Binary, Denary and Hexadecimal Conversions | 二进制、十进制与十六进制转换
To convert a binary number to denary, multiply each bit by its place value, which is a power of 2. The rightmost bit is 2⁰.
将二进制转换为十进制时，将每一位乘以对应的权值（2 的幂次），最右侧位为 2⁰。
Denary value = bₙ₋₁×2ⁿ⁻¹ + bₙ₋₂×2ⁿ⁻² + … + b₁×2¹ + b₀×2⁰
For hexadecimal, each hex digit corresponds to a 4-bit nibble. The digits A–F represent denary values 10–15.
十六进制中每个十六进制位对应一个 4 位二进制半字节，A–F 表示十进制 10–15。
| Hex | Binary | Denary |
|---|---|---|
| 0 | 0000 | 0 |
| 1 | 0001 | 1 |
| A | 1010 | 10 |
| F | 1111 | 15 |
2. File Size Estimations for Images and Sound | 图像与声音文件大小估算
Uncompressed image file size depends on resolution and colour depth. Sound file size depends on sample rate, bit depth, duration and number of channels.
未压缩的图像文件大小取决于分辨率和色深，声音文件大小取决于采样率、位深、时长和声道数。
Image size (bits) = width (px) × height (px) × colour depth (bpp)
Sound size (bits) = sample rate (Hz) × bit depth × duration (s) × channels
To convert bits to bytes divide by 8; for kibibytes divide by 1024 × 8. Pay attention to examiner instructions on whether prefix multipliers are 1000 or 1024.
位转换为字节需除以 8；转换为 KiB 则除以 1024×8。注意题目中要求的乘数是以 1000 还是 1024 为准。
3. Floating‑Point Representation (Binary) | 浮点数表示（二进制）
CAIE uses a mantissa–exponent model with a specified number of bits for each part. The mantissa is normalised so that the first two bits of the mantissa are different (01 or 10) for a normalised positive/negative number.
CAIE 使用尾数–指数模型，为各部分指定位数。规格化要求尾数的前两位不同（01 或 10），分别表示正数和负数。
Number = mantissa × 2exponent
The exponent is stored in two’s complement form. To find the denary value, convert mantissa and exponent separately, then multiply the mantissa by 2 raised to the exponent.
指数以二进制补码形式存储。求十进制值时，分别转换尾数和指数，再将尾数乘以 2 的指数次幂。
Normalisation maximises precision: shift the mantissa left until the leading bit differs from the bit immediately to its right, and adjust the exponent accordingly by decrementing it on each left shift.
规格化最大化精度：向左移动尾数，直到最高位与其右侧位不同，每左移一位指数减一。
4. Logic Gates, Truth Tables and Boolean Algebra Laws | 逻辑门、真值表与布尔代数定律
The fundamental gates are NOT, AND, OR, NAND, NOR and XOR. The output of each gate follows a fixed truth table.
基本逻辑门有非、与、或、与非、或非和异或门，每种的输出由固定的真值表决定。
| Gate | Boolean Expression | Symbol |
|---|---|---|
| NOT | X = A’ or X = ¬A | ―∘⊳ |
| AND | X = A · B | ―D⊳ |
| OR | X = A + B | ―⊳⊳ |
| NAND | X = (A · B)’ | ―D∘⊳ |
| NOR | X = (A + B)’ | ―⊳∘⊳ |
| XOR | X = A ⊕ B | ―=1⊳ |
Boolean algebra laws simplify logic circuits. Key laws include commutativity, associativity, distributivity, identity, annulment, complement, absorption and De Morgan’s theorems:
布尔代数定律用于化简逻辑电路。核心定律包括交换律、结合律、分配律、同一律、零律、补余律、吸收律以及德摩根定理：
(A + B)’ = A’ · B’ (A · B)’ = A’ + B’
5. Karnaugh Maps (K‑maps) | 卡诺图
A Karnaugh map is a grid used to simplify Boolean expressions visually. For 2 variables the grid is 2×2; for 3 variables it is 2×4 (Gray code order: 00, 01, 11, 10).
卡诺图是一种可视化化简布尔表达式的网格。两个变量用 2×2 网格，三个变量用 2×4 网格（格雷码序列 00, 01, 11, 10）。
Minterms are mapped as 1s. Group adjacent 1s in powers of 2 (1, 2, 4, 8…). Each group gives a product term where variables that change within the group are eliminated.
将最小项映射为 1，将相邻的 1 圈成 2 的幂次大小（1、2、4、8…）。每个圈产生一个乘积项，圈内发生变化的变量被消去。
The simplified expression is the sum of the product terms from all groups. “Don’t care” conditions (X) can be treated as either 0 or 1 to make larger groups.
最简表达式为所有圈对应乘积项之和。无关项（X）可视为 0 或 1，以形成更大的圈。
6. Processor Performance Equations | 处理器性能方程
Processor execution time is calculated using the number of clock cycles and the clock period (or clock rate).
处理器执行时间通过时钟周期数和时钟周期（或时钟频率）计算。
CPU execution time = Clock cycles × Clock cycle time
Clock cycle time = 1 / Clock frequency
For a given program, clock cycles = number of instructions × average CPI (cycles per instruction).
对于某程序，时钟周期数 = 指令数 × 平均 CPI（每指令时钟周期数）。
The MIPS (million instructions per second) metric is sometimes used:
有时使用 MIPS（每秒百万条指令）指标：
MIPS = (Clock frequency (Hz) / CPI) / 10⁶
7. Parity, Checksum and CRC Error Detection | 奇偶校验、校验和与循环冗余校验
Even parity sets the parity bit so that the total number of 1s in the data plus parity bit is even. Odd parity ensures an odd total.
偶校验将校验位设置为使数据与校验位中 1 的总数为偶数；奇校验则为奇数。
Parity bit = (count of 1s in data) mod 2 (for even parity)
A checksum is the sum of data blocks (usually one’s complement of the sum) appended to the message. The receiver adds all blocks; a zero result typically indicates no error.
校验和是数据块之和（通常为和的反码）附加到消息尾部。接收方将所有块相加；结果为零通常表示无错误。
Cyclic Redundancy Check (CRC) treats data as a binary polynomial and divides it by a generator polynomial; the remainder becomes the CRC code. The receiver divides the received message by the same generator; a zero remainder indicates correct transmission.
CRC 将数据视为二进制多项式并除以生成多项式，余数成为 CRC 码。接收方用同一生成多项式除接收到的消息，余数为零表示传输正确。
8. Database Normalisation (1NF, 2NF, 3NF) | 数据库范式（1NF、2NF、3NF）
Normalisation rules remove data redundancy. 1NF requires atomic values and no repeating groups. Each intersection of row and column must hold a single value.
范式规则消除数据冗余。1NF 要求原子值且无重复组，每一行与列的交叉处只能有单一值。
2NF: the table must be in 1NF and every non‑key attribute must be fully functionally dependent on the whole primary key (no partial dependencies if the key is composite).
2NF：表必须符合 1NF，且每个非键属性必须完全函数依赖于整个主键（若主键为复合键，则不能有部分依赖）。
3NF: the table must be in 2NF and there must be no transitive dependencies (a non‑key attribute should not depend on another non‑key attribute).
3NF：表必须符合 2NF，且不存在传递依赖（非键属性不应依赖于另一个非键属性）。
9. Stack, Queue and Linked List Operations | 栈、队列及链表操作
Stacks are LIFO structures. Core operations: push (add item to top), pop (remove and return top item), and peek (inspect top item). Checking for empty/full uses a stack pointer.
栈是 LIFO 结构。核心操作：push（压入栈顶）、pop（弹出并返回栈顶元素）和 peek（查看栈顶）。使用栈指针判断空或满。
Queues are FIFO structures. Enqueue adds an item to the rear; dequeue removes an item from the front. A circular queue reuses array space by wrapping the pointers.
队列是 FIFO 结构。入队将元素加入队尾，出队从队首移除元素。循环队列通过环绕指针重用数组空间。
A linked list consists of nodes, each with a data field and a pointer to the next node. Insertion and deletion of a node involve updating the previous node’s pointer. A doubly linked list also has a pointer to the previous node.
链表由节点组成，每个节点包含数据域和指向下一节点的指针。插入和删除节点需更新前一节点的指针。双向链表还有指向前一节点的指针。
10. Binary Tree Traversals and Algorithm Complexity | 二叉树遍历与算法复杂度
Binary trees can be traversed in pre‑order (root, left, right), in‑order (left, root, right) and post‑order (left, right, root). These are typically implemented recursively.
二叉树可按前序（根、左、右）、中序（左、根、右）和后序（左、右、根）遍历，通常用递归实现。
Big‑O notation expresses the worst‑case time complexity. Common classes on the AS syllabus: O(1) constant, O(log n) binary search, O(n) linear search, O(n log n) efficient sorts, O(n²) bubble/insertion sort.
大O记号表示最坏情况时间复杂度。AS 课程常见类型：O(1) 常数、O(log n) 二分查找、O(n) 线性搜索、O(n log n) 高效排序、O(n²) 冒泡/插入排序。
Linear search: n comparisons in worst case; Binary search: log₂(n) comparisons
11. Data Transmission Calculations | 数据传输计算
Transmission time for a file is given by file size (bits) divided by the bit rate (bps). Propagation delay depends on distance and signal speed.
文件传输时间 = 文件大小（位）÷ 比特率（bps）。传播延迟取决于距离和信号速度。
Transmission time = (file size in bits) / (bandwidth in bps)
Propagation delay = distance / propagation speed
Serial transmission sends one bit at a time; parallel sends multiple bits simultaneously (faster but suffers from skew). The total number of bits in a packet includes header, payload and trailer.
串行传输一次发送一个位；并行同时发送多个位（更快但存在偏移问题）。数据包的总位数包括头部、有效载荷和尾部。
12. Assembly Language Addressing Modes | 汇编语言寻址模式
Addressing modes specify how the operand of an instruction is accessed. Immediate addressing uses a constant value directly. Direct addressing gives the memory address of the operand. Indirect addressing uses a register that contains the address of the operand.
寻址模式指定指令操作数的访问方式。立即寻址直接使用常数值；直接寻址给出操作数的内存地址；间接寻址使用一个包含操作数地址的寄存器。
Indexed addressing adds a constant (index) to a base register to form the effective address, useful for accessing array elements. Relative addressing adds an offset to the program counter for branch instructions.
变址寻址将常数（索引）加到基址寄存器以形成有效地址，适用于数组元素访问。相对寻址将偏移量加到程序计数器用于跳转指令。
Published by TutorHao | Computer Science Revision Series | aleveler.com
Find Cambridge Computer Science Textbooks on eBay UK
New, used and second-hand copies of textbooks and revision guides are often much cheaper than retail — check current listings and prices before you buy.
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导