| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2004 |
| Session | November |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Binary Search Execution |
| Difficulty | Easy -1.8 This question tests purely mechanical execution of standard algorithms (quick sort, bubble sort, binary search) with no problem-solving or insight required. Students simply follow memorized procedures step-by-step on small datasets. This is significantly easier than routine calculus questions that at least require some technique selection. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. \(45\ 37\ 18\ \boxed{46}\ 56\ 79\ 90\ 81\ 51\) | M1A1 | |
| or \(37\ 18\ \boxed{45}\ 56\ 79\ 46\ 90\ 81\ 51\) | ||
| or \(45\ 37\ 46\ 18\ \boxed{51}\ 56\ 79\ 90\ 81\) | ||
| (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(56\ 45\ 79\ 46\ 37\ 90\ 81\ 51\ 18\) | M1A1 | |
| or \(90\ 45\ 56\ 37\ 79\ 46\ 18\ 81\ 51\) | ||
| (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(\left[\frac{1+11}{2}\right] = 6\), value 46, discard top | M1 | |
| \(\left[\frac{7+11}{2}\right] = 9\), value 71, discard top | A1 | |
| \(\left[\frac{10+11}{2}\right] = 11\), value 94, discard bottom | A1 | |
| List reduces to \(10^{\text{th}}\) value. This is 73. 73 has been located as the \(10^{\text{th}}\) value. | A1 | |
| (4) | ||
| [8] |
# Question 4:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. $45\ 37\ 18\ \boxed{46}\ 56\ 79\ 90\ 81\ 51$ | M1A1 | |
| or $37\ 18\ \boxed{45}\ 56\ 79\ 46\ 90\ 81\ 51$ | | |
| or $45\ 37\ 46\ 18\ \boxed{51}\ 56\ 79\ 90\ 81$ | | |
| | (2) | |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $56\ 45\ 79\ 46\ 37\ 90\ 81\ 51\ 18$ | M1A1 | |
| or $90\ 45\ 56\ 37\ 79\ 46\ 18\ 81\ 51$ | | |
| | (2) | |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $\left[\frac{1+11}{2}\right] = 6$, value 46, discard top | M1 | |
| $\left[\frac{7+11}{2}\right] = 9$, value 71, discard top | A1 | |
| $\left[\frac{10+11}{2}\right] = 11$, value 94, discard bottom | A1 | |
| List reduces to $10^{\text{th}}$ value. This is 73. 73 has been located as the $10^{\text{th}}$ value. | A1 | |
| | (4) | |
| | **[8]** | |
---4. $45 , \quad 56 , \quad 37 , \quad 79 , \quad 46 , \quad 18 , \quad 90 , \quad 81 , \quad 51$
\begin{enumerate}[label=(\alph*)]
\item Using the quick sort algorithm, perform one complete iteration towards sorting these numbers into ascending order.\\
(2)
\item Using the bubble sort algorithm, perform one complete pass towards sorting the original list into descending order.
Another list of numbers, in ascending order, is
$$7 , \quad 23 , \quad 31 , \quad 37 , \quad 41 , \quad 44 , \quad 50 , \quad 62 , \quad 71 , \quad 73 , \quad 94$$
\item Use the binary search algorithm to locate the number 73 in this list.
\section*{5.}
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-06_1246_1168_294_427}
\end{center}
\end{figure}
Figure 2 shows a network of roads connecting villages. The length of each road, in km, is shown. Village $B$ has only a small footbridge over the river which runs through the village. It can be accessed by two roads, from $A$ and $D$.
The driver of a snowplough, based at $F$, is planning a route to enable her to clear all the roads of snow. The route should be of minimum length. Each road can be cleared by driving along it once. The snowplough cannot cross the footbridge.
Showing all your working and using an appropriate algorithm,
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2004 Q4 [8]}}