Practice Questions · AP CSP-Feeder · US / ON / BC / AB Styles练习题集 · AP CSP 衔接 · 美 / 安 / 卑 / 阿省风格
Questions mix multiple-choice and short-answer items. For MCQs, circle the letter and show your reasoning in the work space. For short-answer items, write precise answers. Code is pseudocode or Python; trace each step to verify before answering.本部分包含选择题与短答题。选择题请圈出字母，并在答题空白处写出推理过程。短答题写出精确答案。代码为伪代码或 Python；作答前逐步追踪验证。
A linear search is performed on the list [11, 4, 27, 9, 15, 3, 22] looking for the target value 15. How many comparisons are made before the target is found (including the comparison that finds it)?对列表 [11, 4, 27, 9, 15, 3, 22] 执行线性查找，查找目标值 15。在找到目标之前（含找到时的那次）共进行了多少次比较？
3457Which of the following lists can binary search be applied to correctly without any modification?以下哪个列表可以正确地直接应用二分查找而无需任何修改？
[8, 3, 12, 1, 19][19, 12, 8, 3, 1][1, 3, 8, 12, 19][1, 8, 3, 12, 19]The pseudocode below implements a linear search on the list [6, 14, 2, 31, 8, 20], searching for target 31.以下伪代码在列表 [6, 14, 2, 31, 8, 20] 上执行线性查找，查找目标 31。
INPUT data, target
SET found TO False
FOR i FROM 0 TO length(data) - 1:
IF data[i] == target THEN
SET found TO True
OUTPUT i
STOP
IF found == False THEN
OUTPUT -1| i | data[i] | data[i] == 31?data[i] == 31？ | Action操作 |
|---|---|---|---|
99 instead. Explain in one sentence why.若目标改为 99，程序将输出什么？用一句话解释原因。 [1]Consider the four algorithms from this unit and their worst-case step counts for a list of size n.考察本单元四种算法在大小为 n 的列表上的最坏情况步骤数。
| Algorithm算法 | Big-O (worst)大O（最坏） | Steps when n = 64n = 64 时步骤数 |
|---|---|---|
| Linear search线性查找 | ||
| Binary search二分查找 | ||
| Bubble sort冒泡排序 | ||
| Binary search requires the list to be sorted. State one cost of this requirement in terms of algorithm complexity.二分查找要求列表已排序。从算法复杂度角度说明此要求的一个代价。 | ||
Bubble sort is applied to the list [7, 2, 9, 4, 6].对列表 [7, 2, 9, 4, 6] 应用冒泡排序。
| Pass遍 | List after pass该遍后列表 | Swaps this pass本遍交换次数 |
|---|---|---|
| Start初始 | [7, 2, 9, 4, 6] | -- |
| 1 | ||
| 2 | ||
| 3 | ||
| 4 |
Show every step of your trace. For trace tables, complete every row. For justification questions, two sentences of clear reasoning earn full marks. Code may be pseudocode or Python.写出每一步追踪过程。追踪表须逐行填写。论证题两句清晰推理即可满分。代码可使用伪代码或 Python。
Binary search is applied to the sorted list [2, 5, 9, 14, 21, 33, 40, 58] (indices 0 to 7) searching for target 21.对有序列表 [2, 5, 9, 14, 21, 33, 40, 58]（索引 0 至 7）应用二分查找，查找目标 21。
low, high, mid, data[mid], and the action taken each step.补全追踪表，填写每步的 low、high、mid、data[mid] 及执行的操作。 [4]
| Step步骤 | low | high | mid | data[mid] | Action操作 |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
21. How many would linear search need in the worst case for the same 8-element list?写出找到 21 所需的比较次数。线性查找在同一 8 元素列表上最坏情况需要多少次？ [2]7 (not in the list), state what binary search returns and briefly explain why.若目标为 7（不在列表中），写出二分查找返回什么，并简要解释原因。 [1]Selection sort is applied to the list [8, 3, 11, 1, 6].对列表 [8, 3, 11, 1, 6] 应用选择排序。
| Pass (i)遍（i） | Min found (value, idx)找到最小值（值，索引） | List after swap交换后列表 |
|---|---|---|
| Start初始 | -- | [8, 3, 11, 1, 6] |
| 0 | ||
| 1 | ||
| 2 | ||
| 3 |
i = 2 of selection sort, how many elements are guaranteed to be in their final sorted positions? Identify which elements these are.选择排序第 i = 2 遍后，有多少个元素一定处于最终排序位置？指出是哪些元素。 [2]Insertion sort is applied to the list [6, 2, 10, 4, 8].对列表 [6, 2, 10, 4, 8] 应用插入排序。
FOR i FROM 1 TO length(data) - 1:
SET key TO data[i]
SET j TO i - 1
WHILE j >= 0 AND data[j] > key:
SET data[j+1] TO data[j] # shift right
SET j TO j - 1
SET data[j+1] TO key # insert keyi, showing the key and the list state after the key is inserted.补全每个 i 值对应的追踪表，显示 key 及插入后的列表状态。 [4]
| i | key | Shifts made移位次数 | List after insertion插入后列表 |
|---|---|---|---|
| Start初始 | -- | -- | [6, 2, 10, 4, 8] |
| 1 | |||
| 2 | |||
| 3 | |||
| 4 |
A student must search a dataset of n = 1,000,000 records. They can either (1) use linear search directly, or (2) first sort the list using a simple O(n²) sort, then use binary search. They plan to perform exactly 10 searches total.一名学生需要搜索包含 n = 1,000,000 条记录的数据集。他们可以选择（1）直接使用线性查找，或（2）先用 O(n²) 的简单排序对列表排序，再使用二分查找。他们计划总共执行 10 次搜索。
sorted() uses Timsort (O(n log n) worst case). Recalculate option 2 with Timsort (n log n = 1,000,000 x 20 steps for the sort). Does this change your recommendation for 10 searches?Python 内置 sorted() 使用 Timsort（最坏情况 O(n log n)）。用 Timsort 重新计算方案 2（排序步骤数 = 1,000,000 x 20）。这是否改变了对 10 次搜索的建议？ [2]Read each scenario carefully. Where pseudocode is requested, use the standard block format. Where Python is requested, show correct indentation. Every question in this part is MEDIUM or HARD difficulty -- no EASY questions appear here.仔细阅读每个场景。伪代码使用标准块格式。Python 须正确缩进。本部分所有题目均为中等或高难度，无易题。
A library system stores book ID numbers. A librarian searches for book ID 47.图书馆系统存储图书 ID 号。馆员搜索图书 ID 47。
Scenario A:场景 A： The IDs are stored as [23, 47, 8, 61, 15, 39, 72] (unsorted).ID 以 [23, 47, 8, 61, 15, 39, 72] 存储（无序）。
Scenario B:场景 B： The IDs are stored as [8, 15, 23, 39, 47, 61, 72] (sorted).ID 以 [8, 15, 23, 39, 47, 61, 72] 存储（已排序）。
47, listing each index checked.对于场景 A，说明必须使用哪种搜索算法及原因。追踪算法找到 47，列出每个检查的索引。 [3]low, high, mid, and data[mid] for each step.对于场景 B，逐步追踪二分查找，填写每步的 low、high、mid、data[mid] 表格。 [3]
| Step步骤 | low | high | mid | data[mid] | Action操作 |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
A student is sorting student scores. The following three lists represent different scenarios. For each scenario, state which of bubble sort, selection sort, or insertion sort is the most appropriate choice and justify your answer.一名学生正在对学生分数进行排序。以下三个列表代表不同场景。对每种场景，说明冒泡排序、选择排序或插入排序中哪种最合适，并为你的答案提供理由。
[88, 91, 85, 89, 92, 87, 90] -- a nearly-sorted list where only a few elements are slightly out of order. Which sort is best? Justify in two sentences.场景 1：[88, 91, 85, 89, 92, 87, 90] -- 近乎有序的列表，只有少数几个元素轻微乱序。哪种排序最好？用两句话说明理由。 [3][95, 90, 85, 80, 75, 70, 65] -- a fully reverse-sorted list. Of bubble sort and selection sort, which makes fewer swaps? Count the swaps for each and state your answer.场景 2：[95, 90, 85, 80, 75, 70, 65] -- 完全逆序的列表。冒泡排序和选择排序中，哪个交换次数更少？各自计算交换次数并给出答案。 [4]A program manages a list of student (name, score) tuples. A student writes the following Python code.一个程序管理学生（姓名，分数）元组的列表。一名学生编写以下 Python 代码。
students = [("Zara", 88), ("Alex", 95), ("Maya", 73), ("Ben", 88), ("Priya", 91)]
# Sort by score ascending
students.sort(key=lambda s: s[1])
# Search for score 88 using linear search
target_score = 88
for i in range(len(students)):
if students[i][1] == target_score:
print("Found:", students[i])
breakstudents after the sort() call.写出 sort() 调用后 students 的内容。 [2]i) the loop exits via break.追踪线性查找循环。写出找到并打印的元素，以及循环在哪次迭代（i 值为多少时）通过 break 退出。 [2]sort() call.重写排序行，使列表按分数降序排列，分数相同时按姓名升序作为次要排序键。只写修改后的 sort() 调用。 [2]students.sort(...) and sorted(students, ...). In this program, which is preferable if you need to keep the original unsorted list? Justify in one sentence.解释 students.sort(...) 和 sorted(students, ...) 的区别。如果需要保留原始未排序列表，本程序中哪个更合适？用一句话说明理由。 [2]3A-AP-11 · 3B-AP-11 · 3.11 · 3.17ICS4U A3.2 · A3.4 · C2.2 · C2.3Full Syllabus Map in Study Guide: ../Study Guides/Unit_7_Searching_and_Sorting.html. CS has no AB standalone diploma exam; AB framing uses CSE3110 outcomes.完整大纲对照见学习指南：../Study Guides/Unit_7_Searching_and_Sorting.html。CS 无独立 AB 毕业考；AB 题使用 CSE3110 结果框架。