Data structures (1.4.2)
Navigate to resources by choosing units within one of the unit groups shown below.
Delivery guides are designed to represent a body of knowledge about teaching a particular topic and contain:
- Content: A clear outline of the content covered by the delivery guide;
- Thinking Conceptually: Expert guidance on the key concepts involved, common difficulties students may have, approaches to teaching that can help students understand these concepts and how this topic links conceptually to other areas of the subject;
- Thinking Contextually: A range of suggested teaching activities using a variety of themes so that different activities can be selected which best suit particular classes, learning styles or teaching approaches.
a) Arrays (of up to 3 dimensions), records, lists, tuples.
b) The following structures to store data: linked-list, graph (directed and undirected), stack, queue, tree, binary search tree, hash table.
c) How to create, traverse, add data to and remove data from the data structures mentioned above. (NB this can be either using arrays and procedural programming or an object-oriented approach).
The websites provided within the activities are for students to self-teach or as revision aids. Some of the websites also give example questions that have been developed specifically for delivering this knowledge at A-Level standard.
Designed to be part of a day course on data structures in Python. 'Python 1' website link covers Stacks, Queues, Linked Lists and Binary Trees.
Implementations in Python 3.
'Python 2' website link covers Linked lists, Stacks, Queues, Trees in lots of detail.
Implementations in Python 3.
'Python 3' website link provides a very detailed in-depth look at Lists, Dictionaries, Linked lists, Stacks, Graphs, trees, queues and hashing.
Implementations in Python 3.
Data structures in relation to Data Types from 1.4.1 outline the relationships between how data is related and how this data can be manipulated. Typical data structures will have specific ways to add, insert, remove, get the next or last element and to locate elements.
It is useful to draw parallels between data structures and their real-life counterparts. For instance, you could say that:
- Arrays are a bit like a CD rack that has numbers on.
- A stack is a lot like a stack of books in that if you want to get to the books at the bottom you can just ‘pop’ books off the stack until you reach the bottom. This is thought of as a LIFO system (last in first out), whereas a Queue – just like a real queue – is FIFO (First in first out) just like going on a rollercoaster.
- Trees can be related to the DOM (Document Object Model) hierarchy, where a page contains many HTML elements that are interrelated.
- Graphs can be found in Networking data models.
- A linked-list is a lot like a scavenger hunt, where you have to find each clue, and then pick up the next clue that ‘points’ to the next clue.
Common misconceptions or difficulties students may have
Learning about data structures is similar to learning about data types. For a lot of students these concepts will be brand new and can only be related to computers, but some can be expressed in terms of real life problems such as queues.
Students may find that the differences between lists and tuples are hard to notice, but the main differences are that tuples cannot be altered through insertion, removal or updating elements whereas lists can. Lists use square brackets and tuples use curved brackets.
Students’ learning and understanding will benefit through having worked-through examples to reference and being able to implement the data structures themselves.
Conceptual links to other areas of the specification – useful ways to approach this topic to set students up for topics later in the course.
Data structures are usually the next field to study after students have a full grasp of Data Types. It would be unusual to study these in reverse order.
Unless the student has studied computer science before, it is unlikely that they have come across many of the data structures present since we are unlikely to encounter them outside the realm of the subject area.
This activity gets students to ‘act out’ linear and binary searches as well as using hashing through a battleships style activity where students must work in pairs (see 'Searching algorithms' link). This activity would be useful before implementing binary trees and hashing in code.
This is in many different languages along with other interpretations and links to similar activities.
Covers linear search, binary search, hashing.
Provided is a 'Questions worksheet' which gives some questions based on some of the topics that have been covered in order to test students (see Teacher resource 1 for answers).
Links have been given in the activities within ‘Curriculum content’ section to enable students to find answers if they get stuck.
'DS cards' resource is given as a set of resources that you can use with students to help them visualise how different data structures work.
You could get students to cut out the cards given at the top of the document and then ask for groups of two to spend a minute thinking how they could use the materials to represent that data structure. When you walk around the class, the pair needs to explain what is going on and you can help to address any misconceptions asking questions such as “how would you go about deleting an item from a linked-list?”.
'Tree Traversal' resource is designed to help students understand tree traversal algorithms pre-order, in-order and post-order.
Students can construct their own trees using the cut-outs and then write the tree down using the templates beneath.
They can then use the table to write down the traversal output for each tree or can use the trick detailed in the worksheet for determining the right order using dots on the nodes.
For more information see both the Tree Traversal 1 (Wikipedia) and 2 (Prof. Robert C. Holte - University of Ottowa) links provided.
OCR’s resources are provided to support the teaching of OCR specifications, but in no way constitute an endorsed teaching method that is required by the Board and the decision to use them lies with the individual teacher. Whilst every effort is made to ensure the accuracy of the content, OCR cannot be held responsible for any errors or omissions within these resources. We update our resources on a regular basis, so please check the OCR website to ensure you have the most up to date version.
© OCR 2015 - This resource may be freely copied and distributed, as long as the OCR logo and this message remain intact and OCR is acknowledged as the originator of this work.