Cognizant Cognizant Data Structures and Algorithms 2 — Questions and Answers
Question 1: Which sorting algorithm has the best average-case time complexity?
- Bubble Sort
- Insertion Sort
- Merge Sort (Correct answer)
- Selection Sort
Correct answer: Merge Sort
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?
- Maximum element
- Median element
- Minimum element (Correct answer)
- Random element
Correct answer: Minimum element
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?
- O(1) (Correct answer)
- O(log n)
- O(n)
- O(n log n)
Correct answer: O(1)
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?
- Stack
- Queue
- Min-Heap / Priority Queue (Correct answer)
- Deque
Correct answer: Min-Heap / Priority Queue
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?
- 2h
- 2h − 1
- 2^(h+1) − 1 (Correct answer)
- h²
Correct answer: 2^(h+1) − 1
A full binary tree of height h has 2^(h+1) − 1 nodes when every level is completely filled.
Question 6: Which algorithm is used to detect a cycle in a linked list?
- Merge Sort
- Floyd's Cycle Detection (Tortoise and Hare) (Correct answer)
- Dijkstra's Algorithm
- DFS with visited array
Correct answer: Floyd's Cycle Detection (Tortoise and Hare)
Floyd's algorithm uses two pointers moving at different speeds; if they meet, a cycle exists.
Cognizant Cognizant Data Structures and Algorithms 2
Which sorting algorithm has the best average-case time complexity?