 # 一文读懂A-level中的Decision 决策数学

Decision 决策数学是Alevel考试中比较独特的一个科目，分为D1和D2,考试内容是各种算法的详细操作。这个科目是为计算机专业打基础的。由于相对来说比较简单，所以很多学生在考Alevel数学和高数时会选择考这两个。 Graph: A graph consists of vertices which are connected by edges.

Degreeorvalencyororder: the number of edges incident to a vertex.

Path: A finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once.

Walk: A path in which you are permitted to return to vertices more than once.

Cycleor circuit: A closed path, i.e. the end vertex of the last edge is the start vertex of the first edge.

Tree: A connected graph with no cycles.

Spanning tree: A spanning tree of a graph, G, is a subgraph which includes all the vertices of G and is also a graph.

Minimum spanning tree: A spanning tree such that the total length of its arcs is as small as possible.

Early event time: is the earliest time of arrival at the event allowing for the completion of all preceding activities.

Late event time: is the latest time that the event can be left without extending the time needed for the project.

Critical activity:An activity is described as a critical activity if any increase in its duration results in a corresponding increase in the duration of the whole project.

Critical path:A path from the source node to the sink node which entirely follows critical activities.

Total float: The total float of an activity is the amount of time that its start may be delayed without affecting the duration of the project.

Matching: A matching is the 1 to 1 pairing of some, or all, of the elements of one set, X, with elements of a second set, Y.

Bipartite graph:Consists of two sets of vertices, X and Y. the edges only join vertices in X to vertices in Y, not vertices within a set.

Maximal matching:A matching in which the number of arcs is as large as possible.

Complete matching:If both sets have n nodes, a complete matching is a matching with n arcs.

Alternating path:Starts at an unmatched node on one side of the bipartite graph and finishes at an unmatched node on the other side. It uses arcs that are alternately ‘not in’ or ‘in’ the initial matching.

1.  Describe how to carry out the first pass of a bubble sort on the numbers in the list.

Start at the beginning of the list. Pass through the list and compare adjacent values. For each pair of values

If they are in order, leave them.

If they are not in order, swap them.

2.   A list of n numbers needs to be sorted into descendingorder starting at the left-hand end of the list.

(a)  State which number in the list is guaranteed to be in the correct final position after the first pass. The smallest one

(b)  Write down the maximum number of passes required to sort a list of n numbers. (c)  Write down the maximum number of compares required to sort a list of n numbers. (d)  Write down the maximum number of swaps required to sort a list of n numbers. 3.   The binary search is applied to an ordered list of 1000 items. Determine the maximum number of iterations needed. 4.   It is not possible to draw a graph with an odd number of vertices of odd degree. Explain why not.

Because the sum of the degrees is twice the sum of the number of edges.

5.   Describe the differences between Prim’s algorithm and Kruskal’s algorithm. 6.   State, giving a reason for your answer, which algorithm is preferable for a large network for find the minimum spanning tree? 7.   A minimum spanning tree for a connected network has n edges. State the number of vertices in the network.  ## 推荐阅读

2022年QS世界大学排名（部分院校） more