Engineering Questions with Answers - Multiple Choice Questions

B-Tree Multiple Choice MCQ

1 - Question

Which of the following is the most widely used external memory data structure?
a) AVL tree
b) B-tree
c) Red-black tree
d) Both AVL tree and Red-black tree

View Answer

Answer: b
Explanation: In external memory, the data is transferred in form of blocks. These blocks have data valued and pointers. And B-tree can hold both the data values and pointers. So B-tree is used as an external memory data structure.




2 - Question

B-tree of order n is a order-n multiway tree in which each non-root node contains __________
a) at most (n – 1)/2 keys
b) exact (n – 1)/2 keys
c) at least 2n keys
d) at least (n – 1)/2 keys

View Answer

Answer: d
Explanation: A non-root node in a B-tree of order n contains at least (n – 1)/2 keys. And contains a maximum of (n – 1) keys and n sons.




3 - Question

A B-tree of order 4 and of height 3 will have a maximum of _______ keys.
a) 255
b) 63
c) 127
d) 188

View Answer

Answer: a
Explanation: A B-tree of order m of height h will have the maximum number of keys when all nodes are completely filled. So, the B-tree will have n = (mh+1 – 1) keys in this situation. So, required number of maximum keys = 43+1 – 1 = 256 – 1 = 255.




4 - Question

Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many nodes are written?
a) 14
b) 7
c) 11
d) 5

View Answer

Answer: c
Explanation: If s splits occur in a B-tree, 2s + 1 nodes are written (2 halves of each split and the parent of the last node split). So, if 5 splits occurred, then 2 * 5 + 1, i.e. 11 nodes are written.




5 - Question

B-tree and AVL tree have the same worst case time complexity for insertion and deletion.
a) True
b) False

View Answer

Answer: a
Explanation: Both the B-tree and the AVL tree have O(log n) as worst case time complexity for insertion and deletion.




6 - Question

2-3-4 trees are B-trees of order 4. They are an isometric of _____ trees.
a) AVL
b) AA
c) 2-3
d) Red-Black

View Answer

Answer: d
Explanation: 2-3-4 trees are isometric of Red-Black trees. It means that, for every 2-3-4 tree, there exists a Red-Black tree with data elements in the same order.




7 - Question

Figure shown below is B-tree of order 5. What is the result of deleting 130 from the tree?
b-tree-questions-answers-q7
a)b-tree-questions-answers-q7a
b)b-tree-questions-answers-q7b
c) b-tree-questions-answers-q7c
d)b-tree-questions-answers-q7d

View Answer

Answer: c
Explanation: Each non-root in a B-tree of order 5 must contain at least 2 keys. Here, when the key 130 is deleted the node gets underflowed i.e. number of keys in the node drops below 2. So we combine the node with key 110 with it’s brother node having keys 144 and 156. And this combined node will also contain the separator key from parent i.e. key 140, leaving the root with two keys 110 and 160.




8 - Question

 What is the best case height of a B-tree of order n and which has k keys?
a) logn (k+1) – 1
b) nk
c) logk (n+1) – 1
d) klogn

View Answer

Answer: a
Explanation: B-tree of order n and with height k has best case height h, where h = logn (k+1) – 1. The best case occurs when all the nodes are completely filled with keys.




9 - Question

Compression techniques can be used on the keys to reduce both space and time requirements in a B-tree.
a) True
b) False

View Answer

Answer: a
Explanation: The front compression and the rear compression are techniques used to reduce space and time requirements in B-tree. The compression enables to retain more keys in a node so that the number of nodes needed can be reduced.




10 - Question

Which of the following is true?
a) larger the order of B-tree, less frequently the split occurs
b) larger the order of B-tree, more frequently the split occurs
c) smaller the order of B-tree, more frequently the split occurs
d) smaller the order of B-tree, less frequently the split occurs

View Answer

Answer: a
Explanation: The average probability of the split is 1/(⌈m / 2⌉ – 1), where m is the order of B-tree. So, if m larger, the probability of split will be less.

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners