We have the best collection of Treap MCQs and answer with FREE PDF. These Treap 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.
Treap MCQs
1. 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
Answer: Each node has a fixed priority field
2. What is the space complexity of a treap algorithm?
a) O(N)
b) O(log N)
c) O(log N)
d) O(N2)
Answer: O(N)
3. A treap is a combination of a tree and a heap.
a) false
b) true
Answer: true
4. Which is the simplest of all binary search trees?
a) AVL tree
b) Treap
c) Splay tree
d) Binary heap
Answer: Treap
5. 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
Answer: a node’s priority should be at least as large as its parent
6. Several other operations like union set difference and intersection can be done in treaps.
a) True
b) False
Answer: True
7. 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)
Answer: O(log N)
8. Which node has the lowest priority in a treap?
a) root node
b) leaf node
c) null node
d) centre node
Answer: root node
9. What is the priority of a null node?
a) 1
b) 0
c) random number
d) infinity
Answer: infinity
10. Who invented treaps?
a) Cecilia and Raimund
b) Arne Andersson
c) Donald Shell
d) Harris and Ross
Answer: Cecilia and Raimund