Sample Sample Final Exam COMP2521
[Instructions] [C language]
[Q1] [Q2] [Q3] [Q4] [Q5] [Q6] [Q7] [Q8]

Question 7

Questions on the following topics:
Tree ADTs: Binary Search Tree, Balanced trees, 2-3-4 trees, heaps, etc.

For example,

Consider the following 2-3-4 tree:

Based on the above answer the following questions:

  1. What value(s) would be stored in the root node of the 2-3-4 tree after the insertion of the value 8? What value(s) would be stored in the node that now contains 8?

  2. What value(s) would be stored in the root node of the 2-3-4 tree after the insertion of the value 42? What value(s) would be stored in the node that now contains 42?

Note:

First insert a value in the suitable leaf node, and if required (due to an overflow), promote a node.

For this question, if you need to promote a value, you must promote the smaller value from the possible alternatives (if any). For example, if you insert 20 in the node [10, 15, 28], you need to promote 15, and the two nodes are [10] and [20,28]. Here, for promoting a value, we have two possible alternatives 15 or 20, we select minimum of these two values.

Answer:
A.  (after inserting 8 into 2-3-4 tree)

root = [12|35|60]
leaf = [1|7|8]

Hint: 
We insert at leaf level. 
No overflow, so no split is required.


B.  (after inserting 42 into 2-3-4 tree)

root = [35]
leaf = [42|60]

Hint: 
We insert at leaf level.
At leaf, we split the overflow node [36,42,44,57], promote 42, two nodes [36] and [44,57].
After that, we split the overflow node [12,35,42,60], promote 35, two nodes [12] and [42,60] . 
Root node now is 35. 

Type the answer to this question into the file called q7.txt and submit it using the command:

$ submit q7

The above command will make a copy of q7.txt as your answer for this question.