Q1. What is a complete binary tree?.
A. Each node has exactly zero or two children.
B. A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from right to left.
C. A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.
D. None of the mentioned.
Answer= A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right
Q2. What is the time complexity for finding the height of the binary tree?.
A. h = O(loglogn).
B. h = O(nlogn).
C. h = O(n).
D. h = O(log n).
Answer= h = O(log n)
Q3. Which of the following is not an advantage of trees?.
A. Hierarchical structure.
B. Faster search.
C. Router algorithms.
D. Undo/Redo operations in a notepad.
Answer= Undo/Redo operations in a notepad
Q4. In a full binary tree if number of internal nodes is I, then number of leaves L are?.
A. L = 2I.
B. L = I + 1.
C. L = I - 1.
D. L = 2I - 1.
Answer= L = I + 1
Q5. In a full binary tree if number of internal nodes is I, then number of nodes N are?.
A. N = 2I.
B. N = I + 1.
C. N = I - 1.
D. N = 2I + 1.
Answer= N = 2I + 1
Q6. In a full binary tree if there are L leaves, then total number of nodes N are?.
A. N = 2L.
B. N = L + 1.
C. N = L - 1.
D. N = 2L - 1.
Answer= N = 2L - 1
Q7. Which of the following is false about a binary search tree?.
A. The left child is always lesser than its parent.
B. The right child is always greater than its parent.
C. The left and right sub-trees should also be binary search trees.
D. None of the mentioned.
Answer= None of the mentioned
Q8. What is the speciality about the inorder traversal of a binary search tree?.
A. It traverses in a non increasing order.
B. It traverses in an increasing order.
C. It traverses in a random fashion.
D. None of the mentioned.
Answer= It traverses in an increasing order
Q9. What are the worst case and average case complexities of a binary search tree?.
A. O(n), O(n).
B. O(logn), O(logn).
C. O(logn), O(n).
D. O(n), O(logn).
Answer= O(n), O(logn)
Q10. What are the conditions for an optimal binary search tree and what is its advantage?.
A. The tree should not be modified and you should know how often the keys are accessed, it improves the lookup cost.
B. You should know the frequency of access of the keys, improves the lookup time.
C. The tree can be modified and you should know the number of elements in the tree before hand, it improves the deletion time.
D. None of the mentioned.
Answer= The tree should not be modified and you should know how often the keys are accessed, it improves the lookup cost
Q11. What will be the height of a balanced full binary tree with 8 leaves?.
A. 8.
B. 5.
C. 6.
D. 4.
Answer= 4
Q12. The balance factor of a node in a binary tree is defined as _____.
A. addition of heights of left and right subtrees.
B. height of right subtree minus height of left subtree.
C. height of left subtree minus height of right subtree.
D. height of right subtree minus one.
Answer= height of left subtree minus height of right subtree
Q13. A binary tree is balanced if the difference between left and right subtree of every node is not more than ____.
A. 1.
B. 3.
C. 2.
D. 0.
Answer= 1
Q14. Which of the following tree data structures is not a balanced binary tree?.
A. AVL tree.
B. Red-black tree.
C. Splay tree.
D. B-tree.
Answer= B-tree
Q15. Balanced binary tree with n items allows the lookup of an item in ____ worst-case time..
A. O(log n).
B. O(nlog 2).
C. O(n).
D. O(1).
Answer= O(log n)
Q16. Which of the following data structures can be efficiently implemented using height balanced binary search tree?.
A. sets.
B. priority queue.
C. heap.
D. both sets and priority queue.
Answer= both sets and priority queue
Q17. Two balanced binary trees are given with m and n elements respectively. They can be merged into a balanced binary search tree in ____ time..
A. O(m+n).
B. O(mn).
C. O(m).
D. O(mlog n).
Answer= O(m+n)
Q18. Which of the following is an advantage of balanced binary search tree, like AVL tree, compared to binary heap?.
A. insertion takes less time.
B. deletion takes less time.
C. searching takes less time.
D. construction of the tree takes less time than binary heap.
Answer= insertion takes less time
Q19. AVL trees are more balanced than Red-black trees..
A. TRUE.
B. FALSE.
C. Nothing Can be said.
D. None of the mentioned.
Answer= TRUE
Q20. Which of the following is not the self balancing binary search tree?.
A. AVL Tree.
B. 2-3-4 Tree.
C. Red - Black Tree.
D. Splay Tree.
Answer= 2-3-4 Tree
Q21. The binary tree sort implemented using a self - balancing binary search tree takes ______ time is worst case..
A. O(n log n).
B. O(n).
C. O(n2).
D. O(log n).
Answer= O(n log n)
Q22. An AVL tree is a self - balancing binary search tree, in which the heights of the two child sub trees of any node differ by _________.
A. At least one.
B. At most one.
C. Two.
D. At most two.
Answer= At most one
Q23. Associative arrays can be implemented using __________.
A. B-tree.
B. A doubly linked list.
C. A single linked list.
D. A self balancing binary search tree.
Answer= A self balancing binary search tree
Q24. Self - balancing binary search trees have a much better average-case time complexity than hash tables..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= FALSE
Q25. Which of the following is a self - balancing binary search tree?.
A. 2-3 tree.
B. Threaded binary tree.
C. AA tree.
D. Treap.
Answer= AA tree
Q26. A self - balancing binary search tree can be used to implement ________.
A. Priority queue.
B. Hash table.
C. Heap sort.
D. Priority queue and Heap sort.
Answer= Priority queue
Q27. In which of the following self - balancing binary search tree the recently accessed element can be accessed quickly?.
A. AVL tree.
B. AA tree.
C. Splay tree.
D. Red - Black tree.
Answer= Splay tree
Q28. The minimum height of self balancing binary search tree with n nodes is _____.
A. log2(n).
B. n.
C. 2n + 1.
D. 2n - 1.
Answer= log2(n)
Q29. Binary tree sort implemented using a self balancing binary search tree takes O(n log n) time in the worst case but still it is slower than merge sort..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q30. Which of the following is a random tree?.
A. Treap.
B. Random Binary Tree.
C. Uniform Spanning Tree.
D. All of the mentioned.
Answer= All of the mentioned
Q31. Which process forms the randomized binary search tree?.
A. Stochastic Process.
B. Branching Process.
C. Diffusion Process.
D. Aggregation Process.
Answer= Stochastic Process
Q32. How many randomized binary search trees can be formed by the numbers (1, 3, 2)?.
A. 2.
B. 3.
C. 6.
D. 5.
Answer= 5