Edexcel FD1 AS 2022 June — Question 1 9 marks

Exam BoardEdexcel
ModuleFD1 AS (Further Decision 1 AS)
Year2022
SessionJune
Marks9
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicSorting Algorithms
TypeQuick Sort Execution
DifficultyEasy -1.2 This is a routine algorithmic execution question requiring mechanical application of quick sort and Kruskal's algorithm with no problem-solving or insight needed. Part (a) is straightforward pivot selection and partitioning on a small list; part (b) is standard MST construction by considering edges in weight order. These are textbook procedures tested exactly as taught, making this easier than average A-level questions.
Spec7.03k Sorting: quick sort7.04c Travelling salesman upper bound: nearest neighbour method
  1. 55534345928373452334247
The list of eleven numbers shown above is to be sorted into ascending order.
  1. Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify your pivots clearly.
    (4) \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{c8134d3b-71cb-4b92-ac54-81a4ff8f3011-03_814_1545_614_260} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure}
  2. Use Kruskal's algorithm to find the minimum spanning tree for the network in Figure 1. You should list the arcs in the order in which you consider them. For each arc, state whether or not you are adding it to your minimum spanning tree.
    1. Draw the minimum spanning tree on Diagram 1 in the answer book.
    2. State the total weight of the tree.
Question 1:
Part (a)
Quick Sort (middle right pivot)
AnswerMarks Guidance
AnswerMarks Guidance
Pivot = 37; correct first pass giving 37 in boldM1 1.1b – method mark for attempting quick sort with middle right pivot
28 41 correct (pivots for second pass)A1 1.1b
33 52 correct (pivots for third pass)A1ft 1.1b – follow through
47 (55) correct; sort completeA1 1.1b
(4 marks)
Part (b)
Kruskal's Algorithm
AnswerMarks Guidance
AnswerMarks Guidance
DE, CF, CD, reject CEM1 1.1b – method mark for starting Kruskal's correctly
BC, EG, reject FGA1 1.1b
reject BD, AB, (reject AC, reject DG)A1 1.1b
(3 marks)
Part (c)(i)
Minimum Spanning Tree diagram
AnswerMarks Guidance
AnswerMarks Guidance
Correct spanning tree drawn connecting A, B, C, D, E, F, G with edges from Kruskal's resultB1 2.2a
Part (c)(ii)
Total weight
AnswerMarks Guidance
AnswerMarks Guidance
Total weight \(= 230\)B1 2.2a
(2 marks)
(9 marks total)
Question 1:
Part (a)
AnswerMarks Guidance
AnswerMarks Guidance
Quick Sort, pivot chosen as middle-left or middle-right elementM1 If choosing one pivot per iteration then M1 only
First two passes correct (pivots for third pass need not be chosen)A1
Third and fourth passes correct, following through from second passA2ft After second pass list must contain 10, 11 or 12 numbers; pivots for fifth pass need not be chosen
Fifth pass included (middle-right) or sixth pass (middle-left)A1 cso
SC: If list sorted into descending order, award maximum M1A1A0A0 (2 marks)
Part (b)
AnswerMarks Guidance
AnswerMarks Guidance
First three arcs correctly chosen (DE, CF, CD), arc CE rejected at correct timeB1M1 Condone list of weights 28, 33, 34; reject 37. No follow through from incorrect list
First five arcs correctly chosen (DE, CF, CD, BC, EG), arc FG rejected at correct timeA1 Must state arcs not corresponding weights
All rejections correct and at correct timeA1 Explicit rejection of AC and DG must be in correct order if stated
Part (c)(i)
AnswerMarks Guidance
AnswerMarks Guidance
Correct MST drawnB1
Part (c)(ii)
AnswerMarks Guidance
AnswerMarks Guidance
Correct weightB1 
# Question 1:

## Part (a)

**Quick Sort (middle right pivot)**

| Answer | Marks | Guidance |
|--------|-------|----------|
| Pivot = 37; correct first pass giving **37** in bold | M1 | 1.1b – method mark for attempting quick sort with middle right pivot |
| 28 41 correct (pivots for second pass) | A1 | 1.1b |
| 33 52 correct (pivots for third pass) | A1ft | 1.1b – follow through |
| 47 (55) correct; sort complete | A1 | 1.1b |

**(4 marks)**

---

## Part (b)

**Kruskal's Algorithm**

| Answer | Marks | Guidance |
|--------|-------|----------|
| DE, CF, CD, reject CE | M1 | 1.1b – method mark for starting Kruskal's correctly |
| BC, EG, reject FG | A1 | 1.1b |
| reject BD, AB, (reject AC, reject DG) | A1 | 1.1b |

**(3 marks)**

---

## Part (c)(i)

**Minimum Spanning Tree diagram**

| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct spanning tree drawn connecting A, B, C, D, E, F, G with edges from Kruskal's result | B1 | 2.2a |

## Part (c)(ii)

**Total weight**

| Answer | Marks | Guidance |
|--------|-------|----------|
| Total weight $= 230$ | B1 | 2.2a |

**(2 marks)**

---

**(9 marks total)**

# Question 1:

## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Quick Sort, pivot chosen as middle-left or middle-right element | M1 | If choosing one pivot per iteration then M1 only |
| First two passes correct (pivots for third pass need not be chosen) | A1 | |
| Third and fourth passes correct, following through from second pass | A2ft | After second pass list must contain 10, 11 or 12 numbers; pivots for fifth pass need not be chosen |
| Fifth pass included (middle-right) or sixth pass (middle-left) | A1 | cso |

**SC:** If list sorted into descending order, award maximum M1A1A0A0 (2 marks)

## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| First three arcs correctly chosen (DE, CF, CD), arc CE rejected at correct time | B1M1 | Condone list of weights 28, 33, 34; reject 37. No follow through from incorrect list |
| First five arcs correctly chosen (DE, CF, CD, BC, EG), arc FG rejected at correct time | A1 | Must state arcs not corresponding weights |
| All rejections correct and at correct time | A1 | Explicit rejection of AC and DG must be in correct order if stated |

## Part (c)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct MST drawn | B1 | |

## Part (c)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct weight | B1 | |

---
\begin{enumerate}
  \item 55534345928373452334247
\end{enumerate}

The list of eleven numbers shown above is to be sorted into ascending order.\\
(a) Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify your pivots clearly.\\
(4)

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{c8134d3b-71cb-4b92-ac54-81a4ff8f3011-03_814_1545_614_260}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}

(b) Use Kruskal's algorithm to find the minimum spanning tree for the network in Figure 1. You should list the arcs in the order in which you consider them. For each arc, state whether or not you are adding it to your minimum spanning tree.\\
(c) (i) Draw the minimum spanning tree on Diagram 1 in the answer book.\\
(ii) State the total weight of the tree.\\

\hfill \mbox{\textit{Edexcel FD1 AS 2022 Q1 [9]}}
This paper (4 questions)
View full paper
Q1 9 Q2 8 Q3 14 Q4 9