Discussion
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 \(n\) of these data structures?
Answer: A
The meld complexities are P: \(\Theta(1)\), Q: \(\Theta(n)\), R: \(\Theta(n)\).
- P, a doubly linked list with head and tail pointers: link the tail of the first list to the head of the second and update one tail pointer. A constant number of pointer changes: Θ(1).
- Q, an array min-heap: copy both arrays into one of size 2n and run the bottom-up build-heap, which is linear: Θ(n). Inserting the elements one at a time would cost Θ(n log n), so that is not the best bound.
- R, a binary search tree: an inorder traversal of each tree gives two sorted lists in Θ(n), merging them takes Θ(n), and a balanced BST can be built from a sorted list in Θ(n).
The other options take the slower insertion-based approaches for Q or R, or treat the list meld as linear.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development