📚 Pre-U CIE Computer Science: Quick Reference for Formulae & Theorems | Pre-U CIE 计算机：公式定理速查手册
This quick reference guide gathers the essential formulae, theorems, and key quantitative relationships required for the Cambridge Pre-U Computer Science syllabus (9618). Use it to reinforce your understanding of binary arithmetic, Boolean logic, computer architecture, operating systems, data structures, and networking. Each section pairs an English statement with a Chinese explanation to help bilingual learners master the material with confidence.
本速查手册汇总了剑桥 Pre-U 计算机科学（9618）课程所需的核心公式、定理与关键定量关系。用它来巩固你对二进制运算、布尔逻辑、计算机体系结构、操作系统、数据结构与网络的理解。每个小节均采用英文与中文配对讲解，帮助双语学习者扎实掌握内容。
1. Number Systems & Conversion | 数制与转换
A number in base b has digits from 0 to b−1. The decimal value is the sum of each digit multiplied by b raised to its positional power.
基数为 b 的数使用的数字范围是 0 到 b−1。其十进制值为每位数字乘以 b 的位权次幂之和。
Decimal to binary conversion: repeatedly divide the decimal integer by 2 and record the remainders; read remainders from bottom to top.
十进制转二进制：将十进制整数反复除以 2，记录余数；从下往上读取余数即得二进制。
For fractional parts, multiply by 2, record the integer part, and repeat with the fractional part; read from top to bottom.
对于小数部分，乘以 2，记录整数部分，对新的小数部分重复此过程；从上往下读取整数部分。
Decimal value = ∑ₙ₋₁ᵢ₌₀ dᵢ × bⁱ (for integer) + ∑₋₁ⱼ₌₋ₘ dⱼ × bʲ (for fraction)
n bits can represent 2ⁿ distinct values; unsigned range is 0 to 2ⁿ−1.
n 个比特可以表示 2ⁿ 个不同的值；无符号范围是 0 到 2ⁿ−1。
Hexadecimal uses digits 0–9 and A–F; one hex digit corresponds to 4 bits.
十六进制使用数字 0–9 和字母 A–F；一个十六进制位对应 4 个比特。
2. Binary Arithmetic & Two’s Complement | 二进制运算与补码
Two’s complement represents signed integers: most significant bit (MSB) is the sign bit (0 positive, 1 negative).
二进制补码用于表示有符号整数：最高有效位（MSB）为符号位（0 正，1 负）。
To negate a two’s complement number: invert all bits and add 1.
求二进制补码的相反数：将所有位取反，然后加 1。
−x = (Bitwise NOT x) + 1
Range for n-bit two’s complement: −2ⁿ⁻¹ to 2ⁿ⁻¹−1.
n 位补码的表示范围：−2ⁿ⁻¹ 到 2ⁿ⁻¹−1。
Binary addition follows standard rules; overflow occurs when the carry into the sign bit differs from the carry out of the sign bit.
二进制加法遵循标准规则；当进入符号位的进位与离开符号位的进位不相同时，发生溢出。
Subtraction is performed by adding the two’s complement of the subtrahend: A − B = A + (−B).
减法通过加上减数的补码来实现：A − B = A + (−B)。
3. Floating-Point Representation | 浮点数表示
A binary floating-point number is stored as mantissa × 2ᵉˣᵖᵒⁿᵉⁿᵗ. Mantissa is usually normalised so that its first bit after the sign is different from the sign bit.
二进制浮点数存储为 尾数 × 2ᵉˣᵖᵒⁿᵉⁿᵗ。尾数通常进行规格化，使得符号位之后的第一位与符号位不同。
Normalised form: for positive numbers, mantissa starts with 0.1; for negative numbers, it starts with 1.0 (in two’s complement).
规格化形式：正数的尾数以 0.1 开头；负数（补码）以 1.0 开头。
The exponent is stored in biased (excess) representation to allow negative exponents; for k-bit exponent, bias = 2ᵏ⁻¹−1.
指数使用移码（biased/excess）存储以支持负指数；对于 k 位指数，偏移量 bias = 2ᵏ⁻¹−1。
Stored exponent = true exponent + bias
Precision is limited; the relative error due to rounding is at most 2⁻ᵐ (where m is the number of mantissa bits).
精度有限；由舍入引起的相对误差最大为 2⁻ᵐ（m 为尾数位数）。
Special values: exponent all 0s and mantissa all 0s represents zero; exponent all 1s with mantissa 0 represents infinity; exponent all 1s with non-zero mantissa represents NaN.
特殊值：指数全 0 且尾数全 0 表示零；指数全 1 且尾数 0 表示无穷大；指数全 1 且尾数非 0 表示 NaN。
4. Logic Gates & Boolean Algebra | 逻辑门与布尔代数
Basic gates: AND (output 1 only if all inputs 1), OR (output 1 if any input 1), NOT (inverts input), NAND (complement of AND), NOR (complement of OR), XOR (output 1 if inputs differ).
基本门：与门（只有全部输入为 1 时输出 1），或门（任何输入为 1 则输出 1），非门（取反），与非门（与的非），或非门（或的非），异或门（输入不同时输出 1）。
Boolean identities:
布尔恒等式：
- Commutative: A + B = B + A, A · B = B · A | 交换律
- Associative: (A + B) + C = A + (B + C), (AB)C = A(BC) | 结合律
- Distributive: A(B + C) = AB + AC, A + BC = (A + B)(A + C) | 分配律
- Identity: A + 0 = A, A · 1 = A | 同一律
- Complement: A + A’ = 1, A · A’ = 0 | 互补律
- Idempotent: A + A = A, A · A = A | 幂等律
- Double negation: (A’)’ = A | 双重否定律
- De Morgan’s Theorems: (A + B)’ = A’ · B’, (A · B)’ = A’ + B’ | 德摩根定理
NAND & NOR as universal gates: any Boolean function can be implemented using only NAND gates or only NOR gates.
与非门和或非门为通用门：任何布尔函数都可以仅用与非门或仅用或非门实现。
5. Karnaugh Maps & Simplification | 卡诺图与简化
A Karnaugh map (K-map) is a two-dimensional representation of a truth table, enabling visual minimisation of Boolean expressions. The number of cells equals 2ⁿ, where n is the number of variables.
卡诺图是二维的真值表表示，可以直观地对布尔表达式进行化简。单元格数等于 2ⁿ，n 为变量个数。
Adjacent cells differ by exactly one variable; grouping 1s in powers of 2 (1, 2, 4, 8…) yields simplified product terms. Overlapping and wrap-around allowed.
相邻单元格仅有一位变量不同；将 1 按 2 的幂次（1, 2, 4, 8…）圈组，即可得到最简乘积项。允许重叠和边界环绕。
Prime implicant: the largest possible group of 1-cells. Essential prime implicant: covers at least one minterm not covered by any other prime implicant.
质蕴含项：可能最大的 1-格组。必要质蕴含项：覆盖了至少一个其他质蕴含项无法覆盖的最小项。
The simplified expression is the sum (OR) of the prime implicants needed to cover all 1s.
最简表达式为覆盖所有 1 所需的所有质蕴含项之和（或）。
6. Computer Architecture & Pipeline | 计算机体系结构与流水线
The CPU executes a fetch-decode-execute cycle. Performance is governed by clock speed and cycles per instruction (CPI).
CPU 执行取指-译码-执行周期。性能由时钟频率和每条指令周期数（CPI）决定。
Execution time = Instruction count × CPI × Clock cycle time
Pipelining increases throughput by overlapping the execution of multiple instructions. Ideal speedup equals the number of stages S, but hazards (structural, data, control) limit real speedup.
流水线通过重叠执行多条指令来提高吞吐量。理想加速比等于流水线段数 S，但冒险（结构冒险、数据冒险、控制冒险）会限制实际加速比。
Speedup = (Non-pipelined execution time) / (Pipelined execution time)
In RISC architectures, each instruction typically takes one cycle, enabling pipelining. CISC instructions may take variable cycles.
在 RISC 架构中，每条指令通常在一个周期内完成，有利于流水线。CISC 指令可能占用变化周期。
7. Memory & Cache Performance | 存储器与缓存性能
Memory hierarchy: registers, cache (L1, L2, L3), main memory (RAM), secondary storage. Access time and cost increase with distance from CPU, while capacity decreases.
存储层次：寄存器、缓存（L1, L2, L3）、主存（RAM）、辅存。离 CPU 越远，访问时间越长、成本越低，但容量越大。
Cache hit: data found in cache. Cache miss: data must be fetched from a lower level.
缓存命中：数据在缓存中找到。缓存缺失：必须从更低层取数据。
Average Memory Access Time (AMAT) = Hit time + Miss rate × Miss penalty
Effective access time can be improved by a high hit rate. A cache with 90% hit rate and 10-cycle miss penalty gives AMAT = 1 + 0.1×10 = 2 cycles.
高命中率可改善有效访问时间。一个命中率 90%、缺失代价 10 周期的缓存，AMAT = 1 + 0.1×10 = 2 周期。
Direct-mapped cache: each memory block maps to exactly one cache line. Fully associative: any block can go anywhere. Set-associative is a compromise.
直接映射缓存：每个存储块映射到唯一的缓存行。全相联：任意块可放在任何位置。组相联是折中方案。
8. Operating System – Scheduling | 操作系统-调度
Scheduling algorithms decide the order processes are assigned to the CPU. Common measures: turnaround time, waiting time, response time, throughput.
调度算法决定进程获得 CPU 的顺序。常用衡量指标：周转时间、等待时间、响应时间、吞吐量。
First-Come, First-Served (FCFS): non-preemptive, simplest. Shortest Job First (SJF): provably optimal for average waiting time, but requires knowledge of future CPU bursts.
先来先服务（FCFS）：非抢占式，最简单。最短作业优先（SJF）：在平均等待时间上可证最优，但需预知将来的 CPU 区间长度。
Round Robin (RR): preemptive, assigns a fixed time quantum q. Average turnaround time depends on q. Preemptive SJF (SRTF) reduces wait further.
轮转调度（RR）：抢占式，分配固定的时间片 q。平均周转时间取决于 q。抢占式 SJF（SRTF）进一步减少等待时间。
Multilevel feedback queues use multiple queues with different priorities; processes move between queues based on CPU usage history.
多级反馈队列使用多个不同优先级的队列；进程根据 CPU 使用历史在队列间移动。
9. Operating System – Paging & Segmentation | 操作系统-分页与分段
Paging divides physical memory into fixed-size frames and logical memory into same-sized pages. A page table maps virtual pages to physical frames.
分页将物理内存划分为固定大小的帧，将逻辑内存划分为同样大小的页。页表将虚拟页映射到物理帧。
Physical address = Frame number × Frame size + Offset
Translation Lookaside Buffer (TLB) is a fast, associative memory for page table entries, reducing address translation time.
转换后备缓冲器（TLB）是一种快速相联存储器，用于存放页表项，减少地址转换时间。
Effective access time with TLB: EAT = hit ratio × (TLB time + memory access) + miss ratio × (TLB time + 2 × memory access).
带 TLB 的有效访问时间：EAT = 命中率 ×（TLB 时间 + 内存访问）+ 缺失率 ×（TLB 时间 + 2 × 内存访问）。
Page replacement algorithms: FIFO, Optimal, LRU. The optimal algorithm replaces the page that will not be used for the longest time—impossible to implement but serves as a gold standard.
页面置换算法：FIFO、最优、LRU。最优算法置换在未来最长时间内不会被使用的页——无法实现，但可作为比较基准。
10. Data Structures & Algorithms Complexity | 数据结构与算法复杂度
Time complexity is expressed using Big O notation as the upper bound of growth rate. Space complexity considers additional memory needed.
时间复杂度用大 O 记法表示增长速率的上界。空间复杂度考虑所需的额外内存。
| Data Structure | Search | Insert | Delete |
| Array (unsorted) | O(n) | O(1) (end), O(n) (shift) | O(n) |
| Sorted Array | O(log n) | O(n) | O(n) |
| Linked List | O(n) | O(1) (head/tail) | O(1) (known node) |
| Binary Search Tree | O(log n) avg, O(n) worst | O(log n) avg, O(n) worst | O(log n) avg, O(n) worst |
| Hash Table | O(1) avg | O(1) avg | O(1) avg |
| Stack/Queue | O(n) | O(1) | O(1) |
Sorting algorithms: Merge sort O(n log n), Quick sort O(n log n) average, O(n²) worst; Bubble sort O(n²).
排序算法：归并排序 O(n log n)，快速排序平均 O(n log n)、最差 O(n²)；冒泡排序 O(n²)。
Recursion relation for divide-and-conquer: T(n) = aT(n/b) + f(n) solved by Master Theorem.
分治递归关系：T(n) = aT(n/b) + f(n)，可用主定理求解。
11. Communication & Networks | 通信与网络
Data transmission time over a network depends on bandwidth and propagation delay.
网络数据传输时间取决于带宽和传播时延。
Transmission time = Data size / Bandwidth
Propagation delay = Distance / Propagation speed
Total latency = Transmission time + Propagation delay + Queuing delay + Processing delay.
总延迟 = 传输时间 + 传播时延 + 排队时延 + 处理时延。
Packet switching divides data into packets; each packet may take a different route. Circuit switching establishes a dedicated path.
分组交换将数据分成包；每个包可能走不同路由。电路交换建立专用路径。
IP address (IPv4) occupies 32 bits, often written in dotted decimal. Subnet mask defines the network portion.
IP 地址（IPv4）占用 32 位，常写作点分十进制。子网掩码定义网络部分。
Number of hosts per subnet: 2ʰ−2, where h = number of host bits (subtracting 2 for network and broadcast addresses).
每个子网的主机数：2ʰ−2，其中 h 为主机位数（减 2 用于网络地址和广播地址）。
Checksum and CRC (Cyclic Redundancy Check) are used for error detection. Hamming distance determines error correction capability: to detect d errors, distance ≥ d+1; to correct c errors, distance ≥ 2c+1.
校验和与循环冗余校验（CRC）用于检错。汉明距离决定纠错能力：要检测 d 个错误，距离 ≥ d+1；要纠正 c 个错误，距离 ≥ 2c+1。
12. Database Normalisation | 数据库规范化
Normalisation eliminates data redundancy and prevents update anomalies. A relation is in 1NF if all attributes are atomic (no repeating groups).
规范化消除数据冗余，防止更新异常。若所有属性都是原子的（无重复组），则该关系属于 1NF。
2NF: in 1NF and every non-key attribute is fully functionally dependent on the whole primary key (no partial dependency).
2NF：满足 1NF，且每个非键属性完全函数依赖于整个主键（无部分依赖）。
3NF: in 2NF and no transitive dependency (non-key attribute depends on another non-key attribute).
3NF：满足 2NF，且没有传递依赖（非键属性不依赖于另一个非键属性）。
Boyce-Codd Normal Form (BCNF): for every non-trivial functional dependency X → Y, X is a superkey. Stronger than 3NF.
BCNF（巴斯-科德范式）：对每个非平凡函数依赖 X → Y，X 是超键。比 3NF 更强。
Denormalisation is sometimes used to improve read performance at the cost of redundancy.
为确保读性能，有时会进行反规范化，以冗余为代价。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导