Questions (33218 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 2012 January Q3
9 marks Moderate -0.8
3 The following network shows the roads connecting seven villages, \(A , B , C , \ldots , G\). The number on each edge represents the length, in miles, between a pair of villages. \includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-06_978_1108_443_466}
  1. Use Kruskal's algorithm to find a minimum spanning tree for the network. (5 marks)
  2. State the length of your minimum spanning tree.
  3. There are two minimum spanning trees for this network. Draw both of these minimum spanning trees.
AQA D1 2012 January Q4
6 marks Standard +0.3
4 The following network shows the times, in minutes, taken by a policeman to walk along roads connecting 12 places, \(A , B , \ldots , L\), on his beat. Each day, the policeman has to walk along each road at least once, starting and finishing at \(A\). \includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-08_1141_1313_461_360} The total of all the times in the network is 224 minutes.
  1. Find the length of an optimal Chinese postman route for the policeman.
  2. State the number of times that the vertex \(J\) would appear in a route corresponding to the length found in part (a).
AQA D1 2012 January Q5
10 marks Standard +0.3
5 The feasible region of a linear programming problem is determined by the following: $$\begin{aligned} y & \geqslant 20 \\ x + y & \geqslant 25 \\ 5 x + 2 y & \leqslant 100 \\ y & \leqslant 4 x \\ y & \geqslant 2 x \end{aligned}$$
  1. On Figure 1 opposite, draw a suitable diagram to represent the inequalities and indicate the feasible region.
  2. Use your diagram to find the minimum value of \(P\), on the feasible region, in the case where:
    1. \(P = x + 2 y\);
    2. \(P = - x + y\). In each case, state the corresponding values of \(x\) and \(y\).
AQA D1 2012 January Q6
11 marks Standard +0.3
6 The network below shows the lengths of roads, in miles, connecting 10 towns, \(A , B , \ldots , J\).
  1. Use Dijkstra's algorithm on the network to find the shortest distance from \(A\) to \(J\). Show all your working at each vertex.
  2. Write down the corresponding route.
  3. A new road is to be constructed connecting \(B\) to \(G\). Find the length of this new road if the shortest distance from \(A\) to \(J\) is reduced by 10 miles. State the new route.
    (3 marks) \includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-12_1846_1719_861_150}
AQA D1 2012 January Q7
19 marks Easy -1.2
7 The diagram shows the locations of some schools. The number on each edge shows the distance, in miles, between pairs of schools. \includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-14_1031_1231_428_392} Sam, an adviser, intends to travel from one school to the next until he has visited all of the schools, before returning to his starting school. The shortest distances for Sam to travel between some of the schools are shown in Table 1 opposite.
  1. Complete Table 1.
    1. On the completed Table 1, use the nearest neighbour algorithm, starting from \(B\), to find an upper bound for the length of Sam's tour.
    2. Write down Sam's actual route if he were to follow the tour corresponding to the answer in part (b)(i).
    3. Using the nearest neighbour algorithm, starting from each of the other vertices in turn, the following upper bounds for the length of Sam's tour were obtained: 77, 77, 77, 76, 77 and 76. Write down the best upper bound. 7
    1. On Table 2 below, showing the order in which you select the edges, use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the schools \(A , B , C\), \(D , F\) and \(G\).
    2. Hence find a lower bound for the length of Sam's minimum tour.
    3. By deleting each of the other vertices in turn, the following lower bounds for the length of a minimum tour were found: \(50,48,52,51,56\) and 64 . Write down the best lower bound.
  2. Given that the length of a minimum tour is \(T\) miles, use your answers to parts (b) and (c) to write down the smallest interval within which you know \(T\) must lie.
    (2 marks) \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{Table 2}
    \(\boldsymbol { A }\)\(\boldsymbol { B }\)\(\boldsymbol { C }\)\(\boldsymbol { D }\)\(\boldsymbol { F }\)G
    A-2641627
    \(\boldsymbol { B }\)2-831526
    \(\boldsymbol { C }\)68-102232
    \(\boldsymbol { D }\)4310-1223
    \(\boldsymbol { F }\)16152212-20
    G2726322320-
    \end{table}
    \includegraphics[max width=\textwidth, alt={}]{5a414265-6273-41c5-ad5f-f6316bd774d0-17_2486_1714_221_153}
AQA D1 2012 January Q8
10 marks Standard +0.8
8 Four distinct positive integers are \(( 3 x - 5 ) , ( 2 x + 3 ) , ( x + 1 )\) and \(( 4 x - 13 )\).
  1. Explain why \(x \geqslant 4\).
  2. The four integers are to be sorted into ascending order using a bubble sort. The original list is \(\begin{array} { c c c c } ( 3 x - 5 ) & ( 2 x + 3 ) & ( x + 1 ) & ( 4 x - 13 ) \end{array}\) After the first pass, the list is \(( 3 x - 5 ) \quad ( x + 1 ) \quad ( 4 x - 13 ) \quad ( 2 x + 3 )\) After the second pass, the list is \(( x + 1 )\) \(( 4 x - 13 )\) \(( 3 x - 5 )\) \(( 2 x + 3 )\) After the third pass, the list is \(( 4 x - 13 ) \quad ( x + 1 )\) \(( 3 x - 5 )\) ( \(2 x + 3\) )
    1. By considering the list after the first pass, write down three inequalities in terms of \(x\).
    2. By considering the list after the second pass, write down two further inequalities in terms of \(x\).
    3. By considering the list after the third pass, write down one further inequality in terms of \(x\).
  3. Hence, by considering the results above, find the value of \(x\).
    \includegraphics[max width=\textwidth, alt={}]{5a414265-6273-41c5-ad5f-f6316bd774d0-19_2486_1714_221_153}
AQA D1 2013 January Q1
4 marks Moderate -0.8
1
  1. Draw a bipartite graph to represent the following adjacency matrix.
    12345
    A00001
    \(\boldsymbol { B }\)00011
    \(\boldsymbol { C }\)01011
    \(\boldsymbol { D }\)00011
    \(\boldsymbol { E }\)11101
  2. If \(A , B , C , D\) and \(E\) represent five people and 1, 2, 3, 4 and 5 represent five tasks to which they are to be assigned, explain why a complete matching is impossible.
    (2 marks)
AQA D1 2013 January Q2
5 marks Easy -1.2
2
  1. Use a Shell sort to arrange the following numbers into ascending order. $$\begin{array} { l l l l l l l l } 7 & 8 & 1 & 6 & 3 & 4 & 5 & 2 \end{array}$$
  2. Write down the number of comparisons on the first pass.
AQA D1 2013 January Q3
7 marks Moderate -0.8
3 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\). A delivery man lives in village \(A\) and is to drive along all the roads at least once before returning to \(A\). \includegraphics[max width=\textwidth, alt={}, center]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-06_1072_1027_548_502}
  1. Find the length of an optimal Chinese postman route around the nine villages, starting and finishing at \(A\).
  2. For an optimal Chinese postman route corresponding to your answer in part (a), state:
    1. the number of times village \(E\) would be visited;
    2. the number of times village \(I\) would be visited.
AQA D1 2013 January Q4
11 marks Easy -1.2
4 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\). A programme of resurfacing some roads is undertaken to ensure that each village can access all other villages along a resurfaced road, while keeping the amount of road to be resurfaced to a minimum. \includegraphics[max width=\textwidth, alt={}, center]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-08_1008_1043_589_497}
    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. Given that Prim's algorithm is used with different start vertices, state the final edge to be added to the minimum spanning tree if:
    1. the start vertex is \(E\);
    2. the start vertex is \(G\).
  2. Given that Kruskal's algorithm is used to find the minimum spanning tree, state which edge would be:
    1. the first to be included in the tree;
    2. the last to be included in the tree.
AQA D1 2013 January Q5
10 marks Moderate -0.8
5 The feasible region of a linear programming problem is defined by $$\begin{aligned} x + y & \leqslant 60 \\ 2 x + y & \leqslant 80 \\ y & \geqslant 20 \\ x & \geqslant 15 \\ y & \geqslant x \end{aligned}$$
  1. On the grid opposite, draw a suitable diagram to represent these inequalities and indicate the feasible region.
  2. In each of the following cases, use your diagram to find the maximum value of \(P\) on the feasible region. In each case, state the corresponding values of \(x\) and \(y\).
    1. \(P = x + 4 y\)
    2. \(P = 4 x + y\)
AQA D1 2013 January Q6
10 marks Easy -1.2
6 The network opposite shows some roads connecting towns. The number on each edge represents the length, in miles, of the road connecting a pair of towns.
    1. Use Dijkstra's algorithm on the network to find the minimum distance from \(A\) to \(J\).
    2. Write down the corresponding route.
  1. The road \(A J\) is a dual carriageway. Ken drives at 60 miles per hour on this road and drives at 50 miles per hour on all other roads. Find the minimum time to travel from \(A\) to \(J\).
    \includegraphics[max width=\textwidth, alt={}]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-15_2487_1714_221_152}
AQA D1 2013 January Q7
8 marks Moderate -0.8
7
  1. A simple connected graph \(X\) has eight vertices.
    1. State the minimum number of edges of the graph.
    2. Find the maximum number of edges of the graph.
  2. A simple connected graph \(Y\) has \(n\) vertices.
    1. State the minimum number of edges of the graph.
    2. Find the maximum number of edges of the graph.
  3. A simple graph \(Z\) has six vertices and each of the vertices has the same degree \(d\).
    1. State the possible values of \(d\).
    2. If \(Z\) is connected, state the possible values of \(d\).
    3. If \(Z\) is Eulerian, state the possible values of \(d\).
AQA D1 2013 January Q8
12 marks Easy -1.2
8 Tony delivers paper to five offices, \(A , B , C , D\) and \(E\). Tony starts his deliveries at office \(E\) and travels to each of the other offices once, before returning to office \(E\). Tony wishes to keep his travelling time to a minimum. The table shows the travelling times, in minutes, between the offices.
AQA D1 2013 January Q9
8 marks Standard +0.3
9 A factory can make three different kinds of balloon pack: gold, silver and bronze. Each pack contains three different types of balloon: \(A , B\) and \(C\). Each gold pack has 2 type \(A\) balloons, 3 type \(B\) balloons and 6 type \(C\) balloons.
Each silver pack has 3 type \(A\) balloons, 4 type \(B\) balloons and 2 type \(C\) balloons.
Each bronze pack has 5 type \(A\) balloons, 3 type \(B\) balloons and 2 type \(C\) balloons.
Every hour, the maximum number of each type of balloon available is 400 type \(A\), 400 type \(B\) and 400 type \(C\). Every hour, the factory must pack at least 1000 balloons.
Every hour, the factory must pack more type \(A\) balloons than type \(B\) balloons.
Every hour, the factory must ensure that no more than \(40 \%\) of the total balloons packed are type \(C\) balloons. Every hour, the factory makes \(x\) gold, \(y\) silver and \(z\) bronze packs.
Formulate the above situation as 6 inequalities, in addition to \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\), simplifying your answers.
(8 marks)
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}