Skip to content
Marlbridge
Free trial

Flashcards · AP® Computer Science A · Unit 2

Unit 2: Selection and Iteration flashcards

66 cards on topics 2.1 to 2.12. 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 66 cards

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

2.1 Algorithms with Selection and Repetition

What are the three building blocks of an algorithm?
Sequencing (steps in order), selection (a true or false decision picks a path) and repetition (a process repeats until a desired outcome is reached).
How do selection and repetition differ?
Selection asks its question once and chooses a path. Repetition asks again and again, and needs a stopping condition with something moving toward it.
What does nesting change in an algorithm?
A decision inside a loop is asked on every pass. A loop inside a decision runs only if the decision comes out the right way.
What is the most common pattern combining selection and repetition?
A selection inside a repetition: go through every item and act only on some of them.
Why must an algorithm's steps be precise?
Anyone following precise steps gets the same result, and the algorithm must finish after a finite number of steps. Vague steps cannot be coded.

2.2 Boolean Expressions

What are the relational operators and what type do they produce?
==, !=, <, >, <= and >=. A relational expression always has type boolean. The ordering operators are used with numeric values only.
Which operator goes with the words at least, at most, more than and fewer than?
At least is >=, at most is <=, more than is >, fewer than is <. Exactly is == and different is !=.
How do you test whether n is a multiple of k?
n % k == 0. For an even number use n % 2 == 0.
Why is 3 < x < 9 invalid, and what replaces it?
Comparisons cannot be chained in Java. Write x > 3 && x < 9.
How should two double values be tested for being close?
Do not use == on computed doubles. Use Math.abs(x - y) < tolerance for a small tolerance value.
What is the value of m / (double) k > 3.5 for m = 14 and k = 4?
false. The division is 14 / 4.0 = 3.5, and 3.5 > 3.5 is false. The arithmetic is finished before the relational operator is applied.

2.3 if Statements

What is the difference between a one-way if and an if-else?
A one-way if runs its body only when the condition is true. An if-else runs exactly one of two bodies, the first if the condition is true, otherwise the second.
What is the difference between two separate ifs and an if-else?
Two separate ifs test both conditions, so both bodies, one or neither can run. An if-else runs exactly one body.
What goes wrong with if (x > 5); { ... } ?
The semicolon ends the if with an empty body, so the braces that follow always run. Never put a semicolon straight after the condition.
Why use braces on an if body?
Without braces only the one next statement belongs to the if, whatever the indentation suggests. Braces make the whole block conditional.
After if (order > stock) { order = stock; } stock = stock - order; with stock 3 and order 5, what are the values?
order becomes 3 and stock becomes 0. The condition 5 > 3 is true, so the body runs, and then the next statement uses the updated order.

2.4 Nested if Statements

How does an if-else-if chain run?
Conditions are tested top to bottom and the first true one runs; the rest are skipped. At most one body runs, and a trailing else runs only if all were false.
Why does the order of conditions in a chain matter?
A later condition is reached only if all earlier ones were false. Put the most specific or demanding condition first, or a low band will catch high values.
What is the difference between a chain and separate ifs?
In a chain at most one body runs. With separate ifs every condition is tested, and later bodies can overwrite what earlier ones set.
Which if does an else pair with (dangling else)?
The nearest unmatched if, whatever the indentation. Braces make the pairing explicit.
What must hold for a variable used after an if structure to compile?
Every path must assign it. Leaving off the final else can leave a variable unassigned on some path, which is a compile-time error.

2.5 Compound Boolean Expressions

What do !, && and || mean?
! is not, && is true when both sides are true, and || is true when at least one side is true. They combine Boolean expressions into one boolean value.
What is the precedence of the logical operators?
After arithmetic and relational operators: ! first, then &&, then ||. Use brackets wherever grouping could be misread.
What is short-circuit evaluation?
For &&, if the left side is false the right side is not evaluated. For ||, if the left side is true the right side is skipped.
Why is d != 0 && n / d > 2 safe but the reverse order is not?
With the guard first, a false d != 0 skips the division. In the reverse order the division runs first, and when d is 0 it throws an ArithmeticException.
How do you write inside a range and outside a range?
Inside: x >= lo && x <= hi. Outside: x < lo || x > hi. Using || for a range gives an always-true condition.
Why is x == 1 || 2 wrong?
Each side of || must be a Boolean expression, and 2 is an int. Write x == 1 || x == 2.

2.6 Comparing Boolean Expressions

What are De Morgan's laws?
!(a && b) is equivalent to !a || !b, and !(a || b) is equivalent to !a && !b. Negate each part and swap && with ||.
What is the complement of x < y, and of x == y?
!(x < y) is x >= y, and !(x == y) is x != y. Do not use > as the complement of <, because it leaves out equality.
How do you prove or disprove that two Boolean expressions are equivalent?
A truth table giving the same value in every row proves it. One row with different values disproves it. Matching on one or two cases proves nothing.
What do == and equals compare for objects?
== compares references, true only if both name the same object. equals compares contents, as with the characters of two Strings.
Why do two Strings with the same text sometimes fail ==?
They can be different objects holding equal text. == asks whether they are the same object, so use equals for the text.
How do you safely test a String that might be null?
Check for null first with short-circuit: s != null && s.length() > 0. Calling a method on a null reference throws a NullPointerException.

2.7 while Loops

How does a while loop run?
The condition is tested before every iteration, including the first. If it is false at the start the body never runs, and the loop ends when a test finds it false.
How many times is a while condition tested compared with the body?
One more time than the body runs. If the body runs three times the condition was tested four times.
What causes an infinite loop?
A condition that is always true: the loop variable is never updated, or is updated in the wrong direction.
What value does the loop variable hold after a while loop ends?
The first value that made the condition false, not the last value processed.
What are the correct starting values for a sum and a product accumulator?
0 for a sum and 1 for a product. Declare the accumulator before the loop and update it inside.
What do x = 3, product = 1; while (x > 0) { product = product * x; x--; } leave?
product is 6 and x is 0. The body runs three times and the condition is tested four times.

2.8 for Loops

What are the three parts of a for header and when does each run?
Initialization runs once before the first test. The Boolean expression is tested before every iteration. The update runs after the whole body, before the next test.
How many times does for (int i = 0; i < n; i++) run its body?
Exactly n times, with i taking the values 0 to n - 1. With i starting at 1 and i <= n it is also n times.
What is the scope of a variable declared in a for header?
Only the loop. It is out of scope afterwards, so code after the loop cannot refer to it.
How do you write a for loop as an equivalent while loop?
Put the initialization before the loop, the test in the while brackets and the update as the last statement of the body.
What does a semicolon right after a for header do?
It makes the loop body empty, so the braces after it run once after the loop finishes instead of on each pass.
What is result after for (int k = 5; k > 0; k -= 2) { result = result * 10 + k; } from 0?
531. The loop uses k = 5, 3 and 1, so result is 5, then 53, then 531, and the test with k = -1 is false.

2.9 Implementing Selection and Iteration Algorithms

How do you find the minimum and maximum in a loop, and where do you start them?
Compare each value: if (v < min) min = v; and if (v > max) max = v;. Start min at Integer.MAX_VALUE (or the first value) and max at Integer.MIN_VALUE (or the first value), never at 0.
How do you take the digits of a positive int apart?
While n > 0, n % 10 is the last digit and n = n / 10 removes it. To reverse a number use rev = rev * 10 + n % 10; inside the loop.
How do you compute an average without losing the fraction?
Cast before dividing: (double) sum / count. Dividing two ints gives integer division.
What is the standard count (frequency) pattern?
Set count to 0 before the loop, and inside the loop write if (criterion) { count++; }. The accumulator is declared before the loop and used after it.
How do you test whether n is prime?
n is not prime if n < 2, or if any d from 2 up to n - 1 divides n (n % d == 0). If no such d exists it is prime.

2.10 Implementing String Algorithms

How do you visit every character of a String s?
for (int i = 0; i < s.length(); i++) with s.substring(i, i + 1) for the one-character String. Running to i <= s.length() causes an exception.
How do you check whether a letter is a vowel?
"aeiou".indexOf(letter) >= 0. Use >= 0, not > 0, because index 0 is a valid position.
What is the loop for a window of length k?
for (int i = 0; i <= s.length() - k; i++) with s.substring(i, i + k). The last start index is s.length() - k, so the test must be <=.
How do you build a String in order, and reversed?
In order: result = result + piece; Reversed: result = piece + result; (prepending). Strings are immutable, so you must assign the new String.
How do you test for a palindrome?
Build the reverse of the String and compare with equals: s.equals(reverse(s)). Do not use ==.

2.11 Nested Iteration

What is nested iteration and how does it run?
A loop inside the body of another loop. Each time the outer loop runs once, the inner loop completes all its iterations, then restarts for the next outer pass.
How many times does the innermost statement run when the loop bounds are independent?
(outer count) x (inner count). For 3 outer and 4 inner passes it runs 12 times.
How many times does the inner body run for i = 1 to n with j = 1 to i?
1 + 2 + ... + n = n(n + 1) / 2. If the inner loop starts at j = i + 1 the count is n(n - 1) / 2.
Where does System.out.println() go to print a grid row by row?
After the inner loop, inside the outer loop body, so each outer pass ends one row. Inside the inner loop gives one item per line; after the outer loop gives one long line.
What does total become after for i = 1 to 3 with inner for j = 1 to i adding j?
10. The inner passes add 1, then 1 + 2, then 1 + 2 + 3, so total goes 1, 4, 10 and the inner statement runs 6 times.

2.12 Informal Run-Time Analysis

What is a statement execution count?
The number of times a statement runs, found by tracing and analysing the loops. It is used to compare the work done by different code.
For for (int i = 0; i < n; i++), how many times do the test and the body run?
The Boolean test runs n + 1 times, the body n times, the update n times and the initialization once.
How many times does count++ run in a loop over i < n with an inner loop j < 4?
4n times, because the inner bound is fixed. For n = 10 that is 40, and doubling n doubles the work.
How does the count change if the inner bound is j < n?
It becomes n x n, so for n = 10 it is 100 and for n = 20 it is 400. Doubling n quadruples the work.
How many passes does a loop that halves n (n = n / 2) or doubles i (i *= 2) make?
About log base 2 of n passes. For n = 1000 there are about 9 halvings, so the work grows very slowly as n grows.
Why can a return inside a loop change the execution count?
An early exit stops the loop sooner, so the count lies between a best case and a worst case that depends on the data.

Study Unit 2 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.