Final answer:
The question relates to calculating the space overhead in a full binary tree where internal nodes store two pointers and leaf nodes store a data field. Overhead is considered the space of pointers and padding for data alignment. We find the total overhead by accounting for all pointers and additional bytes in the leaf nodes and divide it by the total space used to derive the fraction in lowest terms.
Step-by-step explanation:
The question asks about the fraction of total space taken up by overhead in a full binary tree, where internal nodes store two pointers, and leaf nodes store a data field without pointers. With pointers taking 4 bytes and data objects taking 21 bytes, we calculate overhead based on the structure of a full binary tree.
In a full binary tree, there is always one more leaf node than there are internal nodes. If n is the number of internal nodes, then n + 1 is the number of leaf nodes. The overall memory for internal nodes is 2n x 4 bytes because each internal node has two pointers. Leaf nodes require (n + 1) x 21 bytes, as they only have a data field.
Now, let's calculate overhead. Overhead includes the pointers and the extra space not used for data. This is 2n x 4 bytes for internal nodes' pointers plus the extra space associated with converting the 21 bytes of data into the nearest multiple of 4 bytes (which is 24 bytes as memory is often allocated in multiples of 4 for alignment purposes). So each leaf node has an overhead of 3 bytes, totaling (n + 1) x 3 bytes.
Thus, the total overhead is 2n x 4 bytes for the internal nodes plus (n + 1) x 3 bytes for the leaf nodes. The total memory used is the sum of the memory for the internal nodes (2n x 4 bytes) and leaf nodes ((n + 1) x 24 bytes, including the padding for alignment). The fraction of overhead is the total overhead divided by the total memory usage. Simplifying the fraction will give us the overhead in the lowest terms.