Matura Computer Science cheat sheet

Binary search runs in O(log n) time but requires a sorted array; linear search is O(n) and works on any sequence.

Bubble, insertion and selection sort are O(n^2); merge sort and heap sort are O(n log n) in the worst case; quicksort averages O(n log n) but degrades to O(n^2) on already-sorted data with a naive pivot.

Recursion needs a base case and a step that moves toward it; each call consumes stack memory, so depth n costs O(n) stack space.

A stack is LIFO (push/pop at one end); a queue is FIFO (enqueue at rear, dequeue at front); a deque allows both ends.

Big-O describes an upper bound on growth; O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!).

Iterative solutions to problems with overlapping subproblems (e.g. Fibonacci) are usually faster than naive recursion because memoisation or a table avoids recomputation.

A loop invariant is a property true before and after every iteration; at termination it proves correctness (e.g. sorted prefix in insertion sort).

In a 0-indexed array of length n, valid indices are 0..n-1; accessing index n is an out-of-bounds error, not a wrap-around.

n bits represent 2^n distinct values; an unsigned integer of n bits ranges from 0 to 2^n - 1.

Two's complement: to negate a number, invert all bits and add 1; an n-bit signed integer ranges from -2^(n-1) to 2^(n-1) - 1.

Converting binary to hexadecimal groups bits in fours from the right (0000-1111 -> 0-F); octal groups in threes.

A linked list stores a value plus a pointer to the next node: O(1) insertion at a known node, O(n) search, no random access.

A binary search tree keeps left subtree keys smaller and right subtree keys larger; search, insert and delete are O(log n) when balanced and O(n) when degenerate.

A hash table maps a key through a hash function to a bucket; collisions are resolved by chaining or open addressing, and load factor drives resizing.

ASCII uses 7 bits (128 codes); Unicode assigns code points (e.g. U+0041) and UTF-8 encodes them in 1-4 bytes, ASCII-compatible for the first 128.

A heap is a complete binary tree stored in an array where parent index i has children 2i+1 and 2i+2 (0-indexed); the root holds the min or max.

A primary key uniquely identifies a row and cannot be NULL; a foreign key references a primary key in another table and enforces referential integrity.

SELECT ... FROM ... WHERE ... GROUP BY ... HAVING ... ORDER BY ... is evaluated logically in that order; WHERE filters rows before grouping, HAVING filters groups after.

INNER JOIN returns only matching rows; LEFT JOIN keeps all left rows and fills unmatched right columns with NULL; RIGHT JOIN is the mirror image.

COUNT(*) counts rows including NULLs; COUNT(column) ignores NULLs; AVG and SUM also ignore NULLs.

DISTINCT removes duplicate result rows; it applies to the whole selected row, not to a single column.

INSERT adds rows, UPDATE modifies existing rows, DELETE removes rows; all three can be restricted by a WHERE clause (omitting it affects every row).

Normalisation reduces redundancy: 1NF requires atomic values, 2NF removes partial dependencies on part of a composite key, 3NF removes transitive dependencies.

A transaction is atomic, consistent, isolated and durable (ACID); COMMIT makes changes permanent and ROLLBACK undoes uncommitted ones.

The TCP/IP model has four layers: application, transport, internet, and link (network access); each layer encapsulates the payload of the one above.

IPv4 addresses are 32 bits written as four dotted decimal octets; a /24 prefix means 24 network bits and 8 host bits, giving 254 usable hosts.

TCP is connection-oriented and reliable (handshake, acknowledgements, retransmission, ordered delivery); UDP is connectionless with no delivery guarantee.

Ports identify services: 80 HTTP, 443 HTTPS, 25 SMTP, 53 DNS, 22 SSH, 21 FTP control.

DNS resolves domain names to IP addresses recursively through root, TLD and authoritative servers; records include A, AAAA, MX, CNAME and NS.

HTTP is a request-response protocol; GET retrieves data and is cacheable, POST submits data in the body; HTTPS is HTTP over TLS (default port 443).

Switches forward frames by MAC address inside a LAN; routers forward packets by IP address between networks.

A subnet mask separates network and host bits; two hosts communicate directly only if their network portions match, otherwise a gateway is used.

The fetch-decode-execute cycle: the program counter gives the address, the instruction is loaded into the instruction register, decoded, then executed.

Von Neumann architecture shares one memory for instructions and data; Harvard architecture uses separate instruction and data memories.

Registers are fastest, then cache (L1/L2/L3), then RAM, then secondary storage; capacity and access latency grow in the opposite direction.

RAM is volatile and loses contents on power loss; ROM and flash retain data without power.

Binary addition: 1 + 1 = 10 with carry 1; overflow occurs when the result needs more bits than the register width provides.

A half adder produces sum = A XOR B and carry = A AND B; a full adder also accepts a carry-in.

A logic gate set is functionally complete if it can express any Boolean function: NAND alone, NOR alone, and {AND, OR, NOT} are complete.

Memory-mapped I/O and interrupts let the CPU communicate with peripherals without continuously polling device status.

The waterfall model proceeds through sequential phases with fixed requirements; iterative and agile models deliver increments and welcome changing requirements.

Version control (e.g. Git) records snapshots: commit saves a local snapshot, branch diverges history, merge combines branches, and conflicts must be resolved manually.

Black-box testing checks behaviour against specifications without knowledge of internals; white-box testing exercises internal paths and branches.

Unit tests cover single components, integration tests cover interactions, and system/acceptance tests validate the whole product against requirements.

Regression testing re-runs existing tests after a change to confirm previously working behaviour still works.

A UML class diagram shows classes, attributes, methods and relationships (association, inheritance, aggregation, composition); a use-case diagram shows actors and goals.

The software lifecycle: requirements, design, implementation, testing, deployment, maintenance - maintenance usually consumes the largest share of total cost.

Code review and pair programming are static techniques: they find defects without executing the program, unlike dynamic testing.

Personal data protection (e.g. GDPR) grants rights of access, rectification, erasure and portability, and requires a lawful basis for processing.

Copyright protects the expression of a work, not ideas; software licences define permitted use - proprietary, freeware, open source (e.g. GPL, MIT).

A licence grants rights; using software without one is copyright infringement even if the copy was obtained legally.

A patent protects a novel technical invention for a limited term; a trademark protects signs identifying the source of goods or services.

Computer misuse laws criminalise unauthorised access to systems and data; accessing a system without permission is an offence even without damage.

Digital divide refers to unequal access to technology and skills; accessibility aims to make systems usable by people with disabilities (e.g. WCAG guidelines).

Automation shifts employment: it removes routine tasks and creates roles in design, maintenance and data analysis, so reskilling matters.

Net neutrality is the principle that ISPs treat all traffic equally, without blocking or prioritising by content or payment.

Relative references (A1) shift when copied; absolute references ($A$1) stay fixed; mixed references ($A1, A$1) lock only one component.

SUM, AVERAGE, MIN, MAX, COUNT ignore text and empty cells; COUNTA counts non-empty cells and COUNTBLANK counts empty ones.

IF(condition, value_if_true, value_if_false) can be nested; AND/OR combine conditions inside IF or inside conditional formatting rules.

VLOOKUP(value, range, col_index, FALSE) performs an exact match and searches only the first column; XLOOKUP and INDEX+MATCH avoid this limitation.

A pivot table summarises data by grouping rows and columns and applying aggregate functions such as SUM, COUNT or AVERAGE.

A chart type must match the data: line for trends over time, bar/column for category comparison, pie only for parts of a single whole.

In a programming language, an algorithm is expressed as a sequence of statements with variables, conditions and loops; trace tables record variable values per step.

Test data should include normal, boundary and invalid cases; a boundary value such as the first or last valid index often reveals off-by-one errors.