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

Separate chaining (closed addressing), linear probing (open addressing)

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.