A-Level Computer Science

The three number systems 数制 you must use:

• denary 十进制 (decimal, base 10) — uses digits 0–9. Place values are powers of ten.
• binary 二进制 (base 2) — uses 0 and 1. Place values are powers of two. Every byte 字节 is 8 bits 位.
• hexadecimal 十六进制 (base 16) — uses 0–9 then A–F for 10–15. Each hex digit 数位 stands for exactly 4 bits.

An abacus represents numbers by place value — the same idea behind decimal, binary and hexadecimal

Conversions

Denary → binary: keep dividing by 2 and record the remainders, read bottom-up. Or subtract the largest place value 位值 (power of 2) that fits.

Example: $558_{10}$: $558 = 512 + 32 + 8 + 4 + 2 = 2^{9} + 2^{5} + 2^{3} + 2^{2} + 2^{1}$. In 12 bits: 0010 0010 1110.

Binary → hex: group the bits into nibbles 半字节 (4 bits) from the right and convert each. 0010 0010 1110 → 2 2 E → 22E.

Hex → binary: replace each hex digit with its 4-bit pattern. Hex → denary: multiply each digit by its place value. 22E $= 2 \times 256 + 2 \times 16 + 14 = 558$.

Binary vs decimal prefixes

Decimal prefixes (SI, hard-drive sizes, network speeds): kilo $= 10^{3}$, mega $= 10^{6}$, giga $= 10^{9}$, tera $= 10^{12}$.

Binary prefixes (for memory sizes, where powers of 2 are natural): kibi (Ki) $= 2^{10} = 1024$, mebi (Mi) $= 2^{20}$, gibi (Gi) $= 2^{30}$, tebi (Ti) $= 2^{40}$.

So a tebibyte (TiB) $= 2^{40}$ bytes is slightly more than a terabyte (TB) $= 10^{12}$ bytes. A "1 TB" drive holds $10^{12}$ bytes, but an operating system that reports in TiB shows a smaller number.

Binary addition

Add column by column from the right, carrying as in denary:

Overflow 溢出 happens when the result needs more bits than the register 寄存器 can hold — the carry-out of the leftmost column is the overflow bit.

Binary subtraction

The usual way is two's complement 补码 addition: to do $A - B$, form the two's complement of $B$ (invert every bit and add 1), then add, and discard any final carry-out.

To subtract $00011110$ from $01100100$ (unsigned 8-bit):

• two's complement of $00011110$: invert → $11100001$, add 1 → $11100010$.
• add to $01100100$: result $1\,01000110$ (9 bits) — discard the leading 1 → $01000110 = 70_{10}$. Check: $100 - 30 = 70$. ✓

Two's complement signed integers

In an $n$-bit two's-complement number:

• the most significant bit 最高有效位 (MSB) is the sign bit 符号位: 0 = positive, 1 = negative.
• to read a negative number: invert every bit, add 1, then negate.

So $11100010$ is negative; invert → $00011101$, add 1 → $00011110 = 30$, so it is $-30$. This is a signed integer 有符号整数 (unlike an unsigned 无符号 one). The range for $n$ bits is $-2^{n-1}$ to $+2^{n-1} - 1$; for 8 bits, $-128$ ($10000000$) to $+127$ ($01111111$).

Overflow in signed arithmetic happens when the true result falls outside this range — spotted when the sign bit flips wrongly (two positives giving a negative, or two negatives giving a positive).

In BCD 二进码十进数, each denary digit is written as its own 4-bit pattern. The number $93$ is 1001 0011 in BCD — not binary 93 ($01011101$). Each nibble uses only 0–9; patterns $1010$–$1111$ are invalid.

BCD reading: 0010 0111 0101 → 2, 7, 5 → 275.

Use: calculators, digital clocks, and devices that show denary digits — each digit drives a 7-segment display 七段显示器. Currency code often uses BCD to avoid the rounding errors of converting fractions like 0.1 to binary.

A seven-segment display shows one denary digit, often driven by BCD

Hex is a compact way to write binary (1 hex digit = 4 bits):

• memory addresses 内存地址 in low-level programming — 0x7FFE.
• colour values in HTML/CSS — #FF8800.
• MAC addresses — AC:DE:48:00:11:22.

Hex does not change the stored data — it just makes binary easier for humans.

Computers store text as numbers; each character has a numeric code point 码点 set by a character set 字符集.

ASCII

• ASCII uses 7 bits — 128 code points. Basic Latin letters, digits, punctuation, and control codes.
• Extended ASCII uses 8 bits — 256 code points; the lower 128 match ASCII, the upper 128 vary by region.

Unicode

• Unicode is a universal character set covering almost every script, plus symbols and emoji.
• common encodings 编码: UTF-8 (1–4 bytes, ASCII-compatible), UTF-16 (2 or 4 bytes), UTF-32 (fixed 4 bytes).

Why Unicode beats ASCII

• it represents far more characters (every script, emoji); ASCII covers only basic English.
• files are portable with no code-page confusion, and allow multilingual text in one document.
• trade-off: Unicode files are usually larger for English-only text.

A bitmap 位图 image stores the colour of every pixel 像素 in a grid.

• resolution 分辨率: width × height in pixels (e.g. 1920 × 1080).
• colour depth 颜色深度 (bit depth 位深度): bits per pixel. 1 bit → black/white; 8 bits → 256 colours; 24 bits → 16.7 million ("true colour").

The same image stored at three resolutions, from high (A) to low (C): fewer, larger pixels mean less detail

File size

Divide by 8 for bytes, by 1024 for KiB, etc. Example: a $3000 \times 2000$ image at 24 bpp is $3000 \times 2000 \times 24 = 1.44 \times 10^{8}$ bits $\approx 17.2\ \text{MiB}$.

Changing settings

• lower resolution → smaller file, less detail (looks blocky when enlarged).
• lower colour depth → smaller file, but smooth shades show banding.
• higher of either → larger file, better quality.

A vector graphic 矢量图形 stores the instructions to draw the image — geometric primitives 图元 (lines, curves, polygons, circles) with attributes like colour, fill, width and position. To show it, the program renders 渲染 the instructions at any resolution needed.

A vector image is built from labelled geometric shapes, each with attributes

Bitmap vs vector

Vector advantage: it scales without losing quality — a vector logo stays sharp at any size, while a bitmap blurs when enlarged. Vector disadvantage: it cannot describe arbitrary pixel detail (photographs).

A continuous analogue sound wave is turned into digital form by sampling 采样:

• sampling rate 采样率 — samples per second (Hz). CD quality is $44.1\ \text{kHz}$.
• sample resolution 采样分辨率 (bit depth) — bits per sample's amplitude 振幅. CD quality is 16 bits.

Sampling a sound wave: its amplitude is read at each time interval

File size

A 10-second stereo CD clip: $44100 \times 16 \times 10 \times 2 \approx 1.8\ \text{MiB}$.

Changing settings

• higher sampling rate → captures higher pitches, larger file.
• higher sample resolution → finer amplitude steps, less quantisation 量化 noise, larger file.
• lower of either → smaller file, clear quality loss.

(The sampling rate must be at least twice the highest frequency you want to keep.)

Compression 压缩 reduces file size, saving storage and transmission bandwidth 带宽. Two kinds:

• lossless 无损 — the original data is recovered exactly (text, programs, ZIP/PNG).
• lossy 有损 — some detail is dropped for much smaller files (JPEG, MP3, video).

When to use which

• lossless for documents, source code, medical images — anything needing exact data.
• lossy for streaming media. Real-time video streaming uses lossy compression because it must send huge amounts of data in real time over limited bandwidth; lossless would not shrink it enough. Raw HD video is gigabytes per minute, so without compression the picture would keep freezing.

Lossless methods

• run-length encoding 行程编码 (RLE): store "the next $n$ values are $x$" instead of repeating $x$. Great for flat areas; useless for noisy data.
• dictionary methods 字典编码 (ZIP, PNG): replace repeated byte sequences with a short reference. Good for text and code.
• Huffman coding 霍夫曼编码: give short codes to common symbols and long codes to rare ones, bringing the average code length near the data's entropy 熵.

Run-length encoding of the letter F in an $8\times8$ black-and-white grid

Lossy methods

• images (JPEG): drop fine detail and colour differences the eye barely sees.
• sound (MP3, AAC): drop pitches we hear less well, and quiet sounds hidden by louder ones.
• video combines spatial 空间 compression (within each frame, like JPEG) with temporal 时间 compression (most frames store only the differences from the previous frame).

Compression methods: lossless versus lossy, with common examples

A network 网络 is a set of computing devices connected so they can communicate and share resources. Benefits:

• sharing resources (printers, file servers, internet) — cheaper than equipping each computer.
• sharing data — many users access the same files.
• central management — install software, manage users and back up once on a server.
• communication — email, video calls, messaging.
• remote access — work from anywhere.

A local area network 局域网 (LAN) covers a small area — a home, office or school, usually owned by the organisation, with high data rates and low latency 延迟.

A wide area network 广域网 (WAN) covers a large area — a city, country, or the world (the internet is the largest WAN). It uses telecom-company infrastructure, with lower data rates and higher latency. A WAN connects LANs together.

A wide-area network links many systems across a large area

Client-server

• powerful machines act as servers 服务器, providing services (files, web pages, email).
• other machines are clients 客户端 that request services.
• central and easy to manage, but the server is a single point of failure unless backed up.

In a client-server network, clients request services from a central server

Peer-to-peer (P2P)

• all machines are equal peers; each can be both client and server (peer-to-peer 对等网络).
• resources are spread across the peers — no central server. Robust to one failure, but harder to keep secure and consistent.

In a peer-to-peer network, every node is both client and server

A thin client 瘦客户端 does little processing locally and relies on a powerful server (web terminals, remote desktops). A thick client 胖客户端 has strong local processing and storage and runs full applications itself (a normal desktop PC).

The topology 拓扑 is how the nodes and links are arranged.

• bus 总线 — all devices on one shared cable. Cheap; the whole LAN fails if the bus fails; performance drops as more devices share the bandwidth 带宽.
• star 星形 — every device connects to a central switch. One device failing does not affect others; the switch failing brings all down. Most common today.
• mesh 网状 — every device links directly to others, with many paths. Very fault-tolerant 容错 (traffic reroutes) but needs lots of cabling.
• hybrid — a mix (a star in each office, mesh links between offices).

Bus topology: all devices share one cable with a terminator at each end

Star topology: every device connects to a central hub or switch

Mesh topology: every device links directly to the others

Hybrid topology: star clusters joined by a central bus

Cloud computing 云计算 delivers computing services (servers, storage, software) over the internet, hosted by a third party. Benefits: scalability 可扩展性 (pay for what you need), lower cost, access from anywhere, and reliable redundant data centres. Drawbacks: needs internet, your data is held by a third party, and possible vendor lock-in.

• wired (Ethernet 以太网 over twisted-pair 双绞线 or fibre-optic 光纤): higher speed, lower latency, fewer errors, more secure.
• wireless (Wi-Fi, Bluetooth, cellular): no cables, devices can move, but slower, prone to interference and eavesdropping.

For the same generation, wired wins on speed and reliability; wireless wins on convenience.

• network interface card 网络接口卡 (NIC) — lets a device send and receive on the network; has a unique MAC address MAC地址 (a 48-bit hardware address).
• switch 交换机 — forwards Ethernet frames only to the port for the destination MAC address.
• hub 集线器 — a simpler device that copies traffic to all ports (now obsolete).
• wireless access point 无线接入点 (WAP) — lets wireless clients join a wired LAN.
• cabling — twisted-pair for short runs; fibre-optic for longer, faster runs.

A network switch: each device's cable plugs into one of its ports

An RJ-45 plug on a twisted-pair Ethernet cable

A switch sends each frame only to the port for its destination

A router 路由器 connects different networks and forwards data between them — usually at the boundary of a LAN and the internet. It does:

• forwarding — reads each packet 数据包's destination IP address IP地址 and sends it out the right port, using a routing table 路由表.
• network address translation 网络地址转换 (NAT) — lets many private LAN addresses share one public IP.
• DHCP 动态主机配置协议 — hands out private IP addresses to LAN devices.
• firewall 防火墙 — blocks unwanted incoming traffic.

A router connects a LAN to the internet or another network

Ethernet is the main wired LAN technology. On shared media a collision 冲突 can happen when two devices send at once. The protocol is CSMA/CD 载波侦听多路访问 (Carrier Sense Multiple Access with Collision Detection):

1. carrier sense — listen before sending; wait if the cable is busy.
2. multiple access — many devices share the medium.
3. collision detection — keep listening while sending; a clash is a collision.
4. on a collision, both stop, send a brief "jam" signal, then wait a random backoff time before retrying.

Modern switched Ethernet uses full-duplex 全双工 point-to-point links, so collisions no longer happen.

The CSMA/CD process for handling collisions on shared media

Bit streaming 流式传输 sends multimedia as a continuous stream that the receiver plays as it arrives, instead of downloading the whole file first.

• real-time (live): captured and streamed as it happens (live sport, video calls). You cannot rewind; low latency is vital.
• on-demand: pre-recorded on a server (YouTube, Netflix). You can pause and rewind; the server can buffer 缓冲 ahead.

Real-time streaming samples/captures the source, encodes it into a compression 压缩-reduced stream, sends it in packets, and the receiver buffers a little then plays in real time, dropping late packets. Lossy 有损 compression is used because moving pictures hide small losses and the data must fit the bandwidth.

Data streams from the server into a buffer before the media player reads it

The internet 互联网 is a global network of networks using a common protocol 协议 suite (TCP/IP). The World Wide Web 万维网 (WWW) is a service that runs over it: hyperlinked documents identified by URLs, viewed in browsers via HTTP/HTTPS. Email and file transfer are other internet services that are not part of the WWW.

An IP address uniquely identifies a device.

• IPv4 — 32-bit, four denary numbers 0–255 (192.168.1.10); about $4.3 \times 10^{9}$ addresses (now exhausted).
• IPv6 — 128-bit, eight groups of four hex digits; about $3.4 \times 10^{38}$ addresses.

Subnetting

A network can be split into subnets 子网. The IP address splits into a network part and a host part, given by a subnet mask 子网掩码 (e.g. 255.255.255.0 = first 24 bits are network). Subnetting improves management, cuts broadcast traffic, and improves security.

Splitting a network into subnets, one netID per department

Public vs private addresses

• private addresses are used within a LAN and are not routable on the internet (e.g. 192.168.0.0/16).
• public addresses are globally unique and routable, assigned by an ISP 互联网服务提供商.

Devices behind NAT with private addresses are not directly reachable from the internet, giving some protection.

Static vs dynamic

• static — fixed; used for servers that must be found at a known address.
• dynamic — assigned by DHCP and may change; easier for client devices and uses a limited address pool efficiently.

A URL 统一资源定位符 locates a resource on the WWW:

https://www.example.com/about/contact.html
protocol     domain name        path

• protocol: http, https, etc.
• domain name 域名: a readable server address.
• path: the resource on that server.

The Domain Name System 域名系统 (DNS) is a distributed set of servers that turns domain names into IP addresses. When you type a URL, the browser asks a DNS resolver for the IP, which queries DNS servers (root → top-level → authoritative) until it finds it; the browser then connects to that IP and requests the path. DNS saves humans from memorising IP addresses and lets a site change server without changing its name.

How DNS finds a website's IP address before the browser connects

A general-purpose computer has four building blocks:

• input devices 输入设备 — get data in (keyboard, mouse, microphone, scanner, sensors).
• output devices 输出设备 — give results out (monitor, speakers, printer, actuators).
• primary memory 主存储器 — fast memory the processor 处理器 (CPU) reaches directly (RAM and ROM). Holds the running program and its data.
• secondary storage 辅助存储器 — slower, larger, keeps programs and data when not in use (hard disk, SSD, optical disc, USB stick).

A keyboard: a common input device for typing text and commands

A mouse: a pointing input device

A flatbed scanner: an input device that turns a paper page into a digital image

A monitor: a common output device that displays the screen image

An embedded system 嵌入式系统 is a computer built into another device to do one fixed job (washing machine, microwave, car engine unit, thermostat).

• benefits: optimised for one task (low power, small, cheap); reliable; fast to start; cheap in volume.
• drawbacks: limited to its one task; hard to update (its firmware 固件 may need special tools); often not repairable; sometimes weak security.

Laser printer

A laser printer 激光打印机 scans the page image onto a charged photosensitive drum 感光鼓. Toner 墨粉 sticks to the charged areas, transfers to the paper, and is melted on by a fuser. Fast, sharp, high-volume.

A laser printer: fast, sharp printing using a charged drum and toner

3D printer

A 3D printer 3D打印机 builds an object layer by layer: FDM melts plastic filament through a nozzle; stereolithography cures liquid resin with a UV laser. Used for prototypes and custom medical parts.

An FDM 3D printer builds an object layer by layer by melting plastic filament

Microphone and speakers

A microphone 麦克风 turns sound into an electrical signal (a diaphragm vibrates, changing capacitor 电容器 charge or coil position); the signal is digitised by an analogue-to-digital converter 模数转换器 (ADC). A speaker does the reverse — a varying signal drives a coil in a magnetic field, moving a cone to make sound.

A microphone turns sound into an electrical signal

Inside a microphone: sound vibrates the diaphragm and coil to produce a current

Inside a loudspeaker: a varying current in the coil moves the cone to make sound

Magnetic hard disk (HDD)

A hard disk 硬盘 stores data on spinning platters coated with magnetic material. Each platter has tracks 磁道 divided into sectors 扇区. A read/write head 读写头 floats just above and magnetises tiny regions (write) or senses them (read). Cheap per gigabyte, but slower than SSDs and has moving parts.

An opened hard disk: the actuator arm carries the read/write head over a platter

Tracks and sectors on a hard disk platter

Solid-state (flash) memory

A solid-state drive 固态硬盘 stores data as charge in transistors 晶体管, with no moving parts. Faster random access than HDDs, tougher, lower power, but dearer per gigabyte; each cell wears out after many writes.

Inside an SSD: data is stored in flash memory chips, with no moving parts (compare the hard disk above)

Optical disc

A laser detects reflections from tiny pits on an optical disc 光盘 (CD, DVD, Blu-ray). Writing uses a stronger laser to change the surface's reflectivity.

An optical disc drive: a laser reads tiny pits on a CD, DVD or Blu-ray disc

Touchscreen

A touchscreen 触摸屏 senses contact. Resistive 电阻式: two conductive layers pressed together; works with anything but is less accurate. Capacitive 电容式: a finger disturbs a charge field; accurate, multi-touch, used in phones.

A touchscreen senses where a finger touches the glass

Virtual reality headset

A virtual reality 虚拟现实 (VR) headset has two small displays (one per eye) and motion sensors (accelerometer 加速度计, gyroscope 陀螺仪) that track head movement so the scene shifts as you look around.

A virtual reality headset: two small displays and motion sensors track the head

A buffer 缓冲 is memory that holds data temporarily while it moves between devices of different speeds. Example: the CPU writes a document to a printer buffer quickly, then is free to do other work while the printer prints from the buffer at its own pace. Buffers stop the fast device waiting for the slow one (also used in streaming, the keyboard, and disk access).

• RAM 随机存取存储器 (Random Access Memory) — volatile 易失性 (loses data without power). Holds the OS, running programs and their data; read and written constantly.
• ROM 只读存储器 (Read-Only Memory) — non-volatile 非易失性 (keeps data without power). Usually written once; holds firmware needed at start-up (the BIOS / boot loader).

ROM starts the system; RAM then holds the active work.

A RAM module (DIMM) plugs into the motherboard as the computer's fast main memory

• SRAM 静态RAM stores each bit in a flip-flop 触发器 of several transistors. Fast, but expensive and not dense. Used for CPU cache 高速缓存.
• DRAM 动态RAM stores each bit as charge on a tiny capacitor. Cheaper and denser but slower, and must be refreshed 刷新 (rewritten) thousands of times a second. Used for main memory.

Use SRAM for small fast memory (cache); DRAM for large main memory.

ROM variants you can program after manufacture:

• PROM — written once (fuses burned by a programmer); cannot be changed.
• EPROM — erased by strong UV light through a window, then rewritten (whole chip at once).
• EEPROM — erased and rewritten electrically, a byte at a time, in circuit. Flash memory is a derivative optimised for block erase.

Both read sensors; the difference is what they do next.

• monitoring 监控 — collects and reports data but takes no action (a weather station logging readings).
• control system 控制系统 — uses sensor data to decide and act through actuators, usually in a feedback loop (a thermostat turning a boiler on/off).

Monitoring reports data; a control system acts through a feedback loop

Sensors and actuators

A sensor 传感器 turns a physical quantity into a signal: temperature (a thermistor 热敏电阻 or thermocouple), pressure (strain gauge), infra-red, sound. Analogue signals need an ADC first. An actuator 执行器 does the reverse — turns a signal into an action (a motor, valve, heater, buzzer).

A thermistor: a temperature sensor whose resistance changes with heat

A small electric motor: an actuator that turns a signal into movement

Feedback

In a control system the actuator changes the environment, which the sensors then re-measure — a feedback 反馈 loop. Without feedback the system cannot correct itself or know when to stop (a thermostat with no temperature feedback would heat forever).

A logic gate 逻辑门 is a small circuit that does one Boolean 布尔 operation. Inputs and outputs are 0 (false, low) or 1 (true, high). Know the symbol, function and truth table 真值表 for each gate.

The symbols for the six logic gates

NOT (inverter)

AND — output 1 only if all inputs are 1

OR — output 1 if at least one input is 1

NAND (NOT AND) — output 0 only when all inputs are 1

NOR (NOT OR) — output 1 only when all inputs are 0

XOR (Exclusive OR) — output 1 if the inputs are different

A logic circuit 逻辑电路 is a network of gates that carries out a Boolean expression. You should be able to move between a problem statement, a logic expression, a truth table, and a circuit diagram.

From expression to circuit

Draw one gate per operator and wire them up. For $X = (A \text{ AND } B) \text{ OR } (\text{NOT } C)$: a NOT gate on $C$, an AND gate on $A$ and $B$, then an OR gate on the two results.

Gates wired together to carry out a Boolean expression

From circuit to expression

Work forwards from the inputs, labelling each gate's output, until you reach the final output.

From circuit to truth table

For $n$ inputs there are $2^{n}$ rows. List every input combination; for each, work out the internal gates then the output.

From truth table to expression (sum of products)

For each row that outputs 1, write an AND of the inputs (with NOT on any input that is 0 in that row); OR these together. Example: a table that is 1 only on $(A=0,B=1)$ and $(A=1,B=0)$ gives $\overline{A}B + A\overline{B}$, which is $A \text{ XOR } B$.

From a problem statement

Turn the English into a Boolean expression first: "A and B" → A AND B; "A or B or both" → A OR B; "exactly one of A and B" → A XOR B; "neither A nor B" → A NOR B; "not both" → A NAND B.

The Von Neumann architecture 冯·诺依曼体系结构 underlies almost every general-purpose computer:

• a single memory holds both program instructions and data (the stored program 存储程序 idea).
• a processor 处理器 (CPU) fetches instructions from memory and runs them one at a time.
• instructions run in order unless a branch changes the flow.

The stored-program idea is what makes a computer flexible: change the program and you change what it does, with no rewiring.

All of these parts sit inside one small chip. The diagram later in this section shows how they connect; the photo below shows the real thing.

A modern CPU: the whole processor is one small chip (here seen from below, showing the contacts)

The matching CPU socket on the motherboard: the chip's contacts press onto these pins

Arithmetic and Logic Unit (ALU)

The ALU 算术逻辑单元 does the arithmetic (add, subtract, …) and logic (AND, OR, comparisons). It takes operands from registers 寄存器 and puts results back in a register.

Control Unit (CU)

The control unit 控制单元 decodes each instruction and sends the control signals to carry it out — opening data paths, telling the ALU what to do, and controlling memory reads and writes.

System clock

The clock sends a steady stream of pulses that keep the CPU in step. Each instruction takes a fixed number of cycles, and the clock speed 时钟频率 (e.g. 3.8 GHz) is one factor in performance.

Registers

Registers are tiny, very fast stores inside the CPU. Special-purpose ones each have a fixed job in the cycle:

• Program Counter 程序计数器 (PC) — the address of the next instruction.
• Memory Address Register 内存地址寄存器 (MAR) — the address being read or written.
• Memory Data Register 内存数据寄存器 (MDR) — the data going to or from memory.
• Current Instruction Register 当前指令寄存器 (CIR) — the instruction being decoded.
• Accumulator 累加器 (ACC) — the value the ALU is working on.
• Status Register 状态寄存器 — holds flags 标志 (carry, zero, negative, overflow) used by branches.
• Index Register 变址寄存器 — an offset used in indexed addressing.

General-purpose registers 通用寄存器 are used by the programmer for temporary values during a calculation.

The Von Neumann CPU: registers, control unit and ALU linked by buses

Three internal buses 总线 (sets of parallel wires) connect the parts:

• address bus 地址总线 — carries the memory address. One-way (CPU → memory).
• data bus 数据总线 — carries the data. Two-way.
• control bus 控制总线 — carries control signals (read, write, interrupt). Two-way.

An $n$-bit address bus can reach $2^{n}$ memory locations. The data-bus width sets how many bits move per access (often the word size).

The three system buses connecting the CPU, memory and input/output

• clock speed — more cycles per second.
• number of cores 核心 — a multi-core CPU runs several threads at once.
• word size 字长 — a 64-bit CPU handles 64-bit chunks per cycle and can address far more memory than a 32-bit one.
• amount of RAM 随机存取存储器 — more RAM holds more of the working set; too little forces the OS to page 分页 to disk.
• cache 高速缓存 size — more cache cuts average memory access time.
• secondary storage 辅助存储器 type — an SSD loads programs far faster than an HDD.
• bus width and speed — wider/faster buses move data more quickly.

Match the specs to the workload: a quad-core beats a dual-core on parallel work, but higher per-core speed wins on single-threaded work.

A port 端口 is a physical socket for connecting a peripheral 外围设备:

• USB — general-purpose (keyboards, drives, phones).
• HDMI — digital video and audio to a screen.
• Ethernet (RJ-45) — wired LAN. Audio jacks — headphones/microphone.

Different ports use different signals, so an HDMI cable will not fit a USB socket. USB-C is unusual in carrying video, data and power.

The CPU repeats the fetch-execute cycle 取指-执行周期, one run per machine instruction.

Fetch

1. the PC's address is copied to the MAR.
2. the PC is incremented to point to the next instruction.
3. a read signal goes over the control bus.
4. memory puts the instruction on the data bus.
5. it is copied into the MDR, then into the CIR.

Decode

The CU decodes the instruction in the CIR — what operation, and which operands or addresses.

Execute

The CU carries it out: arithmetic/logic goes to the ALU (result to the ACC); a load/store moves data between memory and a register; a branch changes the PC. Then the cycle repeats.

The fetch-execute cycle, with a check for interrupts each time

An interrupt 中断 is a signal that pauses the normal cycle so the CPU can handle an urgent event (a key press, a packet arriving, a hardware fault, division by zero, the OS timer).

Handling one:

1. finish the current instruction.
2. save the state (PC and registers).
3. load the address of the interrupt service routine 中断服务程序 (ISR) into the PC and run it.
4. the ISR handles the event.
5. restore the saved state and carry on.

Interrupts let the system respond promptly without the CPU constantly checking devices, and are how the OS multitasks.

How an interrupt fits into the fetch-execute cycle

The CPU actually runs machine code 机器码 — bit patterns, specific to one architecture. Assembly language 汇编语言 is a readable form, with one instruction per machine instruction, written using mnemonics 助记符 like LDD, ADD, JMP. An assembler 汇编器 translates it to machine code.

Two-pass assembler

A two-pass assembler reads the source twice:

• pass 1 builds a symbol table 符号表: each time a label 标签 (like LOOP:) appears, record its address; no code yet.
• pass 2 generates code: translate each instruction, and when one refers to a label (like JMP LOOP), look up its address in the symbol table.

Two passes handle forward references 前向引用 (a jump to a label defined later).

Example instruction set

Cambridge uses a small generic set: data movement (LDD, LDM, LDI, LDX, STO, MOV), arithmetic (ADD, SUB, INC, DEC), logic/bit (AND, OR, XOR, LSL, LSR), compare and branch (CMP, JMP, JPE, JPN), I/O (IN, OUT), and END. The exact mnemonics are given in the paper's reference table.

The addressing mode 寻址方式 says how the CPU finds the operand:

• immediate addressing 立即寻址 — the operand is the value in the instruction. LDM #10 loads 10.
• direct addressing 直接寻址 — the instruction holds an address; the operand is the value there. LDD 200.
• indirect addressing 间接寻址 — the instruction holds an address that holds another address, which is the data. LDI 200.
• indexed addressing 变址寻址 — effective address is address + index register; used for arrays. LDX 100 with IR = 5 reads address 105.
• relative addressing 相对寻址 — the address is relative to the PC.

To trace it: make a table with columns for the PC, ACC, index register, each variable and any flags. Step through the instructions, updating the table after each; follow branches when they change the PC; stop at END. A common pattern is a loop over an array using indexed addressing.

A logical shift 逻辑移位 moves all the bits left or right by some places, filling new positions with 0.

• left shift by 1 (LSL #1) — bits move left, a 0 enters on the right; for an unsigned number this is × 2.
• right shift by 1 (LSR #1) — bits move right, a 0 enters on the left; for an unsigned number this is integer ÷ 2.

Shifting by $n$ places multiplies or divides by $2^{n}$. Example: 00001011 (11) LSL #1 → 00010110 (22).

An arithmetic right shift keeps the sign bit so a negative signed number stays negative.

Bit manipulation for monitoring/control

Embedded devices often use one bit 位 of a register per signal (e.g. bit $n$ = LED $n$). Using a mask 掩码:

• set bit $n$: R = R OR a mask with bit $n$ set.
• clear bit $n$: R = R AND a mask with bit $n$ clear and the rest set.
• toggle bit $n$: R = R XOR a mask with bit $n$ set.
• test bit $n$: R AND the mask, then check if the result is non-zero.

Bit manipulation is fast, uses little memory, and lets one byte hold up to 8 on/off states.

Why a computer needs an OS

Hardware on its own can only fetch and run instructions — it knows nothing about files, programs, networks or users. The operating system 操作系统 (OS) is the software layer that:

• manages the hardware (processor 处理器, memory, I/O, storage) for the running programs.
• provides services (file system, network, user accounts) through a clear interface, so programs need not talk to the hardware directly.
• provides a user interface (command line, GUI, touch).
• lets several programs share the hardware safely — each gets fair CPU time and is kept out of the others' memory.

Without an OS, every program would need its own drivers, and only one program could safely run at a time.

A desktop operating system manages the screen, files and programs for the user

A smartphone runs a mobile operating system such as Android

Key management tasks

• process management 进程管理 — load programs, schedule them on the CPU, switch between them, and kill misbehaving ones. (A running program is a process 进程.)
• memory management 内存管理 — give memory to processes, keep them apart, and use virtual memory 虚拟内存 / paging 分页 so the working set can exceed physical RAM 随机存取存储器.
• file management — organise files and folders on secondary storage 辅助存储器, control permissions, prevent write corruption.
• device management — handle I/O through device drivers 设备驱动, buffer data, manage interrupts, and give a uniform interface.
• security management — accounts, permissions, firewall, encryption.
• user interface and networking.

The main jobs the operating system manages

Memory protection keeps each application in its own block of memory

Utility software

Most OSes include utility programs 实用程序 to maintain the system:

• file / disk management — copy, move, delete; format; check disk integrity.
• disk defragmenter 碎片整理 — moves the pieces of fragmented files together on a hard disk to cut seek time (not useful on SSDs).
• backup 备份 — copies user data elsewhere so it can be recovered.
• antivirus 杀毒软件 — scans for malware and quarantines threats.
• firewall 防火墙 — filters network traffic by rules.
• compression 压缩 / archiving; system monitor; updates.

Bundling these with the OS saves the user installing each one.

A program library 程序库 is pre-written code (subroutines 子程序, classes, modules) that programs reuse instead of writing it themselves — e.g. a maths library, a network library, a graphics library.

A new program reusing ready-made routines from libraries

Benefits: saves time (off-the-shelf code), reliable (well-tested, widely used), and standardised (consistent behaviour).

• a static library 静态库 is copied into the executable at compile time (stands alone, but larger and needs rebuilding to update).
• a dynamic library 动态库 (DLL, .so) is loaded at run time (smaller executables, shared by many programs, updated once for all).

You write source code; the computer runs machine code 机器码. A translator 翻译器 converts between them.

Assembler

An assembler 汇编器 translates assembly language 汇编语言 into machine code, one instruction per instruction. Used for low-level code (embedded systems, drivers).

Compiler

A compiler 编译器 translates a high-level program into machine code once, before it runs.

• it reports all errors at compile time; once clean, it produces a stand-alone executable 可执行文件 that runs without the compiler installed and can be run many times.
• generally faster at run time (no translation while running), but tied to one CPU/OS — recompile for each platform.

Interpreter

An interpreter 解释器 translates and runs a high-level program one line at a time, producing no executable.

• it reports an error when it reaches that line, then stops; you can fix it and continue — good for development.
• the interpreter must be installed to run the program; generally slower (each run re-translates), but easy to port across platforms.

Choosing between them

Use a compiler for maximum run-time speed, to distribute to users without dev tools, or when the program runs many times. Use an interpreter for fast development cycles, cross-platform scripts, small or run-once programs, and teaching beginners.

Hybrid: Java

Java is compiled into bytecode 字节码 (a platform-independent intermediate form), which a virtual machine 虚拟机 (the JVM) then interprets — or uses just-in-time compilation 即时编译 to turn hot parts into native code. So errors are caught early, the bytecode runs anywhere with a JVM ("write once, run anywhere"), and long-running programs reach near-native speed. C# and Python use similar designs.

An integrated development environment 集成开发环境 (IDE) brings the tools to write, test and debug code into one application:

• source code editor with syntax highlighting 语法高亮 (keywords, strings, comments in different colours), auto-indent and bracket matching.
• auto-complete 自动补全 — suggests names and shows function parameters as you type.
• translator integration — compile/run with one keystroke; errors shown inline.
• debugger 调试器 — set breakpoints 断点 to pause, step through line by line, and inspect variables.
• version control 版本控制 integration (git), project management, a help system, refactoring 重构 tools (safe renaming), and unit test 单元测试 integration.

An IDE speeds development by putting writing → running → debugging → fixing behind one interface. Common IDEs: Visual Studio, PyCharm, Eclipse, VS Code.

These sound alike but mean different things:

• security 安全 — protecting data from unauthorised 未授权 access, change or destruction.
• privacy 隐私 — an individual's right to control who sees their personal data, with consent and a clear purpose.
• integrity 完整性 — the data being accurate and complete — not corrupted or accidentally changed.

A file can be secure (only the right people can open it) but lack integrity (a typo corrupted it); or accurate but not private (anyone can read it). All three are needed.

Two things to protect: the data itself (keep it confidential, intact and available) and the computer system (a compromised system can attack others, steal credentials, or be held to ransom).

• malware 恶意软件 (malicious software):
  • virus 病毒 — self-copying code that attaches to other programs and spreads when they run.
  • worm 蠕虫 — self-copying code that spreads over networks 网络 with no user action.
  • Trojan horse 木马 — looks useful but hides malicious code.
  • spyware 间谍软件 — secretly collects information (keystrokes, passwords).
  • ransomware 勒索软件 — encrypts your files and demands payment.
  • adware 广告软件 — pushes unwanted adverts.
• phishing 网络钓鱼 — fake emails/sites that trick users into giving credentials.
• hacking 黑客入侵 — unauthorised access, often via weak passwords or software flaws.
• denial of service 拒绝服务 (DoS/DDoS) — floods a server so real users cannot reach it.
• eavesdropping 窃听 — capturing data in transit (a risk on open Wi-Fi).
• man-in-the-middle 中间人攻击 — an attacker secretly relays or alters messages between two parties.
• social engineering 社会工程 — tricking people into giving up information.

A standalone PC

• a strong password; antivirus kept up to date; prompt software updates; backup 备份 to separate media; full-disk encryption 加密; a locked screen.

A networked PC

All the above, plus a firewall 防火墙, per-user permissions (admin rights only for admins), central account management, and audit logs 审计日志 (who logged in, what they touched).

A firewall sits between the user's computer and the internet

Across the internet

• VPN 虚拟专用网 — encrypts traffic between the user and the corporate gateway.
• HTTPS / TLS — encrypt web traffic.
• intrusion detection — watches traffic for known attack patterns.

• interception in transit → encrypt the data (HTTPS, VPN). Intercepted ciphertext is useless without the key.
• unauthorised access → strong authentication 身份验证 (long passwords; two-factor authentication 双因素认证 with a phone code or key); user authorisation 授权; lock-out after failed logins.
• malware → antivirus and real-time scanning; patching; avoid untrusted downloads.
• phishing → user training; email filtering; check the URL before entering credentials.
• internal threats → the least-privilege 最小权限 principle (give each user only what they need); auditing.
• DDoS → rate limiting and traffic filtering.

• encryption — turn plaintext 明文 into ciphertext 密文 with a key. Symmetric encryption 对称加密 (AES) uses one shared key; asymmetric encryption 非对称加密 (RSA) uses a public key 公钥 and a private key 私钥. Protects data at rest and in transit.
• access control 访问控制 — file permissions (read/write/execute), enforced by the OS.
• authentication — verify the user: something you know (password), have (token, phone), or are (fingerprint); strongest combined.
• backups — keep copies (some off-site) so loss or corruption is recoverable.
• physical security — locked server rooms, cable locks.

A security token shows a changing code for two-factor authentication ("something you have")

A fingerprint reader checks "something you are" — a feature of the person, not a password

Data has integrity when it is accurate and complete. Two techniques: validation (catch bad data before storing) and verification (confirm data was entered or transferred correctly).

Validation — does the data make sense?

Validation 验证 checks data against sensible rules, automatically:

• range check — within limits (a month is 1–12).
• length check — the right number of characters.
• type / character check — the right kind of data (a phone field allows only digits).
• format check — matches a pattern (an email must contain @).
• presence check — required fields are not empty.
• check digit 校验位 — an extra digit computed from the others (ISBN, card numbers) that spots transcription errors.
• lookup check and consistency check (e.g. delivery date ≥ order date).

Validation catches data that is wrongly formatted, but not data that is the right format yet factually wrong ("Bob" for "Bib").

Verification — was the data entered or transferred correctly?

Verification 核对 checks the data was not changed in moving from one place to another.

During entry: double entry (type it twice and compare, as for a new password) or visual check.

During transfer (bits can flip):

• parity check 奇偶校验 — an extra bit makes the number of 1s even (even parity) or odd. The receiver re-counts. Catches single-bit errors.
• checksum 校验和 — the sender sends a summary value of the data; the receiver recomputes it and compares.
• cyclic redundancy check 循环冗余校验 (CRC) — a stronger checksum using polynomial division, catching many more error types.

The parity bit is set to make the number of 1s even or odd

Working out a checksum for a block of data

Verification only proves what arrived matches what was sent — not that the data is correct, and not against deliberate tampering. Validation asks "is this sensible?"; verification asks "was this copied correctly?" — use both.

A computing professional is someone whose work — software, systems, networks, data — affects other people. Because the work is technical, others often cannot judge whether it was done well or honestly. So the profession follows shared ethics 伦理 (principles for good behaviour).

Why ethics matters

• trust — users and employers trust professionals to act in their interest. Without that trust, software loses credibility.
• impact — software runs medical devices, banking, vehicles. Careless or dishonest work can hurt people.

Professional bodies (BCS, ACM, IEEE) publish codes of ethics for members.

CCTV raises privacy concerns — one of the ethical issues a computing professional must weigh

Discarded electronics (e-waste) are a growing environmental cost of computing

Software development affects the public's wellbeing in several ways

Typical principles

• public interest first — protect the safety and welfare of those affected.
• honesty and competence — be honest about your skills; don't claim expertise you lack.
• confidentiality 保密性 — protect clients' and employers' private information.
• avoid conflicts of interest 利益冲突 — don't take work where your interest clashes with the client's.
• keep your skills current; respect intellectual property 知识产权 and privacy 隐私; treat colleagues fairly.

Acting ethically vs unethically

Acting ethically protects users, strengthens reputation, reduces legal risk, and builds trust. Acting unethically (skipping testing, hiding bugs, misusing data) can harm real users, lead to dismissal or legal action, damage reputation, and erode trust in technology generally.

When you face a borderline decision: identify whose interests are affected, check the code of ethics and the law, weigh the consequences, ask a trusted senior, and choose the option that protects users above short-term convenience.

Copyright 版权 is the legal right of the creator of an original work to control how it is copied, distributed, modified and performed. It applies automatically (no registration) to source code, software, documents, images, audio and video.

Without copyright, anyone could copy software freely, the developer would not be paid, and plagiarism would be legal. With copyright, developers can earn from their work (encouraging more software), users know who made it, and re-use happens on the developer's terms through licensing. Copyright lasts a long time (often 70 years after the creator's death). General ideas and algorithms are not covered by copyright but may be covered by a patent 专利.

A software licence 软件许可证 is a contract granting permission to use software on the owner's terms.

Commercial (proprietary)

• you buy a licence; the software is used only within its terms.
• the source code is not given (a proprietary 专有 product); you cannot modify or redistribute it.
• examples: Microsoft Office, Adobe Photoshop, most games.

Used when the developer wants revenue per user and to keep control of the code.

Open-source

• the source code is public; users can read, modify and redistribute it (open-source 开源).
• permissive licences (MIT, BSD) allow almost any use; copyleft 著佐权 licences (GPL) require that modified versions are released under the same licence ("share-alike").
• examples: Linux, Python, Apache.

Used when the developer wants the software widely used and improved by the community.

Freeware and shareware

• freeware 免费软件 — free of charge, no source code, may be redistributed but not modified (Acrobat Reader, WhatsApp).
• shareware 共享软件 — free for a trial period, then you pay to keep using it; no source code.

To justify a licence choice, link it to the developer's goal (revenue, reach, community), the user's needs (cost, customising), and the use case.

Artificial intelligence 人工智能 builds systems that do tasks once thought to need human intelligence — recognising speech and images, translating, playing games, driving.

Most modern AI uses machine learning 机器学习 — algorithms that improve at a task by learning patterns from large amounts of data, instead of being programmed step by step. Deep learning 深度学习, using neural networks 神经网络 with many layers, is the leading approach today.

Everyday examples

• speech recognition 语音识别 — spoken words to text (voice assistants).
• image recognition 图像识别 — finding objects, faces or text in images.
• machine translation 机器翻译 — automatic translation between languages.
• recommendation systems 推荐系统 — suggesting products, videos or music.
• autonomous vehicles 自动驾驶汽车 and robots.

A common exam scenario: a program reads a label with a camera, translates it, and reads it aloud — using optical character recognition 光学字符识别 to find the words, machine translation to convert them, and text-to-speech 文本转语音 for the audio.

Benefits

• accessibility — speech/image AI helps users with impairments; translation helps non-native speakers.
• productivity — automating repetitive tasks frees people for creative work.
• decision support — AI spots patterns in huge datasets (medical diagnosis, fraud detection).
• always available, and personalised to each user.

Concerns

• bias 偏见 — unfair patterns in the training data become unfair AI decisions (hiring, lending).
• job displacement — AI may replace some roles.
• privacy — training often uses large amounts of personal data.
• transparency — large models are "black boxes", hard to explain.
• accountability — when AI is wrong, who is responsible: developer, user, or operator?
• misuse — deepfakes, misinformation, surveillance.

Professionals must understand the limits of the AI they build, inform users, and reduce harm.

Before databases, programs stored data in flat files 平面文件 — usually one file per program. This is fine for small data but breaks down at scale.

File-based storage keeps data in separate files, like papers in a filing cabinet — hard to search and easy to duplicate

Limitations

• data redundancy 数据冗余 — the same data (a customer's address) is held in several files.
• data inconsistency 数据不一致 — redundant copies updated separately get out of sync.
• data dependence — programs are tied to the file format; change the format and every program must be rewritten.
• hard to enforce integrity 完整性, hard to share safely, weak querying, and weak per-field security.

The files themselves are stored on devices such as hard disk drives

The file-based approach: each program keeps its own files

A relational database 关系数据库 fixes these by storing data in tables managed by one piece of software (the DBMS) that all programs use.

The database approach: one DBMS serves all the programs

• table 表 (relation) — a grid of rows and columns; one table per type of entity 实体 (e.g. CUSTOMER).
• record 记录 (row) — one row; one instance of the entity.
• field 字段 (column) — one column; one piece of information about each record.
• primary key 主键 — a field (or fields) that uniquely identifies each record; never null or duplicated.
• foreign key 外键 — a field whose value matches the primary key of another table, linking the two.
• composite key 复合键 — a primary key made of two or more fields together.
• candidate key 候选键 — any field(s) that could be the primary key.
• referential integrity 参照完整性 — every foreign-key value must match an existing primary key (no orphan records).

A table is written in shorthand with the primary key underlined and foreign keys noted:

CUSTOMER(CustomerID, Name, Phone)
ORDER(OrderID, CustomerID, OrderDate)   -- CustomerID is FK → CUSTOMER

An entity-relationship diagram 实体关系图 shows the structure: each entity is a rectangle, each relationship a line, with the cardinality 基数 marked at each end:

• one-to-one (1:1).
• one-to-many 一对多 (1:M) — each Customer has many Orders; each Order has one Customer.
• many-to-many (M:N) — Students take many Courses, and Courses have many Students.

An E-R diagram: one class has many students

Crow's-foot symbols for the cardinality of a relationship

A many-to-many relationship cannot be stored directly. Break it into two one-to-many relationships through a link table 连接表 holding the two foreign keys:

ENROLMENT(StudentID, CourseID, EnrolmentDate)

Normalisation 规范化 organises tables to cut redundancy and inconsistency, going through normal forms 范式 in order.

• First normal form (1NF) — every field holds a single (atomic 原子) value, with no repeating groups, and a primary key.
• Second normal form (2NF) — in 1NF, and every non-key field depends on the whole primary key (only matters for a composite key).
• Third normal form (3NF) — in 2NF, and every non-key field depends only on the primary key, not on another non-key field (no transitive dependency 传递依赖).

A 3NF design stores each fact once, so insert/update/delete anomalies disappear. The trade-off is more tables and more joins. Aim for 3NF.

To produce a 3NF design: find the entities and their attributes; choose a primary key for each; split repeating/non-atomic fields (1NF); split fields depending on part of a composite key (2NF); split fields depending transitively on the key (3NF); add foreign keys for the relationships.

A DBMS 数据库管理系统 manages the database centrally. Features that fix the file-based limits:

• data dictionary 数据字典 — a description of every table, field, type and key; programs query it instead of hard-coding the structure.
• redundancy/consistency control — each fact stored once.
• concurrent access 并发访问 control — locks and transactions let many users work at once.
• backup 备份 and recovery; security and per-user permissions.
• integrity rules — keys, unique and range constraints, enforced centrally.
• transactions 事务 — a group of operations that all succeed or all fail.
• views 视图 — virtual tables that show each user "their" slice of the data.

Its tools include a data-dictionary editor, a query builder, a forms builder, a report generator, user management, and an SQL editor.

SQL 结构化查询语言 (Structured Query Language) has two halves:

• Data Definition Language 数据定义语言 (DDL) — creates or changes the structure (tables, keys, constraints).
• Data Manipulation Language 数据操纵语言 (DML) — works with the data (insert, update, delete, query 查询).

DDL basics

CREATE TABLE CUSTOMER (
  CustomerID INTEGER PRIMARY KEY,
  Name VARCHAR(50) NOT NULL,
  Phone VARCHAR(20)
);

Add a foreign key:

CREATE TABLE ORDER (
  OrderID INTEGER PRIMARY KEY,
  CustomerID INTEGER,
  OrderDate DATE,
  FOREIGN KEY (CustomerID) REFERENCES CUSTOMER(CustomerID)
);

Modify and drop:

ALTER TABLE CUSTOMER ADD Email VARCHAR(100);
DROP TABLE CUSTOMER;

Common types: INTEGER, VARCHAR(n), CHAR(n), DATE, BOOLEAN, DECIMAL(p, s).

DML basics

Query with SELECT:

SELECT Name, Phone
FROM CUSTOMER
WHERE City = 'London'
ORDER BY Name ASC;

SELECT lists fields, FROM names the table, WHERE filters rows, ORDER BY sorts.

A join 连接 combines two tables using a foreign-key relationship:

SELECT C.Name, O.OrderDate
FROM CUSTOMER C INNER JOIN ORDER O
  ON C.CustomerID = O.CustomerID
WHERE O.OrderDate >= '2024-01-01';

Aggregate functions 聚合函数 (COUNT, SUM, AVG, MIN, MAX) are often used with GROUP BY:

SELECT CustomerID, COUNT(*) AS NumOrders
FROM ORDER
GROUP BY CustomerID;

Insert, update, delete:

INSERT INTO CUSTOMER (CustomerID, Name, Phone)
VALUES (101, 'Ada Lovelace', '020-1234-5678');

UPDATE CUSTOMER SET Phone = '020-9999-0000' WHERE CustomerID = 101;

DELETE FROM CUSTOMER WHERE CustomerID = 101;

Always put a WHERE clause on UPDATE and DELETE, or the change hits every row.

Tips for exam SQL

• use the exact table and field names from the question.
• quote strings with single quotes ('Smith'); don't quote numbers.
• comparisons: =, <, >, <=, >=, <>.
• LIKE 'A%' matches anything starting with A (% = any string, _ = one character); IN (1,2,3); BETWEEN 10 AND 20.
• combine conditions with AND / OR / NOT, and end each statement with a semicolon.

Computational thinking 计算思维 is the set of mental tools for analysing a problem and designing a solution a computer can run. Two key ones are abstraction and decomposition.

Computational thinking breaks a big problem into smaller, easier parts — like solving a jigsaw

Abstraction

Abstraction 抽象 means keeping the essential features of a problem and ignoring the irrelevant detail, giving a simpler model.

Examples: a train-network map keeps the stations and lines but drops geography; a class in object-oriented programming keeps the few attributes and methods the system needs; a function hides a piece of work behind a name. Abstraction is essential because a full model of any real problem would be too big to reason about.

Decomposition

Decomposition 分解 means breaking a large problem into smaller sub-problems, each easier to solve and tackled one at a time.

1. find the main parts of the task.
2. break each into smaller sub-tasks.
3. continue until each is small enough to design directly.
4. solve the small tasks and combine them.

For stock control: "manage stock" → "record sales", "record deliveries", "produce reports" → ("record sales") "look up product", "decrease stock count", "save the transaction". Decomposition makes big problems manageable, lets a team divide the work, and gives modular code.

Decomposing a program into modules and sub-modules

An algorithm 算法 is a solution expressed as a sequence of defined steps. Each step is unambiguous 无歧义 (one meaning), deterministic 确定性 (same input → same output), finite (the steps end), and effective (each can be done). An algorithm says what to do, independent of the programming language used to implement it.

When you start an algorithm, list every piece of data in an identifier table 标识符表 — its variable 变量 name, data type 数据类型, and description:

Use descriptive names (ItemCost, not x); common types are INTEGER, REAL, STRING, CHAR, BOOLEAN, DATE, plus arrays. The table forces you to name every piece of data before writing code.

Pseudocode 伪代码 is a structured, language-neutral way to describe algorithms.

1. Sequence

Steps run one after another (sequence 顺序):

INPUT Name
INPUT Age
OUTPUT "Hello", Name

2. Selection

A choice of which steps run, based on a condition (selection 选择):

IF Age >= 18 THEN
    OUTPUT "Adult"
ELSE
    OUTPUT "Minor"
ENDIF

For more options, use CASE OF ... ENDCASE.

3. Iteration

Repeating a block (iteration 迭代, a loop 循环):

FOR i ← 1 TO 10
    OUTPUT i
NEXT i

A WHILE loop tests the condition before each pass (may run zero times); a REPEAT...UNTIL loop tests after each pass (always runs at least once).

Common operations

• assignment 赋值: x ← 5 (an arrow; = is for comparison).
• input/output: INPUT variable, OUTPUT expression.
• comparisons =, <>, <, >, <=, >=; logic AND, OR, NOT.
• arithmetic + - * /, plus DIV (integer division) and MOD (remainder).
• strings: LENGTH, LEFT, RIGHT, MID, and & for concatenation 拼接 (joining).

Input → Process → Output

Every program follows this shape:

INPUT Length
INPUT Width
Area ← Length * Width
OUTPUT "Area = ", Area

Listing the inputs and outputs first makes the algorithm cleaner.

The same algorithm can be written three ways.

• structured English 结构化英语 — natural language with indentation and fixed keywords; good for a high-level description.
• flowchart 流程图 — a diagram with standard shapes:

• pseudocode — the keyword notation above; closest to code.

You should be able to convert between any pair: each IF is a decision diamond, each loop is a back-arrow, and a sequence is stacked rectangles.

A flowchart for averaging a list of numbers, using the standard shapes

Stepwise refinement 逐步求精 starts with a high-level outline and expands each step until it is small enough to code. For an average of $n$ numbers:

Level 1:

Read in the numbers
Compute the average
Output the average

Level 2:

INPUT n
total ← 0
FOR i ← 1 TO n
    INPUT value
    total ← total + value
NEXT i
average ← total / n
OUTPUT average

Each refinement keeps the previous structure and adds detail.

A logic statement 逻辑语句 is a Boolean 布尔 condition that controls branching, built from comparisons (x > 10), connectives (AND, OR, NOT) and brackets. Use it as the condition of IF, WHILE or REPEAT...UNTIL:

WHILE attempts < 3 AND NOT loggedIn DO
    INPUT password
    IF password = correctPassword THEN
        loggedIn ← TRUE
    ELSE
        attempts ← attempts + 1
    ENDIF
ENDWHILE

Precedence 优先级 (highest to lowest): NOT, then AND, then OR. Use brackets when unsure. Common mistakes:

• a = 1 OR 2 is wrong — write a = 1 OR a = 2.
• NOT a > 5 means NOT (a > 5), i.e. a <= 5.
• NOT (A AND B) is the same as (NOT A) OR (NOT B) (De Morgan's law 德摩根定律) — handy for simplifying conditions.

Every variable needs a data type 数据类型 — the kind of value it holds and the operations allowed:

• INTEGER — a whole number (42, -7). For counts, indexes, IDs.
• REAL — a number with a fractional part (3.14). For money, measurements.
• STRING — characters in quotes ("Hello"). For text.
• CHAR — a single character ('A').
• BOOLEAN — TRUE or FALSE. For flags.
• DATE — a calendar date.

Pick the smallest precise type that fits: INTEGER for whole counts, BOOLEAN for flags (not the strings "yes"/"no").

A record 记录 holds several fields of different types under one name — useful when several values describe one thing.

TYPE TStockItem
    DECLARE ItemID : INTEGER
    DECLARE Category : STRING
    DECLARE ItemCost : REAL
    DECLARE InStock : BOOLEAN
ENDTYPE

This defines the type TStockItem; declare variables of it:

DECLARE Item1 : TStockItem
DECLARE Items : ARRAY[1:100] OF TStockItem

Use dot notation to reach each field 字段:

Item1.Category ← "Fruit"
OUTPUT Item1.Category, " costs ", Item1.ItemCost

Use a record when values always belong together (a customer, a stock item); use separate variables for unrelated values.

An array 数组 is an ordered collection of items of the same type, under one name, reached by an index 索引.

• element 元素 — one item in the array.
• bounds 边界 — the lowest and highest valid indices.
• dimension 维度 — 1-D (a list), 2-D (a table), etc.

1-D arrays

DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"
OUTPUT Names[3]

Process every element with a FOR loop:

FOR i ← 1 TO 5
    OUTPUT Names[i]
NEXT i

A 1-D array (a list) with indices and bounds

2-D arrays

DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99

The first index is the row, the second the column. Use nested loops to visit every cell. Use 1-D for a single sequence, 2-D for two natural dimensions (a grid, rows × columns).

A 2-D array (a table) with row and column indices

Common operations

A linear search 线性查找 checks each element until found:

FOR i ← 1 TO n
    IF A[i] = Target THEN
        OUTPUT "Found at ", i
    ENDIF
NEXT i

To find a sum, count, maximum or minimum, set a running variable then sweep through:

Max ← A[1]
FOR i ← 2 TO n
    IF A[i] > Max THEN Max ← A[i]
NEXT i

A file 文件 is data stored on secondary storage 辅助存储器, kept between program runs. Variables in RAM disappear when the program ends, so to save data permanently (high scores, records, settings) the program writes to a file. Files also let programs share data and restart from a saved state.

A text file 文本文件 is lines of readable characters. Open a file before use and close it after:

OPENFILE "data.txt" FOR READ      // or FOR WRITE, FOR APPEND
WHILE NOT EOF("data.txt") DO
    READFILE "data.txt", LineString
    OUTPUT LineString
ENDWHILE
CLOSEFILE "data.txt"

EOF tests the end of file 文件结束 before reading. To write:

OPENFILE "log.txt" FOR WRITE
FOR i ← 1 TO 100
    WRITEFILE "log.txt", "Event " & i
NEXT i
CLOSEFILE "log.txt"

Always close every file — otherwise buffered writes may be lost and other programs may be locked out.

An Abstract Data Type 抽象数据类型 (ADT) is a collection of data plus operations on it, defined by what it does, not how it is stored. The user works only through the operations; the implementation is hidden, so it can change without affecting code that uses the ADT. Know three: stack, queue, linked list.

Stack

A stack 栈 works in LIFO 后进先出 order (Last In, First Out). Operations: push 入栈 (add to the top), pop 出栈 (remove from the top), peek (look at the top), and tests for empty/full. Uses: undo history, function-call return addresses, expression parsing, backtracking.

Push and pop change the top pointer; the base pointer stays put

Queue

A queue 队列 works in FIFO 先进先出 order (First In, First Out). Operations: enqueue 入队 (add to the rear), dequeue 出队 (remove from the front), and tests for empty/full. Uses: print spooling, scheduling, breadth-first search, buffering.

Enqueue adds at the rear; dequeue removes from the front

Linked list

A linked list 链表 stores data as a sequence of nodes 节点. Each node holds a value and a pointer 指针 to the next node; a head pointer marks the start, and the last node's pointer is a sentinel (e.g. NULL). Operations: insert, delete, search, and traverse 遍历 (visit each node in order). Its advantage over an array is cheap insertion/deletion (just adjust pointers); its disadvantage is slow random access (you must follow pointers from the head).

A linked list: each node points to the next

Stack using an array

Hold items in Stack[1:MaxSize] with an integer Top (0 when empty).

• Push(x): if Top = MaxSize the stack is full (overflow 溢出); else Top ← Top + 1; Stack[Top] ← x.
• Pop(): if Top = 0 the stack is empty (underflow 下溢); else return Stack[Top] and Top ← Top - 1.

Queue using a circular array

A simple queue lets Front and Rear march off the end, wasting the start. The fix is a circular array 循环数组 — when a pointer reaches MaxSize it wraps back to 1:

• Enqueue(x): check full; else Rear ← (Rear MOD MaxSize) + 1; Queue[Rear] ← x.
• Dequeue(): check empty; else return Queue[Front] and Front ← (Front MOD MaxSize) + 1.

Track a separate count to tell empty from full.

A circular queue wraps the pointers back to the start of the array

Linked list using an array

Use an array of records, each with a Next index:

TYPE TNode
    DECLARE Value : INTEGER
    DECLARE Next : INTEGER     // index of the next node, or -1 for end
ENDTYPE

DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER         // index of first node, -1 if empty
DECLARE FreeListHead : INTEGER // first available free node

A free list 空闲列表 chains the unused slots, just as the data list chains its used ones. To insert: take a slot from FreeListHead, set the new node's value and Next, and update the previous node's Next (or Head). To delete: unlink the node and return its slot to the free list. This gives the flexibility of a linked structure with the static allocation of an array.

A linked list stored in an array: a data array and a pointer array

Programming turns a design into instructions written as code

A programmer writes the code and tests it as they go

From design to code

You should be able to turn a design — a flowchart 流程图 or structured English 结构化英语 — into pseudocode 伪代码, and then into a real language:

1. find the variables 变量 and their data types 数据类型.
2. turn input/output boxes into INPUT / OUTPUT.
3. turn decision diamonds into IF...ELSE...ENDIF (or CASE).
4. turn loop arrows into WHILE, REPEAT...UNTIL, or FOR.
5. turn process boxes into assignments or calculations.
6. check by tracing a small input.

Constants and variables

A constant 常量 holds a value that never changes; a variable holds one that may change. Declare them with a type:

CONSTANT Pi ← 3.14159
DECLARE Radius : REAL
DECLARE Area : REAL

Radius ← 5
Area ← Pi * Radius * Radius

Use constants for fixed values that recur (Pi, MaxScore); they make code clearer and easy to change in one place.

Assignment and expressions

Use ← for assignment 赋值:

Total ← Total + 1
Average ← Sum / Count

Expressions use operators 运算符:

• arithmetic + - * /, plus DIV (integer division) and MOD (remainder): 7 DIV 2 = 3; 7 MOD 2 = 1.
• comparisons =, <>, <, >, <=, >=.
• logic AND, OR, NOT.

Precedence 优先级 (highest to lowest): NOT → * / DIV MOD → + - → comparisons → AND → OR. Use brackets when unsure.

Input and output

OUTPUT "Enter your name:"
INPUT Name
OUTPUT "Hello, ", Name

Built-in functions and library routines

Many tasks have ready-made library routines 库例程, so you need not write them:

• string: LENGTH(s), LEFT(s, n), RIGHT(s, n), MID(s, start, len), UCASE(s), LCASE(s).
• numeric: INT(x), ROUND(x), ABS(x), MOD(a, b), RANDOM().
• conversion: STR(x) (number → string), VAL(s) (string → number).

Use the exact names from the question paper's reference list.

Selection 选择 chooses which steps run.

IF age >= 18 THEN
    OUTPUT "Adult"
ELSE
    OUTPUT "Minor"
ENDIF

For more than two cases you can use a nested 嵌套 IF, but deep nesting is hard to read — a CASE is cleaner when testing one value against several options:

CASE OF Grade
    "A": OUTPUT "Excellent"
    "B": OUTPUT "Good"
    OTHERWISE: OUTPUT "Try again"
ENDCASE

Cambridge CASE allows single values, value lists (1, 2, 3:), and ranges (1 TO 5:).

A CASE statement runs the branch that matches the value

Iteration 迭代 repeats a block. Three loops differ in how many times the body runs.

Count-controlled (FOR) loop

A count-controlled loop 计数循环 — use it when you know how many times to repeat:

FOR i ← 1 TO 10
    OUTPUT i
NEXT i

A STEP can change the count (e.g. FOR i ← 10 TO 1 STEP -1). Best for a fixed number of repeats or processing each element of an array 数组.

Pre-condition (WHILE) loop

A pre-condition loop 前测循环 tests the condition before each pass, so it may run zero times:

WHILE total < 100 DO
    INPUT n
    total ← total + n
ENDWHILE

Post-condition (REPEAT...UNTIL) loop

A post-condition loop 后测循环 tests the condition after each pass, so it always runs at least once:

REPEAT
    INPUT password
UNTIL password = correctPassword

Choosing the right loop

• count known up front → FOR.
• may need zero passes → WHILE.
• always at least one pass → REPEAT...UNTIL.

Justify your choice by whether the count is known and whether the body must run at least once. A typical question gives a scenario ("ask for a password until correct, but always ask at least once") and asks which loop fits.

Structured programming 结构化编程 builds a program from small named subroutines 子程序, each with one job.

Procedure

A procedure 过程 is a named block that does an action; it may take parameters 参数 but does not return a value.

PROCEDURE Greet(name : STRING)
    OUTPUT "Hello, ", name
ENDPROCEDURE

CALL Greet("Ada")

Function

A function 函数 is like a procedure but it returns a value that becomes part of an expression.

FUNCTION Square(x : INTEGER) RETURNS INTEGER
    RETURN x * x
ENDFUNCTION

result ← Square(5) + 1     // result = 26

Use a procedure when the subroutine performs an action; use a function when it computes a value for the caller.

Parameters

A parameter is a variable a subroutine declares to receive input; the values the caller supplies are arguments 实参. Two ways to pass them:

• pass by value 传值 — the routine gets a copy; changes inside it do not affect the caller. Use for inputs it only reads.
• pass by reference 传引用 — the routine gets a reference to the caller's variable; changes do affect the caller. Use when it must update a parameter.

PROCEDURE Swap(BYREF a : INTEGER, BYREF b : INTEGER)
    DECLARE temp : INTEGER
    temp ← a
    a ← b
    b ← temp
ENDPROCEDURE

Local vs global variables

A local variable 局部变量 is declared inside a subroutine and exists only while it runs. A global variable 全局变量 is declared outside and is visible everywhere. Prefer locals and parameters — heavy use of globals makes code hard to follow and test. (The region where a name is visible is its scope 作用域.)

When to use a subroutine

Use one when the same logic appears in more than one place, when a block has a clear named purpose, when the program is complex (use decomposition 分解), or when you want to test a piece in isolation. Don't make them so tiny that the call costs more than the content.

Terminology

• definition — the PROCEDURE ... ENDPROCEDURE (or function) block.
• call — where it is invoked. argument — a value passed in. parameter — the variable that receives it.
• return value — what a function passes back.
• signature 签名 — name + parameters + return type.

• move invariants out of loops — if a value (an invariant 不变量) does not change with the loop counter, compute it once before the loop.
• exit a loop early when the answer is found (stop a linear search 线性查找 as soon as the target appears).
• avoid redundant work — store a result and reuse it instead of recomputing.
• choose the right data structure — an array beats many separate variables when the items belong together.
• replace deep nested IFs with CASE when testing one value against many.
• comment the intent, not the mechanics (// validate the postcode, not // loop 6 times).
• use meaningful names (numberOfPupils, not n) and initialise variables before use.

A development life cycle 开发生命周期 is the set of stages from idea to finished, maintained software. It exists to plan, manage and control a project — to build the right product, on time, with good quality.

Software is built by teams who follow a development life cycle to stay coordinated

A flowchart plans a program's logic during the design stage of the cycle

Why a life cycle is needed

It manages complexity (break a big program into phases), coordinates teams, tracks progress with milestones, builds in testing, records design decisions for later, and manages risk.

Why there are different ones

No single life cycle fits every project. The choice depends on the size and complexity, how clear the requirements 需求 are at the start, how much change is expected, the risk level, the team, and the deadline.

Common models

• Waterfall 瀑布模型 — a linear sequence (Analysis → Design → Coding → Testing → Maintenance), each stage finished before the next. Clear and well-documented; good for stable requirements, but poor at coping with mid-project change, and the customer sees nothing working until the end.
• Iterative model 迭代模型 — repeated passes, each producing a partial version that is reviewed and refined. Catches problems earlier; good when requirements are discovered over time, but harder to estimate.
• Rapid Application Development 快速应用开发 (RAD) — heavy use of a prototype 原型 and user feedback. Very fast first delivery; good for changing requirements, but depends on user availability and suits smaller systems.
• Agile 敏捷 — short iterations ("sprints"), constant collaboration and testing. Flexible and adaptive, but needs a committed customer and a skilled team.

The waterfall model: each stage is finished before the next begins

The iterative model: repeated passes refine the program

Rapid application development: teams work on parts in parallel

The standard stages

• analysis — find what the program must do; gather and document requirements.
• design — decide how: data structures, algorithms, modules, interface, file layouts.
• coding (implementation 实现**)** — write the source code following the design.
• testing — run against test data and fix bugs.
• maintenance 维护 — after release, keep it working and useful.

Structure chart

A structure chart 结构图 shows the hierarchical decomposition 分解 of a program into modules (subroutines 子程序) and the parameters 参数 passed between them. Each module is a rectangle; lines link caller (above) to callee (below); small arrows show data going down and results coming back up.

                CalculatePay
            /        |         \
       GetEmployee  CalculateBonus  CalculateTax
       Returns:     Takes: sales    Takes: gross
       employeeID   Returns: bonus  Returns: tax

It is a design-stage tool, and you can read the procedure signatures off it.

A structure chart: modules with the parameters passed between them

State-transition diagram

A state-transition diagram 状态转换图 shows the states 状态 a system can be in and the events that move it between them — good for vending machines, traffic lights, user interfaces. Each state is a circle; each transition is an arrow labelled with the event.

   coin inserted               item selected
[Idle] ──────────────→ [Awaiting selection] ──────────→ [Dispensing]

It makes missing transitions easy to spot ("what if a second coin is inserted while awaiting selection?").

A state-transition diagram for a door lock with code 259

• syntax error 语法错误 — breaks the language's grammar (missing bracket, misspelled keyword). Caught at translation time; the program won't run until fixed.
• run-time error 运行时错误 — happens while running (divide by zero, file not found, array index out of range). The program crashes or raises an exception; fix by adding checks.
• logic error 逻辑错误 — the program runs but gives wrong results (using + for -, an off-by-one loop, conditions in the wrong order). The hardest to find; the only sign is wrong output, so use careful testing and tracing.

• dry run 手工跟踪 — trace the code on paper, writing each variable's value in a table.
• walkthrough 走查 — a team review of the code.
• white-box testing 白盒测试 — designed from the code's internal structure, covering every statement, branch and loop.
• black-box testing 黑盒测试 — designed from the specification only: feed inputs, check outputs.
• integration testing 集成测试 — combine modules and test the interfaces between them.
• alpha testing α测试 — by the developers/in-house before release; beta testing β测试 — by a limited group of real users in their own environment.
• acceptance testing 验收测试 — by the customer, to decide if the product is fit for purpose.
• stub 桩 — a placeholder for a module that does not exist yet, so the structure can be tested top-down.

A test strategy 测试策略 is the high-level approach — which kinds of testing, who does them, when, and the criteria to move on. A test plan 测试计划 is the detailed list of tests — each with input data, expected output, and a column for the actual output.

Choosing test data

For each field or condition, include three kinds:

• normal data 正常数据 — typical values inside the valid range (for marks 0–100: 50, 75).
• abnormal data 异常数据 — values that should be rejected (-10, 200, "abc").
• boundary data 边界数据 — values at the edges, where off-by-one errors hide (0, 100, and just outside -1, 101).

Most of a program's lifetime cost is in maintenance. Three kinds:

• perfective maintenance 完善性维护 — improving performance or features even though it works (a faster query, a new option).
• adaptive maintenance 适应性维护 — keeping it working in a changing environment (a new OS, a new API, a legal change).
• corrective maintenance 纠正性维护 — fixing bugs found in use.

A program may need all three throughout its life.