In a B+- tree where each node can hold at most four key values, a root to leaf path consists of the following nodes:
\( A = (49, 77, 83, -) \)
\( B = (7, 19, 33, 44) \)
\( C = (20^*, 22^*, 25^*, 26^*) \)
The *-marked keys signify that these are data entries in a leaf. Assume that a pointer between keys \( k_1 \) and \( k_2 \) points to a subtree containing keys in \([ k_1, k_2 )\), and that when a leaf is created, the smallest key in it is copied up into its parent. A record with key value 23 is inserted into the B+- tree. The smallest key value in the parent of the leaf that contains 25* is __________ . (Answer in integer)
In a B+- tree where each node can hold at most four key values, a root to leaf path consists of the following nodes:
\( A = (49, 77, 83, -) \)
\( B = (7, 19, 33, 44) \)
\( C = (20^*, 22^*, 25^*, 26^*) \)
The *-marked keys signify that these are data entries in a leaf. Assume that a pointer between keys \( k_1 \) and \( k_2 \) points to a subtree containing keys in \([ k_1, k_2 )\), and that when a leaf is created, the smallest key in it is copied up into its parent. A record with key value 23 is inserted into the B+- tree. The smallest key value in the parent of the leaf that contains 25* is __________ . (Answer in integer)
Show Hint
Solution and Explanation
Step 1: Identify the Correct Leaf Node - Key 23 is inserted into leaf \( C \), which currently contains \( (20^*, 22^*, 25^*, 26^*) \). - After insertion, \( C \) will contain \( (20^*, 22^*, 23^*, 25^*, 26^*) \).
Step 2: Leaf Node Splitting - Since each node can hold at most 4 keys, the leaf splits into two: - First leaf: \( (20^*, 22^*, 23^*) \) - Second leaf: \( (25^*, 26^*) \) - The smallest key of the second leaf (\( 25 \)) is pushed up into its parent (\( B \)).
Step 3: Identify Parent Update - The updated keys in \( B \) are now \( (7, 19, 25, 33, 44) \). - Since \( B \) also exceeds the allowed 4 keys, it splits into two nodes: - First node: \( (7, 19) \) - Second node: \( (33, 44) \) - The smallest key of the second node (\( 33 \)) is pushed up into \( A \). Thus, the answer is \( 33 \).
Top Questions on Trees
- Consider the following algorithm tt{someAlgo that takes an undirected graph \( G \) as input.} tt{someAlgo(G)} Let \( v \) be any vertex in \( G \). Run BFS on \( G \) starting at \( v \). Let \( u \) be a vertex in \( G \) at maximum distance from \( v \) as given by the BFS. Run BFS on \( G \) again with \( u \) as the starting vertex. Let \( z \) be the vertex at maximum distance from \( u \) as given by the BFS. Output the distance between \( u \) and \( z \) in \( G \). The output of tt{someAlgo(T)} for the tree shown in the given figure is ___________ . (Answer in integer) \begin{center} \includegraphics{q59_fig.png} \end{center}
- In a B+- tree where each node can hold at most four key values, a root to leaf path consists of the following nodes: \( A = (49, 77, 83, -) \)
\( B = (7, 19, 33, 44) \)
\( C = (20^*, 22^*, 25^*, 26^*) \)
The *-marked keys signify that these are data entries in a leaf. Assume that a pointer between keys \( k_1 \) and \( k_2 \) points to a subtree containing keys in \([ k_1, k_2 )\), and that when a leaf is created, the smallest key in it is copied up into its parent. A record with key value 23 is inserted into the B+- tree. The smallest key value in the parent of the leaf that contains 25* is ___________ . (Answer in integer) - Suppose the values 10, −4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let \( T \) be the resulting binary search tree. The number of edges in the path from the node containing 19 to the root node of \( T \) is \underline{{1cm}}. {(Answer in integer)}
- Consider a binary tree \( T \) in which every node has either zero or two children. Let \( n%gt;0 \) be the number of nodes in \( T \). Which ONE of the following is the number of nodes in \( T \) that have exactly two children?
A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:
P: Unsorted doubly linked list with pointers to the head node and tail node of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.
Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size \( n \) of these data structures?
Questions Asked in GATE CS exam
In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ______________. {(Answer in integer)}
- GATE CS - 2025
- Flip-Flop
Consider the following C code segment:
int x = 126, y = 105; do { if (x > y) x = x - y; else y = y - x; } while (x != y); printf("%d", x);The output of the given C code segment is ____________. (Answer in integer)
- GATE CS - 2025
- Programming in C
The following two signed 2’s complement numbers (multiplicand \( M \) and multiplier \( Q \)) are being multiplied using Booth’s algorithm:
Multiplicand (\( M \)) Multiplier (\( Q \)) 1100 1101 1110 1101 1010 0100 1010 1010 The total number of addition and subtraction operations to be performed is __________. (Answer in integer)
- GATE CS - 2025
- Complementation
The maximum value of \(x\) such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is __________ (answer in integer).
- GATE CS - 2025
- Programming and Data Structures
Consider the following C program
The value printed by the given C program is __________ (Answer in integer).- GATE CS - 2025
- Programming in C