Randomized Search AA and AVL Tree MCQs

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. 

Answer= 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). 

Answer= (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. 

Answer= (n + 1)/3


Q5. Is Treap a randomized tree.. 

A. TRUE. 

B. FALSE. 

C.  Nothing Can be said. 

D.  None of the mentioned. 

Answer= TRUE


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. 

Answer= 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. 

Answer= TRUE


Q8. AA Trees are implemented using?. 

A. Colors. 

B. Levels. 

C. Node size. 

D. Heaps. 

Answer= Levels


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. 

Answer= by performing right rotation


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. 

Answer= skew and split


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. 

Answer= FALSE


Q13. How many different shapes does maintenance of 

AA-Tree need to consider?. 

A. 7. 

B. 5. 

C. 2. 

D. 3. 

Answer= 2


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. 

Answer= 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). 

Answer= O(log N)


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. 

Answer= TRUE


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

A. Arne Anderson. 

B. Daniel Sleator. 

C. Rudolf Bayer. 

D. Jon Louis Bentley. 

Answer= Arne Anderson


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. 

Answer= 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. 

Answer=  AA-tree


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. 

Answer= log(p)


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. 

Answer= TRUE


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. 

Answer= both statements are true


Q31. What is the speciality of cartesian sorting?. 

A. it sorts partially sorted set of data quickly. 

B. it considers cartesian product of elements. 

C. it sorts elements in less than O(logn). 

D. it is a self balancing tree. 

Answer= it sorts partially sorted set of data quickly

Previous Post Next Post