This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Cartesian Tree”.
1. What happens if we apply the below operations on an input sequence?
i. construct a cartesian tree for input sequence
ii. put the root element of above tree in a priority queue
iii. if( priority queue is not empty) then
iv. search and delete minimum value in priority queue
v. add that to output
vi. add cartesian tree children of above node to priority queue
A) constructs a cartesian tree
B) sorts the input sequence
C) does nothing
D) produces some random output
Explanation: The steps for sorting a cartesian tree are described above. In the case of a partially sorted set of elements, cartesian sort is advantageous. A cartesian sort is a selection or heap sort that maintains a priority queue.
2. Cartesian trees are most suitable for?
B) finding nth element
C) minimum range query and lowest common ancestors
D) self balancing a tree
Explanation: Finding the lowest common ancestor for the extreme elements in a cartesian tree yields the minimum value. Consider the numbers 11,9,19,16. The lowest element is 9 and it is the ancestor of 11 and 16. and a cartesian tree can be used to efficiently identify lowest common ancestors by employing a few techniques.
These can be completed in a fixed amount of time. Trees can be built in linear time (which is the most effective time for any tree construction) and take up a lot of space because there are so many elements.
3. A treap is a cartesian tree with ___________
A) additional value, which is a priority value to the key generated randomly
B) additional value, which is a priority value to the key generated sequentially
C) additional heap rule
D) additional operations like remove a range of elements
Explanation: When fed a sorted list, a cartesian tree will produce a straight path (or in tree terminology a skew tree). Furthermore, a cartesian tree based on the same values from the search keys is ineffective. Treap is a cartesian tree with a priority value in addition to the search key.
4. Cartesian trees solve range minimum query problem in constant time.
Explanation: Finding the minimum element in a given subarray of an array is called a range minimum query. By storing the Cartesian trees for all of the blocks in the array, constant time is achieved. Rmqs are used to compute a sring’s lowest common ancestor and longest common prefix in string matching.
5. Consider below sequences.
array=60 90 10 100 40 150 90 reverse 2 to 3 array=60 10 90 100 40 150 90 reverse 3 to 6 array= 60 100 150 40 100 90 90 now printout from 1 to 6 :-- 60 100 150 40 100 90
How to achieve the above operation efficiently?
A) use linked lists
B) use avl trees
C) use red-black trees
D) use treaps (cartesian trees)
Explanation: This can be solved quickly with the aid of treap, a modified cartesian tree. Every node can have an attribute like “boolean reverse” that indicates whether to reverse or not.
6. Which of the below statements are true?
i. Cartesian tree is not a height balanced tree
ii. Cartesian tree of a sequence of unique numbers can be unique generated
A) both statements are true
B) only i. is true
C) only ii. is true
D) both are false
Explanation: As seen in the previous issue, a height balanced cartesian tree is not feasible. Induction can also be used to prove that a unique sequence has a unique cartesian tree.
7. What is the speciality of cartesian sorting?
A) it sorts partially sorted set of data quickly
B) it considers cartesian product of elements
C) it sorts elements in less than O(logn)
D) it is a self balancing tree
Explanation: It is capable of sorting a collection that only includes any sorting or displacements. for example consider 78, 79, 80, 82, 81, 83, In this only 81 and 82 must be swaped to make it a complete sorted set, in this case cartesian sort comes to the rescue.
8. Consider a sequence of numbers to have repetitions, how a cartesian tree can be constructed in such situations without violating any rules?
A) use any tie-breaking rule between repeated elements
B) cartesian tree is impossible when repetitions are present
C) construct a max heap in such cases
D) construct a min heap in such cases
Explanation: Consider any of the tie-breaking rules; for example, the element that occurs first can be regarded as the smallest of the same elements, and then cartesian tree rules can be applied.
9. What is a Cartesian tree?
A) a skip list in the form of tree
B) a tree which obeys cartesian product
C) a tree which obeys heap property and whose inorder traversal yields the given sequence
D) a tree which obeys heap property only
Explanation: When traversed in order, a tree with heap property (parent is either smaller or larger than children) yields the specified input sequence. For more details, see the diagram query below.
10. Is the below tree representation of 50,100,400,300,280 correct way to represent cartesian tree?
Explanation: A cartesian tree is a tree with the heap property (parent is either smaller or larger than children) that yields the given input sequence when traversed in reverse order. The figure above satisfies both properties. It’s worth noting that even the smallest heap tree can be created. The tree shown above is a maximum heap tree.
A Cartesian tree is a binary tree derived from a sequence of numbers that can be uniquely identified by the properties of being heap-ordered and returning the original sequence after a symmetric (in-order) traversal. Cartesian trees were first used in the sense of geometric range searching data structures by Vuillemin (1980), and they’ve since been used to define the treap and randomised binary search tree data structures for binary search problems.