Please visit, subscribe and share 10 Minutes Lectures in Computer Science

Thursday, 24 December 2020

Multiple choice questions in Data structures and algorithms with answers set 08

Data structures and algorithms multiple choice questions with answers, important interview questions in data structures, data structures questions for entrance exams, frequently asked questions in data structures and algorithms, GATE questions in data structures with explained answers


Data Structures and Algorithms Multiple Choice Questions

SET 08

 

1. What is the minimum number of nodes in an AVL tree of height 5?

a) 20

b) 21

c) 63

d) 12

Answer: (a) 20

Minimum number of nodes in an AVL tree can be recursively calculated as follows;

Min. number of nodes of height h, N(h) = N(h-1) + N(h-2) + 1

Here, 1 is added to include the root node.

N(0) = 1,

N(1) = 2,

N(2) = N(1) + N(0) + 1 = 2+1+1 = 4,

N(3) = N(2) + N(1) + 1 = 4 + 2 + 1 = 7,

N(4) = 12,

N(5) = 20.

AVL tree

An AVL tree is a binary search tree with a self-balancing condition stating that the difference between the height of the left and right subtrees cannot be no more than one.

An AVL tree has the following properties:

1. The sub-trees of every node differ in height by at most one.

2. Every sub-tree is an AVL tree.

 

2. What is the minimum number of nodes that must be examined in order to find the minimum value in an AVL tree of height 5?

a) 20

b) 3

c) 12

d) 5

Answer: (b) 3

Minimum value in an AVL tree can be found at the left most node that has left pointer NULL. Such a node can be found at a height of 3 for an AVL tree of height 5.

 

3. Consider a perfect binary tree of height h. Which of the following options represents the minimum and maximum number of nodes in the right sub-tree of the root?

a) 2h, 2h

b) 2h-1, 2h-1

c) 2h-1, 2h-1

d) 2h-1, 2h-1

Answer: (b) 2h-1, 2h-1

A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level. In this tree each level contains the maximum number of nodes, ie., every level is completely full of nodes.

The number of nodes in a perfect binary tree = 2h+1-1

As per the question, we need to find the number of nodes in the right sub-tree alone. Also, the right sub-tree is at height less than that of original tree. Hence, the number of nodes = 2h-1.

 For a perfect binary tree, the minimum and maximum number of nodes will be 2h+1-1. Hence, for the right sub-tree alone, they are 2h-1.

 

*************************

Interview questions and answers in data structure and algorithms

DSA quiz questions with answers explained

Solved true or false questions in DSA

Practice questions in data structures

Data structures and algorithms GATE exam questions 

What is perfect binary tree and how many nodes it can contain in maximum?

Entrance exam questions with answers in Data structures for Tamilnadu engineering entrance

Entrance exam questions with answers in Data structures for IIT-JEE entrance exam

Entrance exam questions with answers in Data structures for JNTU engineering entrance

 

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents