This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “B-Tree”.
1. 2-3-4 trees are B-trees of order 4. They are an isometric of _____ trees.
B ) AA
Explanation: Red-Black trees are isometric in groups of 2-3-4. It implies that there is a Red-Black tree with data elements in the same order for every 2-3-4 tree.
2. Figure shown below is B-tree of order 5. What is the result of deleting 130 from the tree?
Explanation: In a B-tree of order 5, each non-root must have at least two keys. As key 130 is removed, the node becomes underflowed, meaning the number of keys in the node falls below 2. As a result, we merge the key 110 node with its brother node, which has keys 144 and 156. The separator key from the parent, key 140, will also be present in this combined node, leaving the root with two keys 110 and 160.
3. What is the best case height of a B-tree of order n and which has k keys?
A) logn (k+1) – 1
C) logk (n+1) – 1
Explanation: The best case height of a B-tree of order n and height k is h, where h = logn (k+1) – 1. When all of the nodes are fully loaded with keys, the best case scenario happens.
4. Compression techniques can be used on the keys to reduce both space and time requirements in a B-tree.
Explanation: Front compression and back compression are two methods used in B-tree to minimise space and time requirements. Because of the compression, more keys can be stored in a node, reducing the number of nodes needed.
5. 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
Explanation: The average split likelihood is 1/(m / 2 – 1), where m is the B-tree order. As a result, as m grows larger, the likelihood of a split decreases.
6. Which of the following is the most widely used external memory data structure?
A) AVL tree
C) Red-black tree
D) Both AVL tree and Red-black tree
Explanation: The data is transferred in blocks to external memory. These blocks contain data and pointers. Furthermore, the B-tree can store both data values and pointers. As a result, the B-tree data structure is used as an external memory data structure.
7. 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
Explanation: In a B-tree of order n, every non-root node has at least (n – 1)/2 keys. And it can only have (n – 1) keys and n sons.
8. A B-tree of order 4 and of height 3 will have a maximum of _______ keys.
Explanation: When all nodes are absolutely filled, a B-tree of order m and height h will have the maximum number of keys. 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.
9. Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many nodes are written?
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.
10. B-tree and AVL tree have the same worst case time complexity for insertion and deletion.
Explanation: For insertion and deletion, both the B-tree and the AVL tree have a worst-case time complexity of O(log n).
The B-tree is a self-balancing tree data structure that keeps sorted data and enables logarithmic time searches, sequential access, insertions, and deletions. The B-tree is a variant of the binary search tree that allows nodes to have more than two children. [two] The B-tree is well suited for storage structures that read and write relatively large blocks of data, such as discs, unlike other self-balancing binary search trees. It’s a common database and file system format.