AP Computer Science Chapter 6 (MC)

For questions 1-4, assume values is an int array that is currently filled to capacity, with the following values:

1) What is returned by values[3]?

a) 9

b) 12

c) 2

d) 6

e) 3

c

Explanation: Java array indices start at 0, so values[3] is really the fourth array element, which is 2.

2) What is the value of values.length?

a) 0

b) 5

c) 6

d) 7

e) 18

d

Explanation: The length operator for an array returns the size of the array. The above picture shows that

that values stores 7 elements and since it is full, the size of values is 7.

3) Which of the following loops would adequately add 1 to each element stored in values?

a) for(j=1;j

B

Explanation: The first array element is values[0], so the for-loop must start at 0, not 1. There are

values.length elements in the array where the last element is at values.length-1, so the for loop must stop before

reaching values.length. This is the case in b. In d, the for loop stops 1 before values.length since "<" is being used to

test the condition instead of <=.

4) The statement System.out.println(values[7]); will

a) output 7

b) output 18

c) output nothing

d) cause an ArrayOutOfBoundsException to be thrown

e) cause a syntax error

D

Explanation: The array has 7 values, but these are indexed values[0] to values[6]. Since values[7] is

beyond the bounds of the array, values[7] causes an ArrayOutOfBoundsException to be thrown.

5) Which of the following is a legal way to declare and instantiate an array of 10 Strings?

a) String s = new String(10);

b) String[10] s = new String;

c) String[ ] s = new String[10];

d) String s = new String[10];

e) String[ ] s = new String;

9 4 12 2 6 8 18

C

Explanation: Declaring an array is done by type[ ] variable. Instantiating the array is done by variable =

new type[dimension] where dimension is the size of the array.

6) In Java, arrays are

a) primitive data types

b) objects

c) interfaces

d) primitive data types if the type stored in the array is a primitive data type and objects if the type stored

in the array is an object

e) Strings

B

Explanation: In Java, arrays are implemented as objects. The variable is a reference variable to the block

of memory that stores the entire array. However, arrays are accessed using the notation name[index] rather than by

message passing

7) The "off-by-one" error associated with arrays arises because

a) the first array index is 0 and programmers may start at index 1, or may use a loop that goes one index

too far

b) the last array index is at length + 1 and loops may only iterate to length, missing one

c) the last array element ends at length - 1 and loops may go one too far

d) programmers write a loop that goes from 0 to length - 1 whereas the array actually goes from 1 to

length

e) none of the above, the "off-by-one" error has nothing to do with arrays

A

Explanation: The array is initialized as = new type[x] where x is the size of the array. However, the array

has legal indices of 0 to x - 1 and so, programmers are often off-by-one because programmers will write code to try to

access indices 1 to x.

8) What does the following code do? Assume list is an array of int values, temp is some previously initialized int

value, and c is an int initialized to 0.

for(j=0;j

D

Explanation: The statement if(list[j]

9) Which of the following lists of numbers would accurately show the array after the first pass through the Selection

Sort algorithm?

a) 9, 4, 12, 2, 6, 8, 18

b) 4, 9, 12, 2, 6, 8, 18

c) 2, 4, 12, 9, 6, 8, 18

d) 2, 4, 6, 8, 9, 12, 18

e) 2, 4, 9, 12, 6, 8, 18

C

Explanation: On each successive pass of Selection Sort, the smallest of the unsorted values is found and

swapped with the current array index (where the current index starts at 0 and goes until the second to last position in the array). On the first pass, the smallest element, 2, is swapped with index 0, so 2 and 9 swap places.

9 4 12 2 6 8 18

10) Which of the following lists of numbers would accurately show the array after the second pass of the Selection Sort

algorithm?

a) 9, 4, 12, 2, 6, 8, 18

b) 2, 4, 9, 6, 12, 8, 18

c) 2, 4, 12, 9, 6, 8, 18

d) 2, 4, 6, 8, 9, 12, 18

e) 2, 4, 12, 6, 8, 9, 18

C

Explanation: After one pass, the array would be 2, 4, 12, 9, 6, 8, 18. The second pass would look to swap the item in array index 1 (4) with the smallest value after 2 (4). So, 4 would swap with 4 and the array would stay the same as it was after the first pass.

11) Which of the following lists of numbers would accurately show the array after the fourth pass of the Selection Sort

algorithm?

a) 9, 4, 12, 2, 6, 8, 18

b) 2, 4, 6, 9, 12, 8, 18

c) 2, 4, 6, 8, 9, 12, 18

d) 2, 4, 6, 9, 8, 12, 18

e) 2, 4, 6, 8, 12, 9, 18

E

Explanation: The array would be sorted as follows: First pass: 2, 4, 12, 9, 6, 8, 18. Second pass: 2, 4, 12,

9, 6, 8, 18. Third pass: 2, 4, 6, 9, 12, 8, 18. Fourth pass: 2, 4, 6, 8, 12, 9, 18.

12) How many passes will it take in all for Selection Sort to sort this array?

a) 2

b) 4

c) 5

d) 6

e) 7

D

Explanation: The Selection Sort uses two for-loops where the outer loop iterates through each array index except for the last one. So it makes a total of n - 1 passes where n is the number of items in the array. Since this array has 7 elements, the outer loop iterates 6 times, or requires 6 passes. You might notice that in fact this array is sorted after only 5 passes, but the Selection Sort algorithm will still make 6 passes (even if the array had been sorted after only 1 pass, it would still make 6 passes!)

For questions 13 - 15, assume an int array, candy, stores the number of candy bars sold by a group of children where

candy[j] is the number of candy bars sold by child j. Assume there are 12 children in all.

13) What does the following code do?

int value1 = Keyboard.readInt( );

int value2 = Keyboard.readInt( );

bars[value1] += value2;

a) adds 1 to the number of bars sold by child value1 and child value2

b) adds 1 to the number of bars sold by child value1

c) adds value1 to the number of bars sold by child value2

d) adds value2 to the number of bars sold by child value1

e) inputs a new value for the number of bars sold by both child value1 and child value2

D

Explanation: bars[value1] is the number of bars sold by child value1, and += value2 adds to this value the

amount input for value2.

For questions 13 - 15, assume an int array, candy, stores the number of candy bars sold by a group of children where

candy[j] is the number of candy bars sold by child j. Assume there are 12 children in all.

14) Which of the following code could be used to compute the total number of bars sold by the children?

a) for(int j=0; j<12; j++) sum+= candy[j];

b) for(int j=0; j<12; j++) candy[j] = sum;

c) for(int j=0; j<12; j++) sum = candy[j];

d) for(int j=0; j<12; j++) sum += [j];

e) for(int j=0; j<12; j++) [j] += sum;

A

Explanation: The code in a iterates through all 12 elements of candy, adding each value to sum. The answer in b sets all 12 elements of candy equal to sum, the answer in c sets sum to be each element of candy, resulting in sum = candy[11] and d and e have syntactically invalid code.

For questions 13 - 15, assume an int array, candy, stores the number of candy bars sold by a group of children where

candy[j] is the number of candy bars sold by child j. Assume there are 12 children in all.

15) What does the following method do?

public int question15( )

{

int value1 = 0;

int value2 = 0;

for(int j=0; j<12; j++)

if(candy[j] > value1)

{

value1 = candy[j];

value2 = j;

}

return value2;

}

a) It returns the total number of candy bars sold

b) It returns the total number of children who sold 0 candy bars

c) It returns the total number of children who sold more than 0 candy bars

d) It returns the number of candy bars sold by the child who sold the most candy bars

e) It returns the index of the child who sold the most candy bars

E

Explanation: The loop iterates through all 12 array elements. If a particular value of candy is found to be larger than value1, then this new value is remembered in value1 along with the index of where it was found in value2.

As the loop continues, if a new candy value is found to be greater than the current value1, then it is remembered instead, so the loop finds the maximum number of candy bars sold in value1 and the child's index who sold the most in value2. Since value2 is returned, the code returns the index of the child who sold the most.

16) We compare sorting algorithms by examining

a) the number of instructions executed by the sorting algorithm

b) the number of instructions in the algorithm itself (its length)

c) the types of loops used in the sorting algorithm

d) the amount of memory space required by the algorithm

e) whether the resulting array is completely sorted or only partially sorted

A

Explanation: Different sorting algorithms require a different number of instructions when executing. The

Selection Sort for instance usually requires more instructions than the Insertion Sort. So, we compare sorting

algorithms by the number of instructions that each takes to execute to sort the array. We might count the maximum

number of instructions that a sorting algorithm will execute in the worst case, or the minimum number in the best case,

or count on average the number of instructions executed. If two sorting algorithms require roughly the same number of instructions to sort an array, then we might also examine the amount of memory space required.

17) Both the Insertion Sort and the Selection Sort algorithms have efficiencies on the order of ____ where n is the

number of values in the array being sorted.

a) n

b) n * log n

c) n2

d) n3

e) Insertion sort has an efficiency of n and Selection Sort has an efficiency of n2

C

Explanation: Both sorting algorithms use two nested loops which both execute approximately n times apiece, giving a complexity of n * n or n2 for both.

18) Consider the array declaration and instantiation: int[ ] arr = new int[5]; Which of the following is true about arr?

a) It stores 5 elements with legal indices between 1 and 5

b) It stores 5 elements with legal indices between 0 and 4

c) It stores 4 elements with legal indices between 1 and 4

d) It stores 6 elements with legal indices between 0 and 5

e) It stores 5 elements with legal indices between 0 and 5

B

Explanation: Arrays are instantiated with an int value representing their size, or the number of elements that they can store. So, arr can store 5 elements. Further, all arrays start at index 0 and go to index size - 1, so arr has

legal indices of 0 through 4.

19) If an int array is passed as a parameter to a method, which of the following would adequately define the parameter

list for the method header?

a) (int[ ])

b) (int a[ ])

c) (int[ ] a)

d) (int a)

e) (a[ ])

C

Explanation: The parameter is defined much as the variable is originally declared, as type parameter name.

Here, the type is int[ ] and the parameter is a.

20) If int[ ] x = new int[15]; and the statement x[-1] = 0; is executed, then which of the following Exceptions is thrown?

a) IndexOutOfBoundsException

b) ArrayIndexOutOfBoundsException

c) NegativeArraySizeException

d) NullPointException

e) ArithmeticException

B

Explanation: The array index is out of bounds as the array index can only be between 0 and 14. -1 is an

illegal index because it is out of bounds. One might expect the answer to be c, but the NegativeArraySizeException is

thrown if an array is being declared with a negative number of elements as in int[ ] x = new int[-5];

21) Assume that BankAccount is a predefined class and that the declaration BankAccount[ ] firstEmpireBank; has

already been performed. Then the following instruction reserves memory space for

firstEmpireBank = new BankAccount[1000];

a) a reference variable to the memory that stores all 1000 BankAccount entries

b) 1000 reference variables, each of which point to a single BankAccount entry

c) a single BankAccount entry

d) 1000 BankAccount entries

e) 1000 reference variables and 1000 BankAccount entries

B

Explanation: The declaration BankAccount[ ] firstEmpireBank; reserves memory space for

firstEmpireBank, which itself is a reference variable that points to the BankAccount[ ] object. The statement

firstEmpireBank = new BankAccount[1000]; instantiates the BankAccount[ ] object to be 1000 BankAccount objects.

This means that firstEmpireBank[0] and firstEmpireBank[1] and firstEmpireBank[999] are all now legal references,

each of which is a reference variable since each references a BankAccount object. So, the statement reserves memory

space for 1000 reference variables. Note that none of the 1000 BankAccount objects are yet instantiated, so no memory has been set aside yet for any of the actual BankAccount objects.

22) The following code accomplishes which of the tasks written below? Assume list is an int array that stores positive

int values only.

foo = 0;

for(j=0; j

a) it stores the smallest value in list (the minimum) in foo

b) it stores the largest value in list (the maximum) in foo

c) it stores every value in list, one at a time, in foo, until the loop terminates

d) it counts the number of elements in list that are greater than foo

e) it counts the number of elements in list that are less than foo

B

Explanation: The condition in the if statement tests to see if the current element of list is greater than foo.

If so, it replaces foo. The end result is that every element in list is tested and foo stores the largest element up to that

point, so eventually, foo will be the largest value in the array list.

23) If x is a char, and values is an int array, then values[x]

a) causes a syntax error

b) causes an Exception to be thrown

c) casts x as an int based on x's position in the alphabet (for instance, if x is 'a' then it uses 0 and if x is

'z' then it uses 25)

d) casts x as an int based on x's Unicode value (for instance, if x is 'a' then it uses 97 and if x is 'z' then

it uses 122)

e) casts x as an int based on the digit that is stored in x (for instance, if x is '3' it uses 3) but throws an

exception if x does not store a digit

D

Explanation: An array index must be an int value, so normally values[x] would cause a syntax error if x

were not an int, but the Java compiler will automatically cast x to be an int if it can be cast. Characters are cast as ints by converting the char value to its equivalent Unicode value. So, if x is 'a', it is cast as the int 97 instead and so

values[x] accesses values[97].

24) To initialize a String array names to store the three Strings "Huey", "Duey" and "Louie", you would do

a) String names = {"Huey", "Duey", "Louie"};

b) String[ ] names = {"Huey", "Duey", "Louie"};

c) String[ ] names = new String{"Huey", "Duey", "Louie"};

d) String names[3] = {"Huey", "Duey", "Louie"};

e) String names; names[0] = "Huey"; names[1] = "Duey"; names[2] = "Louie";

B

Explanation: An array does not have to be instantiated with the reserved word new if it is instantiated with

the list of values it is to store. So, names = {"Huey", "Duey", "Louie"}; will create a String array of 3 elements with

the three values already initialized. Of the other answers, a does not specify that names is a String array, c should not

have the reserved word new, d should not have [3] after names and omits [ ] after String, and e does not instantiate the array as String[3], and thus , all four of these other answers are syntactically invalid.

25) To declare a two-dimensional int array called threeD, which of the following would you use?

a) int[2] twoD;

b) int[ , ] twoD;

c) int[ ][ ] twoD;

d) int [ [ ] ] twoD;

e) int[ ] twoD[2];

C

Explanation: In Java, you can only declare one-dimensional arrays. To create a two-dimensional array,

you must declare it as an array of arrays. The proper notation is to declare the type of array using multiple [ ] marks in succession, as in int[ ][ ] for a two-dimensional array.

26) Which of the following statements loops through every element in the ArrayList alist?

a) for (Object item : alist)

b) for (item in alist)

c) for (Object item = null; item : alist)

d) for (Object alist : item)

e) for (alist : Object item)

A

Explanation: Choice a is a proper foreach loop. Every element in alist is assigned to the variable item in turn.

27) Which of the following correctly declares an ArrayList of Car objects?

a) ArrayList Car;

b) ArrayList cars = Car;

c) ArrayList Car[] cars;

d) ArrayList cars;

e) ArrayList[Car] cars;

D

Explanation: Choice d uses the proper syntax to declare an ArrayList of Cars.

28) Which of the following expressions gives the last element in the ArrayList alist?

a) alist.last()

b) alist.get(alist.last())

c) alist.get(alist.length())

d) alist.get(alist.size())

e) alist.get(alist.size()-1)

E

Explanation: The get method on an ArrayList returns the element at the given index, and the size method returns the number of elements in the ArrayList. Elements are numbered starting at index 0, so index size()-1 contains the last element.

29) Which of the following statements adds item to the end of the ArrayList alist?

a) alist.add(item);

b) alist.set(alist.size()-1, item);

c) alist[alist.size()-1] = item;

d) item.addtoEnd(alist);

e) Both a and b.

A

Explanation: The add method adds the given item to the end of the list. Choice b is not correct because it replaces the last element with item

1) Arrays have a built in toString method that returns all of the elements in the array as one String with "\n" inserted between each element.

False

Explanation: Arrays are objects and so they inherit from the Object class. The Object class does have a toString method. However, Object's toString method does not return the value(s) stored in the Object but rather the value of the reference variable. So, toString used on an array will not return the values stored in the array, but instead a meaningless set of characters.

2) Java arrays can store primitive types and Strings, but cannot store any other type of Object other than Strings.

False

Explanation: Java arrays can store any type of class.

3) A Java main method uses the parameter (String[ ] variable) so that a user can run the program and supply "command- line" parameters. Since the parameter is a String array, however, the user does not have to supply any parameters.

True

Explanation: The main method requires the parameter in case a programmer wishes to permit the user to supply command-line parameters. Anything entered at the command line after the java command will then be accepted as the command-line parameter. If it is several words separated by spaces, then each word is stored as a separate String array element. For instance, "java foo.class hi there" would store "hi" in variable[0] and "there" in variable[1] for possible use by the program.

4) An array index cannot be a double, boolean or String.

True

Explanation: An array index must be an int type, or a value that can be narrowed into an int (so char, byte and short are also permissible).

5) If the following statement is performed: CD[ ] mycollection = new CD[200]; where CD is a previously defined class, then mycollection[5] is a CD object.

True

Explanation: The variable mycollection has been declared as an array of CD objects, so mycollection[5] is the 6th CD in the the array, and since a CD is an object, mycollection[5] is a CD object.

6) It is possible to sort an array of int, double or String, but not an array of any other class, such as a CD class.

False

Explanation: It is possible to sort any type of array as long as the type has some mechanism to compare two elements and determine their proper ordering (less than, equal, greater than). So, if the CD class has a compareTo method, then it would be possible to sort them.

7) To swap the 3rd and 4th elements in the int array values, you would do:

values[3] = values[4];

values[4] = values[3];

False

Explanation: This code first copies values[4] into values[3] and then copies values[3] into values[4]. The result is that whatever was stored in values[4] is now stored in both values[3] and values[4]. In order to perform the swap appropriately, you would need a third variable to be used as a temporary storage location, as in

int temp = values[3]; values[3] = values[4]; values[4] = temp;

8) In Java, an array can only store one type of data. For instance, you cannot create an array that stores both double and String values.

True

Explanation: Arrays are known as homogeneous types. This means that the type of value stored in the array must be the same for every element. The type is determined by the declaration. So, int[ ] x makes x an array of int values only. So, no array could store both doubles and Strings.

9) In a two-dimensional array, both dimensions must have the same number of elements, as in [10][10].

False

Explanation: In Java, the dimensions can have any number of positive elements, so it is possible to have a two-dimensional array with dimensions of [5] and [10].

10) The statement int[ ] list = {5, 10, 15, 20}; initializes list to have 4 int values

True

Explanation: An array does not have to be instantiated with the new reserved word if it is instantiated with the list of values it is to store. So, list = {5, 10, 15, 20}; causes list to become an array of 4 int values with the values of 5, 10, 15, 20 already initialized. Note that the array is automatically an array of 4 values, so list[n] for any value of n other than 0, 1, 2 or 3 would result in a thrown Exception.

11) An array, when instantiated, is fixed in size, but an ArrayList can dynamically change in size when new elements are added to it.

True

Explanation: A drawback of an array is its fixed size. Once instantiated, it is fixed in size and so, if a program tries to add more elements than the size of the array, it results in an Exception being thrown. The ArrayList is a class that uses an array and automatically creates a larger array, copying the old array into the new array so that the ArrayList can be larger as needed. While this gets around the problem of a thrown Exception, it does lead to poorer performance because of having to copy from one array to another every time the ArrayList size is increased.

12) If a and b are both int arrays, then a = b; will copy all elements of b into a.

False

Explanation: The "=" is an assignment operator. If the two variables are primitives, than the left-hand variable gets a copy of the right-hand variable (so if a and b are int values and b = 5, then a would become 5). However, since a and b are arrays, the reference variable a is set to the reference variable b, resulting in both a and b referencing the same array in memory, or they are now aliases of each other.

13) Since a binary search is faster, there is no reason to use a linear search over a binary search.

False

Explanation: When the data is not sorted a binary search cannot be used, so a linear search is more appropriate.

14) Each pass of a binary search eliminates approximately half the remaining elements from consideration.

True

Explanation: A binary search examines the middle element and moves left or right depending on whether the key is less than or greater than the middle element, so half the remaining elements are eliminated in each pass.

15) An O(n2) algorithm is faster than an O(n) algorithm for large values of n.

False

Explanation: The statement is backwards: O(n) is faster than O(n2).

16) The time efficiency of an algorithm is the number of milliseconds it takes the algorithm to complete.

False

Explanation: Time efficiency is not measured in real time units, since it is used only to compare algorithms to each other. It is a measure of how long it takes an algorithm to run, expressed in terms of the size of the input.

17) The insertion sort and selection sort algorithms have space efficiency O(n).

True

Explanation: Since both sorts sort the array in place, their space efficiency is O(n).

18) A hash table is an array whose indices are not integers.

False

Explanation: All arrays have integer indices. A hash table refers to an array (or other data structure) that is used for hashing.

19) A hash function calculates the index an element should be stored at in a hash table.

True

20) The input to a hash function is usually the data item itself.

True

Explanation: A hash function calculates an index from properties of the data item itself.

21) If our hash function for a hash table storing integers was to take the integer modulo 5, then the integer 5 would be stored in cell 5.

False

Explanation: 5 % 5 is 0, so 5 would be stored in cell 0.

22) A collision is when two adjacent cells in a hash table store the same value.

False

Explanation: A collision is when two values hash to the same cell.

23) Unlike an array, an ArrayList object can grow and shrink in size.

True

Explanation: An ArrayList is more flexible than an array in this regard.

24) An ArrayList can store only objects, not primitive types.

True

Explanation: The add method on the ArrayList class which is used to add elements to the list, takes an Object as a parameter, so only objects can be added to an ArrayList.

25) If a is an ArrayList, we can say a.add(5); to add an integer to a.

True

Explanation: An ArrayList can store only objects, not primitive types, so in this case autoboxing occurs. That is, new Integer(5) is automatically performed and the Integer object is then added to a. (Note that this feature is new with Java 5. Using previous versions of Java, the answer to this question would be false.)

26) Foreach loops can be used with ArrayList objects, but not with arrays.

False

Explanation: Foreach loops can be used with both arrays and ArrayList objects (as well as other collection objects).

27) An ArrayList can store any type of object, but it is not possible to store objects of two different types in the same ArrayList.

False

Explanation: An ArrayList declared with no type, or declared with type Object, stores Objects, which means it can store objects of any type (since all classes have Object as an ancestor).

28) In order to store primitive values in an ArrayList, wrapper classes must be used.

True

Explanation: An ArrayList can store only objects, not primitive types, thus, primitive values must be wrapped in objects, using wrapper classes like Integer, in order to be stored in an ArrayList.

29) ArrayLists can store primitive types when the generics syntax is used, as in ArrayList.

False

Explanation: ArrayLists cannot store primitive types.