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?

When an X*is a*kind of Y.

When it makes sense for X objects to have all the operations of 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?

A method to test if the stack is "full."

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

boolean add(E e)

`contains`

boolean contains(Object o)

`containsAll`

boolean containsAll(Collection<?> c)

`iterator`

Iterator<E> iterator()

`equals`

boolean equals(Object o)

- (5 points) Draw a line between each set-theoretic operation and the
`Set`

method that implements it.

`addAll`

(-> union) union `contains`

(-> member) intersection `containsAll`

(-> subset) difference `removeAll`

(-> difference) member `retainAll`

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

private int last() {

if (next == null) return value;

else return next.last();

}

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

method described in the previous question.

private int last() {

MyList here = next;

while (here.next != null) {

here = here.next;

}

return here.value;

}

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

It makes it more difficult to understand the class as a whole.

It makes it harder to recognize the "essential" operations.

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

or an`ArrayList`

, and why?

Use an ArrayList. Finding the n^{th}element of an array is O(1) time, but for a linked list it is O(n) time.

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

A B C D E F - in inorder?

D C E F B A - in postorder?

D F E C B A

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

O(log n) time, because the number of digits in a number is the log_{10}of the number.

- (5 points) What two methods are found in a
`ListIterator`

but not in an`Iterator`

?

hasPrevious() and previous() (or: boolean hasPrevious() and E previous()).

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

?

It's probably implemented as a doubly-linked list.

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

method throw a`ConcurrentModificationException`

?

When the collection is modified during the iteration. (The exception is noticed when the iterator's hasNext() or next() method is called.)

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

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

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<small integer> ::= <digit> | <digit> <digit> | - <digit> | - <digit><digit>

(OR: <small integer> ::= [ - ] <digit> [ <digit> ] )

- (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 hashCode() and equals(Object).

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

objects into a`TreeSet`

(which is a`SortedSet`

), the`Vehicle`

class must override both equals(Object) and compareTo(T) (OR compare(T, T)).

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

.

An array of ten rows, each of which is capable of holding an array of Strings.

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

Do the base cases first

Recur only with a simpler case

Don't modify and use nonlocal variables

Don't look down