CS 509 Test 2

CS 509, Advanced Programming II

Fall 2001 - Test 2

A colleague of yours explains that it is possible to find the median of a list of values without sorting the list. Is your colleague correct? Explain.
Your colleague is correct. The median value in a list of numbers is the value which is at least as large as half the numbers on the list and no larger than the other half. Sorting the list is one way to find the median value, but not the only way.
One way to find the median of a list of n numbers without sorting is to throw away half the smallest numbers, where half is defined as floor(n/2). The smallest of the remaining numbers is the median, assuming n is odd; if n is even, the median is the average of the smallest of the remaining numbers and the largest of the numbers thrown away.
For example, given the list [1,2,3,4,5], the smallest number remaining after the 2 ( = floor(5/2)) smallest numbers are thrown away is 3, which is the median of the list. Given the list [1,2,3,4,5,6], the median 3.5, the average of 3 (the largest number thrown away) and 4 (the smallest number kept).
Explain the difference between a function's declaration and it's definition.
A function's declaration gives its prototype; that is, the function's return value, the function's name, and the number, order, and type if it's parameters. The declaration does not give the function's body.
A function's definition contains all the information contains all the information given in the declaration, but also includes the function's body.
Write a function that accepts as input the root node of a tree and returns as output number of leaves in the tree. A tree is defined as it was for the second programming assignment; leaf is a node with no 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 leaves follows directly:
1. If a tree is a node, then the node is a leaf and the tree has one leaf.
2. If the tree is a node with trees underneath, then the node isn't a leaf and adds nothing to the count, which is the sum of the leaf-counts of the trees underneath the node.
This algorithm leads directly to a simple, recursive function for counting leaves:
```
int count_leaves(tree)
  int count = 0

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

  return count
```
A colleague of yours is under the impression using a catch clause of the form
```
catch (exception e) { 
  // whatever
  }
```
in a try block will catch any exception not otherwise caught. Is your colleague correct? Explain.
Only up to a point. The catch clause catch (exception e) will catch any uncaught value thrown as long as the uncaught value is an ancestor of the exception class. It will not catch any arbitrary uncaught value; for that your colleague needs to use the catch clause catch (...).

This page last modified on 11 October 2001.