EECS2030Z Exam

What is the difference between a static field and a non-static field?

Consider the two classes Shape and Circle from Question 1.

Suppose that you have two Circle references x and y where x.equals(y) is true. Why is it important that x.hashCode() == y.hashCode() is also true?

When implementing a class, why do we sometimes need to use composition instead of aggregation?

Consider the two classes Shape and Circle from Question 1.

Is Shape substitutable for Circle, or is Circle substitutable for Shape, or are both statements true?

In our discussion of the model-view-controller pattern, what interface does the controller implement?

What is the inorder traversal of the tree shown above?

Adding an element to the end of an array-based list usually requires O(1) time, but sometimes requires O(n) time. Under what condition is O(n) required?

Consider a linked list data structure.

Complete the implementation of the method below. You can provide either an iterative or recursive solution. Note: The method does not have access to fields that belong to the linked list; the only information your method can use is the node n.

/**
 * Returns the char stored in the last node of the sublist with
 * head node n.
 *
 * @param n the head node of a sublist
 * @return the char stored in the last node of the sublist
 */
public static char last(Node n) {
    // n.data is the char stored in the node
    // n.next is a reference to the next node in the sequence
    
    
}

Consider the following recursive method:

    /**
     * Searches for a value in a sorted list. Returns true if
     * val is contained in the list t, and false otherwise.
     * 
     * @pre. t.size() is zero or more 
     * @pre. t is in sorted order 
     * @pre. t has no duplicate elements
     * 
     * @param val
     *            a value to search for
     * @param t
     *            a list
     * @return true if val is contained in t, and false otherwise
     */
    public static boolean bsearch(Integer val, List<Integer> t) {
        if (t.size() == 0) {                                       // a
            return false;                                          // b
        }
        int i = t.size() / 2;                                      // c
        Integer mid = t.get(i);                                    // d
        if (val.equals(mid)) {                                     // e
            return true;                                           // f
        } else if (val.compareTo(mid) < 0) {                       // g
            return bsearch(val, t.subList(0, i));                  // h
        } else {                                                   // i
            return bsearch(val, t.subList(i + 1, t.size()));       // j
        }
    }

Prove that the method bsearch is correct using the approach from the lectures (i.e., prove that the base cases are correct and that the recursive case of the method is correct).

Prove that the method bsearch (from part 4A) terminates using the approach from the lectures.

Count the number of elementary operations for each line (labelled a-j) of the method bsearch (from part 4A).

Using your answer from part 4C, state the recurrence relation for the method bsearch. Make sure to include the relations for the base case and the recursive case.