# 12.4. Exam 3 for the AP CS A Exam (not timed)¶

The following problems are similar to what you might see on the AP CS A exam. Please answer each to the best of your ability.

14-4-1: Consider the following segment of code. For the method call t(5), how many calls to t will be made, including the original call?

public int t(int n)
{
if (n == 1 || n == 2)
return 2 * n;

else
return t(n - 1) - t(n - 2);
}

• 4
• The method makes more than 4 calls. Remember that the method must make a call to check every value of n, even if n is the value in the base case.
• 15
• This would be correct if t(6) was used. Try tracing the code again.
• 9
• t(5) returns t(4) - t(3). t(4) returns t(3) - t(2), while t(3) returns t(2) - t(1). If you trace the code throughout the calls, t is called 9 times.
• 14
• This would be correct if the method reached the base case when n equaled 1 or 0, not 1 or 2. Check the code to see when a recursive call is made.
• 5
• This would be correct if t(4) was called. Try tracing the code again.

14-4-2: Consider the following class declarations. Which of the following code can be executed in the Swan class?

public class Bird
{
private String color;

public Bird(String theColor)
{
/* implementation not shown */
}

public void makeNoise()
{
/* implementation not shown */
}

public void eat()
{
/* implementation not shown */
}

public string showFeathers()
{
return color;
}
}

public class Swan extends Bird
{
/* no constructors or other methods have been declared */
}

I. this.color = "blue";

II. eat();

III. Swan s = new Swan("blue");

• I only
• The color is a private instance variable in Bird. Children classes do not have direct access to private variables. They must use the public getter and setter methods to access the private variables.
• II only
• The public eat method was inherited from the Bird class and can be called from code in the Swan class.
• III only
• Constructors are not inherited by sub classes. Only public accessor and mutator methods are inherited by sub classes.
• I and II only
• II is correct, but I is incorrect. Private instance variables cannot be directly accessed by the child class.
• I, II, and III
• II is correct, but I and III are incorrect. Constructors are not inherited and subclasses do not have direct access to private instance variables.

14-4-3: Consider the following code. Assume that list is an ArrayList of integers that contains [7, 3, 2]. What will the contents of list be after the following code is executed?

list.add(4);
list.remove(2);
list.set(2, 1);

• [7, 1, 4, 8, 3]
• Remember that in ArrayLists, indexing starts at 0, not at 1. If the add method has two parameters, then the value is added at a specific index, not at the end of the list.
• [7, 8, 1, 2, 4, 3]
• The set method replaces a value at the specific index. The original value is erased.
• [7, 3, 1, 4, 3]
• Remember that there are two add methods for ArrayLists. If the add method has two parameters, then a value is added at a specific index, not at the end of the list.
• [8, 1, 2, 4, 3]
• Remember that in ArrayLists, indexing starts at 0, not at 1.
• [7, 8, 1, 4, 3]
• 4 is added to the end of the ArrayList, then 8 is added at index one between 7 and 3. The 3 in index two is removed, then the 2 in the second index is replaced with 1. Finally, 3 is added to the end of the ArrayList, which contains [7, 8, 1, 4, 3].

14-4-4: The method rowSums returns an array of integers. Each element of the array holds the sum of the corresponding row of a 2-D matrix. Which line correctly fills in \* to be determined *\ in rowSums?

public int[] rowSums(int[][] arr)
{
int[] ans = new int[arr.length];

for (int i = 0; i < arr.length; i++)
{
for (int j = 0; j < arr[0].length; j++)
{
/* to be determined */
}
}

return ans;
}

• arr[i][j] = ans[i];
• In Java, assignments work from right to left. This answer assigns the value of ans[i] in the 1-D array to the value of the 2-D array. Instead, we want to add the values of the row i in the 2-D array and assign this sum to ans[i] in the 1-D array.
• ans[i] += arr[i][j];
• In order to return the right array, the value at ans[i] must contain the sums of every element in row i of the 2-D array. The second for-loop adds the value of every element in row i of the 2-D array and assigns these values to ans[i].
• ans[i ][j] += arr[i][j];
• Notice that ans is a 1-D array, not a 2-D array. There cannot be two indexes for an element of ans, because ans is only a 1-D array.
• ans[i] = arr[i][j];
• This line reassigns the value of arr[i][j] to ans[i], but it does not sum all the values in the row. This line would return an array with the value in the last column of each row.
• arr[i][j] += ans[i];
• Remember that assignment works from right to left in Java. This line adds the value of ans[i] in the 1-D array to the value of arr[i][j] in the 2-D array. The 2-D array should not be modified by this method.

14-4-5: Consider the following method binSearch, which uses binary search to locate an element key in an array of integers arr. If list is an array of integers containing {4, 7, 9, 11, 20, 24, 30, 41}, how many iterations of the while loop occur in binSearch(30, list)?

public static int binSearch(int key, int[] arr)
{
int low = 0;
int high = arr.length - 1;

while (low <= high)
{
int mid = (low + high) / 2;

if (arr[mid] == key)
return mid;

else if (arr[mid] < key)
low = mid + 1;

else
high = mid - 1;
}

return -1;
}

• 1
• 30 would not have been located in 1 iteration of the while loop. After one iteration, low would equal 0, mid would equal 3, and high would equal 7. Because list[3] is equal to 11, not 30, nothing is returned, low becomes 4, and the while-loop continues.
• 2
• 30 would not have been located in 2 iterations of the while loop. After two iterations, mid would equal 5. Because list[5] is equal to 24, not 30, low would increase, and the while-loop would run again. Try one more iteration of the while loop.
• 3
• 30 would be found in 3 iterations. After the third iteration of the while loop, mid would equal 6. list[6] equals 30, so 6 is returned and the while-loop is exited.
• 4
• 4 iterations is too many iterations. Only 3 iterations are needed to find 30 in the array. After 4 iterations for an array with 7 elements, either the key is not present in the array or the key is at the first or last index of the array.
• 5
• Only 3 iterations of the while loop are needed to find 30 in the array. After 5 iterations for an array with seven elements, it must be that the key was not found.

14-4-6: The wordScramble method is shown below. What is returned as a result of wordScramble("hello")?

public static String wordScramble (String str)
{
if (str.length() == 0)
return "!";
else
return wordScramble(str.substring(1)) + str.substring(0,1);
}

• "!hello!"
• The exclamation point is returned only once, when the method reaches its base case. Because the compiler works through the recursive calls to the end of the word before it returns any strings, the letters are printed in reverse order.
• "hello!"
• The compiler works through all of the recursive calls before it returns any strings. The exclamation point is returned first, followed by the letters of the original string in reverse order.
• "!hello"
• This string would be correct if the substring was returned before the recursive call. Because the recursive call occurs before the substring is returned, the compiler reaches the end of the string before it returns the letters, so the letters are reversed.
• "olleh!"
• The exclamation point is printed before the letters of the word. The method makes recursive calls until the length of the string equals 0 and the base case has been reached. Then, an exclamation point is returned to the recursive calls, and the letters are returned after the exclamation point in reverse order.
• "!olleh"
• This method makes multiple calls, removing the first letter from the string until the length of the string in the call equals 0. Then, it returns an exclamation point, followed by the letters of the string in reverse order.

14-4-7: Which of these loops will print multiples of 10, from 0 to 100 inclusive?

I. for (int i = 0; i < 11; i++)
{
System.out.print(i * 10 + " ");
}

II. int i = 0;

while (i <= 10)
{
System.out.print(i * 10 + " ");
i++;
}

III. for (int i = 0; i <= 100; i += 10)
{
System.out.print(i + " ");
}

• I only
• I is correct, but II and III are correct as well. This task can be accomplished by using a for loop or a while loop.
• II only
• II is correct, but I and III are correct as well. This task can be accomplished by using a for loop or a while loop.
• III only
• III is correct, but I and II are correct as well. Even though i increments by 1 after each passing of the loop in I and II, i * 10 is printed.
• I and III only
• I and III are correct, but II is correct as well. This task can be accomplished using a for loop or a while loop.
• I, II, and III
• Each of these loops will print out multiples of 10 from 0 to 100, starting at 0 and ending at 10.

14-4-8: The Person and Student classes are found below. Which of the following correctly replaces /* to be completed */ in the Student class?

public class Person
{
private String name;
private int age;

public Person(String theName, int theAge)
{
name = theName;
age = theAge;
}
}

public class Student extends Person
{

public Student(String theName, int theAge, int theGrade)
{
/* to be completed */
}
}

I. name = theName;
age = theAge;

II. super(theName, theAge);

III. super(theName, theAge);
name = theName;
age = theAge;

• I only
• name and age are private instance variables in the Person class. Children classes do not have direct access to private variables in the parent class.
• II only
• This answer correctly calls on the constructor in the Person class using super. Then, it correctly instantiates the instance variable grade, located in the Student class.
• III only
• name and age are private instance variables in the Person class. Children classes do not have direct access to private variables in the parent class. Although the Person constructor has correctly been implemented using the super keyword, name and age cannot be accessed by the Student class.
• I and II only
• II is correct, but name and age instance variables found in the Person class. Instance variables are not inherited and cannot be modified by sub classes.
• I and III only
• name and age are private instance variables in the Person class. Although the constructor from the Person class may be implemented using super, the instance variables in the parent class are not directly accessible by the child class.

14-4-9: A list of integers containing [12, 8, 7, 30, 62, 45, 10, 3] is sorted from largest to smallest using a selection sort method. After three passes, what does the list look like?

• [62, 45, 30, 12, 7, 8, 10, 3]
• This is the fully sorted array after eight passes. Reread the question and try again.
• [30, 12, 8, 7, 62, 45, 10, 3]
• This is the result after three passes of insertion sort. Remember that in selection sort, only two values swap positions after every pass.
• [62, 45, 30, 7, 12, 8, 10, 3]
• Since 62 is the largest value in the array, it swaps position with the value in index 0 of the array, 12. 45 is the next largest value, and it swaps with 8. 30 is the next largest value, and it swaps with 7. So, after three passes the list contains [62, 45, 30, 7, 12, 8, 10, 3].
• [62, 45, 30, 12, 7, 8, 10, 3]
• This is the result after 4 passes of selection sort. Check your steps and try again.
• [12, 8, 30, 7, 62, 45, 10, 3]
• This is the result after one merge of merge sort. Remember that in selection sort, only two values change postions at every pass.

14-4-10: Consider the classes Animal and Pig shown below. What is printed as a result of executing the code below?

public class Animal
{
private String name;

public Animal(String theName)
{
name = theName;
}

public Animal()
{
name = "Animal";
}

public String makeNoise() { return ""; };

public String getName()
{
return name;
}
}

public class Pig extends Animal
{
public Pig(String theName)
{
super(theName);
}

public String makeNoise()
{
return "Oink!";
}

public String getName()
{
return "My name is " + super.getName() + "!";
}

public static void main(String[] args)
{
Animal piglet = new Pig("Piglet");
System.out.print(piglet.getName());
}
}

• "My name is Piglet!"
• At run-time, piglet is a Pig object. The compiler uses the overwritten getName method located in the Pig class, which prints out "My name is " before calling on the getName method in the Animal class.
• "Piglet"
• This would be correct if the getName method had not been overwritten in the Pig class. Because piglet is a Pig object at run-time, the compiler uses the getName method from the Pig class.
• "My name is Animal!"
• Check the constructor method in the Pig class. The Pig class constructor uses the Animal class constructor that has one String parameter, not the default Animal constructor.
• "Animal"
• The constructor in the Pig class uses the Animal class constructor that takes in a string parameter, not the default constructor. The getName method has been overwritten in the Pig class, so "My name is " is printed before the name of the object.
• "Oink"
• Check the problem and note which method has been used. This is what is returned by the makeNoise method.

14-4-11: Consider the following method oddArray, which changes every even number value in the array to 0. By the end of the method, only odd numbers will be present in the array. Which line correctly completes /* to be determined */ to make the code work as intended?

public void oddArray (int[] arr)
{
for (int i = 0; i < arr.length; i++)
{
//if the number at arr[i] is even, it becomes 0
if( /* to be determined */ )
arr[i] = 0;
}
}

• arr[i] / 2 = 2
• To check if a number is even, the modulo operator (%) should be used.
• arr[i] % 2 == 1
• This method checks to see if a number is odd, not even. Because this method changes even numbers, not odd numbers, we do not need to find odd numbers.
• arr[i] / 2 == 1
• To check if a number is even, the modulo operator (%) should be used.
• arr[i] % 2 == 0
• If the value at arr[i] divided by two leaves a remainder of 0, then the number is even and should be reassigned.
• arr[i] / 2 == 0
• To check if a number is even, the modulo operator (%) should be used.

14-4-12: The method numFun is below. What is returned as a result of numFun(21560)?

public static int numFun(int num)
{
if (num / 10 == 0)
return num;

else
return (num % 10) + numFun(num / 10);
}

• 4
• Trace the recursive call and the return statements.
• 5
• Examine the recursive call and the return statements. This method adds the values of the digits in a number; it does not find the number of digits.
• 0
• Examine the return statements. Although the last digit of the number is 0, 0 is returned to the previous calls, where it is added to the other digits.
• 13
• Try tracing the recursive calls again.
• 14
• The method divides the number by 10 until it reaches the first dight. Then, it adds the values of all of the digits together.

14-4-13: Consider the method emptyList, shown below. The method returns true if a List of integers is filled with zeros and false otherwise. Which of the following should replace /* to be completed */ so that the method will work as intended?

public boolean emptyList (List <Integer> list)
{
/* to be completed */
}

// I.
for (int i = 0; i < list.size(); i++)
{
if (list.get(i) != 0)
return false;
}
return true;

// II.
for (int i = 0; i < list.size(); i++)
{
if (list[i] != 0)
return false;
}
return true;

// III.
for (int i = 0; i < list.size(); i++)
{
if (list.get(i) != 0)
return true;
}
return false;

• I only
• This answer checks every index in the list, correctly selects the values in the list and compares them to zero. If a value is not equal to zero, the method returns false, and the array is NOT empty. Otherwise, the method returns true.
• II only
• The variable list is a List, not an array. List values are not directly accessible, so list.get(i) should be used instead of list[i].
• III only
• This method returns true if the list has at least one value in it that is not zero.
• I and II only
• I is correct, but II is incorrect. Because list is not an array, the get method must be used to find the value at a certain index.
• II and III only
• You can not use list[i] to get a value from a list so II is incorrect. III would return true if at least one value in the list is not zero.

14-4-14: You need to find a random integer in the range 1 to 25, inclusive. Which of the following always returns a value that satisfies this condition?

• (int) (Math.random() * 25) * 1
• This returns a value between 0 and 24, not 1 and 25. This would be correct if the last part of the expression had + 1 instead of * 1.
• (int) (Math.random() + 1) * 25
• This always returns 25. Math.random() + 1 becomes 1 when it is cast to an integer, and 1 * 25 equals 25.
• (int) (Math.random() + 25) * 1
• This always returns 25. Math.random() produces a number between 0 and 1, so when it is added to 25 and cast as an integer, the number always becomes 25.
• (int) (Math.random()) * 25 + 1
• This always returns 1. Math.random() produces a value between 0 and 1, so casting Math.random() to an int results in 0. 0 * 25 remains 0, and 0 + 1 equals 1.
• (int) (Math.random() * 25) + 1
• Math.random() * 25 finds a random double value between 0 and 24.9999. This is cast to an integer, and 1 is added so the range becomes 1 to 25.

14-4-15: A list of 120 names has been sorted in alphabetical order. Using a binary search method, what is the minimum number of passes needed to confirm that a name is not in the list?

• 5
• This is not enough passes to guarantee that a name is not present. 2 ^ 5, is 32, which is not enough elements. Remember that binary search takes log2 (number of elements) passes at most to find an item.
• 7
• 2 ^ 7 is 128, which is greater than 120. 120 passes will guarantee that the name is not present in the list. Binary search takes log2 (number of elements) at most to find an item.
• 10
• Yes, you would know by 10 passes, but there is a better answer. Remember that binary search takes log2 (number of elements) passes at most to find an item.
• 12
• Yes, you would know by 12 passes, but not all 12 passes are required. Remember that binary search takes log2 (number of elements) passes at most to find an item.
• 128
• This would be true if the list was searched using sequential search. Binary search only requires log2 (number of elements) at most to find an item.

14-4-16: The method recur is shown below. In which case will recur terminate without error?

public void recur (String str)
{
if (str.length() < 15)
System.out.print("s");

recur(str + "!");
}

• When the length of str is less than 15
• If the string length is less than 15, "s" will be printed, but the recursive call will still be made.
• When the length of str is greater than or equal to 15
• This would be correct if the recursive call was located in an else statement. If the string length is 15 or greater, "s" will not be printed, but the recursive call will still occur.
• When the length of str is equal to 0
• If the string has length 0, the if statement will occur and "s" will be printed, but the recursive call will still occur.
• For all string inputs
• Check the recursive call. The method is always called recursively, regardless of the string length.
• For no string inputs
• There is no base case present in this method that stops the recursive calls. This method will continue until the compiler runs out of memory. You could fix this code by placing the recursive call in an else statement or creating a base case to end the call.

14-4-17: Consider the Fruit, Grape, and SeedlessGrape classes shown below. Which of the following object declarations will compile without error?

public class Fruit
{
private String name;
private boolean seeds;

public Fruit(String theName)
{
name = theName;
seeds = true;
}

public void setSeeds()
{
seeds = !seeds;
}

}

public class Grape extends Fruit
{
private String color;

public Grape(String theName, String theColor)
{
super(theName);
color = theColor;
}
}

public class SeedlessGrape extends Grape
{
public SeedlessGrape(String theName, String theColor)
{
super(theName, theColor);
setSeeds();
}
}

I. Fruit a = new SeedlessGrape("grape", "red");
II. Grape b = new Grape("grape");
III. SeedlessGrape c = new Grape("grape", "green");

• I only
• A SeedlessGrape IS-A fruit, so the inheritance relationship is correct. The constructor for the SeedlessGrape class has two string parameters.
• II only
• The Grape class constructor has two parameters. Although a Grape IS-A fruit, the Grape constructor must have two string parameters to compile without error.
• III only
• A Grape is NOT a SeedlessGrape. The inheritance relationship is incorrect, and III does not compile. Object a is a Fruit at compile-time and a SeedlessGrape at run-time. A SeedlessGrape IS-A Fruit, so the code compiles.

14-4-18: The method printNames is located below. It prints out all the names in a 2-D matrix. Which of the following correctly replaces /* to be determined */ to make the method work as intended?

public void printNames (String[][] arr)
{
for (String[] row : arr)
{
for (String x : row)
{
/* to be determined */
}

System.out.println();
}
}

• System.out.print(arr[x] + " ");
• x refers to a String object, not an index in the array. x can be printed directly, because the second for-loop individually selects Strings in each row of the array.
• System.out.print(x + " ");
• This method uses two for-each loops. The variable x refers to a single String located in the array, so only x needs to be printed. This method will loop through the entire 2-D array, printing out all the names in the matrix.
• System.out.print(x.toString() + " ");
• This will compile without error, but the toString is unnecessary. x is already a String and can be printed directly.
• System.out.print(row[x] + " ");
• x refers to a String object, not an index in the array row. x can be printed directly.
• System.out.print(row.get(x) + " ");
• x is a String, not an index.

14-4-19: Which of the following is equivalent to ! ( (x > 10) && (x <= 5) )?

• (x < 10) && (x > 5)
• Use A and B to represent the expressions -- A becomes (x > 10), B becomes (x <= 5). ! (A && B) is NOT equivalent to (!A && !B). Also, (x < 10) is not correct negation for (x > 10); the correct negation is (x <= 10).
• (x > 10) && (x <=5)
• Use A and B to represent the expressions -- A becomes (x > 10), B becomes (x <= 5). ! (A && B) is NOT equivalent to (A && B).
• (x <= 10) && (x > 5)
• Use A and B to represent the expressions -- A becomes (x > 10), B becomes (x <= 5). ! (A && B) is NOT equivalent to (!A && !B). The AND should be changed to an OR.
• (x <= 10) || (x > 5)
• Use A and B to represent the expressions -- A becomes (x > 10), B becomes (x <= 5). ! (A && B) is equivalent to (!A || !B), according to DeMorgan's principle. The negation of (x > 10) is (x <= 10), and the negation of (x <= 5) is (x > 5).
• (x > 10) || (x <= 5)
• Use A and B to represent the expressions -- A becomes (x > 10), B becomes (x <= 5). ! (A && B) is NOT equivalent to (A || B). Both A and B should also be negated.

14-4-20: Consider the method mystery. What is returned as a result of mystery(4)?

public int mystery (int num)
{
if (num == 1)
return 3;
else
return 3 * mystery (num - 1);
}

• 12
• This would be correct if the recursive method called 3 + mystery (num - 1). Check the recursive call and try again.
• 243
• This method calculates 3 ^ num. 3 ^ 4 is not equal to 243, so check your tracing and try again.
• 81
• This method calculates 3 ^ num. It goes through the recursive calls until num reaches 1, then 3 is multiplied by itself (num) times. The method has been called four times, and 3 ^ 4 is 81.
• 15
• This would be correct if the recursive method called 3 + mystery (num - 1), and num was equal to 5. Check the base case and the parameter and try again.
• 27
• This method calculates 3 ^ num. 3 ^ 4 is not equal to 27, so check your tracing and try again.