📚 A-Level CCEA Mathematics: Algorithms Revision Guide | A-Level CCEA 数学：算法考点精讲
Algorithms form the backbone of decision mathematics, giving you systematic procedures to solve optimisation and routing problems efficiently. In the CCEA A-Level specification, you are expected to understand, apply, and trace a variety of algorithms – from sorting and searching through to graph-based methods and bin packing. This guide breaks down every key type, explains the steps clearly, and provides the detail you need for exam success.
算法是决策数学的基石，为你提供系统化的步骤，高效地解决优化问题和路径问题。在 CCEA A-Level 大纲中，要求理解、应用并追踪多种算法——从排序、搜索到基于图的方法以及装箱问题。本指南将剖析每一种考点类型，清晰解释步骤，并为你提供考试成功所需的细节。
1. What is an Algorithm? | 什么是算法？
An algorithm is a finite sequence of step-by-step instructions designed to solve a specific problem. It must be precise, unambiguous, and terminate after a finite number of steps. The same input should always produce the same output.
算法是一组有限的有序指令，旨在解决特定问题。它必须精确、无歧义，并在有限步骤后终止。同样的输入应始终产生相同的输出。
Algorithms can be expressed in plain English, flowcharts, or pseudocode. In CCEA exams, you will often work with a given algorithm written as a numbered list of instructions and be asked to complete a trace table to show how variables change step by step.
算法可以用普通英语、流程图或伪代码表示。在 CCEA 考试中，通常会面对以编号指令列表给出的算法，并被要求完成跟踪表，以展示变量如何逐步变化。
2. Trace Tables | 跟踪表
A trace table records the values of variables at each step of an algorithm. It is the primary tool for testing an algorithm’s correctness manually. You list all variables as column headings and fill in a new row whenever a value changes.
跟踪表记录算法每一步中变量的值。这是手动测试算法正确性的主要工具。你将所有变量列为列标题，每当值发生变化时就填写一行新行。
When completing a trace table, follow these rules: start with the initial state, then step through the instructions sequentially. If a condition is evaluated, record the outcome (true/false). Use a new row for each change, and only update the variables that are actually altered.
完成跟踪表时，遵循以下规则：从初始状态开始，然后按顺序逐步执行指令。如果评估了条件，记录结果（真/假）。每次变化使用新行，并且只更新实际发生变化的变量。
3. Bubble Sort Algorithm | 冒泡排序算法
Bubble sort compares adjacent pairs of items and swaps them if they are in the wrong order. After each pass, the largest remaining unsorted value ‘bubbles’ to its correct position at the end of the list.
冒泡排序比较相邻的一对项，如果顺序错误则交换它们。每经过一趟扫描，剩余未排序值中的最大值就会“冒泡”到列表末尾的相应位置。
For a list of n items, you need at most n–1 passes. In each pass i, you compare items 1 and 2, 2 and 3, …, up to items n–i and n–i+1. If the list becomes sorted before the final pass, the algorithm can stop early if no swaps occur in a pass.
对于有 n 个元素的列表，最多需要 n–1 趟。在第 i 趟中，依次比较第 1 和第 2、第 2 和第 3，直到第 n–i 和第 n–i+1 项。如果在最后一趟之前列表已经排好序，并且某趟没有发生任何交换，算法可以提前停止。
Example: sort [5, 1, 4, 2, 8].
示例：对 [5, 1, 4, 2, 8] 排序。
| Pass | Comparisons | List after pass |
|---|---|---|
| 1 | 5>1 swap, 5>4 swap, 5>2 swap, 5<8 no swap | [1, 4, 2, 5, 8] |
| 2 | 1<4, 4>2 swap, 4<5, 5<8 | [1, 2, 4, 5, 8] |
| 3 | No swaps needed | Sorted |
In a trace table, record the list after each comparison, or after each pass as required by the question.
在跟踪表中，根据题目要求，记录每次比较后的列表或每趟后的列表。
4. Quick Sort Algorithm | 快速排序算法
Quick sort works by choosing a pivot (often the middle item) and partitioning the remaining items into two sub-lists: those less than the pivot and those greater than the pivot. The process is then applied recursively to each sub-list.
快速排序通过选择一个基准（通常是中间项）并将剩余项分成两个子列表来工作：小于基准的项和大于基准的项。然后对每个子列表递归地应用该过程。
The CCEA specification often uses the middle item as the pivot. After selecting the pivot, write the items smaller than the pivot to the left, and items larger to the right, preserving their original relative order within each sub-list. Then choose new pivots for each sub-list and repeat until all sub-lists are of length 1 or empty.
CCEA 大纲通常使用中间项作为基准。选定基准后，将小于基准的项写在左边，大于基准的项写在右边，保持每个子列表中各项原来相对顺序。然后为每个子列表选择新的基准，重复直到所有子列表长度为 1 或为空。
Example: sort [6, 3, 8, 5, 2, 7, 4]
示例：对 [6, 3, 8, 5, 2, 7, 4] 排序
First pivot: middle number 5. Left: [3, 2, 4], Right: [6, 8, 7]. Then recursively sort left and right.
第一个基准：中间数 5。左：[3, 2, 4]，右：[6, 8, 7]。然后递归排序左右。
The number of comparisons and the depth of recursion can be asked, so practise drawing the tree diagram of pivots and sub-lists.
比较次数和递归深度也可能被考到，因此要练习绘制基准与子列表的树状图。
5. Binary Search Algorithm | 二分查找算法
Binary search finds a target value within a sorted list by repeatedly comparing the target to the middle item and discarding the half that cannot contain the target. It is far more efficient than a linear search for large lists.
二分查找通过在已排序列表中将目标值与中间项反复比较，并丢弃不可能包含目标值的那一半，从而找到目标值。对于大型列表，它比线性查找效率高得多。
Algorithm: locate the midpoint of the current search interval. If the midpoint equals the target, stop. If the target is smaller, repeat on the left half; if larger, repeat on the right half. Continue until the target is found or the interval is empty.
算法：确定当前搜索区间的中点。如果中点等于目标值，停止。如果目标值更小，对左半部分重复；如果更大，对右半部分重复。继续直到找到目标值或区间为空。
In a trace table, you typically record the lower bound, upper bound, midpoint, and the value at the midpoint for each iteration, as well as the comparison result.
在跟踪表中，通常记录每次迭代的下界、上界、中点以及中点处的值，还有比较结果。
For example, searching for 36 in [2, 5, 9, 14, 21, 36, 40]: initially L=1, U=7, mid=4 (value 14). 36>14, new L=5, U=7…
例如，在 [2, 5, 9, 14, 21, 36, 40] 中查找 36：初始下界 L=1，上界 U=7，中点 mid=4（值14）。36>14，新 L=5，U=7……
6. Bin Packing Algorithms | 装箱算法
Bin packing deals with fitting items of given sizes into bins of fixed capacity, minimising the number of bins used. Three heuristic algorithms are tested: first-fit, first-fit decreasing, and full-bin packing.
装箱问题涉及将给定大小的物品装入固定容量的箱子中，并使所用箱子数量最少。考查三种启发式算法：首次适应、降序首次适应和满箱组合。
First-fit: take items in the order given. Place each item into the first bin that has enough space. If no bin can take it, open a new bin.
首次适应：按给定顺序取物品。将每件物品放入第一个有足够空间的箱子。如果没有箱子能装下，就打开一个新箱子。
First-fit decreasing: sort the items into descending order of size, then apply the first-fit algorithm. This usually gives a better packing.
降序首次适应：将物品按大小降序排列，然后应用首次适应算法。这样通常能得到更好的装箱效果。
Full-bin packing: use inspection to find combinations of items that exactly fill a bin. Remove those items and repeat. Pack the remaining items using first-fit. This method can minimise bins but relies on observation rather than a fixed rule.
满箱组合：通过观察找到恰好能装满一个箱子的物品组合。移除这些物品并重复。剩余物品使用首次适应法装箱。该方法可以最小化箱子数量，但依赖于观察而非固定规则。
Exam questions may ask you to apply an algorithm, determine the number of bins, and compare the efficiency (wasted space) of different methods.
考题可能要求应用算法、确定箱子数量，并比较不同方法的效率（浪费的空间）。
7. Kruskal’s Algorithm for Minimum Spanning Tree | 最小生成树的 Kruskal 算法
Kruskal’s algorithm finds a minimum spanning tree (MST) in a weighted, connected graph. It builds the tree by repeatedly adding the shortest available edge that does not form a cycle.
Kruskal 算法在加权连通图中寻找最小生成树。它通过反复添加不构成环的最短可用边来构造树。
Steps: list all edges in ascending order of weight. Start with an empty set of edges. Go through the sorted list and add the next edge to the tree if it connects two different components (i.e., doesn’t create a cycle). Stop when the tree includes n–1 edges, where n is the number of vertices.
步骤：将所有边按权重升序列出。从空边集开始。遍历排序后的列表，如果下一条边连接两个不同的连通分量（即不构成环），就将其加入树中。当树包含 n–1 条边时停止，其中 n 是顶点数。
CCEA often requires a clear indication of when an edge is rejected, usually by writing it in a separate list or marking the order of selection.
CCEA 通常要求明确指明某条边被拒绝，一般通过写在单独的列表或标记选择顺序来表示。
If two edges have the same weight, you may choose either, but be consistent. Sometimes the question will prescribe the order.
如果有两条边权重相同，你可以任选一条，但要保持一致。有时题目会规定选择顺序。
8. Prim’s Algorithm for Minimum Spanning Tree | 最小生成树的 Prim 算法
Prim’s algorithm also finds the MST but works by growing the tree from an initial vertex. At each step, it chooses the smallest-weight edge that connects a vertex already in the tree to a vertex not yet in the tree.
Prim 算法也能找到最小生成树，但它通过从一个初始顶点开始生长树。在每一步，它选择连接树内顶点与树外顶点的最小权重边。
There are two ways to apply Prim’s: using a matrix form or a graphical form with ordered edge selection. CCEA often uses the matrix (table) method. You start at a given vertex, cross out its row, and look down the column for that vertex to find the smallest entry not yet connected. Select the cheapest, add the new vertex, cross out its row, and repeat.
Prim 有两种实现方法：使用矩阵形式或带顺序边选择的图形形式。CCEA 常使用矩阵（表格）法。从给定顶点开始，划掉其行，然后在该顶点的列中向下查找尚未连接的最小值。选择最便宜的边，加入新顶点，划掉其行，重复。
When there is a tie, you can choose any, but you must state your decision. The number of edges chosen will be n–1.
出现平局时，可以任选一条，但必须说明你的选择。选出的边数将是 n–1。
Practice constructing the tree from the sequence of selected edges and weights. Compare with Kruskal’s: both algorithms always produce a minimum spanning tree, but the edge order differs.
练习从所选的边和权重序列构造树。与 Kruskal 比较：两种算法总能产生最小生成树，但边的顺序不同。
9. Dijkstra’s Algorithm for Shortest Path | 最短路径的 Dijkstra 算法
Dijkstra’s algorithm finds the shortest path from a start vertex to every other vertex in a weighted graph where all edge weights are non-negative. It labels each vertex with a working value (tentative distance) and final value, then iteratively fixes the smallest tentative label.
Dijkstra 算法在边权重均为非负的加权图中，寻找从起点到其他每个顶点的最短路径。它为每个顶点标记工作值（暂定距离）和最终值，然后迭代地固定最小的暂定标签。
Algorithm steps: assign the start vertex final value 0 and working value 0; all others get working value ∞. At each step, find the vertex with the smallest working value that has not yet been finalised. Update the working values of its neighbours if a shorter path is found via this vertex. Mark the smallest working value as final and record the order of finalisation.
算法步骤：为起点赋予最终值 0 和工作值 0；其他所有顶点赋予工作值 ∞。在每一步，找出尚未最终确定且具有最小工作值的顶点。如果通过该顶点能找到更短路径，则更新其邻居的工作值。将最小的工作值标记为最终值，并记录最终确定的顺序。
In CCEA trace tables, you will typically show the working values and the vertex from which the shortest path comes. This allows you to then trace back the route.
在 CCEA 的跟踪表中，通常要展示工作值以及最短路径的来源顶点。这使你随后能回溯出路径。
Be careful with updating: if working value via the current vertex is strictly less than the existing working value, update it and change the previous vertex. In ties, keep the existing label.
更新时要注意：如果通过当前顶点的工作值严格小于现有工作值，就更新它并更改前驱顶点。在相等情况下，保持现有标签。
10. Algorithmic Complexity and Order | 算法复杂度与阶
In Decision Mathematics, you are expected to understand the efficiency of algorithms in terms of the number of operations such as comparisons or swaps as a function of the size of the input n.
在决策数学中，你需要理解算法的效率，即比较或交换等操作的次数作为输入规模 n 的函数。
Bubble sort: worst-case comparisons = n(n–1)/2, order O(n²). Quick sort: average O(n log n), but worst-case O(n²). Binary search: maximum comparisons ≈ log₂(n+1), order O(log n). Kruskal’s and Prim’s algorithms typically involve ordering edges or scanning a matrix and are of order O(n²) or O(n log n) depending on implementation, but you may not be asked to compute Big-O in detail – rather to compare numbers of comparisons for a given list size.
冒泡排序：最坏情况比较次数 = n(n–1)/2，阶为 O(n²)。快速排序：平均 O(n log n)，但最坏情况 O(n²)。二分查找：最大比较次数 ≈ log₂(n+1)，阶为 O(log n)。Kruskal 和 Prim 算法通常涉及边排序或扫描矩阵，根据实现方式为 O(n²) 或 O(n log n)，但你可能不会被要求详细计算大 O——而是比较给列表规模下的比较次数。
Exam questions might ask: “How many comparisons are made by bubble sort on a list of 8 items?” Answer: 7+6+…+1 = 28 in the worst case. You should be able to justify such counts.
考题可能问：“冒泡排序对 8 个元素的列表进行多少次比较？”答案：最坏情况下 7+6+…+1 = 28。你应该能够解释这样的计数。
11. Applying Algorithms in Context | 在实际情境中应用算法
CCEA exam papers often present a real-world scenario: scheduling tasks, packing boxes, designing a network, or finding the quickest route. You must identify which algorithm is appropriate and apply it correctly.
CCEA 试卷经常呈现真实世界的情境：任务调度、装箱、设计网络或找到最快路线。你必须判断哪种算法合适并正确应用。
When answering, show your working clearly: list edges or items, indicate choices, state when an edge is rejected, and finish with a clear statement of the solution (e.g., “The minimum spanning tree has total weight 47”). For packing, draw bins with contents. For graph algorithms, draw the tree or highlight the path.
作答时，要清晰地展示步骤：列出边或物品，标明选择，说明某条边被拒绝的时刻，并在最后清楚地陈述解答（例如，“最小生成树的总权重为 47”）。对于装箱问题，画出箱子及其内容物。对于图算法，画出树或高亮路径。
Marks are awarded for method as well as final answer, so even if you make an arithmetic slip, your logical steps can earn substantial credit.
分数既给方法也给最终答案，因此即使你犯了算术错误，你的逻辑步骤仍能获得大量分数。
12. Common Exam Pitfalls | 常见考试陷阱
One frequent mistake is not reading the algorithm precisely as given in the question. CCEA may present a variant, and you must follow it exactly rather than using the standard version from memory.
一个常见错误是没有准确按照题目给出的算法来执行。CCEA 可能提供一种变体，你必须完全遵循，而不是凭记忆使用标准版本。
In trace tables, forgetting to record a variable that is tested in a condition or omitting the result of the condition can lose marks. Practise the tabular layout so it becomes automatic.
在跟踪表中，忘记记录在条件中测试的变量或遗漏条件结果可能会失分。练习表格布局，使其成为习惯。
In bin packing, when using first-fit, always scan from the first bin for every item – don’t just place it in the last opened bin. In first-fit decreasing, ensure you sort into descending order first.
在装箱算法中，使用首次适应时，对每件物品始终从第一个箱子开始扫描——不要只把它放进最后打开的箱子。在降序首次适应中，确保首先按降序排列。
With Dijkstra, don’t finalise a vertex until you have checked and updated all its neighbours. Also remember to show the vertex from which a label was derived; without it, you cannot trace the shortest path.
使用 Dijkstra 算法时，在检查并更新完所有邻居之前不要最终确定顶点。还要记得显示标签的来源顶点；没有它，你将无法回溯最短路径。
Lastly, watch for directed graphs – Kruskal and Prim only apply to undirected graphs, while Dijkstra works on directed or undirected provided weights are non-negative. Read the stem carefully.
最后，注意有向图——Kruskal 和 Prim 只适用于无向图，而 Dijkstra 在权重非负的条件下既适用于有向图也适用于无向图。仔细阅读题目主干。
Published by TutorHao | Decision Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导