# Randomized Search AA and AVL Tree MCQs

Q1. 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).

Answer= 2 log n + O(1)

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

Q3. 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).

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

Q5. Is Treap a randomized tree..

A. TRUE.

B. FALSE.

C.  Nothing Can be said.

D.  None of the mentioned.

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

Q7. Is mathematical randomized tree can be generated using beta distribution..

A. TRUE.

B. FALSE.

C.  Nothing Can be said.

D.  None of the mentioned.

Q8. AA Trees are implemented using?.

A. Colors.

B. Levels.

C. Node size.

D. Heaps.

Q9. Which of the following is the correct definition for a horizontal link?.

A. connection between node and a child of equal levels.

B. connection between two nodes.

C. connection between two child nodes.

D. connection between root node and leaf node.

Answer= connection between node and a child of equal levels

Q10. How will you remove a left horizontal link in an AA-tree?.

A. by performing right rotation.

B. by performing left rotation.

C. by deleting both the elements.

D. by inserting a new element.

Q11. What are the two different operations done in an AA-Tree?.

A. shift and color.

B. skew and split.

C. zig and zag.

D. enqueue and dequeue.

Q12. In an AA-tree, we process split first, followed by a skew..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

Q13. How many different shapes does maintenance of

AA-Tree need to consider?.

A. 7.

B. 5.

C. 2.

D. 3.

Q14. What is the prime condition of

AA-tree which makes it simpler than a red-black tree?.

A. Only right children can be red.

B. Only left children can be red.

C. Right children should strictly be black.

D. There should be no left children.

Answer= Only right children can be red

Q15. Which of the following trees is similar to that of an  AA-Tree?.

A. Splay Tree.

B. B+ Tree.

C. AVL Tree.

D. Red-Black Tree.

Q16. What is the worst case analysis of an  AA-Tree?.

A. O(N).

B. O(log N).

C. O( N log N).

D. O(N2).

Q17.  AA-Trees makes more rotations than a red-black tree..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

Q18. Who is the inventor of  AA-Tree?.

A. Arne Anderson.

B. Daniel Sleator.

C. Rudolf Bayer.

D. Jon Louis Bentley.

Q19. What should be the condition for the level of a left node?.

A. It should be less than or equal to that of its parent.

B. It should be greater than that of its parent.

C. It should be strictly less than that of its parent.

D. The level should be equal to one.

Answer= It should be strictly less than that of its parent

Q20. Of the following rules that are followed by an

AA-tree, which of the following is incorrect?1- Only right children can be red2- Procedures are coded recursively3- Instead of storing colors, the level of a node is stored4- There should not be any left children.

A. 1.

B. 2.

C. 3.

D. 4.

Q21. Comparing the speed of execution of Red-Black trees and

AA-trees, which one has the faster search time?.

A.  AA-tree.

B. Red-Black tree.

C. Both have an equal search time.

D. It depends.

Q22. What is an AVL tree?.

A. a tree which is balanced and is a height balanced tree.

B. a tree which is unbalanced and is a height balanced tree.

C. a tree with three children.

D. a tree with atmost 3 children.

Answer= a tree which is balanced and is a height balanced tree

Q23. Why we need to a binary tree which is height balanced?.

A. to avoid formation of skew trees.

B. to save memory.

C. to attain faster memory access.

D. to simplify storing.

Answer= to avoid formation of skew trees

Q24. What is the maximum height of an AVL tree with p nodes?.

A. p.

B. log(p).

C. log(p)/2.

D. pÃ¢„2.

Q25. To restore the AVL property after inserting a element, we start at the insertion point and move towards root of that tree. is this statement true?.

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

Q26. Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without performing any rotations?.

A. just build the tree with the given input.

B. find the median of the set of elements given, make it as root and construct the tree.

C. use trial and error.

D. use dynamic programming to build the tree.

Answer= find the median of the set of elements given, make it as root and construct the tree

Q27. What maximum difference in heights between the leafs of a AVL tree is possible?.

A. log(n) where n is the number of nodes.

B. n where n is the number of nodes.

C. 0 or 1.

D. atmost 1.

Answer= log(n) where n is the number of nodes

Q28. Why to prefer red-black trees over AVL trees?.

A. Because red-black is more rigidly balanced.

B. AVL tree store balance factor in every node which costs space.

C. AVL tree fails at scale.

D. Red black is more efficient.

Answer= AVL tree store balance factor in every node which costs space

Q29. What is a Cartesian tree?.

A. a skip list in the form of tree.

B. a tree which obeys cartesian product.

C. a tree which obeys heap property and whose inorder traversal yields the given sequence.

D. a tree which obeys heap property only.

Answer= a tree which obeys heap property and whose inorder traversal yields the given sequence

Q30. Which of the below statements are true:  i.Cartesian tree is not a height balanced tree  ii.Cartesian tree of a sequence of unique numbers can be unique generated.

A. both statements are true.

B. only i. is true.

C. only ii. is true.

D. both are untrue.