Sample Midterm # 1

This sample midterm contains the kinds of questions that will be on the actual midterm. It is much longer than the midterm will be. At least one question on the midterm will be all but identical to one here.

We will not post solutions to the sample midterm problems because, in our experience, people will be tempted to look at the solution before completely doing the problem. If anyone wishes to check their answers, they may give us a paper copy for review.

We will also answer questions by email, generally by giving hints or asking leading questions back.

Definitions and Motivation

What does the acronym ``ADT'' stands for? What is an ADT? What is the connection, if any, between an ADT and a data structure? Use an example to illustrate the answer to your last question.
Why do we distinguish data structure from operational behavior? How are they each represented in Java programs? Give two reasons why we separate the operational behavior from data structure when defining abstract data types.
What does it mean to throw an exception? How does one express throwing an exception in Java? Give two different ways program handle errors other than throw exceptions. Give one reason to use exceptions instead of these other ways.
How are exceptions useful for implementing libraries or generic ADT's used by different applications?
In Homework # 2, we changed the size of the array we were using. Since arrays are fixed size, how did we accomplish this feat?
Compare and contrast internal versus external iterators. What are the advantages of each? Give examples.
What requirement must be established if you are going to dereference a variable? Explain how one can recognize a deference operation in the code, and then explain what the requirement for a safe dereference is and why.
Distinguish exogenous from endogenous linked lists.

Code

Write a version of a new public member function Bag::contains, assuming Bag has the following fields:
```
private int _count;
private Coin contents[CAPACITY];
```
Fill the code in the following skeleton:
/** Return when a matching coin is found in the Bag * Return false otherwise. * @param item coin to match against (must not be null) * @throw NullPointerException if item is null */ public boolean contains(Coin item) { // Your code here!}

Do the same code assuming the following data structure:

private class Node {
  public Coin data;
  public Node next;
  public Node(Coin c, Node n) { data = c; next = n; }
}
private Node head;
public Bag() { head = null; }

Implement the following function (using the array data structure)
/** Remove and discard all coins matching the argument. * @param item coin to match against (must not be null) * @throw NullPointerException if item is null * @return number of coins discarded */ public int removeAll(Coin item) { // Your code here!}
Do the previous problem, but with the linked list data structure.

Debugging

In an array-based Seq implementation, a friend wrote the following code for insert:
```
116 public void insert(Disk element)
117 {
118   ensureCapacity(2*contents.length+1);
119  
120   ++manyItems;
121
122   if (currentIndex == manyItems) {
123      contents[currentIndex] = element;
124   } else if (currentIndex == 0) {
125     for (int i=manyItems; i > 0; --i) {
126        contents[i] = contents[i-1];
127     }
128   } else {
129     for (int i=currentIndex; i < manyItems; ++i) {
130        contents[i+1] = contents[i];
131     }
132   }
133   
134   contents[currentIndex] = element;
135   
136 }
```
1. As soon as you see the code, without even looking at the actual details of the logic, you can see that it is likely to have bugs. Why? Explain!
2. When you run the code with the driver, the result is:
```
java.lang.ArrayIndexOutOfBoundsException: 1
	at edu.uwm.cs351.DiskSeq.insert(DiskSeq.java:126)
	at Driver.testDiskSeq(Driver.java:182)
	at Driver.main(Driver.java:27)
Initial tests
Passed 112 tests.
Failed 1 test.
```
  Your friend says ``Great! I failed only 1 out of 113 tests!'' You gently tell them ...[what?]
3. Why would ``1'' be a bad array index in the given code? Surely the array has at least one element?
4. You fix a problem on line 125, and now the driver passes all tests. But there are still two errors. The first was not found by the driver because it never tested inserting an element before the second element of a sequence with at least three elements. (This is fixed now!) What is the bug?
5. Why does the driver not detect the problem even though it inserts at all locations in a two element sequence (at the start, in the middle and at the end?)
6. There is another problem which happens when one inserts 28 elements in the sequence. It gets slower and slower and then there is an OutOfMemoryError. What is this error? Why did the driver not catch it?

About this document

John Tang Boyland 2010-10-01