List of top Programming and Data Structures Questions on Trees

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is __________. (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?

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)}

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)

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}

Consider the following code:

int a;
int arr[] = {30, 50, 10};
int *ptr = arr[10] + 1;
a = *ptr;
(*ptr)++;
ptr = ptr + 1;
printf("%d", a + arr[1] + *ptr);

Which of the following is the greatest? \[ 0.6, \ 0.666, \ \frac{5}{6}, \ \frac{2}{3} \]

Consider the following hierarchical cache system with the following access times:

\[ \begin{array}{|c|c|c|} \hline \textbf{Cache Level} & \textbf{Hit Rate} & \textbf{Access Time} \\ \hline L1 & 90\% & 1 \text{ ns} \\ L2 & 80\% & 10 \text{ ns} \\ L3 & 100\% & 100 \text{ ns} \\ \hline \end{array} \]

Find \( T_{avg} \) for hierarchical or simultaneous access.

Consider the following algorithm someAlgo that takes an undirected graph \( G \) as input.
someAlgo(G) Let \( v \) be any vertex in \( G \).
1. Run BFS on \( G \) starting at \( v \). Let \( u \) be a vertex in \( G \) at maximum distance from \( v \) as given by the BFS.
2. 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. 3. 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)

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 __________. (Answer in integer)

What is the output of the following C code?

  void foo(int *p, int x) {
      *p = x;
  }

  void main() {
      int *z;
      int a = 20, b = 25;
      z = a;  // Incorrect: Should be z = a;
      foo(z, b);
      printf("%d", a);
  }

Issue: The statement z = a; is invalid because a is an integer, and z is a pointer.

In a binary search tree with the following elements: \( 10, -4, 15, 13, 20, 5, 16, 19 \), the number of edges from node 19 to the root is?

Find the signed binary expansion of the number -6.

Given the following information:
The logical address (L.A.) is 32 bits. The physical address (P.A.) is 20 bits. The page size (P.S.) is 2048 bytes (2 KB). What is the maximum number of entries in the page table?

Consider a binary tree in which every node has either 0 or 2 children. Let \( N>0 \) be the number of nodes in the tree. The number of nodes that have exactly 2 children is:

A binary search tree \( T \) contains \( n \) distinct elements. What is the time complexity of picking an element in \( T \) that is smaller than the maximum element in \( T \)?