37. Consider the following method:

    public int[][] makeCounts(int n) { int[][] counts = new int[3][n]; counts[0][0] = 0; counts[1][0] = 0; counts[2][0] = 1; for (int k = 1; k < n; k++) { counts[0][k] = counts[0][k-1] + counts[1][k-1]; counts[1][k] = counts[1][k-1] + counts[0][k-1] + counts[2][k-1]; counts[2][k] = counts[2][k-1] + counts[1][k-1]; } return counts; }

    What values are in the array returned by makeCounts(5)?

    1. 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1

    2. 0 0 1 2 3 0 1 2 3 4 1 2 3 4 5

    3. 0 0 1 3 6 0 1 2 5 8 1 1 4 7 9

    4. 0 0 1 3 8 0 1 2 5 12 1 1 2 4 9

    5. 0 1 3 9 27 0 1 3 9 27 1 1 3 9 27

38. What is the output from the following code segment?

    List cities = new ArrayList(); cities.add("Atlanta"); cities.add("Boston"); cities.add("Chicago"); for (String city : cities) city = city.substring(1); System.out.println(cities);

    1. [A, B, C]

    2. [C, B, A]

    3. [a, n, o]

    4. [tlanta, oston, hicago]

    5. [Atlanta, Boston, Chicago]

39. Consider the following two recursive versions of the method choose(n, k).

    Version 1

    public static int choose(int n, int k) { if (k == 0) return 1; else return choose(n, k-1) * (n-k+1)/k; }

    Version 2

    public static int choose(int n, int k) { if (k < 0 || k > n) return 0; else if (n == 0) return 1; else return choose(n-1, k-1) + choose(n-1, k); }

    When choose(4, 2) is called, how many times total, including the original call, will choose be called in each version?

    	Version 1		Version 2
    	2		7
    	2		19
    	3		7
    	3		19
    	3		27

40. Given two arrays of double values, sorted in ascending order, one with 100 elements, the other with 10 elements, how many comparisons will it take in an optimal algorithm to merge these arrays into one sorted array, in the best case and in the worst case?

    	Best case		Worst case
    	10		109
    	50		110
    	100		110
    	109		999
    	100		1000