| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | State number of edges formula |
| Difficulty | Easy -1.8 Part (a) tests direct recall of the fundamental MST formula (n-1 edges), requiring no calculation or problem-solving. Part (b) applies Kruskal's algorithm mechanically to a small network—a standard textbook exercise with no novel insight required. This is significantly easier than average A-level content. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(15\) comparisons | B1 | For 16 items, first pass of quicksort = \(n-1 = 15\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(8\) comparisons | B1 | Shell sort first pass: \(\frac{n}{2} = 8\) comparisons |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(1\) comparison (minimum on final pass) | B1 | Shuttle sort final pass minimum = 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Maximum total = \(\frac{n(n-1)}{2} = \frac{16 \times 15}{2} = 120\) | M1 A1 | M1 for correct method |
# Question 3:
## Part (a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $15$ comparisons | B1 | For 16 items, first pass of quicksort = $n-1 = 15$ |
## Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $8$ comparisons | B1 | Shell sort first pass: $\frac{n}{2} = 8$ comparisons |
## Part (c):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $1$ comparison (minimum on final pass) | B1 | Shuttle sort final pass minimum = 1 |
## Part (d):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum total = $\frac{n(n-1)}{2} = \frac{16 \times 15}{2} = 120$ | M1 A1 | M1 for correct method |
---3
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item State the number of edges in a minimum spanning tree of a network with 10 vertices.
\item State the number of edges in a minimum spanning tree of a network with $n$ vertices.
\end{enumerate}\item The following network has 10 vertices: $A , B , \ldots , J$. The numbers on each edge represent the distances, in miles, between pairs of vertices.\\
\includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-004_1294_1118_785_445}
\begin{enumerate}[label=(\roman*)]
\item Use Kruskal's algorithm to find the minimum spanning tree for the network.
\item State the length of your spanning tree.
\item Draw your spanning tree.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 Q3}}