Questions - AQA D1 - A-Level Maths

Trace the algorithm when the input values are:
1. $A = 36$ and $B = 16$;
2. $A = 11$ and $B = 7$.
State the purpose of the algorithm.

AQA D1 2013 June Q7

7 Paul is a florist. Every day, he makes three types of floral bouquet: gold, silver and bronze. Each gold bouquet has 6 roses, 6 carnations and 6 dahlias.
Each silver bouquet has 4 roses, 6 carnations and 4 dahlias.
Each bronze bouquet has 3 roses, 4 carnations and 4 dahlias.
Each day, Paul must use at least 420 roses and at least 480 carnations, but he can use at most 720 dahlias. Each day, Paul makes $x$ gold bouquets, $y$ silver bouquets and $z$ bronze bouquets.

In addition to $x \geqslant 0 , y \geqslant 0$ and $z \geqslant 0$, find three inequalities in $x , y$ and $z$ that model the above constraints.
On a particular day, Paul makes the same number of silver bouquets as bronze bouquets.
1. Show that $x$ and $y$ must satisfy the following inequalities. $$\begin{aligned} & 6 x + 7 y \geqslant 420
  & 3 x + 5 y \geqslant 240
  & 3 x + 4 y \leqslant 360 \end{aligned}$$
2. Paul makes a profit of $\pounds 4$ on each gold bouquet sold, a profit of $\pounds 2.50$ on each silver bouquet sold and a profit of $\pounds 2.50$ on each bronze bouquet sold. Each day, Paul sells all the bouquets he makes. Paul wishes to maximise his daily profit, $\pounds P$. Draw a suitable diagram, on the grid opposite, to enable this problem to be solved graphically, indicating the feasible region and the direction of the objective line.
  (6 marks)
3. Use your diagram to find Paul's maximum daily profit and the number of each type of bouquet he must make to achieve this maximum.
On another day, Paul again makes the same number of silver bouquets as bronze bouquets, but he makes a profit of $\pounds 2$ on each gold bouquet sold, a profit of $\pounds 6$ on each silver bouquet sold and a profit of $\pounds 6$ on each bronze bouquet sold. Find Paul's maximum daily profit, and the number of each type of bouquet he must make to achieve this maximum.
(3 marks) Turn over -

AQA D1 Q3

1. State the number of edges in a minimum spanning tree of a network with 10 vertices.
2. State the number of edges in a minimum spanning tree of a network with $n$ vertices.
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}
1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
2. State the length of your spanning tree.
3. Draw your spanning tree.

AQA D1 Q4

4 The diagram shows the feasible region of a linear programming problem.
\includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-005_1349_1395_408_294}

On the feasible region, find:
1. the maximum value of $2 x + 3 y$;
2. the maximum value of $3 x + 2 y$;
3. the minimum value of $- 2 x + y$.
Find the 5 inequalities that define the feasible region.

AQA D1 Q5

5 [Figure 1, printed on the insert, is provided for use in this question.]
The network shows the times, in minutes, to travel between 10 towns.
\includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-006_412_1561_568_233}

Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from $A$ to $J$.
(6 marks)
State the corresponding route.
(1 mark)

AQA D1 Q7

7 Stella is visiting Tijuana on a day trip. The diagram shows the lengths, in metres, of the roads near the bus station.
\includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-007_1539_1162_495_424} Stella leaves the bus station at $A$. She decides to walk along all of the roads at least once before returning to $A$.

Explain why it is not possible to start from $A$, travel along each road only once and return to $A$.
Find the length of an optimal 'Chinese postman' route around the network, starting and finishing at $A$.
At each of the 9 places $B , C , \ldots , J$, there is a statue. Find the number of times that Stella will pass a statue if she follows her optimal route.

AQA D1 2006 January Q1

Draw a bipartite graph representing the following adjacency matrix.
(2 marks)

	$\boldsymbol { U }$	$V$	$\boldsymbol { W }$	$\boldsymbol { X }$	$\boldsymbol { Y }$	$\boldsymbol { Z }$
$\boldsymbol { A }$	1	0	1	0	1	0
$\boldsymbol { B }$	0	1	0	1	0	0
$\boldsymbol { C }$	0	1	0	0	0	1
$\boldsymbol { D }$	0	0	0	1	0	0
$\boldsymbol { E }$	0	0	1	0	1	1
$\boldsymbol { F }$	0	0	0	1	1	0

Given that initially $A$ is matched to $W , B$ is matched to $X , C$ is matched to $V$, and $E$ is matched to $Y$, use the alternating path algorithm, from this initial matching, to find a complete matching. List your complete matching.

AQA D1 2006 January Q2

2 Use the quicksort algorithm to rearrange the following numbers into ascending order. Indicate clearly the pivots that you use. $$\begin{array} { l l l l l l l l } 18 & 23 & 12 & 7 & 26 & 19 & 16 & 24 \end{array}$$

AQA D1 2006 January Q3

1. State the number of edges in a minimum spanning tree of a network with 10 vertices.
2. State the number of edges in a minimum spanning tree of a network with $n$ vertices.
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]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-03_1294_1118_785_445}
1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
2. State the length of your spanning tree.
3. Draw your spanning tree.

AQA D1 2006 January Q4

4 The diagram shows the feasible region of a linear programming problem.
\includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-04_1349_1395_408_294}

On the feasible region, find:
1. the maximum value of $2 x + 3 y$;
2. the maximum value of $3 x + 2 y$;
3. the minimum value of $- 2 x + y$.
Find the 5 inequalities that define the feasible region.

AQA D1 2006 January Q5

5 [Figure 1, printed on the insert, is provided for use in this question.]
The network shows the times, in minutes, to travel between 10 towns.
\includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-05_412_1561_568_233}

Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from $A$ to $J$.
(6 marks)
State the corresponding route.
(1 mark)

AQA D1 2006 January Q6

6 Two algorithms are shown. \section*{Algorithm 1}

Line 10	Input $P$
Line 20	Input $R$
Line 30	Input $T$
Line 40	Let $I = ( P * R * T ) / 100$
Line 50	Let $A = P + I$
Line 60	Let $M = A / ( 12 * T )$
Line 70	Print $M$
Line 80	Stop

\section*{Algorithm 2}

Line 10	Input $P$
Line 20	Input $R$
Line 30	Input $T$
Line 40	Let $A = P$
Line 50	$K = 0$
Line 60	Let $K = K + 1$
Line 70	Let $I = ( A * R ) / 100$
Line 80	Let $A = A + I$
Line 90	If $K < T$ then goto Line 60
Line 100	Let $M = A / ( 12 * T )$
Line 110	Print $M$
Line 120	Stop

In the case where the input values are $P = 400 , R = 5$ and $T = 3$ :

trace Algorithm 1;
trace Algorithm 2.

AQA D1 2006 January Q7

7 Stella is visiting Tijuana on a day trip. The diagram shows the lengths, in metres, of the roads near the bus station.
\includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-06_1539_1162_495_424} Stella leaves the bus station at $A$. She decides to walk along all of the roads at least once before returning to $A$.

Explain why it is not possible to start from $A$, travel along each road only once and return to $A$.
Find the length of an optimal 'Chinese postman' route around the network, starting and finishing at $A$.
At each of the 9 places $B , C , \ldots , J$, there is a statue. Find the number of times that Stella will pass a statue if she follows her optimal route.

AQA D1 2006 January Q8

8 Salvadore is visiting six famous places in Barcelona: La Pedrera $( L )$, Nou Camp $( N )$, Olympic Village $( O )$, Park Guell $( P )$, Ramblas $( R )$ and Sagrada Familia $( S )$. Owing to the traffic system the time taken to travel between two places may vary according to the direction of travel. The table shows the times, in minutes, that it will take to travel between the six places.

\backslashbox{From}{To}	La Pedrera ( $L$ )	Nou Camp (N)	Olympic Village ( $O$ )	Park Guell (P)	Ramblas (R)	Sagrada Familia ( $S$ )
La Pedrera $( L )$	-	35	30	30	37	35
Nou Camp $( N )$	25	-	20	21	25	40
Olympic Village ( $O$ )	15	40	-	25	30	29
Park Guell ( $P$ )	30	35	25	-	35	20
Ramblas ( $R$ )	20	30	17	25	-	25
Sagrada Familia ( $S$ )	25	35	29	20	30	-

Find the total travelling time for:
1. the route $L N O L$;
2. the route $L O N L$.
Give an example of a Hamiltonian cycle in the context of the above situation.
Salvadore intends to travel from one place to another until he has visited all of the places before returning to his starting place.
1. Show that, using the nearest neighbour algorithm starting from Sagrada Familia $( S )$, the total travelling time for Salvadore is 145 minutes.
2. Explain why your answer to part (c)(i) is an upper bound for the minimum travelling time for Salvadore.
3. Salvadore starts from Sagrada Familia ( $S$ ) and then visits Ramblas ( $R$ ). Given that he visits Nou Camp $( N )$ before Park Guell $( P )$, find an improved upper bound for the total travelling time for Salvadore.

AQA D1 2006 January Q9

AQA D1 2007 January Q1

1 The following network shows the lengths, in miles, of roads connecting nine villages.
\includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-02_856_1251_568_374}

Use Prim's algorithm, starting from $A$, to find a minimum spanning tree for the network.
Find the length of your minimum spanning tree.
Draw your minimum spanning tree.
State the number of other spanning trees that are of the same length as your answer in part (a).

AQA D1 2007 January Q2

2 Five people $A , B , C , D$ and $E$ are to be matched to five tasks $R , S , T , U$ and $V$.
The table shows the tasks that each person is able to undertake.

Person	Tasks
$A$	$R , V$
$B$	$R , T$
$C$	$T , V$
$D$	$U , V$
$E$	$S , U$

Show this information on a bipartite graph.
Initially, $A$ is matched to task $V , B$ to task $R , C$ to task $T$, and $E$ to task $U$. Demonstrate, by using an alternating path from this initial matching, how each person can be matched to a task.

AQA D1 2007 January Q3

3 Mark is driving around the one-way system in Leicester. The following table shows the times, in minutes, for Mark to drive between four places: $A , B , C$ and $D$. Mark decides to start from $A$, drive to the other three places and then return to $A$. Mark wants to keep his driving time to a minimum.

\backslashbox{From}{To}	$\boldsymbol { A }$	$\boldsymbol { B }$	$\boldsymbol { C }$	$\boldsymbol { D }$
A	-	8	6	11
B	14	-	13	25
C	14	9	-	17
$\boldsymbol { D }$	26	10	18	-

Find the length of the tour $A B C D A$.
Find the length of the tour $A D C B A$.
Find the length of the tour using the nearest neighbour algorithm starting from $A$.
Write down which of your answers to parts (a), (b) and (c) gives the best upper bound for Mark's driving time.

AQA D1 2007 January Q4

A student is using a bubble sort to rearrange seven numbers into ascending order.
Her correct solution is as follows:
Initial list 18 17 13 26 10 14 24
After 1st pass 17 13 18 10 14 24 26
After 2nd pass 13 17 10 14 18 24 26
After 3rd pass 13 10 14 17 18 24 26
After 4th pass 10 13 14 17 18 24 26
After 5th pass 10 13 14 17 18 24 26
Write down the number of comparisons and swaps on each of the five passes.
Find the maximum number of comparisons and the maximum number of swaps that might be needed in a bubble sort to rearrange seven numbers into ascending order.

AQA D1 2007 January Q5

5 A student is using the following algorithm with different values of $A$ and $B$.

Line 10	Input $A , B$
Line 20	Let $C = 0$ and let $D = 0$
Line 30	Let $C = C + A$
Line 40	Let $D = D + B$
Line 50	If $C = D$ then go to Line 110
Line 60	If $C > D$ then go to Line 90
Line 70	Let $C = C + A$
Line 80	Go to Line 50
Line 90	Let $D = D + B$
Line 100	Go to Line 50
Line 110	Print $C$
Line 120	End

1. Trace the algorithm in the case where $A = 2$ and $B = 3$.
2. Trace the algorithm in the case where $A = 6$ and $B = 8$.
State the purpose of the algorithm.
Write down the final value of $C$ in the case where $A = 200$ and $B = 300$.

AQA D1 2007 January Q6

6 [Figure 1, printed on the insert, is provided for use in this question.]
Dino is to have a rectangular swimming pool at his villa.
He wants its width to be at least 2 metres and its length to be at least 5 metres.
He wants its length to be at least twice its width.
He wants its length to be no more than three times its width.
Each metre of the width of the pool costs $\pounds 1000$ and each metre of the length of the pool costs $\pounds 500$. He has $\pounds 9000$ available. Let the width of the pool be $x$ metres and the length of the pool be $y$ metres.

Show that one of the constraints leads to the inequality $$2 x + y \leqslant 18$$
Find four further inequalities.
On Figure 1, draw a suitable diagram to show the feasible region.
Use your diagram to find the maximum width of the pool. State the corresponding length of the pool.

AQA D1 2007 January Q7

7 [Figure 2, printed on the insert, is provided for use in this question.]
The network shows the times, in seconds, taken by Craig to walk along walkways connecting ten hotels in Las Vegas.
\includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-07_1435_1267_525_351} The total of all the times in the diagram is 2280 seconds.

1. Craig is staying at the Circus ( $C$ ) and has to visit the Oriental ( $O$ ). Use Dijkstra's algorithm on Figure 2 to find the minimum time to walk from $C$ to $O$.
2. Write down the corresponding route.
1. Find, by inspection, the shortest time to walk from $A$ to $M$.
2. Craig intends to walk along all the walkways. Find the minimum time for Craig to walk along every walkway and return to his starting point.

AQA D1 2007 January Q8

The diagram shows a graph $\mathbf { G }$ with 9 vertices and 9 edges.
\includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_188_204_411_708}
\includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_184_204_415_1105}
\includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_183_204_612_909}
1. State the minimum number of edges that need to be added to $\mathbf { G }$ to make a connected graph. Draw an example of such a graph.
2. State the minimum number of edges that need to be added to $\mathbf { G }$ to make the graph Hamiltonian. Draw an example of such a graph.
3. State the minimum number of edges that need to be added to $\mathbf { G }$ to make the graph Eulerian. Draw an example of such a graph.
A complete graph has $n$ vertices and is Eulerian.
1. State the condition that $n$ must satisfy.
2. In addition, the number of edges in a Hamiltonian cycle for the graph is the same as the number of edges in an Eulerian trail. State the value of $n$.

AQA D1 2008 January Q1

1 Five people, $A , B , C , D$ and $E$, are to be matched to five tasks, $J , K , L , M$ and $N$. The table shows the tasks that each person is able to undertake.

Person	Task
$A$	$J , N$
$B$	$J , L$
$C$	$L , N$
$D$	$M , N$
$E$	$K , M$

Show this information on a bipartite graph.
Initially, $A$ is matched to task $N , B$ to task $J , C$ to task $L$, and $E$ to task $M$. Complete the alternating path $D - M \ldots$, from this initial matching, to demonstrate how each person can be matched to a task.
(3 marks)

AQA D1 2008 January Q2

2 [Figure 1, printed on the insert, is provided for use in this question.]
The feasible region of a linear programming problem is represented by $$\begin{aligned} x + y & \leqslant 30
2 x + y & \leqslant 40
y & \geqslant 5
x & \geqslant 4
y & \geqslant \frac { 1 } { 2 } x \end{aligned}$$

On Figure 1, draw a suitable diagram to represent these inequalities and indicate the feasible region.
Use your diagram to find the maximum value of $F$, on the feasible region, in the case where:
1. $F = 3 x + y$;
2. $F = x + 3 y$.

	\(\boldsymbol { U }\)	\(V\)	\(\boldsymbol { W }\)	\(\boldsymbol { X }\)	\(\boldsymbol { Y }\)	\(\boldsymbol { Z }\)
\(\boldsymbol { A }\)	1	0	1	0	1	0
\(\boldsymbol { B }\)	0	1	0	1	0	0
\(\boldsymbol { C }\)	0	1	0	0	0	1
\(\boldsymbol { D }\)	0	0	0	1	0	0
\(\boldsymbol { E }\)	0	0	1	0	1	1
\(\boldsymbol { F }\)	0	0	0	1	1	0

Person	Tasks
\(A\)	\(R , V\)
\(B\)	\(R , T\)
\(C\)	\(T , V\)
\(D\)	\(U , V\)
\(E\)	\(S , U\)

Person	Task
\(A\)	\(J , N\)
\(B\)	\(J , L\)
\(C\)	\(L , N\)
\(D\)	\(M , N\)
\(E\)	\(K , M\)

Line 10	Input \(P\)
Line 20	Input \(R\)
Line 30	Input \(T\)
Line 40	Let \(I = ( P * R * T ) / 100\)
Line 50	Let \(A = P + I\)
Line 60	Let \(M = A / ( 12 * T )\)
Line 70	Print \(M\)
Line 80	Stop

\backslashbox{From}{To}	La Pedrera ( \(L\) )	Nou Camp (N)	Olympic Village ( \(O\) )	Park Guell (P)	Ramblas (R)	Sagrada Familia ( \(S\) )
La Pedrera \(( L )\)	-	35	30	30	37	35
Nou Camp \(( N )\)	25	-	20	21	25	40
Olympic Village ( \(O\) )	15	40	-	25	30	29
Park Guell ( \(P\) )	30	35	25	-	35	20
Ramblas ( \(R\) )	20	30	17	25	-	25
Sagrada Familia ( \(S\) )	25	35	29	20	30	-

Initial list	18	17	13	26	10	14	24
After 1st pass	17	13	18	10	14	24	26
After 2nd pass	13	17	10	14	18	24	26
After 3rd pass	13	10	14	17	18	24	26
After 4th pass	10	13	14	17	18	24	26
After 5th pass	10	13	14	17	18	24	26

Line 10	Input \(A , B\)
Line 20	Let \(C = 0\) and let \(D = 0\)
Line 30	Let \(C = C + A\)
Line 40	Let \(D = D + B\)
Line 50	If \(C = D\) then go to Line 110
Line 60	If \(C > D\) then go to Line 90
Line 70	Let \(C = C + A\)
Line 80	Go to Line 50
Line 90	Let \(D = D + B\)
Line 100	Go to Line 50
Line 110	Print \(C\)
Line 120	End

Questions — AQA D1 (167 questions)

Browse by module

Browse by board

AQA D1 2013 June Q6

AQA D1 2013 June Q7

AQA D1 Q3

AQA D1 Q4

AQA D1 Q5

AQA D1 Q7

AQA D1 2006 January Q1

AQA D1 2006 January Q2

AQA D1 2006 January Q3

AQA D1 2006 January Q4

AQA D1 2006 January Q5

AQA D1 2006 January Q6

AQA D1 2006 January Q7

AQA D1 2006 January Q8

AQA D1 2006 January Q9

AQA D1 2007 January Q1

AQA D1 2007 January Q2

AQA D1 2007 January Q3

AQA D1 2007 January Q4

AQA D1 2007 January Q5

AQA D1 2007 January Q6

AQA D1 2007 January Q7

AQA D1 2007 January Q8

AQA D1 2008 January Q1

AQA D1 2008 January Q2