CIT594 Midterm ExamSpring 2009 |
Name_________________________________________ |

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

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

- (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?

- (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>)`

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

- (5 points) Write the
*iterative*version of the`int last()`

method described in the previous question.

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

- (5 points) Suppose you frequently need to do a binary search on a list. Should you
use a
`LinkedList`

or an`ArrayList`

, and why?

- (3 points) In what order are the nodes of this binary tree traversed
- in preorder?
- in inorder?
- in postorder?

- in preorder?
- (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?

- (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`

?

- (5 points) Under what circumstances will an
`Iterator`

method throw a`ConcurrentModificationException`

?

- (6 points) Write all BNF rules necessary to define
`<small integer>`

, where a "small integer" is a number in the range -99 to 99.

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

`a b c d`

`a b c`

`a a b d d`

`a b b c d c c d`

`d`

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

- (4 points) If you want to put
`Vehicle`

objects into a`HashSet`

, the`Vehicle`

class must override both _________________ and _________________.

- (4 points) If you want to put
`Vehicle`

objects into a`TreeSet`

(which is a`SortedSet`

), the`Vehicle`

class must override both _________________ and _________________.

- (5 points) Describe the object created by the declaration
`new String[10][]`

.

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