1.4.2 Data Structures

Question 1

Define mutable and immutable

Answer 1

Mutable means that a variable’s value can be changed without creating an entirely new variable. Immutable values cannot be changed.

Question 2

Define static and dynamic

Answer 2

A static data structure has a fixed length. A dynamic data structure’s length is not fixed.

Question 3

Define linear and non-linear

Answer 3

In a linear data structure elements are stored contiguously. They may be stored non-contiguously in a non-linear structure.

Question 4

Define zero-indexed

Answer 4

The first element in the data-structure is considered to be at position zero.

Question 5

Describe an Array

Answer 5

A mutable static data structure
An array is a data structure that contains a fixed number of values of one data type. The data is mutable and stored linearly. Each value is identified by a single index and it can be iterated by index.

Question 6

How do you identify the position of an element in 2D and 3D arrays?

Answer 6

Generally, when searching in a 2D array, you go down the rows, then across the columns. In 3D arrays, you go to the array number, then down, then along.

Question 7

Describe a record

Answer 7

A record is a data structure consisting of a fixed number of variables, called fields. Every field has an identifier and a data type. Each field in a record can have a different data type.

Question 8

Describe a list

Answer 8

Lists are dynamic data structures, consisting of ordered items where an item can occur more than once. They are non-contiguous and can hold multiple data types. Like arrays, it identifies values by an index.

Question 9

Describe a tuple

Answer 9

An ordered, immutable set of values. Values can be of differing data types.

Question 10

Describe a linked list

Answer 10

An ordered, linear dynamic data structure in which data can be stored non-contiguously and each element is called a node.

Question 11

Describe how pointers work in a linked list

Answer 11

Each node contains the data relating to the element and the pointer to the next node.
You must start from the first position indicated by the startpointer, then read the next pointer value and follow this pointer value to access the next data item, and so on…

Question 12

Describe graphs

Answer 12

Graphs are non-linear data structures made up of nodes. They are an abstract structure that represents complex, non-linear relationships.

Question 13

Define each term related to graphs

Answer 13

Nodes: The elements in a graph
Edges: The connections between nodes
Neighbours: When two nodes are connected by an edge
Degree: The number of other nodes that a node is connected to
A loop: An edge that connects a node to itself
A path: A sequence of nodes that are connected by edges
A cycle: A closed path, i.e. a path that starts and ends at the same node (and no node is visited more than once)

Question 14

Describe the difference between directed and undirected graphs

Answer 14

In a directed graph the edges can only be traversed in one direction. In an undirected graph the edges can be traversed in both directions.

Question 15

Describe a stack

Answer 15

A stack is an abstract data type that holds an ordered, linear sequence of items. It is a Last In, First Out (LIFO) structure. You need to maintain a pointer at the top of a stack. They may be static or dynamic.

Question 16

Define overflow and underflow in relation to stacks

Answer 16

Overflow - attempting to push onto a stack that is full
Underflow - attempting to pop from a stack that is empty

Question 17

State the main stack operations and their uses

Answer 17

push(data) = adds an element to the top of the stack
pop() = removes an element from the top of the stack
peek() = returns a copy of the element on the top of the stack without removing it
is_empty() = checks whether a stack is empty
is_full() = checks whether a stack is at maximum capacity when stored in a static (fixed-size) structure

Question 18

Describe a queue

Answer 18

A queue is an abstract data type that holds an ordered, linear sequence of items. It is a First in, First Out (FIFO) structure. You need to maintain a pointer at both the front and back of the stack.
They may be static or dynamic.
New elements are added to the back or rear of the queue. When an element is removed, the remaining elements do not move up to take the empty space.

Question 19

State the main queue operations and their uses

Answer 19

enqueue(data) = adds an element to the queue
dequeue() = returns an element from the front of the queue
is_empty() = checks whether the queue is empty
is_full() = checks whether the queue is at maximum capacity
(if the size of the queue is constrained)

Question 20

Describe a tree

Answer 20

A tree is an abstract data structure used to represent non-linear data. It is a connected, undirected graph consisting of nodes and edges. There are no cycles in trees so only one path between any 2 nodes.

Question 21

Define each term related to trees

Answer 21

Root = The first node, at the top. It does not have any incoming nodes.
Child = A node with incoming edges
Parent = A node with outgoing edges
Subtree = Subsection of a tree consisting of a parent and all the children of a parent
Leaf = A node with no children

Question 22

Describe a binary search tree

Answer 22

A binary tree is a type of tree in which each node has a​ maximum of two children.
Nodes are added in the order given, with the first item at the root. If the next item is less than the root, it is added to the left of the root, otherwise to the right. Apply the same rule at the root of each sub-tree.
​These are used to represent information for binary searches​.

Question 23

Describe a hash table

Answer 23

A hash table is an array that uses the hash function.
It is a data structure which will find any record in the dataset almost instantly, no matter how large the dataset is.
It enables access to data that is not stored in a structured manner.

Question 24

State the hash function and its use

Answer 24

The hash function is Address = key mod TableSize.

A hash function takes an input (key) and computes a numerical index within the bounds of a hash table. Large data sets can be organised so each record is assigned a unique address.

Question 25

Define collisions in hash tables

Answer 25

When a key creates a hash value that references a position that is already occupied.

Question 26

Describe linear probing/open addressing

Answer 26

This places the data in the next free position in a hash table if a collision occurs. This is done through probing (incrementing) either sequentially or by a skip factor (interval) until an empty position is found. (It's best to have the table size as a prime number to avoid looping if a skip factor is used)

Question 27

State the advantages and disadvantages of linear probing

Answer 27

**Advantages** = This technique is simple and, because it probes adjacent slots, it often benefits from CPU caching, which can make it fast in practice when the table isn’t too full. **Disadvantage** = Linear probing suffers from a problem called primary clustering. This means that as keys collide and probe linearly, long sequences of occupied slots tend to build up. When a new key hashes into this cluster, it has to probe further down the sequence, potentially making the cluster even longer. This significantly slows down insertions and searches as the table gets fuller.

Question 28

Describe chaining/closed addressing

Answer 28

Chaining is used to avoid collisions, by storing multiple elements in the same slot using a linked list. E.g. [10 → 24 → 31 → 17 → 45 → 3]

Question 29

What are the benefits of using the hash function/a hash table?

Answer 29

-It distributes keys uniformly -It's fast to compute -It minimises collisions