| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Easy -1.2 This is a straightforward procedural question testing basic algorithm execution. Part (a) requires mechanical application of quick sort with no problem-solving—just following the standard algorithm steps. Part (b) applies Kruskal's algorithm using the sorted list, which is also routine procedure. Both are standard textbook exercises requiring only recall and careful execution, making this easier than average A-level questions. |
| Spec | 7.03k Sorting: quick sort7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Pivot chosen and 2 sublists, one \(<\) pivot, one \(>\) pivot | M1 | |
| \(1^{\text{st}}\) pass correct, all next set of pivots chosen consistently (condone 1 term lists) | A1 | |
| As above for \(2^{\text{nd}}\) pass | A1ft | |
| All correct, follow through; pivots must be chosen consistently | A1ft |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Using Kruskal – CF then GI | M1 | |
| First 4 arcs chosen correctly: CF, GI, (BC or BF – accept one, reject one), CD, EF | A1 | |
| All arcs chosen correctly (condone lack of rejection) | A1 | DF\(\times\), HI, BE\(\times\), AB, AC\(\times\), EG |
| All correct including rejections | A1 | Tree complete |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(107\ \text{m}\) | B1 | cao |
# Question 2:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Pivot chosen and 2 sublists, one $<$ pivot, one $>$ pivot | M1 | |
| $1^{\text{st}}$ pass correct, all next set of pivots chosen consistently (condone 1 term lists) | A1 | |
| As above for $2^{\text{nd}}$ pass | A1ft | |
| All correct, follow through; pivots must be chosen consistently | A1ft | |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Using Kruskal – CF then GI | M1 | |
| First 4 arcs chosen correctly: CF, GI, (BC or BF – accept one, reject one), CD, EF | A1 | |
| All arcs chosen correctly (condone lack of rejection) | A1 | DF$\times$, HI, BE$\times$, AB, AC$\times$, EG |
| All correct including rejections | A1 | Tree complete |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $107\ \text{m}$ | B1 | cao |
**Total: [10]**2. (a)\\
$\begin{array} { l l l l l l l l l l l } 18 & 20 & 11 & 7 & 17 & 15 & 14 & 21 & 23 & 16 & 9 \end{array}$
The list of numbers shown above is to be sorted into ascending order. Apply quick sort to obtain the sorted list. You must make your pivots clear.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{7396d930-0143-4876-b019-a4d73e09b172-3_839_1275_614_395}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
Figure 3 represents a network of paths in a park. The number on each arc represents the length of the path in metres.\\
(b) Using your answer to part (a) and Kruskal's algorithm, find a minimum spanning tree for the network in Figure 3. You should list the arcs in the order in which you consider them and state whether you are adding it to your minimum spanning tree.\\
(c) Find the total weight of the minimum spanning tree.\\
\hfill \mbox{\textit{Edexcel D1 2008 Q2 [10]}}