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
