Design & Analysis of Algorithm logo

DAA Unit 3 Part 1 MCQs

PREV
NEXT
Menu
Unit 3

Advance Data Structure:- Binary Search Tree, AVL Tree, Red-Black Tree, B-Tree, B+ Tree, Binomial Tree, Binomial Heap, Fibonacci Heap, Trie, Skip List.

Q1 – The depth of a complete binary tree with ‘n’ nodes is
  1. log(n + 1) – 1
  2. log n
  3. log(n – 1) + 1
  4. log n + 1

Ans – (1)

Explanation – Complete binary tree – A binary tree that has each level entirely filled (except last leaf node level) with nodes. 

Complete binary Tree

Its depth = 2(d+1) + 1

à n + 1 = 2(d+1)

à log(n + 1) = d + 1

à d = log(n + 1) – 1.

Number of nodes = 4

Depth is = log(n + 1) – 1 = log(4 + 1) – 1 = 2

Q2 – Average successful search taken by binary search on a sorted array of 10 items is
  1. 2.6
  2. 2.7
  3. 2.8
  4. 2.9

Ans – (4)

Explanation –

Time refers to the average number of comparisons.

Create a binary search tree with 10 items. You will see that there are 1 root, 2 branches, 2 nodes from each branch, then 4 branches and 4 nodes from each branch, then 3 nodes in the leaf. 

Create a binary search tree with 10 items. You will see that there are 1 root, 2 branches, 2 nodes from each branch, then 4 branches and 4 nodes from each branch, then 3 nodes in the leaf. 

So, you might have to reach these heights to collect the components.

Average comparisons = (1*1 + 2*2 + 3*4 + 4*3) / 10 = 29/10 = 2.9

 

Q3 – A binomial tree Bk contains
  1. 2k nodes
  2. height k
  3. exactly kCi nodes
  4. All of these

Ans – (4)

Explanation – A binomial tree is an ordered tree, and it is denoted by Bk where k is the degree of the root.
It has some properties which is –
1. Bk tree has 2k nodes.
2. Degree of root is k. it means the root have k children. All the other nodes who are present in the tree have a degree less than k.
3. Height of the tree is also k.
4. There are exactly kCi nodes at depth i, where kCi = (k!) / (k-i)! i!

https://compgeek.co.in/binomial-heap/ to know more.

Q4 – The maximum degree of any node in an n-node binomial tree is
  1. n
  2. n*lgn
  3. logn
  4. none of these

Ans – (3)

Explanation –

Degree of a node is the number of its children.

Minimum degree is 0 and the maximum degree goes up to log n.

In B3 binomial tree, the number of nodes is 8, and the root of the binomial tree has maximum degree 3 = log 8. All the other nodes have a degree from 0 to 2.

Q5 – In B-Tree, every node can contain at most _____ keys.
  1. 2t
  2. t-1
  3. 2t-1
  4. t

Ans – (3)

Explanation –

You can see the degree of a B-Tree.

Maximum degree = 2t – 1

Minimum degree = t

Q6 – Suppose h is the height of B-tree, t is the minimum degree and n is the number of keys, then
  1. n ≥ logt((n+1)/2)
  2. h ≤ logt((n-1)/2)
  3. h ≤ logt((n+1)/2)
  4. h = logt(n/2)

Ans – (3)

Explanation –

With n nodes and t being the smallest number of children a non-root node can have, the maximum height of the B-Tree that can exist is: h ≤ logt((n+1)/2)

Q7 – Every node in the b-tree, except the root, must have at least
  1. t keys
  2. one key
  3. t-1 keys
  4. t+1 keys

Ans – (3)

Explanation –

The maximum and minimum keys that a node can hold are bound. The minimum degree of the B-tree, which is a fixed integer with a value greater than two (t ≥ 2), can be used to represent these bounds:

(a) Each node must have t-1 keys, except the root. This means that every internal node except for the root has t or more children. The root of the tree must include at least one key if it is not empty.

(b) Each node can hold a maximum of 2t-1 keys. An internal node can therefore have a maximum of 2t children. If a node has exactly 2t-1 keys, we say it is full.

https://compgeek.co.in/b-tree/ to know more.

Q8 – In red-black tree, each red node have a ______ children.
  1. Red
  2. Red or Black
  3. Black
  4. None of these

Ans – (3)

Explanation –

These four requirements must be met by a red-black tree:

The root node is always a black node.

It is believed that a nil is black.

Every red node has black children.

The equal number of black nodes appear on each path from the root to the leaf nodes.

Q9 – The root of red-black tree is
  1. Black
  2. Red
  3. Both red or black
  4. Red or black

Ans – (1)

Explanation –

These four requirements must be met by a red-black tree:

The root node is always a black node.

It is believed that a nil is black.

Every red node has black children.

The equal number of black nodes appear on each path from the root to the leaf nodes.

Q10 – The height of Red-Black Tree is at most
  1. log n
  2. 2log(n+1)
  3. log(n+1)
  4. log((n+1)/2)

Ans – (2)

Explanation –

The claim follows from the fact that in a binary tree, the longest root-to-leaf path has length k, and the number of nodes on this path is at least 2^k-1. Therefore, if we have n nodes in the tree, we must have n >= 2^k-1, which implies k <= log2(n+1).

For Red-Black trees, property states that every root-to-leaf path has the same number of black nodes. Therefore, if there is a path with at most k black nodes, then all paths have at most k black nodes. Hence, the longest root-to-leaf path in the tree has at most log2(n+1) black nodes.

Other property of Red-Black trees states that every red node has two black children. Therefore, in any path from the root to a leaf, the number of black nodes is at least half the number of nodes on the path (since every red node is followed by two black nodes). The root node is black. Therefore, the number of black nodes in the tree is at least half the number of nodes in the tree, which implies that the number of black nodes is at least ⌊ n/2 ⌋, and the height of Red-Black Tree is at most 2log(n+1).

Q11 – A full binary tree with n leaves contain
  1. log2n nodes
  2. 2n + 1 nodes
  3. 2n – 1 nodes
  4. n nodes

Ans – (3)

Explanation –

Draw the tree and check.

Q12 – A full binary tree with n non-leaf nodes contains
  1. n+1 nodes
  2. 2n nodes
  3. 2n+1 nodes
  4. log2n nodes

Ans – (3)

Explanation – Draw the tree and check.

Q13 – If a binary tree traversed is inorder then number of the node are printed in an order
  1. Descending Order
  2. Ascending Order
  3. Randomly
  4. none of these

Ans – (2)

Explanation – In an in-order traversal of a binary tree, the left subtree is visited first, followed by the root node, and then the right subtree. When performing an in-order traversal on a binary search tree, the nodes are visited in ascending order. All nodes in its left subtree have keys that are less than the node’s key, and all nodes in its right subtree have keys that are greater than the node’s key.

Q14 – The five items P, Q, R, S and T are pushed in a stack, one after the other starting from P. The stack is popped 3 times and each element is inserted in a queue. Then two elements are deleted from queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
  1. Q
  2. R
  3. S
  4. T

Ans – (3)

Explanation –

Stack have PQRST in which T comes first and P comes last.

The stack is popped 3 times – T S R

Each element is inserted in a queue – T S R in which T comes first and R comes last.

Two elements are deleted from the queue and pushed to stack.

T comes first and pushed to stack.

S comes second and pushed to stack.

One item is popped from stack that is S.

Q15 – which of the following data structures has least height. (RPSC-2021)
  1. B-tree of order 4
  2. b-tree of order 3
  3. B-tree of order 5
  4. b-tree of order 6

Ans – (4)

Explanation –

The height of a B-tree or a b-tree is determined by the order of the tree, which is the maximum number of children that a node can have. The larger the order, the larger the maximum number of keys that can be stored in each node, and therefore the shallower the tree will be.

Therefore, the data structure with the least height would be the B-tree of order 6, since it has the largest order among the given options. The B-tree of order 6 can store up to 5 keys per node, and has a minimum of 2 children per non-root node. This makes it possible to store a large number of keys in a relatively small number of nodes, which results in a shallower tree.

Q16 – The number of leaf nodes in a rooted tree of ‘n’ nodes with each node having 0 or 3 children is (RPSC-2021)
  1. n/2
  2. (n-1)/3
  3. (n-1)/2
  4. (2n+1)/3

Ans – (4)

Explanation –

You can calculate by hidden trial rule. If you have just root node, option 4 will give you the result.

Q17 – In a binary min heap containing ‘n’ numbers, the largest can be found in ______ time. (RPSC-2021)
  1. ÆŸ(n)
  2. ÆŸ(logn)
  3. ÆŸ(loglogn)
  4. ÆŸ(1)

Ans – (1)

Explanation – To find the largest element in a binary min heap, we need to perform a linear search of all the leaf nodes to find the maximum value among them. Since a binary heap is a complete binary tree, it contains at most n/2 leaf nodes. Therefore, the time complexity of finding the largest element in a binary min heap is Θ(n), where n is the total number of elements in the heap.

Q18 – From the following what is the average case time complexity for finding the height of the binary tree? (RPSC-2022)
  1. h = O(loglogn)
  2. h = O(nlogn)
  3. h = O(n)
  4. h = O(logn)

Ans – (4)

Q19 – What is the balance factor of an AVL tree? (DSSSB PGT 2021)
  1. |h(TR)| ≤ 1
  2. |h(TL)| ≤ 1
  3. |h(TL) – h(TR)| ≤ 1
  4. |h(TL) + h(TR)| ≤ 1

Ans – (3)

Explanation – An AVL tree is called balanced when the difference of height is -1, 0, 1. It is also called balance factor (BF).

BALANCE FACTOR = Height of left subtree – Height of right subtree

That’s why |height(TL) – height(TR)| ≤ 1

https://compgeek.co.in/avl-tree/ to know more.

Q20 – Which of the following statement is false about a B-tree of order M? (DSSSB PGT 2021)
  1. Leaf nodes are not at the same level.
  2. The internal nodes except the root have at least ceiling(M/2) child nodes.
  3. The root has at least two child nodes and at most M child nodes.
  4. A node is full if it has (M – 1) keys.

Ans – (1)

Explanation –

All the leaf nodes are at the same level.

PREV
NEXT

BOOKS

Algorithm T H CoremanAlgorithm by Udit AgarwalAlgorithm Ellis HorowitzData Structure & Algorithm Made Easy Narasimha

 

GATE Study Material
Previous Year Paper
Subjective Questions