CIT594 Midterm Exam
Spring 2009
Name_________________________________________

Please keep all your answers short and to the point. Do not provide extra information that was not asked for.

  1. (5 points) When is it appropriate for a class X to extend a class Y?






  2. (5 points) An array implementation of a Stack class typically has one more method than it would if it were implemented as a linked list. What is that operation?




  3. (5 points) Which of the following are methods of the Collection interface? (Cross out the ones that are not.)



  4. (5 points) Write the complete signature, including the return type and generics, for each of the following methods in the Collection interface:

  5. (5 points) Draw a line between each set-theoretic operation and the Set method that implements it.
    addAll
       union
    contains
      intersection
    containsAll
      difference
    removeAll
      member
    retainAll
      subset

  6. (5 points) Suppose you have a singly-linked list declared as
       class MyList { int value; MyList next; ...}
    with a constructor
       MyList(int value, MyList next). Write a recursive method int last() to put in this class; the method should return the last value in the list. You may assume the list is not empty.













  7. (5 points) Write the iterative version of the int last() method described in the previous question.















  8. (5 points) In an ADT, why is it a bad idea to have too many "convenience" methods?





  9. (5 points) Suppose you frequently need to do a binary search on a list. Should you use a LinkedList or an ArrayList, and why?






  10. (3 points) In what order are the nodes of this binary tree traversed

    1. in preorder?


    2. in inorder?


    3. in postorder?

    binary tree
  11. (5 points) The following code counts the number of digits in a positive integer variable number:
        int n = number;
        int count = 0;
        while (n > 0) {
            n = n / 10;
            count++;
        }
    How long (in Big-O terms) does this method take? Why?





  12. (5 points) What two methods are found in a ListIterator but not in an Iterator?




    What does this tell you about Sun's implementation of LinkedList?




  13. (5 points) Under what circumstances will an Iterator method throw a ConcurrentModificationException?






  14. (6 points) Write all BNF rules necessary to define <small integer>, where a "small integer" is a number in the range -99 to 99.









  15. (5 points) Suppose <foo> ::= { [ a ] b } { c [ d ] }, where the brackets and braces are BNF metasymbols. Circle each of the following strings that are <foo>s, and cross out the ones that are not.

    1. a b c d

    2. a b c

    3. a a b d d

    4. a b b c d c c d

    5. d

  16. (5 points) Draw a state machine to accept a string of 'A's and 'B's if it contains an even number of 'A's.











  17. (4 points) If you want to put Vehicle objects into a HashSet, the Vehicle class must override both _________________ and _________________. 

  18. (4 points) If you want to put Vehicle objects into a TreeSet (which is a SortedSet), the Vehicle class must override both _________________ and _________________. 

  19. (5 points) Describe the object created by the declaration new String[10][].





  20. (8 points) What are Dave's four rules for doing recursion?