5 Steps to a 5 AP Computer Science A 2017 (2016)

STEP 4

Review the Knowledge You Need to Score High

CONCEPT 5

Data Structures

IN THIS CONCEPT

Summary: Sometimes a simple variable is not enough. To solve certain problems, you need a list of variables or objects. The array, the two-dimensional array, and the ArrayList are three complex data structures that are tested on the AP Computer Science A Exam. You must learn the advantages and disadvantages of each of these data structures, know how to work with them, and be able to choose the best one for the job at hand.

Key Ideas

   An array is a data structure that can store a list of variables of the same data type.

   An array is not resizable once it is created.

   A two-dimensional (2-D) array is a data structure that is an array of arrays.

   The 2-D array simulates a rectangular grid with coordinates for each location based on the row and the column.

   An ArrayList is a data structure that can store a list of objects from the same class.

   An ArrayList resizes itself as objects are added to and removed from the list.

   To traverse a data structure means to visit each element in the structure.

   The enhanced for loop (for-each loop) is a special looping structure that can be used by either arrays or ArrayLists.

What Is a Data Structure?

Have you ever dreamed about having the high score in the “Top Scores” of a game? How does Facebook keep track of your friends? How does Vine know what video to loop next? All of these require the use of a complex data structure.

Simple Data Structure Versus Complex Data Structure

As programmers, we use data structures to store information. A primitive variable is an example of a simple data structure as it can store a single value to be retrieved later. A variable that can store a list of other variables is called a complex data structure .

Thinking of ways to represent physical objects by using virtual objects can be challenging. Really awesome programmers have the ability to visualize complex real-world situations and design data structures to represent these physical objects in a virtual way. In the drawing below, the programmer is trying to figure out a way to represent the choices from the lunch menu in a program by creating a complex data structure.

Three Important Complex Data Structures

There are three complex data structures that are tested on the AP Computer Science A Exam:

  • The array (or one-dimensional array)
  • The 2-D array
  • The ArrayList

Each of these will be explained in detail later in this concept, but for now, I want to give you an overview of which data structure would be the best choice for a given situation. You will want to become a master at deciding the best data structure for a particular situation. This normally comes with experience, but here are a few examples as to which one is the best under what circumstances.

The Array

Definition of an Array

The non-programming definition of an array is “an impressive display of a particular thing.” We use the word in common language when we say things like, “Wow, look at the wide array of phone cases at the mall!” It means that there is a group or list of things that are of the same kind.

An array (one-dimensional array ) in Java is a complex data structure because it can store a list of primitives or objects. It also stores them in such a way that each of the items in the list can be referenced by an index . This means that the array assigns a number to each of the slots that holds each of the values. By doing this, the programmer can easily find the value that is stored in a slot, change it, print it, and so on. The values in the array are called the elements of the array. An array can hold any data type, primitive or object.

Declaring an Array and Initializing It Using a Predefined List of Data

There are two ways to create an array on the AP Computer Science A Exam. The first technique is used when you already know the values that you are going to store in the list and you have no reason to add any more items. A pair of brackets , [ ] , tells the compiler to create an array, not just a regular variable.

General Form for Creating an Array Using a Predefined List of Data

Notice the pair of brackets [ ] after dataType. The brackets signify this variable is a reference to an array object.

Example

Declare an array of String variables that represent food choices at a restaurant:

The graphic at the right is a visual representation of the foodChoices array. The strings representing the actual food choices are the elements in the array (Pizza, Cheeseburger, etc.) and each slot is assigned a number, called the index (0, 1, 2, etc.). The index is a number that makes it easy for the programmer to know what element is placed in what slot. The first index is always zero. The last index is always one less than the length of the array.

How to “Speak” Array

When talking about elements of an array, we say things like, “Pizza is the first element in the foodChoices array and its index is zero” or “The element at index 2 of the foodChoices array is Tacos.”

The length Field

After an array is created and initialized, you can ask it how many slots it has by using the length field. Think of the length as an instance variable for an array. Notice that the length does not have a pair of parentheses after it, because it is not a method.

Example

Find the length of the foodChoices array:

The length of an Array

The length field of an array returns the total number of slots that are set aside for that array. It does not return the total number of valid elements in the array. Also, since the first index of an array is always zero, the length of the array is always one more than the last index.

Declaring an Array Using the Keyword new

The second technique for creating an array is used when you know the length of the list, but you may not know all of the values that will go in the list. Again, a pair of brackets , [ ], is used to tell the compiler that you want to create an array, not just a regular variable.

General Form for Creating an Array Using the Keyword new

The number of slots is fixed and all of the elements in the array get the default value for the data type. You can also declare just an array reference variable and then use the keyword new to create the array later.

No Resizing an Array

An array cannot be resized after it is created.

Example

Create an array that will represent all of your semester grade point averages for all four years of high school. Let’s assume there are two semesters per year. This makes a total of eight semesters. So, let’s declare an array to hold eight double values and call the array myGPAs.

Ouch, all zeros. That hurts. No worries, we can change that. You see, when an array is created in this manner, all of the elements become whatever the default value is for that data type. The default value for a double is 0.0.

Now that the array is created, let’s put some valid numbers into it. In order to replace a value in an array, you need to know the correct index.

Let’s let index 0 represent the first semester of your freshman year and let’s suppose you earned a GPA of 3.62.

And, let’s suppose you earned a 3.75 for the second semester of your sophomore year.

Smart, but Not so Smart

The computer has no idea that these numbers represent the GPAs for a student in school. As far as it’s concerned, it is just storing a bunch of numbers in an array.

Example

Pick a random color from an array of color names:

The ArrayIndexOutOfBoundsException

If you ever accidently use an index that is too big (greater than or equal to the length of the array) or negative, you will get a run-time error called an ArrayIndexOutOfBoundsException .

Example

You declare an array of Circle objects and attempt to print the radius of the last circle. But you get an ArrayIndexOutOfBoundsException because your index is too large. Note: The length of the array is 6. The index of the last Circle object is 5. Then, write it the correct way:

Common Error

A common error is to accidentally set the index of an array to be the length of the array. The first index of the array is zero, so the last index of the array is length – 1 .

Traversing an Array

To traverse an array means to move through each slot in the array, one at a time. The most common way to perform a traversal is to start with the first index and end with the last index. But that’s not the only way. You could start with the last index and move toward the first. You also could do all of the even indices first and then all of the odds. You get what I’m saying? Traversing an array just means that you visit every element at every index in an array.

Print the Contents of a One-Dimensional Array by Traversing It

Example

Print out the names of all your friends on Facebook using a for loop. By traversing the array from the first element to the last element, you can print each friend’s name.

Off-by-One Error

This is a logic error that every programmer has committed at some point. It means that in a loop of some kind, your index is off by one number. You either went one index too high or one index too low.

The Enhanced for Loop (the for-each Loop)

The enhanced for loop (aka the for-each loop ) can also be used to traverse an array. It does not work the same way as the standard for loop. The for-each loop always starts at the beginning of the array and ends with the last element in the array. As the name indicates, the for-each loop iterates through each of the elements in the array, and for each element, the temporary variable “takes on” its value. The temporary variable is only a copy of the actual value and any changes to the temporary variable are not reflected in the actual value.

General Form for the Enhanced for Loop (the for-each Loop)

There is no loop control variable for the enhanced for loop (it is a black box ). You only have access to the elements in the array, not the index. Also, the data type of the temporary variable must be the same as the data type of the array.

Traversing a One-Dimensional Array Using the Enhanced for Loop

Example

Print out the names of all your friends on Facebook using a for-each loop. Note: friend is a temporary variable that is of the same data type as the data stored in the array.

Mistake When Printing the Contents of an Array

Beginning programmers make the mistake of trying to print the contents of an array by printing the array reference variable. The result that is printed is garbage . This is because the reference variable only contains the address of where the array is; it does not store the elements of the array.

OUTPUT

Note: The best way to print the contents of an array is to traverse the array using either a for loop or a for-each loop.

The 2-D Array

Definition of a 2-D Array

two-dimensional (2-D) array is a complex data structure that can be visualized as a rectangular grid made up of rows and columns . Technically, it is an array of arrays . It can store any kind of data in its slots; however, each piece of data has to be of the same data type.

Two-dimensional arrays are actually fun to work with and are very practical when creating grid-style games. Many board games are based on a grid: checkers, chess, Scrabble, etc. Many apps are based on grids too: CandyCrush, 2048, Ruzzle. I’m sure you can think of others.

Declaring a 2-D Array and Initializing It Using a Predefined List of Data

When you know the values that you want to store in the 2-D array, you can declare the array and store the values in it immediately. This operation is just like what we did for the one-dimensional array. Two pairs of brackets , [ ][ ] , are used to tell the computer that it is not a regular variable.

General Form for Creating a 2-D Array Using a Predefined List of Data

Note: Pairs of curly braces are used to wrap the first row, then the second row, and so on. If you look closely at this visual, you will see how a 2-D array is really an array of arrays.

Example

Declare a 2-D array that represents a CandyCrush board with four rows and three columns. Notice that the four rows are numbered 0 through 3 and the three columns are numbered 0 through 2.

This is the visual representation of what the candyBoard array looks like inside the computer.

Rows and Columns of the 2-D Array

Every cell in a 2-D array is assigned a pair of coordinates that are based on the row number and the column number. The first pair of brackets represents the row number and the second pair of brackets represents the column number. The rows and columns both begin at zero and end with one less than the number of rows or columns.

Example

Change the “Lozenge” in row 2 and column 0 to be a “Lemon Drop”.

candyBoard[2][0] = “Lemon Drop”;

Declaring a 2-D Array Using the Keyword new

A 2-D array object can be created using the keyword new . Every cell in the 2-D array is filled with the default value for its data type.

General Form for Creating a 2-D Array Using the Keyword new

Example

Declare a 2-D array that represents a Sudoku Board that has nine rows and nine columns. Put the number 6 in row 2, column 7:

How to Refer to the Rows and Columns in a 2-D Array

The position, myBoard[0][5] , is read as row 0, column 5 .

The position, myBoard[3][0] , is read as row 3, column 0 .

Using the length Field to Find the Number of Rows and Columns

The number of rows in a 2-D array is found by accessing the length field. The number of columns in a 2-D array is found by accessing the length field on the name of the array along with one of the rows (it doesn’t matter which row).

Example 1

Retrieve the number of rows from a 2-D array:

Example 2

Retrieve the number of columns from a 2-D array:

Accessing a 1-D Array from Within the 2-D Array

Consider this 2-D array declaration:

double[][] myBoard = new double[8][3];

myBoard[0] is a 1-D array that consists of the row with index 0.

myBoard[5] is a 1-D array that consists of the row with index 5.

Traversing a 2-D Array in Row-Major Order

Traversing a 2-D array means to visit every cell in the grid. This can be done in many different ways, but for the AP Exam, you need to know two specific ways.

Row-Major order is the process of traversing a 2-D array in the manner that English-speaking people read a book. Start at the top left cell and move toward the right along the first row until you reach the end of the row. Then start at the next row at the left-most cell, and then move along to the right until you reach the end of that row. Repeat this process until you have visited every cell in the grid and finish with the bottom-right cell.

Example

Traverse an array in row-major order using a nested for loop. Start with row 0 and end with the last row. For each row, start with column 0 and end with the last column.

Traversing a 2-D Array in Column-Major Order

Column-Major order is the process of traversing a 2-D array by starting at the top left cell and moving downward until you reach the bottom of the first column. Then start at the top of the next column and work your way down until you reach the bottom of that column. Repeat this until you have visited every cell in the grid and finish with the bottom-right cell.

Example

Traverse an array in column-major order using a nested for loop. Start with column 0 and end with the last column. For each column, start with row 0 and end with the last row.

ArrayIndexOutOfBoundsException

As with a 1-D array, if you use an index that is not within the 2-D array, you will get an ArrayIndexOutOfBoundsException.

Fun Fact Java provides support for multi-dimensional arrays, such as 3-D arrays; however, the AP Computer Science A Exam does not require you to know about them .

The ArrayList

Definition of an ArrayList

An ArrayList is a complex data structure that allows you to add or remove objects from a list and it changes size automatically.

Declaring an ArrayList Object

An ArrayList is an object of the ArrayList class. Therefore, to create an ArrayList, you need to use the keyword new along with the constructor from the ArrayList class. You also need to know the data type of the objects that will be stored in the list. The ArrayList uses a pair of angle brackets , < and >, to enclose the class name of the objects it will store.

Two General Forms for Declaring an ArrayList

ArrayList <ClassName> nameOfArrayList = new ArrayList<ClassName>();

or

List <ClassName> nameOfArrayList = new ArrayList<ClassName>();

Note: Questions on the AP Exam will use either ArrayList or List for the data types of the reference variables for an ArrayList object. List will be explained in Concept 9.

The graphic that follows is a visual representation of what the ArrayList looks like in memory.

Example

Declare an ArrayList of Circle objects. Please note that I am referring back to the Circle Class from Concept 2 and that the memory address is simulated.

An ArrayList Always Starts Out Empty

When you create an ArrayList object, it is empty, meaning that there are no items in the list. It’s like when your mom starts to make a “To Do” list and she writes the words “To Do” on the top of a piece of paper. The list is created but there is nothing in the list.

An ArrayList Is Resizable

When your mom writes, “Go grocery shopping” or “Buy awesome video game for favorite child” on her To Do list, the size of the list grows. As she completes a task on the list, she crosses it out and the size of the list shrinks. This is exactly how an ArrayList is resized.

Automatic Resizing

An awesome feature of the ArrayList is its ability to resize itself as elements are added to or removed from the list. The size() method (explained later) immediately recalculates how many elements are in the list.

An ArrayList Requires an import Statement

The ArrayList is not part of the built-in Java language package, so you have to let the compiler know that you plan on creating an ArrayList by putting an import statement prior to the class declaration.

You will not need to write any import statements on the AP exam.

An ArrayList Can Only Store Objects

Unlike the array, which could store primitive variables like an int or double, as well as objects, the ArrayList can only store objects . If you want to store an int or double in an ArrayList, you must use the Integer or Double wrapper classes. This is one of the reasons why the wrapper classes were created.

Example

Create an ArrayList of Integers. Add an int to the ArrayList and secretly watch as the int is automatically converted to an Integer using a secret, Java black box technique called autoboxing .

Important ArrayList Methods

The ArrayList class comes with a large array of methods (see my pun). These methods make it easy to work with the objects inside the ArrayList. The AP Computer Science A Exam does not require you to know all of the methods from the ArrayList class; however, it does require you to know a subset of them.

The add Method

There are two add methods for the ArrayList. The add(E object) method appends the object to the end of the list. This means that it adds the object to the end of the list. It also returns the value true. The size of the ArrayList is automatically updated to reflect the addition of the new element.

Example

Create an ArrayList of Circle objects. Add three Circle objects to the ArrayList where the first has a radius of 8, the second doesn’t provide a radius so the radius gets the default value of zero, and finally, the last circle has a radius of 6.5. Note: This example will be used in the explanations for the other ArrayList methods.

After line 1 is executed: There is one Circle object in the ArrayList.

After line 2 is executed: There are two Circle objects in the ArrayList.

After line 3 is executed: There are three Circle objects in the ArrayList.

What’s with E?

The data type E is known as a generic type . It simply means that you can put any kind of data type here. I like to say, “The method takes E very kind of data type.”

Another add Method

The add(int index, E object) method inserts the object into the position index in the ArrayList, shifting the object that was previously at position index and each of the objects after it over one index. The index for each of the objects affected by the add is incremented. The method does not return a value.

An ArrayList Is Like the Lunch Line at School

An ArrayList can be visualized like the lunch line at school. Imagine there are 10 students in line and they are numbered 0 through 9. Person 0 is the first person in line.

Suppose the unthinkable happens and a student walks up and cuts the line. They have just inserted themselves into the list. If the cutter is now the third person in line, then they have just performed an add(2, “cutter”) . This action impacts everyone who is in line after the cutter. The person who used to be in position 2, is now in position 3. The person who used to be at position 3 is now in position 4, and so on. The index for each person behind the cutter was incremented by one .

After line 4 is executed: The Circle object with a radius of 4 was inserted into the position with an index of 1 (the second position). All of the Circle objects after it had to move over one slot.

The size Method

The size() method returns the number of items in the ArrayList. Notice that this is different from the length field of the array, which tells you how many slots were set aside and not the actual number of valid items stored in the array.

IndexOutOfBoundsException

As in the 1-D array and the 2-D array, you will get an error if you try to access objects outside of the range of the list. The error when doing this with an ArrayList is called the IndexOutOfBoundsException .

The index, 88, is not in the range of 0 ≤ index ≤ myCircle.size().

The remove Method

The remove(int index) method deletes the object from the list that is at index. Each of the objects after this shifts down one index. The method also returns a reference to the object that was removed from the list.

After line 6 is executed: the Circle object that used to be in the slot at index 2 is removed (the circle with a radius of 0). The Circle objects that were positioned after it all move down one slot and someCircle now points to the Circle object that was removed.

The get Method

The get(int index) method returns the object that is located in the ArrayList at position index. It doesn’t remove the object; it just returns a copy of the object reference. This way, an alias is created (more than one object reference pointing to the same object). The value of index must be greater than or equal to zero and less than the size of the ArrayList.

Example

Get the Circle object at index 2 and assign it to a different Circle reference variable:

The set Method

The set(int index, E object) method replaces the object in the ArrayList at position index with object. It returns a reference to the object that was previously at index.

Example

Replace the Circle object at index 0 with a new Circle object with a radius of 20:

length Versus size() Versus length()

To find the number of slots in an array, use the length field.

To find the number of objects in an ArrayList, use the size() method.

To find the number of characters in a string, use the length() method.

Traversing an ArrayList Using a for Loop

The following code uses a for loop to print the area of each of the Circle objects in the ArrayList. The get method is used to retrieve each Circle object and then the getArea method is used on each of these Circle objects. Note that the dot operator is used twice in the same instruction. First, to get the current circle in the ArrayList, and second to get the area for that circle.

Traversing an ArrayList Using the Enhanced for Loop

The enhanced for loop (for-each loop) can be used with an ArrayList. The following code prints the area of each of the Circle objects in the ArrayList. Notice that the temporary variable, circle, is the same data type as the objects in the ArrayList. In contrast to the general for loop shown above, the enhanced for loop does not use a loop control variable. Therefore, there is no need for the get(i) method since the variable circle is a copy of each of the Circle objects, one at a time and the getArea method can be used directly with circle.

Printing the Contents of an ArrayList

Unlike an array, the contents of an ArrayList can be displayed to the console by printing the reference variable. The contents are enclosed in brackets and separated by commas.

Note: If you want to format the output when printing the contents of an ArrayList, you should traverse the ArrayList.

Do Not Use remove() in the Enhanced for Loop

Never use the enhanced for loop (for-each) loop to remove an item from an ArrayList. You need the index to perform this process and the for-each loop doesn’t use one.

If you have to perform a remove, use an index variable with a while loop. Increment the index to get to the next element in the ArrayList. But, if you perform a remove, then don’t increment the index.

 Rapid Review

The Array

  • An array is a complex data structure that can store a list of data of the same data type.
  • An array is also referred to as a one-dimensional (or 1-D) array.
  • An array can be created by assigning it a predetermined list.
  • An array can be created by using the keyword new.
  • An array can store either primitive data types or object reference types.
  • Even though arrays are objects, they do not have methods.
  • An array has one public field, called length.
  • The length of the array refers to how many elements can be stored in the array and is decided when the array is created.
  • The length of an array cannot be resized once it is declared. That is, an array cannot be made shorter or longer once it is created.
  • The length field returns the total number of locations that exist in the array, and not the number of meaningful elements in the array.
  • An element of an array refers to the item that is stored in the array.
  • The index of an array refers to the position of an element in an array.
  • The first index of an array is 0. The last index is its length – 1.
  • Unused indices in an array automatically receive the default value for that data type.
  • If an array contains objects, their default values are null. You need to instantiate an object for each element of the array before they can be used.
  • Using an index that is not in the range of the array will throw an ArrayIndexOutOfBoundsException.

Traversing an Array

  • Traversing an array refers to the process of visiting every element in the array.
  • There are many options for traversing an array; however, the most common way is to start at the beginning and work toward the end.
  • Based on the situation, there are times where you may want to traverse an array starting at the end and work toward the beginning.
  • Sometimes you may want to traverse only a section of the array.
  • When using a for loop to traverse an array, be sure to use length – 1 rather than length when accessing the last element in the array.
  • The enhanced for loop iterates through each element in the array without using an index.
  • The enhanced for loop is also known as the for-each loop.
  • The enhanced for loop always starts with the first element and ends with the last.
  • Use an enhanced for loop when you don’t need to know the index for each element and you don’t need to change the element in any way.

The 2-D Array

  • A 2-D array is a complex data structure that can store a grid of data of the same type.
  • The 2-D array is actually an array of arrays.
  • The rows and columns are numbered starting with zero.
  • The top row is row zero. The left-most column is column zero.
  • The access to each cell in the 2-D array is always [row][column ].
  • The indices of the top-left cell are [0][0].
  • The index of the bottom-right cell is [numberOfRows– 1][numberOfColumns – 1].
  • Two-dimensional arrays can store primitive data or object data.
  • To store a value in a 2-D array: arrayName[rowNumber][columnNumber ] = value;
  • To retrieve the number of rows in a 2-D array, use arrayName.length.
  • To retrieve the number of columns in a rectangular 2-D array, use arrayName[0].length. Note: Any valid row number works instead of 0.
  • Using an index that is not in the range of the 2-D array will throw an ArrayIndexOutOfBoundsException.

Traversing a 2-D Array

  • To traverse a 2-D array means to visit each element in every row and column.
  • The most common way to traverse a 2-D array is called Row-Major order.
  • Row-Major order starts in the upper left, location [0][0], and travels to the right until the end of the row is reached. Then the next move is to the next row [1][0]. The process is repeated until the right-most column in the bottom row is reached.
  • The second most common way to traverse a 2-D array is called Column-Major order.
  • Column-Major order also starts in the upper left location [0][0]; however, it travels down until the end of the first column is reached. Then, the next move is to the top of the next column [0][1]. The process is repeated until the bottom row in the right-most column is reached.
  • All of the 2-D arrays on the AP Computer Science A Exam will be rectangular.

The ArrayList

  • The ArrayList is a complex data structure that can store a list of objects.
  • The two general forms for declaring an ArrayList are:

   

  • An ArrayList can only hold a list of objects; it cannot hold a list of primitive data.
  • Use the Integer or Double classes to make an ArrayList of int or double values.
  • The initial size of an ArrayList is 0.
  • The add(E object) method appends the object to the end of the ArrayList. It also returns true.
  • To append means to add on to the end of a list.
  • The add(int index, E object) method inserts object at position index (note: index must be in the interval: [0,size]). As a result of this insertion, the elements at position index and higher move 1 index further from the 0 index.
  • The get(int index) method returns a reference to the object that is at index.
  • The set(int index, E object) method replaces the element at position index with object and returns the element that was formerly at index.
  • The remove(int index) method removes the element at position index, and subsequently subtracts one from the indices of the elements at positions index + 1 and greater. It also returns the element that was removed.
  • The size() method returns an int that represents the number of elements that are currently in the ArrayList.
  • The size of the ArrayList grows and shrinks by either adding or removing elements.
  • The size() method adjusts accordingly as elements are added or removed.
  • Using an index that is not in the range of the ArrayList will throw an IndexOutOfBoundsException.
  • The ArrayList requires an import statement since it is not in the standard library, but this will never be required on the AP exam.

Traversing an ArrayList

  • To traverse an ArrayList means to visit each of the elements in the list.
  • There are many ways to traverse an ArrayList, but the most common way is to start at the beginning and work toward the end.
  • If a for loop is used to traverse an ArrayList, then the get() method will be required to gain access to each of the elements in the ArrayList.
  • If an enhanced for loop is used to traverse an ArrayList, then the get() method is not required to gain access to each of the elements in the ArrayList, since each object is automatically retrieved by the loop, one at a time.

 Review Questions

Basic Level

  1. Consider the following code segment.

What is printed as a result of executing the code segment?

(A)   0

(B)   13

(C)   26

(D)   28

(E)   56

  1. Consider the following code segment.

What is printed as a result of executing the code segment?

(A)   0

(B)   1

(C)   3

(D)   7

(E)   16

  1. Assume that cities is anArrayList<String> that has been correctly constructed and populated with the following items.

Consider the following code segment.

What items does cities contain after executing the code segment?

(A)   ["Cleveland", “Detroit", “Oakland", “Chicago", “Seattle", “Denver", “Boston"]

(B)   ["Oakland", “Milwaukee", “Seattle", “Boston", “Detroit", “Cleveland"]

(C)   ["Oakland", “Chicago", “Seattle", “Boston", “Detroit", “Cleveland"]

(D)   ["Oakland", “Milwaukee", “Denver", “Boston", “Detroit", “Cleveland"]

(E)   ["Oakland", “Chicago", “Seattle", “Denver", “Detroit", “Cleveland"]

  1. Consider the following code segment.

What is printed as a result of executing the code segment?

(A)   91

(B)   746

(C)   913

(D)   79416385

(E)   416385

  1. Consider the following code segment.

What is printed as a result of executing the code segment?

(A)   [French, English, Math, Biology]

(B)   [French, Art, Biology]

(C)   [French, English, Art, Math, Biology]

(D)   [French, Math, Biology]

(E)   IndexOutOfBoundsException

  1. Free-Response Practice: Modifying a 2-D array

Write a method that takes a 2-D array as a parameter and returns a new 2-D array.

The even rows of the new array should be exactly the same as the array passed in.

The odd rows of the new array should be replaced by the contents of the row above.

Here is the declaration for your method.

public int[][] modify(int[][] arr)

Advanced Level

  1. Consider the following code segment.

What is printed as a result of executing the code segment?

(A)   34

(B)   37

(C)   46

(D)   47

(E)   49

  1. Consider the following code segment.

What values are stored in array nums after executing the code segment?

(A)   ArrayIndexOutOfBoundsException

(B)   {2, 2, 3, 3, 4, 4, 5, 5}

(C)   {0, 0, 1, 3, 5, 7, 9, 11}

(D)   {0, 0, 1, 1, 3, 4, 5, 6}

(E)   {0, 0, 1, 2, 2, 3, 4, 5 }

  1. Assume thatmsg is an ArrayList<String> that has been correctly constructed and populated with the following items.

Which code segment removes all String objects starting with a letter from the second half of the alphabet (n-z) from the ArrayList ?

Precondition: all String objects will be lowercase

Postcondition: msg will contain only String objects from the first half of the alphabet (a–m)

  1.    
  2.    

 III.    

(A)   I only

(B)   I and II only

(C)   II and III only

(D)   I and III only

(E)   I, II, and III

  1. Free-Response Practice: Filling a 2-D array

Write a method that will fill in a 2-D boolean array with a checkerboard pattern of alternating true and false . The upper left corner (0, 0) should always be true .

Given a grid size of 3 × 4, the method should return:

The method will take the number of rows and columns as parameters and return the completed array. Here is the method declaration and the array declaration:

 Answers and Explanations

Bullets mark each step in the process of arriving at the correct solution.

  1. The answer is D.
  • This is a for-each loop. Read it like this: “For each int (which I will call val) in values. . . .”
  • The loop will go through each element of the array values and add it to number. Notice that number starts at 13.

13 + 0 + 1 + 2 + 3 + 4 + 5 = 28

  1. The answer is D.
  • values[total] = values[3] = -2. Remember to start counting at 0.
  • 3 + -2 = 1, now total = 1
  • values [total] = values[1] = 6
  • 1 + 6 = 7 and that is what is printed.
  1. The answer is E.
  • Let’s picture the contents of our ArrayList in a table:
  • After the remove at index 2, we have this (notice how the indices have changed):
  • After adding Detroit, we have:
  • After the remove at index 4, we have
  • And then we add Cleveland:
  1. The answer is C.
  • Let’s lay out the array along with its indices.
  • The first time through the loop, i = 3.
  • values[3–2] = values [1] = 9 Print it.
  • Next time through the loop, i = 5.
  • values [5–2] = values [3] = 1 Print it.
  • Next time through the loop, i = 7.
  • Remember that even though the last index is 7, the length of the array is 8.
  • values [7–2] = values[5] = 3 Print it.
  • We exit the loop having printed “913”.
  1. The answer is E.
  • Let’s make tables to represent what happens as each statement is executed.

Oops! Can’t do it. Trying will generate an IndexOutOfBoundsException

  1. We can find the even rows by using the condition (row % 2 = = 0). In other words, if I can divide the row number by 2 and not have a remainder, it’s an even row. Even rows just get copied as is. Odd rows get copied from the row above [row – 1].

Here is the completed method.

  1. The answer is C.
  • After the initial for loop, the contents of the ArrayList are: [10, 11, 12, 13].
  • Let’s consider what the for-each loop is doing. For each Integer (called i) in integerList
  • add it to total (notice that total starts at 3).
  • (total % 2 = = 1) is a way of determining if a number is odd. If total is odd, subtract 1 from it.
  • Executing the for-each loop gives us:
  • total = 3 + 10 = 13 . . . odd  12
  • total = 12 + 11 = 23 . . . odd  22
  • total = 22 + 12 = 34 . . . even!
  • total = 34 + 13 = 47 . . . odd  46 and our final answer.
  1. The answer is D.
  • On entering the loop, nums = {0, 0, 1, 1, 2, 2, 3, 3} and i = 3. Set nums[4] to 3.
  • Now nums = {0, 0, 1, 1, 3, 2, 3, 3} and i = 4. Set nums[5] to 4.
  • Now nums = {0, 0, 1, 1, 3, 4, 3, 3} and i = 5. Set nums[6] to 5.
  • Now nums = {0, 0, 1, 1, 3, 4, 5, 3} and i = 6. Set nums[7] to 6.
  • Now nums = {0, 0, 1, 1, 3, 4, 5, 6} and i = 7. nums.length – 1 = 7, so exit the loop.
  1. The answer is C.
  • Using a loop to remove items from an ArrayList can be very tricky because when you remove an item, all the items after the removed item change indices. That’s why option I does not work. When item 3 “words” is removed, “starting” shifts over and becomes item 3, but the loop marches on to item 4 (now “with") and so “starting” is never considered and never removed.
  • Working backward through a loop works very well when removing items from an ArrayList because only items after the removed item will change indices, and you will have already looked at those items. Option II works and is the simplest solution.
  • Option III also works because it only increments the loop counter when an item is not removed. If an item is removed, the loop counter remains the same, so the item that gets shifted down ("starting” in the example above) is not skipped. Option III uses a while loop because it changes the loop index i, and it is bad programming style to mess with the loop index inside a for loop.
  1. There are many ways to solve this problem. This implementation uses the fact that grid[row][col] is true when row + col is even.

Here is a tester class so you can see if the way you wrote the method was also correct. Copy in your code. Try it with all shapes and sizes of grid to test it thoroughly.