1.2 Fundamentals of data structures

Question 1

What is a data structure?

Answer 1

A data structure is any method used to store data in an organised and accessible format

Question 2

What is an abstract data type?

Answer 2

A conceptual model of how the data is stored and the operations that can be performed upon them

Question 3

Define queue

Answer 3

A data structure where the first item added is the first item removed

Question 4

Define stack

Answer 4

A data structure where the last item added is the first item removed

Question 5

What is a static data structure?

Answer 5

A method of storing data where the amount of data stored and the memory used to store it is fixed

Question 6

What is a dynamic data structure?

Answer 6

A method of storing data where the amount of data stored and memory used to store it will vary as the program is being run

Question 7

Define heap

Answer 7

A pool of unused memory that can be allocated to a dynamic data structure

Question 8

Define stack frame

Answer 8

A collection of data about a subroutine call

Question 9

Define call stack

Answer 9

A special type of stack used to store information about active subroutines and functions within a program

Question 10

Define interrupt

Answer 10

A signal sent by a device or program to the processor requesting its attention

Question 11

Define recursion

Answer 11

The process of a subroutine calling itself

Question 12

Define the 3 different types of queue

Answer 12

• Linear: a first in first out structure organised as a line of data such as a list
• Circular: a first in first out structure implemented as a ring where the front and rear pointers can wrap around from the end to the start of the array
• Priority: a variation of a first in first out structure where some data may leave out of sequence if it has a higher priority than other items

Question 13

Define graph

Answer 13

A mathematical structure which models the relationship between pairs of objects

Question 14

Define vertex

Answer 14

An object in a graph, this can also be known as a node

Question 15

Define arc

Answer 15

A join or relationship between two nodes, this can also be known as an edge

Question 16

What is a weighted graph?

Answer 16

A graph that has a data value labelled on each edge

Question 17

Define directed graph

Answer 17

A directed graph is a graph where the relationship between nodes is one way

Question 18

Define unirected graph

Answer 18

A graph where the relationship between vertices is two way

Question 19

Define adjacency list

Answer 19

A data structure that stores a list of nodes with their adjacent nodes

Question 20

Define adjacency matrix

Answer 20

A data structure set up as a two dimensional array or grid that shows whether there is an edge between each pair of nodes

Question 21

What are the differences between an adjacency list and an adjacency matrix?

Answer 21

• An adjacency list only stores data when there is an edge so it requires less memory than an adjacency matrix which stores a value for every combination of adjacencies
• In an adjacency matrix it is faster to check if an adjacency exists as all possible adjacencies are stored, whereas in adjacency list you have to check the whole list to see if it exists
• Adjacency lists are more suitable for graphs with few nodes (sparse graphs) and adjacency matrices are more suitable for graphs with more nodes (dense graphs)

Question 22

Define tree

Answer 22

A data structure similar to a graph with no loops

Question 23

Define root

Answer 23

The starting node in a rooted tree structure from which all other nodes branch off

Question 24

Define parent

Answer 24

A type of node in a tree where there are further nodes below it

Question 25

Define child

Answer 25

A node in a tree that has nodes above it in the hierarchy

Question 26

Define leaf

Answer 26

A node that does not have any other nodes beneath it

Question 27

What is a binary tree?

Answer 27

A tree where each node can only have up to 2 child nodes attached to it

Question 28

What are the uses of a tree?

Answer 28

• Can be used to store data that has an inherent hierarchical structure
• Are dynamic so it is easy to add and delete nodes
• Easy to search and sort with traversal algorithms
• Can process syntax of statements so commonly used in compiling code

Question 29

Define hash table

Answer 29

A data structure that stores key / value pairs based on an index calculated from an algorithm

Question 30

Define key / value pair

Answer 30

The key and its associated data

Question 31

What is a hashing algorithm?

Answer 31

Code that creates a unique index from given items of key data

Question 32

How do hash tables function?

Answer 32

A hashing algorithm is carried out on the piece of data / key, which gives a value that acts as an index for that data item within the array of data. The same key can then be put through the hashing algorithm to look up and locate data within the hash table

Question 33

What are some uses of hashing algorithms?

Answer 33

• Used to create indices for databases for quick storage and retrieval of data
• Used to generate memory addresses where data will be stored
• Used to encrypt data
• Used to index keywords and identifiers so the compiler can easily access them during compilation

Question 34

Define collision

Answer 34

When a hashing algorithm produces the same index for two or more different keys

Question 35

Define clustering

Answer 35

When a hashing algorithm produces indices that are not randomly distributed

Question 36

Define load factor

Answer 36

The ratio of how many indices are available to how many there are in total

Question 37

Define index

Answer 37

The location where values will be stored, calculated from the key

Question 38

Define chaining

Answer 38

A technique for generating a unique index when there is a collision by adding the key / value to a list stored at the same index

Question 39

What are the criteria for a suitable hashing algorithm?

Answer 39

• Numeric value generated to act as the index
• Generates unique indices
• Generates a uniform spread of indices to reduce clustering
• Enough possible indices to store the volume of data
• Balance issues of speed with complexity

Question 40

What are the methods for handling collisions?

Answer 40

• Chaining: A list is created at that index which contains all key / value pairs which are to be stored at that index
• Rehashing: The algorithm is run again or a new algorithm is run until a new, unique index is created

Question 41

Define rehashing

Answer 41

The process of running the hashing algorithm again when a collision occurs

Question 42

Define magnitude of a vector

Answer 42

One of the two components of its vector, refers to the size of the vector

Question 43

Define scalar

Answer 43

A real value used to multiply a vector to scale the vector

Question 44

Define the dot product

Answer 44

The process of combining 2 vectors to calculate a single number, for vectors (a,b) and (c,d), the dot product is given by ac + bd

Question 45

Define convex combination

Answer 45

A method of multiplying vectors that produces a resulting vector within the convex hull. For 2 vectors a and b, this is given by c (convex combination) = pa + qb, where p and q are both greater than 0, and p + q = 1

Question 46

Define vector space

Answer 46

A collection of elements that can be formed by adding or multiplying vectors together

Question 47

Define convex hull

Answer 47

A spatial representation of the vector space between two vectors