Assignment: #FinalAssessment Due: 12/12/02018 Points: 15
  1. Given ArrayList a = new ArrayList(); The memory for the object variable a gets allocated from the _____ and the memory for the ArrayList object gets allocated from the _____.


  2. class Foo does not compile.

       public class Foo {
          public static void main(String[] argv) {
             Foo f = new Foo();
          }
          public Foo() throws Exception { }
    
          //
          // note:  Exception e = new Exception();
          //        The expression:  e instanceof RuntimeException
          //        evaluates to false.
          //
       }
    
    Explain the two ways class Foo can be modified to get it to compile.


  3. Array B and array C are unsorted arrays each having n elements. The Big-O notation for a failed search of both arrays is what?

       a. O(log n)   b. O(n log n)   c. O(n)   d.  O(n^2)
    


  4. Record the Big-O notation for a failed search of a balanced binary search tree.


  5. Record the Big-O notation for a failed search of a degenerate binary search tree.


  6. The worst case run-time for algorithm A is defined by the function: f(n) = 2.5n^2 + 4n + 3.14. Record the Big-O notation for algorithm A.


  7. Rewrite the following code snippet without using the logical NOT operator.

       if (!isEmpty()) {   // isEmpty() returns a boolean value
          A;              
       } else {
          B;          
       }
    


  8. Rewrite the following code snippet without using the logical NOT operator.

       !(yn == 'n' || yn == 'N')
    


  9. Rewrite the following code snippet without using the logical NOT operator.

       !(!false && !true)
    


  10. Write the method comment block for method goo.

       int goo(Scanner stdin) {
          int ntries = 2, sum = 0;
          do { 
             System.out.print("enter an integer: ");
             try {
                sum += Integer.parseInt(stdin.next());
             } catch (NumberFormatException e) {
                ntries--;
             }
          } while (ntries != 0);
          return sum;
       }
    


  11. This is a #FinalAssessment, so let's look one final time at Java's final keyword.

       [a]  What does it mean when a class is declared final?
       [b]  What does it mean when a method is declared final?
       [c]  What does it mean when a variable is declared final?
    


  12. Briefly explain the difference between overriding a method versus overloading a method.


  13. Explain why class Int prints:

          205 == 205
          x != y
          !x.equals(y)
          Int@5fe5c6f...Int@6979e8cb
    
       public class Int {
          public int i;
          public Int(int i) { this.i = i; }
          public static void main(String[] argv) {
             Int x = new Int(205);
             Int y = new Int(205);
             if (x.i == y.i) System.out.println(x.i + " == " + y.i);
             if (x == y) System.out.println("x == y");
             else System.out.println("x != y");
             if (x.equals(y)) System.out.println("x.equals(y)");
             else System.out.println("!x.equals(y)");
             System.out.println(x + "..." + y);
          }
       }
    


  14. The following code snippet prints 3.14. Document how the code computes Pi rounded to the nearest hundredth.

       Stack stack = new Stack();  
       stack.push(100).push(3).push(11).push(3).push(100);
       Queue queue = new Queue();  
       queue.enqueue('f').enqueue('o').enqueue('o').enqueue('!');
       double answer = 0.0;
       int y = stack.pop();
       do {
          char m = queue.dequeue();
          int n = stack.pop();
          if (m == 'f') y = y * n;
          else if (m == 'o') y = y + n;
          else if (m == '!') answer = (double)y / n;
       } while ((int)answer == 0);
       System.out.println(answer);
    


  15. Write the file comment block for class Lognames and the method comment block for method logname.

       public class Lognames {
          public static void main(String[] argv) {
             char d[] = { 'd','e','n','n','i','s','m','r','i','t','c','h','i','e' };
             char j[] = { 'j','a','m','e','s',' ','a','g','o','s','l','i','n','g' };
             int  i[] = { 7, 6, 0 };
             System.out.println(logname(d, i));  // c created circa 1972
             System.out.println(logname(j, i));  // java created circa 1995
          }
          static char[] logname(char a[], int[] b) {
             char[] c = new char[b.length];
             c[0] = a[b[2]]; 
             c[1] = a[b[1]]; 
             c[2] = a[b[0]];
             return c;
          }
       }
    


  16. Rewrite the for statement so that is uses polymorphism.

       abstract class Foo { abstract int f(int x); }
       class Goo extends Foo { int f(int a) { return a - 95; } }
       class Moo extends Foo { int f(int b) { return b; } }
       class Boo extends Foo { int f(int c) { return c + 35; } }
    
       public class Polymorphism {
          public static void main(String[] a) {
             Foo[] y = { new Goo(), new Moo(), new Boo() };
             for (int i = 0, j = y.length; i < j; i++) {
                if (!(y[i] instanceof Foo)) continue;
                if (y[i] instanceof Goo) {
                   Goo x = (Goo) y[i];
                   System.out.println(x.f(205));
                } else if (y[i] instanceof Moo) {
                   Moo x = (Moo) y[i];
                   System.out.println(x.f(205));
                } else if (y[i] instanceof Boo) {
                   Boo x = (Boo) y[i];
                   System.out.println(x.f(205));
                }
             }
          }
       }
    


  17. Is class QueueOrStack an implementation of a stack or queue?

       public class QueueOrStack {
          private Vector<Object> v = new Vector<Object>();
          public void push_or_enqueue(Object o)  { 
             v.add(o);   // object o appended to the end of v
          }
          public Object pop_or_dequeue() { 
             if (v.size() == 0) return null;
             return v.remove(0);  
                // via class Vector API at Oracle.com:
                // Removes the element at the specified position 
                // in this Vector. Shifts any subsequent elements
                // to the left (subtracts one from their indices).
                // Returns the element that was removed from the Vector.
          }
          public static void main(String[] argv) {
             int[] y = { 1, 5, 3, 2, 9 };
             QueueOrStack q_or_s = new QueueOrStack();
             for (int i = 0; i < y.length; i++)
                q_or_s.push_or_enqueue(y[i]);
             for (int i = 0; i < y.length; i++) 
                System.out.println(q_or_s.pop_or_dequeue());
          }
       }
    


  18. Write the file comment block for class StroustrupCPP.

       public class StroustrupCPP {  // bs created C++ circa 01985
          public static void main(String[] argv) {
             System.out.println(stroustrupCPP()); 
          }
          static int stroustrupCPP() { return stroustrupCPP(2, 2 * 2); }
          static int stroustrupCPP(int a, int b) {
             if (0 == b) return 1;
             return a * stroustrupCPP(a, b - 1);
          }
       }
    


  19. Briefly explain the motivation for a class to implement interface Serializable.


  20. Briefly explain the motivation for a class to implement interface Cloneable.


  21. Briefly explain the motivation for having an instance method return this.


  22. No or Yes: The statement Object[] o = new Object[205]; results in the instantiation of 205 objects of type Object.


  23. A linked-list has a "head" pointer to the first node in the list. Briefly explain the motivation for using a "tail" pointer.


  24. Match application with either stack or queue.

       method calls
       line printer spooler
       buffered I/O
       RPN calculator
    

  25. If a class contains an abstract method, then it must be declared abstract. Briefly explain the motivation for declaring classes and methods to be abstract.


  26. int[] a = { 5, 2, 9, 4, 7, 8, 3, 6 }; is sorted using selection sort. Print a after the third pass through the array.


  27. Given the following tree:

       node: 50;  left: 10    right: 75
       node: 10;  left: 7     right: 15
       node:  7;  left: null  right: null
       node: 15;  left: 12    right: null
       node: 12;  left: null  right: null
       node: 75;  left: 60    right: null
       node: 60;  left: 55    right: 64
       node: 55;  left: null  right: null
       node: 64;  left: null  right: null
    
    [a] Record all of the leaf nodes.
    [b] Record the parent of node 60.
    [c] Record the sibling of node 64.
    [d] Record the grandparent of node 15.
    [e] No or Yes:  Node 75 has two children.
    [f] Record all of the descendants of node 10.
    


  28. Record the post-order traversal (left right root) for the following BST.

                               87
                             /    \
                            /      \
                          84        103
                         /  \       / \
                       68    86    90  109
                      /  \        /  \
                    32   74      88   97
                        /  \
                      70   80
    


  29. Draw the BST for the following inputs. No duplicates are allowed.

    
                   J A M E S G O S L I N G
    
    Note: numerically (Unicode): A < B < C < ...


  30. The following is not a BST, but it is a binary tree and it can be traversed. Record the in-order traversal (left root right) for the following binary tree.

    
                 or
                  |
           +------+--------+
           |               |
        program        programmed
                          |
                    +-----+
                    |
                    be