Solutions to sample final exam questions

Note that the actual final exam will have quite a few more questions than shown below - these are just sample questions, to give you an idea of the types of questions you will be asked.

Short-answer style questions

Question

Insert the following items into an initially empty BST, in the following order: 60, 42, 35, 12, 70. Show what the tree looks like after each insertion (i.e. show five trees). 
60

   60
  /
42

      60
     /
   42
  /
35

         60
        /
      42
     /
   35
  /
12

         60
        /  \
      42    70
     /
   35
  /
12

Question

The Bag<E> class was implemented with an array with elements of type E as its underlying data store, named _store. Assume _store.length is the capacity of the array, and _size is an int instance variable which indicates the first available position of _store. You may assume that 0 <= _size <= _store.length. Because arrays are of a fixed size, a resize(int capacity) method must be defined for the Bag<E> class, whose job it is to allocate a new array with elements of type E, of length capacity, and copy data from the old array into the new array. Define the resize method.
(See code in lecture code repository - we did this in lecture when we defined the Bag.)

Question

In the worst case, and expressed using the O-notation, how long does it take to search a linear list containing N items?
O(N)

Question

In the worst case, and expressed using the O-notation, how long does it take to search a binary search tree (not necessarily balanced) containing N items?
O(N)

Question

In the worst case, and expressed using the O-notation, how long does it take to search a balanced binary search tree containing N items?
O(log N)

Question

There is a typical "identify parts of code" question. Be sure, when you do this question, to circle precisely and clearly the part of the code which corresponds to each vocabulary item: no more, no less. Number clearly too!
(no solution provided - look over old in-class exams)

Question

Give the following method definition: 
public int mystery(int x, int y) {
    int z = 0;
    if (x < y) {
        z = y - x;
    }
    if (x >= y) {
        z = (++x - ++y);
    }
    if (x == y) {
        z = z + 2;
    }
    return z * 3;
}
What is the value of each of the following expressions?

Multiple-choice style questions

Correct answers are bold italic.

Question

"Fred" is a primitive value, while new String("Fred") is an object.

Question

The access policy of a stack is:

Question

Which of the following represents the order in which a pre-order traversal would visit the nodes of the following binary tree? 
        10
       /  \
     20    30
    /  \     \
  40    50    60
       /     /  \
     70    80    90

Question

Consider the following code: 
public class A {
    public void m1() { System.out.println("A.m1()"); }
    public void m2() { System.out.println("A.m2()");}
}
public class B extends A{
    public void m1() { System.out.println("B.m1()"); }
    public void m3() { System.out.println("B.m3()");}
}

Part 1

If A obj = new A(), what is printed when the following method call executes: obj.m1()

Part 2

If A obj = new B(), what is printed when the following method call executes: obj.m1()

Part 3

If A obj = new A(), what is printed when the following method call executes: obj.m2()

Part 4

If A obj = new B(), what is printed when the following method call executes: obj.m2()

Part 5

If A obj = new A(), what is printed when the following method call executes: obj.m3()

Part 6

If A obj = new B(), what is printed when the following method call executes: obj.m3()
Carl G. Alphonce
Last modified: Fri May 4 13:10:47 EDT 2007