GATE Algorithms and Data Structures 3

Question 1

What is the amortized time complexity of a single push or pop operation on a dynamic array that doubles in size when full?

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Answer

O(n log n)

Question 2

In an AVL tree, what is the maximum number of rotations required to restore the AVL balance property after a single insertion?

Accepted Answer

1

Answer

O(log n)

Answer

O(n)

Answer

O(√n)

Question 3

What is the amortized time complexity per operation of Union-Find with both path compression and union by rank?

Accepted Answer

O(α(n))

Answer

O(log n)

Answer

O(1)

Answer

O(n)

Question 4

In a hash table using chaining with n keys stored in m slots under simple uniform hashing, the expected time for a successful search is:

Accepted Answer

O(1 + n/m)

Answer

O(n)

Answer

O(log n)

Answer

O(m)

Question 5

What is the time complexity of building a binary max-heap from an unsorted array of n elements using the linear-time build-heap procedure?

Accepted Answer

O(n)

Answer

O(n log n)

Answer

O(log n)

Answer

O(n²)

Question 6

Which of the following problems can be solved in polynomial time and is therefore in class P (not NP-complete)?

Accepted Answer

Minimum Spanning Tree

Answer

3-SAT

Answer

Hamiltonian Cycle

Answer

Vertex Cover

Question 7

What is the space complexity of Depth-First Search (DFS) on a graph with V vertices and E edges?

Accepted Answer

O(V)

Answer

O(V + E)

Answer

O(E)

Answer

O(V²)