Relevant to Both Papers
Data Structures
1/2.1 (Year 1) Arrays (of up to 3 dimensions), records, lists, tuples.
● Candidates should be able to describe what is meant by arrays (up to 3 dimensions),
records, lists and tuples. They are expected to be able recognise when they can be used
and incorporate them in their programs to store data.
● Candidates should be able to describe what is meant by arrays (up to 3 dimensions),
records, lists and tuples. Candidates are expected to be able recognise when they can be
used and incorporate them in their programs to store data.
● Candidates should have an understanding of the purpose and use of a record structure to
store data of different data types in a program. Candidates should have experience of
using records to store, search, manipulate and retrieve data.
● Candidates should have an understanding of the purpose and use of a list to store data in
a program.
● Candidates should have experience of using lists to store, search, manipulate and retrieve
data.
● Candidates should have an understanding of the purpose and use of tuples to store data in
a program.
● Candidates should have experience of using tuples to store, search, manipulate and
retrieve data.
June 2018 Q6 a ii, iii [6, 3 marks] Complete, Write
1/2.2 (Year 1 & 2) The following structures to store data: linked-list, graph (directed and undirected), stack, queue,
tree, binary search tree, hash table (Year 2).
● Candidates need to have an understanding of the behaviour of linked-lists, graphs, stacks,
queues, trees, binary search trees and hash tables.
● Candidates need to have an understanding of the behaviour of stacks and queues (i.e. LIFO
and FIFO).
June 2017 Q3 c, d [5, 5 marks] Complete, Describe
June 2018 Q5 a, b, c [4, 4, 2, 3 marks] Show, Describe, Identify, Describe
June 2018 Q6 b i [2 marks] Define
June 2018 Q6 b vi, vii [5, 2 marks] Write, Describe
June 2019 Q1 a, bii [2, 3 marks] Explain, Complete
June 2019 Q2 a i [1 mark] State
Nov 2020 Q1 b, c [1, 1 mark] State, State
Nov 2020 Q1 f [4 marks] Give
Nov 2020 Q5 a, b [2, 5 marks] State, Show
Nov 2020 Q5 e [3 marks] Describe
Nov 2020 Q6 d i [3 marks] Identify
Page 1 of 57
,Data Structures (abstract data types) – Conceptual so not physical in
computer [up to programmer on how to implement it].
Info:
- Up to programmer on which data types to use and how.
- Faced with problem and find best way to make solution.
-
Arrays = Series of values in memory – must specify an index to find a value. Can sort;
Strings = Arrays of characters. Null character 0 at end of string to denote end.
Strcat = takes 2 strings and copies second to the end of the first e.g. forename and surnames;
Matrix = like 2d. e.g. sub arrays. Can make as large as you want;
Struct = Bundled data – compound data e.g. print 2 variables at once by having them together in a
bundle. Can do [x].name for specific thing;
Node/node struct = variable with a pointer. Pointer is another memory address held in a memory
address to point to another node etc. So they are linked.
Linked lists = dynamic bunch of nodes and pointers (doubly linked lists, )
Queue = in order. Waiting longest = served first (FIFO – First-In First-Out)
2.30 Stacks = LIFO (Last-In First-Out). Or FILO;
Info:
- Place data on top of stack;
- Data on top comes out. Aka LIFO;
- E.g. back button on browser pages are in a stack, undo/redo = describe and explain q;
- Hold return addresses when subroutines are called = justify q;
- Static structure = once defined cannot change e.g. size of stack;
- Dynamic structure = can change after defining;
- 6 operations: .push (put into stack), .isEmpty (check if stack is empty), .peek (look what
went in last), .pop (takes top item in stack off), .size (checks how many items are in stack),
.isFull (check if stack is full)
- StackOverflow = when try to .push when stack is static and full we get a stackoverflow
error
- StackUnderflow = when try to .pop when empty we get a stackunderflow error
A pointer points to the next available memory location in the stack. It increments by 1 before
pushing data. And decreases by 1 before/after? popping data.Data will be added to the memory
Page 2 of 57
,location of the pointer when pushed and it will be taken out of the memory location when
popped.
Pop() Pop() Push(“A”) ***in quote marks
Explain how a stack data structure is used to handle the execution of multiple subroutines?
• Local variables are pushed via subroutine to stack;
• return addresses or instruction pointers pushed to stack at the end of subroutine;
• going back subroutines can traverse stack frame;
• Returning control = pops and return addresses;
• Next subroutine cleans prev stack when returning control;
•
Trees = multiple pointers. Like a tree. Top node is a root. Other nodes are children nodes.
Graph Data = can point to anything. So not a tree.
Depth First Search = goes deep before going broad (to neighbours)
Breadth First Search = Goes broad (to neighbours) before going deep
Red-Black Trees & Heaps =
Page 3 of 57
,Hash Tables = Key Values.
Graphs
Edge – Describes how the nodes are linked together;
Nodes – Something that we are representing.
Bidirectional – Can go both ways;
Undirected graphs – Assume that you can travel both ways;
Directed graphs – Direction of travel between 2 nodes can be bi or not.
Weighted – Measurement of some form of an edge e.g. distance etc;
Unweighted – No measurement so all of equal importance.
Page 4 of 57
,Layout of nodes on a graph doesn’t matter. Only how they are connected.
Adjacency Matrix:
A 2d array can be used to store information about a directed or undirected graph.
Each of the rows / column represents a node. A value stored at intersection indicates that there is
an edge connecting the 2 nodes.
Represented as a 2D array:
Matrix:
( [ ],
[ ])
Read from left first then
top. So, node 0 then 1 has
an arrow so is a 1 as has a
connection. But cannot
go the other way so is a 0.
Adjacency List:
A list of all the nodes is created. Each node points to a list of all the adjacent nodes.
Can be implemented as a list of dictionaries.
Uses much less memory as don’t need to store 0s. So, only stores meaningful data.
As a dictionary (for WEIGHTED graphs only):
Key = Node;
Value = Weight of edge.
Depth First traversal:
To find a specific value in a graph;
Page 5 of 57
,Go down as far as possible on the left side then go back up one and go as left as possible etc.
Breadth First Traversal:
Visits top node, then next level down etc. So, orange then green then blue (as seen below);
Trees:
All trees are a graph but not all graphs are trees.
Tree – no circular connections only a branch to another node.
Key terms:
Page 6 of 57
,Uses:
Binary search Tree: 17,8,4,12,22,19,14
Only ever 2 children coming from each
node (like 0 and 1 in binary).
Traversing Binary trees (3 ways):
Pre Order Traversal:
Draw the dot at 9 oclock.
Draw the dot at 6 oclock.
Draw the dot at 3 oclock.
Page 7 of 57
,Summary:
Hashing:
Video:
Page 8 of 57
,collisions
Page 9 of 57
, Hash tables:
How is data inserted -
How is data accessed – via the index of an item
Index can be calculated by the data to be stored itself
How to write/read:
• Adding values,
• dividing by the number in the array,
• use the remainder as index
Hash functions – 1-way function
Hash map – key value pairs
Hashing algorithm – calculation used
e.g.
Common hashing algorithms – address = key Mod n (n number of available addresses)
Take remainder
e.g.
folding phone numbers…
If an index is the same for both this is called a collision – if this happens place in the next
available position linearly this is called OPEN ADDRESSING
linear probing – probing for an available slot after finding the original position. Will circle around
to front if needed.
Find by a linear search after finding the original position.
Load factor = total number of items stored/size of the array
Chaining – separate linked list connected to original position that has nodes of the same value for
the original array.
To find use index for array then traverse linked list as normally would.
Page 10 of 57
