Fundamentals of Data Structures

Question 1

What is a queue?

Answer 1

A FIFO (First in, first out) data structure

Question 2

What is a stack?

Answer 2

A LIFO (Last in, first out) data structure

Question 3

What’s a graph?

Answer 3

A data structure made up of nodes which have a cyclical structure

Question 4

What is a tree?

Answer 4

A data structure made up of nodes which isn’t cyclical.

Usually hierarchical.

The top level is known as the “root node”

The bottom level nodes are known as “leaf nodes”

Question 5

What is a hash table?

Answer 5

A data structure where a hash function is used to mark the position in the table where data should be stored.

This allows us to access data directly rather than a search

Question 6

What is a dictionary?

Answer 6

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

Question 7

What is a dynamic data structure?

Answer 7

A data structure that changes in size to store their contents.

Question 8

What is a static data structure?

Answer 8

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

Question 9

Discuss the advantages and disadvantages of dynamic data structures compared to static data structures.

Answer 9

Advantages of dynamic:
There’s no wasted memory, static allocates at creation dynamic allocates as it’s needed.
No limit on the number of items which can be added, static has a finite/fixed limit.

Disadvantages of dynamic:
Can take longer to add a new item to the structure, because it has to allocate memory.
Can cause a memory leak, if memory that’s no longer needed isn’t returned to the heap

Question 10

What is a linear queue?

Answer 10

Organised as a list or line of data

Question 11

Describe the steps involved in adding an item to a linear queue that has been implemented as a static data structure using an array

Answer 11

Check that the queue is not already full;
(if it isn’t) then add 1 to the value of the rear pointer; [increment address]

then add the new item to the position indicated by the rear pointer;

Question 12

What is a priority queue?

Answer 12

Queue where each item has a priority, and items are kept sorted with the highest priority item in front (priority is signified as subscript numbers)

Question 13

What is a circular queue?

Answer 13

The last node is connected back to the first node in nature

Its static; has a limited number of elements

Question 14

What is meant by the term ‘push’?

Answer 14

A process which adds an item to a data structure typically to a stack.

Question 15

What is meant by the term ‘pop’?

Answer 15

A process which removes an item from a data structure typically from a stack.

Question 16

What is meant by the term ‘peek’?

Answer 16

A process which allows you to inspect a data structure and returns the item at the front or top without removing it.

Question 17

What is a weighted graph?

Answer 17

A graph in which each edge has a value associated with it

Question 18

What is an Adjacency Matrix used for?

Answer 18

To represent a graph by listing each node and indicating where there is an edge between pairs.

Question 19

What is an Adjacency List?

Answer 19

A collection of lists used to represent a finite graph, where each list escribes the set of adjacent nodes in the graph.

Question 20

How do you make an Adjacency Matrix?

Answer 20

Look at graph, if there is an edge between them, put a 1.
If not, put a 0.

If it’s weighted:
Instead of 1, put the weight. If no edge, put infinity symbol.

On directed graph only do when you could go in that direction.

Question 21

When is it good to use an adjacency list instead of an adjacency matrix?

Answer 21

When the graph is sparse.

When edges are rarely changed.

Question 22

What is a rooted tree?

Answer 22

A tree in which one node has been designated as the root and ever edge is directed away from it.

Question 23

What is binary tree?

Answer 23

A tree where each node can only have 0, 1 or 2 leaf nodes

Question 24

Describe the steps involved in adding a record to a hash table

Answer 24

Take your key value and put it through a hashing algorithm.

The hash number (the result) is the location in the table where the data should be stored.

If the location found isn’t empty:

A hash collision has occurred, and you should move onto the next available location.

With large lists, a hash cluster may occur where many data items aren’t in the correct location as per the hashing algorithm. Instead, you can create a linked list and store multiple pieces of data in the same location

Question 25

What is a linked list?

Answer 25

A list of nodes or elements of data connected by pointers

Question 26

What is meant by the term ‘hash collision’?

Answer 26

When two different inputs to a hash function produce the same output as a hash value

Question 27

What is meant by the term ‘rehashing’?

Answer 27

Increasing the size of a hash tables array and restoring all the items into the array using the hash

Typically happens when a hash table starts to become full or when an insertion fails

Question 28

What is hash clustering?

Answer 28

After a hash collision, you put it in another memory address near to the desired one because it was full.

But then if you want to add something else which should have the memory address that was just taken, it’ll then create another collision.

This will repeat that process; this can get tedious with a large block of data.

Question 29

What is hash overflow?

Answer 29

Overflow attempts to overcome clustering by using a linked list

If a collision occurs, it creates a linked list which is attached to the collision key.

Instead of going to the next memory address it attaches a “tail” to the data currently in the desired memory address. So, you go the memory address, check if the data is the one you’re looking for; if not move down the “tail”

Question 30

What is a Stack Frame?

Answer 30

A structure stored on the stack where all information associated with a function call is recorded.

This could include Parameters, Local Variables

Question 31

What is a Pointer?

Answer 31

A variable which stores the memory address of another variable.

Question 32

What is an opcode?

Answer 32

Mathematical command

Question 33

What is an operand?

Answer 33

data

Question 34

What is Dot/Scalar product?

Answer 34

An algebraic operation that takes two equal-length sequences of numbers (usually coordinate vectors) and returns a single number.

[1,3]
[4,5]

Dot product = 1x4 + 3x5 = 19

Question 35

How do pointers work in a queue?

Answer 35

when an item is removed from a queue the front pointer moves to the next item that is now at the front of the queue.

when an item is added to a queue the rear pointer points at the newly added item.

Question 36

How can you implement a linear queue as an array or list?

Answer 36

two ways:

1. as items leave the queue, all of the other items move up soi that the front of the queue is always the first element of the structure.
2. a linear queue can be implemented with pointers to the front and rear of the queue. An integer holding the size of the array is needed, as well as a variable giving the current number of items in the queue. When items are added and removed from the queue a space is created at the front of the queue which cannot be filled, and items are added until rear pointer points to the last element of the data structure.

Question 37

What is meant by the term ‘heap’ in relation to dynamic data structures?

Answer 37

the portion of memory from which space is allocated and de-allocated as required.

Question 38

Functions of a call stack

Answer 38

store information about active subroutines while a computer program is running.

call stack keeps track of addresses of the instruction that control should return to when subroutine ends.

parameters required for a subroutine may be held on a call stack, each call to a subroutine will be given a space on the call stack for these values.

local variable are also held on a call stack because its much more efficient than using dynamic memory allocation, which uses heap space.

Question 39

What algorithm is used to find the shortest path on a unweighted graph?

Answer 39

Breadth First Traversal

Question 40

How do you search for an item in a Hash Table?

Answer 40

When an item is looked up in a hash table, the key is hashed . This hash code is used as an index into the hash table to locate the item

Question 41

How do you delete a value from the Hash Table?

Answer 41

Search for item you wish to delete. Once the key is found remove the key-value pair from the list.

Question 42

How do you add an item to a circular queue?

Answer 42

1. Check if full
2. If not full, increment the rear pointer (wrap around if needed)
3. Add item to the rear position

Question 43

How to remove item from circular queue?

Answer 43

1. Check if empty
2. If not empty increment the front pointer by 1
3. Dequeue element from front of queue

Question 44

Describe the steps involved in adding an item to a priority queue.

Answer 44

Starting from rear of queue, move each item back one place.

Until you reach the start of the queue or an item with the same or higher priority.

Add the new item before that item.

Question 45

What is a vector?

Answer 45

A vector can be represented as a list of numbers, a function, or a way of representing a geometric point in space

Question 46

Advantages of a circular queue over a linear queue?

Answer 46

Circular queues use memory more efficiently by reusing space,

have faster enqueue and dequeue operations,

are simpler to implement since they avoid shifting elements,

and are suitable for memory-constrained applications due to their efficient use of available memory.