APCSP Algorithms and Programming 2 — Questions and Answers
Question 1: Which of the following best describes an undecidable problem in computer science?
- A problem that takes too long to solve
- A problem for which no algorithm can always produce a correct yes/no answer (Correct answer)
- A problem with more than one correct solution
- A problem that requires parallel processing to solve
Correct answer: A problem for which no algorithm can always produce a correct yes/no answer
An undecidable problem is one for which no algorithm can be written that will always correctly determine a yes or no answer for all possible inputs.
Question 2: A programmer writes a procedure that calls itself. What is this technique called?
- Iteration
- Recursion (Correct answer)
- Abstraction
- Decomposition
Correct answer: Recursion
Recursion is a programming technique where a procedure calls itself to solve smaller instances of the same problem.
Question 3: What is the result of evaluating the Boolean expression: NOT (TRUE AND FALSE)?
- TRUE (Correct answer)
- FALSE
- Undefined
- NULL
Correct answer: TRUE
TRUE AND FALSE evaluates to FALSE, and NOT FALSE evaluates to TRUE.
Question 4: A list contains [3, 7, 1, 9, 4]. After one pass of a selection sort (finding and placing the minimum), what does the list look like?
- [1, 7, 3, 9, 4] (Correct answer)
- [1, 3, 7, 9, 4]
- [3, 1, 7, 9, 4]
- [1, 7, 9, 4, 3]
Correct answer: [1, 7, 3, 9, 4]
Selection sort finds the minimum (1) and swaps it with the first element (3), yielding [1, 7, 3, 9, 4].
Question 5: Which of the following is an example of a heuristic approach to solving a problem?
- Using a mathematical proof to verify correctness
- Using a lookup table with precomputed results
- Using a 'good enough' approximation strategy when an exact solution is impractical (Correct answer)
- Using a recursive algorithm to find all solutions
Correct answer: Using a 'good enough' approximation strategy when an exact solution is impractical
A heuristic is a problem-solving approach that finds an approximate solution quickly when finding the exact solution would be too time-consuming.
Question 6: In a programming language, what does the MOD operator return?
- The quotient of integer division
- The absolute value of a number
- The remainder after integer division (Correct answer)
- The product of two numbers modulo 10
Correct answer: The remainder after integer division
The MOD operator returns the remainder after dividing one integer by another (e.g., 17 MOD 5 = 2).
Question 7: Which traversal strategy visits all neighbors of a node before moving to the next level in a graph or tree?
- Depth-first search
- Breadth-first search (Correct answer)
- Binary search
- Linear search
Correct answer: Breadth-first search
Breadth-first search (BFS) explores all nodes at the current depth before advancing to nodes at the next depth level.
APCSP Algorithms and Programming 2
Which of the following best describes an undecidable problem in computer science?