Questions - AQA D1 - A-Level Maths

1. Use Prim's algorithm starting from $A$, showing the order in which you select the edges, to find a minimum spanning tree for the network.
2. Draw your minimum spanning tree.
3. Calculate the minimum cost to the council of making it possible for each town to be safely reached on treated roads from any other town.
On one occasion, the road from $C$ to $E$ is impassable because of flooding. Find the minimum cost of treating sufficient roads for safe travel in this case.
[0pt] [2 marks]

AQA D1 2015 June Q3

3 Four students, $A , B , C$ and $D$, are using different algorithms to sort 16 numbers into ascending order.

Student $A$ uses the quicksort algorithm. State the number of comparisons on the first pass.
Student $B$ uses the Shell sort algorithm. State the number of comparisons on the first pass.
Student $C$ uses the shuttle sort algorithm. State the minimum number of comparisons on the final pass.
Student $D$ uses the bubble sort algorithm. Find the maximum total number of comparisons.

AQA D1 2015 June Q4

2 marks

4 The network opposite shows roads connecting 10 villages, $A , B , \ldots , J$. The time taken to drive along a road is not proportional to the length of the road. The number on each edge shows the average time, in minutes, to drive along each road.

A commuter wishes to drive from village $A$ to the railway station at $J$.
1. Use Dijkstra's algorithm, on the diagram opposite, to find the shortest driving time from $A$ to $J$.
2. State the corresponding route.
A taxi driver is in village $D$ at 10.30 am when she receives a radio call asking her to pick up a passenger at village $A$ and take him to the station at $J$. Assuming that it takes her 3 minutes to load the passenger and his luggage, at what time should she expect to arrive at the station?
[0pt] [2 marks]
\includegraphics[max width=\textwidth, alt={}]{f5890e58-38c3-413c-8762-6f80ce6dcec7-09_2484_1717_223_150}

AQA D1 2015 June Q5

5 The network shows the paths mown through a wildflower meadow so that visitors can use these paths to enjoy the flowers. The lengths of the paths are shown in metres.
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-10_1097_1603_413_214} The total length of all the paths is 1400 m .
The mower is kept in a shed at $A$. The groundskeeper must mow all the paths and return the mower to its shed.

Find the length of an optimal Chinese postman route starting and finishing at $A$.
State the number of times that the mower, following the optimal route, will pass through:
1. $C$;
2. $D$.

AQA D1 2015 June Q6

1 marks

6 The network shows the roads linking a warehouse at $A$ and five shops, $B , C , D , E$ and $F$. The numbers on the edges show the lengths, in miles, of the roads. A delivery van leaves the warehouse, delivers to each of the shops and returns to the warehouse.
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-12_1241_1239_484_402}

Complete the table, on the page opposite, showing the shortest distances between the vertices.
1. Find the total distance travelled if the van follows the cycle $A E F B C D A$.
2. Explain why your answer to part (b)(i) provides an upper bound for the minimum journey length.
Use the nearest neighbour algorithm starting from $D$ to find a second upper bound.
By deleting $A$, find a lower bound for the minimum journey length.
Given that the minimum journey length is $T$, write down the best inequality for $T$ that can be obtained from your answers to parts (b), (c) and (d).
[0pt] [1 mark] \section*{Answer space for question 6} REFERENCE

	$\boldsymbol { A }$	$\boldsymbol { B }$	$\boldsymbol { C }$	$\boldsymbol { D }$	$\boldsymbol { E }$	$\boldsymbol { F }$
$\boldsymbol { A }$	-	7
$\boldsymbol { B }$	7	-	5
$\boldsymbol { C }$		5	-	4
$\boldsymbol { D }$			4	-	6
$\boldsymbol { E }$				6	-	10
$\boldsymbol { F }$					10	-

AQA D1 2015 June Q7

2 marks

A simple connected graph has 4 edges and $m$ vertices. State the possible values of $m$.
A simple connected graph has $n$ edges and 4 vertices. State the possible values of $n$.
A simple connected graph, $G$, has 5 vertices and is Eulerian but not Hamiltonian. Draw a possible graph $G$.
[0pt] [2 marks]

AQA D1 2015 June Q8

8 A student is tracing the following algorithm.
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-18_1431_955_372_539}

Trace the algorithm illustrated in the flowchart for the case where the input value of $N$ is 5 .
Explain the role of $N$ in the algorithm.

AQA D1 2015 June Q9

10 marks

9 A company producing chicken food makes three products, Basic, Premium and Supreme, from wheat, maize and barley. A tonne $( 1000 \mathrm {~kg} )$ of Basic uses 400 kg of wheat, 200 kg of maize and 400 kg of barley.
A tonne of Premium uses 400 kg of wheat, 500 kg of maize and 100 kg of barley.
A tonne of Supreme uses 600 kg of wheat, 200 kg of maize and 200 kg of barley.
The company has 130 tonnes of wheat, 70 tonnes of maize and 72 tonnes of barley available. The company must make at least 75 tonnes of Supreme.
The company makes $\pounds 50$ profit per tonne of Basic, $\pounds 100$ per tonne of Premium and $\pounds 150$ per tonne of Supreme. They plan to make $x$ tonnes of Basic, $y$ tonnes of Premium and $z$ tonnes of Supreme.

Write down four inequalities representing the constraints (in addition to $x , y \geqslant 0$ ).
[0pt] [4 marks]
The company want exactly half the production to be Supreme. Show that the constraints in part (a) become $$\begin{aligned} x + y & \leqslant 130
4 x + 7 y & \leqslant 700
2 x + y & \leqslant 240
x + y & \geqslant 75
x & \geqslant 0
y & \geqslant 0 \end{aligned}$$
On the grid opposite, illustrate all the constraints and label the feasible region.
Write an expression for $P$, the profit for the whole production, in terms of $x$ and $y$ only.
[0pt] [2 marks]
1. By drawing an objective line on your graph, or otherwise, find the values of $x$ and $y$ which give the maximum profit.
  [0pt] [2 marks]
2. State the maximum profit and the amount of each product that must be made.
  [0pt] [2 marks] \section*{Answer space for question 9}
  \includegraphics[max width=\textwidth, alt={}]{f5890e58-38c3-413c-8762-6f80ce6dcec7-21_1349_1728_310_148}
  QUESTION
  PART
  REFERENCE
  \includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-24_2488_1728_219_141}

AQA D1 2016 June Q1

3 marks

1 Alfred has bought six different chocolate bars. He wants to give a chocolate bar to each of his six friends. The table gives the names of the friends and indicates which of Alfred's six chocolate bars they like.

AQA D1 2016 June Q2

4 marks

Use a shuttle sort to rearrange into alphabetical order the following list of names:
Rob, Eve, Meg, lan, Xavi
Show the list at the end of each pass.
A list of ten numbers is sorted into ascending order, using a shuttle sort.
1. How many passes are needed?
2. Give the maximum number of comparisons needed in the sixth pass.
3. Given that the list is initially in descending order, find the total number of swaps needed.
  [0pt] [4 marks]

AQA D1 2016 June Q3

3 The network below shows vertices $A , B , C , D$ and $E$. The number on each edge shows the distance between vertices.
\includegraphics[max width=\textwidth, alt={}, center]{fb95068f-f76d-492a-b385-bce17b26ae30-06_563_736_402_651}

1. In the case where $x = 8$, use Kruskal's algorithm to find a minimum spanning tree for the network. Write down the order in which you add edges to your minimum spanning tree.
2. Draw your minimum spanning tree.
3. Write down the length of your minimum spanning tree.
Alice draws the same network but changes the value of $x$. She correctly uses Kruskal's algorithm and edge $C D$ is included in her minimum spanning tree.
1. Explain why $x$ cannot be equal to 7 .
2. Write down an inequality for $x$.

AQA D1 2016 June Q4

4 Amal delivers free advertiser magazines to all the houses in his village. The network shows the roads in his village. The number on each road shows the time, in minutes, that Amal takes to walk along that road.
\includegraphics[max width=\textwidth, alt={}, center]{fb95068f-f76d-492a-b385-bce17b26ae30-08_846_1264_445_388}

Amal starts his delivery round from his house, at vertex $A$. He must walk along each road at least once.
1. Find the length of an optimal Chinese postman route around the village, starting and finishing at Amal's house.
2. State the number of times that Amal passes his friend Dipak's house, at vertex $D$.
Dipak offers to deliver the magazines while Amal is away on holiday. Dipak must walk along each road at least once. Assume that Dipak takes the same length of time as Amal to walk along each road.
1. Dipak can start his journey at any vertex and finish his journey at any vertex. Find the length of time for an optimal route for Dipak.
2. State the vertices at which Dipak could finish, in order to achieve his optimal route.
1. Find the length of time for an optimal route for Dipak, if, instead, he wants to finish at his house, at vertex $D$, and can start his journey at any other vertex.
2. State the start vertex.

AQA D1 2016 June Q5

5 A fair comes to town one year and sets up its rides in two large fields that are separated by a river. The diagram shows the ten main rides, at $A , B , C , \ldots , J$. The numbers on the edges represent the times, in minutes, it takes to walk between pairs of rides. A footbridge connects the rides at $D$ and $F$.

1. Use Dijkstra's algorithm on the diagram below to find the minimum time to walk from $A$ to each of the other main rides.
2. Write down the route corresponding to the minimum time to walk from $A$ to $G$.
The following year, the fair returns. In addition to the information shown on the diagram, another footbridge has been built to connect the rides at $E$ and $G$. This reduces the time taken to travel from $A$ to $G$, but the time taken to travel from $A$ to $J$ is not reduced. The time to walk across the footbridge from $E$ to $G$ is $x$ minutes, where $x$ is an integer. Find two inequalities for $x$ and hence state the value of $x$. \section*{Answer space for question 5}
1. \includegraphics[max width=\textwidth, alt={}, center]{fb95068f-f76d-492a-b385-bce17b26ae30-12_659_1591_1692_223}

AQA D1 2016 June Q6

6 A connected graph is semi-Eulerian if exactly two of its vertices are of odd degree.

A graph is drawn with 4 vertices and 7 edges. What is the sum of the degrees of the vertices?
Draw a simple semi-Eulerian graph with exactly 5 vertices and 5 edges, in which exactly one of the vertices has degree 4 .
Draw a simple semi-Eulerian graph with exactly 5 vertices that is also a tree.
A simple graph has 6 vertices. The graph has two vertices of degree 5 . Explain why the graph can have no vertex of degree 1.

AQA D1 2016 June Q7

7 A company operates a steam railway between six stations. The minimum cost (in euros) of travelling between pairs of stations is shown in the table below.

On Figure 1 below, use Prim's algorithm, starting from $P$, to find a minimum spanning tree for the graph connecting $P , Q , R , S , T$ and $U$. State clearly the order in which you select the vertices and draw your minimum spanning tree. \section*{Question 7 continues on page 20} \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Figure 1}

	$\boldsymbol { P }$	$\boldsymbol { Q }$	$\boldsymbol { R }$	$\boldsymbol { S }$	$\boldsymbol { T }$	$\boldsymbol { U }$
$\boldsymbol { P }$	-	14	7	11	6	12
$\boldsymbol { Q }$	14	-	8	10	9	10
$\boldsymbol { R }$	7	8	-	12	13	15
$\boldsymbol { S }$	11	10	12	-	5	11
$\boldsymbol { T }$	6	9	13	5	-	10
$\boldsymbol { U }$	12	10	15	11	10	-

\end{table}

Another station, $V$, is opened. The minimum costs (in euros) of travelling to and from $V$ to each of the other stations are added to the table in part (a), as shown in Figure 2(i) below. Further copies of this table are shown in Figure 2(ii). Arjen is on holiday and he plans to visit each station. He intends to board a train at $V$ and visit all the other stations, once only, before returning to $V$.

By first removing $V$, obtain a lower bound for the minimum travelling cost of Arjen's tour. (You may use Figure 2(i) for your working.)
Use the nearest neighbour algorithm twice, starting each time from $V$, to find two different upper bounds for the minimum cost of Arjen's tour. State, with a reason, which of your two answers gives the better upper bound. (You may use Figure 2(ii) for your working.)

Hence find an optimal tour of the seven stations. Explain how you know that it is optimal. Answer space for question 7(b) \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Figure 2(ii)}

	$\boldsymbol { P }$	$Q$	$\boldsymbol { R }$	$\boldsymbol { S }$	$T$	$\boldsymbol { U }$	$V$
$\boldsymbol { P }$	-	14	7	11	6	12	15
$Q$	14	-	8	10	9	10	18
$\boldsymbol { R }$	7	8	-	12	13	15	14
$\boldsymbol { S }$	11	10	12	-	5	11	14
$T$	6	9	13	5	-	10	17
$\boldsymbol { U }$	12	10	15	11	10	-	12
$V$	15	18	14	14	17	12	-

\end{table}

AQA D1 2016 June Q8

8 Nerys runs a cake shop. In November and December she sells Christmas hampers. She makes up the hampers herself, in two sizes: Luxury and Special. Each day, Nerys prepares $x$ Luxury hampers and $y$ Special hampers.
It takes Nerys 10 minutes to prepare a Luxury hamper and 15 minutes to prepare a Special hamper. She has 6 hours available, each day, for preparing hampers. From past experience, Nerys knows that each day:

she will need to prepare at least 5 hampers of each size
she will prepare at most a total of 32 hampers
she will prepare at least twice as many Luxury hampers as Special hampers.

Each Luxury hamper that Nerys prepares makes her a profit of $\pounds 15$; each Special hamper makes a profit of $\pounds 20$. Nerys wishes to maximise her daily profit, $\pounds P$.

Show that $x$ and $y$ must satisfy the inequality $2 x + 3 y \leqslant 72$.
In addition to $x \geqslant 5$ and $y \geqslant 5$, write down two more inequalities that model the constraints above.
On the grid opposite draw a suitable diagram to enable this problem to be solved graphically. Indicate a feasible region and the direction of an objective line.
1. Use your diagram to find the number of each type of hamper that Nerys should prepare each day to achieve a maximum profit.
2. Calculate this profit.
  \includegraphics[max width=\textwidth, alt={}]{fb95068f-f76d-492a-b385-bce17b26ae30-27_2490_1719_217_150}
  \section*{DO NOT WRITE ON THIS PAGE ANSWER IN THE SPACES PROVIDED}

	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	\(\boldsymbol { C }\)	\(\boldsymbol { D }\)	\(\boldsymbol { E }\)	\(\boldsymbol { F }\)
\(\boldsymbol { A }\)	-	7
\(\boldsymbol { B }\)	7	-	5
\(\boldsymbol { C }\)		5	-	4
\(\boldsymbol { D }\)			4	-	6
\(\boldsymbol { E }\)				6	-	10
\(\boldsymbol { F }\)					10	-

	\(\boldsymbol { P }\)	\(\boldsymbol { Q }\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(\boldsymbol { T }\)	\(\boldsymbol { U }\)
\(\boldsymbol { P }\)	-	14	7	11	6	12
\(\boldsymbol { Q }\)	14	-	8	10	9	10
\(\boldsymbol { R }\)	7	8	-	12	13	15
\(\boldsymbol { S }\)	11	10	12	-	5	11
\(\boldsymbol { T }\)	6	9	13	5	-	10
\(\boldsymbol { U }\)	12	10	15	11	10	-

	\(\boldsymbol { P }\)	\(Q\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(T\)	\(\boldsymbol { U }\)	\(V\)
\(\boldsymbol { P }\)	-	14	7	11	6	12	15
\(Q\)	14	-	8	10	9	10	18
\(\boldsymbol { R }\)	7	8	-	12	13	15	14
\(\boldsymbol { S }\)	11	10	12	-	5	11	14
\(T\)	6	9	13	5	-	10	17
\(\boldsymbol { U }\)	12	10	15	11	10	-	12
\(V\)	15	18	14	14	17	12	-

Questions — AQA D1 (167 questions)

Browse by module

Browse by board

AQA D1 2015 June Q1

AQA D1 2015 June Q2

AQA D1 2015 June Q3

AQA D1 2015 June Q4

AQA D1 2015 June Q5

AQA D1 2015 June Q6

AQA D1 2015 June Q7

AQA D1 2015 June Q8

AQA D1 2015 June Q9

AQA D1 2016 June Q1

AQA D1 2016 June Q2

AQA D1 2016 June Q3

AQA D1 2016 June Q4

AQA D1 2016 June Q5

AQA D1 2016 June Q6

AQA D1 2016 June Q7

AQA D1 2016 June Q8