148 + Mcqs in Trees Mcqs Page 2 McqOptions

51.	What is the complexity of given function of insertion.
A.	O(logn)
B.	Amortized O(1)
C.	O(n)
D.	None of the mentioned
Answer» C. O(n)

Discussion

52.	What could be the worst case height of an AVL tree?
A.	0.97 log n
B.	2.13 log n
C.	1.44 log n
D.	N^2 log n
Answer» D. N^2 log n

Discussion

53.	What does the below definations convey?i. A binary tree is balanced if for every node it is gonna hold that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.ii. A binary tree is balanced if for any two leaves the difference of the depth is at most 1.
A.	Weight balanced and height balanced tree definations
B.	Height balanced and weight balanced tree definations
C.	Definations of weight balanced tree
D.	Definations of height balanced tree
Answer» B. Height balanced and weight balanced tree definations

Discussion

54.	What does this pseudo_code return ?
A.	Last added element to heap
B.	First element added to heap
C.	Root of the heap
D.	Leftmost node of the heap
Answer» D. Leftmost node of the heap

Discussion

55.	The number of binary trees with 3 nodes which when traversed in post order gives the sequence A,B,C is ?
A.	3
B.	4
C.	5
D.	6
Answer» D. 6

Discussion

56.	The number of different directed trees with 3 nodes are
A.	2
B.	3
C.	4
D.	5
Answer» C. 4

Discussion

57.	The number of nodes in a complete binary tree of depth d (with root at depth 0) is
A.	2^(d 1) +1
B.	2^(d+1) -1
C.	2^(d 1) -1
D.	2^(d+1) +1
Answer» C. 2^(d 1) -1

Discussion

58.	The number of nodes in a complete binary tree of level 5 is
A.	10
B.	21
C.	63
D.	77
Answer» D. 77

Discussion

59.	One can convert a binary tree into its mirror image by traversing it in
A.	Inorder
B.	Preorder
C.	Postorder
D.	Any order
Answer» D. Any order

Discussion

60.	One can determine whether a Binary tree is a Binary Search Tree by traversing it in .
A.	Pre-order
B.	In-order
C.	Post-order
D.	Any of these
Answer» C. Post-order

Discussion

61.	One can make an exact replica of a Binary Search Tree by traversing it in
A.	In-order
B.	Pre-order
C.	Post-order
D.	Any order
Answer» C. Post-order

Discussion

62.	One way is to have the linear relationship between the elements by means of sequential memory locations and such linear structures are called ______.
A.	Linked list
B.	Stacks
C.	Arrays
D.	All are the same
Answer» D. All are the same

Discussion

63.	In the array representation, what is represented sequentially in memory using a single one-dimensionalarray?
A.	Binary tree
B.	Stacks
C.	Nodes
D.	None of the above
Answer» B. Stacks

Discussion

64.	In the deletion operation of max heap, the root is replaced by
A.	Next available value in the left sub-tree.
B.	Next available value in the right sub-tree.
C.	Any random value from the heap.
D.	Last element of the last level
Answer» E.

Discussion

65.	In the .. traversal we process all of a vertex s descendants before we move to an adjacent vertex.
A.	Depth First
B.	Breadth First
C.	Width First
D.	Depth Limited
Answer» B. Breadth First

Discussion

66.	In which traversal, the root node is visited after the traversal of its left subtree and before the traversal of its right subtree?
A.	Pre-order traversal
B.	In-order traversal
C.	Post-order traversal
D.	Level-order traversal
Answer» C. Post-order traversal

Discussion

67.	In which tree, the right NULL pointer of each node (not having a right child node) points to its in-order successor?
A.	Right-threaded binary tree
B.	Left-threaded binary tree
C.	Full-threaded binary tree
D.	All of the above
Answer» B. Left-threaded binary tree

Discussion

68.	Internal nodes have___________.
A.	Child nodes
B.	Parent nodes
C.	Both (a) and (b)
D.	None of the above
Answer» D. None of the above

Discussion

69.	Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _____.
A.	18
B.	19
C.	20
D.	21
Answer» B. 19

Discussion

70.	Level of any node of a tree is
A.	Height of its left subtree minus height of its right subtree
B.	Height of its right subtree minus height of its left subtree
C.	Its distance from the root
D.	None of these
Answer» D. None of these

Discussion

71.	Like _________- binary trees can also be represented in two ways in the memory array (sequential) representation and linked representation.
A.	Stacks
B.	Queues
C.	Strings
D.	Both (a) and (b)
Answer» E.

Discussion

72.	Maximum number of nodes in a binary tree with height k, where root is height 0, is
A.	2k 1
B.	2k+1 1
C.	2k-1 + 1
D.	2k 1
Answer» C. 2k-1 + 1

Discussion

73.	Number of possible binary trees with 3 nodes is
A.	5
B.	7
C.	9
D.	11
Answer» B. 7

Discussion

74.	Re-balancing of AVL tree costs
A.	(1)
B.	(log n)
C.	(n)
D.	(n2)
Answer» C. (n)

Discussion

75.	Select the code snippet that performs post-order traversal iteratively.
A.	A
B.	B
C.	C
D.	D
Answer» C. C

Discussion

76.	Select the code snippet that performs pre-order traversal iteratively.
A.	A
B.	B
C.	C
D.	D
Answer» D. D

Discussion

77.	Select the code snippet which performs in-order traversal.
A.	A
B.	B
C.	C
D.	D
Answer» C. C

Discussion

78.	Select the code snippet which performs level-order traversal.
A.	A
B.	B
C.	C
D.	D
Answer» B. B

Discussion

79.	Select the code snippet which performs post-order traversal.
A.	A
B.	B
C.	C
D.	D
Answer» B. B

Discussion

80.	Select the code snippet which performs pre-order traversal.
A.	A
B.	B
C.	C
D.	D
Answer» B. B

Discussion

81.	State the complexity of algorithm gien below:
A.	O(n)
B.	O(logn)
C.	O(1)
D.	O(n logn)
Answer» D. O(n logn)

Discussion

82.	The balance factor for an AVL tree is either
A.	0,1 or -1
B.	-2,-1 or 0
C.	0,1 or 2
D.	All the above
Answer» B. -2,-1 or 0

Discussion

83.	The degree of a node is equal to the number of its__________.
A.	Child nodes
B.	Parent nodes
C.	Sibling nodes
D.	Tree nodes
Answer» B. Parent nodes

Discussion

84.	The depth of a binary tree is the highest level number of any ______ in the binary tree.
A.	Leaf node
B.	Parent node
C.	Sibling node
D.	None of the above
Answer» B. Parent node

Discussion

85.	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» E.

Discussion

86.	In a binary tree, the number of terminal or leaf nodes is 10. The number of nodes with two children is
A.	9
B.	11
C.	25
D.	20
Answer» B. 11

Discussion

87.	How to search for a key in a binary search tree?
A.	A
B.	B
C.	C
D.	D
Answer» B. B

Discussion

88.	How will you find the maximum element in a binary search tree?
A.	A
B.	B
C.	C
D.	D
Answer» D. D

Discussion

89.	How will you find the minimum element in a binary search tree?
A.	A
B.	B
C.	C
D.	D
Answer» B. B

Discussion

90.	If each node in a tree has value greater the every value in its left subtree and has value less than every value in its right subtree, the tree is called
A.	AVL tree
B.	Complete tree
C.	Full binary tree
D.	Binary search tree
Answer» E.

Discussion

91.	Each node of a tree stores a data value and has zero or more pointers pointing to the other nodes of the tree, which are also known as its__________.
A.	Child nodes
B.	Leaf nodes
C.	Root
D.	None of the above
Answer» B. Leaf nodes

Discussion

92.	If the in-order and pre-order traversal of a binary tree are D,B,F,E,G,H,A,C and A,B,D,E,F,G,H,C respectively then the post-order traversal of that tree is
A.	D,F,G,A,B,C,H,E
B.	F,H,D,G,E,B,C,A
C.	C,G,H ,F,E,D,B,A
D.	D,F,H,G,E,B,C,A
Answer» E.

Discussion

93.	Binary search tree is an example of complete binary tree with special attributes.
A.	BST does not care about complete binary tree properties.
B.	BST takes care of complete binary tree properties.
C.	It depends upon the input.
D.	None of the above.
Answer» B. BST takes care of complete binary tree properties.

Discussion

94.	Consider below sequences: array=60 90 10 100 40 150 90 reverse 2 to 3 array=60 10 90 100 40 150 90 reverse 3 to 6 array= 60 100 150 40 100 90 90 now printout from 1 to 6 : 60 100 150 40 100 90How to achieve the above operation efficiently?
A.	Use linked lists
B.	Use avl trees
C.	Use red-black trees
D.	Use treaps (cartesian trees)
Answer» E.

Discussion

95.	Consider the below left-left rotation pseudo code where the node contains value pointers to left, right child nodes and a height value and Height() function returns height value stored at a particular node. What is missing?
A.	Height(w-left), x-height
B.	Height(w-right), x-height
C.	Height(w-left), x
D.	Height(w-left)
Answer» B. Height(w-right), x-height

Discussion

96.	Consider the following nested representation of binary trees indicates y and z are the left right subtrees, respectively, of node x. Note that y and z may be NULL or further nested. Which of the following represents a valid binary tree?
A.	(1(234)(567)
B.	(1 2(4 5 6 7))
C.	(1(2 3 NULL)(4 5))
D.	1((2 3 NULL)4 5 6)7)
Answer» B. (1 2(4 5 6 7))

Discussion

97.	Cosider the below formations of red-black tree. All the below 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» B. 50-red root, 18-red left subtree, 100-red right subtree

Discussion

98.	Elements in a nonlinear data structure do not form a sequence for example_________.
A.	Tree
B.	Hash tree
C.	Binary tree
D.	All of the above
Answer» E.

Discussion

99.	Every internal node in a B-tree of minimum degree 2 can have
A.	2, 3 or 4 children
B.	1, 2 or 3 children
C.	2, 4 or 6 children
D.	0, 2 or 4 children
Answer» C. 2, 4 or 6 children

Discussion

100.	If we implement heap as maximum heap , adding a new node of value 15 to the left most node of right subtree . What value will be at leaf nodes of the right subtree of the heap.
A.	15 and 1
B.	25 and 1
C.	3 and 1
D.	2 and 3
Answer» B. 25 and 1

Discussion

Explore topic-wise MCQs in Data Structures Mcqs.

What is the complexity of given function of insertion.

What could be the worst case height of an AVL tree?

What does this pseudo_code return ?

The number of binary trees with 3 nodes which when traversed in post order gives the sequence A,B,C is ?

The number of different directed trees with 3 nodes are

The number of nodes in a complete binary tree of depth d (with root at depth 0) is

The number of nodes in a complete binary tree of level 5 is

One can convert a binary tree into its mirror image by traversing it in

One can determine whether a Binary tree is a Binary Search Tree by traversing it in .

One can make an exact replica of a Binary Search Tree by traversing it in

One way is to have the linear relationship between the elements by means of sequential memory locations and such linear structures are called ______.

In the array representation, what is represented sequentially in memory using a single one-dimensionalarray?

In the deletion operation of max heap, the root is replaced by

In the .. traversal we process all of a vertex s descendants before we move to an adjacent vertex.

In which traversal, the root node is visited after the traversal of its left subtree and before the traversal of its right subtree?

In which tree, the right NULL pointer of each node (not having a right child node) points to its in-order successor?

Internal nodes have___________.

Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _____.

Level of any node of a tree is

Like _________- binary trees can also be represented in two ways in the memory array (sequential) representation and linked representation.

Maximum number of nodes in a binary tree with height k, where root is height 0, is

Number of possible binary trees with 3 nodes is

Re-balancing of AVL tree costs

Select the code snippet that performs post-order traversal iteratively.

Select the code snippet that performs pre-order traversal iteratively.

Select the code snippet which performs in-order traversal.

Select the code snippet which performs level-order traversal.

Select the code snippet which performs post-order traversal.

Select the code snippet which performs pre-order traversal.

State the complexity of algorithm gien below:

The balance factor for an AVL tree is either

The degree of a node is equal to the number of its__________.

The depth of a binary tree is the highest level number of any ______ in the binary tree.

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

In a binary tree, the number of terminal or leaf nodes is 10. The number of nodes with two children is

How to search for a key in a binary search tree?

How will you find the maximum element in a binary search tree?

How will you find the minimum element in a binary search tree?

If each node in a tree has value greater the every value in its left subtree and has value less than every value in its right subtree, the tree is called

Each node of a tree stores a data value and has zero or more pointers pointing to the other nodes of the tree, which are also known as its__________.

If the in-order and pre-order traversal of a binary tree are D,B,F,E,G,H,A,C and A,B,D,E,F,G,H,C respectively then the post-order traversal of that tree is

Binary search tree is an example of complete binary tree with special attributes.

Consider below sequences: array=60 90 10 100 40 150 90 reverse 2 to 3 array=60 10 90 100 40 150 90 reverse 3 to 6 array= 60 100 150 40 100 90 90 now printout from 1 to 6 : 60 100 150 40 100 90How to achieve the above operation efficiently?

Consider the below left-left rotation pseudo code where the node contains value pointers to left, right child nodes and a height value and Height() function returns height value stored at a particular node. What is missing?

Consider the following nested representation of binary trees indicates y and z are the left right subtrees, respectively, of node x. Note that y and z may be NULL or further nested. Which of the following represents a valid binary tree?

Cosider the below formations of red-black tree. All the below formations are incorrect for it to be a redblack tree. Then what may be the correct order?

Elements in a nonlinear data structure do not form a sequence for example_________.

Every internal node in a B-tree of minimum degree 2 can have

If we implement heap as maximum heap , adding a new node of value 15 to the left most node of right subtree . What value will be at leaf nodes of the right subtree of the heap.