Data Structure Questions and Answers-Cartesian Tree

YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

CLICK HERE TO DOWNLOAD

Data Structure Questions and Answers-Cartesian Tree

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 1 Explanation: 
A tree with heap property (parent is either small or big than children) and when traversed in inorder yields the given input sequence. refer below diagram question for clarity.

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Is the below tree representation of 50, 100, 400, 300, 280 correct way to represent cartesian tree?
A
true
B
false
Question 2 Explanation: 
A tree with heap property (parent is either small or big than children) and when traversed in inorder yields the given input sequence is called as a cartesian tree. as the above figure satisies both the properties. note that even min heap tree can be generated. the above is a max heap tree.

Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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 untrue
Question 3 Explanation: 
A height balanced cartesian tree is not possible as seen in above question. also any time a unique sequnce possess a unique cartesian tree, this can be proven through induction.

Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 4 Explanation: 
It can sort a set which requires only some 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.

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 5 Explanation: 
Consider any of the tie breaking rules, for example:-the element which appears first can be taken as small among the same elements and then apply cartesian tree rules.

There are 5 questions to complete.