Questions (30179 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 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 Mechanics 1 PURE Pure 1 S1 S2 S3 S4 Stats 1 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 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 2010 January Q1
7 marks Moderate -0.8
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.
GirlPizza
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)
  1. Show this information on a bipartite graph.
  2. 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
8 marks Easy -1.8
2
  1. 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}$$
  2. State the number of comparisons and the number of swaps (exchanges) for each of the first three passes.
AQA D1 2010 January Q3
10 marks Easy -1.2
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}$$
  1. On Figure 1, draw a suitable diagram to represent the inequalities and indicate the feasible region.
  2. 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
14 marks Moderate -0.8
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.
  1. 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
10 marks Easy -1.3
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.71.91.82.1
B3.1-2.51.83.7
\(\boldsymbol { C }\)3.12.9-2.74.2
\(\boldsymbol { D }\)2.02.82.1-2.3
E2.23.61.91.7-
  1. Find the length of the tour \(B E C D A B\).
  2. Find the length of the tour obtained by using the nearest neighbour algorithm starting from \(B\).
  3. Write down which of your answers to parts (a) and (b) would be the better upper bound for the total distance that Mia drives.
  4. 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
8 marks Easy -1.8
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:
  1. \(A = 1 , B = 5 , N = 2\);
  2. \(A = 1 , B = 5 , N = 4\).
AQA D1 2010 January Q7
10 marks Challenging +1.2
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.
  1. Use Dijkstra's algorithm on Figure 2 to find this minimum total weight.
  2. Find the values of \(x\) and \(y\).
AQA D1 2010 January Q8
8 marks Standard +0.8
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
5 marks Easy -1.8
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
8 marks Moderate -0.8
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\) )
  1. Show all these preferences on a bipartite graph.
  2. 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
11 marks Moderate -0.3
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}
  1. Use Prim's algorithm, starting from \(A\), to find the minimum spanning tree for the network.
  2. State the length of cabling required.
  3. Draw your minimum spanning tree.
  4. 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
7 marks Easy -1.2
4
  1. 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.
  2. A connected graph has 6 vertices and 10 edges. Draw an example of such a graph which is Eulerian.
AQA D1 2005 June Q5
8 marks Easy -1.2
5 A student is using the following algorithm with different values of \(X\).
LINE 10INPUT \(X\)
LINE 20LET \(K = 1\)
LINE 30LET \(Y = \left( X ^ { * } X + 16 \right) / \left( 2 ^ { * } X \right)\)
LINE 40PRINT \(Y\)
LINE 50LET \(X = Y\)
LINE 60LET \(K = K + 1\)
LINE 70IF \(K = 4\) THEN GO TO LINE 90
LINE 80GO TO LINE 30
LINE 90STOP
  1. Trace the algorithm, giving your answers to three decimal places where appropriate:
    1. in the case where the input value of \(X\) is 2 ;
    2. in the case where the input value of \(X\) is - 6 .
  2. Another student used the same algorithm but omitted LINE 70. Describe the outcome for this student.
AQA D1 2005 June Q6
13 marks Moderate -0.5
6 Mia is on holiday in Venice. There are five places she wishes to visit: Rialto \(( R )\), St Mark's \(( S )\), Murano ( \(M\) ), Burano ( \(B\) ) and Lido ( \(L\) ). Boat services connect the five places. The table shows the times, in minutes, to travel between the places. Mia wishes to keep her travelling time to a minimum.
Rialto ( \(R\) )St Mark's ( \(S\) )Murano ( \(M\) )Burano (B)Lido (L)
Rialto ( \(R\) )-15557525
St Mark's ( \(S\) )15-906020
Murano ( \(M\) )5590-2580
Burano (B)756025-50
Lido ( \(L\) )25208050-
    1. Find the length of the tour \(S R M B L S\).
    2. Find the length of the tour using the nearest neighbour algorithm starting from \(S\).
  1. By deleting Burano ( \(B\) ), find a lower bound for the length of the minimum tour.
  2. Sketch a network showing the edges that give the lower bound found in part (b) and comment on its significance.
AQA D1 2005 June Q7
10 marks Moderate -0.3
7 [Figure 1, printed on the insert, is provided for use in this question.]
The diagram shows some of the main roads connecting Royton to London. The numbers on the edges represent the travelling times, in minutes, between adjacent towns. David lives in Royton and is planning to travel along some of the roads to a meeting in London. \includegraphics[max width=\textwidth, alt={}, center]{a1290c22-f28d-42aa-89d5-10d60ca4741c-06_2196_1479_557_310}
    1. Use Dijkstra's algorithm on Figure 1 to find the minimum travelling time from Royton to London.
    2. Write down the route corresponding to this minimum travelling time.
  1. On a particular day, before David leaves Royton, he knows that the road connecting Walsall and Marston is closed. Find the minimum extra time required to travel from Royton to London on this day. Write down the corresponding route.
AQA D1 2005 June Q8
13 marks Easy -1.2
8 [Figure 2, printed on the insert, is provided for use in this question.]
A company makes two types of boxes of chocolates, executive and luxury.
Every hour the company must make at least 15 of each type and at least 35 in total.
Each executive box contains 20 dark chocolates and 12 milky chocolates.
Each luxury box contains 10 dark chocolates and 18 milky chocolates.
Every hour the company has 600 dark chocolates and 600 milky chocolates available.
The company makes a profit of \(\pounds 1.50\) on each executive box and \(\pounds 1\) on each luxury box.
The company makes and sells \(x\) executive boxes and \(y\) luxury boxes every hour.
The company wishes to maximise its hourly profit, \(\pounds P\).
  1. Show that one of the constraints leads to the inequality \(2 x + 3 y \leqslant 100\).
  2. Formulate the company's situation as a linear programming problem.
  3. On Figure 2, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and an objective line.
  4. Use your diagram to find the maximum hourly profit.
AQA D1 2006 June Q1
6 marks Easy -1.2
1 Five people, \(A , B , C , D\) and \(E\), are to be matched to five tasks, 1, 2, 3, 4 and 5. The table shows which tasks each person can do.
PersonTasks
\(A\)\(1,3,5\)
\(B\)2,4
\(C\)2
\(D\)4,5
\(E\)3,5
  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 . Use an alternating path from this initial matching to find a complete matching.
AQA D1 2006 June Q2
8 marks Easy -1.8
2
  1. Use a shuttle sort to rearrange the following numbers into ascending order. $$\begin{array} { l l l l l l l l } 18 & 2 & 12 & 7 & 26 & 19 & 16 & 24 \end{array}$$
  2. State the number of comparisons and swaps (exchanges) for each of the first three passes.
AQA D1 2006 June Q3
14 marks Standard +0.3
3 [Figure 1, printed on the insert, is provided for use in part (b) of this question.]
The diagram shows a network of roads. The number on each edge is the length, in kilometres, of the road. \includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-03_716_1303_559_388}
    1. Use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the network.
    2. State the length of your minimum spanning tree.
    1. Use Dijkstra's algorithm on Figure 1 to find the shortest distance from \(A\) to \(J\).
    2. A new road, of length \(x \mathrm {~km}\), is built connecting \(I\) to \(J\). The minimum distance from \(A\) to \(J\) is reduced by using this new road. Find, and solve, an inequality for \(x\).
AQA D1 2006 June Q4
11 marks Standard +0.8
4 The diagram shows a network of roads connecting 6 villages. The number on each edge is the length, in miles, of the road. \includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-04_670_1298_466_356} Total length of the roads \(= 164\) miles
  1. A police patrol car based at village \(A\) has to travel along each road at least once before returning to \(A\). Find the length of an optimal 'Chinese postman' route for the police patrol car.
  2. A council worker starts from \(A\) and travels along each road at least once before finishing at \(C\). Find the length of an optimal route for the council worker.
  3. A politician is to travel along all the roads at least once. He can start his journey at any village and can finish his journey at any village.
    1. Find the length of an optimal route for the politician.
    2. State the vertices from which the politician could start in order to achieve this optimal route.
AQA D1 2006 June Q5
18 marks Moderate -0.8
5 [Figure 2, printed on the insert, is provided for use in this question.]
  1. Gill is solving a travelling salesperson problem.
    1. She finds the following upper bounds: 7.5, 8, 7, 7.5, 8.5. Write down the best upper bound.
    2. She finds the following lower bounds: \(6.5,7,6.5,5,7\). Write down the best lower bound.
  2. George is travelling by plane to a number of cities. He is to start at \(F\) and visit each of the other cities at least once before returning to \(F\). The diagram shows the times of flights, in hours, between cities. Where no time is shown, there is no direct flight available. \includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-05_936_826_1162_589}
    1. Complete Figure 2 to show the minimum times to travel between all pairs of cities.
    2. Find an upper bound for the minimum total flying time by using the route FTPOMF.
    3. Using the nearest neighbour algorithm starting from \(F\), find an upper bound for the minimum total flying time.
    4. By deleting \(F\), find a lower bound for the minimum total flying time.
AQA D1 2006 June Q6
18 marks Moderate -0.8
6 [Figure 3, printed on the insert, is provided for use in this question.]
Ernesto is to plant a garden with two types of tree: palms and conifers.
He is to plant at least 10, but not more than 80 palms.
He is to plant at least 5 , but not more than 40 conifers.
He cannot plant more than 100 trees in total. Each palm needs 20 litres of water each day and each conifer needs 60 litres of water each day. There are 3000 litres of water available each day. Ernesto makes a profit of \(\pounds 2\) on each palm and \(\pounds 1\) on each conifer that he plants and he wishes to maximise his profit. Ernesto plants \(x\) palms and \(y\) conifers.
  1. Formulate Ernesto's situation as a linear programming problem.
  2. On Figure 3, 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 maximum profit for Ernesto.
  4. Ernesto introduces a new pricing structure in which he makes a profit of \(\pounds 1\) on each palm and \(\pounds 4\) on each conifer. Find Ernesto's new maximum profit and the number of each type of tree that he should plant to obtain this maximum profit.
AQA D1 2006 June Q7
6 marks Moderate -0.8
7 A connected graph \(\mathbf { G }\) has \(m\) vertices and \(n\) edges.
    1. Write down the number of edges in a minimum spanning tree of \(\mathbf { G }\).
    2. Hence write down an inequality relating \(m\) and \(n\).
  1. The graph \(\mathbf { G }\) contains a Hamiltonian cycle. Write down the number of edges in this cycle.
  2. In the case where \(\mathbf { G }\) is Eulerian, draw a graph of \(\mathbf { G }\) for which \(m = 6\) and \(n = 12\).
AQA D1 2007 June Q1
9 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
A010100
B101010
\(\boldsymbol { C }\)001011
D000100
E010001
\(\boldsymbol { F }\)000110
  1. Show this information on a bipartite graph.
  2. At first \(F\) insists on being matched to task 4. Explain why, in this case, a complete matching is impossible.
  3. To find a complete matching \(F\) agrees to be assigned to either task 4 or task 5. Initially \(B\) is matched to task 3, \(C\) to task 6, \(E\) to task 2 and \(F\) to task 4.
    From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.
AQA D1 2007 June Q2
8 marks Easy -1.2
2
  1. Use a Shell sort 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 } 28 & 22 & 20 & 17 & 14 & 11 & 6 & 5 \end{array}$$
    1. Write down the number of comparisons on the first pass.
    2. Write down the number of swaps on the first pass.
  2. Find the total number of comparisons needed to rearrange the original list of 8 numbers into ascending order using a shuttle sort.
    (You do not need to perform a shuttle sort.)