# 12.2. Exam 1 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-2-1: Which of the following is equivalent to the statement below? Recall DeMorgan’s Law.

```!((a <= b) && (b < 0))
```
• (a >= b) && (b >= 0)
• The "!" would negate everything inside the parentheses. There are a few mistakes here. The opposite of <= is not >= and the opposite of AND is OR.
• !(a > b) || !(b >= 0)
• Both of the expressions inside the parentheses were altered. If we wanted to distribute the negation symbol "!" then we would leave the expressions inside the parentheses alone.
• (a >= b) || (b > 0)
• Negating less than or equals (<=) results in greater than (>). In addition, less than (<) in the second argument should have been changed to greater than or equals (>=).
• (a > b) || (b >= 0)
• Using DeMorgan's Law we negate everything. This includes our AND statement (which becomes an OR) and everything inside both parentheses.
• (a > b) && (b >= 0)
• Here we forgot to negate our AND (&&) into an OR (||).

14-2-2: Consider the following recursive method. What does `mystery(4)` return?

```public int mystery(int m)
{
if (m == 1)
{
return 3;
} else
{
return 3 * mystery(m - 1);
}
}
```
• 9
• This would be true if we called mystery(2).
• 81
• The argument is 4 so will have 4 recursive calls and then return 3 when we get to mystery(1). Each call will multiply our result by 3, so you can think of this as 3 raised to the 4th power (or 3 * 3 * 3 * 3 = 81).
• 3
• This value is returned when we call mystery(1), since 1 is the base case and doesn't result in a recursive call.
• 243
• This value would be returned from mystery(5).
• 27
• This value would be returned from mystery(3).

14-2-3: In which of these cases will an ascending order (from smallest to largest) insertion sort have the fastest run time?

```I.   An array that is in reverse order (from largest to smallest).
II.  An array that is in sorted order already (from smallest to largest).
III. An array that is in random order (not already sorted).
```
• II only
• If an array is already sorted from smallest to largest then we do not need to move anything in the array and we would only need to go through each element at most once, so this is fastest run time for insertion sort.
• I only
• An array in reverse order is actually the worst run time for insertion sort because we would need to move everything to make it in order from smallest to largest.
• I and II only
• II is correct, but number I will actually be the worst run time for insertion sort since all values will have to be moved each time through the loop.
• II and III only
• While II is the correct anwser, an array in random order will have average run time.
• III only
• When the array is not sorted the run time will be average.

14-2-4: Which of these loops will output `01234`?

```int max = 5;

//Loop I
for (int i = 0; i < max; i++)
{
System.out.print(i);
}

//Loop II
int j = 0;
while (j < max)
{
System.out.print(j);
j++;
}

//Loop III
int k = 0;
for (int i = max; i > 0; i--)
{
System.out.print(i);
}
```
• I only
• Loop I will produce this output, but it is not the only loop that will output these values.
• II only
• Loop II will produce this output, but it is not the only loop that will output these values.
• II and III only
• Loop II is correct, but loop III will produce the reverse output, 43210.
• I and II only
• Both of these loops will have the correct output. They iterate (and print each value) starting from 0 until the max value which we defined earlier in our code.
• I, II, and III
• While loop I and II will produce the correct output, loop III will actually produce the reverse of the correct output.

14-2-5: Consider the following block of code. What are the first and last numbers printed after running the code?

```int value = 15;
while (value < 30)
{
value++;
System.out.println(value);
}
```
• First: 15 Last: 29
• We add 1 to value before actually printing it, so the first value printed will be 16. The last time through the loop the value will be 29 (less than 30) but then the code will add one so it will print 30.
• First: 15 Last: 30
• We add 1 to value before actually printing it, so the first value printed will be 16.
• First: 16 Last: 29
• The last time through the loop the value will be 29 (less than 30) but then the code will add one so it will print 30.
• First: 16 Last: 30
• The code adds one to value before the value is printed so 16 will be the first value printed. The last time through the loop the value will be 29 (less than 30) but then the code will add one so it will print 30.
• First: 16 Last: 28
• The last time through the loop the value will be 29 (less than 30) but then the code will add one so it will print 30.

14-2-6: Consider the following block of code. What value is returned from `solution(5)`?

```public int solution(int limit)
{
int s = 0;

for (int outside = 1; outside <= limit; outside++)
{
for (int middle = 1; middle <= limit; middle++)
{
for (int inside = 1; inside <= limit; inside++)
{
s++;
}
}
}
return s;
}
```
• 25
• This would be correct if we only had one inner for loop, but there are two.
• 15
• The outer loop will execute 5 times, each time the outer loop executes the middle loop will execute 5 times, and each time the middle loop executes the inner loop will execute 5 times. So the answer is 5 * 5 * 5 = 125.
• 125
• The number of times a loop executes is (largest value in loop - smallest value in loop + 1) each loop executes (5 - 1 + 1 = 5) times. When you have nested loops you multiply the number of times each loop executes. So the result is 5 for the outer loop * 5 for the middle loop * 5 for the innermost loop.
• 64
• This would be correct if we called solution(4) or the conditions to stop each loop were just less than, and not less than or equal to.
• 625
• If you got this value you probably made one extra call to the each of the loops, notice that the loops start at 1 and not 0.

14-2-7: Given that both `count` and `n` are integer values, which of the following statements is true about both code blocks?

```// Code block I
for (count = 0; count <= n; count++)
{
System.out.println(count);
}

//Code block II
count = 0;
while (count <= n)
{
count = count + 1;
System.out.println(count);
}
```
• I and II are exactly equivalent for all input values n.
• I and II will never be equivalent because because count is incremented after it is printed in Code block I and before it is printed in Code block II.
• I and II are only equivalent when n is an even number.
• I and II are not equivalent when n is even.
• I and II are only equivalent when n = 0
• When n = 0, Code block I will print out 0, while Code block 2 will print out 1.
• I and II are equivalent for all values except when n = 0
• The code blocks never output the same value.
• I and II are never going to have the exact same outputs.
• I and II will never be equivalent because count is incremented after it is printed in Code block I and before it is printed in Code block II.

14-2-8: Consider the following class declarations. Which statements are true?

``` public class Animal
{
/* Some code */
}

public class Cat extends Animal
{
/* Some code */
}

I. Cat inherits the constructors of Animal
II. Cat cannot add new methods and private instance variables that Animal does not have.
III. Cat can override existing public methods of Animal
```
• I only
• A subclass needs to specify its own constructors.
• II only
• A subclass has the ability to add new methods and variables that are unique to it (meaning its parent class dosen't contain them)
• III only
• Subclasses can overide public methods from their parent classes to specialize behavior.
• I and II
• Neither of these statements are true.
• II and III
• Statement III is correct, but not statement II.

14-2-9: Consider the following code. What is the maximum amount of times that `HELLO` could possibly be printed?

```for (int i = 0; i <= k; i++)
{
if (arr[i] < someValue)
{
System.out.print("HELLO")
}
}
```
• k
• This would be the case if i had the initial value 1 and arr[i] < someValue would be true for all i values.
• k + 1
• If arr[i] < someValue for all i from 0 to k, HELLO will be printed on each iteration of the for loop. The number of times a loop executes is the biggest value in the loop - the smallest value in the loop + 1 (k - 0 + 1 is k + 1).
• k - 1
• This would be the case if i had the initial value 2 and arr[i] < someValue would be true for all i values.
• 1
• This would be the case if only one element in the array would fulfill the condition that arr[i] < someValue.
• 0
• This is the minimum number of times that HELLO could be executed.

14-2-10: When will the method `stringRecursion` produce a run time error?

```public void stringRecursion(String s)
{

if (s.length() < 16)
{
System.out.println(s);
}
stringRecursion(s + "*");
}
```
• It will never produce a run time error.
• Since there is no terminating condition surrounding our recursive method call (because the call lies outside of the if statement), it will keep doing recursive calls until we eventually get a run time error.
• It will always produce a run time error.
• Since there is no statement that terminates the recursive call to stringRecursion (the length of the string s will increase until it is greater than 16, but the recursive call will keep happening because the recursive call is outside the if statement) the computer will keep doing recurisve calls until it runs out of memory and a run time error will happen.
• Only when the length of the input string is greater than or equal to 16.
• Since the recursive call is outside the condition and the conditional doesn't include a return then this will result in infinite recursion and eventually a run time error.
• Only when an empty string is input.
• The length of the string will not matter in this case because the recursive call to stringRecursion will always happen, since the recursive call lies outside the body of the conditional. The string length will only determine if the string s is printed out to the console or not.
• Whenever the input string length is less than 16.
• We will get run time errors regardless of the length of the string s. This is due to the fact that the recursive call lies outside the body of the conditional. If the length of the string s is less than 16 then we will get something printed out to the console until the length of s becomes greater than 16, and then we will continue in a infinite recursion.

14-2-11: Consider the following interface and class definitions. Which of I, II and III below would cause an error when used in place of the missing code in the main method?

```public interface A
{
public abstract void method1();
}

public class B implements A
{
// Instance variables and other methods not shown

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

public class C extends B
{
//Instance variables and other methods not shown

public void method2(C o)
{
/* implementation not shown */
}

public static void main(String[] args)
{
C objectC = new C();
B objectB = new B();
// Missing code
}
}

I objectC.method1();
II objectB.method2(objectC);
III objectC.method2(objectB);
```
• I only
• This method call compiles because class C inherits all the public methods in class B. This will not produce an error.
• II only
• Method II will produce a compile time error because class B (the superclass) does not inherit the methods of class C due to the fact that class C is its subclass. But, it is not the only call that will result in a compile time error.
• II and III only
• Method II will produce a compile time error because class B (the superclass) does not inherit the methods of class C due to the fact that class C is its subclass. Method III will produce an error because of the parameter it takes in. objectB is not a class C type object which is what the method definition for method III required.
• III only
• This method produces a compile time error, but method II will also produce a compile time error.
• I, II and III
• Methods II and III will both produce compile time errors, but method I works because class C inherits all the public methods of class B.

14-2-12: Which of these declarations will not cause an error?

```I ArrayList<String> stringList = new List<String>();
II List<int> intList = new ArrayList<int>();
III List<String> stringList = new ArrayList<String>();
```
• I only
• Because List is an abstract class you can not create a new object of the type List.
• II only
• The type parameter in a generic ArrayList must be a class type, not a primitive type. int is a primitive type.
• III only
• Since an ArrayList is a List (implements the List interface), we can declare an ArrayList object as a List object. This is called upcasting since we are casting it to the parent type.
• II and III
• III is correct, but II will cause a compile time error since we cannot use a primitive (int) as the type parameter in a generic ArrayList.
• I and II
• Both of these solutions will cause an error.

14-2-13: What of the following is true about class `A` below?

```public abstract class A
{
public int v1;
public int v2;

//methods of the class
}
```
• In a program that uses A, more than one instance (object) of type A can be created.
• Instances of abstract classes cannot be created.
• If a program has an object of type A that it calls methods on, then the class A must have a subclass that is not abstract.
• Abstract classes can not be instantiated, so if a program has an object of type A the class A must have a subclass that is not abstract.
• The class A needs to have a constructor that takes two parameters in order to initialize v1 and v2.
• The fields v1 and v2 could be initiliazed in a default constructor that takes in no parameters.
• Any program that uses class A will have an error since abstract classes cannot contain public instance variables.
• An abstract class can contain any number of public, private, and protected instance variables.
• One or more methods in A must be declared abstract.
• The purpose behind abstract classes is having a class that cannot be instantiated. An abstract class is not required to have any abstract methods.

14-2-14: Suppose that the following method takes in a two dimensional array called `matrix`. After the method call `printMatrix(matrix)` what will the output be? Possible options are listed below the method definition.

```/* assume that matrix has the following values */
7654
3210
4567
0123

public static void printMatrix(int[][] matrix)
{
for (int i = 0; i < matrix.length; i++)
{

for (t = 0; t < i; t++)
{
System.out.println(matrix[i][t]);
}
System.out.println();
}
}

Possible output:

I.
7654
3210
4567
0123

II.
7
32
456
0123

III.
3
45
012

IV.
7
3
4
0
```
• I
• Since the inside for loop starts with t = 0 and continues while t < i (and i begins at 0) it will not be print out every single element of the 4x4 matrix.
• II
• This anwser is not correct because our inside for loop will start with t = 0 and loop while t < i and, as such, the entire first row of our matrix will be ignored, since both t and i = 0 and t is not less than i.
• III
• When i = 0, the inner for loop does not get executed and the entire first row of the matrix is ignored. When i = 1 t goes from 0 to 0 and the element matrix will be printed out. Similarly, when i = 2 we will print out elements matrix and matrix. Finally, when i = 3, we will print out matrix, matrix and matrix.
• IV
• This would be the correct anwser if we kept incrementing i by one (the outer for loop) but the inner for variable t would always be 0. We would get the first element of each row.
• An ArrayIndexOutOfBoundsException will be thrown.
• We will not get an index out of bounds exception since we made sure to increment i only until the max length of the array and the other variable we use to index, t, will only increase while it is still less than i.

14-2-15: If randomList is an `ArrayList` of `Integer` objects and is initially set to {0, 1, 2, 3}, what will randomList look like after the following code is executed?

```randomList.add(5);
int randomNum = randomList.get(2);
randomList.remove(2);
randomList.set(1, 8);
```
• [0, 1, 2, 3, 5, 7]
• This is what the ArrayList will look like after the first two operations in the code.
• [0, 1, 4, 3, 5, 7]
• This is what the ArrayList will look like before we set the element at index 1 to be 8.
• [0, 8, 3, 4, 5, 7]
• This is what would have happened if we thought randomNum was actually 3 and we added the number 4 at the incorrect index.
• [0, 8, 4, 3, 5, 7]
• After we add 5 and 7 to the end of the array we remove the element at index 2 (which was 2). Then we use the index we had previously obtained (also 2) to add a new element 4. This pushes the element already at that index (and the ones after it) one space to the right. Fianlly, we set the element at index 1 to be 8. This sets the value at index 1 to 8.
• [5, 7, 0, 8, 4, 3]
• This is what we would have happened if we thought the add method would add elements to the beggining of the ArrayList and not the end.

14-2-16: Consider the following code segment. What will be printed as a result of executing the code below?

```String str = "fedcba";
int counter = 0;
while(counter < str.length() - 1)
{
System.out.print(str.substring(counter + 1, counter + 2));
counter++;
}
```
• edcba
• The substring method takes two arguments, a start index (which is inclusive) and an end index (which is exclusive). The first substring is from index 1 (counter + 1) to index 2 (counter + 2). However the second index is not included so its just index 1 which is e. We then simply keep getting every indidual element from the string one by one until the end of the string.
• edcb
• This substring is mostly correct but it ends early and is missing the a character at the end.
• Nothing is printed because an IndexOutOfBoundsException is thrown.
• Even though the end of the substring is specified as index counter + 2, which will be past the end of the string the last time through the loop, substring doesn't include the value at the end index, so the code will execute.
• feeddccbba
• The first substring element has a start value of index 1 and so f will not be printed out. Also because each substring is a single character, no character will be repeated in the substring.
• fededcdcbcba
• This is what we would have happened if the substring had started at index counter (and not index counter + 1).

14-2-17: Consider the following class declarations. Which of the following statements will not compile?

```public class B
{

public int myValue;

public B()
{
myValue = 0;
}

public B(int x)
{
myValue = x;
}
}

public class C extends B
{

public C()
{
super(0);
}
}
```
• C c1 = new C();
• Here we are simply creating a new instance of class C by calling the appropiate constructor. Nothing is wrong here.
• B b1 = new B();
• Here we are simply creating a new instance of class B by calling the appropiate constructor. Nothing is wrong here.
• B c2 = new C();
• Since class C is a subclass of class B, you can upcast an object of type C to be of type B.
• B b3 = new B(10);
• This statement is creating a new object using the second constructor of the B class. This is also a valid way to create a B object.
• C c3 = new C(24);
• Even though class C has a super class with a constructor that takes in a single int argument, class C does not have a constructor that takes an int value.

14-2-18: Consider the following method. Assume that `String s = "rain";` and `int b = 4;` have been executed. What are the values of `s` and `b` after `test(s,b)` is executed?

```public static void test(String str, int y)
{
str = str + "bow";
y = y * 2;
}
```
• s="rainbow"; b=8;
• Strings are immutable so changing str doesn't affect the string that s refers to. The value of b also will not change since Java passes a copy of the value.
• s="rain"; b=8;
• Java copies the value of primitive types when they are passed to methods so nothing done in the method test affects the value of b.
• s="rainbow"; b=4;
• Strings are immutable so changing str doesn't affect the string that s refers to.
• s="rain"; b=4;
• Since strings are immutable any change returns a new string and doesn't affect what s refers to. Also the value of primitive types are copied and nothing done in test affects the orignal primitive value.
• s="bow"; b=4;
• The string that s refers to is not changed by the test method. All changes to string result in a new string object.

14-2-19: Which of the following is/are true about using insertion sort versus using merge sort?

```I. Insertion sort requires more storage space than mergesort.
II. Insertion sort is only more efficient than mergesort in the case that we have a very small and nearly sorted array.
III. Insertion sort is almost always less efficient than mergesort.
```
• I only
• Merge sort often uses a temporary array when merging arrays, which means it actually uses more storage space than insertion sort.
• II only
• Insertion sort is more efficient for a small array because merge sort has extra overhead from the recursive function calls that cause it to take longer.
• III only
• Merge sort uses the "divide and conquer" approach to sort an array. This will end up being more efficient than insertion sort in the case where we have a long unordered array.
• I and III
• Statement III is true but statement I is false since mergesort often utilizes a temporary array and will actually require more storage space than insertion sort.
• II and III
• Merge sort uses the "divide and conquer" approach to sort an array. This will end up being more efficient than insertion sort in the case where we have long unordered array. However if we have a very small almost sorted array, then insertion sort will outperform merge sort.

14-2-20: What would the contents of `matrix`, a 2-D array of integers, be after a call to `alter(1)`? The method alter is defined below.

```  private int[][] matrix;

/* matrix looks like this initially
1 3 5 7
2 4 6 8
3 5 7 9
*/

public void alter(int c)
{
for (int i = 0; i < matrix.length; i++)
{
for (int j = c + 1; j < matrix.length; j++)
{
matrix[i][j - 1] = matrix[i][j];
}
}
}

I. 1 7 7 7
2 8 8 8
3 9 9 9

II. 1 5 7
2 6 8
3 7 9

III. 1 3 5 7
3 5 7 9

IV. 1 3 5 7
3 5 7 9
3 5 7 9

V. 1 5 7 7
2 6 8 8
3 7 9 9
```
• I
• The method alter shifts the values in the columns starting at column c + 1 and shifting back to entry to the left of c + 1. This matrix is what would result if c was three and we were shifitng the number there to the two spots before it.
• II
• Although some numbers are overwriten in the matrix, the matrix will still be 3x4 matrix.
• III
• Although some numbers are overwriten in the matrix, the matrix will still be 3x4 matrix.
• IV
• This is what would happen if we were shifting rows instead of columns in the alter method.
• V
• Method alter shifts the values in the columns, starting at column c + 1, one column to the left. It also overwrites column c. Here are the replacements made for the method call alter(1): matrix = matrix, matrix = matrix, matrix = matrix, matrix = matrix, matrix = matrix, matrix = matrix