Treap Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Treap”.

1. 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).
advertisement

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

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

6. 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. 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).
advertisement

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

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

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter