📚 AS Mathematics Unit 5 (June 2019) Key Topic Review | AS数学Unit5 2019年6月考卷知识点精讲
In the June 2019 sitting of AS Mathematics Unit 5 (Decision Mathematics 1), candidates were tested on a wide range of algorithmic and modelling skills. This paper typically features graph theory, sorting, bin packing, critical path analysis and linear programming problems. The following review unpacks each examined topic with worked-style insights to help you master the core techniques and avoid common pitfalls.
在2019年6月的AS数学Unit 5（决策数学1）考试中，考生需要运用多种算法与建模能力解决实际问题。试卷通常涵盖图论、排序、装箱、关键路径分析及线性规划等题型。以下内容将逐一剖析考察的核心知识点，通过实战型讲解帮助你牢牢掌握解题技巧并规避常见失分点。
1. Bubble Sort and Quick Sort Algorithms | 冒泡排序与快速排序算法
The June 2019 paper requires you to understand the step‑by‑step mechanics of both the bubble sort and the quick sort. For bubble sort, you work through successive passes, comparing adjacent items and swapping them if they are out of order. You must know how to count the number of comparisons and swaps, and be able to state the list after a given number of passes or after the point where no further swaps occur. Mark schemes often award marks for clearly showing the state of the list after each pass and identifying the final sorted order.
2019年6月的试题要求你掌握冒泡排序和快速排序的逐步操作过程。对于冒泡排序，你需要逐趟比较相邻元素并将逆序的元素交换位置。你必须能够统计比较次数和交换次数，并能在给定趟数后或不再发生交换时写出列表的状态。评分方案通常会奖励那些清晰展示每趟后列表状态并正确识别最终排序结果的解答。
- Bubble sort terminates when an entire pass makes zero swaps — the list is then sorted.
- 当某趟没有发生任何交换时冒泡排序终止——此时列表已排序。
- Quick sort uses a pivot; you must show two sub‑lists (values less than the pivot and values greater than the pivot), then recursively apply the process. Marks are given for correct pivot choices and sub‑list formation.
- 快速排序使用一个基准值；你需要展示两个子列表（小于基准和大于基准的值），然后递归地重复这一过程。正确选择基准并划分子列表是得分关键。
Practice writing out the working clearly: for quick sort, underline the pivot each time and use consistent notation for the growing ordered list.
练习时请确保书写清晰：快速排序中每次都要给基准加下划线，并用一致的记号写出不断扩展的有序列表。
2. Bin Packing: First‑Fit, First‑Fit Decreasing and Full‑Bin Strategies | 装箱策略：首次适应、降序首次适应与满箱组合
Bin packing problems appeared in the June 2019 paper, where you were asked to pack items into bins of a fixed capacity using three standard heuristics. First‑fit simply places each item into the earliest bin that has enough space. First‑fit decreasing sorts items into descending order first, which usually yields fewer bins. The full‑bin method involves manually identifying groups of items that exactly fill a bin before packing the remaining items using first‑fit.
装箱问题出现在了2019年6月的试卷中，题目要求你使用三种标准启发式算法将物品放入固定容量的箱子。首次适应算法只把每个物品放入第一个有足够空间的箱子。降序首次适应算法先将物品按降序排列，通常能使用更少的箱子。满箱组合法则是先手动找出恰好装满一个箱子的物品组合，再用首次适应法处理剩余物品。
You need to be able to compare the number of bins used by each method for a given list. The exam often asks: ‘Determine an upper bound for the number of bins required’ and ‘Explain why the number of bins used by first‑fit decreasing is not necessarily optimal’. The full‑bin approach that you construct does not need to be optimal, but you must show a clear packing that respects the bin capacity.
你需要能够比较每种方法在给定列表下所用箱子的数量。试题常问：“确定所需箱子数量的一个上界” 以及 “解释为什么降序首次适应所用的箱子数不一定是最优的”。你构造的满箱组合并不要求最优，但你必须展示一个明确且遵守箱子容量限制的装箱方案。
3. Kruskal’s Algorithm for Minimum Spanning Trees | 克鲁斯卡尔算法求最小生成树
Kruskal’s algorithm selects edges in ascending order of weight, ignoring any edge that would form a cycle, until a spanning tree is formed. In the June 2019 paper, you were likely given a network and asked to find the minimum spanning tree, listing the edges in the order they are selected and stating its total weight. You must also be prepared to interpret the meaning of the tree in a practical context, such as connecting points with minimum cost.
克鲁斯卡尔算法按权重升序选择边，跳过任何会形成回路的边，直至生成树形成。在2019年6月的试卷中，你很可能看到一个网络，需要寻找最小生成树，按选择顺序列出边并说明总权重。你也需要准备在实际情境中解释生成树的意义，例如用最低成本连接各点。
Always draw a clear working diagram. Even if the question does not require you to draw the tree, sketching helps you avoid accidental cycles. When reporting the total weight, double‑check your sum and show it separately as a final answer. Some questions also ask for the number of edges in a minimum spanning tree for a network with n vertices — remember it is n−1.
画一个清晰的演算草图总是有帮助的。即使题目没有要求画出生成树，随手画一下也能避免不小心形成回路。报告总权重时要仔细核对总和，并单独列出作为最终答案。有些问题还会问一个有 n 个顶点的网络的最小生成树有多少条边——记住答案是 n−1。
4. Prim’s Algorithm on a Table and on a Graph | 普里姆算法：表格形式与图像形式
Prim’s algorithm can be applied directly on a distance matrix or on a network diagram. In a tabular format, you start from an arbitrary vertex, delete that vertex’s column and scan its row for the smallest entry as the next vertex to join. You then delete the new vertex’s column, compare the rows of all connected vertices, and repeat. The June 2019 paper tests your ability to perform Prim’s algorithm on a table, writing down which vertices are added and which edge is selected at each iteration.
普里姆算法可直接在距离矩阵或网络图上执行。在表格形式中，你从任意一个顶点开始，删除该顶点所在的列，扫描其所在行中的最小数值作为下一个要加入的顶点。然后删除新顶点的列，比较所有已连接顶点的行，重复这一过程。2019年6月的试卷测试了你在表格上执行普里姆算法的能力，要求写出每一步添加了哪个顶点以及选择了哪条边。
When using Prim on a graph, bubble your way outward by selecting the minimum weight edge that connects a vertex already in the tree to a vertex not yet in the tree. Examiners expect clear indication of your start vertex and a record of the chosen edges in order. Avoid the common mistake of overlooking an edge that could create a cycle — Prim naturally avoids cycles if you strictly follow the rule.
在图上使用普里姆算法时，始终选择连接树内顶点与树外顶点的最小权重边向外扩展。考官希望你明确指出起始顶点并按顺序记录所选边。常见错误是忽略某条可能导致回路的边——只要严格遵循规则，普里姆算法本身就会避免回路。
5. Dijkstra’s Shortest Path Algorithm | 迪杰斯特拉最短路径算法
Dijkstra’s algorithm finds the shortest path from a start node to all other nodes in a weighted network. The June 2019 paper almost certainly contains a question where you must produce a fully labelled working diagram showing temporary and permanent labels at each node. You are expected to write the working values at vertices, using a consistent format: a box for permanent labels, and working values updated with brackets.
迪杰斯特拉算法用于在加权网络中寻找从起始节点到所有其他节点的最短路径。2019年6月的试卷几乎一定包含一道需要你画出完整标注工作图的题目，显示每个节点处的临时标号和永久标号。你需要用统一格式在顶点旁记录处理值：用方框标记永久标号，并用括号更新临时值。
After completing the labelling, you often need to state the shortest distance to several destinations and trace back the actual route. Route tracing should list vertices in reverse order from the destination back to the start, then reverse them for the final answer. Pay close attention to whether the question wants distance, route, or both.
完成标号后，题目通常要求你写出到几个目的地的最短距离并回溯实际路线。回溯路线时应从目的地逆序列出顶点回到起点，再反转顺序给出最终答案。请仔细留意题目是要求写出距离、路线、还是两者都要。
6. Critical Path Analysis: Forward and Backward Scans | 关键路径分析：前向扫描与后向扫描
Critical path analysis (CPA) uses activity‑on‑node precedence networks. The June 2019 session required you to construct an activity network from a precedence table, perform forward and backward scans, and identify the critical path(s) and total float of activities. You must be able to calculate early event times (EET) and late event times (LET) for each node, then use them to derive total float.
关键路径分析使用节点表示活动的优先关系网络。2019年6月的考试要求你根据优先关系表构建活动网络，执行前向扫描和后向扫描，并识别关键路径以及各项活动的总浮动时间。你必须能够为每个节点计算最早事件时间（EET）和最晚事件时间（LET），进而求出总浮动。
Total float for an activity is LET at the finish node − EET at the start node − duration. Activities with zero total float lie on the critical path. When presenting dummies in the activity network, draw them as dashed arrows and ensure they correctly reflect the dependencies. A frequent pitfall is missing a dependency that introduces an unnecessary constraint, so double‑check the precedence table.
一项活动的总浮动时间 = 结束节点的LET − 开始节点的EET − 活动持续时间。总浮动为零的活动位于关键路径上。在活动网络中绘制虚工作时，要用虚线箭头表示，并确保它们正确反映依赖关系。常见错误是漏了一个依赖关系而导致不必要的约束，因此务必再次核对优先关系表。
7. Schedule Construction and Gantt Charts | 调度安排与甘特图
Using the results from critical path analysis, the June 2019 paper asks you to produce a schedule (often a Gantt chart) given a limited number of workers. You need to assign activities to workers while respecting precedence constraints, aiming to minimise the project makespan. The chart should clearly represent start and end times for each activity.
利用关键路径分析的结果，2019年6月的试卷会要求你基于有限的工人数量制定一个调度方案（通常以甘特图呈现）。你需要在不违反优先关系的前提下为工人分配活动，同时尽量缩短项目完工时间。甘特图应该清晰地表示出每项活动的开始和结束时间。
When constructing the Gantt chart, process activities in order of their early start times if resource levelling is required. Exam questions often include a part where you explain why a particular activity must start at a certain time. You may also be asked: “How many workers are needed at time t?” — answer by counting overlapping activities at that moment.
当需要进行资源平衡时，可按活动最早开始时间的顺序来绘制甘特图。试题经常包含一个小问，让你解释为什么某项活动必须在特定时间开始。你也可能被问到：“在时刻 t 需要多少名工人？”——只需统计该时刻下正在进行中的活动数目即可解答。
8. Linear Programming: Graphical Method and Objective Function | 线性规划：图解法与目标函数
Linear programming questions in the June 2019 Unit 5 paper require you to formulate constraints, graph the feasible region, and find the optimal value of an objective function. You must be able to draw accurate straight lines from inequalities, shade the unwanted region clearly, and test vertices (or use an objective line) to determine the optimal solution.
2019年6月Unit 5试卷中的线性规划题要求你列出约束条件、画出可行域并找到目标函数的最优值。你必须能准确地根据不等式画出直线，清晰地标明不可行区域，并通过检验顶点（或使用目标函数等值线）来确定最优解。
If the context asks for integer solutions, you may need to test integer points around the continuous optimum. Always check integer coordinates inside the feasible region, not just the vertices. In your answer, state the final decision variables and the value of the objective function clearly, with units if applicable.
如果情境要求整数解，你可能需要在连续最优解附近检验整数点。务必检查可行域内部的整数坐标，而不仅仅是顶点。在答案中要明确写出最终的决策变量值和目标函数值，必要时带单位。
9. Matching in Bipartite Graphs and Alternating Paths | 二部图匹配与交错路径
The matching problem on bipartite graphs usually starts with an initial matching, and you are asked to improve it using alternating paths until a maximal matching is found. The June 2019 paper expects you to correctly construct the bipartite graph representation, identify exposed vertices, and find an alternating path from an unmatched vertex on one side to an unmatched vertex on the other side.
二部图的匹配问题通常从初始匹配开始，然后要求你利用交错路径不断改进匹配，直到找到最大匹配。2019年6月的试卷期望你能正确构建二部图表示，识别未匹配顶点，并从一侧未匹配顶点出发找到一条到达另一侧未匹配顶点的交错路径。
Once you have an alternating path, you change the status of the edges along it: matched edges become unmatched and unmatched edges become matched, increasing the size of the matching by exactly one. After reaching a maximal matching, you often need to write down the final allocation and confirm that no further alternating path exists.
找到交错路径后，你需要改变路径上边的状态：将已匹配边变为未匹配，未匹配边变为已匹配，从而使匹配的规模精确增加1。达到最大匹配后，你通常需要写出最终的分配方案，并确认不存在可进一步改进的交错路径。
10. Travelling Salesman Problem: Bounds and Nearest Neighbour | 旅行商问题：上下界与最近邻算法
The June 2019 Unit 5 paper may include a travelling salesman problem (TSP) where you need to find an upper bound using the nearest neighbour algorithm (or using the weight of the minimum spanning tree plus the two shortest edges from a vertex). A lower bound is often found by deleting a vertex and its incident edges, then finding the weight of the minimum spanning tree on the remaining network and adding the two shortest edges from the deleted vertex.
2019年6月的Unit 5试卷可能包含旅行商问题，要求你利用最近邻算法（或利用最小生成树权重加上从某个顶点出发的两条最短边）找到上界。下界通常通过删除一个顶点及其关联边，在剩余网络上求最小生成树的权重，再加上被删顶点的两条最短边之和来得到。
When applying the nearest neighbour algorithm, start from a specified vertex, repeatedly go to the nearest unvisited vertex, and finally return to the start. The total distance is an upper bound for the optimal tour. You may then need to use the bounds to argue about the quality of the nearest neighbour tour.
应用最近邻算法时，从指定顶点出发，每次前往距离最近的未访问顶点，最后返回起点。总距离就是最优巡回的一个上界。接下来你可能会利用这些上下界来评价最近邻巡回的优劣。
Remember that a minimum spanning tree provides a lower bound on the TSP if you double the tree, but the standard method using deleted vertices usually gives a better lower bound. Pay attention to whether the question specifies using a particular vertex for the lower bound calculation.
记住，如果把最小生成树加倍固然可以得到一个TSP的下界，但采用删除顶点法通常能获得更好的下界。注意审题，看题目是否指定用哪个顶点来计算下界。
11. Algorithmic Tracing and Order of Operations | 算法跟踪与操作顺序
Throughout the June 2019 paper, marks are heavily allocated to showing correct steps, not just the final answer. For any algorithm question, follow the operation order precisely as set out in the specification. Whether it is bubble sort, quick sort, Dijkstra, or critical path scans, clearly display intermediate states, labels, and selected edges.
在2019年6月整张试卷中，答题步骤的正确展示占据大量分值，而不仅仅是最终答案。对于任何算法题，都要精确遵循大纲规定的操作顺序。无论是冒泡排序、快速排序、迪杰斯特拉算法还是关键路径扫描，都要清晰展示中间状态、标号和所选边。
Using structured layouts — numbered passes, tables with rows for each worker in scheduling, or labelled nodes in networks — makes your working easier for the examiner to follow. If you make a slip in a final value but your method is clear, you can still gain the majority of method marks.
使用结构化的书写格式——如带编号的趟次、调度中按工人分行的表格、带标号的网络节点——都能让考官更容易跟踪你的解题步骤。即使最终数值出现一点小失误，只要方法清晰，仍能拿到绝大部分方法分。
12. Exam‑Style Tips and Common Mistakes | 应试技巧与常见错误
Many students lose marks by not reading the question carefully: specifying the wrong vertex as the start for Prim or Dijkstra, forgetting to state units in linear programming, or not completing the alternating path all the way to an unmatched vertex on the opposite side. In sorting questions, check whether the list is to be sorted into ascending or descending order.
很多学生因审题不仔细而丢分：把普里姆或迪杰斯特拉的起始顶点写错，在线性规划中忘记注明单位，或者交错路径没有一直延伸到对侧未匹配顶点。在排序题中，要核实列表是要求升序还是降序排列。
Time management is crucial: a full Unit 5 paper features multiple long algorithm questions. Practice writing quickly but neatly, and know when to move on. Keep your working concise: for Kruskal, write edge and weight, and maintain a running total. For bin packing, use a simple column layout to show which items go into each bin.
时间分配至关重要：整套Unit 5试卷包含多道较长的算法题。练习快速而工整地书写，并知道何时该暂时跳过。保持解题过程简练：对于克鲁斯卡尔算法，写出边和权重，并维护一个累积总重；对于装箱问题，用简洁的列排版展示每个箱子装入了哪些物品。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导