We have the best collection of Cartesian Tree MCQs and answer with FREE PDF. These Cartesian Tree MCQs will help you to prepare for any competitive exams like: BCA, MCA, GATE, GRE, IES, PSC, UGC NET, DOEACC Exams at all levels – you just have to practice regularly.

Cartesian Tree MCQs

1. 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

Answer: it sorts partially sorted set of data quickly

2. Cartesian trees solve range minimum query problem in constant time.

a) true

b) false

Answer: true

3. 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

Answer: a tree which obeys heap property and whose inorder traversal yields the given sequence

4. 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

Answer: use any tie-breaking rule between repeated elements

5. 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

Answer: sorts the input sequence

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

Answer: both statements are true

7. Cartesian trees are most suitable for?

a) searching

b) finding nth element

c) minimum range query and lowest common ancestors

d) self balancing a tree

Answer: minimum range query and lowest common ancestors

8. 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

Answer: additional value, which is a priority value to the key generated randomly

Cartesian Tree MCQs PDF Download

Categories: Binary Trees