AP Computer Science Unit 10 Test Project Stem

Which of the following is not a step in the merge-sort algorithm?

Merge all the smaller arrays together

simultaneously into one large array

The smaller arrays are merged in pairs, not all at once.

When you pass an int variable to a method, the method receives ______.

➜ a copy of the variable

int is a primitive data type. And when a primitive data type

variable is passed into a method as a parameter, a copy of it is

made. So any changes made to the variable within the method are made to the copy and do NOT affect the original.

public static void recurMethod(String str)

{

if (str.length() > 1)

{

recurMethod(str.substring(1, str.length() - 1));

}

System.out.println(str);

}

Which of the following is printed as a result of the call recurMethod("program")?

g

ogr

rogra

program

This is correct. Each time recurMethod is called, it calls itself with the same string parameter with the

first and last character removed until the length is smaller than 2. After this the method stops calling

itself and moves on to the last line which prints the string parameter. This completes with the final call

of the method first (with parameter "g"), then continues with each previous call until the original (with

parameter "program") is complete.

Consider the following recursive method.

public static void wackyPrinter(String str)

{

if (str.length() < 10)

{

wackyPrinter("!" + str + "!");

}

else

{

System.out.println(str);

}

}

What will be printed as a result of the call wackyPrinter("cpu")?

!!!!cpu!!!!

This is correct. The method checks whether the length of str is

smaller than 10. If it is, then the method is called again with a new

parameter which is formed by joining a "!" both before and after

the string from the previous call. This continues until the

parameter is no longer smaller than 10, at which point it is printed.

The parameters passed to the method in order are therefore cpu,

!cpu!, !!cpu!!, !!!cpu!!!, !!!!cpu!!!!, and only the last of these has a

length smaller than 10 and is printed as a result.

Which method(s) would produce the following output if they were passed the parameter, "hamster"?

hamster

hamste

hamst

hams

ham

ha

h

public static void mystery(String wo)

{

System.out.println(wo);

if (wo.length() > 1)

{

mystery(wo.substring(0, wo.length() - 1));

}

}

I only ➜ In choice II the word is printed after the recursive call so the printed words would

be in the opposite order. In choice III the recursive call is just a substring of the last

character of the string. Choice I works because the method prints the string, then

calls itself with the same string with the last letter cut off.

You need to search an unordered list of fifteen students for the student id #1124. Which search would be most effective?

linear

A binary search only works on ordered lists, so the only alternative is to use

a linear/sequential search.

int list [] = / missing code /;

int val = / missing code /;

int n = -1;

for (int i = 0; i < list.length; i++)

{

if (val == list[i])

{

n = i;

break;

}

}

What algorithm is shown?

Linear Search

The elements in the array are iterated through in order and checked to see

if they are equal to val. This is how a linear search works.

public static int goRound(int num)

{

if (num < 100)

{

return 10 * ((num + 5) / 10);

}

return 10 * goRound(num / 10);

}

What is returned as a result of the call goRound(56348)?

60000

➜ This is correct. This method effectively rounds positive integer values to 1

significant figures. The initial call is goRound(56348). This has a return of

10goRound(5634) = 1010goRound(563) = 101010goRound(56). The call

goRound(56) has a return of 10(56+5)/10 = 1061/10 = 10*6 = 60. Therefore the value

returned by the initial call is 101010*60 = 60000.

Consider the following recursive method:

public static int recur(int x)

{

if (x >= 0)

{

return x + recur(x - 1);

}

return 0;

}

What is returned by the method call recur(9)?

45

This method sums x with the value of the method called with a value one smaller

until x is 0. This means the method sums all the ints from the initial value of x to 0 and

9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45.

Questions 10-11 refer to the following information.

Consider the following instance variable and methods. You may assume that word has been initialized as a String

with length greater than 0. The methods are intended to return true if a character appears twice in a row in word;

false otherwise.

private String word;

public boolean hasRepeat()

{

return hasRepeatHelper(word.length() - 1);

}

private boolean hasRepeatHelper(int pos)

{

// Missing line

String letter1 = word.substring(pos-1,pos);

String letter2 = word.substring(pos, pos+1);

if (letter1.equals(letter2))

return true;

else

return hasRepeatHelper(pos - 1);

}

10. For which of the following values of word, will the call hasRepeat result in an error?

I. "aadvark"

II. "mississippi"

III. "repeat"

Three only

➜ This is correct. The value "aadvark" will not cause an error. The recursive

method hasRepeatHelper will be called 6 times in total, and the sixth of these

calls, with an argument of 1 will return true. The value "mississippi" will not

cause an error. The recursive method hasRepeatHelper will be called twice, and

the second of these calls, with an argument of 9 will return true. The value

"repeat" will cause an error. The recursive method hasRepeatHelper will be

called 6 times in total, and the sixth of these calls, with an argument of 0 will

cause an IndexOutOfBoundsException to be thrown.

Which of the following should be used to replace // Missing line in hasRepeatHelper so that hasRepeat

will work as intended?

if (pos < 1)

{

return false;

}

This is correct. The method hasRepeat calls hasRepeatHelper with an initial value of pos as word.length -

1. The helper method checks if the characters at pos and pos-1 are equal, and returns true if so.

Otherwise it calls itself with a value of pos-1. When the value of pos is 0 or smaller the character at pos-1

does not exist. So since no repeats have been found up to this point the method should return false.

Which of the following are real advantages of using the merge-sort algorithm?

I. It is very easy to code

II. It is very fast for large data sets

III. It uses no memory if coded correctly

Two only

The merge-sort algorithm is quite challenging to code, but is fast when used on

large data sets. All algorithms require memory use when they are implemented in code.

13. Consider the following recursive method.

public static String recur(int val)

{

if (val == 0)

{

return "";

}

if (val % 2 == 0)

{

return recur(val / 2) + "f";

}

else

{

return recur(val / 2) + "t";

}

}

What is printed as a result of executing the statement System.out.println(recur(13))?

ttft

➜ This is correct. The first call, recur(13) returns the value recur(6) + "t". By evaluating the call recur(6) we see that recur(13) is

equivalent to recur(3) + "f" + "t". Subsequent evaluations of the

calls give this as equivalent to recur(1) + "t" + "f" + "t", which is

equivalent to recur(0) + "t" + "t" + "f" + "t" which is equivalent to

"" + "t" + "t" + "f" + "t". Therefore the final string returned is ttft.

Consider the following recursive method.

/* Precondition: num > 0 /

public static int mystery(int num)

{

if (num % 2 == 1)

{

return 1;

}

else

{

return 2 * mystery(num / 2);

}

}

Assume that int x has been declared and initialized with a value that satisfies the precondition of the method.

Which of the following best describes the value returned by the call mystery(x)?

➜ The largest power of 2 which divides x evenly

This is correct. The effect of this method is to call itself with a

parameter which is half its value if it can be divided by 2. The result

from this call is multiplied by 2. In total, including the original call,

the method is called one more time than the number of times the

original parameter can be divided by 2 evenly. The final call returns a

value of 1, and each return is then multiplied by 2. This means 2 is

multiplied by itself the number of times that the original number can

be divided by 2. This gives the

public static int mystery( int [] list, int val)

{

int n = -1;

int max = list.length - 1;

int min = 0;

int mid = 0;

while (max > min)

{

mid = (max + min) / 2;

if (list[mid] == val)

{

n = mid;

break;

}

if (list[mid] > val)

{

max = mid-1;

}

else

{

min = mid+1;

}

}

return n;

}

What algorithm is this an implementation of?

Binary Search

A midpoint of the remaining array is compared to val, and if it does not

match then one half of the array is specified and the process repeats

itself. This is how a binary search algorithm works on an ordered array.

Consider the following recursive method.

public static void doWhat(int num)

{

if (num < 15)

{

doWhat(num + 4);

System.out.print(num + " ");

}

}

What is printed as a result of the call doWhat(2)?

14 10 6 2

This is correct. When the method doWhat is called, it checks if the condition

num < 15 is satisfied, where num is the parameter it was called with. If this is

satisfied it then calls doWhat again with a parameter which is 4 greater. This

call must complete before the rest of the method continues. Therefore

successive calls doWhat(2), doWhat(6), doWhat(10), doWhat(14), doWhat(18)

are made. On the final of these calls num < 15 is no longer satisfied so that call

completes. The call doWhat(14) can then complete, printing "14 ", then

doWhat(10), doWhat(6) and doWhat(2), thus in order, 14 10 6 2 is printed.

17. The two methods below are intended to implement the merge sort algorithm when used in conjunction.

/** Main method to sort an array of ints.

* @param arr the array to be sorted

* @return an array with the same contents as arr, sorted in

* increasing order

*/

public static int[] mergeSort(int[] arr)

{

// Base case: if list length is 1 then it is already sorted

if (arr.length <= 1)

{

return arr;

}

// Split list into two half-lists

int[] lowerHalf = new int[arr.length / 2];

int[] upperHalf = new int[(arr.length + 1) / 2];

for (int i = 0; i < lowerHalf.length; i++)

{

lowerHalf[i] = arr[i];

}

for (int i = 0; i < upperHalf.length; i++)

{

upperHalf[i] = arr[i + arr.length / 2];

}

return / missing expression /;

}

/** Helper method which merges two ordered arrays of ints

* @param arr1 the first ordered array

* @param arr2 the second ordered array

* @return an array containing contents of both arr1 and arr2,

* sorted i

merge(mergeSort(lowerHalf), mergeSort(upperHalf))

The individual halves of the list will be sorted, then merged together to create one sorted list. This will be

done recursively (i.e. lowerHalf and upperHalf will themselves be sorted by the same process).

Consider the following recursive method.

public int recur(int x)

{

if (x > 10)

{

return 2 * recur(x / 2);

}

if (x < 10)

{

return recur(x + 2) / 2;

}

return 10;

}

What value is returned as a result of the call recur(12)?

4

This is correct. The call recur(12) returns the value 2*recur(6). The call

recur(6) returns the value recur(8) / 2. The call recur(8) returns the value

recur(10) / 2. As the call recur(10) returns 10, the call recur(8) returns 10 /

2 = 5, the call recur(6) returns 5 / 2 = 2, and the call recur(12) returns 2 * 2 =

4.

Consider the following recursive method.

public static void mystery(String s)

{

if (s.length() > 2)

{

mystery (s.substring(0,s.length() / 2));

mystery (s.substring(s.length() / 2));

}

else

{

System.out.println(s);

}

}

What is printed as a result of the call mystery("method")?

m

et

h

od

This is correct. The initial call, with s equal to "method" results in two calls to mystery, one with s equal

to "met", and one with s equal to "hod". The first of these runs first and results in two further calls to

mystery, with s equal to "m", and s equal to "et". Each of these strings is printed in the order called, as

both are under length 2. The call to mystery with s equal to "hod" runs next: this creates another two

calls to mystery, with s equal to "h", and s equal to "od", and once again these are both printed in that

order.

Consider the following instance variable and method.

private ArrayList vals;

// vals is sorted into increasing order

public void binaryInsert(int num)

{

int low = 0;

int high = vals.size();

while (high > low)

{

int mid = (low + high) / 2; / calculate midpoint /

if (vals.get(mid).intValue() < num)

{

low = mid + 1;

}

else

{

high = mid;

}

}

vals.add(low,new Integer(num)); / insert new number /

}

The binaryInsert method creates and inserts an Integer element into the correct position of the list vals which is

sorted into increasing order. Suppose vals contains the following Integer values: [2, 3, 4, 4, 4, 8], and that the following command is executed:

binaryInsert(4);

What will be the value of low when the line marked / insert new number / in the binaryInsert method is executed?

2

This is correct. On the first pass of the while loop, the value of mid is set to 3. The element

at this index is not smaller than 4, so the value of high is set to mid, which is 3. The second

pass the value of mid is set to 1. The element at this index is smaller than 4, so the value of

low is set to mid + 1, which is 2. The third pass of the loop the value of mid is set to 2. The

element at this index is not smaller than 4, so the value of high is set to mid, which is 2. At

this point the values of high and low are the same, so the loop exits. The value of low is at this

point equal to 2, so this is the index at which the new element is inserted.