Eduqas A-Level Computer Science data structures and algorithms: arrays, trees, searching, sorting and Big-O made exam-ready

What this section actually demands

The data structures and algorithms part of Component 1 (specification sections 2.1 and 2.2) is the most algorithmic of the course. Eduqas rewards two things: knowing each structure's operations and complexity, and being able to trace algorithms by hand with shown working. Almost every question pairs a structure or algorithm with a trace and a complexity statement.

This guide walks through the topics in order and sets out the exam patterns Eduqas repeats. Each topic has a matching dot-point page with practice; this overview ties them together.

Data structures

Static structures (arrays, records, tuples and sets) are stored contiguously and accessed directly, so array access is $O(1)$ via the formula $\text{base} + i \times \text{element size}$. Dynamic structures trade fixed size for flexibility: a stack is LIFO (push and pop a top pointer), a queue is FIFO (enqueue at the rear, dequeue at the front), a circular queue wraps with $\bmod \text{size}$ to reuse slots, and a linked list stores nodes joined by pointers so it grows and shrinks freely at $O(n)$ access.

Trees, graphs and hash tables organise data for search and relationships. A binary search tree orders keys (smaller left, larger right) for $O(\log n)$ search, with in-order, pre-order and post-order traversals. A graph is stored as an adjacency matrix (dense) or adjacency list (sparse). A hash table maps keys to indices for $O(1)$ average lookup, resolving collisions by chaining or open addressing.

Algorithms

Searching uses linear search ($O(n)$, any list) or binary search ($O(\log n)$, sorted only), while graph traversals use breadth-first (a queue, shortest paths) or depth-first (a stack, deep exploration). Sorting ranges from the quadratic bubble and insertion sorts ($O(n^2)$, in-place, simple) to the divide-and-conquer merge and quick sorts ($O(n \log n)$ on average). Recursion (a base case plus a recursive case using the call stack) expresses these divide-and-conquer methods, and Big-O notation measures how each algorithm scales.

How this section is examined

A typical Eduqas profile for sections 2.1 and 2.2:

• Structure traces. Push/pop a stack; enqueue/dequeue a circular queue; insert/delete a linked-list node; build a BST and read a traversal.
• Searching and sorting. Trace a binary search with the middle indices; show one pass of bubble or insertion sort; describe the split-and-merge of merge sort.
• Recursion. Write a short recursive function with a clear base case; describe how the call stack is used.
• Complexity. State and order Big-O classes; justify why an algorithm is $O(n^2)$ or $O(n \log n)$.

Check your knowledge

A mix of recall and trace questions covering the section. Attempt them under timed conditions, then check against the solutions.

1. Give the formula for the address of element $i$ in a 1D array with base address $B$ and element size $s$. (1 mark)
2. State the order of removal for a stack and for a queue. (2 marks)
3. What output order does an in-order traversal of a binary search tree produce? (1 mark)
4. State the time complexity of binary search and its precondition. (2 marks)
5. State the worst-case complexity of bubble sort and the average complexity of merge sort. (2 marks)
6. What two parts must every correct recursive subroutine contain? (2 marks)