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

O(1)

Answer

O(log n)

Answer

O(n²)

Question 2

Which graph traversal algorithm uses a queue?

Accepted Answer

Breadth-First Search

Answer

Depth-First Search

Answer

Dijkstra's Algorithm

Answer

Prim's Algorithm

Question 3

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

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Answer

O(n²)

Question 4

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

Accepted Answer

Dijkstra's

Answer

BFS

Answer

DFS

Answer

Bellman-Ford

Question 5

A hash table with chaining resolves collisions by:

Accepted Answer

Maintaining a linked list at each bucket

Answer

Probing to the next empty slot

Answer

Resizing the table

Answer

Discarding the duplicate key

Question 6

What property must a graph satisfy to have a valid topological sort?

Accepted Answer

It must be a directed acyclic graph (DAG)

Answer

It must be undirected

Answer

It must be a complete graph

Answer

It must be a tree