I85PREP
⌘ K
GACE Computer Science - independent content foundations study materials
GACE Computer Science - independent content foundations study resources

GACE Computer Science - independent content foundations: Data representation and structures

GACE Computer Science - independent content foundations · Work through your exam, one topic at a time.

All guide sections

Data representation and structures

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, MP3) 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).