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