You can expect similar questions on the exam. Try to answer all the questions before looking at the solutions linked at the bottom.

Fill in the blank

  1. Abstract Data Types (ADTs) define two things: ____________________ and ____________________.

  2. A class can be built in two ways:
    • ____________________ (using instances of previously defined classes)
    • ____________________ (extending a previously defined class)
  3. If a method in a superclass is redefined (overridden) in one or more subclasses, that is a ____________________ method.

  4. The two Bag implementations that we discussed used ____________________ and ____________________ as their underlying data implementations.

  5. A program that executes operations for a problem of size N has a Big-O runtime of ____________________.

  6. Recursive methods have three things:
    • ____________________ case(s)
    • ____________________ case(s)
    • ____________________ (an important property - so that it won’t run forever)
  7. Getting the ith item in an array is a O(__) operation, while getting the ith item in a linked list is a O(__) operation.

  8. Divide-and-conquer is a problem-solving technique where each subproblem is ____________________ of the size of the larger problem.

Short answer

  1. Given this method signature, what kind of objects can be passed to it?

     <T extends MyInterface> void doSomething(T thing);
    
  2. Describe the binary search algorithm. It doesn’t have to be highly detailed, but it should be detailed enough that you could convert it to code relatively simply.

  3. Can singly-recursive functions do anything that a loop cannot? Justify your answer.

  4. Subtype polymorphism is very commonly used in Java, but there are really two kinds: class inheritance, and interface implementation. What is an advantage of each?

Tracing and Analysis

  1. Show what this code outputs.

     interface Eats {
         String getFood();
     }
    
     class Cat implements Eats {
         String getFood() { return "meat"; }
     }
    
     class Cow implements Eats {
         String getFood() { return "grass"; }
     }
    
     class Dog implements Eats {
         String getFood() { return "who knows"; }
     }
    
     public static void main(String[] args) {
         Eats[] eaters = new Eats[] {
             new Cat(), new Cow(), new Dog()
         };
    
         for(Eats e : eaters) {
             System.out.println(
                 "The " + e.getClass() +
                 " eats " + e.getFood());
         }
     }
    
  2. Figure out the big-O runtime of these methods.

     int one(int[] arr) {
         int sum = 0;
    
         for(int item : arr) {
             sum += item;
         }
    
         return sum / arr.length;
     }
    
     int[] two(int[] arr) {
         int[] ret = new int[arr.length];
    
         for(int i = 0; i < arr.length; i++) {
             int[] copy = Arrays.copyOf(arr, i);
             ret[i] = one(copy);
         }
    
         return ret;
     }
    
     double three(int n) {
         if(n == 0 || n == 1)
             return 1.0;
         else
             return three(n - 1) + (1.0 / n);
     }
    
  3. Draw the linked list as it appears at the two indicated points.

     class Node {
         int value;
         Node next;
         Node(int v) { value = v; }
     }
    
     public static void main(String[] args) {
         Node a = new Node(10);
         Node b = new Node(20);
         Node c = new Node(30);
         c.next = b;
         c.next.next = a;
         // >>>>>>>>>>>>>HERE<<<<<<<<<<<<<<<<
         Node d = new Node(40);
         Node e = new Node(50);
    
         d.next = c.next.next;
         c.next.next = d;
    
         Node n = c;
         while(n.next != null)
             n = n.next;
    
         n.next = e;
         // >>>>>>>>>>>>>HERE<<<<<<<<<<<<<<<<
     }
    

Application

  1. Evaluate this postfix expression using the algorithm we learned. Show each step in the table.

    3 5 + 2 10 4 - * -

    Remaining tokens Operand stack
       
       
       
       
       
       
       
       
       
  2. You are making a system for reserving seats on airplanes. You need to keep track of which seats are taken and which are available. Airplane seats are built into the airplane and there are a limited number of them. Of the following three implementations, which would you choose and why?

    • Linked list
    • Fixed-size array
    • Resizable array

Now check your answers here.


Topics to study

Java Programming

Data Structures

Theory