Skip to content
Marlbridge
Free trial

Flashcards · AP® Computer Science A · Unit 4

Unit 4: Data Collections flashcards

104 cards on topics 4.1 to 4.17. Pick a topic or study the whole unit.

Study mode needs JavaScript. Every card is listed below, so you can still cover the answers and test yourself.

All 104 cards

For a quick read-through or printing. Cover the right-hand side to test yourself.

4.1 Ethical and Social Issues Around Data Collection

What is algorithmic bias?
Systemic and repeated errors in a program that create unfair outcomes for a specific group of users. A one-off bug that does not target a group is not algorithmic bias.
How can the way data are collected cause bias?
Some people are missing or over-represented. For example voluntary app data leaves out people without devices, so a program tuned on it can repeatedly serve those groups worse.
What can go wrong if a data set is incomplete or inaccurate?
A program using it can work incorrectly or inefficiently. For example a code such as -999 for no reading, averaged as a real value, gives a badly wrong mean.
Why might a data set be unsuitable for a different question?
It describes only the group and topic it was collected for. Adult data cannot answer a question about school students, however large the data set is.
How can programmers safeguard users' personal privacy?
Collect only the data that is needed, store it securely and not for longer than necessary, and say clearly what is collected and why.
What should a good answer about a harm or issue include?
Who is affected and why, not just the name of the harm. A large data set is not automatically fair, so check who the data represents.

4.2 Introduction to Using Data Sets

What is a data set and how are data sets used in a program?
A collection of specific pieces of information. Values are accessed one at a time and processed to give the outcome wanted, such as a count, total, largest or average.
What are the three steps of a plan to process a data set?
Set up what must be remembered, repeat for each value (examine it and update what is remembered), then report the answer after all the values have been processed.
Where must a count or total be set up in a plan?
Before the repeated part, starting at 0. Resetting it inside the repeated part loses the earlier values, so only the last reading is counted.
How does the plan for the largest value in a data set start?
Start the best so far from the first value, and replace it whenever a value is larger. Starting at 0 fails for data that can be negative.
For rainfall 0, 12, 5, 20, 0, 8, 15, what are the count of at least 10, the total and the mean?
Three days have at least 10 (12, 20, 15), the total is 60 and the mean is 60 / 7, about 8.57. A trace table with a column per remembered value checks it.

4.3 Array Creation and Access

What does an array store, and can its length change?
Multiple values of the same type, primitives or object references. The length is fixed when the array is created and is read with the length attribute, with no parentheses.
What are the default values of a new array's elements?
0 for int, 0.0 for double, false for boolean and null for String or any other reference type.
What are the valid indices of an array, and what happens outside them?
0 through length - 1. An index outside that range throws an ArrayIndexOutOfBoundsException at run time.
How do you create an array with an initializer list?
Write the values in braces: int[] scores = {72, 65, 90};. It creates the array and fills it in one statement, and the length is the number of values.
What does w[w[0]] = 8; do when w[0] is 3?
It stores 8 in w[3]. When an index is itself an array element, the inner one is evaluated first.
How do you swap two array elements?
Use a temporary variable: int temp = v[0]; v[0] = v[2]; v[2] = temp;. Without it one value is overwritten and lost.
Why is scores.length() wrong for an array?
For an array length is an attribute, not a method, so it has no parentheses. Writing length() is a compile-time error. A String uses length() and an ArrayList uses size().

4.4 Array Traversals

What is the standard indexed loop over an array a?
for (int i = 0; i < a.length; i++). The test uses < with length because the last valid index is a.length - 1.
What does the enhanced for loop for (int v : a) do?
It gives v a copy of each element in turn, with no index. Assigning a new value to v does not change the array.
When must you use an indexed loop instead of an enhanced for loop?
When you need to change stored primitive values with a[i] = ..., or when you need the position of an element, or to go backward or skip elements.
For an array of objects, what can the enhanced for loop variable do?
Calling a method on it can change the object's state, which is shared. It cannot change which references are stored in the array.
How do you traverse an array from last to first?
for (int i = a.length - 1; i >= 0; i--). Every other element is for (int i = 0; i < a.length; i += 2).
What does doubling each element in an enhanced for loop do to {3, 8, 1, 6}?
Nothing: the array stays 3 8 1 6, because the loop variable is a copy. With a[i] = a[i] * 2 in an indexed loop it becomes 6 16 2 12.

4.5 Implementing Array Algorithms

How do you find the maximum of an array, and where does the best start?
Keep a best so far, started at a[0], and loop from index 1 replacing it when a[i] is larger. Do not start at 0, which fails for negative data.
How do you write an any (at least one) test and an all test?
Any: return true inside the loop on the first match, and return false after the loop. All: return false inside the loop on the first failure, and return true after the loop.
How do you compare consecutive elements of an array?
Compare a[i] with a[i + 1] and loop with i < a.length - 1. Using i < a.length reads a[i + 1] past the end and throws an exception.
How do you rotate an array left by one position?
Save a[0], copy a[i + 1] into a[i] for i up to length - 2, then put the saved value in a[length - 1]. Rotating {1, 2, 3, 4, 5} left gives 2 3 4 5 1.
How do you reverse an array in place?
Swap a[i] with a[length - 1 - i] for i < length / 2. Looping over the whole array swaps every pair twice and restores the original order.
How do you find duplicates in an array?
Use nested loops where the inner index j starts at i + 1, so an element is never compared with itself. Return true on the first equal pair.
How do you compute an average of an int array?
Sum from 0, then divide as a double: (double) total / a.length. Two ints divide with integer division and lose the fraction.

4.6 Using Text Files

How does a program read a text file with Scanner?
Create a File from the file name and a Scanner from that File, loop while in.hasNext(), read with next, nextInt, nextDouble or nextLine, then call close. Reading is forward only.
What must the method have, and what must be imported, to read a file?
The method header needs throws IOException. File and IOException come from java.io and Scanner from java.util, so both need import statements.
What does hasNext do, and what does next do?
hasNext only looks: it reports whether another token exists without moving the cursor. next returns the next token as a String, stopping at whitespace.
What happens if nextInt meets a token that is not an int?
It throws an InputMismatchException at run time. nextInt reads one token, not a whole line.
What does split(String del) do?
It returns a String array of the pieces around del. Trailing empty pieces are dropped, so "a,b,,".split(",") has two elements.
How many times does while (in.hasNext()) { total += in.nextInt(); } run?
Once per token, not once per line. A file with lines 12 0 7, 3 25 and 0 8 1 gives eight passes and a total of 56.

4.7 Wrapper Classes

What are wrapper classes?
Integer and Double, in java.lang, each holding one int or one double. They are immutable objects, so no import is needed.
What are autoboxing and unboxing?
Autoboxing converts a primitive to its wrapper automatically, as in Integer a = 5;. Unboxing converts a wrapper to a primitive automatically, as in int b = a + 3;.
Why does Double d = 7; not compile?
Autoboxing works only from int to Integer and double to Double. An int cannot box to a Double, so write 7.0 or declare a double.
What do Integer.parseInt and Double.parseDouble do?
They convert a String to an int or a double. Integer.parseInt("42") is 42 and Double.parseDouble("4") is 4.0. Text that is not a valid number, such as "12a", throws a NumberFormatException.
What is Integer 10 divided by Integer 3?
3. The wrappers are unboxed first, so the division is integer division. Arithmetic on wrapper objects uses the primitive rules.
What happens when you unbox a null wrapper?
A NullPointerException is thrown, as in Integer z = null; int w = z;. Compare wrapper values with equals, not ==.

4.8 ArrayList Methods

How do you create an ArrayList and what types may it hold?
Write new ArrayList, the element type in angle brackets, then (), which creates an empty list. The element type must be an object type such as String or Integer, never int. It needs import java.util.ArrayList.
What do size, get and set do?
size() gives the number of elements, get(i) returns the element at index i, and set(i, obj) replaces it and returns the old element. None of them changes the size.
What is the difference between add(obj) and add(index, obj)?
add(obj) appends at the end and returns true. add(index, obj) inserts at the index, shifts later elements right, and the size goes up by 1.
What does remove(index) do?
It removes the element at the index, shifts later elements left, reduces the size by 1 and returns the removed element.
What is the valid index range for get, set, remove and add?
get, set and remove need 0 to size() - 1. add(index, obj) allows 0 to size(). Anything else throws an IndexOutOfBoundsException.
What is the final list after add(4), add(8), add(0, 1), set(1, get(2) + 5), remove(0)?
[13, 8]. The list goes [4], [4, 8], [1, 4, 8], [1, 13, 8] (get(2) is 8), then [13, 8] after removing index 0.
Why are length, length() and [ ] wrong for an ArrayList?
An ArrayList is not an array or a String. Use size() for the count and get(i) to read an element.

4.9 ArrayList Traversals

What is the standard indexed loop for an ArrayList?
for (int i = 0; i < list.size(); i++) with list.get(i). Using i <= list.size() throws an IndexOutOfBoundsException on the last pass.
Why does a forward loop that calls remove(i) skip elements?
After remove(i), later elements shift left, so the next element is now at index i, but the loop moves on to i + 1. Adjacent matches such as -1, -2 are missed.
How do you safely remove matching elements in a traversal?
Loop backward from size() - 1 to 0, or use a while loop that adds 1 to i only when nothing was removed.
Why should you not add or remove inside an enhanced for loop over a list?
It may throw a ConcurrentModificationException. Reading and replacing with get and set are safe during a traversal, but adding and removing change the size.
What does removing the negatives from [3, -1, -2, 5, -4] give with a forward remove(i) loop and with a backward loop?
The forward loop gives [3, -2, 5], because -2 is skipped. The backward loop gives the correct [3, 5]. Test deletion code with adjacent matches.
What does assigning to the enhanced for variable do to a list?
Nothing to the list. The variable is a copy of the element reference. To replace elements use set(i, x) in an indexed loop.

4.10 Implementing ArrayList Algorithms

How do you find the maximum of an ArrayList?
Start max at list.get(0), loop from i = 1, and replace max when list.get(i) is larger. The list must not be empty.
How do you compute the average of an ArrayList safely?
Cast before dividing, (double) sum / list.size(), and guard against size() == 0. Without the cast the quotient is an int.
How do you insert a value into a sorted list so it stays sorted?
Find the index with while (i < list.size() && list.get(i) < value) i++, then call list.add(i, value). The size test must come first.
How do you rotate an ArrayList left, and right?
Left: list.add(list.remove(0)). Right: list.add(0, list.remove(list.size() - 1)).
How do you reverse an ArrayList in place?
Swap elements i and size() - 1 - i for i < size() / 2. Looping to size() swaps every pair twice and leaves the list unchanged.
How do you look at consecutive pairs in an ArrayList?
Loop with i < list.size() - 1 and compare get(i) with get(i + 1). On [1, 3, 2, 5, 6] there are 3 increasing pairs.

4.11 2D Array Creation and Access

What is a 2D array, and which index is the row?
An array of arrays: arr[row][col], first index row and second index column. Only rectangular arrays are used, and the size is fixed at creation.
How do you get the number of rows and columns of arr?
Rows: arr.length. Columns: arr[0].length (or arr[r].length). Using arr.length for the columns is a common mistake.
What does int[][] grid = new int[3][4]; create?
3 rows and 4 columns, with all 12 elements 0. The same default rule gives 0.0, false or null for other element types.
What is arr[r] for a 2D array, and is it a copy?
It is the 1D array for row r, held by reference. int[] row = m[1]; row[0] = 40; changes m[1][0], because the row is shared.
What exceptions can a 2D array cause?
ArrayIndexOutOfBoundsException for a row or column index out of range, and NullPointerException when you call a method on a null element, such as an unset String in a new String[][].
What does m[1][2] + m[0][1] give for m = {{1, 2, 3}, {4, 5, 6}}?
8, since m[1][2] is 6 and m[0][1] is 2. Row 1 is {4, 5, 6} and index 2 of it is 6.

4.12 2D Array Traversals

What are row-major and column-major traversal?
Row-major: the outer loop over rows and the inner over columns. Column-major: the outer loop over columns and the inner over rows. Access is always m[r][c].
What does each order print for {{1, 2, 3}, {4, 5, 6}}?
Row-major prints 1 2 3 4 5 6. Column-major prints 1 4 2 5 3 6. Nesting order changes the output order.
What are the loop bounds for rows and columns?
Rows: r < m.length. Columns: c < m[r].length (or m[0].length). Swapping them on a non-square array throws an ArrayIndexOutOfBoundsException.
What types are the variables in a nested enhanced for over an int[][] m?
The outer variable is an int[] (a whole row) and the inner is an int: for (int[] row : m) for (int v : row). Assigning to v does not change the array.
How do you reach the two diagonals of a square array m?
Main diagonal: m[i][i]. Other diagonal: m[i][m.length - 1 - i].
How big are the row sums array and the column sums array?
Row sums have length m.length and column sums have length m[0].length. Making a column-sums array of length m.length is a common mistake.

4.13 Implementing 2D Array Algorithms

How do you apply a 1D pattern to a 2D array?
Choose the pattern, then the region. A row is a loop over c with r fixed, a column is a loop over r with c fixed, and the whole table uses nested loops.
Where is the accumulator declared for a sum per row?
Inside the outer loop, so it resets for each row. Declared outside, it keeps adding across rows and gives a running total instead.
How do you find the maximum of a 2D array?
Start max at an existing element, m[0][0], then use nested loops and replace max whenever m[r][c] is larger. Starting at 0 fails for negative data.
How do you do an any or all test on a 2D array?
Any: return true inside the loops on the first match and return false after both loops. All: return false inside on the first failure and return true after both loops.
How do you rotate row r left?
Save m[r][0], copy m[r][c + 1] into m[r][c] for c < m[r].length - 1, then put the saved value in the last column. The first element must be saved before it is overwritten.
How do you check the neighbours of a cell?
Loop the row and column offsets -1 to 1, skip (0, 0), and check that the row and column are within bounds before reading, using && so the bounds test comes first.

4.14 Searching Algorithms

How does linear search work and what does it return?
It checks each element in order until it finds the target or reaches the end. The standard method returns the index of the first match from inside the loop and returns -1 after the loop.
Does linear search need sorted data?
No. It works on data in any order, and can start from either end. Starting from the end finds the last match.
What are the best and worst case comparisons for linear search of n elements?
Best case 1 comparison, when the target is first. Worst case n comparisons, when the target is last or absent. An unsuccessful search makes exactly n comparisons.
How do you compare Strings in a search?
Use list.get(i).equals(target), not ==. == compares references, so equal text in different objects would be missed.
What is wrong with a linear search that returns -1 in an else branch inside the loop?
It returns -1 as soon as the first element does not match. The return -1 must come after the loop, once every element has been checked.
How do you search a 2D array?
Search each row, or nest the loops and return from inside the inner loop with the row and column. Return a failure value only after both loops finish.

4.15 Sorting Algorithms

How does selection sort work?
Each pass finds the smallest element of the unsorted portion and swaps it into its correct, final position. After k passes the first k elements are final.
How does insertion sort work?
Each pass takes the next element and inserts it into its correct place among the sorted elements by shifting larger ones right. The sorted front part is in order but not necessarily final.
How do the comparison counts of selection and insertion sort differ?
Selection sort always makes n(n - 1) / 2 comparisons. Insertion sort makes n - 1 if already sorted and up to n(n - 1) / 2 if reversed, so sorted input is its best case.
What is the array after pass 1 and pass 2 of selection sort on {5, 2, 9, 1, 7}?
After pass 1: 1 2 9 5 7 (the 1 is swapped to the front). After pass 2: 1 2 9 5 7 (the 2 is already in place). Pass 3 gives 1 2 5 9 7.
What are common mistakes when writing selection and insertion sort?
A swap with no temporary variable, starting the inner search at 0 instead of i + 1, comparing a[j] to the index min instead of a[min], and testing a[j] > key before j >= 0.
How many passes does each sort make on n elements?
n - 1 passes. Selection sort runs i from 0 to n - 2. Insertion sort runs i from 1 to n - 1, and its first pass inserts the element at index 1.

4.16 Recursion

What are the two essential parts of a recursive method?
A base case that returns without calling the method again, and a recursive case that calls the method on a smaller or simpler argument. Without a reachable base case the result is a StackOverflowError.
Do recursive calls share their parameters and local variables?
No. Each call has its own set of parameters and local variables, so the value of n differs in each call.
How do you trace a recursive call such as fact(4)?
Expand the calls down to the base case, then substitute the returns back up: fact(4) is 4 * 3 * 2 * 1 = 24. Do not stop when the base case first returns.
What is the printing order for output placed before and after a recursive call?
Output before the call appears in call order, outermost first. Output after the call appears in reverse order, innermost first, so printing n before and after for n = 3 gives 3 2 1 1 2 3.
Why can two recursive calls make the number of calls grow quickly?
Each call can spawn two more. fib(4) makes 9 calls and fib(5) makes 15, including the base-case calls.
Does the course ask you to write recursive methods?
No. Writing recursive code is outside the course scope; tracing and understanding it is what is needed. Any recursive solution can also be written with a loop.

4.17 Recursive Searching and Sorting

What does binary search require?
Sorted data. It examines the middle element and discards half of the range each time, so it is typically more efficient than linear search.
How do you move the range in binary search?
Use mid = (low + high) / 2 with integer division. If a[mid] is less than the target set low = mid + 1; if greater set high = mid - 1. Stop with -1 when low > high.
How many steps does binary search take on {2, 5, 8, 11, 14, 17, 20, 23} for 17, and for 6?
17 is found at index 5 in 2 steps (mid 3 holds 11, then mid 5 holds 17). 6 is not found: mids 3, 1, 2 and then low > high gives -1 in 3 steps.
Why must low = mid + 1 and high = mid - 1 be used, not low = mid?
mid has already been checked. Setting low or high to mid can make the range stop shrinking and loop forever.
How does merge sort work?
It is recursive: divide the array until each piece has one element, then merge the sorted pieces back in order. The merge compares the fronts of two sorted lists and copies the smaller.
In what order does merge sort process {8, 3, 5, 1, 9, 2}?
It splits into [8, 3, 5] and [1, 9, 2], sorts the left half first (to [3, 5, 8]), then the right (to [1, 2, 9]), and merges them to [1, 2, 3, 5, 8, 9]. Elements are reordered only when merging.

Study Unit 4 further

AP® and Advanced Placement® are trademarks registered by the College Board, which is not affiliated with, and does not endorse, this website. Marlbridge is an independent tuition provider. It is not an authorized AP course provider, an AP school or an exam centre, and these resources are not official College Board materials. Reading them or doing simulations does not meet the laboratory requirement of an AP science course.