Worked Solutions · AP CSP-Feeder · US / ON / BC / AB Styles解题答案 · AP CSP 衔接 · 美 / 安 / 卑 / 阿省风格
Answer: (C) Abstraction答案：(C) 抽象 A1
Abstraction means stripping away irrelevant detail and keeping only what matters for the problem at hand. The student is choosing to store only temperature and precipitation because those are the only fields relevant to her forecasts. Wind speed, humidity, and UV index are real data, but they are not needed for this program's purpose, so they are abstracted away.抽象意味着去除无关细节，只保留解决当前问题所需的内容。该学生选择只存储温度和降水量，因为这些是对她的天气预报唯一相关的字段。风速、湿度和紫外线指数是真实数据，但对此程序的目的不需要，因此被抽象掉。
Distractors: Decomposition (A) breaks a problem into sub-problems, not data selection. Pattern recognition (B) identifies repeated structures. Algorithmic thinking (D) writes step sequences.干扰项：分解 (A) 将问题拆分为子问题，而非选择数据。模式识别 (B) 识别重复结构。算法思维 (D) 编写步骤序列。
Answer: (C) It violates the finiteness property because it never terminates答案：(C) 它违反了有限性属性，因为它永远不会终止 A1
A valid algorithm must satisfy three properties: finiteness (terminates after a finite number of steps), definiteness (every step is precisely defined), and effectiveness (every step can actually be executed). WHILE TRUE: OUTPUT "Hello" loops forever because the condition is always true and there is no break or exit mechanism. It produces output (so B is wrong) and uses valid pseudocode syntax (so A is wrong). Finiteness is the violated property.有效算法必须满足三个属性：有限性（经过有限步骤后终止）、确定性（每个步骤都精确定义）和有效性（每个步骤都可以实际执行）。WHILE TRUE: OUTPUT "Hello" 永远循环，因为条件始终为真且没有 break 或退出机制。它产生输出（所以 B 错误）并使用有效的伪代码语法（所以 A 错误）。有限性是被违反的属性。
The four standard flowchart shapes:四种标准流程图形状：
Two decision diamonds.两个判断菱形。 B1 The first diamond asks "is the number greater than 0?" and the second asks "does the number equal 0?". Each condition is a separate yes/no branch requiring its own diamond.第一个菱形问"数字是否大于 0？"，第二个问"数字是否等于 0？"。每个条件是独立的是/否分支，需要各自的菱形。 B1
Output: "Zero"输出："Zero" B1
When the input is 0: the first diamond ("number > 0?") evaluates to NO, so we proceed to the second diamond ("number == 0?") which evaluates to YES, sending us to the "Output Zero" parallelogram.当输入为 0 时：第一个菱形（"数字 > 0？"）评估为否，因此进入第二个菱形（"数字 == 0？"）评估为是，导向"输出 Zero"平行四边形。
Completed trace table (1 mark per correctly completed row, up to 4):完整追踪表（每行正确得 1 分，最多 4 分）：
| Line行 | a | b | c |
|---|---|---|---|
| Start初始 | - | - | - |
| 1 | 3 | - | - |
| 2 | 3 | 5 | - |
| 3 | 3 | 5 | 15 |
| 4 | 10 | 5 | 15 |
Working: Line 1: a = 3. Line 2: b = a + 2 = 3 + 2 = 5. Line 3: c = b * a = 5 * 3 = 15. Line 4: a = c - b = 15 - 5 = 10.过程：行 1：a = 3。行 2：b = a + 2 = 3 + 2 = 5。行 3：c = b * a = 5 * 3 = 15。行 4：a = c - b = 15 - 5 = 10。
Output: 10输出：10 B1
Input: none (values are hardcoded). Process: the four assignment statements that compute b, c, then the final value of a. Output: the value of a (10).输入：无（值已硬编码）。处理：计算 b、c 以及 a 最终值的四条赋值语句。输出：a 的值（10）。 B1
Trace table (1 mark per 2 correct rows, up to 3):追踪表（每 2 行正确得 1 分，最多 3 分）：
| Iter迭代 | i (before body)（循环体前） | i < 4?i < 4？ | total (after body)（循环体后） | i (after body)（循环体后） |
|---|---|---|---|---|
| 1 | 1 | TRUE | 1 | 2 |
| 2 | 2 | TRUE | 3 | 3 |
| 3 | 3 | TRUE | 6 | 4 |
| Check检查 | 4 | FALSE | exits退出 | 4 |
Actual output: 6实际输出：6 B1 (only 1 + 2 + 3 = 6 were summed; 4 was never added)（只计算了 1 + 2 + 3 = 6；4 从未被加入）
Error type: Logic error错误类型：逻辑错误 B1 -- the code runs without crashing but produces the wrong answer (6 instead of 10).-- 代码运行不崩溃但产生错误答案（6 而非 10）。
Fix: change WHILE i < 4 to WHILE i <= 4修复：将 WHILE i < 4 改为 WHILE i <= 4 B1 (or equivalently WHILE i < 5). This is a classic off-by-one error.（或等价地 WHILE i < 5）。这是经典的"差一"错误。
Accept any three of the following sub-problems (1 mark each, max 3):接受以下任意三个子问题（每个 1 分，最多 3 分）：
Data the program needs (accept any two):程序需要的数据（接受任意两个）：
Data the program does NOT need (accept any two):程序不需要的数据（接受任意两个）：
Input: a positive integer n.输入：正整数 n。 B1
Process: iterate through integers from 1 to n; for each odd integer, add it to a running total.处理：遍历从 1 到 n 的整数；对每个奇数，将其加到累计总和中。 B1
Output: the sum of all odd integers from 1 to n inclusive.输出：1 到 n（含）所有奇数之和。
Model answer (other correct pseudocode accepted). Award: 1 mark INPUT/OUTPUT present; 1 mark accumulator initialised to 0; 1 mark correct loop range; 1 mark correct odd check or step-by-2 logic.参考答案（接受其他正确伪代码）。评分：1 分 INPUT/OUTPUT 存在；1 分累加器初始化为 0；1 分正确循环范围；1 分正确奇数检查或步长为 2 逻辑。
Version A -- using modulo to check odd:版本 A -- 用取模检查奇数：
INPUT n
SET sum TO 0
SET i TO 1
WHILE i <= n:
IF i % 2 != 0 THEN
SET sum TO sum + i
END IF
SET i TO i + 1
END WHILE
OUTPUT sumVersion B -- stepping by 2 (more efficient):版本 B -- 步长为 2（更高效）：
INPUT n
SET sum TO 0
SET i TO 1
WHILE i <= n:
SET sum TO sum + i
SET i TO i + 2
END WHILE
OUTPUT sumTrace with n = 5 (using Version B for clarity). 1 mark for correct sequence of accumulator values; 1 mark for correct final answer.以 n = 5 追踪（使用版本 B）。1 分正确的累加器值序列；1 分正确最终答案。
| i | i <= 5?i <= 5？ | sum |
|---|---|---|
| Init初始 | - | 0 |
| 1 | TRUE | 1 |
| 3 | TRUE | 4 |
| 5 | TRUE | 9 |
| 7 | FALSE | exits退出 |
Output: 9. (Odd numbers from 1 to 5: 1 + 3 + 5 = 9.)输出：9。（1 到 5 的奇数：1 + 3 + 5 = 9。）
List: [3, 9, 15, 22, 31, 44, 57, 71, 83, 96] (indices 0-9), target = 71.列表：[3, 9, 15, 22, 31, 44, 57, 71, 83, 96]（索引 0-9），目标 = 71。
Linear search trace (1 mark per 3 correct rows, up to 3):线性搜索追踪（每 3 行正确得 1 分，最多 3 分）：
| Step步骤 | Index索引 | Value值 | == 71?== 71？ |
|---|---|---|---|
| 1 | 0 | 3 | No |
| 2 | 1 | 9 | No |
| 3 | 2 | 15 | No |
| 4 | 3 | 22 | No |
| 5 | 4 | 31 | No |
| 6 | 5 | 44 | No |
| 7 | 6 | 57 | No |
| 8 | 7 | 71 | YES |
Total steps: 8.总步数：8。
Binary search trace (1 mark per correct step, up to 3):二分搜索追踪（每步正确得 1 分，最多 3 分）：
| Step步骤 | low | high | mid | list[mid]list[mid] | Action操作 |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 31 | 71 > 31, search right向右 |
| 2 | 5 | 9 | 7 | 71 | FOUND找到 |
Total steps: 2. (Step 1: mid = floor((0+9)/2) = 4, list[4] = 31. Step 2: low = 5, mid = floor((5+9)/2) = 7, list[7] = 71. Found.)总步数：2。（步骤 1：mid = floor((0+9)/2) = 4，list[4] = 31。步骤 2：low = 5，mid = floor((5+9)/2) = 7，list[7] = 71。找到。）
Pre-condition: the list must be sorted (in ascending or descending order).前提条件：列表必须已排序（按升序或降序）。 B1 Without sorting, eliminating half the list based on a midpoint comparison is meaningless.没有排序，基于中点比较来排除一半列表是没有意义的。
(i) Linear search worst case: 1,000 steps (must check every element). (ii) Binary search worst case: 10 steps (log2(1000) < 10; since 210 = 1024 > 1000, at most 10 halvings).（i）线性搜索最坏情况：1,000 步（必须检查每个元素）。（ii）二分搜索最坏情况：10 步（log2(1000) < 10；由于 210 = 1024 > 1000，最多 10 次减半）。 B1
Binary search is far more efficient because it eliminates half the remaining search space on each step, reducing 1,000 elements to 1 in only 10 steps instead of up to 1,000.二分搜索效率远高于线性搜索，因为它每步排除一半剩余搜索空间，只需 10 步就能将 1,000 个元素缩减到 1 个，而非最多 1,000 步。 B1
Linear search: O(n) -- in the worst case it checks all n items, so the step count grows linearly with n.线性搜索：O(n) -- 在最坏情况下检查所有 n 项，因此步骤数随 n 线性增长。 B1
Binary search: O(log n) -- each step halves the search space, so the step count grows logarithmically with n.二分搜索：O(log n) -- 每步将搜索空间减半，因此步骤数随 n 对数增长。 B1
n = 1,048,576 = 220. Binary search worst case = log2(n) = log2(220) = 20 steps.n = 1,048,576 = 220。二分搜索最坏情况 = log2(n) = log2(220) = 20 步。 B1
Working: since 220 = 1,048,576, each halving reduces the space by a factor of 2. After 20 halvings: 220 / 220 = 1 item remains, so at most 20 comparisons are needed.过程：由于 220 = 1,048,576，每次减半将空间缩小 2 倍。20 次减半后：220 / 220 = 1 项剩余，因此最多需要 20 次比较。 B1
Linear search worst case on 1,048,576 items: 1,048,576 steps. Binary search worst case: 20 steps.1,048,576 项的线性搜索最坏情况：1,048,576 步。二分搜索最坏情况：20 步。
Ratio: 1,048,576 / 20 = 52,429 times more steps for linear search.比率：1,048,576 / 20 = 52,429 倍线性搜索所需步骤更多。 B1
Practically: if binary search takes 1 millisecond, linear search would take over 52 seconds on the same list -- an unusable user experience for a search feature.实际意义：如果二分搜索需要 1 毫秒，线性搜索在同一列表上将需要超过 52 秒——对搜索功能来说是不可接受的用户体验。 B1
A programmer would choose linear search when the list is not sorted, because binary search requires a pre-sorted list and sorting itself takes time.当列表未排序时，程序员会选择线性搜索，因为二分搜索需要预排序的列表，而排序本身也需要时间。 B1
Example scenario: searching an unsorted email inbox for a message containing a specific word -- the emails arrive in random order and sorting them before each search would not be worth the cost for a small inbox.场景示例：在未排序的电子邮件收件箱中搜索包含特定词的邮件——邮件以随机顺序到达，对于小收件箱而言，每次搜索前排序不值得付出这个代价。 B1
Trace with amount = 41 (1 mark per correct denomination group, up to 4):以 amount = 41 追踪（每个面值组正确得 1 分，最多 4 分）：
| coin面值 | amount before扣除前金额 | amount after扣除后金额 | count |
|---|---|---|---|
| 25 | 41 | 16 | 1 |
| 10 | 16 | 6 | 2 |
| 5 | 6 | 1 | 3 |
| 1 | 1 | 0 | 4 |
Note: the FOR EACH coin loop advances once per denomination. The WHILE loop inside runs until the denomination no longer fits. For coins 25 and 10 and 5 the WHILE body each executes once; for coin 1 it executes once (amount 1 to 0). Total WHILE executions = 4.注意：FOR EACH coin 循环每个面值推进一次。内部的 WHILE 循环运行直到该面值不再合适。对于面值 25、10 和 5，WHILE 循环体各执行一次；对于面值 1，执行一次（金额从 1 到 0）。WHILE 总执行次数 = 4。
Final count: 4最终 count：4 B1
Coins used: 25 + 10 + 5 + 1 = 41 cents. One coin of each denomination.使用的硬币：25 + 10 + 5 + 1 = 41 分。每种面值各一枚。 B1
Pillar: Algorithmic thinking支柱：算法思维 B1 -- the greedy strategy is a precise, unambiguous, step-by-step procedure: "at each stage, take the largest coin that does not exceed the remaining amount." This step sequence is repeatable and produces a definite result, which is the definition of an algorithm.-- 贪心策略是一个精确、无歧义的逐步程序："在每个阶段，取不超过剩余金额的最大面值硬币。"这个步骤序列可重复并产生确定结果，这正是算法的定义。 B1
Model pseudocode (1 mark per structural element: INPUT line; outer IF/ELSE; inner IF/ELSE; correct END IF nesting):参考伪代码（每个结构元素 1 分：INPUT 行；外层 IF/ELSE；内层 IF/ELSE；正确的 END IF 嵌套）：
INPUT password
IF LENGTH(password) >= 8 THEN
IF CONTAINS_DIGIT(password) THEN
OUTPUT "Strong"
ELSE
OUTPUT "Add a digit"
END IF
ELSE
OUTPUT "Too short"
END IFAccept equivalent pseudocode. The key requirements: INPUT first, outer condition on length, inner condition on digit presence, correct branch outputs.接受等价伪代码。关键要求：INPUT 在第一行，外层条件检查长度，内层条件检查是否含数字，正确的分支输出。
Updated sub-problems (accept any three, 1 mark per sub-problem, max 2 since only 2 marks available):更新后的子问题（接受任意三个，每个子问题 1 分，由于只有 2 分，最多 2 分）：
Output: "Too short"输出："Too short" B1
Path: START → Read password ("hello") → Diamond "length ≥ 8?" (5 ≥ 8 is FALSE) → NO branch → Output "Too short" → END.路径：START → 读取密码（"hello"）→ 菱形"长度 ≥ 8？"（5 ≥ 8 为否）→ 否分支 → 输出"Too short" → END。 B1 The digit check is never reached because the length check fails first.数字检查从未到达，因为长度检查首先失败。
Three high-level sub-problems (1 mark per correct sub-problem, max 2 since only 2 marks available):三个高层子问题（每个正确子问题 1 分，由于只有 2 分，最多 2 分）：
Binary search is more appropriate.二分搜索更合适。 B1
Binary search on a 5,000-title sorted catalogue needs at most log2(5000) < 13 steps to find any title. Linear search needs up to 5,000 steps in the worst case. Since the catalogue is already sorted (a required pre-condition that holds here), binary search is 5000/13 ≈ 385 times more efficient.在 5,000 个书名的已排序目录上，二分搜索最多需要 log2(5000) < 13 步找到任何书名。线性搜索最坏情况下需要最多 5,000 步。由于目录已排序（此处满足的必要前提条件），二分搜索效率约高 5000/13 ≈ 385 倍。 B1
Model pseudocode procedure (1 mark per structural element: correct variable initialisation; correct WHILE condition; correct mid computation; correct return logic):参考伪代码过程（每个结构元素 1 分：正确的变量初始化；正确的 WHILE 条件；正确的 mid 计算；正确的返回逻辑）：
PROCEDURE SEARCH(catalogue, target):
SET low TO 0
SET high TO LENGTH(catalogue) - 1
WHILE low <= high:
SET mid TO FLOOR((low + high) / 2)
IF catalogue[mid] == target THEN
RETURN TRUE
ELSE IF catalogue[mid] < target THEN
SET low TO mid + 1
ELSE
SET high TO mid - 1
END IF
END WHILE
RETURN FALSE
END PROCEDUREAward marks: [B1] low=0, high=LENGTH-1 initialised. [B1] WHILE low <= high (loop terminates correctly). [B1] mid = FLOOR((low+high)/2). [B1] Returns TRUE when found, adjusts low or high correctly, returns FALSE after loop.评分：[B1] low=0，high=LENGTH-1 初始化。[B1] WHILE low <= high（循环正确终止）。[B1] mid = FLOOR((low+high)/2)。[B1] 找到时返回 TRUE，正确调整 low 或 high，循环后返回 FALSE。
Logic error.逻辑错误。 B1 The procedure would not crash (no syntax error, no runtime crash for most inputs), but it would produce wrong answers: when the mid element is compared to the target on an unsorted list, the decision to search left or right is based on a false assumption that smaller values are to the left and larger values to the right. The procedure may report FALSE (not found) for a title that actually exists, or TRUE for a wrong position.该过程不会崩溃（无语法错误，对大多数输入无运行时崩溃），但会产生错误答案：当在未排序列表上将中间元素与目标比较时，向左或向右搜索的决策基于错误假设——较小值在左边，较大值在右边。该过程可能为实际存在的书名报告 FALSE（未找到），或在错误位置报告 TRUE。