Data Structures

Question 1

Static Data Structures

Answer 1

A static data structure is a coollection of data in memory that is fixed in size - memory locations are set aside for these data structures

Question 2

Dynamic Data Structures

Answer 2

A dynamic data structure is a collection of data in memory that is flexible in size - it can grow and shrink while a program is running.

Memory is allocated from a heap - a collection of all the available memory locations in the main memory

Question 3

Pointer

Answer 3

A variable that holds the memory address of another variable
eg. The variable at the top of a stack

Question 4

Static Advantages and Disadvantages

Answer 4

Static Advantages:
- Easier to program
- No issues with adding/removing data items since size is fixed

Static Disadvantages:
- Memory that’s set aside might not be used; wasteful

Question 5

Dynamic Advantages and Disadvantages

Answer 5

Advantages:
- More memory efficient; only uses the data it needs

Disadvantages:
- Can lead to memory leaks if memory isn’t deallocated properly
- Harder to program

Question 6

Queues

Answer 6

A queue is an ADT that has a First In First Out principle - data items are added to the back of the queue and leave from the front

Front and Rear are indicated with pointers

Uses = Buffers; Print queues

Question 7

Priority Queues

Answer 7

A type of queue where data items are assigned a priority value - items with the highest priority value are dequeued before lower priority items

If 2 items have the same priority, the FIFO order is followed

Uses = Priority print queues, A&E systems, the processor to prioritise apps in use over apps running in the background

Question 8

Circular Queues

Answer 8

A type of queue where the Front and Rear pointers can move over both ends of the queue - more memory efficient

Front and Rear pointing to the same element = Empty queue

Rear = Front - 1 = Full queue

Question 9

Queues: Insertion

Answer 9

1 - Check if the queue is full
2 - If the queue is full, report an error and stop
3 - Increment the Rear pointer and stop
4 - Insert new data into the location pointed to by the Rear pointer

For circular queues:
1 - Check if the queue is full
2 - if the queue is full, report an error and stop
3 - Compare the value of the rear pointer to the max size of the array minus 1.
If they are equal, then the rear pointer becomes 0.
Otherwise, add one to the rear pointer.
4 - Insert new data into the location pointed to by the Rear pointer

Question 10

Queues: Deletion

Answer 10

1 - Check if the queue is empty
2 - If the queue is empty, report an error and stop
3 - Copy data item in the location pointed to by the Front pointer
4 - Increment the Front pointer and stop

For circular queues:
1 - Check if the queue is empty
2 - If the queue is empty, report an error and stop
3 - Copy data item in the location pointed to by the Front pointer
4 - Compare the value of the front pointer to the max size of the array minus one.
If they are equal then the front pointer becomes 0.
5 - Increment the Front pointer and stop

Question 11

Stacks

Answer 11

An ADT where data can only be accessed from the top - data items are added and removed from the top

Top of the stack is indicated with a Top pointer

Uses a Last In First Out principle

Question 12

Stack: Insertion/Pushing

Answer 12

1 - Check if the stack is full

2 - If it is, report an error and stop

3 - Increment the Top pointer

4 - Insert new data item into the location pointed to by the Top pointer and stop

Question 13

Stack: Deletion/Popping

Answer 13

1 - Check if the stack is empty

2 - If the stack is empty report an error and stop

3 - Copy data in location pointed to by the Top pointer

4 - Decrement the stack pointer

Question 14

Graphs

Answer 14

A diagram of connected nodes and edges - each edge joins 2 nodes

Usually represents a complex relationship eg a network of computers

Question 15

Adjacency Matrix and List

Answer 15

Adjacency matrix = A table that records info about which edges are connected
- Best used when the graph is dense

Adjacency list = A list that shows which nodes are connected
- Best used when the graph is sparse

Question 16

Graph Types

Answer 16

Digraph = Graph where all the edges are single-headed arrows

Weighted graph = Graph where all the edges are labelled with a value that could represent distance

Question 17

Trees

Answer 17

A connected, undirected graph with no cycles

Question 18

Rooted Trees

Answer 18

A type of tree where one node is singled out as a starting point called the node

Parent-child relationship exists between the nodes

Question 19

Binary Trees

Answer 19

A rooted tree where each node has a maximum of 2 child nodes and where each node contains Left and Right pointers

3 arrays are used to store the data, the left pointer’s value and the right pointer’s value for each data item

Left-Right pointers are set to terminators (-1) when the binary tree is first initialised

Question 20

Binary Search Tree

Answer 20

A binary tree constructed with some order of precedence such as alphabetical order

Question 21

Hash Tables

Answer 21

A collection of data stored by using hash key-value pairs; this makes data lookup and data comparison much faster

Question 22

Hashing

Answer 22

Hash function = a procedure that converts a large number / string into a small datum, usually an integer

Hash value = the value returned by a hash function

Hash key = Value that the hash function is applied to

Question 23

Collisions

Answer 23

A collision happens when 2 or more keys can generate the same hash value

They are solved by either Open or Closed Hashing

Question 24

Open and Closed Hashing

Answer 24

Open Hashing = Storing the colliding record in the next available memory location by searching through the table

Closed Hashing = Each record contains a pointer - these store the colliding record in a linked list connected to the table.
These pointers are set as terminators when the table is first set up

Question 25

Dictionaries

Answer 25

A collection of key-value pairs where data is accessed using its associated key

use = dictionary-based compression

Question 26

Vectors

Answer 26

1D array or list of elements where each element is identified by a single index or key

They can be represented as a list of numbers [p2.45, 13.89, 1.05, 5.90]
and as a function using a dictionary:
- f: S -> R, the set S {0, 1, 2, 3} and the co-domain R, the set of Real numbers
- 0 ↦ 2.45
- 1 ↦ 13.89
- 2 ↦ 1.05
- 3 ↦ 5.90
where ↦ = ‘maps to’
Can also be stored as a dictionary {0: 2.45, 1: 13.89, 2: 1.05, 3: 5.90}

Question 27

Vector Addition and Multiplication

Answer 27

Vector addition is done by adding respective components of vectors together
eg. Vector u = [3.0, 2.0] and Vector v = [1.0, 3.0]
u + v = [3.0 + 1.0, 2.0 + 3.0] = [4.0, 5.0]
- Achieves translation

Scalar-vector multiplication is done by multiplying the components of a vector with the same number
eg. 1.5 * u = [3.0 * 1.5, 2.0 * 1.5] = [4.5, 3.0]

Question 28

Convex combination of Vectors

Answer 28

Convex combination of 2 vectors is an expression of the form αu + βv ((α * u)+ (β* v)) where u and v are vectors, α + β = 1 and both α & β are greater than or equal to 0

eg. for Vector u = [3.0, 2.0] and Vector v = [1.0, 3.0], one convex combination could be 0.25u + 0.75v which is [0.25 * 3.0, 0.25 * 2.0] + [0.75 * 1.0, 0.75 * 3.0] = [0.75, 0.5] + [0.75, 2.25] = [1.5, 2.75]

Question 29

Dot product of 2 vectors

Answer 29

The dot product is a process that combines 2 vectors to find a single value
Done by multiplying respective components together
(u * v = (u1 * v1) + (u2 * v2) etc)

eg. for Vector u = [3.0, 2.0] and Vector v = [1.0, 3.0], the dot product would be (3.0 * 1.0) + (2.0 * 3.0) = 3 + 6 = 9

Used to find the angle between 2 vectors - if the angle is <90 degrees, the dot product will be negative. if the angle is >90 degrees, the dot product will be positive
If the vectors are perpendicular, the dot product will be 0