CS 509 Test 2

CS 509, Advanced Programming II

Fall 2001 - Test 2

A colleague of yours claims that a program to neatly layout trees can be written with an algorithm that operates on each node exactly once in a root-to-leaf sweep of the tree. Is your colleague correct? Explain.
Your colleague is incorrect. A child node can't be fixed relative to its siblings until the subtrees rooted at the siblings have been properly formatted; only after the two subtrees have been properly formatted can the two children at the roots be placed relative to each other. This requires a bottom up sweep of the tree.
The vector-provided type size_type represents a value able to hold the maximum number of elements in a vector. Vectors don't provide the type index_type to represent a value able to hold the largest possible index for a vector. A colleague of yours speculates that index_type isn't needed because size_type is good enough. What is your opinion of your colleague's speculation? Explain.
Your colleague also speculates that vectors could provide only the type index_type, which could also be used to represent size_type. What is your opinion of this speculation? Explain.
In the first case, your colleague is correct. If n is a value of type size_type, then the legal index values are 0 through n - 1, all of which can be interpreted as values of type size_type.
In the second case, your colleague is incorrect. If n is a value of type index_type representing the largest legal index for some vector, then the vector has n + 1 elements, which is a value that may not be representable as a value of type index_type.
For example, suppose index_type is equivalent to unsigned char, that is, an eight-bit unsigned value. The largest possible vector index value is 255, and the vector itself would have 256 elements, a value not representable in eight bits.
Write a function that accepts as input the root node of a tree and returns as output number of interior nodes in the tree. A tree is defined as it was for the second programming assignment; an interior node is a node with children.
Your function should contain the fewest statements possible.
Remembering that a tree is either a node or a node with a list of other trees underneath, the algorithm for counting interior follows directly:
1. If a tree is just a node, then the node has no children and is not an interior node.
2. If the tree is a node with trees underneath, then the node has children and adds one to the interior-node count, which is the sum of the interior-node counts of the trees underneath the node.
This algorithm leads directly to a simple, recursive function for counting interior nodes:
```
int count_interior_nodes(tree) 
  int count = 0

  if tree.children.size() > 0
    count = 1
    for each c in tree.children
      count += count_interior_nodes(c)

  return count
```
A colleague of yours wrote the following code
```
static void t(int i) {
  throw i + 1;
  }

int main() {
  int i;
  try {
    i = 1;
    }
  catch (int j) {
    cout << "j = " << j << "\n";
    }
  t(i);
  }
```
Unfortunately, the program, when run, never prints the message. Explain to your colleague what's going on.
The throw is taking place inside of the call to t(), but the call to t() is taking place outside the scope of the try-catch statement. Because the throw is taking place outside the scope of the try, the associated catch cannot receive the exception because it doesn't know about it.

This page last modified on 11 October 2001.