Trees Questions

MCQ bookmark_border

101.

Why to prefer red-black trees over AVL trees?

A

Because red-black is more rigidly balanced

B

AVL tree store balance factor in every node which costs space

C

AVL tree fails at scale

D

Red black is more efficient

Correct Answer: B

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

102.

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

Correct Answer: C

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

103.

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

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

104.

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

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

105.

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

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

106.

After applying the below operations on a input sequence, what happens?

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

.search and delete minimum value in priority queue

.add that to output

.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

Correct Answer: B

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

107.

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

Correct Answer: C

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

108.

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

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

109.

Cartesian trees solve range minimum query problem in constant time

A

1

C

May be

D

Can't say

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

110.

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)

Correct Answer: D

None.

Check Answer report_problem Report forum Discussion