Questions — AQA D1 (170 questions)

Browse by board
AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 PURE S1 S2 S3 S4 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 Pre-U Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4
AQA D1 2008 June Q1
7 marks Moderate -0.8
1 Six people, \(A , B , C , D , E\) and \(F\), are to be matched to six tasks, \(1,2,3,4,5\) and 6 .
The following adjacency matrix shows the possible matching of people to tasks.
Task 1Task 2Task 3Task 4Task 5Task 6
\(\boldsymbol { A }\)001011
B010100
\(\boldsymbol { C }\)010001
\(\boldsymbol { D }\)000100
\(E\)101010
\(\boldsymbol { F }\)000110
  1. Show this information on a bipartite graph.
  2. Initially, \(A\) is matched to task 3, \(B\) to task 4, \(C\) to task 2 and \(E\) to task 5. From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.
AQA D1 2008 June Q2
7 marks Easy -1.2
2
  1. Use a quick sort to rearrange the following letters into alphabetical order. You must indicate the pivot that you use at each pass.
    P
    B
    M
    N
    J
    K
    R
    D
    (5 marks)
    1. Find the maximum number of swaps needed to rearrange a list of 8 numbers into ascending order when using a bubble sort.
      (1 mark)
    2. A list of 8 numbers was rearranged into ascending order using a bubble sort. The maximum number of swaps was needed. What can be deduced about the original list of numbers?
      (1 mark)
AQA D1 2008 June Q3
10 marks Easy -1.8
3
    1. State the number of edges in a minimum spanning tree of a network with 11 vertices.
    2. State the number of edges in a minimum spanning tree of a network with \(n\) vertices.
  1. The following network has 11 vertices, \(A , B , \ldots , K\). The number on each edge represents the distance, in miles, between a pair of vertices. \includegraphics[max width=\textwidth, alt={}, center]{4c5c963b-0183-4dc7-9054-b2c7a3eb8c1b-03_1468_1239_721_404}
    1. Use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the network.
    2. Find the length of your minimum spanning tree.
    3. Draw your minimum spanning tree.
AQA D1 2008 June Q4
16 marks Moderate -0.8
4 David, a tourist, wishes to visit five places in Rome: Basilica ( \(B\) ), Coliseum ( \(C\) ), Pantheon ( \(P\) ), Trevi Fountain ( \(T\) ) and Vatican ( \(V\) ). He is to start his tour at one of the places, visit each of the other places, before returning to his starting place. The table shows the times, in minutes, to travel between these places. David wishes to keep his travelling time to a minimum.
\(\boldsymbol { B }\)\(\boldsymbol { C }\)\(\boldsymbol { P }\)\(T\)\(V\)
\(\boldsymbol { B }\)-43575218
\(\boldsymbol { C }\)43-181356
\(P\)5718-848
\(T\)52138-51
\(V\)18564851-
    1. Find the total travelling time for the tour TPVBCT.
    2. Find the total travelling time for David's tour using the nearest neighbour algorithm starting from \(T\).
    3. Explain why your answer to part (a)(ii) is an upper bound for David's minimum total travelling time.
    1. By deleting \(B\), find a lower bound for the total travelling time for the minimum tour.
    2. Explain why your answer to part (b)(i) is a lower bound for David's minimum total travelling time.
  1. Sketch a network showing the edges that give the lower bound found in part (b)(i) and comment on its significance.
AQA D1 2008 June Q5
11 marks Standard +0.8
5 The diagram shows a network of sixteen roads on a housing estate. The number on each edge is the length, in metres, of the road. The total length of the sixteen roads is 1920 metres. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4c5c963b-0183-4dc7-9054-b2c7a3eb8c1b-05_1371_1267_466_422} \captionsetup{labelformat=empty} \caption{Total Length = 1920 metres}
\end{figure}
  1. Chris, an ice-cream salesman, travels along each road at least once, starting and finishing at the point \(A\). Find the length of an optimal 'Chinese postman' route for Chris.
  2. Pascal, a paperboy, starts at \(A\) and walks along each road at least once before finishing at \(D\). Find the length of an optimal route for Pascal.
  3. Millie is to walk along all the roads at least once delivering leaflets. She can start her journey at any point and she can finish her journey at any point.
    1. Find the length of an optimal route for Millie.
    2. State the points from which Millie could start in order to achieve this optimal route.
AQA D1 2008 June Q6
15 marks Moderate -0.8
6 [Figure 1, printed on the insert, is provided for use in this question.]
A factory makes two types of lock, standard and large, on a particular day.
On that day:
the maximum number of standard locks that the factory can make is 100 ;
the maximum number of large locks that the factory can make is 80 ;
the factory must make at least 60 locks in total;
the factory must make more large locks than standard locks.
Each standard lock requires 2 screws and each large lock requires 8 screws, and on that day the factory must use at least 320 screws. On that day, the factory makes \(x\) standard locks and \(y\) large locks.
Each standard lock costs \(\pounds 1.50\) to make and each large lock costs \(\pounds 3\) to make.
The manager of the factory wishes to minimise the cost of making the locks.
  1. Formulate the manager's situation as a linear programming problem.
  2. On Figure 1, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of the objective line.
  3. Find the values of \(x\) and \(y\) that correspond to the minimum cost. Hence find this minimum cost.
AQA D1 2008 June Q7
9 marks Standard +0.8
7 [Figure 2, printed on the insert, is provided for use in this question.]
The following network has eight vertices, \(A , B , \ldots , H\), and edges connecting some pairs of vertices. The number on each edge is its weight. The weights on the edges \(E H\) and \(G H\) are functions of \(x\) and \(y\). \includegraphics[max width=\textwidth, alt={}, center]{4c5c963b-0183-4dc7-9054-b2c7a3eb8c1b-07_1170_1705_596_164} Given that there are three routes from \(A\) to \(H\) with the same minimum weight, use Dijkstra's algorithm on Figure 2 to find:
  1. this minimum weight;
  2. the values of \(x\) and \(y\).
AQA D1 2009 June Q1
7 marks Moderate -0.5
1
  1. Draw a bipartite graph representing the following adjacency matrix.
    123456
    \(\boldsymbol { A }\)101010
    B010100
    \(\boldsymbol { C }\)010001
    \(\boldsymbol { D }\)000100
    E001011
    \(\boldsymbol { F }\)000110
  2. Initially, \(A\) is matched to \(3 , B\) is matched to \(4 , C\) is matched to 2 , and \(E\) is matched to 5 . Use the maximum matching algorithm, from this initial matching, to find a complete matching. List your complete matching.
AQA D1 2009 June Q2
6 marks Moderate -0.5
2
2
} & \multirow{3}{*}{\includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-04_699_1486_269_366} \includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-04_508_1272_462_366} }
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline
AQA D1 2009 June Q3
10 marks Easy -1.8
3
    1. State the number of edges in a minimum spanning tree for a network with 10 vertices.
    2. State the number of edges in a minimum spanning tree for a network with \(n\) vertices.
  1. The following network has 10 vertices: \(A , B , \ldots , J\). The number on each edge represents the distance between a pair of adjacent vertices. \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-06_921_1710_717_150}
    1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
    2. State the length of your minimum spanning tree.
    3. Draw your minimum spanning tree. \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-07_38_118_440_159} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-07_40_118_529_159}
AQA D1 2009 June Q4
13 marks Moderate -0.5
4 The diagram opposite shows a network of roads on a housing estate. The number on each edge is the length, in metres, of the road. Joe is starting a kitchen-fitting business.
  1. Joe delivers leaflets advertising his business. He walks along all of the roads at least once, starting and finishing at \(C\). Find the length of an optimal Chinese postman route for Joe.
  2. Joe gets a job fitting a kitchen in a house at \(T\). Joe starts from \(C\) and wishes to drive to \(T\). Use Dijkstra's algorithm on the diagram opposite to find the minimum distance to drive from \(C\) to \(T\). State the corresponding route. \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-08_1791_1705_916_155}
    (b) \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-09_2395_1602_312_260}
AQA D1 2009 June Q5
10 marks Moderate -0.3
5 Angelo is visiting six famous places in Palermo: \(A , B , C , D , E\) and \(F\). He intends to travel from one place to the next until he has visited all of the places before returning to his starting place. Due to the traffic system, the time taken to travel between two places may be different dependent on the direction travelled. The table shows the times, in minutes, taken to travel between the six places.
\backslashbox{From}{To}A\(\boldsymbol { B }\)\(\boldsymbol { C }\)\(\boldsymbol { D }\)E\(F\)
A-2520202725
\(\boldsymbol { B }\)15-10111530
\(\boldsymbol { C }\)530-152019
\(\boldsymbol { D }\)202515-2510
\(\boldsymbol { E }\)1020715-15
F2535292030-
  1. Give an example of a Hamiltonian cycle in this context.
    1. Show that, if the nearest neighbour algorithm starting from \(F\) is used, the total travelling time for Angelo would be 95 minutes.
    2. Explain why your answer to part (b)(i) is an upper bound for the minimum travelling time for Angelo.
  2. Angelo starts from \(F\) and visits \(E\) next. He also visits \(B\) before he visits \(D\). Find an improved upper bound for Angelo's total travelling time.
    \includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-11_2484_1709_223_153}
AQA D1 2009 June Q6
21 marks Moderate -0.3
6 Each day, a factory makes three types of widget: basic, standard and luxury. The widgets produced need three different components: type \(A\), type \(B\) and type \(C\). Basic widgets need 6 components of type \(A , 6\) components of type \(B\) and 12 components of type \(C\).
Standard widgets need 4 components of type \(A , 3\) components of type \(B\) and 18 components of type \(C\).
Luxury widgets need 2 components of type \(A , 9\) components of type \(B\) and 6 components of type \(C\).
Each day, there are 240 components of type \(A\) available, 300 of type \(B\) and 900 of type \(C\).
Each day, the factory must use at least twice as many components of type \(C\) as type \(B\).
Each day, the factory makes \(x\) basic widgets, \(y\) standard widgets and \(z\) luxury widgets.
  1. In addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), find four inequalities in \(x , y\) and \(z\) that model the above constraints, simplifying each inequality.
  2. Each day, the factory makes the maximum possible number of widgets. On a particular day, the factory must make the same number of luxury widgets as basic widgets.
    1. Show that your answers in part (a) become $$2 x + y \leqslant 60 , \quad 5 x + y \leqslant 100 , \quad x + y \leqslant 50 , \quad y \geqslant x$$
    2. Using the axes opposite, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region.
    3. Find the total number of widgets made on that day.
    4. Find all possible combinations of the number of each type of widget made that correspond to this maximum number.
AQA D1 2009 June Q7
8 marks Moderate -0.3
7
  1. The diagram shows a graph with 16 vertices and 16 edges. \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_204_365_758} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_365_1080} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_204_689_758} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_200_689_1082}
    1. On Figure 1 below, add the minimum number of edges to make a connected graph.
    2. On Figure 2 opposite, add the minimum number of edges to make the graph Hamiltonian.
    3. On Figure 3 opposite, add the minimum number of edges to make the graph Eulerian.
  2. A complete graph has \(n\) vertices and is Eulerian.
    1. State the condition that \(n\) must satisfy.
    2. 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\). \section*{Figure 1} \section*{Connected Graph} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(a)(i)} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_195_200_2014_758}
      \end{figure} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(a)(i)} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_197_200_2012_1082}
      \end{figure}
      \includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_2334_758}
      \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(a)(i)} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_2334_1080}
      \end{figure} \section*{Figure 2} \section*{Hamiltonian Graph} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_218_536_511_753} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_213_212_836_753} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_215_214_836_1073}
      1. (iii) \section*{Eulerian Graph} \begin{figure}[h]
        \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_207_204_1356_758}
        \end{figure} \begin{figure}[h]
        \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_211_206_1354_1078}
        \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_206_209_1681_753} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_200_202_1681_1080}
AQA D1 2011 June Q1
7 marks Moderate -0.5
1 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 adjacency matrix shows the tasks that each of the people is able to undertake.
123456
\(\boldsymbol { A }\)101000
\(\boldsymbol { B }\)110001
C010100
\(\boldsymbol { D }\)010010
E001010
F000010
  1. Represent this information in a bipartite graph.
  2. Initially, \(A\) is assigned to task 3, \(B\) to task 2, \(C\) to task 4 and \(D\) to task 5 . Use an algorithm from this initial matching to find a maximum matching, listing your alternating paths.
AQA D1 2011 June Q2
6 marks Easy -1.2
2 Five different integers are to be sorted into ascending order.
  1. A bubble sort is to be used on the list of numbers \(\quad 6 \quad 4 \quad 5 \quad x \quad 2 \quad 11\).
    1. After the first pass, the list of numbers becomes $$\begin{array} { l l l l l } 4 & x & 2 & 6 & 11 \end{array}$$ Write down an inequality that \(x\) must satisfy.
    2. After the second pass, the list becomes $$\begin{array} { l l l l l } x & 2 & 4 & 6 & 11 \end{array}$$ Write down a new inequality that \(x\) must satisfy.
  2. The five integers are now written in a different order. A shuttle sort is to be used on the list of numbers \(\quad \begin{array} { l l l l l } 11 & x & 2 & 4 & 6 . \end{array}\)
    1. After the first pass, the list of numbers becomes $$\begin{array} { l l l l l } x & 11 & 2 & 4 & 6 \end{array}$$ Write down an inequality that \(x\) must satisfy.
    2. After the second pass, the list becomes $$\begin{array} { l l l l l } 2 & x & 11 & 4 & 6 \end{array}$$ Write down a further inequality that \(x\) must satisfy.
  3. Use your answers from parts (a) and (b) to write down the value of \(x\).
AQA D1 2011 June Q3
9 marks Moderate -0.8
3 A group of eight friends, \(A , B , C , D , E , F , G\) and \(H\), keep in touch by sending text messages. The cost, in pence, of sending a message between each pair of friends is shown in the following table.
\(\boldsymbol { A }\)\(\boldsymbol { B }\)\(\boldsymbol { C }\)\(\boldsymbol { D }\)\(\boldsymbol { E }\)\(\boldsymbol { F }\)\(\boldsymbol { G }\)\(\boldsymbol { H }\)
\(\boldsymbol { A }\)-15101216111417
\(\boldsymbol { B }\)15-151415161615
\(\boldsymbol { C }\)1015-111012149
\(\boldsymbol { D }\)121411-11121412
\(\boldsymbol { E }\)16151011-131514
\(\boldsymbol { F }\)1116121213-148
G141614141514-13
\(\boldsymbol { H }\)171591214813-
One of the group wishes to pass on a piece of news to all the other friends, either by a direct text or by the message being passed on from friend to friend, at the minimum total cost.
    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 table.
    2. Draw your minimum spanning tree.
    3. Find the minimum total cost.
  1. Person \(H\) leaves the group. Find the new minimum total cost.
AQA D1 2011 June Q4
9 marks Easy -1.2
4 The network below shows some pathways at a school connecting different departments. The number on each edge represents the time taken, in minutes, to walk along that pathway. Carol, the headteacher, wishes to walk from her office ( \(O\) ) to the Drama department (D) .
    1. Use Dijkstra's algorithm on the network to find the minimum walking time from \(O\) to \(D\).
    2. Write down the corresponding route.
  1. On another occasion, Carol needs to go from her office to the Business Studies department \(( B )\).
    1. Write down her minimum walking time.
    2. Write down the route corresponding to this minimum time. \includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-08_1499_1714_1208_153}
AQA D1 2011 June Q5
10 marks Moderate -0.5
5 A council is responsible for gritting main roads in a district. The network shows the main roads in the district. The number on each edge shows the length of the road, in kilometres. The gritter starts from the depot located at point \(A\), and must drive along all the roads at least once before returning to the depot. \includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-10_1294_923_525_555}
  1. Find the length of an optimal Chinese postman route around the main roads in the district, starting and finishing at \(A\).
  2. Zac, a supervisor, wishes to inspect all the roads. He leaves the depot, located at point \(A\), and drives along all the roads at least once before finishing at his home, located at point \(C\). Find the length of an optimal route for Zac.
  3. Liz, a reporter, intends to drive along all the roads at least once in order to report on driving conditions. She can start her journey at any point and can finish her journey at any point.
    1. Find the length of an optimal route for Liz.
    2. State the points from which Liz could start in order to achieve this optimal route.
      \includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-11_2486_1714_221_153}
AQA D1 2011 June Q6
7 marks Easy -1.2
6 A student is tracing the following algorithm.
Line 10 Let \(A = 6\) Line \(20 \quad\) Let \(B = 7\) Line 30 Input \(C\) Line 40 Let \(D = ( A + B ) / 2\) Line \(50 \quad\) Let \(E = C - D ^ { 3 }\) Line 60 If \(E ^ { 2 } < 1\) then go to Line 120
Line 70 If \(E > 0\) then go to Line 100
Line 80 Let \(B = D\) Line 90 Go to Line 40
Line \(100 \quad\) Let \(A = D\) Line 110 Go to Line 40
Line 120 Stop
  1. Trace the algorithm in the case where the input value is \(C = 300\).
  2. The algorithm is intended to find the approximate cube root of any input number. State two reasons why the algorithm is unsatisfactory in its present form.
    (3 marks)
AQA D1 2011 June Q7
12 marks Moderate -0.8
7 A builder needs some screws, nails and plugs. At the local store, there are packs containing a mixture of the three items. A DIY pack contains 200 nails, 200 screws and 100 plugs.
A trade pack contains 1000 nails, 1500 screws and 2500 plugs.
A DIY pack costs \(\pounds 2.50\) and a trade pack costs \(\pounds 15\).
The builder needs at least 5000 nails, 6000 screws and 4000 plugs.
The builder buys \(x\) DIY packs and \(y\) trade packs and wishes to keep his total cost to a minimum.
  1. Formulate the builder's situation as a linear programming problem.
    1. On the grid opposite, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of an objective line.
    2. Use your diagram to find the number of each type of pack that the builder should buy in order to minimise his cost.
    3. Find the builder's minimum cost.
AQA D1 2011 June Q8
15 marks Moderate -0.8
8 Mrs Jones is a spy who has to visit six locations, \(P , Q , R , S , T\) and \(U\), to collect information. She starts at location \(Q\), and travels to each of the other locations, before returning to \(Q\). She wishes to keep her travelling time to a minimum. The diagram represents roads connecting different locations. The number on each edge represents the travelling time, in minutes, along that road. \includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-16_524_866_612_587}
    1. Explain why the shortest time to travel from \(P\) to \(R\) is 40 minutes.
    2. Complete Table 1, on the opposite page, in which the entries are the shortest travelling times, in minutes, between pairs of locations.
    1. Use the nearest neighbour algorithm on Table 1, starting at \(Q\), to find an upper bound for the minimum travelling time for Mrs Jones's tour.
    2. Mrs Jones decides to follow the route given by the nearest neighbour algorithm. Write down her route, showing all the locations through which she passes.
  1. By deleting \(Q\) from Table 1, find a lower bound for the travelling time for Mrs Jones's tour. \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{Table 1}
    \(\boldsymbol { P }\)\(Q\)\(\boldsymbol { R }\)\(\boldsymbol { S }\)\(T\)\(\boldsymbol { U }\)
    \(P\)-25
    \(Q\)25-20212311
    \(\boldsymbol { R }\)20-
    \(\boldsymbol { S }\)21-
    \(T\)23-12
    \(\boldsymbol { U }\)1112-
    \end{table}
    \includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-18_2486_1714_221_153}
AQA D1 2012 June Q1
5 marks Easy -1.2
1 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]{1258a6d3-558a-46dc-a916-d71f71b175ff-02_1003_547_740_737}
  1. Represent this information in an adjacency matrix.
  2. Initially, \(B\) is assigned to task 4, \(C\) to task 3, \(D\) to task 1, \(E\) to task 5 and \(F\) to task 6. By using an algorithm from this initial matching, find a complete matching.
    (3 marks)
AQA D1 2012 June Q2
5 marks Easy -1.8
2 A student is using a shuttle sort algorithm to rearrange a set of numbers into ascending order. Her correct solution for the first three passes is as follows.
AQA D1 2012 June Q3
9 marks Easy -1.3
3 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\). \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-06_810_501_445_388} \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-06_812_499_443_1135}
    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. State the length of your minimum spanning tree.
    3. Draw your minimum spanning tree.
  1. Prim's algorithm from different starting points produces the same minimum spanning tree for this network. State the final edge that would complete the minimum spanning tree using Prim's algorithm:
    1. starting from \(D\);
    2. starting from \(H\).