AP Computer Science 2nd Semester Programming Test #1
0. (0 points) NAME________________________________________ PERIOD_________
INSTRUCTIONS
1. (5 points) In this problem, you will set up and create a Human class.
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 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 (datum.compareTo(this.datum) < 0) {
if (left == null) {
// documentation says setLeft calls the constructor
setLeft(datum, depth);
} else {
left.insert(datum, depth+1);
}
} else if (datum.compareTo(this.datum) > 0) {
if (right == null) {
setRight(datum, depth);
} 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);
}
}
}