📚 Decision Maths 1 Exam Practice: Core Topics and Worked Examples | 决策数学1考试实战：核心考点与例题解析
Decision Maths 1 (D1) focuses on discrete algorithms, networks, and optimisation. Exam questions often ask you to trace an algorithm step by step, draw or interpret a graph, or formulate and solve a linear programming problem. This article reviews the highest-yield topics, using exam-style examples and clear rules to help you avoid common mistakes.
决策数学1（D1）主要考察离散算法、网络与最优化。考试题常要求逐步追踪算法、绘制或解读图，或者建立并求解线性规划问题。本文梳理最高频考点，结合考试风格例题和清晰规则，帮助你避开常见错误。
1. Sorting Algorithms: Bubble and Quick Sort | 排序算法：冒泡排序与快速排序
Bubble sort compares adjacent pairs and swaps them if they are out of order. A complete pass with no swaps confirms that the list is sorted. In an exam, you must record the list after each pass, not only the final order, because marks are awarded for correct intermediate steps.
冒泡排序比较相邻元素，如果顺序错误就交换。一次完整遍历中没有发生交换即说明列表已排好。考试中必须记录每趟遍历后的列表，而不仅仅是最终顺序，因为中间步骤也有分数。
Quick sort chooses a pivot, places all smaller items to its left and all larger items to its right, then repeats on each sublist. If the pivot is the middle value, always write down the two sublists before the pivot and after the pivot. An example for 9, 4, 7, 1, 6 with pivot 7 would produce sublist 4, 1, 6 before 7 and sublist 9 after 7.
快速排序选择一个基准元素，将比它小的项放在左边、比它大的项放在右边，然后对每个子列表重复操作。如果基准是中间值，必须写出基准前和基准后的两个子列表。例如对 9, 4, 7, 1, 6 以 7 为基准，会得到 7 前的子列表 4, 1, 6 和 7 后的子列表 9。
When a question asks for the number of comparisons or swaps, count them exactly from your trace. Do not rely on memory of a formula unless the question states that list size is large; for small lists, count directly from the sorted trace.
当题目要求比较次数或交换次数时，要根据追踪过程准确计数。除非题目说明列表规模很大，否则不要直接套公式；对小列表应直接从排序追踪中数出来。
2. Bin Packing Algorithms | 装箱算法
First-fit bin packing places each item into the first existing bin that has enough remaining capacity, opening a new bin only if no current bin fits the item. First-fit decreasing sorts the items into descending order of size before applying first-fit, which usually gives a better result but is not guaranteed to be optimal.
首次适应装箱算法将每件物品放入第一个有足够剩余容量的已有箱子，如果没有当前箱子能容纳才打开新箱。降序首次适应先把物品按大小降序排列，再使用首次适应，通常效果更好，但不保证最优。
A full-bin strategy looks for combinations of items that exactly fill a bin capacity. In exam questions, you may be asked to use a given capacity and state how many bins are used. Always show the contents of each bin clearly, for example: Bin 1: 7 + 3 = 10, Bin 2: 6 + 4 = 10.
满箱策略寻找恰好填满箱子容量的物品组合。考试中可能给出箱子容量并要求说明用多少个箱子。务必清晰写出每个箱子的内容，例如：箱1: 7 + 3 = 10，箱2: 6 + 4 = 10。
To decide when an answer is optimal, compare with the lower bound: total size ÷ bin capacity, rounded up to the next integer. If your number of bins equals the lower bound, the solution is optimal.
判断答案是否最优时，与下界比较：总大小 ÷ 箱子容量，向上取整。如果所用箱子数等于下界，则该解最优。
3. Graph Terminology and Minimum Spanning Trees | 图论术语与最小生成树
A graph consists of vertices connected by edges. A tree is a connected graph with no cycles, and a spanning tree connects all vertices using only edges from the original graph. The minimum spanning tree is the spanning tree with the smallest total edge weight.
图由顶点和连接顶点的边组成。树是连通且无环的图，生成树使用原图的边连接所有顶点。最小生成树是总边权最小的生成树。
Kruskal’s algorithm sorts all edges by weight and adds the shortest edge that does not form a cycle. Prim’s algorithm grows a tree from a starting vertex by repeatedly adding the cheapest edge that connects the current tree to a new vertex. Both produce the same total weight if all edge weights are distinct or tie-breaking is consistent.
克鲁斯卡尔算法将所有边按权排序，加入不形成环的最短边。普里姆算法从起始顶点开始，不断加入连接当前树与新顶点的最便宜边。如果所有边权不同或平局处理一致，两种算法得到相同总权重。
When drawing the minimum spanning tree, write the order of edge selection clearly. If using Kruskal, reject any edge that would create a cycle and show the reason for rejection. This is a common marking point.
画最小生成树时，要清晰写出选边顺序。使用克鲁斯卡尔时，须拒绝任何会形成环的边并说明拒绝原因，这是常见的得分点。
4. Dijkstra’s Algorithm for Shortest Path | 迪杰斯特拉最短路径算法
Dijkstra’s algorithm finds the shortest path from a start vertex to all other vertices in a weighted graph with non-negative edges. At each step, the vertex with the smallest temporary label becomes permanent, and its neighbours’ labels are updated if a shorter route is found.
迪杰斯特拉算法在非负边权图中求从起点到所有其他顶点的最短路径。每一步中，临时标签最小的顶点变为永久标签，如果找到更短路线则更新其邻居的标签。
A standard trace uses boxes for permanent labels and written working values for temporary labels. For example, if vertex A is permanent at 0 and edges are A→B = 5, A→C = 8, write temporary labels 5 at B and 8 at C. Then choose B, and update C if 5 + 4 = 9 is not less than 8.
标准追踪用方框表示永久标签，用书写值表示临时标签。例如，若顶点 A 永久标签为 0，边 A→B = 5、A→C = 8，则在 B 处写临时标签 5，在 C 处写 8。然后选择 B，如果 5 + 4 = 9 不小于 8 则不更新 C。
To state the shortest path from A to a target vertex, work backwards from the final label and list the vertices in order. Always give both the route and its total length, such as A → B → D with length 12.
要说出从 A 到目标顶点的最短路径，从最终标签反向追溯并按顺序列出顶点。必须同时给出路线和总长度，例如 A → B → D，长度 12。
5. Route Inspection Problem | 路线检查问题
The route inspection problem, also called the Chinese postman problem, asks for a shortest route that traverses every edge at least once. An Eulerian graph allows a closed trail using every edge exactly once, which exists only when all vertices have even degree.
路线检查问题也称中国邮递员问题，要求找出一条至少经过每条边一次的最短路线。欧拉图允许恰好使用每条边一次的闭合路线，仅当所有顶点度数均为偶数时存在。
If a graph has odd-degree vertices, you must repeat paths between pairs of odd vertices. Find all pairings of odd vertices, compute the shortest distances between each pair, and choose the pairing with the smallest total additional distance.
如果图有奇度顶点，必须重复奇数顶点对之间的路径。找出奇度顶点的所有配对，计算每对之间的最短距离，选择额外距离总和最小的配对。
The total route length = sum of all original edge weights + minimum repeated distance. In an exam answer, state the repeated edges and then the total length. If the start and end must differ, mention that one pair of odd vertices can remain unmatched.
总路线长度 = 所有原边权之和 + 最小重复距离。考试作答时，要说明重复的边，再写总长度。如果起终点必须不同，则说明一对奇度顶点可以保持不配对。
6. Critical Path Analysis | 关键路径分析
Critical path analysis uses activity networks to schedule a project. Each activity has a duration and precedence relationships. A forward pass gives the earliest event times, and a backward pass gives the latest event times.
关键路径分析使用活动网络安排项目。每项活动有持续时间和先后关系。前向计算得到事件最早时间，后向计算得到事件最迟时间。
Total float = latest finish time − earliest finish time
总浮动时间 = 最迟完成时间 − 最早完成时间
An activity is critical if its total float is zero. The critical path is a continuous chain of critical activities from the start event to the end event. If any critical activity is delayed, the whole project is delayed by the same amount.
如果活动的总浮动时间为零，则该活动是关键活动。关键路径是从开始事件到结束事件的一条连续关键活动链。任何关键活动延误都会使整个项目延误相同时间。
When drawing a cascade chart or scheduling diagram, show each activity at its earliest start time but mark its total float. Exam questions often ask for the minimum project completion time and the critical activities, so always complete both passes before identifying the path.
绘制级联图或调度图时，以最早开始时间显示每项活动并标出总浮动时间。考题常要求最小项目完成时间和关键活动，因此务必完成两轮计算后再确定路径。
7. Linear Programming: Graphing and Optimising | 线性规划：图解与优化
Linear programming formulates constraints as linear inequalities and an objective function to maximise or minimise. In Decision Maths 1, you usually graph the feasible region, identify vertices, and test them in the objective function.
线性规划将约束表示为线性不等式，目标函数求最大值或最小值。在决策数学1中，通常画出可行区域，确定顶点，并将顶点代入目标函数检验。
To graph a constraint such as 2x + 3y ≤ 24, draw the boundary line 2x + 3y = 24, then shade or clearly mark the region that satisfies the inequality. The feasible region is the intersection of all constraint regions, including x ≥ 0 and y ≥ 0 if required.
画约束如 2x + 3y ≤ 24 时，画出边界线 2x + 3y = 24，然后标出满足不等式的区域。可行区域是所有约束区域的交集，如需要还包括 x ≥ 0 和 y ≥ 0。
If the objective is maximise P = 3x + 2y, evaluate P at each vertex of the feasible region. The optimal solution is the vertex giving the highest P value. Use exact coordinates, especially when a vertex lies at the intersection of two boundary lines, and solve simultaneously to find those coordinates.
如果目标是最大化 P = 3x + 2y，在可行区域的每个顶点处计算 P。最优解是使 P 值最大的顶点。使用精确坐标，尤其是顶点位于两条边界线交点时，应联立方程求出坐标。
8. Matchings and Hall’s Theorem | 匹配与霍尔定理
A matching in a bipartite graph pairs vertices from one set with vertices from another set, with no vertex used more than once. A maximal matching cannot be extended by adding an edge, while a maximum matching has the greatest possible number of edges.
二分图中的匹配将一个集合的顶点与另一个集合的顶点配对，每个顶点最多使用一次。最大基数匹配不能通过加边扩展，而最大匹配具有尽可能多的边数。
An alternating path starts on an unmatched vertex and alternates between edges not in the matching and edges in the matching. If an alternating path starts and ends at unmatched vertices, it is an augmenting path; switching matched and unmatched edges along it increases the matching size by one.
交替路径从未匹配顶点开始，在非匹配边和匹配边之间交替。如果一条交替路径起点和终点都是未匹配顶点，则它是增广路径；沿该路径交换匹配边和非匹配边可使匹配大小增加一。
Hall’s theorem states that a complete matching from one set to the other exists if and only if for every subset of the first set, the number of available partners is at least the size of that subset. To apply it, inspect small subsets and show that the condition fails when no complete matching exists.
霍尔定理指出，从第一个集合到第二个集合存在完全匹配当且仅当第一个集合的每个子集的可匹配对象数不小于该子集的大小。应用时检查小子集，若不满足条件则说明不存在完全匹配。
9. Algorithm Tracing and Complexity | 算法追踪与复杂度
Exam trace tables require you to show the value of every variable after each step. For sorting, bin packing, and Dijkstra, a neat table with rows and labelled columns is often the fastest way to earn full marks.
考试追踪表要求显示每一步后每个变量的值。对于排序、装箱和迪杰斯特拉算法，整洁的行列表格通常是拿满分的快速方式。
Efficiency is described using order of growth. Bubble sort requires O(n²) comparisons in the worst case, while quick sort has average complexity O(n log n). You may be asked to state which algorithm is more efficient for large inputs.
效率用增长阶描述。冒泡排序最坏情况需要 O(n²) 次比较，而快速排序平均复杂度为 O(n log n)。题目可能问哪种算法对大规模输入更高效。
For decision problems such as bin packing, first-fit is O(n²) or O(n log n) depending on implementation, but the examination focus is on the number of bins used rather than runtime. Always follow the order of items exactly as given unless the question asks for a sorted first-fit decreasing version.
对于装箱等决策问题，首次适应复杂度取决于实现为 O(n²) 或 O(n log n)，但考试重点是所用箱子数而不是运行时间。除非题目要求降序首次适应，否则严格按给定物品顺序执行。
10. Exam Technique: Common Pitfalls | 考试技巧：常见失分点
Show every step of your working. Decision Maths questions often award method marks for correct application of an algorithm, even if the final answer has a small arithmetic slip, so a clear trace can save many marks.
展示每一步计算过程。决策数学题经常为正确应用算法给方法分，即使最终答案有小算术错误，清晰的追踪也能保住很多分数。
Read the question carefully for direction requirements. In graphs, arrows on edges show traversable direction; in critical path analysis, precedence arrows show dependency direction. Confusing these can invalidate an entire network diagram.
仔细阅读题目对方向的要求。图中边上的箭头表示可通行方向；关键路径分析中，先后箭头表示依赖方向。混淆这些可能使整张网络图无效。
Check units and labels. For shortest paths, state length in the same units as edge weights; for linear programming, label axes and clearly shade the feasible region; for project scheduling, state the completion time and list critical activities explicitly.
检查单位和标签。最短路径要使用与边权相同的单位；线性规划要标明坐标轴并清晰涂色可行区域；项目调度要说明完成时间并明确列出关键活动。
If the question asks for an optimal solution, always state why it is optimal, such as matching a lower bound or testing all vertices. A numerical answer without justification often loses the final accuracy mark.
如果题目要求最优解，务必说明为何最优，例如与下界一致或检验了所有顶点。没有理由的数值答案经常丢掉最后的准确性分。
Published by TutorHao | Decision Maths 1 Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导