North Rhine-Westphalia Abitur Computer Science - independent foundations: Data representation, arrays, lists, trees and graphs

Data representation and structures

This domain covers how numbers, text, images and sound are encoded in binary, and how collections of data are organised so operations are efficient. Calculations - file sizes, two's complement ranges, normalised floating point - are examined as much as definitions.

Encoding rules

• Two's complement: with n bits the range is −2ⁿ⁻¹ to 2ⁿ⁻¹−1; negation is invert-then-add-one.
• BCD stores one decimal digit per nibble, used where display accuracy matters (clocks, currency).
• Bitmaps: file size = width × height × colour depth ÷ 8 bytes. Sound: size = sample rate × resolution (bits) × channels × duration ÷ 8.
• Compression: lossless (RLE, Huffman) preserves every bit; lossy (JPEG, MP 3) discards detail the eye or ear is less likely to notice.

Floating point

A binary float is mantissa × 2^exponent. In two's complement, a value is normalised when the two most significant mantissa bits differ - 01… for a positive number, 10… for a negative one. A longer mantissa gives more precision; a longer exponent gives more range.

Worked example

Store −3.25 using an 8-bit two's complement mantissa and a 4-bit two's complement exponent.

1. −3.25 = −11.01₂.
2. Normalise: shift the point two places left → −0.1101 × 2².
3. Mantissa: +0.1101000 is 01101000; invert → 10010111, add 1 → 10011000.
4. Exponent: 2 = 0010.
5. Check: 10011000 as a fraction = −1 + 0.125 + 0.0625 = −0.8125, and −0.8125 × 2² = −3.25 ✓.

The top two mantissa bits are 1 and 0, so the value is normalised.

Data structures

Arrays give O(1) indexed access but fixed size; linked lists insert and delete in O(1) once the position is known but need sequential traversal; stacks are LIFO (function calls, undo); queues are FIFO (buffers, scheduling); binary search trees give O(log n) search when balanced; hash tables give near-constant lookup; graphs model arbitrary relationships.

Traps that cost marks

• Dropping the binary point position when normalising, or normalising a positive number to 00….
• Forgetting that doubling colour depth doubles file size while resolution stays the same.
• Stating that a queue is LIFO, or that a stack is FIFO.
• Omitting the +1 step in two's complement negation.
• Confusing resolution (pixels) with colour depth (bits per pixel).

In a standard unit-cost classroom model, array index access is constant time, while insertion in the middle can require shifting many elements. A linked list can update links in constant time when the relevant node is already known, but locating that node can require a linear scan. A balanced binary-search tree supports logarithmic-height operations under its balance invariant; an arbitrary search tree can degenerate. Graph traversal costs depend on representation: with adjacency lists, breadth-first traversal takes order V plus E over the visited graph. A hash-table lookup is expected constant time only under suitable hashing and load assumptions; the worst case need not be constant. State the operation and model before comparing structures.