OCR H446 1.4.2: Data Structures
The free BugBot lessons that teach this point, a robot to try it on, and the past-paper questions that test it.
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.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 OCR's own document; this page says which of our lessons teach point 1.4.2 and is not endorsed by the board.