AP CSP Practice Test – Unit 10 Review Questions

Questions refer to the Hi-Lo game described below.

Consider the problem of writing a Hi-Lo game in which a user thinks of an integer from 1 to 100 inclusive and the computer tries to guess that number. Each time the computer makes a guess, the user makes one of three responses:

• “lower” (i.e., the number is lower than the computer’s guess)
• “higher” (i.e., the number is higher than the computer’s guess)
• “you got it in < however many > tries!”

Suppose the game is programmed so that the computer uses a binary search strat- egy for making its guesses. What is the maximum number of guesses the com- puter could make before guessing the user’s number?

Consider a binary search algorithm to search an ordered list of numbers. Which of the following choices is closest to the maximum number of times that such an algorithm will execute its main comparison loop when searching a list of 1 million numbers?

A binary search is to be performed on an array with 600 elements. In the worst case, which of the following best approximates the number of iterations of the algorithm?

Assume that mergesort will be used to sort an array arr of n integers into increas- ing order. What is the purpose of the merge method in the mergesort algorithm?

The array names[0], names[1], . . . , names[9999] is a list of 10,000 name strings.
The list is to be searched to determine the location of some name X in the list.

Which of the following preconditions is necessary for a binary search?

The code shown sorts the array a[0] . . . a[a.length-1] in descending order using the following approach:

public static void sort(String[] a)
{
for (int i = 0; i < a.length - 1; i++)
for (int j = 0; j < a.length - i - 1; j++)
if (a[j].compareTo(a[j+1]) < 0)
swap(a, j, j + 1); // swap a[j] and a[j+1]
}

This sorting method involves comparing adjacent elements and swapping them if they are in the wrong order, repeatedly passing through the array. This process continues until the entire array is sorted.

This is an example of:

Questions are based on the binSearch method and the private instance variable a for some class:

private int[] a;
/** Does binary search for key in array a[0]...a[a.length-1],
* sorted in ascending order.
* @param key the integer value to be found
* Postcondition:
* - index has been returned such that a[index]==key.
* - If key not in a, return -1.
*/
public int binSearch(int key)
{

int low = 0;
int high = a.length - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] == key)
return mid;
else if (a[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;

}

A binary search will be performed on the following list.

For binSearch, which of the following assertions will be true following every iteration of the while loop?

Questions are based on the binSearch method and the private instance variable a for some class:

private int[] a;
/** Does binary search for key in array a[0]...a[a.length-1],
* sorted in ascending order.
* @param key the integer value to be found
* Postcondition:
* - index has been returned such that a[index]==key.
* - If key not in a, return -1.
*/
public int binSearch(int key)
{

int low = 0;
int high = a.length - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] == key)
return mid;
else if (a[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;

}

A binary search will be performed on the following list.

 If the test for the while loop is changed to while (low < high), the binSearch method does not work as intended. Which value in the given list will not be found?

Questions are based on the binSearch method and the private instance variable a for some class:

private int[] a;
/** Does binary search for key in array a[0]...a[a.length-1],
* sorted in ascending order.
* @param key the integer value to be found
* Postcondition:
* - index has been returned such that a[index]==key.
* - If key not in a, return -1.
*/
public int binSearch(int key)
{

int low = 0;
int high = a.length - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] == key)
return mid;
else if (a[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;

}

A binary search will be performed on the following list.

What will be stored in y after executing the following?

int y = binSearch(4);

Questions are based on the binSearch method and the private instance variable a for some class:

private int[] a;
/** Does binary search for key in array a[0]...a[a.length-1],
* sorted in ascending order.
* @param key the integer value to be found
* Postcondition:
* - index has been returned such that a[index]==key.
* - If key not in a, return -1.
*/
public int binSearch(int key)
{

int low = 0;
int high = a.length - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] == key)
return mid;
else if (a[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;

}

A binary search will be performed on the following list.

How many iterations will be required to determine that 27 is not in the list?

Questions are based on the binSearch method and the private instance variable a for some class:

private int[] a;
/** Does binary search for key in array a[0]...a[a.length-1],
* sorted in ascending order.
* @param key the integer value to be found
* Postcondition:
* - index has been returned such that a[index]==key.
* - If key not in a, return -1.
*/
public int binSearch(int key)
{

int low = 0;
int high = a.length - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] == key)
return mid;
else if (a[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;

}

A binary search will be performed on the following list.

To find the key value 27, the search interval after the first pass through the while loop will be

Consider the following class:

/** A class that sorts an array of Integer objects from
* largest to smallest using a selection sort.
*/
public class Sorter
{
private Integer[] a;

public Sorter(Integer[] arr)
{
a = arr;
}

/** Swap a[i] and a[j] in array a. */
private void swap(int i, int j)
{
// implementation not shown
}

/** Sort array a from largest to smallest using selection sort.
* Precondition: a is an array of Integer objects.
*/
public void selectionSort()
{
for (int i = 0; i < a.length - 1; i++)
{
// find max element in a[i+1] to a[n-1]
Integer max = a[i];
int maxPos = i;
for (int j = i + 1; j < a.length; j++)
if (max.compareTo(a[j]) < 0) // max less than a[j]
{
max = a[j];
maxPos = j;
}
swap(i, maxPos); // swap a[i] and a[maxPos]
}
}
}

If an array of Integer contains the following elements: 89, 42, -3, 13, 109, 70, 2, what would the array look like after the third pass of selectionSort, sorting from high to low?

An algorithm for searching a large sorted array for a specific value x compares every third item in the array to x until it finds one that is greater than or equal to x. When a larger value is found, the algorithm compares x to the previous two items. If the array is sorted in increasing order, which of the following describes all cases when this algorithm uses fewer comparisons to find x than would a binary search?

A user enters several positive integers at the keyboard and terminates the list with a sentinel (-999). A writeEven method reads those integers and outputs the even integers only, in the reverse order that they are read. Thus, if the user enters 3 5 14 6 1 8 -999, the output for the writeEven method will be 8 6 14. Assume that the user enters at least one positive integer and terminates the list with -999. Here is the method:

/** Postcondition: All even integers in the list are output in
* reverse order.
*/
public static void writeEven()
{
int num = IO.readInt(); // read user input
if (num != -999)
{
/* code */
}
}

Which /* code */ satisfies the postcondition of method writeEven?

I. if (num % 2 == 0) System.out.print(num + " "); writeEven();

II. if (num % 2 == 0) writeEven(); System.out.print(num + " ");

III. writeEven(); if (num % 2 == 0) System.out.print(num + " ");

Which best describes what the printString method below does?

public void printString(String s)
{
if (s.length() > 0)
{
printString(s.substring(1));
System.out.print(s.substring(0, 1));
}
}

What does method recur do?

/** @param x an array of n integers

@param n a positive integer
*/
public int recur(int[] x, int n)
{
int t;
if (n == 1)
return x[0];
else
{
t = recur(x, n - 1);
if (x[n-1] > t)
return x[n-1];
else
return t;
}
}

Refer to method f:

public int f(int k, int n)
{
if (n == k)
return k;
else
if (n > k)
return f(k, n - k);
else
return f(k - n, n);
}

What value is returned by the call f(6, 8)?

Refer to method mystery:

public int mystery(int n, int a, int d)
{
if (n == 1)
return a;
else
return d + mystery(n - 1, a, d);
}

What value is returned by the call mystery(3, 2, 6)?

Questions  refer to method result:

public int result(int n)
{
if (n == 1)
return 2;
else
return 2 * result(n - 1);
}

If n > 0, how many times will result be called to evaluate result(n) (including the initial call)?

Questions  refer to method result:

public int result(int n)
{
if (n == 1)
return 2;
else
return 2 * result(n - 1);
}

What value does result(5) return?

Which of the following statements about recursion are true?

I. Every recursive algorithm can be written iteratively.
II. Tail recursion is always used in “divide-and-conquer” algorithms.
III. In a recursive definition, a process is defined in terms of a simpler case of itself.

Which of the following, when used as the /* body / of method sum, will enable that method to compute 1 + 2 + · · · + n correctly for any n > 0?

/* @param n a positive integer

@return 1 + 2 + ... + n
/
public int sum(int n)
{
/ body */
}

I. return n + sum(n - 1);
II. if (n == 1) return 1; else return n + sum(n - 1);
III. if (n == 1) return 1; else return sum(n) + sum(n - 1);

Refer to the method stringRecur:

public void stringRecur(String s)
{
if (s.length() < 15) System.out.println(s);
stringRecur(s + "*");
}

When will method stringRecur terminate without error?

Refer to method strRecur:

public void strRecur(String s)
{
if (s.length() < 15)
{
System.out.println(s);
strRecur(s + "*");
}
}

When will method strRecur terminate without error?