Randomized Binary Search Tree Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Randomized Binary Search Tree”.

1. Which of the following is not a random tree?
a) Treap
b) Random Binary Tree
c) Uniform Spanning Tree
d) AVL Tree
View Answer

Answer: d
Explanation: Treap, also known as random binary search tree, Random binary tree and Uniform spanning tree are all random tree. Random tree is a tree formed by a random process of addition and deletion of nodes. AVL tree is a self – balanced binary search tree.
advertisement

2. Which process forms the randomized binary search tree?
a) Stochastic Process
b) Branching Process
c) Diffusion Process
d) Aggregation Process
View Answer

Answer: a
Explanation: The randomized binary search tree is formed by the stochastic process. The stochastic process or also called random process is a mathematical tool or object including random variables.

3. How many randomized binary search trees can be formed by the numbers (1, 3, 2)?
a) 2
b) 3
c) 6
d) 5
View Answer

Answer: d
Explanation: As there are 3 numbers (1, 3, 2) so total of 6 combinations can be formed using three numbers but Since (2, 1, 3) and (2, 3, 1) are same so in total there are 5 randomized binary search tree that can be formed.
advertisement
advertisement

4. What is the expected depth of a node in a randomized binary search tree?
a) log n
b) n!
c) n2
d) 2 log n + O(1)
View Answer

Answer: d
Explanation: The expected value of depth of a node that is for a node a, the expected value of length of path from root to node a is found to be at most 2 log n + O(1).

5. What is the longest length path for a node x in random binary search tree for the insertion process?
a) log x
b) x2
c) x!
d) 4.311 log x
View Answer

Answer: d
Explanation: Although it is difficult to find the length of the longest path in randomized binary search tree, but it has been found that the longest length is around 4.311 log x.
advertisement

6. What is the range of β in finding the length of the longest path in a randomized binary search tree?
a) (-1, 0)
b) (1, 0)
c) (0, 5)
d) (0, 1)
View Answer

Answer: d
Explanation: The longest path in a randomized binary search tree, but it has been found that the longest length is around 4.311 log x for node x. This is also equal to 1/β log x where β lies in the range (0, 1).

7. What is the expected number of leaves in a randomized binary search tree?
a) n + 1
b) (n + 1)/3
c) (n + 1)/2
d) n + 3
View Answer

Answer: b
Explanation: In a random mathematical model, the expected value of number of leaves in a randomized binary search tree is found to be exactly (n + 1)/3 using probability.
advertisement

8. Is Treap a randomized tree.
a) True
b) False
View Answer

Answer: a
Explanation: Treap is a type of data structure which is a combination of binary tree and heap. It is an example of a randomized binary search tree. It stores value in pairs.

9. What is the probability of selecting a tree uniformly at random?
a) Equal to Catalan Number
b) Less Than Catalan Number
c) Greater than Catalan Number
d) Reciprocal of Catalan Number
View Answer

Answer: d
Explanation: Catalan number is a sequence of natural number that is used in counting problem. Hence it is found that the selecting off a tree uniformly at random is reciprocal of Catalan number.
advertisement

10. Is mathematical randomized tree can be generated using beta distribution.
a) True
b) False
View Answer

Answer: a
Explanation: Beta distribution can be used using a different shape to generate a randomized binary search tree to create a special type of tree known as a botanical tree.

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