Recursion: MCQ

Consider the following recursive method, which is intended to display the binary equivalent of a decimal
number. For example, toBinary(100) should display 1100100.

public static void toBinary(int num)

{
if (num < 2)
{
[Link](num);
}
else
{
/* missing code */
}

Which of the following can replace /* missing code */ so that toBinary works as intended?
A
[Link](num % 2);
toBinary(num / 2);

B
[Link](num / 2);
toBinary(num % 2);

C
toBinary(num % 2);
[Link](num / 2);

D
toBinary(num / 2);
[Link](num % 2);

E
toBinary(num / 2);
[Link](num / 2);
2

Consider the following recursive method, which is intended to return a String with any
consecutive duplicate characters removed. For example, removeDupChars("aabcccd") returns
"abcd".

public static String removeDupChars(String str)

{
if (str == null || [Link]() <= 1)
{
return str;
}
else if ([Link](0, 1).equals([Link](1, 2)))
{
return removeDupChars([Link](1));
}
else
{
/* missing code */
}

Which of the following can replace /* missing code */ so that removeDupChars works as intended?

A. return removeDupChars([Link](2));
B. return removeDupChars([Link](1)) + [Link](0, 1);
C. return removeDupChars([Link](2)) + [Link](1, 2);
D. return [Link](0, 1) + removeDupChars([Link](1));
E. return [Link](1, 2) + removeDupChars([Link](2));
3

Consider the following method, which is intended to return the sum of all the even digits in its
parameter num. For example, sumEvens(15555234) should return 6, the sum of 2 and 4.

/** Precondition: num >= 0 */

public static int sumEvens(int num)

{
if (num < 10 && num % 2 == 0)
{
return num;
}
else if (num < 10)
{
return 0;
}
else if (num >= 10 && num % 2 == 0)
{
/* missing statement */
}
else
{
return sumEvens(num / 10);
}

Which of the following can be used as a replacement for /* missing statement */ so that the
sumEvens method works as intended?

A. return sumEvens(num % 10);

B. return sumEvens(num / 10);
C. return num % 10 + sumEvens(num % 10);
D. return num % 10 + sumEvens(num / 10);
E. return num / 10 + sumEvens(num % 10);
4
Consider the following method.
/** Precondition: n > 0 */

public static void mystery(int n)

{
[Link](n + " ");
if (n > 1)
{
mystery(n - 1);
}

Which of the following best describes the output produced by the method call mystery(val) ?
A. All integers from 1 to val, separated by spaces
B. All integers from val to 1, separated by spaces
C. The digits of val in their original order, separated by spaces
D. The digits of val in reverse order, separated by spaces
E. The last digit of val, then a space, then the first digit of
val

Consider the following recursive method.

public static String doSomething(String str)

{
if ([Link]() < 1)
{
return "";
}
else
{
return [Link](0, 1) +
doSomething([Link](1));
}

Which of the following best describes the result of the call doSomething(myString) ?

A. The method call returns a String containing the contents of myString unchanged.
B. The method call returns a String containing the contents of myString with the order of the
characters reversed from their order in myString.
C. The method call returns a String containing all but the first character of myString.
D. The method call returns a String containing only the first and second characters of myString.
E. The method call returns a String containing only the first and last characters of myString.
6

Consider the following recursive method.

/** Precondition: n > 0 */

public static int calc(int n)

{
if (n <= 9)
{
return n;
}
else
{
return calc(n / 10);
}

}
Which of the following best describes the value returned by the method call calc(num) ?

A. The int value 9.

B. The leftmost digit of num
C. The rightmost digit of num
D. The number of digits in num
E. The result of the integer division of num by 10
 Sorting and Searching: MCQ
1
Consider the following correct implementation of the insertion sort algorithm.

public static void insertionSort(int[] elements)

{
for (int j = 1; j < [Link]; j++)
{
int temp = elements[j];
int possibleIndex = j;
while (possibleIndex > 0 && temp < elements[possibleIndex - 1])
{
elements[possibleIndex] = elements[possibleIndex - 1];
possibleIndex--; // line 10
}
elements[possibleIndex] = temp;
}
}

The following declaration and method call appear in a method in the same class as insertionSort.

int[] arr = {10, 8, 3, 4};

insertionSort(arr);

How many times is the statement possibleIndex--; in line 10 of the method executed as a result of the call to
insertionSort ?
A. 0
B. 1
C. 4
D. 5
E. 6
 2
Consider the following correct implementation of the insertion sort algorithm.
public static void insertionSort(int[] elements)
{
for (int j = 1; j < [Link]; j++)
{
int temp = elements[j];
int possibleIndex = j;
while (possibleIndex > 0 && temp < elements[possibleIndex - 1])
{
elements[possibleIndex] = elements[possibleIndex - 1];
possibleIndex--;
}
elements[possibleIndex] = temp; // line 12
}
}

The following declaration and method call appear in a method in the same class as insertionSort.
int[] nums = {8, 7, 5, 4, 2, 1};
insertionSort(nums);

How many times is the statement elements[possibleIndex] = temp; in line 12 of the method executed as a
result of the call to insertionSort ?
A. 3
B. 4
C. 5
D. 6
E. 7
 3
Consider the following correct implementation of the selection sort algorithm.

public static void selectionSort(int[] elements)

{
for (int j = 0; j < [Link] - 1; j++)
{
int minIndex = j;
for (int k = j + 1; k < [Link]; k++)
{
if (elements[k] < elements[minIndex])
{
minIndex = k;
}
}

if (j != minIndex)
{
int temp = elements[j];
elements[j] = elements[minIndex];
elements[minIndex] = temp; // line 19
}
}

The following declaration and method call appear in a method in the same class as selectionSort.

int[] arr = {30, 40, 10, 50, 20};

selectionSort(arr);

How many times is the statement elements[minIndex] = temp; in line 19 of the method executed as a result
of the call to selectionSort ?

A. 1
B. 2
C. 3
D. 4
E. 5
4

Consider the following mergeSortHelper method, which is part of an algorithm to recursively

sort an array of integers.

/** Precondition: ([Link] == 0 or 0 <= from <= to <=

* [Link])
* [Link] == [Link]
*/

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[] arr1 = {9, 1, 3, 5, 4};

int[] temp = new int[[Link]];

mergeSortHelper(arr1, 0, [Link] - 1, temp);

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

A. {9} and {1} are merged to form {1, 9}.

B. {1, 9} and {3} are merged to form {1, 3, 9}.
C. {1, 9} and {5, 4} are merged to form {1, 4, 5, 9}.
D. {1, 3, 9} and {5} are merged to form {1, 3, 5, 9}.
E. {1, 3, 9} and {4, 5} are merged to form {1, 3, 4, 5, 9}.
5

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

/** Returns an index in arr where target appears, if target appears

* in arr between arr[low] and arr[high], inclusive;
* otherwise, returns -1.
* Precondition: arr is sorted in ascending order.
* low >= 0, high < [Link], [Link] > 0
*/

public static int binarySearch(int[] arr, int low, int high, int target)
{

if (low > high)

{
return -1;
}

int middle = (low + high) / 2;

if (target == arr[middle])
{
return middle;
}
else if (target < arr[middle])
{
return binarySearch(arr, low, middle - 1, target);
}
else
{
return binarySearch(arr, middle + 1, high, target);
}

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

int[] arr = {2, 3, 12, 34, 54};

int result = binarySearch(arr, 0, [Link] - 1, 5);

If the first call to binarySearch is the call in the code segment above, with low = 0 and high = 4,
which, if any, of the following shows the values of low and high when binarySearch is called for
the third time?

A. low = 0, high = 1
B. low = 0, high = 2
C. low = 1, high = 1
D. low = 2, high = 1
E. The method returns to the calling code segment before the third call to binarySearch.
6

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 < [Link], [Link] > 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 target = 10;

int[] arrWithDups = {2, 3, 7, 8, 10, 10, 10, 20};
int arrIndex = bSearch(arrWithDups, 0, [Link] - 1, target);

What is the value of arrIndex after the code segment has been executed?
A. 4
B. 5
C. 6
D. 7
E. 10
7

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

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

* if target appears in theList between the elements at indices
* low and high, inclusive; otherwise returns -1.
* Precondition: theList is sorted in ascending order.
* low >= 0, high < [Link](), [Link]() > 0
*/

public static int binarySearch(ArrayList<Integer> theList, int low,

int high, int target)
{
if (low > high)
{
return -1;
}

int middle = (low + high) / 2;

if (target == [Link](middle))
{
return middle;
}
else if (target < [Link](middle))
{
return binarySearch(theList, low, middle - 1, target);
}
else
{
return binarySearch(theList, middle + 1, high, target);
}

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

ArrayList<Integer> theList = new ArrayList<Integer>();

for (int k = 10; k < 65; k = k + 5)
{
[Link](k);
}
int result = binarySearch(theList, 0, [Link]() - 1, 45);

Including the call to binarySearch in the last statement of the given code segment, how many
times will binarySearch be called before a value is returned?
A. 1
B. 2
C. 3
D. 4
E. 8
8

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

/** Returns an index in arr where the value str appears if str appears
* in arr between arr[left] and arr[right], inclusive; otherwise returns -1.
* Precondition: arr is sorted in ascending order.
* left >= 0, right < [Link], [Link] > 0
*/
public static int bSearch(String[] arr, int left, int right, String str)
{

if (right >= left)

{
int mid = (left + right) / 2;
if (arr[mid].equals(str))
{
return mid;
}
else if (arr[mid].compareTo(str) > 0)
{
return bSearch(arr, left, mid - 1, str);
}
else
{
[Link]("right");
return bSearch(arr, mid + 1, right, str);
}
}
return -1;

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

String[] words = {"arc", "bat", "cat", "dog", "egg", "fit", "gap",

"hat"};

int index = bSearch(words, 0, [Link] - 1, "hat");

How many times will "right" be printed when the code segment is executed?
A. 1
B. 2
C. 3
D. 7
E. 8
9

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

/** Returns an index in nums where target appears if target appears in nums between
* nums[lo] and nums[hi], inclusive; otherwise, returns -1.
* Precondition: nums is sorted in ascending order.
* low >= 0, high < [Link], [Link] > 0
*/
public static int bSearch(int[] nums, int low, int high, int target)
{

if (high >= low)

{
int mid = (low + high) / 2;
if (nums[mid] == target)
{
return mid;
}
if (nums[mid] > target)
{
return bSearch(nums, low, mid - 1, target);
}
else
{
return bSearch(nums, mid + 1, high, target);
}
}
return -1;

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

int target = 3;
int[] nums = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int targetIndex = bSearch(nums, 0, [Link] - 1, target);

How many times will bSearch be called as a result of executing the code segment above?

A. 1
B. 2
C. 3
D. 4
E. 5
 10
Consider the following correct implementation of the insertion sort algorithm. The insertionSort method
correctly sorts the elements of ArrayList data into increasing order.
public static void insertionsort(ArrayList<Integer> data)
{
for (int j = 1; j < [Link](); j++)
{
int v = [Link](j);
int k = j;
while (k > 0 && v < [Link](k - 1))
{
[Link](k, [Link](k - 1)); /* Statement 1 */
k--；
}
[Link](k, v); /* Statement 2 */
/* End of outer loop */
}
}
Assume that insertionSort has been called with an ArrayList parameter that has been initialized with the
following integer objects.
[5, 2, 4, 1, 3, 6]
What will the contents of data be after three passes of the outside loop (i.e., when j == 3 at the point
indicated by /* End of outer loop */) ?
(A) [1, 2, 3, 4, 5, 6]
(B) [1, 2, 3, 5, 4, 6]
(C) [1, 2, 4, 5, 3, 6]
(D) [2, 4, 5, 1, 3, 6]
(E) [5, 2, 1, 3, 4, 6]
 11
Consider the following correct implementation of the insertion sort algorithm. The insertionsort method
correctly sorts the elements of ArrayList data into increasing order.
public static void insertionsort(ArrayList<Integer> data)
{
for (int j = 1; j < [Link](); j++)
{
int v = [Link](j);
int k = j;
while (k > 0 && v < [Link](k - 1))
{
[Link](k, [Link](k - 1)); /* Statement 1 */
k--；
}
[Link](k, v); /* Statement 2 */
/* End of outer loop */
}
}
Assume that insertionsort is called with an ArrayList parameter that has been initialized with the following
integer objects.
[1, 2, 3, 4, 5, 6 ]
How many times will the statements indicated by /* Statement 1 */ and /* Statement 2 */ execute?

(A)
Statement 1 Statement 2

0 0

(B)
Statement 1 Statement 2

0 5

(C)
Statement 1 Statement 2

0 6

(D)
Statement 1 Statement 2

5 5

(E)
Statement 1 Statement 2

6 6
 12
Consider the following correct implementation of the selection sort algorithm.
public static void selectionSort(int[] elements)
{
for (int j = 0; j < [Link] - 1; j++)
{
int minindex = j;
for (int k = j + 1; k < [Link]; k++)
{
if (elements[k] < elements[minindex])
{
minindex = k;
}
}
if (j != minindex)
{
int temp = elements[j];
elements[j] = elements[minindex];
elements[minindex] = temp; // Line 19
}
}
}
The following declaration and method call appear in a method in the same class as selectionsort.
int[ ] arr = {9, 8, 7, 6, 5};
selectionSort(arr);
How many times is the statement elements [minindex ] = temp； in line 19 of the method
executed as a result of the call to selectionSort ?
(A) 1
(B) 2
(C) 3
(D) 4
(E) 5

13
Consider the following code segment from an insertion sort program.
for (int j = 1； j < [Link]； j++)
{
int insertitem = arr[j];
int k = j - 1;
while (k >= 0 && insertitem < arr[k])
{
arr[k + 1] = arr[k];
k--；
}
arr[k + 1] = insertitem；
/* end of for loop */
}
Assume that array arr has been defined and initialized with the values {5,4,3,2,1}. What are the
values in array arr after two passes of the for loop (i.e., when j = 2 at the point indicated by / * end of for
loop */) ?
(A) {2, 3, 4, 5, 1}
(B) {3, 2, 1, 4, 5}
(C) {3, 4, 5, 2, 1}
(D) {3, 5, 2, 3, 1}
(E) {5, 3, 4, 2, 1}
 14
The following sort method correctly sorts the integers in elements into ascending order
Line 1: public static void sort (int [] elements)
Line 2: {
Line 3: for (int j = 0； j < elements. length - 1； j+ + )
Line 4: {
Line 5. int index = j ；
Line 6:
Line 7: for (int k = j + 1； k < elements. length； k+ + )
Line 8: {
Line 9: if (elements [k] < elements [index])
Line 10: {
Line 11: index = k；
Line 12: }
Line 13: }
Line 14:
Line 15： int temp = elements [ j ]；
Line 16: elements [ j ] = elements [index]；
Line 17: elements [index] = temp；
Line 18: }
Line 19: }
Which of the following changes to the sort method would correctly sort the integers in elements into
descending order?

I. Replace line 9 with:

Line 9: if (elements [k] > elements [index])

II. Replace lines 15-17 with:

Line 15: int temp = elements [index]；
Line 16: elements [index] = elements [ j ]；
Line 17: elements [ j ] = temp；

III. Replace line 3 with:

Line3: for (int j = [Link] - 1； j > 0； j —)
and replace line 7 with:
Line 7: for (int k = 0； k < j ； k+ + )

(A) I only
(B) II only
(C) I and II only
(D) I and III only
(E) I, II and III
 15
Consider the following correct implementation of the insertion sort algorithm.
public static void insertionSort(int[] elements)
{
for (int j= 1; j < [Link]; j++)
{
int temp = elements [j];
int possibleIndex = j;

while (possibleIndex > 0 && temp < elements [possibleIndex - 1])

{
elements [possibleIndex] = elements [possibleIndex - 1];
possibleIndex--; // Line 10
}
elements [possibleIndex] = temp;
}
}

The following declaration and method call appear in a method in the same class as insertionSort.

int[] arr = {4, 12, 4, 7, 19, 6};

insertionSort(arr);

How many times is the statement possibleIndex--; in line 10 of the method executed as a result of the
call to insertionSort?

(A) 2
(B) 3
(C) 4
(D) 5
(E) 6
 16
Consider the following correct implementation of the selection sort algorithm.
public static void selectionSort(int[] elements)
{

for(int j = 0; j < [Link] – 1; j++)

{
int minIndex= j;
for (int k=j+1; k < [Link];k++)
{
if (elements[k] < elements[minIndex])
{
minIndex=k; // Line 11
}
}
if (j!= minIndex)
{
int temp = elements[j];
elements[j]= elements[minIndex];
elements[minIndex]=temp;
}
}
}

The following declaration and method call appear in the same class as selectionsort.

int[] vals ={5, 10, 2, 1,12};

selectionSort(vals);

How many times is the statement minIndex = k; in line 11 of the method executed as a result of the call
to selectionsort?
(A) 0
(B) 1
(C) 2
(D) 3
(E) 4

17
Consider the following two data structures for storing several million words.

I. An array of words, not in any particular order

II. An array of words, sorted in alphabetical order

Which of the following statements most accurately describes the time needed for operations on these data
structures?

(A) Inserting a word is faster in II than in I.

(B) Finding a given word is faster in I than in II.
(C) Finding a given word is faster in II than in I.
(D) Finding the longest word is faster in II than in I.
(E) Finding the first word in alphabetical order is faster in I than in II.
 18
Consider the static method selectSort shown below. Method selectSort is intended to sort an array into
increasing order; however, it does not always work as intended.

// precondition: [Link] > 0

// postcondition: numbers is sorted in increasing order
public static void selectsort (int [] numbers)
{
int temp;
Line 1: for (int j = 0;j < [Link] - 1; j++)
{
Line 2: int pos = 0;
Line 3: for (int k = j + 1; k < [Link]; k++)
{
Line 4: if (numbers [k] < numbers [pos])
{
Line 5: pos = k;
}
}
temp = numbers [j];
numbers [j] = numbers [pos];
numbers [pos] = temp;
}
}

Which of the following changes should be made so that selectSort will work as intended?

(A) Line 1 should be changed to

for (int j = 0; j < [Link] - 2; j++)

(B) Line 2 should be changed to

int pos = j;

(C) Line 3 should be changed to

for (int k = 0; k < [Link]; k++)

(D) Line 4 should be changed to

If( numbers[k] > numbers[pos] )

(E) Line 5 should be changed to

k = pos;
 19
Consider the following method.

public static void sort (String [] arr)

{
for (int pass = [Link] - 1; pass >= 1; pass--)
{
String large = arr[0];
int index = 0;
for (int k = 0; k <= pass; k++)
{
if ((arr[k] .compareTo (large)) > 0)
{
large = arr[k];
index = k;
}
}
arr [index] = arr [pass];
arr [pass] = large;
}
}
Assume arr is the following array.
"Ann" "Mike" "Walt" "Lisa" "Shari" "Jose" "Mary" "Bill"

What is the intermediate value of arr after two iterations of the outer for loop in the call sort (arr)?

(A)
"Ann" "Mike" "Walt" "Lisa" "Shari" "Jose" "Mary" "Bill"

(B)
"Ann" "Mike" "Lisa" "Shari" "Jose" "Mary" "Bill" "Walt"

(C)
"Ann" "Bill" "Jose" "Lisa" "Mary" "Mike" "Shari" "Walt"

(D)
"Ann" "Mike" "Bill" "Lisa" "Mary" "Jose" "Shari" "Walt"

(E)
"Walt" "Shari" "Ann" "Lisa" "Mike" "Jose" "Mary" "Bill"
 20
Directions: Select the choice that best fits each statement. The following question(s) refer to the following
information.
Consider the following sort method. This method correctly sorts the elements of array data into increasing
order.
public static void sort(int[]data)
{
for (int j=0; j<[Link] – 1; j ++)
{
int m = j;
for (int k = j+1;k < [Link]; k ++)
{
if (data[k] < data[m]) /*Compare values */
{
m = k;
}
}
int temp = data[m]; /*Assign to temp */
data[m] = data[j];
data[j]=temp;
/* End of outer loop */
}
}
Assume that sort is called with the array {6,3,2,5,4,1}.What will the value of data be after three passes of the
outer loop(i.e.,when j=2 at the point indicated by /* End of outer loop*/)?

(A) {1, 2, 3, 4, 5, 6}
(B) {1, 2, 3, 5, 4, 6}
(C) {1, 2, 3, 6, 5, 4}
(D) {1, 3, 2, 4, 5, 6}
(E) {1, 3, 2, 5, 4, 6}
 21
Directions: Select the choice that best fits each statement. The following question(s) refer to the following
information.
Consider the following sort method. This method correctly sorts the elements of array data into increasing
order.
public static void sort(int[] data)
{
for (int j = 0; j < [Link] - 1; j++)
{
int m = j;
for (int k = j + 1; k < [Link]; k++)
{
if (data [k] < data [m] ) /* Compare values */
{
m = k;
}
}
int temp = data[m] ; /* Assign to temp */
data[m] = data[j];
data[j] = temp；
/ * End of outer loop * /
}
}
Assume that sort is called with the array {1,2,3,4,5,6}. How many times will the expression indicated by /*
Compare values */ and the statement indicated by /* Assign to temp */ execute?
(A) Compare values / Assign to temp
15/0
(B) Compare values / Assign to temp
15/5
(C) Compare values / Assign to temp
15/6
(D) Compare values / Assign to temp
21/5
(E) Compare values / Assign to temp
21/6
 22
The following incomplete method is intended to sort its array parameter arr in increasing order.
//postcondition: arr is sorted in increasing order
public static void sortArray(int[] arr)
{
int j, k;
for (j = [Link] - 1; j > 0; j--)
{
int pos = j;
for ( /* missing code */ )
{
if (arr(k] > arr(pos])
{
pos = k;
}
}
swap(arr, j, pos);
}
}

Assume the swap(arr, j, pos) exchanges the values of arr[i] and arr[j]. Which of the
following could be used to replace /* missing code */ so that executing the code segment sorts the
values in array arr?

(A) k = j - 1; k > 0; k--

(B) k = j - 1; k >= 0; k--
(C) k = 1; k < [Link]; k++
(D) k = 1; k > [Link]; k++
(E) k = 0; k <= [Link]; k++