AP Computer Science 2nd Semester Programming Test #1

0. (0 points) NAME________________________________________ PERIOD_________

INSTRUCTIONS

• Put your name on the test. Failure to do so will result in a loss of one point. (Let's face it, if you don't know your name, you probably have bigger problems than this test.)
• This test is closed book. No friends, no computer, just you, your brain, your test, and your pencil.
• Where possible, SHOW YOUR WORK! I don’t know how to assign partial credit to the void.
• Don't panic. It's just a test.

1. (5 points) In this problem, you will set up and create a Human class.

1. Animals compare each other by weight. Write the compareTo method in the Animal class that returns appropriate values based on whether an Animal weighs more, less, or the same amount as another Animal.
2. Complete the Mammal constructor to store the input weight. NOTE: You may NOT add a field to the Mammal class. That completely defeats the point of having the weight field in the Animal class.
3. Complete the Human class so that the following are all true:
1. A Human needs a constructor that properly assigns weight and name.
2. When a Human is printed, its name and weight are part of the output.

Write the code to complete the Animal class. Then fill in the blanks to complete the Mammal and Human classes.

```public abstract class Animal implements Comparable<Animal> {
private double weight;

public Animal() { this(100); }
public Animal(double weight) { this.weight = weight; }
public double getWeight() { return weight; }
public void eat(double food) { weight += food; }
public String toString() { return "I weigh " + weight + " pounds."; }

public int compareTo(Animal a) {
if (weight - a.weight > 0) { // (or weight - a.getWeight())
return 1;
} else if (weight - a.weight < 0) {
return -1;
} else {   // must be same weight
return 0;
}
}
}

public abstract class Mammal extends Animal {

public Mammal(double weight) { super(weight); }
}

public class Human extends Mammal {
// DO NOT PUT A weight STATE VARIABLE HERE: IT DEFEATS THE WHOLE POINT OF INHERITANCE AND DELEGATION
private String name;

public Human() { this("Anonymous", 100); }
public Human(String name) { this(name, 100); }
public Human(String name, double weight) {

// The order of these two lines matters.  A constructor in the superclass must be
// performed before any additional code in the subclass.

super(weight);

this.name = name;
}

public String toString() {
// Notice that getWeight() is needed because a Human cannot see the private
// weight variable of the Animal class.  Only members of the exact same class can do that.

return "My name is " + name + " and I weigh " + getWeight();
}
}```

2. (15 points; three 5 point problems)

Suppose we want to find the depth of a node in a binary search tree. The search process can be sped up if we store a node's depth along with its datum. Here is an abstraction for this (assume all contents indicated have been written and work correctly):
```public class BST<T extends Comparable<T>> {
BST();                                         // constructor; produces an empty tree w/datum == null
BST(T datum);                                  // constructor
BST(T datum, int depth)                        // constructor
private T datum;                               // datum of a node in a BST
private int depth;                             // depth of the node (root is depth 1)
private BST<T> left;                           // left subtree
private BST<T> right;                          // right subtree
public T getDatum();                           // returns datum
public void setDatum(T datum)                  // changes a datum
public BST<T> getLeft();                       // returns left subtree
public void setLeft(T datum, int depth);       // sets left subtree to a new node w/datum & depth
public BST<T> getRight();                      // returns right subtree
public void setRight(T datum, int depth);      // sets right subtree to a new node w/datum & depth
}```

2A. (5 points) In the BST class, write the method insert which takes an Integer as its input and inserts it in the tree AND stores the depth of the node when inserted.

Example. Given the BST<Integer>, t, with the datum on the left and depth on the right for each node:

```                  t --> 10,1
/  \
/    \
5,2      12,2
/ \       \
/   \       \
1,3   8,3    15,3
/       /
/       /
6,4     13,4```

t.insert(7) would insert a node to the right of the node containing the 6 with 7 as the datum and 5 as the depth.

t.insert(11) would insert a node to the left of the node containing the 12 with 11 as the datum and 3 as the depth.

Assume that the following has been written:

```public void insert(T datum) {
insert(datum, 1);
}```

Fill in the blanks to write insert with two inputs.

```	public void insert(T datum, int depth) {
if (getDatum() == null) {

// Note that setDatum must have this.datum = datum in it
setDatum(datum);

depth = 1;

} else if (datum.compareTo(this.datum) < 0) {

if (left == null) {
// documentation says setLeft calls the constructor
setLeft(datum, depth+1);
} else {
left.insert(datum, depth+1);
}
} else if (datum.compareTo(this.datum) > 0) {

if (right == null) {

setRight(datum, depth+1);
} else {
right.insert(datum, depth+1);
}
}
}
```

2B. (5 points) Write the static (i..e, not in the BST class) method sum(BST<Integer> integerTree, T targetDatum) which returns the sum of the data of all the nodes in the tree down to targetDatum.

```                  t --> 10,1
/  \
/    \
5,2      12,2
/ \       \
/   \       \
1,3   8,3    15,3
/       /
/       /
6,4     13,4```

sum(t,8) would return 10+5+8 = 23 as the nodes containing 10 and 5 would be traversed on the way to reaching the 8.

Write sum by filling in the blanks. You are GUARANTEED that the targetDatum will be in integerTree.

```
public static int sum(BST<Integer> bst, Integer n) {
Integer datum = bst.getDatum();				if (n.equals(datum)) {
return n;
} else if (element.compareTo(datum) < 0) {
return datum + sum(bst.getLeft(), n);
} else {
return datum + sum(bst.getRight(), n);		}	}```

2C. (5 points) In the BST class, write the method depth(T element) which searches for element in the binary search tree. If element is in the tree, the depth of the node containing it is returned.

Your depth method should take advantage of the fact that depths are stored in nodes when inserted, rather than recomputing depths while searching. Failing to do this misses The Idea and will result in a maximum of 2 points out of 5.

```    public int depth(T element) {
if (element.equals(datum)) {
return depth;
} else if (element.compareTo(datum) < 0) {
if (left == null) {
return -1;    // Added to problem during test; need a way to report when the element not in tree
} else {
return left.depth(element);
}
} else {
if (right == null) {
return -1;
} else {
return right.depth(element);
}
}
}```