CIT594 Midterm Exam Spring 2009 Name_________________________________________

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

• `boolean add(E o)`

• `boolean addAll(Collection<? extends E> c)`

• `void add(int index, E element)`

• `Iterator<E> iterator()`

• `Set<E> toSet(Collection<E>)`

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

• `add`

• `contains`

• `containsAll`

• `iterator`

• `equals`

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
 in preorder? in inorder? in postorder? 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[]```.

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