IN THIS UNIT
Summary: In this unit we will discuss the ArrayList
, along with some of the methods that are used to access and manipulate its elements. In addition to the array algorithms that were introduced in the previous unit (which can also be done with ArrayLists
), we will look at searching and sorting algorithms that you need to know for the AP Computer Science A Exam.
Key Ideas
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
.
The copy algorithm makes a duplicate of a data structure.
The accumulate algorithm traverses a list, adding each value to a total.
The find-highest algorithm traverses and compares each value in the list to determine which one is the largest.
The process of developing an original algorithm requires concentration and analytical thought.
Accessing data that is buried within a class hierarchy requires the programmer to use the methods that belong to the class.
The sequential search algorithm finds a value in a list.
The Insertion Sort, Selection Sort, and Merge Sort are sorting routines.
ArrayList
ArrayList
An ArrayList
is a complex data structure that allows you to add or remove objects from a list and it changes size automatically.
ArrayList
ObjectAn 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.
Using a raw ArrayList
(without <>) allows the user to store a different data type in each position of the ArrayList
, which is not typically done since Java 5.0 arrived in 2004. The ArrayList <E>
notation is preferred over ArrayList
because it allows the compiler to find errors that would otherwise be found at run-time. You might see some older AP Computer Science A Exam questions using this syntax.
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 Unit 5 and that the memory address is simulated.
ArrayList
Always Starts Out EmptyWhen 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.
Example
ArrayList
Is ResizableWhen 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.
ArrayList
Requires an import
StatementThe 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.
ArrayList
Can Only Store ObjectsUnlike 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 (back in Unit 2 they were introduced).
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 (also introduced back in Unit 2).
ArrayList
MethodsThe 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.
add
MethodThere 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.
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 Every kind of data type.”
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 0, 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
.
add
MethodThe 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.
size
MethodThe size() method returns the number of elements 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.
As in the 1D
array and the 2D
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().
remove
MethodThe 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.
get
MethodThe 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:
set
MethodThe 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:
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.
ArrayList
Using a for
LoopTraversing is a way of accessing each element in an array or ArrayList
through the use of iteration. 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.
ArrayList
Using the Enhanced for
LoopThe 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, element, 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
Deleting elements during a traversal requires special techniques to avoid skipping elements. 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. However, 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.
Since the indices for an ArrayList
start at 0 and end at the number of elements - 1, accessing an index value outside of this range will result in an ArrayIndexOutOfBoundsException
being thrown.
Changing the size of an ArrayList
while traversing it using an enhanced for
loop can result in a ConcurrentModifcationException
being thrown. Therefore, when using an enhanced for
loop to traverse an ArrayList
, you should not add or remove elements.
You will receive a Java Quick Reference sheet to use on the multiple-choice and free-response sections which lists the ArrayList
class methods that may be included on the exam. Make sure you are familiar with it before you take the exam.
ArrayList
Making a copy of an ArrayList
means to create a brand-new object that is a duplicate of the original. This is different from creating a new ArrayList
variable that references the original ArrayList
. That was called making an alias. It is easy for new programmers to make the mistake of thinking that these two are the same.
Step 1: Create an array that is the same length as the original
Step 2: Look at each of the values in the original array one at a time
Step 3: Assign the value in the copy to be the corresponding value in the original
Step 4: Continue until you reach the last index of the original array
Create an array called duplicate that has the same length as the original array for (iterate through each element in the original array)
ArrayList
(for
loop)ArrayList
(for-each
loop)When you search iTunes for a song, how does it actually find what you are looking for? It may use a sequential search to find the name of a song. A sequential (or linear) search is the process of looking at each of the elements in a list, one at a time, until you find what you are looking for. Sequential (or linear) search is one standard algorithm for searching. Another search algorithm, the binary search, will be discussed in Unit 10.
The Search Target
When you search for a specific item in a list, the item you are looking for is often referred to as the search target. If the target is not found, a value of -1 is often returned.
Algorithm 1:
Step 1: Create a variable called foundIndex
and set it equal to -1
Step 2: Look at each of the titles in the array one at a time
Step 3: Compare each title to the target title
Step 4: If the title is equal to the target title, then assign foundIndex
to value of the current index
Step 5: Continue looking until you reach the end of the list
Step 6: Return the value of foundIndex
Pseudocode 1:
ArrayList
Did you notice that neither of the examples used a for-each loop? That was on purpose. Remember, if you need to access the index of an element in an array or ArrayList
, then a for-each loop cannot be used.
Algorithm 2:
Step 1: Look at each of the titles in the array one at a time
Step 2: Compare the target title to each of the titles
Step 3: If the title is equal to the target title, then stop looking and return the current index
Step 4: Continue looking until you reach the end of the list
Step 5: Return -1
Pseudocode 2:
ArrayList
Analyze the two solutions that searched for the title of a song.
The second algorithm is more efficient than the first because the method stops looking for the title as soon as it finds it. The first algorithm is less efficient than the second because it continues to compare each of the titles in the list against the search target even though it may have already found the search target.
Efficiency
An efficient algorithm does its job in the fastest way it can. Efficient programs are optimized to reduce CPU (central processing unit) time and memory usage.
Suppose you have a list of all the baseball players on a team and you want to find the total number of hits that the team had. As humans, we can do this quite easily. Just add them up. But how do you teach a computer to add up all of the hits?
General Problem: Add up all of the hits for a baseball team.
Refined Problem: Write a method that finds the sum of all of the hits in an array of hits.
Final Problem: Write a method called findSum
that has one parameter: an ArrayList
of Integers
. The method should return the sum of all of the elements in the array.
Algorithm:
Step 1: Create a variable called sum
and set it equal to zero
Step 2: Look at each of the elements in the list
Step 3: Add the element to the sum
Step 4: Continue until you reach the end of the list
Step 5: Return the sum
Pseudocode:
Java code 1: Using an ArrayList
(for-each
loop)
ArrayList
(for
loop)What is the highest score on your favorite video game? As more people play a game, how does the computer figure out what is the highest score in the list?
Algorithm:
Step 1: Create a variable called high
and set it to the first element in the list
Step 2: Look at each of the scores in the list
Step 3: If the score is greater than the high score, then make it be the new high score
Step 4: Continue until you reach the end of the list
Step 5: Return the high score
Pseudocode:
Java code 1: Using an ArrayList
(for-each
loop)
Java code 2: Using an ArrayList
(for
loop)
There is an alternative solution to the high/low problem that you should know. To execute this alternative, we modify the first step in the previous algorithm.
high
and set it to a really, really small number.This algorithm works as long as the really, really small number is guaranteed to be smaller than at least one of the numbers in the list. In Java, we can use the public fields from the Integer
class to solve this problem.
Likewise, to solve the find-lowest problem, you could set the low to be a really, really big number.
Searching for the Smallest Item in a List
If we changed the previous example to find the lowest score in the list, then the comparator in the if-statement would be changed to less than, <, instead of greater than, >.
You have been hired by the high school baseball team to write a program that calculates statistics for the players on the team. You decide to have a class called BaseballPlayer
. Every BaseballPlayer
has a name, a numberOfHits, and a numberOfAtBats. The BaseballRunner
has an array of BaseballPlayer
objects called roster. Your goal is to find the team batting average.
Algorithm:
Step 1: Create a variable called totalHits
and set it equal to 0
Step 2: Create a variable called totalAtBats
and set it equal to 0
Step 3: Look at each player on the roster
Step 4: Get the number of hits for the player and add it to totalHits
Step 5: Get the number of atBats
for the player and add it to totalAtBats
Step 6: Continue until you reach the end of the list
Step 7: Compute the teamBattingAverage
by dividing the totalHits
by the totalAtBats
Step 8: Return the teamBattingAverage
Pseudocode:
Java Code 1: Java code using an array (for loop)
Java Code 2: Java code using an array (for-each
loop)
Java Code 3: Java code using an ArrayList
(for
loop)
Java Code 4: Java code using an ArrayList
(for-each
loop)
Algorithm:
Step 1: Create a variable called highestAverage
and assign it a really small number
Step 2: Create a variable called bestPlayer
and assign it the empty string
Step 3: Look at each of the players in the roster
Step 4: If the batting average of the player is greater than highestAverage
, then set the highestAverage
to be that player’s average and set bestPlayer
to be the name of the player
Step 5: Continue until you reach the end of the list
Step 6: Return the name of bestPlayer
Pseudocode:
Java Code 1: Java code using an array (for
loop)
Java Code 2: Java code using an array (for-each
loop)
ArrayList
(for
loop)Java Code 4: Java code using an ArrayList
(for-each
loop)
Twitter has become very popular and Twitter Sentiment Analysis has grown in popularity. The idea behind Twitter Sentiment is to pull emotions and/or draw conclusions from the tweets. A large collections of tweets can be used to make general conclusions of how people feel about something. The important words in the tweet are analyzed against a library of words to give a tweet a sentiment score.
One of the first steps in processing a tweet is to remove all of the words that don’t add any real value to the tweet. These words are called stop words, and this step is typically part of a phase called preprocessing. For this problem, your job is to remove all the stop words from the tweet. There are many different ways to find meaningless words, but for our example, the stop words will be all words that are three characters long or less.
ArrayList
Algorithm 1:
Step 1: Create a list called longWords
Step 2: Look at each word in the original list
Step 3: If the word is greater than three characters, add that word to longWords
Step 4: Continue until you reach the end of the original list
Step 5: Return longWords
Pseudocode 1:
create a list called longWords
ArrayList
(for-each
loop)This solution requires more work than the ArrayList
solution. Since we don’t know how big to make the array, we need to count how many words are greater than three characters before creating it.
Algorithm 2:
Step 1: Create a counter and set it to zero
Step 2: Look at each word in the original list
Step 3: If the length of the word is greater than three characters, add one to the counter
Step 4: Continue until you reach the end of the list
Step 5: Create an array called longWords that has a length of counter
Step 6: Create a variable that will be used as an index for longWords and set it to zero
Step 7: Look at each word in the original list
Step 8: If the length of the word is greater than three characters, add the word to longWords and also add one to the index that is used for longWords
Step 9: Continue until you reach the end of the list
Step 10: Return the longWords array
Pseudocode 2:
set counter = 0
create an array called longWords whose length is the same as counter
set index = 0
Java Code 2: Using an array (using a for-each
loop and a for
loop)
The idea of sorting is quite easy for humans to understand. In contrast, teaching a computer to sort items all by itself can be a challenge. Through the years, hundreds of sorting algorithms have been developed, and they have all been critiqued for their efficiency and memory usage. The AP Computer Science A Exam expects you to be able to read and analyze code that uses three main sorts: the Insertion Sort, the Selection Sort, and the Merge Sort (to be discussed in Unit 10).
The most important thing to remember is different sorting algorithms are good for different things. Some are easy to code, some use the CPU efficiently, some use memory efficiently, some are good at adding an element to a pre-sorted list, some don’t care whether the list is pre-sorted or not, and so on. Of our three algorithms, Merge Sort is the fastest, but it uses the most memory.
Recall the swapping algorithm that you learned in Unit 6: Array. It is used in some of the sorting algorithms in this concept.
Sorting Algorithms on the AP Computer Science A Exam
You will not have to write the full code for any of the sorting routines described in this unit in the Free-Response Section. You should, however, understand how each works because they might appear in the Multiple-Choice Section.
The Insertion Sort algorithm is similar to the natural way that people sort a list of numbers if they are given the numbers one at a time. For example, if you gave a person a series of number cards one at a time, the person could easily sort the numbers “on the fly” by inserting the card where it belonged as soon as the card was received. Insertion Sort is considered to be a relatively simple sort and works best on very small data sets.
To write the code that can automate this process on a list of numbers requires an algorithm that does a lot of comparing. Let’s do an example of how Insertion Sort sorts a list of numbers from smallest to largest.
This algorithm uses a temporary variable that I will call temp
. The first step is to put the number that is in the second position into the temporary variable (temp
). Compare temp
with the number in the first position. If temp
is less than the number in the first position, then move the number that is in the first position to the second position and put temp
in the first position. Now, the first pass is completed and the first two numbers are sorted from smallest to largest.
Next, put the number in the third position in temp
. Compare temp
to the number in the second position in the list. If temp
is less than the second number, move the second number into the third position and compare temp
to the number in the first position. If temp
is less than the number in the first position, move the number in the first position to the second position, and move temp
to the first position. Now, the second pass is completed and the first three numbers in the list are sorted. Continue this process until the last number is compared against all of the other numbers and inserted where it belongs.
I’ll Pass
A pass in programming is one iteration of a process. Each of these sorts makes a series of passes before it completes the sort. An efficient algorithm uses the smallest number of passes that it can.
The following class contains a method that sorts an array of integers from smallest to greatest using the Insertion Sort algorithm. Note, an ArrayList
could have also been used.
The Selection Sort algorithm forms a sorted list by repeatedly finding and selecting the smallest item in a list and putting it in its proper place.
To sort a list of numbers from smallest to largest using Selection Sort, search the entire list for the smallest item, select it, and swap it with the first item in the list (the two numbers change positions). This completes the first pass. Next, search for the smallest item in the remaining list (not including the first item), select it, and swap it with the item in the second position. This completes the second pass. Then, search for the smallest item in the remaining list (not including the first or second items), select it, and swap it with the item in the third position. Repeat this process until the last item in the list becomes (automatically) the largest item in the list.
The following class contains a method that sorts an array of integers from smallest to greatest using the Selection Sort algorithm. Note, an ArrayList
could have also been used.
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 farther 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.
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.
• If you need to remove elements from an ArrayList
, you may consider starting at the end of the list and working toward the beginning.
• An algorithm is a sequence of steps that, when followed, produces a specific result.
• Algorithms are an extremely important component of software development since you are teaching the computer how to do something all by itself.
• There is an infinite number of algorithms.
• Pseudocode is a hybrid between an algorithm and real code.
• Pseudocode does not use correct syntax and is not typed into an IDE.
• Pseudocode helps you translate an algorithm into real code since it is code-like and more refined than an algorithm.
• Programmers translate algorithms into pseudocode and then translate pseudocode into real code.
• The process of developing an original algorithm requires concentration and analytical thought.
• Accessing data buried within a class hierarchy requires the programmer to use the methods that belong to the class.
• The copy algorithm is used to create a duplicate version of a data structure.
• It looks at each element in the original list and assigns it to the duplicate list.
• The duplicate is not an alias of the original; it is a new object that contains all of the same values as the original.
• The sequential search algorithm searches a list to find a search target.
• It looks at each element in the list one at a time comparing the element to the search target.
• If the element is not found, -1 is usually returned.
• The accumulate algorithm finds the sum of all the items in a list.
• It looks at each element in the list one at a time, adding the value to a total.
• The find-highest algorithm finds the largest value in a list.
• It looks at each element in the list one at a time, comparing the value to the current high value.
• Common ways to implement this algorithm include initializing the highest value with the first value in the list or to an extremely small negative number.
• The find-highest algorithm can be modified to find the lowest item in a list.
• Insertion Sort uses an algorithm that repeatedly compares the next number in the list to the previously sorted numbers in the list and inserts it where it belongs.
• Selection Sort uses an algorithm that repeatedly selects the smallest number in a list and swaps it with the current element in the list.
1. Assume that cities is an ArrayList<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"]
2. 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
Questions 3-6 refer to the following information.
Array arr
has been defined and initialized as follows
3. Which of the following shows the elements of the array in the correct order after the first pass through the outer loop of the Insertion Sort algorithm?
(A) 1 5 3 8 6 4 2 7
(B) 1 3 8 5 6 4 2 7
(C) 5 3 7 1 6 4 2 8
(D) 3 5 8 1 6 4 2 7
(E) 1 2 3 4 5 6 7 8
4. Which of the following shows the elements of the array in the correct order after the fourth pass through the outer loop of the Insertion Sort algorithm?
(A) 1 3 5 6 8 4 2 7
(B) 1 2 3 4 6 5 8 7
(C) 1 2 3 4 5 6 7 8
(D) 3 5 8 1 6 4 2 7
(E) 1 2 3 4 5 6 8 7
5. Which of the following shows the elements of the array in the correct order after the first pass through the outer loop of the Selection Sort algorithm?
(A) 1 2 3 5 6 4 8 7
(B) 1 3 8 5 6 4 2 7
(C) 1 3 5 8 6 4 2 7
(D) 1 5 3 8 6 4 2 7
(E) 5 3 1 6 4 2 7 8
6. Which of the following shows the elements of the array in the correct order after the fourth pass through the outer loop of the Selection Sort algorithm?
(A) 3 1 4 2 5 6 7 8
(B) 3 1 4 2 5 8 6 7
(C) 1 2 3 4 5 6 7 8
(D) 1 2 3 4 5 8 6 7
(E) 1 2 3 4 6 5 8 7
7. 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
8. Assume that msg
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)
I.
II.
III.
(A) I only
(B) I and II only
(C) II and III only
(D) I and III only
(E) I, II, and III
9. Consider the following code segment that implements the Insertion Sort algorithm.
Which of the following can be used to replace /* condition */
so that insertionSort
will work as intended?
(A) arr[i] > key
(B) arr[j] > key
(C) arr[i + 1] > key
(D) arr[j + 1] > key
(E) arr[i - 1] > key
10. Determine if the numbers in an ArrayList
are always increasing.
Write a method that determines if the values in an ArrayList
are always increasing. The method takes one parameter: an ArrayList
of Integer
. The method returns true if the elements in the array are continually increasing and false if the elements are not continually increasing.
The ArrayList
passed to the method:
11. Determine if the rate is increasing.
If a stock price is increasing, that means the value of it is going up. If the rate that the stock price is increasing is increasing, it means that the price is rising at a faster rate than it was the day before. Write a method that determines if the rate at which a stock price increases is increasing. The method has one parameter: an ArrayList
of Double values that represent the stock prices. Return true if the rate that the stock is increasing is increasing, and false if the rate is not increasing.
stockPrices contains the following:
12. Count the empty lockers.
A high school has a specific number of lockers so students can store their belongings. The office staff wants to know how many of the lockers are empty so they can assign these lockers to new students. Consider the following classes and complete the implementation for the countEmptyLockers
method.
Bullets mark each step in the process of arriving at the correct solution.
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:
2. 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
.
3. The answer is D.
• Our array starts as:
• The 5 is bigger than everything to its left (which is nothing), so let it be. Our algorithm starts with the 3.
• Take out the 3 and store it in a variable: tempKey = 3. Now we have a gap.
• Is 3 < 5? Yes, so move the 5 to the right.
• There’s nothing more to check, so pop the 3 into the open space the 5 left behind.
• That’s the order after the first pass through the loop (question 3).
4. The answer is A.
• We start where we left off at the end of question 3.
• Now for the second pass. The 3 and 5 are in order; tempKey = 8, leaving a gap.
• Since 5 < 8, we put the 8 back into its original spot.
• Now for the third pass: 3, 5, 8 are sorted; tempKey = 1, leaving a gap.
• 1 < 8, move 8 into the space 1 left behind. 1 < 5, move 5 over. 1 < 3, move 3 over, and put 1 in the first spot.
• Now for the fourth pass: 1, 3, 5, 8 are sorted; tempKey = 6, leaving a gap.
• 6 < 8, move the 8 into the space 6 left behind. 5 < 6, so we’ve found the spot for 6 and we pop it in.
• Giving us the answer to question 4.
• Note: One thing to look for in the answers when trying to recognize Insertion Sort—the end of the array doesn’t change until it is ready to be sorted. So the 4 2 7 in our example are in the same order that they were in at the beginning.
5. The answer is B.
• Our array starts as:
• We scan the array to find the smallest element: 1.
• Now swap the 1 and the 5.
• That’s the order after the first pass through the loop (question 5).
6. The answer is E.
• We start where we left off at the end of question 5.
• Now for the second pass. Leave the 1 alone and scan for the smallest remaining item:
• The 3 is in the spot the 2 needs to go into, so swap the 3 and the 2.
• The third pass swaps the 8 and the 3.
• The fourth pass swaps the 5 and the 4.
• This gives us the answer to question 6.
7. 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.
8. 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.
9. The answer is B.
• There are many small alterations possible when writing any algorithm. Do you go from 1 to length or from 0 to length -1, for example. This algorithm makes those kinds of alterations to the version given in the text. But in all cases, the general approach is:
• The outer loop goes through the array. Everything to the left of the outer loop index (i in this case) is sorted.
• Take the next element and put it into a temporary variable (key in this case).
• Look at the element to the left of the element you are working on. If it is larger than the element to be sorted, move it over. Keep doing that until you find an element that is smaller than the element to be sorted (this is the condition we need).
• Now you’ve found where our element needs to go. Exit inner loop and pop the element into place.
• So the condition we are looking for reflects keep doing that until we find an element that is smaller than the element to be sorted, or, phrasing it like a while
loop (“as long as” instead of “until”), keep going as long as the element we are looking at is larger than our key. In code, we want to keep going as long as arr[j] > key, so that’s our condition.
10. Determine if the numbers in an ArrayList
are always increasing.
Algorithm:
Step 1: Look at each of the scores in the list starting at the second element
Step 2: If the first score is less than or equal to the second score, then return false
Step 3: Advance to the next element and continue until you reach the end of the list
Step 4: Return true
Pseudocode:
Java code:
11. Determine if the rate is increasing.
Algorithm:
Step 1: Iterate through the parameter array starting at the third element
Step 2: If (the third element minus the second element) is less than or equal to the (second element minus the first element), then return false
Step 3: Move onto the next element and go to Step 2 (and adjust the elements #s)
Step 4: If you get this far without returning, return true
Pseudocode:
Java code:
12. Count the empty lockers.
Algorithm:
Step 1: Create a variable called total
and set it to zero
Step 2: Look at each of the lockers in the list
Step 3: If the locker is not in use, increment the total
Step 4: Continue until you reach the end of the list
Step 5: Return the total
Pseudocode:
Java Code: Java code using an array (for-each
loop)