4.2 Fundamentals of data structures

Data structures and abstract data types

Data structures

Content	Additional information
Be familiar with the concept of data structures.	It may be helpful to set the concept of a data structure in various contexts that students may already be familiar with. It may also be helpful to suggest/demonstrate how data structures could be used in a practical setting.

Single- and multi-dimensional arrays (or equivalent)

Content	Additional information
Use arrays (or equivalent) in the design of solutions to simple problems.	A one-dimensional array is a useful way of representing a vector. A two-dimensional array is a useful way of representing a matrix. More generally, an n-dimensional array is a set of elements with the same data type that are indexed by a tuple of n integers, where a tuple is an ordered list of elements.

Fields, records and files

Content	Additional information
Be able to read/write from/to a text file.
Be able to read/write data from/to a binary (non-text) file.

Abstract data types/data structures

Content	Additional information
Be familiar with the concept and uses of a: queue stack graph tree hash table dictionary vector.	Be able to use these abstract data types and their equivalent data structures in simple contexts. Students should also be familiar with methods for representing them when a programming language does not support these structures as built-in types.
Be able to distinguish between static and dynamic structures and compare their uses, as well as explaining the advantages and disadvantages of each.
Describe the creation and maintenance of data within: queues (linear, circular, priority) stacks hash tables.

Content

Additional information

Be familiar with the concept and uses of a:

queue
stack
graph
tree
hash table
dictionary
vector.

Be able to use these abstract data types and their equivalent data structures in simple contexts.

Students should also be familiar with methods for representing them when a programming language does not support these structures as built-in types.

Be able to distinguish between static and dynamic structures and compare their uses, as well as explaining the advantages and disadvantages of each.

Describe the creation and maintenance of data within:

queues (linear, circular, priority)
stacks
hash tables.

Queues

Content	Additional information
Be able to describe and apply the following to linear queues, circular queues and priority queues: add an item remove an item test for an empty queue test for a full queue.

Content

Additional information

Be able to describe and apply the following to linear queues, circular queues and priority queues:

add an item
remove an item
test for an empty queue
test for a full queue.

Stacks

Content	Additional information
Be able to describe and apply the following operations: push pop peek or top test for empty stack test for stack full.	Peek or top returns the value of the top element without removing it.

Content

Additional information

Be able to describe and apply the following operations:

push
pop
peek or top
test for empty stack
test for stack full.

Peek or top returns the value of the top element without removing it.

Graphs

Content	Additional information
Be aware of a graph as a data structure used to represent more complex relationships.
Be familiar with typical uses for graphs.
Be able to explain the terms: graph weighted graph vertex/node edge/arc undirected graph directed graph.
Know how an adjacency matrix and an adjacency list may be used to represent a graph.
Be able to compare the use of adjacency matrices and adjacency lists.

Trees

Trees (including binary trees)

Content	Additional information
Know that a tree is a connected, undirected graph with no cycles.	Note that a tree does not have to have a root.
Know that a rooted tree is a tree in which one vertex has been designated as the root. A rooted tree has parent-child relationships between nodes. The root is the only node with no parent and all other nodes are descendants of the root.
Know that a binary tree is a rooted tree in which each node has at most two children.	A common application of a binary tree is as a binary search tree.
Be familiar with typical uses for rooted trees.

Hash tables

Content	Additional information
Be familiar with the concept of a hash table and its uses.	A hash table is a data structure that creates a mapping between keys and values.
Be able to apply simple hashing algorithms.
Know what is meant by a collision and how collisions are handled using rehashing.	A collision occurs when two key values compute the same hash.

Dictionaries

Content	Additional information
Be familiar with the concept of a dictionary.	A collection of key-value pairs in which the value is accessed via the associated key.
Be familiar with simple applications of dictionaries, for example information retrieval, and have experience of using a dictionary data structure in a programming language.	Information retrieval: For example, the document 'The green, green grass grows' would be represented by the dictionary: {‘grass’ : 1, ‘green’ : 2, ‘grows’ : 1, ‘the’ : 1} ignoring letter case.

Content

Additional information

Be familiar with the concept of a dictionary.

A collection of key-value pairs in which the value is accessed via the associated key.

Be familiar with simple applications of dictionaries, for example information retrieval, and have experience of using a dictionary data structure in a programming language.

Information retrieval:

For example, the document 'The green, green grass grows' would be represented by the dictionary:

{‘grass’ : 1, ‘green’ : 2, ‘grows’ : 1, ‘the’ : 1} ignoring letter case.

Vectors

Content	Additional information
Be familiar with the concept of a vector and the following notations for specifying a vector: [2.0, 3.14159, -1.0, 2.718281828] 4-vector over ℝ written as ℝ⁴ function interpretation 0 ↦ 2.0 1 ↦ 3.14159 2 ↦ -1.0 3 ↦ 2.718281828 ↦ means maps to That all the entries must be drawn from the same field, eg ℝ.	A vector can be represented as a list of numbers, as a function and as a way of representing a geometric point in space. A dictionary is a useful way of representing a vector if a vector is viewed as a function. f : S → ℝ the set S = {0,1,2,3} and the co-domain, ℝ, the set of Reals For example, in Python the 4-vector example could be represented as a dictionary as follows: {0:2.0, 1:3.14159, 2:-1.0, 3:2.718281828}
Dictionary representation of a vector.	See above.
List representation of a vector.	For example, in Python, a 2-vector over ℝ would be written as [2.0,3.0].
1-D array representation of a vector.	For example in VB.Net, a 4-vector over ℝ would be written as Dim example(3) As Single.
Visualising a vector as an arrow.	For example a 2-vector [2.0, 3.0] over ℝ can be represented by an arrow with its tail at the origin and its head at (2.0, 3.0).
Vector addition and scalar-vector multiplication.	Know that vector addition achieves translation and scalar-vector multiplication achieves scaling.
Convex combination of two vectors, u and v.	Is an expression of the form αu + βv where α, β ≥ 0 and α + β = 1
Dot or scalar product of two vectors.	The dot product of two vectors, u and v, u = [u₁, …., u_n ] and v = [v₁, ….., v_n] is u ∙ v = u₁v₁ + u₂v₂ + …… + u_nv_n
Applications of dot product.	Finding the angle between two vectors.

Previous
4.1 Fundamentals of programming

Next
4.3 Fundamentals of algorithms