PROGRAMMING WITH DATA STRUCTURES
(SET:2)
1. What is the maximum height of any AVL tree with 7 nodes? Assume that the height of a tree
with single node is 0.
(a) 2 (b) 3
(c) 4 (d) 5
2. Consider a B+ tree in which the maximum number of keys is a node is 5. What is the
maximum no. of keys in any non-root node?
(a) 1 (b) 2
(c) 3 (d) 4
3. In a binary tree with n nodes every node has an odd no. of descendants. Every node is
considered to be its own descendant. What is the no. of nodes in the tree that has exactly one
child?
(a) 0 (b) 1
(c) (n-1)/ 2 (d) n-1
4. Which of the following is a true about Binary trees?
(a) Every binary tree is either complete or full
(b) Every complete binary tree is also a full binary tree
(c) Every full binary tree is also a complete binary tree
(d) None of these
5. What are the main applications of a tree data structure?
(a) Manipulate hierarchical data (b) Make information easy to search
(c) Router algorithms (d) All of these
6. In a complete K-ary tree, every internal node has exactly K children or no child. The no. of
leaves in such a tree with n internal nodes is:
1
(a) nK (b) (n-1) K+1
(c) n(K-1) +1 (d) n(K-1)
7. The no. of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
(a) n/ 2 (b) (n-1)/ 3
(c) (n-1)/ 2 (d) (2n+1)/ 3
8. A weight balanced tree is a binary tree in which for each node, the no. of nodes in the left sub
tree is atleast half and at most twice the no. of nodes in the right sub tree. The maximum possible
height of such a tree with n nodes is best described by which of the following?
(a) log2 n (b) log4/3 n
(c) log3 n (d) log3/2 n
9. A schema for storing a binary tree in an array X is as follows. Indexing of X starts at 1 instead
of 0. The root is stored at X[1]. For a node stored at X[i] the left childs if any is stored at X[2i]
and right child at X[2i + 1]. To be able to store any binary tree of n vertices, the minimum size of
X should be:
(a) log2 n (b) n
(c) 2n+1 (d) 2n-1
10. Postorder traversal of a given BST, t produces the order:
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
Which of the following is inorder traversal?
(a) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
(b) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
(c) 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
(d) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29
11. Consider a node X in a Binary tree. Given that X has 2 children. Y be a inorder successor of
X. Which of the following is true about Y?
2
(a) Y has no right child (b) Y has no left child
(c) Y has both children (d) None of the above
12. The height of a tree is the length of the longest root-to-leaf path in it. The max and min no. of
nodes in a binary tree of height 5 are:
(a) 63 and 6 (b) 64 and 5
(c) 32 and 6 (d) 31 and 5
13. A binary tree T has 20 leaves. The no. of nodes in T having 2 children is:
(a) 18 (b) 19
(c) 17 (d) any number between 10 and 20
14. Consider a complete binary tree where the left and right subtrees of the root are max- heaps.
The upper bound of the no. of operations to convert the tree to a heap is:
(a) Ω (log n) (b) Ω (n)
(c) Ω (n log n) (d) Ω (n2)
15. The inorder and preorder traversal of a binary tree is—d b e a f c g and a b d e c f g
respectively. The postorder traversal of the binary tree is:
(a) d e b f g c a (b) e d b g f c a
(c) e d b f g c a (d) d e f g b c a
16. Which of the following pair of traversals is not sufficient to build a binary tree from the
given traversals?
(a) Preorder and Inorder (b) Preorder and Postorder
(c) Inorder and Postorder (d) None of the above
17. Which traversal of tree resembles the breadth first search of the graph?
(a) Preorder (b) Inorder
3
(c) Postorder (d) Levelorder
18. Which of the following tree traversal uses a queue data structure?
(a) Preorder (b) Inorder
(c) Postorder (d) Levelorder
19. What is the worst case complexity for search, insert and delete operations in a general binary
search tree?
(a) 0 (n) for all
(b) 0 (log n) for all
(c) 0 (log n) for search and insert, 0(n) for delete
(d) 0 (log n) for search and 0 (n) for insert and delete
20. The following numbers are inserted into an empty binary search tree in the given order:
10, 1, 3, 5, 15, 12, 16.
What is the height of the BST (the height is the max. distance of a leaf node from the root)?
(a) 2 (b) 3
(c) 4 (d) 6