Engineering Questions with Answers - Multiple Choice Questions

Treap Multiple Choice MCQ

1 - Question

 What is the space complexity of a treap algorithm?
a) O(N)
b) O(log N)
c) O(log N)
d) O(N2)

View Answer

Answer: a
Explanation: The average case and worst case space complexity of a treap is mathematically found to be O(N).




2 - Question

A treap is a combination of a tree and a heap.
a) false
b) true

View Answer

Answer: b
Explanation: A treap is a combination of a tree and a heap. The structure of a treap is determined by the fact that it is heap-ordered.




3 - Question

Which is the simplest of all binary search trees?
a) AVL tree
b) Treap
c) Splay tree
d) Binary heap

View Answer

Answer: b
Explanation: A treap is the simplest of all binary search trees. Each node is given a numeric priority and implementation is non recursive.




4 - Question

What is the reason behind the simplicity of a treap?
a) Each node has data and a pointer
b) Each node is colored accordingly
c) It is a binary search tree following heap principles
d) Each node has a fixed priority field

View Answer

Answer: d
Explanation: A treap is the simplest of all because we don’t have to worry about adjusting the priority of a node.




5 - Question

What is the condition for priority of a node in a treap?
a) a node’s priority should be greater than its parent
b) a node’s priority should be at least as large as its parent
c) the priority is randomly assigned and can have any value
d) a node’s priority is always given in decreasing order

View Answer

Answer: b
Explanation: A node’s priority should satisfy heap order. That is, any node’s priority should be at least as large as its parent.




6 - Question

Several other operations like union set difference and intersection can be done in treaps.
a) True
b) False

View Answer

Answer: a
Explanation: Other than insertion, deletion and search operations, several operations like union, intersection and set difference can be done in treaps.




7 - Question

What is the average running time of a treap?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(M log N)

View Answer

Answer: c
Explanation: The average case and worst case analysis of a treap are mathematically found to be O(log N).




8 - Question

Which node has the lowest priority in a treap?
a) root node
b) leaf node
c) null node
d) centre node

View Answer

Answer: a
Explanation: A root node has the lowest priority in a treap since the node’s priority is based on heap order.




9 - Question

What is the priority of a null node?
a) 1
b) 0
c) random number
d) infinity

View Answer

Answer: d
Explanation: The priority of a null node is set to be infinity in a treap so that during deletion, priority of that particular node is set to infinity, rotated and freed.




10 - Question

Who invented treaps?
a) Cecilia and Raimund
b) Arne Andersson
c) Donald Shell
d) Harris and Ross

View Answer

Answer: a
Explanation: Cecilia and Raimund invented Treaps. Arne Andersson invented AA – Trees. Donald Shell invented shell sort and Harris and Ross formulated maximum flow problem.

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners