Data Structures and Abstract Data Types

Question 1

What is the time complexity for hash table lookup?

Answer 1

O(1)

Question 2

Name 2 collision resolution methods

Answer 2

closed addressing (linked list at location), open addressing (new location)

Question 3

What is the time complexity for linked list insertion and deletion? (Assuming the index for insertion/deletion is already known)

Answer 3

O(1)

Question 4

What is the time complexity for linked list search?

Answer 4

O(n)

Question 5

State three features of a good hashing algorithm

Answer 5

1. The hash function uses all the input data
2. The hash function uniformly distributes the data across the entire set of possible hash values
3. The hash function generates very different hash values for similar (but non-identical) strings

Question 6

Name 2 Abstract Data Types.

Answer 6

Stack and Queue

Question 7

How does a stack work?

Answer 7

Elements are pushed onto the stack, or popped from the stack.
The first element pushed onto the stack is the last element popped from the stack (FILO)

Question 8

How does a queue work?

Answer 8

Elements are enqueued into the queue, or dequeued from the queue.
The first element enqueued is also the first element dequeued (FIFO)

Question 9

What methods are required for a Queue ADT?

Answer 9

Enqueue: add an element to the queue
Dequeue: get the next element from the queue

Question 10

What methods are required for a Stack ADT?

Answer 10

Push: add an element to the stack
Pop: get the next element from the stack

Question 11

What are the key features of a Circular Queue?

Answer 11

Circular queues have a fixed capacity.
The last location in the array wraps around to the first location.

Question 12

What does a hash function do in a hash table?

Answer 12

Hash function takes an input key and returns a location/index of fixed size. Each unique key hashes to the same location/index.

Question 13

static vs dynamic memory allocation

Answer 13

Static allocation pre allocates fixed amount of memory upfront … / has constant access time …
1. predetermined data format (element size is calculated)
2. constant access
3. fixed size

while dynamic allocation requests memory on an ad-hoc basis / only when needed / requires traversal to reach further nodes
1. flexible data format
2. no constant time access
3. dynamic size

Question 14

BST vs Hash table (5 criteria)

Answer 14

1. sorting: In order traversal of BST allows us to display items in incremental order
2. searching for closest value: BST allows us to search for the key that has the closest value to target
3. memory efficient: BST requires the exact amount of memory for its nodes
4. time complexity of searching : hash table O(1), BST: O(logn)
5. worse time complexity of searching:
   - hash table (collision O(n)) -> choose appropriate size table
   - BST (unbalanced O(n)) -> self balancing BST every time there is a change made

Question 15

state the differences between circular queue and linear queue

Answer 15

1. space utilisation
   circular queue efficiently utilises available space by reusing positions that become free whereas a linear queue may leave unused spaces at the beginning as elements are dequeued
   (linear= less efficient use of memory)
2. wrapping
   in a circular queue, the last position is connected back to the first position, forming a loop
   in a linear queue elements only move in a straight line from front to back