Match the following and choose the correct answer in the order A, B, C A. Heap…
2017
Match the following and choose the correct answer in the order A, B, C
A. Heap Construction p. O(n log n)
B. Hash table construction with linear probing q. O(n2)
C. AVL Tree construction r. O(n)
(Bounds given may or may not be asymptotically tight)
- A.
q, r, p
- B.
p, q, r
- C.
q, p, r
- D.
r, q, p
Attempted by 151 students.
Show answer & explanation
Correct answer: D
To determine the correct matches, we analyze the time complexity of each construction method:
A. Heap Construction: Building a heap from n elements using the bottom-up approach (heapify) has a time complexity of O(n). This matches with r.
B. Hash Table Construction (Linear Probing): In the worst-case scenario with frequent collisions, inserting n elements results in O(n^2) time complexity. This matches with q.
C. AVL Tree Construction: Inserting n elements sequentially into an AVL tree requires balancing at each step, leading to O(n log n) time complexity. This matches with p.
Therefore, the correct order for A, B, C is r, q, p.