GATE Algorithms and Data Structures

Question 1

What is the worst-case time complexity of Merge Sort on an array of n elements?

Accepted Answer

O(n log n)

Answer

Merge Sort satisfies the recurrence T(n) = 2T(n/2) + O(n), which by the Master Theorem resolves to O(n log n) in all cases.

Question 2

Which data structure is used in Breadth-First Search (BFS) to track the order in which vertices are visited?

Accepted Answer

Queue

Answer

BFS explores vertices level by level, requiring a FIFO queue so that nodes discovered earlier are processed before later-discovered nodes.

Question 3

What is the worst-case time complexity of QuickSort?

Accepted Answer

O(n²)

Answer

QuickSort's worst case occurs when the pivot is always the minimum or maximum element (e.g., already-sorted input with a fixed pivot), producing unbalanced partitions and O(n²) comparisons.

Question 4

In a randomly constructed Binary Search Tree (BST), what is the average-case time complexity for a search operation?

Accepted Answer

O(log n)

Answer

A randomly constructed BST has an expected height of O(log n), so search visits at most O(log n) nodes on average.

Question 5

What is the height of a complete binary tree containing n nodes?

Accepted Answer

O(log n)

Answer

A complete binary tree of height h has between 2^h and 2^(h+1)−1 nodes, so h = ⌊log₂ n⌋, which is O(log n).

(GATE) Graduate Aptitude Test in Engineering Practice Test

(GATE) Graduate Aptitude Test in Engineering Practice Test

GATE Algorithms and Data Structures