Questions - AQA D1 - A-Level Maths

Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the 10 bus stops.
State the minimum length of cabling needed.
Draw your minimum spanning tree.
If Prim's algorithm, starting from $A$, had been used to find the minimum spanning tree, state which edge would have been the final edge to complete the minimum spanning tree.

AQA D1 2008 January Q4

4 [Figure 2, printed on the insert, is provided for use in this question.]
The network shows 11 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges.
\includegraphics[max width=\textwidth, alt={}, center]{92175666-ef7a-4dca-9cdb-ebde1b40b2c9-04_1762_1056_516_484} The total of all of the times is 308 minutes.

1. Use Dijkstra's algorithm on Figure 2 to find the minimum time to travel from $A$ to $K$.
2. State the corresponding route.
Find the length of an optimum Chinese postman route around the network, starting and finishing at $A$. (The minimum time to travel from $D$ to $H$ is 40 minutes.)

AQA D1 2008 January Q5

5 [Figure 3, printed on the insert, is provided for use in this question.]

James is solving a travelling salesperson problem.
1. He finds the following upper bounds: $43,40,43,41,55,43,43$. Write down the best upper bound.
2. James finds the following lower bounds: 33, 40, 33, 38, 33, 38, 38 . Write down the best lower bound.
Karen is solving a different travelling salesperson problem and finds an upper bound of 55 and a lower bound of 45 . Write down an interpretation of these results.
The diagram below shows roads connecting 4 towns, $A , B , C$ and $D$. The numbers on the edges represent the lengths of the roads, in kilometres, between adjacent towns.
\includegraphics[max width=\textwidth, alt={}, center]{92175666-ef7a-4dca-9cdb-ebde1b40b2c9-05_451_1034_1160_504} Xiong lives at town $A$ and is to visit each of the other three towns before returning to town $A$. She wishes to find a route that will minimise her travelling distance.
1. Complete Figure 3, on the insert, to show the shortest distances, in kilometres, between all pairs of towns.
2. Use the nearest neighbour algorithm on Figure 3 to find an upper bound for the minimum length of a tour of this network that starts and finishes at $A$.
3. Hence find the actual route that Xiong would take in order to achieve a tour of the same length as that found in part (c)(ii).

AQA D1 2008 January Q6

6 A student is solving cubic equations that have three different positive integer solutions.
The algorithm that the student is using is as follows:
Line 10 Input $A , B , C , D$
Line $20 \quad$ Let $K = 1$
Line $30 \quad$ Let $N = 0$
Line $40 \quad$ Let $X = K$
Line 50 Let $Y = A X ^ { 3 } + B X ^ { 2 } + C X + D$
Line 60 If $Y \neq 0$ then go to Line 100
Line $70 \quad$ Print $X$, "is a solution"
Line $80 \quad$ Let $N = N + 1$
Line 90 If $N = 3$ then go to Line 120
Line $100 \quad$ Let $K = K + 1$
Line 110 Go to Line 40
Line 120 End

Trace the algorithm in the case where the input values are:
1. $A = 1 , B = - 6 , C = 11$ and $D = - 6$;
2. $A = 1 , B = - 10 , C = 29$ and $D = - 20$.
Explain where and why this algorithm will fail if $A = 0$.

AQA D1 2008 January Q7

7 The numbers 17, 3, 16 and 4 are to be sorted into ascending order.
The following four methods are to be compared: bubble sort, shuttle sort, Shell sort and quick sort (with the first number used as the pivot). A student uses each of the four methods and produces the correct solutions below. Each solution shows the order of the numbers after each pass.

\multirow[t]{4}{*}{Solution 1}	17	3	16	4
	3	17	16	4
	3	16	17	4
	3	4	16	17
\multirow[t]{3}{*}{Solution 2}	17	3	16	4
	16	3	17	4
	3	4	16	17
\multirow[t]{4}{*}{Solution 3}	17	3	16	4
	3	16	4	17
	3	16	4	17
	3	4	16	17
\multirow[t]{4}{*}{Solution 4}	17	3	16	4
	3	16	4	17
	3	4	16	17
	3	4	16	17

Write down which of the four solutions is the bubble sort, the shuttle sort, the Shell sort and the quick sort.
For each of the four solutions, write down the number of comparisons and swaps (exchanges) on the first pass.

AQA D1 2008 January Q8

8 Each day, a factory makes three types of hinge: basic, standard and luxury. The hinges produced need three different components: type $A$, type $B$ and type $C$. Basic hinges need 2 components of type $A , 3$ components of type $B$ and 1 component of type $C$. Standard hinges need 4 components of type $A , 2$ components of type $B$ and 3 components of type $C$. Luxury hinges need 3 components of type $A$, 4 components of type $B$ and 5 components of type $C$. Each day, there are 360 components of type $A$ available, 270 of type $B$ and 450 of type $C$. Each day, the factory must use at least 720 components in total.
Each day, the factory must use at least $40 \%$ of the total components as type $A$.
Each day, the factory makes $x$ basic hinges, $y$ standard hinges and $z$ luxury hinges.
In addition to $x \geqslant 0 , y \geqslant 0 , z \geqslant 0$, find five inequalities, each involving $x , y$ and $z$, which must be satisfied. Simplify each inequality where possible.

AQA D1 2009 January Q1

1 The following network shows the lengths, in miles, of roads connecting 11 villages, $A , B , \ldots , K$.
\includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-2_915_1303_591_365}

Starting from $G$ and showing your working at each stage, use Prim's algorithm to find a minimum spanning tree for the network.
State the length of your minimum spanning tree.
Draw your minimum spanning tree.

AQA D1 2009 January Q2

2 Six people, $A , B , C , D , E$ and $F$, are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake.
\includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-3_401_517_429_751}
\includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-3_408_520_943_751}

Represent this information in an adjacency matrix.
Initially, $B$ is assigned to task $1 , C$ to task $2 , D$ to task 4, and $E$ to task 5 . Demonstrate, by using an algorithm from this initial matching, how each person can be allocated to a task.

AQA D1 2009 January Q3

3 [Figure 1, printed on the insert, is provided for use in this question.]
The diagram shows roads connecting some places of interest in Berlin. The numbers represent the times taken, in minutes, to walk along the roads.
\includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-4_1427_1404_502_319} The total of all walking times is 167 minutes.

Mia is staying at $D$ and is to visit $H$.
1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to walk from $D$ to $H$.
2. Write down the corresponding route.
Each day, Leon has to deliver leaflets along all of the roads. He must start and finish at $A$.
1. Use your answer to part (a) to write down the shortest walking time from $D$ to $A$.
2. Find the walking time of an optimum Chinese Postman route for Leon. (6 marks)

AQA D1 2009 January Q4

4 [Figure 2, printed on the insert, is provided for use in this question.]
Each year, farmer Giles buys some goats, pigs and sheep.
He must buy at least 110 animals.
He must buy at least as many pigs as goats.
The total of the number of pigs and the number of sheep that he buys must not be greater than 150 .
Each goat costs $\pounds 16$, each pig costs $\pounds 8$ and each sheep costs $\pounds 24$.
He has $\pounds 3120$ to spend on the animals.
At the end of the year, Giles sells all of the animals. He makes a profit of $\pounds 70$ on each goat, $\pounds 30$ on each pig and $\pounds 50$ on each sheep. Giles wishes to maximize his total profit, $\pounds P$. Each year, Giles buys $x$ goats, $y$ pigs and $z$ sheep.

Formulate Giles's situation as a linear programming problem.
One year, Giles buys 30 sheep.
1. Show that the constraints for Giles's situation for this year can be modelled by $$y \geqslant x , \quad 2 x + y \leqslant 300 , \quad x + y \geqslant 80 , \quad y \leqslant 120$$ (2 marks)
2. On Figure 2, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of the objective line.
  (8 marks)
3. Find Giles's maximum profit for this year and the number of each animal that he must buy to obtain this maximum profit.
  (3 marks)

AQA D1 2009 January Q5

5 A student is using the algorithm below to find an approximate value of $\sqrt { 2 }$.
Line 10 Let $A = 1 , B = 3 , C = 0$
Line $20 \quad$ Let $D = 1 , E = 2 , F = 0$
Line 30 Let $G = B / E$
Line $40 \quad$ Let $H = G ^ { 2 }$
Line 50 If $( H - 2 ) ^ { 2 } < 0.0001$ then go to Line 130
Line 60 Let $C = 2 B + A$
Line 70 Let $A = B$
Line 80 Let $B = C$
Line 90 Let $F = 2 E + D$
Line 100 Let $D = E$
Line 110 Let $E = F$
Line 120 Go to Line 30
Line 130 Print ' $\sqrt { 2 }$ is approximately', $B / E$
Line 140 Stop
Trace the algorithm.

AQA D1 2009 January Q6

6 A connected graph $G$ has five vertices and has eight edges with lengths $8,10,10,11,13,17$, 17 and 18.

Find the minimum length of a minimum spanning tree for $G$.
Find the maximum length of a minimum spanning tree for $G$.
Draw a sketch to show a possible graph $G$ when the length of the minimum spanning tree is 53 .

AQA D1 2009 January Q7

7 Liam is taking part in a treasure hunt. There are five clues to be solved and they are at the points $A , B , C , D$ and $E$. The table shows the distances between pairs of points. All of the distances are functions of $x$, where $\boldsymbol { x }$ is an integer. Liam must travel to all five points, starting and finishing at $A$.

	$\boldsymbol { A }$	$\boldsymbol { B }$	$\boldsymbol { C }$	$\boldsymbol { D }$	$\boldsymbol { E }$
A	-	$x + 6$	$2 x - 4$	$3 x - 7$	$4 x - 14$
$\boldsymbol { B }$	$x + 6$	-	$3 x - 7$	$3 x - 9$	$x + 9$
$\boldsymbol { C }$	$2 x - 4$	$3 x - 7$	-	$2 x - 1$	$x + 8$
$\boldsymbol { D }$	$3 x - 7$	$3 x - 9$	$2 x - 1$	-	$2 x - 2$
E	$4 x - 14$	$x + 9$	$x + 8$	$2 x - 2$	-

The nearest point to $A$ is $C$.
1. By considering $A C$ and $A B$, show that $x < 10$.
2. Find two other inequalities in $x$.
The nearest neighbour algorithm, starting from $A$, gives a unique minimum tour $A C D E B A$.
1. By considering the fact that Liam's tour visits $D$ immediately after $C$, find two further inequalities in $x$.
2. Find the value of the integer $x$.
3. Hence find the total distance travelled by Liam if he uses this tour.

AQA D1 2010 January Q1

1 Six girls, Alfonsa (A), Bianca (B), Claudia (C), Desiree (D), Erika (E) and Flavia (F), are going to a pizza restaurant. The restaurant provides a special menu of six different pizzas: Margherita (M), Neapolitana (N), Pepperoni (P), Romana (R), Stagioni (S) and Viennese (V). The table shows the pizzas that each girl likes.

Girl	Pizza
Alfonsa (A)	Margherita (M), Pepperoni (P), Stagioni (S)
Bianca (B)	Neapolitana (N), Romana (R)
Claudia (C)	Neapolitana (N), Viennese (V)
Desiree (D)	Romana (R), Stagioni (S)
Erika (E)	Pepperoni (P), Stagioni (S), Viennese (V)
Flavia (F)	Romana (R)

Show this information on a bipartite graph.
Each girl is to eat a different pizza. Initially, the waiter brings six different pizzas and gives Alfonsa the Pepperoni, Bianca the Romana, Claudia the Neapolitana and Erika the Stagioni. The other two pizzas are put in the middle of the table. From this initial matching, use the maximum matching algorithm to obtain a complete matching so that every girl gets a pizza that she likes. List your complete matching.

AQA D1 2010 January Q2

Use a bubble sort to rearrange the following numbers into ascending order. $$\begin{array} { l l l l l l l l } 13 & 16 & 10 & 11 & 4 & 12 & 6 & 7 \end{array}$$
State the number of comparisons and the number of swaps (exchanges) for each of the first three passes.

AQA D1 2010 January Q3

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

On Figure 1, draw a suitable diagram to represent the inequalities and indicate the feasible region.
Use your diagram to find the maximum value of $P$, stating the corresponding coordinates, on the feasible region, in the case where:
1. $P = x + 5 y$;
2. $\quad P = 5 x + y$.

AQA D1 2010 January Q4

4 In Paris, there is a park where there are statues of famous people; there are many visitors each day to this park. Lighting is to be installed at nine places, $A , B , \ldots , I$, in the park. The places have to be connected either directly or indirectly by cabling, to be laid alongside the paths, as shown in the diagram. The diagram shows the length of each path, in metres, connecting adjacent places.
\includegraphics[max width=\textwidth, alt={}, center]{f99fad35-3304-4e8f-be02-1439dfdc10e1-4_1109_1120_612_459}

1. Use Prim's algorithm, starting from $A$, to find the minimum length of cabling required.
2. State this minimum length.
3. Draw the minimum spanning tree.
A security guard walks along all the paths before returning to his starting place. Find the length of an optimal Chinese postman route for the guard.

AQA D1 2010 January Q5

5 There is a one-way system in Manchester. Mia is parked at her base, $B$, in Manchester and intends to visit four other places, $A , C , D$ and $E$, before returning to her base. The following table shows the distances, in kilometres, for Mia to drive between the five places $A , B , C , D$ and $E$. Mia wants to keep the total distance that she drives to a minimum.

\backslashbox{From}{To}	$\boldsymbol { A }$	$\boldsymbol { B }$	$\boldsymbol { C }$	$D$	E
A	-	1.7	1.9	1.8	2.1
B	3.1	-	2.5	1.8	3.7
$\boldsymbol { C }$	3.1	2.9	-	2.7	4.2
$\boldsymbol { D }$	2.0	2.8	2.1	-	2.3
E	2.2	3.6	1.9	1.7	-

Find the length of the tour $B E C D A B$.
Find the length of the tour obtained by using the nearest neighbour algorithm starting from $B$.
Write down which of your answers to parts (a) and (b) would be the better upper bound for the total distance that Mia drives.
On a particular day, the council decides to reverse the one-way system. For this day, find the length of the tour obtained by using the nearest neighbour algorithm starting from $B$.

AQA D1 2010 January Q6

6 A student is finding a numerical approximation for the area under a curve.
The algorithm that the student is using is as follows:
Line 10 Input $A , B , N$
Line 20 Let $T = 0$
Line 30 Let $D = A$
Line $40 \quad$ Let $H = ( B - A ) / N$
Line $50 \quad$ Let $E = H / 2$
Line 60 Let $T = T + A ^ { 3 } + B ^ { 3 }$
Line $70 \quad$ Let $D = D + H$
Line 80 If $D = B$ then go to line 110
Line 90 Let $T = T + 2 D ^ { 3 }$
Line 100 Go to line 70
Line $110 \quad$ Print 'Area $=$, $T \times E$
Line 120 End
Trace the algorithm in the case where the input values are:

$A = 1 , B = 5 , N = 2$;
$A = 1 , B = 5 , N = 4$.

AQA D1 2010 January Q7

7 [Figure 2, printed on the insert, is provided for use in this question.]
The following network has 13 vertices and 24 edges connecting some pairs of vertices. The number on each edge is its weight. The weights on the edges $G K$ and $L M$ are functions of $x$ and $y$, where $x > 0 , y > 0$ and $10 < x + y < 27$.
\includegraphics[max width=\textwidth, alt={}, center]{f99fad35-3304-4e8f-be02-1439dfdc10e1-7_1218_1431_660_312} There are three routes from $A$ to $M$ of the same minimum total weight.

Use Dijkstra's algorithm on Figure 2 to find this minimum total weight.
Find the values of $x$ and $y$.

AQA D1 2010 January Q8

8 A factory packs three different kinds of novelty box: red, blue and green. Each box contains three different types of toy: $\mathrm { A } , \mathrm { B }$ and C . Each red box has 2 type A toys, 3 type B toys and 4 type C toys.
Each blue box has 3 type A toys, 1 type B toy and 3 type C toys.
Each green box has 4 type A toys, 5 type B toys and 2 type C toys.
Each day, the maximum number of each type of toy available to be packed is 360 type A, 300 type B and 400 type C. Each day, the factory must pack more type A toys than type B toys.
Each day, the total number of type A and type B toys that are packed must together be at least as many as the number of type C toys that are packed. Each day, at least $40 \%$ of the total toys that are packed must be type C toys.
Each day, the factory packs $x$ red boxes, $y$ blue boxes and $z$ green boxes.
Formulate the above situation as 6 inequalities, in addition to $x \geqslant 0 , y \geqslant 0$ and $z \geqslant 0$, simplifying your answers.

AQA D1 2005 June Q1

1 Use a shuttle sort algorithm to rearrange the following numbers into ascending order, showing the new arrangement after each pass. $$\begin{array} { l l l l l l l l } 23 & 3 & 17 & 4 & 6 & 19 & 14 & 3 \end{array}$$ (5 marks)

AQA D1 2005 June Q2

2 A father is going to give each of his five daughters: Grainne ( $G$ ), Kath ( $K$ ), Mary ( $M$ ), Nicola ( $N$ ) and Stella ( $S$ ), one of the five new cars that he has bought: an Audi ( $A$ ), a Ford Focus ( $F$ ), a Jaguar ( $J$ ), a Peugeot ( $P$ ) and a Range Rover ( $R$ ). The daughters express preferences for the car that they would like to be given, as shown in the table.

	Preferences
Grainne ( $G$ )	Audi $( A )$ or Peugeot ( $P$ )
Kath ( $K$ )	Peugeot ( $P$ ) or Ford Focus ( $F$ )
Mary ( $M$ )	Jaguar ( $J$ ) or Range Rover ( $R$ )
Nicola ( $N$ )	Audi $( A )$ or Ford Focus ( $F$ )
Stella ( $S$ )	Jaguar ( $J$ ) or Audi ( $A$ )

Show all these preferences on a bipartite graph.
Initially the father allocates the Peugeot to Kath, the Jaguar to Mary, and the Audi to Nicola. Demonstrate, by using alternating paths from this initial matching, how each daughter can be matched to a car which is one of her preferences.
(6 marks)

AQA D1 2005 June Q3

3 A theme park has 11 rides, $A , B , \ldots K$. The network shows the distances, in metres, between pairs of rides. The rides are to be connected by cabling so that information can be collated. The manager of the theme park wishes to use the minimum amount of cabling.
\includegraphics[max width=\textwidth, alt={}, center]{a1290c22-f28d-42aa-89d5-10d60ca4741c-03_988_1575_488_248}

Use Prim's algorithm, starting from $A$, to find the minimum spanning tree for the network.
State the length of cabling required.
Draw your minimum spanning tree.
The manager decides that the edge $A E$ must be included. Find the extra length of cabling now required to give the smallest spanning tree that includes $A E$.

AQA D1 2005 June Q4

In the complete graph $\mathrm { K } _ { 7 }$, every one of the 7 vertices is connected to each of the other 6 vertices by a single edge. Find or write down:
1. the number of edges in the graph;
2. the number of edges in a minimum spanning tree;
3. the number of edges in a Hamiltonian cycle.
1. Explain why the graph $\mathrm { K } _ { 7 }$ is Eulerian.
2. Write down the condition for $\mathrm { K } _ { n }$ to be Eulerian.
A connected graph has 6 vertices and 10 edges. Draw an example of such a graph which is Eulerian.

	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	\(\boldsymbol { C }\)	\(\boldsymbol { D }\)	\(\boldsymbol { E }\)
A	-	\(x + 6\)	\(2 x - 4\)	\(3 x - 7\)	\(4 x - 14\)
\(\boldsymbol { B }\)	\(x + 6\)	-	\(3 x - 7\)	\(3 x - 9\)	\(x + 9\)
\(\boldsymbol { C }\)	\(2 x - 4\)	\(3 x - 7\)	-	\(2 x - 1\)	\(x + 8\)
\(\boldsymbol { D }\)	\(3 x - 7\)	\(3 x - 9\)	\(2 x - 1\)	-	\(2 x - 2\)
E	\(4 x - 14\)	\(x + 9\)	\(x + 8\)	\(2 x - 2\)	-

	Preferences
Grainne ( \(G\) )	Audi \(( A )\) or Peugeot ( \(P\) )
Kath ( \(K\) )	Peugeot ( \(P\) ) or Ford Focus ( \(F\) )
Mary ( \(M\) )	Jaguar ( \(J\) ) or Range Rover ( \(R\) )
Nicola ( \(N\) )	Audi \(( A )\) or Ford Focus ( \(F\) )
Stella ( \(S\) )	Jaguar ( \(J\) ) or Audi ( \(A\) )

Questions — AQA D1 (167 questions)

Browse by module

Browse by board

AQA D1 2008 January Q3

AQA D1 2008 January Q4

AQA D1 2008 January Q5

AQA D1 2008 January Q6

AQA D1 2008 January Q7

AQA D1 2008 January Q8

AQA D1 2009 January Q1

AQA D1 2009 January Q2

AQA D1 2009 January Q3

AQA D1 2009 January Q4

AQA D1 2009 January Q5

AQA D1 2009 January Q6

AQA D1 2009 January Q7

AQA D1 2010 January Q1

AQA D1 2010 January Q2

AQA D1 2010 January Q3

AQA D1 2010 January Q4

AQA D1 2010 January Q5

AQA D1 2010 January Q6

AQA D1 2010 January Q7

AQA D1 2010 January Q8

AQA D1 2005 June Q1

AQA D1 2005 June Q2

AQA D1 2005 June Q3

AQA D1 2005 June Q4