Data Structures

Question 1

What is a Queue?

Answer 1

A queue is a data structure based on an array. It is a FIFO data structure

Question 2

What are Queues used for?

Answer 2

Queues are used by computers in keyboard buffers.
Each keypress is added to a queue and is removed once the computer has processed them.
This ensures all letters come out in the right order

Question 3

What is a Linear Queue?

Answer 3

A linear queue has 2 pointers, a front and rear pointer
The rear pointer points to the next available position in the queue
When the queue is empty, the rear and front pointer are the same.

Question 4

What is a circular queue?

Answer 4

When an item is dequeued from a static array, space frees up at the front of the array
It is too time consuming to move all the elements up the array, so a circular queue is implemented
If there is space at front, once the rear pointer reaches the end and an item is enqueued, it wraps to the front
If there is space at the front, once the front pointer reaches the end and an item is dequeued, it wraps to the front

Question 5

What is a priority queue?

Answer 5

In a priority queue, items are assigned a priority
Items with the highest priority are dequeued first.

Question 6

What are priority queues used for?

Answer 6

Processors assign time to applications according to their priority.
Applications currently in use by the user are prioritised over background applications

Question 7

What is a Stack?

Answer 7

A data structure which is LIFO

Question 8

What is the use of a Stack?

Answer 8

Store local variables
Store parameters

Question 9

What is a Hash Table?

Answer 9

A table which allows data to be retrieved with a constant time complexity

Question 10

What is a Collision and how are they dealt with?

Answer 10

A collision is when different inputs produce the same hash value, this can lead to data being overwritten.
To fix this, the value is rehashed - which is moving it to the next available place in the table.

Question 11

How is a record added to a hash table?

Answer 11

1) A hashing algorithm is applied to a key
2) The result of the hashing algorithm is an index to show where the record should be stored in an array
3) The list is checked to see if the index is empty, if it is then the record is added
4) If it isn’t then a collision has occurred and the record must be rehashed, this involves moving it into the next available location in the table or a linked list associated with that index

Question 12

How is a record searched for in a hash table?

Answer 12

1) Put the key of the record you are searching for into the hashing algorithm
2) Use the result of the hash function to work out the position in the table
3) If the value in the index is the one you are searching for, the algorithm stops
4) If the value is different, use the linked list overflow until its found.

Question 13

What are the differences between Static and Dynamic Data Structures?

Answer 13

1) A static data structure is fixed in size, whereas dynamic can change - this makes dynamic more memory efficient as it only uses as much memory as it needs, whereas memory in static may go unused.
2) Static data structures store in consecutive memory locations, Dynamic stores more spread out.
3) Dynamic Data structures are faster as all you need to do is move the pointers, whereas static data structures require all data to be moved down the array.
4)Static Data structures are easier to program as there isn’t a requirement to check on the size of the data structure before accessing it

Question 14

What is a heuristic technique?

Answer 14

A method which finds the solution in a way which isn’t the most efficient

Question 15

What are the differences between Adjacency Matrices and Adjacency Lists

Answer 15

1) Adjacency Lists are more memory efficient, as matrices store every possible edge combination - whist lists only store existing ones
2) Adjacency Matrices are more time efficient, as you can search easily using rows/columns, Lists are far more jumbled

Question 15

What are the differences between Adjacency Matrices and Adjacency Lists

Answer 15

1) Adjacency Lists are more memory efficient, as matrices store every possible edge combination - whist lists only store existing ones
2) Adjacency Matrices are more time efficient, as you can search easily using rows/columns, Lists are far more jumbled

Question 16

What are the properties of a Tree?

Answer 16

A tree is a graph which is connected, undirected and has no cycles

Question 17

What is a binary tree?

Answer 17

A tree in which each parent node has no more than 2 child nodes

Question 18

What is the Peek Function in a stack?

Answer 18

Outputs the item at the top of the stack but doesn’t remove it

Question 19

How does a Circular Queue work?

Answer 19

When an item is enqueued, the rear pointer wraps around the array

When an item is dequeued, the front pointer wraps around the array.

This is more efficient as its quicker than all the elements in a queue being moved every time a new one is added.

Question 20

What is a dictionary?

Answer 20

A dictionary is a general purpose data structure used to store groups of objects
Has a set of keys, each key has a single value associated with it
When the key is supplied, the associated value is returned

Question 21

How does a Stack and Undo action work with a stack

Answer 21

1) The stack stores the user’s actions
2) Each time a user completes an action it moves to the top of the stack
3) If it’s a repeat function, the item at the top of the stack is copied and pushed to the top
4) If it’s an undo function, the item is popped from the stack

Question 22

How do you enqueue an item in a circular queue?

Answer 22

1) Check if it is full (Rear + 1 % Max Size will equal Front)
2) If it is, output that the queue is full
3) If it isn’t then rear = rear + 1 % Max Size
4) Queue[Rear] = Data

Question 23

How do you dequeue an item from a circular queue?

Answer 23

1) Check if it is empty (If front = -1)
2) If it is, output that the queue is empty
3) If it isn’t, then Front = Front + 1 % Max Size

Question 24

How do you check if a linear queue is empty/full?

Answer 24

Full: If Rear + 1 = Max Size
Empty: If Front > Rear

Question 25

How do you enqueue and dequeue from a linear queue?

Answer 25

Enqueue:
Check if queue is full
If not, then Rear = Rear + 1
Queue[Rear] = Data

Dequeue:
Check if Queue is Empty
If not, Front = Front + 1

Question 26

Why is a Stack needed for recursion?

Answer 26

To store the local variables of the previous recursions of the algorithm (the previous state of the alogirthm in the previous calls)

Question 27

What are the drawbacks of recursion?

Answer 27

Difficult to trace as it requires you to track multiple iterations of the function
Uses more memory as you store the data in stack frames (local variables, parameters, return addresses)

Question 28

What is the base case of recursion?

Answer 28

The condition to stop the recursive subroutine, so it doesn’t loop forever