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.
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?
b) O(log N)
c) O(log N)
3. A treap is a combination of a tree and a heap.
4. Which is the simplest of all binary search trees?
a) AVL tree
c) Splay tree
d) Binary heap
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.
7. What is the average running time of a treap?
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?
c) random number
10. Who invented treaps?
a) Cecilia and Raimund
b) Arne Andersson
c) Donald Shell
d) Harris and Ross
Answer: Cecilia and Raimund