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 after a particular node, or deletion of a specific node?

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

What is a stack?

Answer 7

A stack is a last-in-first-out/first-in-last-out (FILO/LIFO) data structure.
The first element pushed onto the stack is the last element popped from the stack.

Question 8

What is a queue?

Answer 8

A queue is a first-in-first-out (FIFO) data structure.
The first element enqueued is also the first element dequeued.

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. The same input key is always hashed to the same location.