Answer key for final exam in CS U370, fall 2004. Except where noted, the most popular answers were correct. 70 students took the test. The low score was 50, the median was 76, and the high was 95. The arithmetic mean was 75.3, and the sample deviation was 10.6. The results reported here exclude one student who, under NU policies that limit the number of final exams taken in one day, took the exam at a different time. For each alternative answer to a multiple choice question, the percentage of students who chose that answer is shown in square brackets to the right of the answer. (These percentages may not add up to 100% because of rounding.) For other questions, the percentage of credit that was earned by students is shown in square brackets following the question. Name_______________________________________ Final Exam. CS U370. Object-oriented design. Fall 2003. Each true/false question is worth 2 points. Each multiple choice question is worth 3 points. The last three questions are worth 10 points each. F 1. All good code is correct code. [91%] F 2. All code that works is correct. [91%] 3. In Java, which of these features best illustrates late binding? ____ A. overloading based on argument number and types [29%] ____ B. dynamic method dispatch [correct: 32%] ____ C. static methods [ 1%] ____ D. final attributes [ 3%] ____ E. compile-time type checking [35%] 4. Which of these features is *not* provided by Java? ____ A. overloading [14%] ____ B. multiple inheritance [71%] ____ C. abstract methods ____ D. local classes [ 9%] ____ E. private instance variables [ 6%] 5. Tail recursion is a natural consequence of ____ A. delegation [72%] ____ B. static initializers [ 7%] ____ C. public methods [ 3%] ____ D. use cases [ 7%] ____ E. the Contractor pattern [10%] 6. With regard to reuse, Alan Perlis observed that ____ A. The aim of a joke is not to degrade the human being, but to remind him that he is already degraded. ____ B. If all you have is a hammer, everything looks like a [ 7%] nail. When your hammer is C++, everything begins to look like a thumb. ____ C. It is easier to recycle programmers into managers [ 7%] than to recycle managers into programmers. ____ D. We prefer code that obviously contains no errors [ 9%] to code that contains no obvious errors. ____ E. It is better to have 100 functions operate on one [77%] data structure than 10 functions on 10 data structures. 7. Which of these bugs is least likely to be detected at compile time? ____ A. storage leak [81%] ____ B. undeclared variable [ 1%] ____ C. missing semicolon [ 3%] ____ D. mismatched parentheses [ 1%] ____ E. type error [13%] 8. In Java, which modifier declares that a variable is immutable? ____ A. final [97%] ____ B. private [ 1%] ____ C. immutable [ 1%] ____ D. protected ____ E. volatile 9. Exhaustive testing of a quicksort routine would take ____ A. several minutes [12%] ____ B. several days [ 3%] ____ C. several years [ 7%] ____ D. several millennia [ 4%] ____ E. much longer than the estimated age of this universe [74%] 10. The instructor believes that any object-oriented programming language worthy of the name must include ____ A. contravariant subtyping [ 9%] ____ B. automatic garbage collection [74%] ____ C. case-sensitive identifiers ____ D. strong typing [17%] ____ E. switch statements 11. Parametric polymorphism ____ A. is the main reason Java is better than C++. ____ B. would make the Java library less useful. [ 9%] ____ C. makes it easier to write reusable code. [84%] ____ D. is a consequence of Java's single inheritance. [ 7%] ____ E. is the main reason Fortran is better than Cobol. 12. An immutable abstract data type ____ A. does not provide mutators. [72%] ____ B. does not provide predicates. [13%] ____ C. does not provide selectors. [ 7%] ____ D. exposes its representations to clients. [ 7%] ____ E. is implemented using big-O notation. 13. According to the instructor, Java provides good support for ____ A. multiple inheritance [19%] ____ B. delegation and proper tail recursion [30%] ____ C. monadic first order logic programming [ 3%] ____ D. higher order function types [ 3%] ____ E. extensible sums of extensible product types [45%] 14. The classes of an OO program often come from ____ A. nouns that occur in use case scenarios. [97%] ____ B. space/time scatter plots of risk/reward ratios. ____ C. predictive parsing of bidirectional macroblocks. [ 3%] ____ D. the MCPC and MPEG-2 compression standards. ____ E. navigational charts and tide tables. 15. One important characteristic of an abstract data type is that ____ A. its specification is distinct from its implementations. [84%] ____ B. its values are always stack-allocated. ____ C. its clients define its representation. [14%] ____ D. its data fields are visible to its clients. ____ E. its methods are devious. [ 1%] 16. Which design process is associated with 3x5 inch cards? ____ A. Class, Responsibility, Collaborator [86%] ____ B. Unified Process [ 7%] ____ C. Downward Spiral [ 1%] ____ D. Excellent Adventure ____ E. Extreme Programming [ 6%] 17. In general, white-box tests ____ A. provide the foundation for a black-box test suite. [ 4%] ____ B. give programs a glossy monochrome finish. ____ C. determine which algorithm is the fastest. [ 1%] ____ D. are used to prove that a program is correct. [14%] ____ E. must be revised when the tested code changes. [80%] 18. A primary purpose of the Visitor pattern is to ____ A. expose the representation of a data structure so it [33%] can be traversed more easily. ____ B. ensure that the postcondition of a while loop implies [ 1%] the loop's test expression. ____ C. hide the code required to traverse some representation [61%] of a data structure. ____ D. retrofit message-passing buzzword technology onto nominally late-binding APIs. ____ E. make it impossible for client code to traverse complex [ 4%] data structures. 19. The Java compiler provides a constructor of no arguments whenever ____ A. a class is declared final. ____ B. a class defines more than one constructor. ____ C. a class does not define any constructors. [90%] ____ D. a class implements the java.util.Iterator interface. [ 1%] ____ E. a class is declared abstract. [ 9%] 20. The definition of a Java constructor ____ A. must conform to RFC 1855, as amended. [ 1%] ____ B. always appears within an interface of the same name. ____ C. must precede all instance variable declarations. [ 6%] ____ D. does not declare a return type. [84%] ____ E. cannot be declared private. [ 9%] 21. One important way to improve the efficiency of Java programs is ____ A. to use switch statements instead of method dispatch. [ 3%] ____ B. to avoid use of the StringBuffer class. ____ C. to avoid computing the same thing over and over. [86%] ____ D. to avoid static final variables. ____ E. to use interfaces instead of abstract classes. [12%] 22. If s1 and s2 are strings of length m and n, respectively, then computing their concatenation s1+s2 takes O(m+n) time. What is the running time for the following method? // Returns a string that consists of k copies of the given string. String kCopies (int k, String s) { int i = 0; String result = ""; // Loop invariant: result is i copies of s. while (i < k) { i = i + 1; result = result + s; } return result; } ____ A. O(k lg n), where n is the length of s [ 6%] ____ B. O(k n), where n is the length of s [65%] ____ C. O(k n^2), where n is the length of s [ 9%] ____ D. O(k^2 n), where n is the length of s [correct: 4%] ____ E. O(n^k), where n is the length of s [16%] The next two questions involve the following Java program. public class A { public static void main (String[] args) { Object o1 = new A(); A o2 = new A(); B o3 = new B(); A o4 = o3; /* ... */ } void m (Object x) { System.out.print ("1 "); } void m (A x) { System.out.print ("2 "); } void m (B x) { System.out.print ("3 "); } private static final class B extends A { void m (Object x) { System.out.print ("4 "); } } } 23. What would this program print if /* ... */ were replaced by o2.m(o3); o2.m(o4); o3.m(o1); o4.m(o2); ____ A. 2 3 2 4 [ 4%] ____ B. 4 2 3 2 ____ C. 3 2 4 2 [96%] ____ D. 3 2 2 4 ____ E. 2 4 3 2 24. What would this program print if /* ... */ were replaced by o4.m(o1); o3.m(o1); o2.m(o3); o2.m(o4); ____ A. 4 4 2 3 [ 3%] ____ B. 3 4 2 4 ____ C. 3 4 4 2 [ 1%] ____ D. 4 2 4 3 [ 1%] ____ E. 4 4 3 2 [94%] 25. [10 points] Suppose A, B, C, D, and E are Java classes [87%] whose subclass relationships are shown by the UML class diagram --- --- | A | | D | --- --- ^ ^ | | ----------- --- | | | E | --- --- --- | B | | C | --- --- Suppose further that Java variables a, b, c, d, and e are defined by A a = new A(); B b = new B(); C c = new C(); D d = new D(); E e = new E(); For each of the following assignment statements, indicate whether the assignment would be legal if it were to appear immediately after the above declarations. If the assignment would not be legal, indicate whether it would result in a compile-time type error or a run-time ClassCastException. a = (A) b; legal a = (A) c; legal a = (A) d; type error b = (B) a; ClassCastException b = (B) c; type error b = (B) e; type error c = (C) a; ClassCastException d = (D) e; legal e = (E) c; type error e = (E) e; legal 26. [10 points] Write Java code for a reversePrint predicate [76%] that, given an IntIterator as defined below (and as in assignment 4), prints the generated int values in reverse order. For example, the first int generated by the iterator is to be printed last, and the last generated string is to be printed first. You may assume that all classes in java.util have been imported. // IntIterator. // // The IntIterator interface is almost the same as the // java.util.Iterator interface. The only differences are that // an IntIterator's next() method returns an int instead of // an Object, and that an IntIterator has no remove method. public interface IntIterator { // Returns true if the iteration has more elements. public boolean hasNext(); // Returns the next int in the iteration. public int next(); } //////////////////////////////////////////////////////////////// // // There are infinitely many incorrect answers to this question, // as well as infinitely many correct answers. // // Below are several possible answers, all untested. (Those who // took the test were not allowed to test their answers using // electronic devices, so not testing them seems fair.) // // Common errors included: // omitting new Integer(...).intValue() junk (up to 2 pts) // incorrect class or method names in java.util.* (1 pt each) // printing the values in the wrong order (5 pts) // running through an IntIterator twice (2 pts) // assuming an IntIterator is cloned by assignment (2 pts) // assuming an array won't overflow (3 pts) // //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// // // Possible answer 1: use recursion // //////////////////////////////////////////////////////////////// // Prints the values generated by the IntIterator in reverse order. void reversePrint (IntIterator it) { if (it.hasNext()) { // Remember the next value. int n = it.next(); // Print the rest of the values in reverse order. reversePrint (it); // Print the remembered value. System.out.println (n); } } //////////////////////////////////////////////////////////////// // // Possible answer 2: use an explicit stack // //////////////////////////////////////////////////////////////// // Prints the values generated by the IntIterator in reverse order. void reversePrint (IntIterator it) { Stack stk = new Stack(); // Loop invariant: // The values generated so far have been pushed onto stk, // in the order they were generated. while (it.hasNext()) { // Push the next value. stk.push (new Integer(it.next())); } // Now print the values in the reverse of the order in // which they were pushed. while (! (stk.empty())) { System.out.println (((Integer) stk.pop()).intValue()); } } //////////////////////////////////////////////////////////////// // // Possible answer 3: use an explicit stack, which you implement // yourself because you didn't appreciate the value of reusable // software enough to bring your notes on the standard libraries // to this open-book open-notes test // // Programmers who write their code from scratch tend to write // horribly inefficient as well as horribly ugly code. Below // is an example. // //////////////////////////////////////////////////////////////// // Prints the values generated by the IntIterator in reverse order. void reversePrint (IntIterator it) { int k = 0; // number of values generated so far int[] values = new int [k]; // array of values generated so far // Loop invariant: // k is the number of values generated so far, // k == values.length, // and values contains the values generated so far, // with values[0] being the first generated value. while (it.hasNext()) { // Copy the values into a bigger array. int[] newValues = new int [k+1]; for (int i = 0; i < k; i = i + 1) newValues[i] = values[i]; // Use the bigger array, store the next value into it, // and increment k to preserve the loop invariant. values = newValues; values[k] = it.next(); k = k + 1; } // Now print the values in the reverse of the order in // which they were generated. for (int i = k - 1; i >= 0; i = i - 1) System.out.println (values[i]); } } 27. [10 points] Write Java code for an AllDistinct class that [58%] implements the IntVisitor interface below. This class shall define a public constructor that takes no arguments. It shall also define a public result method that takes no arguments and returns a boolean value signifying whether any int value has been passed to this visitor's visit method more than once. For example: AllDistinct v = new AllDistinct(); assert (v.result()); // v.result() is true v.visit(3); v.visit(4); v.visit(5); assert (v.result()); // v.result() is true v.visit(3); assert (! (v.result())); // v.result() is false public interface IntVisitor { // Performs some operation that may be parameterized by the given int. public void visit (int n); } //////////////////////////////////////////////////////////////// // // // There are infinitely many incorrect answers to this question, // as well as infinitely many correct answers. // // Below are several possible answers, all untested. // // Common errors included several noted for question 26, plus: // overwriting evidence of a previously detected duplicate (1 pt) // //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// // // Possible answer 1: use the standard class libraries // //////////////////////////////////////////////////////////////// class AllDistinct implements IntVisitor { // visited is a Set of all int values visited so far private Set visited = new TreeSet(); // sawDuplicate is true if and only if a duplicate has been visited private boolean sawDuplicate = false; public AllDistinct () { } // If the visited int is a duplicate, remembers the duplication. // Otherwise remembers the visited int. public void visit (int n) { // The lack of parametric polymorphism is a pain. Object nn = new Integer(n); if (visited.contains(nn)) sawDuplicate = true; else visited.add(nn); } // Returns true if and only if no duplicate has been seen. public boolean result () { return ! sawDuplicate; } } //////////////////////////////////////////////////////////////// // // Possible answer 2: roughly the same as possible answer 1, but // implements immutable int-sets from scratch, badly, instead of // reusing the standard class libraries // //////////////////////////////////////////////////////////////// class AllDistinct implements IntVisitor { // visited is a Set of all int values visited so far private IntSet visited = new IntSet(); // sawDuplicate is true if and only if a duplicate has been visited private boolean sawDuplicate = false; public AllDistinct () { } // If the visited int is a duplicate, remembers the duplication. // Otherwise remembers the visited int. public void visit (int n) { if (visited.contains(n)) sawDuplicate = true; else visited = visited.adjoin(n); } // Returns true if and only if no duplicate has been seen. public boolean result () { return ! sawDuplicate; } // A poor-quality implementation of sets of int values. private static class IntSet { // Constructs an empty IntSet. IntSet () { } // Does this IntSet contain the given int? boolean contains (int n) { return false; } // Returns this IntSet union { n }. IntSet adjoin (int n) { return new NonemptyIntSet (n, this); } private static class NonemptyIntSet extends IntSet { int n; // one element of this IntSet IntSet s; // the other elements of this IntSet // Invariant: n is not an element of s. // Constructs a nonempty IntSet. // Precondition: n is not an element of s. NonemptyIntSet (int n, IntSet s) { this.n = n; this.s = s; } // Does this IntSet contain the given int? boolean contains (int n) { return (this.n == n) || s.contains (n); } // Returns this IntSet union { n }. IntSet adjoin (int n) { if (this.contains (n)) return this; else return new NonemptyIntSet (n, this); } } } }