A meld operation on two instances of a data structure combines them into one…
GATE · 2025 · CS · Set 2 · Computer Science & IT
A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:
P: Unsorted doubly linked list with pointers to the head node and tail node of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.
Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size 𝑛 of these data structures?
- A.
P: Θ(1), Q: Θ(𝑛), R: Θ(𝑛)
- B.
P: Θ(1), Q: Θ(𝑛 log 𝑛), R: Θ(𝑛)
- C.
P: Θ(𝑛), Q: Θ(𝑛 log 𝑛), R: Θ(𝑛2)
- D.
P: Θ(1), Q: Θ(𝑛), R: Θ(𝑛 log 𝑛)
Attempted by 322 students.
Show answer
Correct answer: A
The worked solution is available to enrolled students.
Video solution available to enrolled students.
Explore the full course: Iocl Engineers Officers Grade A Paper 2