Data Structures and Data Representation
Data Structures and Data Representation tests two linked skills: picking the structure whose cost matches the operation, and converting faithfully between binary, hexadecimal, two's complement, floating point and character encodings.
Structures and their costs
- Stack: LIFO - function calls, undo, bracket matching, DFS. Queue: FIFO - BFS, print queues, scheduling.
- Array: O(1) indexed access, O(n) insertion in the middle. Linked list: O(1) insert at a known node, O(n) search, extra pointer memory.
- BST: average O(log n) search and insert; O(n) if it degenerates into a chain; in-order traversal yields sorted keys.
- Graph: adjacency matrix O(V²) memory, edge lookup O(1); adjacency list O(V+E), better for sparse graphs.
- Hash table: average O(1), collisions handled by chaining or open addressing; worst case O(n).
Representation
- n bits give 2^n patterns; unsigned range 0 … 2^n−1.
- Two's complement: invert all bits, add 1. In 8 bits the range is −128…127, and subtraction is addition of the negated value.
- IEEE 754 stores sign, biased exponent and mantissa; values such as 0.1 have no exact binary form, so equality comparisons on floats are unsafe.
- Text: ASCII is 7-bit; UTF-8 uses 1–4 bytes and is backward compatible with ASCII; Polish letters need UTF-8 or ISO-8859-2.
Worked example
Represent −5 in 8-bit two's complement. 5 = 0000 0101. Invert: 1111 1010. Add 1: 1111 1011. As unsigned that is 251, and 251 − 256 = −5, which confirms the sign bit carries weight −128.
Traps
- Mixing sign-magnitude (1000 0101) with two's complement; forgetting the +1.
- Treating 1111 1111 as −0; it is −1.
- Confusing bits with bytes, or kB (1000) with KiB (1024).
- Assuming ASCII covers ą, ł, ż - it does not.
- Ignoring overflow: 127 + 1 in 8-bit signed wraps to −128.