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
Option : b
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
Option : d
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
Option : b
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
Option : c
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
Option : C
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
Option : c
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
Option : b
If a node having two children is to be deleted from binary search tree, it is
replaced by its
a) In-order predecessor
b) In-order successor
c) Pre-order predecessor
d) None
Option : b
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
Option : d
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
Option : b
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))
Option : b
What does ‘stack underflow’ refer to?
a) accessing item from an undefined stack
b) adding items to a full stack
c) removing items from an empty stack
d) index out of bounds exception
Option : a
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
Option : d
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)
Option : c
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)
Option : b
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
Option : b
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
c) Complete binary tree
d) Max-heap
Option : d
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) 2^n
Option : b
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)
Option : b