Unit 10 APCSA

Consider the following method.

public int addFun(int n)

{

if (n <= 0)

return 0;

if (n == 1)

return 2;

return addFun(n - 1) + addFun(n - 2);

}

What value is returned as a result of the call addFun(6) ?

• 12

• 10

• 16

• 26

• 32

Consider the following method, which implements a recursive binary search.

/** Returns an index in arr where the value x appears if x appears

* in arr between arr[left] and arr[right], inclusive;

* otherwise returns -1.

* Precondition: arr is sorted in ascending order.

* left >= 0, right < arr.length, arr.length > 0

*/

public static int bSearch(int[] arr, int left, int right, int x)

{

if (right >= left)

{

int mid = (left + right) / 2;

if (arr[mid] == x)

{

return mid;

}

else if (arr[mid] > x)

{

return bSearch(arr, left, mid - 1, x);

}

else

{

return bSearch(arr, mid + 1, right, x);

}

}

return -1;

}

The following code segment appears in a method in the same class as bSearch.

int[] nums = {0, 4, 4, 5, 6, 7};

int result = bSearch(nums, 0, nums.length - 1, 4);

What is the value of result after the code segment has been executed?

• 1

• 2

• 3

• 4

• 5

Consider the following method, which implements a recursive binary search.

/** Returns an index in myList where target appears,

* if target appears in myList between the elements at indices

* low and high, inclusive; otherwise returns -1.

* Precondition: myList is sorted in ascending order.

* low >= 0, high < myList.size(), myList.size() > 0

*/

public static int binarySearch(ArrayList<Integer> myList,

int low, int high, int target)

{

int mid = (high + low) / 2;

if (target < myList.get(mid))

{

return binarySearch(myList, low, mid - 1, target);

}

else if (target > myList.get(mid))

{

return binarySearch(myList, mid + 1, high, target);

}

else if (myList.get(mid).equals(target))

{

return mid;

}

return -1;

}

Assume that inputList is an ArrayList of Integer objects that contains the following values.

[0, 10, 30, 40, 50, 70, 70, 70, 70]

What value will be returned by the call binarySearch(inputList, 0, 8, 70) ?

• -1

• 5

• 6

• 7

• 8

Consider the following method.

public static int calcMethod(int num)

{

if (num == 0)

{

return 10;

}

return num + calcMethod(num / 2);

}

What value is returned by the method call calcMethod(16) ?

• 10

• 26

• 31

• 38

• 41

Consider the following two static methods, where f2 is intended to be the iterative version of f1.

public static int f1(int n)

{

if (n < 0)

{

return 0;

}

else

{

return (f1(n - 1) + n * 10);

}

}

public static int f2(int n)

{

int answer = 0;

while (n > 0)

{

answer = answer + n * 10;

n--;

}

return answer;

}

The method f2 will always produce the same results as f1 under which of the following conditions?

I. n < 0

II. n = 0

III. n > 0

• I only

• II only

• III only

• II and III only

• I, II, and III

Consider the following method.

public String goAgain(String str, int index)

{

if (index >= str.length())

return str;

return str + goAgain(str.substring(index), index + 1);

}

What is printed as a result of executing the following statement?

System.out.println(goAgain("today", 1));

• today

• todayto

• todayoday

• todayodayay

• todayodaydayayy

Directions: Select the choice that best fits each statement. The following question(s) refer to the following information

Consider the following binarySearch method. The method correctly performs a binary search.

Consider the following code segment.

int [ ] values = {1, 2, 3, 4, 5, 8, 8, 8};int target = 8;

What value is returned by the call binarySearch (values, target) ?

• -1

• 3

• 5

• 6

• 8

Directions: Select the choice that best fits each statement. The following question(s) refer to the following information

Consider the following binarySearch method. The method correctly performs a binary search.

Suppose the binarySearch method is called with an array containing 2,000 elements sorted in increasing order. What is the maximum number of times that the statement indicated by / Calculate midpoint / could execute?

• 2,000

• 1,000

• 20

• 11

• 1

Consider the following mergeSortHelper method, which is part of an algorithm to recursively sort an array of integers.

/** Precondition: (arr.length == 0 or 0 <= from <= to <= arr.length)

* arr.length == temp.length

*/

public static void mergeSortHelper(int[] arr,

int from, int to, int[] temp)

{

if (from < to)

{

int middle = (from + to) / 2;

mergeSortHelper(arr, from, middle, temp);

mergeSortHelper(arr, middle + 1, to, temp);

merge(arr, from, middle, to, temp);

}

}

The merge method is used to merge two halves of an array (arr[from] through arr[middle], inclusive, and arr[middle + 1] through arr[to], inclusive) when each half has already been sorted into ascending order. For example, consider the array arr1, which contains the values {1, 3, 5, 7, 2, 4, 6, 8}. The lower half of arr1 is sorted in ascending order (elements arr1[0] through arr1[3], or {1, 3, 5, 7}), as is the upper half of arr1 (elements arr1[4] through arr1[7], or {2, 4, 6, 8}). The array will contain the values {1, 2, 3, 4, 5, 6, 7, 8} after the method call merge(arr1, 0, 3, 7, temp). The array temp is a temporary array declared in the calling program.

Consider the following code segment, which appears in a method in the same class as mergeSortHelper and merge.

int[] vals = {80, 50, 30, 20, 60, 70};

int[] temp = new int[vals.length];

mergeSortHelper(vals, 0, vals.length - 1, temp);

Which of the following represents the arrays merged the last time the merge method is executed as a result of the code segment above?

• {20, 30, 50} and {60, 70, 80} are merged to form {20, 30, 50, 60, 70, 80}.

• {20, 50, 70} and {30, 60, 80} are merged to form {20, 30, 50, 60, 70, 80}.

• {20, 50, 70} and {30, 60, 80} are merged to form {20, 50, 70, 30, 60, 80}.

• {30, 50, 80} and {20, 60, 70} are merged to form {20, 30, 50, 60, 70, 80}.

• {30, 50, 80} and {20, 60, 70} are merged to form {30, 50, 80, 20, 60, 70}.

Consider the following data field and method. Method maxHelper is intended to return the largest value among the first numVals values in an array; however, maxHelper does not work as intended.

private int[] nums;

// precondition: 0 < numVals <= nums.length

private int maxHelper(int numVals)

{

Line 1: int max = maxHelper(numVals - 1);

Line 2: if (max > nums[numVals - 1])

return max;

else

return nums[numVals - 1];

}

Which of the following best describes the conditions under which maxHelper does not work as intended?

• When numVals is 1

• When numVals is even

• When the elements of nums are in nonincreasing order

• When the elements of nums are in nondecreasing order

• Method maxHelper never works as intended.