lOMoARcPSD|3768221
lOMoARcPSD|3768221
1. The height of a BST is given as h. Consider the height of the tree as the no. of
edges in the longest path from root to the leaf. The maximum no. of nodes possible
in the tree is?
a) 2h-1 -1
b) 2h+1 -1
c) 2h +1
d) 2h-1 +1
ANSWER: b) 2h+1 -1
2. The no of external nodes in a full binary tree with n internal nodes is?
a) n
b) n+1
c) 2n
d) 2n + 1
ANSWER: b) n+1
3. The difference between the external path length and the internal path length of
a binary tree with n internal nodes is?
a) 1
b) n
c) n + 1
d) 2n
ANSWER: d) 2n
4. Suppose a binary tree is constructed with n nodes, such that each node has
exactly either zero or two children. The maximum height of the tree will be?
a) (n+1)/2
b) (n-1)/2
c) n/2 -1
d) (n+1)/2 -1
ANSWER: b) (n-1)/2
5. Which of the following statement about binary tree is CORRECT?
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) A binary tree cannot be both complete and full
lOMoARcPSD|3768221
ANSWER: c) Every full binary tree is also a complete binary tree
6. Suppose we have numbers between 1 and 1000 in a binary search tree and want
to search for the number 363. Which of the following sequence could not be the
sequence of the node examined?
a) 2, 252, 401, 398, 330, 344, 397, 363
b) 924, 220, 911, 244, 898, 258, 362, 363
c) 925, 202, 911, 240, 912, 245, 258, 363
d) 2, 399, 387, 219, 266, 382, 381, 278, 363
ANSWER: c) 925, 202, 911, 240, 912, 245, 258, 363
7. In full binary search tree every internal node has exactly two children. If there
are 100 leaf nodes in the tree, how many internal nodes are there in the tree?
a) 25
b) 49
c) 99
d) 101
ANSWER: c) 99
8. Which type of traversal of binary search tree outputs the value in sorted order?
a) Pre-order
b) In-order
c) Post-order
d) None
ANSWER: b) In-order
9. Suppose a complete binary tree has height h>0. The minimum no of leaf
nodes possible in term of h is?
a) 2h -1
b) 2h -1 + 1
c) 2h -1
d) 2h +1
ANSWER: c) 2h -1
10. If a node having two children is to be deleted from binary search tree, it is
replaced by its
lOMoARcPSD|3768221
a) In-order predecessor
b) In-order successor
c) Pre-order predecessor
d) None
ANSWER: b) In-order successor
11. A binary search tree is formed from the sequence 6, 9, 1, 2, 7, 14, 12, 3, 8, 18. The
minimum number of nodes required to be added in to this tree to form an
extended binary tree is?
a) 3
b) 6
c) 8
d) 11
ANSWER: d) 11
12. In a full binary tree, every internal node has exactly two children. A full binary
tree with 2n+1 nodes contains
a) n leaf node
b) n internal nodes
c) n-1 leaf nodes
d) n-1 internal nodes
ANSWER: b) n internal nodes
13. the run time for traversing all the nodes of a binary search tree with n nodes
and printing them in an order is
a) O(nlg(n))
b) O(n)
c) O(√n)
d) O(log(n))
ANSWER: b) O(n)
14. When a binary tree is converted in to an extended binary tree, all the nodes of
a binary tree in the external node becomes
a) Internal nodes
b) External nodes
c) Root nodes
d) None
ANSWER: a) Internal nodes
lOMoARcPSD|3768221
15. If n numbers are to be sorted in ascending order in O(nlogn) time, which of
the following tree can be used
a) Binary tree
b) Binary search tree
c) Max-heap
d) Min-heap
ANSWER: d) Min-heap
16. If n elements are sorted in a binary search tree. What would be the
asymptotic complexity to search a key in the tree?
a) O(1)
b) O(logn)
c) O(n)
d) O(nlogn)
ANSWER: c) O(n)
17. If n elements are sorted in a balanced binary search tree. What would be
the asymptotic complexity to search a key in the tree?
a) O(1)
b) O(logn)
c) O(n)
d) O(nlogn)
ANSWER: b) O(logn)
18. A threaded binary tree is a binary tree in which every node that does not have right
child has a thread to its
a) Pre-order successor
b) In-order successor
c) In-order predecessor
d) Post-order successor
ANSWER: b) In-order successor
19. In which of the following tree, parent node has a key value greater than or equal
to the key value of both of its children?
a) Binary search tree
b) Threaded binary tree
lOMoARcPSD|3768221
c) Complete binary tree
d) Max-heap
ANSWER: d) Max-heap
20. A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is
a) log2n
b) n-1
c) n
d) 2n
ANSWER: b) n-1
21. A binary search tree is generated by inserting in order the following integers:
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
The number of the node in the left sub-tree and right sub-tree of the root, respectively, is
a) (4, 7)
b) (7, 4)
c) (8, 3)
d) (3, 8)
ANSWER: b) (7, 4)
22. The post order traversal of binary tree is DEBFCA. Find out the pre
order traversal.
A. ABFCDE
B. ADBFEC
C. ABDECF
D. ABDCEF
Answer: C. ABDECF
23. While converting binary tree into extended binary tree, all the original nodes
in binary tree are .......
A. Internal nodes on extended tree
B. External nodes on extended tree
C. Vanished on extended tree
lOMoARcPSD|3768221
D. Intermediate nodes on extended tree
Answer:A. Internal nodes on extended tree
24. The in-order traversal of tree will yield a sorted listing of elements of tree in ........
A. binary trees
B. binary search trees
C. heaps
D. binary heaps
Answer: B. binary search trees
25. In a binary tree, certain null entries are replaced by special pointers which point
to nodes higher in the tree for efficiency. These special pointers are called .........
A. Leaf
B. Branch
C. Path
D. Thread
Answer: D. Thread
26. In a graph if e=(u,v) means .......
A. u is adjacent to v but v is not adjacent to u.
B. e begins at u and ends at v
C. u is node and v is an edge.
D. both u and v are edges.
Answer: B. e begins at u and ends at v
27. A binary tree whose every node has either zero or two children is called .........
A. Complete binary tree
B. Binary Search tree
lOMoARcPSD|3768221
C. Extended binary tree
D. E2 tree
Answer: C. Extended binary tree
28. If every node u in G is adjacent to every other node v in G,A graph is said
to be ........
A. isolated
B. complete
C. finite
D. strongly connected.
Answer: B. complete
29. In a graph if e=[u,v], then u and v are called
A. endpoints of e
B. adjacent nodes
C. neighbours
D. all of the above
Answer: D. all of the above
30. In-order traversing a tree resulted E A C K F H D B G; the pre-order
traversal would return.
A. FAEKCDBHG
B. FAEKCDHGB
C. EAFKHDCBG
D. FEAKDCHBG
Answer: B. FAEKCDHGB
31. A connected graph T without any cycles is called .
A. a tree graph
lOMoARcPSD|3768221
B. free tree
C. a tree
D. All of above
Answer: D. All of above
32. In linked representation of Binary trees LEFT[k] contains the.........of at the node
N, where k is the location.
A. Data
B. Location and left child
C. Right child address
D. Null value
Answer: A. Data
33. If every node u in G adjacent to every other node v in G, A graph is said to be
A. isolated
B. complete
C. finite
D. strongly connected
Answer: B. complete
34. Three standards ways of traversing a binary tree T with root R .......
A. Prefix, infix, postfix
B. Pre-process, in-process, post-process
C. Pre-traversal, in-traversal, post-traversal
D. Pre-order, in-order, post-order
Answer: D. Pre-order, in-order, post-order
35. In threaded binary tree..........points to higher nodes in tree.
A. Info
B. Root
lOMoARcPSD|3768221
C. Threads
D. Child
Answer: C. Threads
36. A graph is said to be........if its edges are assigned data.
A. Tagged
B. Marked
C. Lebeled
D. Sticked
Answer: C. Lebeled
37. If node N is a terminal node in a binary tree then its .........
A. Right tree is empty
B. Left tree is empty
C. Both left & right sub trees are empty
D. Root node is empty
Answer: C. Both left & right sub trees are empty
38. What is the maximum height of any AVL-tree with 7 nodes? Assume that the
height of a tree with a single node is 0.
A. 2
B. 3
C. 4
D. 5
Answer: 3
39. 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: a
40. Which of the below diagram is following AVL tree property?
lOMoARcPSD|3768221
i. ii.
a) only i
b) only i and ii
c) only ii
d) none of the mentioned
Answer: b) only i and ii
41. 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: b) log(p)
42. 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: b) AVL tree store balance factor in every node which costs space
43. A Binary Tree can have
A. Can have 2 children
B. Can have 1 children
C. Can have 0 children
D. All
Answer: All
44. Height of a binary tree is
A. MAX( Height of left Subtree, Height of right subtree)+1
B. MAX( Height of left Subtree, Height of right subtree)
C. MAX( Height of left Subtree, Height of right subtree)-1
D. None
lOMoARcPSD|3768221
Answer: A) MAX( Height of left Subtree, Height of right subtree)+1
45. Postfix expression for (A+B) *(C+D) is
A. ABC*+D+
B. AB+CD+*
C. ABCD++*
D. None
Answer: B) A B + C D + *
46. Match the following for binary tree traversal
(1) Pre Order (A)Left Right Root
(2) In Order (B)Left Root Right
(2) Post Order (C)Root Left Right
A. 1 → A, 2 → B, 3 → C
B. 1 → C, 2 → B, 3 → A
C. 1 → A, 2 → C, 3 → B
D. 1 → B, 2 → A, 3 → C
Answer: B) 1 → C, 2 → B, 3 →
47. The operation of processing each element in the list is known as ......
A. sorting
B. merging
C. inserting
D. traversal
Answer: D. traversal
48. Other name for directed graph is ..........
A. Direct graph
B. Digraph
C. Dir-graph
D. Digraph
Answer: B. Digraph
49. Binary trees with threads are called as .......
lOMoARcPSD|3768221
A. Threaded trees
B. Pointer trees
C. Special trees
D. Special pointer trees
Answer: A. Threaded trees
50. Graph G is...............if for any pair u, v of nodes in G there is a path from u to v or path
from v to u.
A. Leterally connected
B. Widely Connected
C. Unliterally connected
D. Literally connected
Answer: C. Unliterally connected
51. In Binary trees nodes with no successor are called ......
A. End nodes
B. Terminal nodes
C. Final nodes
D. Last nodes
Answer: B. Terminal nodes
52. A connected graph T without any cycles is called ........
A. free graph
B. no cycle graph
C. non cycle graph
D. circular graph
Answer: A. free graph
53. Trees are said...........if they are similar and have same contents at corresponding nodes.
A. Duplicate
B. Carbon copy
lOMoARcPSD|3768221
C. Replica
D. Copies
Answer: D. Copies
54. A connected graph T without any cycles is called a ........
A. A tree graph
B. Free tree
C. A tree d
D. All of the above
Answer: D. All of the above
55. Every node N in a binary tree T except the root has a unique parent called the..........of
N.
A. Antecedents
B. Predecessor
C. Forerunner
D. Precursor
Answer: B. Predecessor
56. In a graph if E=(u,v) means ......
A. u is adjacent to v but v is not adjacent to u
B. e begins at u and ends at v
C. u is predecessor and v is successor
D. both b and c
Answer: D. both b and c
57. Sequential representation of binary tree uses ........
A. Array with pointers
lOMoARcPSD|3768221
B. Single linear array
C. Two dimentional arrays
D. Three dimentional arrays
Answer: A. Array with pointers
58. TREE[1]=NULL indicates tree is ........
A. Overflow
B. Underflow
C. Empty
D. Full
Answer: C. Empty
59. A binary tree whose every node has either zero or two children is called .......
A. complete binary tree
B. binary search tree
C. extended binary tree
D. data structure
Answer: C. extended binary tree
60. Linked representation of binary tree needs..........parallel arrays.
A. 4
B. 2
C. 3
D. 5
Answer: C. 3
61. The depth of complete binary tree is given by ......
lOMoARcPSD|3768221
A. Dn = n log2n
B. Dn= n log2n+1
C. Dn = log2n
D. Dn = log2n+1
Answer: D. Dn = log2n+1
62. Which indicates pre-order traversal?
A. Left sub-tree, Right sub-tree and root
B. Right sub-tree, Left sub-tree and root
C. Root, Left sub-tree, Right sub-tree
D. Right sub-tree, root, Left sub-tree
Answer: C. Root, Left sub-tree, Right sub-tree
63. In a extended-binary tree nodes with 2 children are called ........
A. Interior node
B. Domestic node
C. Internal node
D. Inner node
Answer: C. Internal node
64. A terminal node in a binary tree is called ............
A. Root
B. Leaf
C. Child
D. Branch
Answer: B. Leaf
65. Why do we impose restrictions like
. root property is black
lOMoARcPSD|3768221
. every leaf is black
. children of red node are black
. all leaves have same black
a) to get logarithm time complexity
b) to get linear time complexity
c) to get exponential time complexity
d) to get constant time complexity
Answer: a) to get logarithm time
complexity
66. Cosider the below formations of red-black tree.
All the above formations are incorrect for it to be a redblack tree. then what may be the
correct order?
a) 50-black root, 18-red left subtree, 100-red right subtree
b) 50-red root, 18-red left subtree, 100-red right subtree
c) 50-black root, 18-black left subtree, 100-red right subtree
d) 50-black root, 18-red left subtree, 100-black right subtree
Answer: a) 50-black root, 18-red left subtree, 100-red right subtree
67. What are the operations that could be performed in O(logn) time complexity by
red- black tree?
a) insertion, deletion, finding predecessor, successor
b) only insertion
c) only finding predecessor, successor
d) for sorting
Answer: a) insertion, deletion, finding predecessor, successor
68. When it would be optimal to prefer Red-black trees over AVL trees?
a) when there are more insertions or deletions
b) when more search is needed
c) when tree must be balanced
d) when log(nodes) time complexity is needed
lOMoARcPSD|3768221
Answer: a) when there are more insertions or deletions
69. Why Red-black trees are preferred over hash tables though hash tables have
constant time complexity?
a) no they are not preferred
b) because of resizing issues of hash table and better ordering in redblack trees
c) because they can be implemented using trees
d) because they are balanced
Answer: b) because of resizing issues of hash table and better ordering in redblack trees
70. When to choose Red-Black tree, AVL tree and B-trees?
a) many inserts, many searches and when managing more items respectively
b) many searches, when managing more items respectively and many inserts respectively
c) sorting, sorting and retrieval respectively
d) retrieval, sorting and retrieval respectively
Answer: a) many inserts, many searches and when managing more items respectively
