AMCAT Data Structures and Algorithms 2

Question 1

What is the space complexity of a recursive Fibonacci function (without memoization)?

Accepted Answer

O(n)

Answer

The call stack depth is proportional to n, giving O(n) space complexity.

Question 2

Which graph traversal algorithm uses a queue?

Accepted Answer

Breadth-First Search

Answer

Breadth-First Search uses a queue to explore neighbors level by level.

Question 3

What is the time complexity of inserting an element at the beginning of a singly linked list?

Accepted Answer

O(1)

Answer

Inserting at the head of a linked list only requires updating two pointers, which is O(1).

Question 4

Which algorithm is used to find the shortest path in a weighted graph with non-negative weights?

Accepted Answer

Dijkstra's

Answer

Dijkstra's algorithm finds the shortest path in graphs with non-negative edge weights using a priority queue.

Question 5

A hash table with chaining resolves collisions by:

Accepted Answer

Maintaining a linked list at each bucket

Answer

In chaining, each bucket holds a linked list of all keys that hash to the same index.

AMCAT Practice Test