Top Tree Test - Sanfoundry

1. Cartesian trees are most suitable for?

minimum range query and lowest common ancestors

searching

finding nth element

self balancing a tree

2. A treap is a cartesian tree with ___________

additional operations like remove a range of elements

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

additional heap rule

additional value, which is a priority value to the key generated sequentially

3. What is a Cartesian tree?

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

a tree which obeys heap property only

a skip list in the form of tree

a tree which obeys cartesian product

4. Is the below tree representation of 50,100,400,300,280 correct way to represent cartesian tree?

false

true

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

false

true

6. Consider a sequence of numbers to have repetitions, how a cartesian tree can be constructed in such situations without violating any rules?

use any tie-breaking rule between repeated elements

cartesian tree is impossible when repetitions are present

construct a max heap in such cases

construct a min heap in such cases

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

does nothing

constructs a cartesian tree

produces some random output

sorts the input sequence

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

use linked lists

use treaps (cartesian trees)

use avl trees

use red-black trees

9. What is the speciality of cartesian sorting?

it considers cartesian product of elements

it sorts partially sorted set of data quickly

it sorts elements in less than O(logn)

it is a self balancing tree

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

only ii. is true

both are false

both statements are true

only i. is true