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.

  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) {
            // YOUR_CODE_HERE (see Part a)
    
    
    
    
    
    
    
    
    	}
    }
    
    public abstract class Mammal extends Animal {
    
        public Mammal(double 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) {
        
                 ________________________;
    
                 ________________________;
        }
        
        public String toString() {
        	
           ________________________________________________________________________;
        }
    }

     

    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) {
    
    			________________________________;
    
    			________________________________;
    
    		} else if (datum.compareTo(this.datum) < 0) {
    
    			if (________________________________) {
    
    				setLeft(________________________________);
    			} else {
    				left.insert(________________________________);
    			}
    		} else if (datum.compareTo(this.datum) > 0) {
    
    			if (________________________________) {
    
    				setRight(________________________________);
    			} else {
    				right.insert(________________________________);
    			}
    		}
    	}
    

     

    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 (________________________________) {
    return ________________________________;
    } else if (________________________________) {
    return ________________________________;
    } else {
    return ________________________________;
    }
    }

     

    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.