Cognizant Cognizant Data Structures and Algorithms 2

Question 1

Which sorting algorithm has the best average-case time complexity?

Accepted Answer

Merge Sort

Answer

Merge Sort consistently achieves O(n log n) average and worst-case time complexity.

Question 2

In a min-heap, which element is always at the root?

Accepted Answer

Minimum element

Answer

A min-heap property requires every parent to be smaller than its children, so the root holds the minimum.

Question 3

What is the average time complexity for searching in a hash table?

Accepted Answer

O(1)

Answer

With a good hash function and low load factor, hash table lookups are O(1) on average.

Question 4

Which data structure is used to implement Dijkstra's shortest path algorithm efficiently?

Accepted Answer

Min-Heap / Priority Queue

Answer

A min-heap priority queue lets Dijkstra always extract the node with the smallest tentative distance in O(log n).

Question 5

What is the maximum number of nodes in a binary tree of height h?

Accepted Answer

2^(h+1) − 1

Answer

A full binary tree of height h has 2^(h+1) − 1 nodes when every level is completely filled.

(Cognizant) Cognizant Test Practice Test