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

Doubling doubles the capacity but the total copying cost over all insertions sums to O(n), so by the aggregate method each operation costs O(1) amortized.

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

After insertion, only the deepest unbalanced ancestor needs a single or double rotation; once fixed, all ancestors above it automatically regain balance.

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

With path compression and union by rank, the amortized cost per operation is O(α(n)), the inverse Ackermann function, which is less than 5 for any input encountered in practice.

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

The expected chain length is the load factor α = n/m, so a successful search costs O(1) for hashing plus O(1 + α) = O(1 + n/m) for traversal.

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

Build-heap calls sift-down on n/2 internal nodes; since most are near the leaves, the total work sums to O(n) by the geometric series argument.

(GATE) Graduate Aptitude Test in Engineering Practice Test

(GATE) Graduate Aptitude Test in Engineering Practice Test

GATE Algorithms and Data Structures 3