B-Tree Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “B-Tree”.

1. 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.
advertisement

2. 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. 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.
advertisement
advertisement

4. 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. 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.
advertisement

6. 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. 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.
advertisement

8. 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. 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.
advertisement

10. 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.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter