Pervious Year question: B Tree | Programming and Data Structures - Computer Science Engineering (CSE) PDF Download

Q1: A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?  (2008)
(a) 3
(b) 4
(c) 5
(d) 6
Ans: (c)
Sol: Total 5 splitting will occur during 10 successive insertions
 Let's take 10 successive key values as {1 ,2 ,3 , …10} which can cause maximum possible splits.

Q2: Consider the following 2-3-4 tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree  (2003)

What is the result of inserting G in the above tree ?

(a) A
(b) B
(c) C
(d) None of the above
Ans: (b)
Sol: Once we add G , the leaf node becomes B G H I , since we can have only 3 keys. the node has to split at G or H , and G or H will be added to parent node.
Since P is the parent node in options 1 and 2 , its evident the 3rd element i.e. H should be selected for splitting (because after adding any key from the leftmost child node, P becomes the 3rd element in the node)
 Now parent node becomes H L P U , select P as for splitting, and you get option B.

Q3:  Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
 A 2-3 tree is such that a. All internal nodes have either 2 or 3 children b. All paths from root to the leaves have the same length.
The number of internal nodes of a 2-3 tree having 9 leaves could be  (1992)
(a) 4
(b) 5
(c) 6
(d) 7
Ans: (a, d)
Sol:
 4 → When each leaf has 3 child. So 9 / 3 = 3 Internal nodes, Then one internal node those internal nodes.
 7 → When each leaf has 2 child  & one leaf out of 4 get 3 child.  Ex → 8 / 4 = 2 child per internal node. Then one of that internal node get extra third child. Then 2 internal nodes to connect these 4 .Then 1 internal node to connect this 2 . So 4+2+1=7