26 + Interview Questions in B-Trees in Data Structures & Algorithms I Page 1 InterviewSolution

1.	Which of the following is false?(a) 2-3 tree requires less storage than the BST(b) lookup in 2-3 tree is more efficient than in BST(c) 2-3 tree is shallower than BST(d) 2-3 tree is a balanced treeThe above asked question is from B-Trees in chapter B-Trees of Data Structures & Algorithms IThis question was posed to me in quiz.
Answer» CORRECT choice is (a) 2-3 tree REQUIRES less STORAGE than the BST Best explanation: Search is more efficient in the 2-3 tree than in BST. 2-3 tree is a BALANCED tree and performs efficient insertion and deletion and it is shallower than BST. But, 2-3 tree requires more storage than the BST.

Discussion

2.	AVL trees provide better insertion the 2-3 trees.(a) True(b) FalseQuestion is from B-Trees in division B-Trees of Data Structures & Algorithms IThe question was posed to me in a job interview.
Answer» Correct answer is (B) False Easiest explanation - Insertion in AVL tree and 2-3 tree requires searching for proper POSITION for insertion and transformations for balancing the tree. In both, the trees searching takes O(log N) time, but rebalancing in AVL tree takes O(log n), while the 2-3 tree takes O(1). So, 2-3 tree provides better INSERTIONS.

Discussion

3.	Which of the following is not true about the 2-3 tree?(a) all leaves are at the same level(b) it is perfectly balanced(c) postorder traversal yields elements in sorted order(d) it is B-tree of order 3My question comes from B-Trees in section B-Trees of Data Structures & Algorithms II have been asked this question in class test.
Answer» Right CHOICE is (c) postorder traversal yields elements in sorted order Explanation: In a 2-3 tree, LEAVES are at the same LEVEL. And 2-3 trees are perfectly balanced as every path from root node to the NULL link is of EQUAL length. In 2-3 tree in-order traversal yields elements in sorted order.

Discussion

4.	LLRB maintains 1-1 correspondence with 2–3 trees.(a) True(b) FalseThis is a very interesting question from B-Trees topic in section B-Trees of Data Structures & Algorithms IThe question was posed to me during an online exam.
Answer» Right OPTION is (a) True Easiest EXPLANATION - LLRB (LEFT Leaning Red Black tree)is the data STRUCTURE which is used to implement the 2-3 tree with very BASIC code. The LLRB is like the 2-3 tree where each node has one key and two links. In LLRB the 3-node is implemented as two 2-nodes connected by the red link that leans left. Thus, LLRB maintains 1-1correspondence with 2–3 tree.

Discussion

5.	Which of the following data structure can provide efficient searching of the elements?(a) unordered lists(b) binary search tree(c) treap(d) 2-3 treeQuestion is from B-Trees in chapter B-Trees of Data Structures & Algorithms IThe question was posed to me in final exam.
Answer» The correct choice is (d) 2-3 tree Easiest explanation - The average case time for lookup in a BINARY search tree, treap and 2-3 tree is O(LOG n) and in unordered LISTS it is O(n). But in the worst case, only the 2-3 trees perform lookup efficiently as it takes O(log n), while others take O(n).

Discussion

6.	Which of the following the BST is isometric with the 2-3 tree?(a) Splay tree(b) AA tree(c) Heap(d) Red – Black treeI'm obligated to ask this question of B-Trees in section B-Trees of Data Structures & Algorithms II had been asked this question in an online quiz.
Answer» Correct answer is (b) AA tree For EXPLANATION: AA tree is isometric of the 2-3 trees. In an AA tree, we store each NODE a level, which is the HEIGHT of the corresponding 2-3 tree node. So, we can convert a 2-3 tree to an AA tree.

Discussion

7.	The height of 2-3 tree with n elements is ______(a) between (n/2) and (n/3)(b) (n/6)(c) between (n) and log2(n + 1)(d) between log3(n + 1) and log2(n + 1)This interesting question is from B-Trees topic in section B-Trees of Data Structures & Algorithms IThis question was addressed to me by my school teacher while I was bunking the class.
Answer» The CORRECT answer is (d) between log3(n + 1) and LOG2(n + 1) To explain: The number of elements in a 2-3 TREE with height h is between 2h – 1 and 3h – 1. THEREFORE, the 2-3 tree with n elements will have the height between log3(n + 1) and log2(n + 1).

Discussion

8.	2-3 tree is a specific form of _________(a) B – tree(b) B+ – tree(c) AVL tree(d) HeapQuestion is taken from B-Trees topic in division B-Trees of Data Structures & Algorithms II had been asked this question during an interview.
Answer» Right option is (a) B – tree Best EXPLANATION: The 2-3 trees is a balanced tree. It is a specific FORM the B – tree. It is B – tree of ORDER 3, where every node can have two child SUBTREES and one key or 3 child subtrees and two keys.

Discussion

9.	Which one of the following data structures are preferred in database-system implementation?(a) AVL tree(b) B-tree(c) B+ -tree(d) Splay treeI would like to ask this question from B-Trees topic in chapter B-Trees of Data Structures & Algorithms II had been asked this question during an interview for a job.
Answer» Right option is (C) B+ -TREE The BEST explanation: The database-system implementations use B+ -tree data structure because they can be USED for multilevel indexing.

Discussion

10.	Which of the following is false?(a) Compared to B-tree, B+ -tree has larger fanout(b) Deletion in B-tree is more complicated than in B+ -tree(c) B+ -tree has greater depth than corresponding B-tree(d) Both B-tree and B+ -tree have same search and insertion efficienciesI want to ask this question from B-Trees topic in section B-Trees of Data Structures & Algorithms II got this question during an interview.
Answer» Correct answer is (C) B+ -tree has greater depth than CORRESPONDING B-tree For EXPLANATION: A B+ -tree has larger FANOUT and therefore have a depth smaller than that of corresponding B-tree.

Discussion

11.	What is the maximum number of keys that a B+ -tree of order 3 and of height 3 have?(a) 3(b) 80(c) 27(d) 26I'm obligated to ask this question of B-Trees topic in chapter B-Trees of Data Structures & Algorithms II got this question in a job interview.
Answer» CORRECT option is (d) 26 To EXPLAIN: A B+ tree of ORDER n and height H can have at most n^h – 1 keys. Therefore MAXIMUM number of keys = 3^3 -1 = 27 -1 = 26.

Discussion

12.	Efficiency of finding the next record in B+ tree is ____(a) O(n)(b) O(log n)(c) O(nlog n)(d) O(1)The above asked question is from B-Trees in chapter B-Trees of Data Structures & Algorithms IThe question was asked in exam.
Answer» CORRECT CHOICE is (d) O(1) BEST explanation: In a B+ -tree finding the next recored (successor) involves accessing an additional LEAF at most. So, the EFFICIENCY of finding the next record is O(1).

Discussion

13.	Statement 1: When a node is split during insertion, the middle key is promoted to the parent as well as retained in right half-node.Statement 2: When a key is deleted from the leaf, it is also deleted from the non-leaf nodes of the tree.(a) Statement 1 is true but statement 2 is false(b) Statement 2 is true but statement 1 is false(c) Both the statements are true(d) Both the statements are falseI'd like to ask this question from B-Trees in section B-Trees of Data Structures & Algorithms IThe question was posed to me by my college director while I was bunking the class.
Answer» CORRECT CHOICE is (a) Statement 1 is true but statement 2 is false Easy explanation - During the SPLIT, the middle key is retained in the right half node and also promoted to parent node. When a key is deleted from the leaf, it is retained in non-leaves, because it can be still a VALID separator between keys in nodes below.

Discussion

14.	Which of the following is false?(a) A B+ -tree grows downwards(b) A B+ -tree is balanced(c) In a B+ -tree, the sibling pointers allow sequential searching(d) B+ -tree is shallower than B-treeMy enquiry is from B-Trees in chapter B-Trees of Data Structures & Algorithms IThe question was posed to me during an online exam.
Answer» The CORRECT answer is (a) A B+ -tree grows downwards To explain: A B+ -tree always grows upwards. And In a B+tree –i)The path from the root to every leaf node is of the same length, so the tree is BALANCED. ii) Leaves are linked, so allow sequential searching. iii) An index is built with a single KEY PER block of data RATHER than with one key per data record, so it is shallower than B-tree.

Discussion

15.	A B+ tree can contain a maximum of 7 pointers in a node. What is the minimum number of keys in leaves?(a) 6(b) 3(c) 4(d) 7My question is based upon B-Trees in portion B-Trees of Data Structures & Algorithms IThis question was addressed to me during an internship interview.
Answer» The correct option is (b) 3 The BEST explanation: Maximum number of pointers in a node is 7, i.e. the order of the B+ -tree is 7. In aB+ tree of order n each LEAF node contains at most n – 1 key and at least ⌈(n − 1)/2⌉ keys. Therefore, a minimum number of keys each leaf can have = ⌈(7 – 1)/2⌉ = 3.

Discussion

16.	Which of the following is true?(a) B + tree allows only the rapid random access(b) B + tree allows only the rapid sequential access(c) B + tree allows rapid random access as well as rapid sequential access(d) B + tree allows rapid random access and slower sequential accessQuestion is from B-Trees in chapter B-Trees of Data Structures & Algorithms IThe question was posed to me during an interview.
Answer» Right ANSWER is (c) B + tree ALLOWS RAPID random ACCESS as well as rapid sequential access Easiest EXPLANATION - The B+ -tree being a variation of B-tree allows rapid random access. In a B+ -tree the leaves are linked together, so it also provides rapid sequential access.

Discussion

17.	In a B+ tree, both the internal nodes and the leaves have keys.(a) True(b) FalseQuestion is taken from B-Trees topic in section B-Trees of Data Structures & Algorithms IThe question was posed to me in final exam.
Answer» Correct answer is (b) False The explanation is: In a B+ -tree, only the LEAVES have keys, and these keys are replicated in non-leaf NODES for defining the PATH for LOCATING individual records.

Discussion

18.	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 occursThis interesting question is from B-Trees topic in division B-Trees of Data Structures & Algorithms II had been asked this question in homework.
Answer» RIGHT option is (a) LARGER the ORDER of B-tree, less frequently the split occurs To explain: 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.

Discussion

19.	Compression techniques can be used on the keys to reduce both space and time requirements in a B-tree.(a) True(b) FalseMy query is from B-Trees topic in portion B-Trees of Data Structures & Algorithms II have been asked this question in an interview.
Answer» Correct answer is (a) True Easiest 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.

Discussion

20.	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) klognThe origin of the question is B-Trees topic in portion B-Trees of Data Structures & Algorithms IThis question was addressed to me in my homework.
Answer» RIGHT CHOICE is (a) logn (K+1) – 1 Easiest 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.

Discussion

21.	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-BlackThis question is from B-Trees in chapter B-Trees of Data Structures & Algorithms II had been asked this question by my school teacher while I was bunking the class.
Answer» Right CHOICE is (d) Red-Black Best 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.

Discussion

22.	B-tree and AVL tree have the same worst case time complexity for insertion and deletion.(a) True(b) FalseMy question is taken from B-Trees topic in section B-Trees of Data Structures & Algorithms IThis question was posed to me at a job interview.
Answer» Right ANSWER is (a) True Best EXPLANATION: Both the B-tree and the AVL tree have O(log n) as WORST case TIME COMPLEXITY for insertion and deletion.

Discussion

23.	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) 5Query is from B-Trees in division B-Trees of Data Structures & Algorithms II got this question during an interview.
Answer» Right answer is (C) 11 For 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.

Discussion

24.	A B-tree of order 4 and of height 3 will have a maximum of _______ keys.(a) 255(b) 63(c) 127(d) 188I would like to ask this question from B-Trees in portion B-Trees of Data Structures & Algorithms II had been asked this question during an interview for a job.
Answer» The correct choice is (a) 255 Easiest 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 = (m^h+1 – 1) keys in this SITUATION. So, REQUIRED number of maximum keys = 4^3+1 – 1 = 256 – 1 = 255.

Discussion

25.	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 keysEnquiry is from B-Trees in portion B-Trees of Data Structures & Algorithms IThis question was addressed to me during an interview for a job.
Answer» Right choice is (d) at LEAST (N – 1)/2 keys The EXPLANATION is: 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.

Discussion

26.	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 treeQuestion is taken from B-Trees in portion B-Trees of Data Structures & Algorithms IThis question was posed to me in a job interview.
Answer» Correct ANSWER is (b) B-tree The BEST 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.

Discussion

Explore topic-wise InterviewSolutions in .

AVL trees provide better insertion the 2-3 trees.(a) True(b) FalseQuestion is from B-Trees in division B-Trees of Data Structures & Algorithms IThe question was posed to me in a job interview.

LLRB maintains 1-1 correspondence with 2–3 trees.(a) True(b) FalseThis is a very interesting question from B-Trees topic in section B-Trees of Data Structures & Algorithms IThe question was posed to me during an online exam.

Which of the following data structure can provide efficient searching of the elements?(a) unordered lists(b) binary search tree(c) treap(d) 2-3 treeQuestion is from B-Trees in chapter B-Trees of Data Structures & Algorithms IThe question was posed to me in final exam.

Which of the following the BST is isometric with the 2-3 tree?(a) Splay tree(b) AA tree(c) Heap(d) Red – Black treeI'm obligated to ask this question of B-Trees in section B-Trees of Data Structures & Algorithms II had been asked this question in an online quiz.

2-3 tree is a specific form of _________(a) B – tree(b) B+ – tree(c) AVL tree(d) HeapQuestion is taken from B-Trees topic in division B-Trees of Data Structures & Algorithms II had been asked this question during an interview.

What is the maximum number of keys that a B+ -tree of order 3 and of height 3 have?(a) 3(b) 80(c) 27(d) 26I'm obligated to ask this question of B-Trees topic in chapter B-Trees of Data Structures & Algorithms II got this question in a job interview.

Efficiency of finding the next record in B+ tree is ____(a) O(n)(b) O(log n)(c) O(nlog n)(d) O(1)The above asked question is from B-Trees in chapter B-Trees of Data Structures & Algorithms IThe question was asked in exam.

A B+ tree can contain a maximum of 7 pointers in a node. What is the minimum number of keys in leaves?(a) 6(b) 3(c) 4(d) 7My question is based upon B-Trees in portion B-Trees of Data Structures & Algorithms IThis question was addressed to me during an internship interview.

In a B+ tree, both the internal nodes and the leaves have keys.(a) True(b) FalseQuestion is taken from B-Trees topic in section B-Trees of Data Structures & Algorithms IThe question was posed to me in final exam.

Compression techniques can be used on the keys to reduce both space and time requirements in a B-tree.(a) True(b) FalseMy query is from B-Trees topic in portion B-Trees of Data Structures & Algorithms II have been asked this question in an interview.

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) klognThe origin of the question is B-Trees topic in portion B-Trees of Data Structures & Algorithms IThis question was addressed to me in my homework.

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-BlackThis question is from B-Trees in chapter B-Trees of Data Structures & Algorithms II had been asked this question by my school teacher while I was bunking the class.

B-tree and AVL tree have the same worst case time complexity for insertion and deletion.(a) True(b) FalseMy question is taken from B-Trees topic in section B-Trees of Data Structures & Algorithms IThis question was posed to me at a job interview.

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) 5Query is from B-Trees in division B-Trees of Data Structures & Algorithms II got this question during an interview.

A B-tree of order 4 and of height 3 will have a maximum of _______ keys.(a) 255(b) 63(c) 127(d) 188I would like to ask this question from B-Trees in portion B-Trees of Data Structures & Algorithms II had been asked this question during an interview for a job.

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 treeQuestion is taken from B-Trees in portion B-Trees of Data Structures & Algorithms IThis question was posed to me in a job interview.