Fundamentals of Data Structures

Question 1

Define ‘static data structure’.

Answer 1

A collection of data in memory that has a fixed storage size determined at compile-time.

Question 2

Define ‘dynamic data structure’.

Answer 2

A collection of data in memory that has the flexibility to grow or shrink at run-time.

Question 3

Explain two differences between static and dynamic data structures.

Answer 3

Static data structures may waste memory if the number of data items stored is less than the allocated storage space. However, dynamic data structures only take up the amount of storage space required for the actual data.

Static data structures store data in contiguous memory locations, dynamic data structures do not.

Question 4

Which type of data structure requires a pointer.

Answer 4

Dynamic data structures require memory to store a pointer to the next item which static data structures do not require.

Question 5

What are the three types of queues?

Answer 5

Priority
Circular
Linear

Question 6

What type of data structure is a stack

Answer 6

LIFO
Last item in is the first item out

Question 7

What is an abstract data type?

Answer 7

A system described in terms of its behaviour, without regard to its implementation.

Question 8

What type of data structure is a queue

Answer 8

FIFO
First item in is the first item out

Question 9

How many pointers does a queue require?

Answer 9

Two pointers
One for the front of the queue, and another for the back.

Question 10

How many pointers does a stack require?

Answer 10

One pointer
It points to the top of the stack.

Question 11

What operations are implemented for a stack?

Answer 11

Push (add item)
Pop (remove item)
Peek (view item)

Question 12

Describe the algorithm for insertion into a stack.

Answer 12

Check if stack is full.
If the stack is full report an error and stop.
Increment stack pointer.
Insert new data item into location pointed to by stack pointer and stop.

Do the opposite for deletion (empty, decrement). To peek, copy data item from location pointed to by stack pointer.

Question 13

Describe the algorithm for insertion into a queue.

Answer 13

Check if queue is full.
If the queue is full report an error and stop.
Increment back pointer.
Insert new data item into location pointed to by back pointer and stop.

Question 14

Describe the algorithm for deletion/reading from a queue.

Answer 14

Check if queue is empty.
If the queue is empty report an error and stop.
Copy data item from location pointed to by front pointer. (reading only)
Increment front pointer and stop. (deletion only)

Question 15

What are the components of a graph

Answer 15

Vertex
Edge

Question 16

State two advantages of using an adjacency matrix.

Answer 16

Very quick and easy to work with
Adding new edges / checking for presence of edges is simple and quick using a 2D array.

Question 17

State two disadvantages of using an adjacency matrix.

Answer 17

If the graph is sparse (lots of nodes but very few edges), it results in lots of wasted memory.

Implementing it as a 2D array can make it difficult to add / delete nodes.

Question 18

What is the best way to store a sparse graph?

Answer 18

Adjacency list, they are very space efficient.

Question 19

State the components of a tree.

Answer 19

Root node
Children nodes
Branches
Leaf nodes

Question 20

What are the properties of a binary tree.

Answer 20

No more than two children per node.
Each node consists of data, a left pointer, and a right pointer.

Question 21

What is an array?

Answer 21

Stores data of the same type in contiguous memory locations.

Question 22

What is a hash table?

Answer 22

A data structure that maps keys to values using a hash function.
It is used to insert, look up, and remove key-value pairs quickly.

Question 23

What is a collision when working with hash tables?

Answer 23

Collisions happen when two or more keys point to the same array index.

Question 24

What does a good hash function do?

Answer 24

Keep collisions to a minimum.

Question 25

How are collisions handled in a hash table? Describe two methods

Answer 25

Open addressing, look for the next available empty space in the table. This may cause clustering.

Separate chaining, a linked list of objects that hash to each slot in the hash table is present. Two keys are included in the linked list if they hash to the same slot. This is good for handling several collisions.

Question 26

Describe the algorithm for adding a value to a hash table.

Answer 26

Feed in key to hash function.
Go directly to array index.
If location is empty insert the value.
Otherwise, follow linked list in sequence until free space is found.
Insert value.

Question 27

Describe the implementation of a dictionary.

Answer 27

Stores groups of objects using key value pairs. Each key has a single value associated with it, which is returned when the key is supplied.

Question 28

State a use of dictionaries

Answer 28

Dictionary encoding

Question 29

How can a vector with three components, drawn from the set of real numbers be represented?

Answer 29

3-vector over R
R^3

where R is the symbol for set of real numbers.

Question 30

How can a vector be represented?

Answer 30

As a list
As a 1D array
As a dictionary (which can be considered to be representing it as a function)
Graphically (as an arrow)
Using set notation

Question 31

a = (5, 13) b = (29, 5)

a + b = ?

Answer 31

(34, 18)

Question 32

multiplying a = (5, 13) by 2 will give the vector…

Answer 32

(10, 26)

Question 33

what is the expression for the convex combination of vectors?

Answer 33

(a * u) + (b * v)
OR
au + bv

a is alpha, and b is beta
a + b = 1
a and b are greater than or equal to zero
u and v are vectors

Question 34

a = (2, -1) b = (-7, -4)

What is the dot product of a and b?

Answer 34

a.b = (2 * -7) + (-1 * -4) = -14 + 4 = -10

a.b = -10

Question 35

What is the purpose of finding the dot product of two vectors?

Answer 35

Can be used to find the angle between them.

Question 36

What is the formula for finding the angle between two vectors?

Answer 36

cos(theta) = a.b / |a|.|b|