Assignment 1 Solutions
Part of
the homework for 22C:50, Spring 2003
|
no solutions offered to the above!
A complete binary tree has n+1 leaves, always, without exception. (Complete binary trees have no null pointers). If the tree might be incomplete, it has at most n+1 leaves, or alternately, the sum of leaves and null pointers is n+1.
For each item, we need space for two pointers, plus two integers. On most modern machines, an integer is 4 bytes and a pointer is 4 bytes, so we need 8 bytes per item. With n items, we therefore need n+1 bytes of memory.
a) What is the address of p?
ap
b) What is the value of p?
ao
Indirect addressing takes the value that might otherwise be used as an operand and uses it as a pointer to the operand. For example, register-indirect addressing uses the contents of a register as a pointer, where normal register addressing directly uses the contents of that register.
In its most elementary form, indexed addressing involves taking the sum of the contents of an index register with a displacement to compute the address of the operand.