CIT 594 Second Midterm
Spring 2003, Dave Matuszek
Name _______________________________________

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

    2. inorder traversal

    3. postorder traversal

  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. ________ getLeftChild()

    2. ________ setLeftChild(BinaryTree)

    3. ________ getValue()

    4. ________ setValue(Object)

  3. (4 points) If you want to make an object Serializable, what are the four conditions you must satisfy?

  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.

  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?

  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?

  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?

  8. (2 points) What class contains a binarySearch method?

  9. (2 points) What two methods are provided by a ListIterator object in addition to those provided by an Iterator object?

  10. (6 points) Here is a picture of the Collections framework. Fill in the names of the interfaces.
  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. What will this be used for?

    2. (3 points) You need to write an equals(Object) method for Employees. What will this be used for?

    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?

    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?

    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?

  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. _____ isEmpty()
    2. _____ iterator()
    3. _____ get(Object)
    4. _____ contains(Object)
    5. _____ hasNext()

  13. (2 points) Which of the following defines the "natural order" of objects in a class: Comparable or Comparator?

  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));

  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.

  16. (2 points) When you write out a Serializable object to a file, is it in plain text format? (Yes or no)

  17. (2 points) What does The Pragmatic Programmer recommend about a text editor?

  18. (8 points) Briefly define each of the following:

    1. coupling:

    2. unit test:

    3. DBC

    4. Refactoring:

  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.

    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.)

    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.