Eduqas A500QS 1.1: Data structures
The free BugBot lessons that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
A data structure is a way of organising data in memory so a program can use it efficiently. At GCSE you met lists as one-dimensional arrays, two-dimensional arrays for the depth grid, and records for the robot's readings (module F3). At A level you need to say exactly what each structure is, how it is laid out in memory, and why you would choose it. This module works through the structures on the specifications, starting with the simplest: arrays, records and tuples.
- Arrays
- Two and three dimensions
- Records and fields
- Tuples and lists
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A3.1 Arrays, records and tuples Data structures
Arrays in one, two and three dimensions, records and fields, tuples and lists, and static structures. - A3.2 Abstract data types and stacks Data structures
ADTs, static and dynamic structures, and a stack with a top pointer: an undo stack for the robot's moves. - A3.3 Queues: linear, circular and priority Data structures
Front and rear pointers, wrapping round with MOD, and priority queues: a command queue for the robot. - A3.4 Linked lists Data structures
Nodes and pointers, the free list, and traversing, inserting and deleting: a route of waypoints. - A3.5 Hash tables Data structures
Hashing functions, collisions, rehashing by probing, chaining and load factor: finding markers fast. - A3.6 Dictionaries Data structures
Keys and values, dictionaries built on hash tables, and information retrieval: commands looked up by name. - A3.9 Project: mission control Data structures
A mission read from a file into a circular queue, moves looked up in a dictionary, position tracked as a vector, and an undo stack to… - A4.1 Graphs Trees and graphs
Vertices and edges; directed, undirected and weighted graphs; degree, the handshake lemma and typical uses. - A4.2 Adjacency matrix and adjacency list Trees and graphs
Two ways to store a graph, and choosing between them for dense and sparse graphs. - A4.5 Trees Trees and graphs
Trees as connected graphs with no cycles, rooted trees and their vocabulary, binary trees and typical uses. - A4.6 Binary search trees Trees and graphs
Building, inserting and searching, O(log n) against O(n), trees stored in arrays, and deletion in outline. - A4.7 Tree traversals Trees and graphs
Pre-order, in-order and post-order, the outline method, expression trees and what each traversal is for. - A4.8 Project: plan the route Trees and graphs
Model the mat as a graph, find the shortest route with breadth-first search, and drive it.
Try it on a robot
The task from A3.1 Arrays, records and tuples, running here. Change the program and press Run.
The specification is Eduqas's own document; this page says which of our lessons teach point 1.1 and is not endorsed by the board.