practice.pdf

CS 2420: Introduction to Algorithms and Data Structures PRACTICE QUESTIONS Do not limit your studying to finding the answers to these practice questions. 1. (3 minutes) Consider the following Java code. public class MyClass { pub...

CS 2420: Introduction to Algorithms and Data Structures PRACTICE QUESTIONS Do not limit your studying to finding the answers to these practice questions. 1. (3 minutes) Consider the following Java code. public class MyClass { public static void doSomething(char c, double[] d) { ? ? ? } public static void main(String[] args) { char letter = 'a'; double[] arr = {1.2, 3.4, 5.6, 7.8}; doSomething(letter, arr); System.out.println(letter); System.out.println(arr); } } Which of the following is definitely true? Fill in one or more choices. ⃝ The value printed in the next-to-last statement of main is 'a'. ⃝ The value printed in the next-to-last statement of main is not 'a'. ⃝ The value printed in the last statement of main is 1.2. ⃝ The value printed in the last statement of main is not 1.2. 2. (3 minutes) Is the following statement true or false? Justify your answer. All Java interfaces are abstract classes, but not all abstract classes are Java interfaces. 3. (3 minutes) What is the running-time behavior of the following loop nest? for(int i = 0; i < N+N; i++) for(int j = N; j > 0; j--) System.out.println("hello world"); Give your answer using proper big-O notation. 1 4. (9 minutes) Given the following class definition fragments, complete the table below. Assume that the methods shown here do not appear in any other classes. (E.g., The Restaurant class does not define a toString method.) public class Building { public Point getLocation()... } public class Restaurant extends Building { public int getSeatCount()... } public class Lab extends Building { public String toString()... } public class Diner extends Restaurant { public boolean equals(Object other)... } For each row, use the second column to indicate what would happen if the code fragment in the first column is executed. Choose (only one) from the following: compiler error run-time exception calls method from Class The first two rows are done for you, as examples. Lab a = new Lab(); a.getLocation(); calls getLocation from Building Building b = new Restaurant(); b.getSeatCount(); compiler error Object c = new Building(); c.getSeatCount(); Object d = new Building(); ((Building)d).getLocation(); Object e = new Restaurant(); ((Lab)e).toString(); Restaurant f = new Diner(); Object g = new Object(); g.equals(f); Restaurant h = new Building(); h.toString(); Building i = new Diner(); i.toString(); Diner j = new Diner(); Building k = j; k.equals(j); Restaurant l = new Diner(); l.getSeatCount(); 2 5. (6 minutes) Carefully explain to a new Java programmer why all sorting methods that have a basic array as a parameter also have a void return type. (Use complete sentences and make sig- nificant, relevant points — avoid trivial, terse answers.) 6. (3 minutes) Consider the check analysis technique, which computes T (N )/F (N ) as N increases. N T (N ) T (N )/ log N T (N )/N T (N )/N log N T (N )/N 2 2000 3397 ∗ 102 3098 ∗ 101 1698 ∗ 10−1 1549 ∗ 10−2 8492 ∗ 10−5 4000 6739 ∗ 102 5632 ∗ 101 1685 ∗ 10−1 1408 ∗ 10−2 4212 ∗ 10−5 8000 1354 ∗ 103 1044 ∗ 102 1692 ∗ 10−1 1305 ∗ 10−2 2115 ∗ 10−5 16000 2696 ∗ 103 1931 ∗ 102 1685 ∗ 10−1 1207 ∗ 10−2 1053 ∗ 10−5 32000 5398 ∗ 103 3607 ∗ 102 1687 ∗ 10−1 1127 ∗ 10−2 5272 ∗ 10−6 64000 1077 ∗ 104 6748 ∗ 102 1683 ∗ 10−1 1054 ∗ 10−2 1415 ∗ 10−6 Which growth rate is the best match? Give your answer using proper big-O notation. 3 7. (14 minutes) Provide a generic method for finding and returning the smallest item in an ar- ray. Recall that when a generic type T extends Comparable