Please keep all answers brief and to the point. I like answers to the question that I asked, and would prefer not to read everything you know about the general subject area.

1. (6 points) For the following binary tree, in what order would the nodes be visited if you did a:
   
   
   1. preorder traversal
      A B C D E
      
   2. inorder traversal
      A C B E D
   3. postorder traversal
      C E D B A
      
      
2. (4 points) For the BinaryTree ADT, classify each of the following methods as a constructor (C), an accessor (A), an applicative transformer (AT), or a mutative transformer (MT).
   
   
   1. Accessor OR applicative transformer getLeftChild()


   2. Mutative transformer setLeftChild(BinaryTree)


   3. Accessor getValue()


   4. Mutative transformer setValue(Object)
      
      
      
3. (4 points) If you want to make an object Serializable, what are the four conditions you must satisfy?
   
   
   1. The (class of the) object must be public.
      
      
   2. The (class of the) object must implement Serializable.
      
      
   3. The class must have a no-argument constructor.
      
      
   4. Every object it references must be serializable.
      
      
      
4. (5 points) Your instructor believes that a class should keep its data private and not let any other class directly access that data. "Setter" methods should do validity checking. For a small program, written by a single person, explain briefly how this approach helps the programmer.
   When an error occurs, it's easier to determine which class caused the error.
   (It's likely that other good answers will occur.)
   
   
5. (3 points) Briefly, for what kind of error or exception should you use an assert statement, rather than throwing one of the more traditional kinds of Exception?
   Use assert for errors that logically could never occur.
   OR (2 points) use asserts for debugging within a class.
   
6. (3 points) Suppose you have a collection of objects, and you want to choose objects at random from the collection. Is it easier to randomly choose objects from a Set, or from a Vector? Why?
   
   A vector, since you can use a random integer as an index.
   
   
7. (2 points) If a queue is implemented with an array, the implementation may declare the queue full when there is still one space left in the array. Why would it do this?
   
   So that a full queue may be distinguished from an empty queue.
   
   
8. (2 points) What class contains a binarySearch method?    Arrays
   
   
9. (2 points) What two methods are provided by a ListIterator object in addition to those provided by an Iterator object?
   hasPrevious(), previous()
   
   
10. (6 points) Here is a picture of the Collections framework. Fill in the names of the interfaces.

    Collection           Map / \ | / \ | Set List SortedMap | | SortedSet

11. You have written an Employee class, and now you want to create a Hashtable using Employee objects as keys.
    
    
    1. (3 points) You need to write a hashCode() method for Employees. How will this be used?
       Finding an initial index into the hash table
       
       
    2. (3 points) You need to write an equals(Object) method for Employees. How will this be used?
       Testing whether the object in the hash table is the object sought
       
       
    3. (3 points) You know that you will never have two distinct objects in memory representing the same employee. Do you still have to write an equals(Object) method? Why or why not?
       No, because the default equals(Object) method, using ==, works fine for this.
       
       
    4. (3 points) You know that you will never have two distinct objects in memory representing the same employee. Do you still have to write a hashCode(Object) method? Why or why not?
       No, because the default hashCode() method, using the object's address, works fine for this.
       
       
    5. (3 points) If you do write both equals(Object) and hashCode(), what is the one relationship between the two methods that you must be sure to satisfy?
       Equal objects must have the same hash code.
       NOT: Objects with the same hash code must be equal.
       
       
12. (5 points) Here is a list of methods. For each method, tell whether it is in the Collection interface (C), the Map interface (M), both (B), or neither (N). Hint: The commonsense answer is probably the correct one.
    1. B isEmpty()
    2. C iterator()
    3. M get(Object)
    4. C contains(Object)
    5. N hasNext()


13. (2 points) Which of the following defines the "natural order" of objects in a class: Comparable or Comparator?
    Comparable
    
    
14. (3 points) You have a Vector v containing several objects. What is the effect of the following statement?
    
          v = new Vector(new TreeSet(v));
    Sorts the vector and removes duplicate elements.
    
    
    
15. (2 points) One advantage of keeping your data as plain text, rather than in some binary format, is that it is human-readable. Name one other advantage.
    It doesn't get obsolete
    Leverage--most tools can use it
    Easier testing--no special tools needed
    
16. (2 points) When you write out a Serializable object to a file, is it in plain text format? (Yes or no)
    NO
    
    
17. (2 points) What does The Pragmatic Programmer recommend about a text editor?
    Pick one and learn to use all its features
    
    
    
18. (8 points) Briefly define each of the following:
    
    
    1. coupling:
       Two things are coupled if a change in one requires a change in the other
       
       
    2. unit test:
       Testing a module in isolation (by itself)
       
       
    3. DBC
       Design By Contract--specifying the rights and responsibilities of each module
       
       
    4. Refactoring:
       Rewriting, reworking, and re-architecting code
       Reorganizing a program when you find a better way to do things
       
       
       
19. Here's a small portion of a road map. The names represent towns, and the lines represent roads between those towns. The number along each line represents the distance (in miles) along that road between the two towns that it connects. There is never more than one road connecting two towns. This map will be created once, rarely or never modified, and used frequently to determine the best (shortest) route between two towns. You can assume a small number of towns (< 100) and that each town has a uinque name.
    
    
    1. (5 points) What kind of data structure would you use to store this information? (Draw a picture or describe in English--do not write code.) Note that this is a question about implementation.
       
       Many possible answers--
       
       In subsequent classes we have discussed adjacency matrices, edge sets, adjacency sets, etc.
       
       
       
       
       
       
    2. (10 points) Describe an ADT for road maps. That is, list the constructors, methods, and anything else needed to create and use such a road map. Try to use meaningful names, and describe what your methods do only if you think it isn't obvious from the name. (The less I have to read, the better.)
       
       Many possible answers--For example:
       class Town
            Town(String name) // constructor
       
       
       
       
       
       
       
       
    3. (5 points) Tell how long it will take, using Big-O notation, to find the distance between two adjacent towns on your road map, and tell why. (Note that this means looking up a single number in the road map, not using a fancy algorithm.) Don't write code.
       
       
       
       
       
       
    4. (5 points) Will your implementation scale up to handle a large number of towns, say, 50000? It is okay if it doesn't, but tell why you think it will or will not scale up.