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) 2^h, 2^h

b) 2^h-1, 2^h-1

c) 2^h-1, 2^h-1

d) 2h-1, 2h-1

Answer: (b) 2^h-1, 2^h-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 = 2^h+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 = 2^h-1.

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

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

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

MCQ on various aspects in DBMS including database disk access and querying, cost for reading disk block pages, count the number of disk pages required to store a table, serializability, serial schedules, RDBMS Multiple Choice Questions with Answers

Database management systems - MCQ exam questions

1. Which of the following is TRUE about serializable schedules?

a) Every serializable schedule is recoverable.

b) Every serializable schedule contains no conflicting actions.

c) Every 2PL schedule is serializable.

d) Every view serializable schedule is also a conflict serializable

Answer: (c) Every 2PL schedule is serializable

Two-phase locking protocol ensures conflict serializability.

Consider any transaction. If the transaction has acquired its final lock, we say that it has reached the end of growing phase. The point in the schedule is referred as lock point. Now, transactions can be ordered according to their lock points—this ordering is, in fact, a serializability ordering for the transactions.

Every serializable schedule is recoverable – FALSE

Every serializable schedule contains no conflicting actions – FALSE. View serializable schedules may have conflicting actions.

Every view serializable schedule is also a conflict serializable – FALSE. Alternate of this statement is true.

2. Let us join two relations R(a, b) and S(a, c) on attribute a using a merge join. Suppose B(R)=10,000 and B(S)=5,000. Assume a memory size of 101 blocks. If both R and S are already sorted on a, how many disk IOs are needed for a merge join?

a) 10000

b) 15000

c) 5000

d) 150000000

Answer: (b) 15000

Cost of merge join for sorted relations = Sum of number of disk blocks occupied by the relations.

= B(R) + B(S) = 10000 + 5000 = 15000

3. Which of the following is TRUE about recoverable schedules?

a) In a recoverable schedule, if a transaction T commits, then any other transaction that T read from must also have committed.

b) In a recoverable schedule, no transaction will ever be aborted because a transaction that it read from has aborted.

c) Every recoverable schedule is serializable.

d) Every cascadeless schedule is also non-recoverable.

Answer: (a) In a recoverable schedule, if a transaction T commits, then any other transaction that T read from must also have committed.

Let us suppose that there are two transactions T1 and T2 in a schedule. Also, let us suppose that T2 reads a data item (say A) which was written by T1. That is, WRITE(A) of T1 appears before READ(A) of T2. Then, the COMMIT instruction of T1 must appear before the COMMIT of T2.

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

Related posts:

Go to Multiple Choice Questions in DBMS home

Go to Normalization - MCQs page

Go to General Mixed Quiz in all topics of DBMS page

Go to Advanced DBMS Concepts page

Quiz questions with answers on DBMS concepts

calculate blocking factor

TOPICS (Click to Navigate)

Thursday, December 24, 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