AMCAT Data Structures and Algorithms 2 — Questions and Answers
Question 1: What is the space complexity of a recursive Fibonacci function (without memoization)?
- O(1)
- O(n) (Correct answer)
- O(log n)
- O(n²)
Correct answer: O(n)
The call stack depth is proportional to n, giving O(n) space complexity.
Question 2: Which graph traversal algorithm uses a queue?
- Depth-First Search
- Breadth-First Search (Correct answer)
- Dijkstra's Algorithm
- Prim's Algorithm
Correct answer: Breadth-First Search
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?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(n²)
Correct answer: O(1)
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?
- BFS
- DFS
- Dijkstra's (Correct answer)
- Bellman-Ford
Correct answer: Dijkstra's
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:
- Probing to the next empty slot
- Maintaining a linked list at each bucket (Correct answer)
- Resizing the table
- Discarding the duplicate key
Correct answer: Maintaining a linked list at each bucket
In chaining, each bucket holds a linked list of all keys that hash to the same index.
Question 6: What property must a graph satisfy to have a valid topological sort?
- It must be undirected
- It must be a complete graph
- It must be a directed acyclic graph (DAG) (Correct answer)
- It must be a tree
Correct answer: It must be a directed acyclic graph (DAG)
Topological sort is only defined for Directed Acyclic Graphs (DAGs) with no cycles.
AMCAT Data Structures and Algorithms 2
What is the space complexity of a recursive Fibonacci function (without memoization)?