📚 Edexcel D1 Decision Mathematics 1 Complete Revision Guide | 爱德思D1决策数学1完整复习指南
This revision guide covers the main topics in Edexcel Decision Mathematics 1 (D1), including algorithms, graph theory, network optimisation, critical path analysis, linear programming and matchings. It is designed to help you master key definitions, standard procedures and exam-style techniques for the D1 paper.
本复习指南涵盖爱德思决策数学1（D1）的主要主题，包括算法、图论、网络优化、关键路径分析、线性规划和匹配。旨在帮助你掌握D1考试中的关键定义、标准流程和题型技巧。
1. Algorithms and Flow Charts | 算法与流程图
An algorithm is a finite, step-by-step set of instructions that always finishes. In Edexcel D1 you may be asked to trace an algorithm, complete a flow chart, or explain what an algorithm does. Flow charts use ovals for start and end, rectangles for processes, and diamonds for decisions. Always record values after each pass or iteration clearly.
算法是一组有限、逐步的指令，且总能结束。在爱德思D1中，你可能被要求追踪某个算法、填写流程图，或解释算法的功能。流程图用椭圆表示开始和结束，矩形表示处理，菱形表示判断。每次遍历或迭代后要清晰记录变量值。
For sorting and searching, the three standard algorithms in D1 are bubble sort, quick sort and binary search. You must be able to follow each step, state the number of comparisons, and identify whether the list is already sorted after a pass.
对于排序与搜索，D1中的三种标准算法是冒泡排序、快速排序和二分查找。你必须能够执行每一步、说明比较次数，并判断一趟后列表是否已有序。
2. Sorting Algorithms in Detail | 排序算法详解
Bubble sort compares adjacent pairs and swaps them if they are out of order. After the first pass the largest value is in its final position; after k passes the k largest values are fixed. For n items, the maximum number of comparisons and swaps is ½ n(n − 1). Bubble sort is easy to trace but inefficient for large lists.
冒泡排序比较相邻元素，若顺序错误则交换。第一趟后最大值到达最终位置；经过 k 趟后最大的 k 个值已固定。对于 n 个数据，最大比较次数和交换次数为 ½ n(n − 1)。冒泡排序易于追踪，但对大量数据效率较低。
Quick sort chooses a pivot, writes items smaller than the pivot to its left and larger items to its right, then sorts each sub-list recursively. The pivot is usually the middle value of the current list or sub-list. If the list contains duplicate values, keep them on the same side of the pivot according to the rule you state.
快速排序选择一个基准值，将小于基准的写在左边，大于基准的写在右边，然后递归排序各子列表。基准值通常取当前列表或子列表的中间值。如果列表包含重复值，则按你声明的规则将它们放在基准值的同一侧。
3. Binary Search and Bin Packing | 二分查找与装箱问题
Binary search works only on an ordered list. Compare the target with the middle item; if it is larger, discard the lower half, and if it is smaller, discard the upper half. Repeat until the target is found or no items remain. The maximum number of comparisons is logarithmic, so binary search is very efficient.
二分查找只适用于有序列表。将目标与中间项比较；若目标更大，则舍弃下半部分；若目标更小，则舍弃上半部分。重复此过程直到找到目标或没有剩余项。最大比较次数为对数级别，因此二分查找非常高效。
Bin packing problems ask for the minimum number of bins of fixed capacity needed to store a given list of weights. First-fit places each item into the earliest bin that has enough remaining space. First-fit decreasing sorts weights into descending order before applying first-fit. Full-bin looks for groups that exactly fill a bin. First-fit decreasing usually performs better than first-fit, but it does not guarantee the optimum.
装箱问题要求用固定容量的箱子存放给定重量列表，求最少箱数。首次适应法把每件物品放入最早能容纳它的箱子。降序首次适应法先把重量按降序排列，再用首次适应法。满箱法寻找恰好装满箱子的组合。降序首次适应法通常优于首次适应法，但不保证得到最优解。
4. Graph Theory Definitions | 图论定义
A graph consists of vertices connected by edges. The degree of a vertex is the number of edges meeting it. A path visits each vertex at most once; a cycle is a closed path. A tree is a connected graph with no cycles. A complete graph Kₙ has every pair of vertices joined, giving ½ n(n − 1) edges. A graph is planar if it can be drawn without crossing edges; K₅ and K₃,₃ are non-planar.
图由顶点和连接顶点的边组成。顶点的度是与该顶点相连的边数。路径中每个顶点最多出现一次；环是闭合的路径。树是连通且无环的图。完全图 Kₙ 的每对顶点都相连，因此有 ½ n(n − 1) 条边。若图可以画成没有交叉边，则称为平面图；K₅ 和 K₃,₃ 是非平面图。
Edges in Kₙ = ½ n(n − 1)
The handshaking lemma states that the sum of all vertex degrees is exactly 2 × number of edges. Therefore the number of odd-degree vertices must be even. This fact is used repeatedly in route inspection and network construction problems.
握手引理指出所有顶点度数之和恰好等于边数的 2 倍。因此奇度顶点的个数必为偶数。这一事实在路径检查和网络构建问题中会反复使用。
5. Minimum Spanning Trees | 最小生成树
A minimum spanning tree is a tree connecting all vertices with the smallest possible total edge weight. Kruskal’s algorithm sorts all edges by increasing weight and adds the next edge unless it would create a cycle. Prim’s algorithm starts at any vertex and repeatedly adds the cheapest edge connecting the growing tree to a new vertex.
最小生成树是用尽可能小的总边权连接所有顶点的树。Kruskal算法将所有边按权重递增排序，依次加入不会形成环的下一条边。Prim算法从任意顶点开始，反复加入将当前树与新顶点连接且权重最小的边。
When several edges have equal weight, you must state your tie-breaking rule, such as choosing the edge that appears first alphabetically or the edge with the smallest end vertex. Both Kruskal and Prim always produce the same total minimum weight, though the edges selected may differ.
当多条边权重相同时，必须说明你的平局处理规则，例如选择字母顺序最先的边，或选择端点编号最小的边。Kruskal和Prim算法总是得到相同的最小总权重，尽管所选边可能不同。
6. Dijkstra’s Shortest Path Algorithm | Dijkstra最短路径算法
Dijkstra’s algorithm finds the shortest path from a start vertex to every other vertex in a weighted network. At each stage, label vertices with working values in boxes, choose the smallest temporary label, make it permanent, and update the working values of its neighbours. Always shade or mark permanent labels.
Dijkstra算法在带权网络中找到从起点到其他各顶点的最短路径。每一步用方框中的工作值标记顶点，选择最小的临时标记使其永久化，并更新相邻顶点的工作值。务必对永久标记进行阴影或记号标注。
The final permanent label at each vertex gives the shortest distance from the start. To find the actual route, trace backwards from the target vertex: at each step move to the previous vertex whose permanent label plus edge weight equals the current label.
每个顶点最终的永久标记就是从起点出发的最短距离。要找到实际路径，从目标顶点反向追踪：每一步移动到满足其永久标记加边权等于当前标记的前一个顶点。
7. Route Inspection | 路径检查问题
A route is Eulerian if it starts and ends at the same vertex and uses every edge exactly once; this is possible exactly when all vertices have even degree. If exactly two vertices have odd degree, the graph is semi-Eulerian: an open route must start at one odd vertex and end at the other.
一条路线若从同一顶点出发并结束，且每条边恰好经过一次，则称为欧拉路线；当所有顶点度数均为偶数时才有可能。若恰好有两个奇度顶点，则图为半欧拉图：开放路线必须从一个奇度顶点开始，在另一个结束。
For route inspection, if there are more than two odd vertices, list all odd vertices and find the shortest distances between each pair. Pair the odd vertices so that the total extra distance is minimised, then add these shortest paths as repeated edges. The inspection route length is the total network weight plus the minimum extra weight.
对于路径检查问题，若有超过两个奇度顶点，列出所有奇度顶点并求出每对之间的最短距离。将奇度顶点配对，使总额外距离最小，然后将这些最短路径作为重复边加入。检查路线长度为网络总权重加最小额外权重。
Inspection length = total weight + minimum extra weight
8. Critical Path Analysis | 关键路径分析
Critical path analysis uses activity-on-arc networks to plan a project. Dummy activities are shown as dashed arrows and represent dependence without consuming time or resources. Forward pass gives the earliest event times; backward pass gives the latest event times.
关键路径分析使用活动–弧网络来规划项目。虚活动用虚线箭头表示，代表依赖关系但不消耗时间或资源。正向递推给出事件的最早时间；反向递推给出事件的最迟时间。
An activity is critical if its total float is zero. Total float measures how long an activity can be delayed without delaying the whole project. It can be calculated as latest start time minus earliest start time, or latest finish time minus earliest finish time. The critical path is the longest path through the network and determines the minimum project duration.
若某活动的总时差为零，则该活动为关键活动。总时差衡量某活动在不延迟整个项目的情况下可以推迟的时间。它可以用最迟开始时间减最早开始时间，或用最迟完成时间减最早完成时间来计算。关键路径是网络中最长的路径，决定项目的最短工期。
Total Float = Latest Start − Earliest Start = Latest Finish − Earliest Finish
9. Linear Programming | 线性规划
Linear programming maximises or minimises a linear objective function subject to linear inequality constraints. Define decision variables clearly, write the constraints, and draw the feasible region on a graph. Use an objective line, for example P =
Published by TutorHao | Exam Prep Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply