Questions D1 (932 questions)

Browse by module
All questions AEA AS Paper 1 AS Paper 2 AS Pure 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 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 S1 S2 S3 S4 Unit 1 Unit 2 Unit 3 Unit 4
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
Sort by: Default | Easiest first | Hardest first
Edexcel D1 2003 January Q4
9 marks Standard +0.3
\includegraphics{figure_2} The arcs in Fig. 2 represent roads in a town. The weight on each arc gives the time, in minutes, taken to drive along that road. The times taken to drive along \(AB\) and \(DE\) vary depending upon the time of day. A police officer wishes to drive along each road at least once, starting and finishing at \(A\). The journey is to be completed in the least time.
  1. Briefly explain how you know that a route between \(B\) and \(E\) will have to be repeated. [1]
  2. List the possible routes between \(B\) and \(E\). State how long each would take, in terms of \(x\) where appropriate. [2]
  3. Find the range of values that \(x\) must satisfy so that \(DE\) would be one of the repeated arcs. [3] Given that \(x = 7\),
  4. find the total time needed for the police officer to carry out this journey. [3]
Edexcel D1 2003 January Q5
10 marks Moderate -0.8
\includegraphics{figure_3} A project is modelled by the activity network in Fig. 3. The activities are represented by the arcs. One worker is required for each activity. The number in brackets on each arc gives the time, in hours, to complete the activity. The earliest event time and the latest event time are given by the numbers in the left box and right box respectively.
  1. State the value of \(x\) and the value of \(y\). [2]
  2. List the critical activities. [2]
  3. Explain why at least 3 workers will be needed to complete this project in 38 hours. [2]
  4. Schedule the activities so that the project is completed in 38 hours using just 3 workers. You must make clear the start time and finish time of each activity. [4]
Edexcel D1 2003 January Q6
9 marks Easy -1.3
25 22 30 18 29 21 27 21 The list of numbers above is to be sorted into descending order.
    1. Perform the first pass of a bubble sort, giving the state of the list after each exchange.
    2. Perform further passes, giving the state of the list after each pass, until the algorithm terminates.
    [5]
The numbers represent the lengths, in cm, of pieces to be cut from rods of length 50 cm.
    1. Show the result of applying the first fit decreasing bin packing algorithm to this situation.
    2. Determine whether your solution to \((b)\) \((i)\) has used the minimum number of 50 cm rods.
    [4]
Edexcel D1 2003 January Q7
14 marks Standard +0.3
\includegraphics{figure_4} Figure 4 shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow from sources \(A\) and \(B\) to sinks \(I\), \(J\) and \(K\). Take this as the initial flow pattern.
  1. On Diagram 1 in the answer booklet, add a supersource \(S\) and a supersink \(W\) to obtain a capacitated network with a single source and single sink. State the minimum capacities of the arcs you have added. [3]
    1. Use the given initial flow and the labelling procedure on Diagram 2 to find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
    2. Verify that your flow is maximal.
    [9]
  3. Show your maximum flow pattern on Diagram 3. [2]
Edexcel D1 2003 January Q8
14 marks Moderate -0.3
The tableau below is the initial tableau for a maximising linear programming problem.
Basic Variable\(x\)\(y\)\(z\)\(r\)\(s\)Value
\(r\)234108
\(s\)3310110
\(P\)-8-9-5000
  1. For this problem \(x \geq 0\), \(y \geq 0\), \(z \geq 0\). Write down the other two inequalities and the objective function. [3]
  2. Solve this linear programming problem. [8]
  3. State the final value of \(P\), the objective function, and of each of the variables. [3]
Edexcel D1 2004 January Q1
6 marks Easy -2.0
Define the terms
  1. bipartite graph, [2]
  2. alternating path, [2]
  3. matching, [1]
  4. complete matching. [1]
Edexcel D1 2004 January Q2
6 marks Moderate -0.3
A three-variable linear programming problem in \(x\), \(y\) and \(z\) is to be solved. The objective is to maximise the profit P. The following tableau was obtained.
Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(s\)30201\(-\frac{2}{3}\)\(\frac{2}{3}\)
\(r\)40\(\frac{7}{2}\)108\(\frac{9}{2}\)
\(y\)5170037
P30200863
  1. State, giving your reason, whether this tableau represents the optimal solution. [1]
  2. State the values of every variable. [3]
  3. Calculate the profit made on each unit of \(y\). [2]
Edexcel D1 2004 January Q3
7 marks Moderate -0.5
\includegraphics{figure_1} Figure 1 shows a network of roads represented by arcs. The capacity of the road represented by that arc is shown on each arc. The numbers in circles represent a possible flow of 26 from \(B\) to \(L\). Three cuts \(C_1\), \(C_2\) and \(C_3\) are shown on Fig. 1.
  1. Find the capacity of each of the three cuts. [3]
  2. Verify that the flow of 26 is maximal. [1]
The government aims to maximise the possible flow from \(B\) to \(L\) by using one of two options. Option 1: Build a new road from \(E\) to \(J\) with capacity 5. or Option 2: Build a new road from \(F\) to \(H\) with capacity 3.
  1. By considering both options, explain which one meets the government's aim [3]
Edexcel D1 2004 January Q4
9 marks Standard +0.3
\includegraphics{figure_2} An engineer needs to check the state of a number of roads to see whether they need resurfacing. The roads that need to be checked are represented by the arcs in Fig. 2. The number on each arc represents the length of that road in km. To check all the roads, he needs to travel along each road at least once. He wishes to minimise the total distance travelled. The engineer's office is at \(G\), so he starts and ends his journey at \(G\).
  1. Use an appropriate algorithm to find a route for the engineer to follow. State your route and its length. [6]
The engineer lives at \(D\). He believes he can reduce the distance travelled by starting from home and inspecting all the roads on the way to his office at \(G\).
  1. State whether the engineer is correct in his belief. If so, calculate how much shorter his new route is. If not, explain why not. [3]
Edexcel D1 2004 January Q5
10 marks Easy -1.2
\includegraphics{figure_3} Figure 3 describes an algorithm in the form of a flow chart, where \(a\) is a positive integer. List \(P\), which is referred to in the flow chart, comprises the prime numbers 2, 3, 5, 7, 11, 13, 17, ...
  1. Starting with \(a = 90\), implement this algorithm. Show your working in the table in the answer book. [7]
  2. Explain the significance of the output list. [2]
  3. Write down the final value of \(c\) for any initial value of \(a\). [1]
Edexcel D1 2004 January Q6
10 marks Moderate -0.8
ABCDEF
A\(-\)73\(-\)811
B7\(-\)42\(-\)7
C34\(-\)59\(-\)
D\(-\)25\(-\)63
E8\(-\)96\(-\)\(-\)
F117\(-\)3\(-\)\(-\)
The matrix represents a network of roads between six villages \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\). The value in each cell represents the distance, in km, along these roads.
  1. Show this information on the diagram in the answer book. [2]
  2. Use Kruskal's algorithm to determine the minimum spanning tree. State the order in which you include the arcs and the length of the minimum spanning tree. Draw the minimum spanning tree. [5]
  3. Starting at \(D\), use Prim's algorithm on the matrix given in the answer book to find the minimum spanning tree. State the order in which you include the arcs. [3]
Edexcel D1 2004 January Q7
13 marks Moderate -0.3
Becky's bird food company makes two types of bird food. One type is for bird feeders and the other for bird tables. Let \(x\) represent the quantity of food made for bird feeders and \(y\) represent the quantity of food made for bird tables. Due to restrictions in the production process, and known demand, the following constraints apply. $$x + y \leq 12,$$ $$y < 2x,$$ $$2y \geq 7,$$ $$y + 3x \geq 15.$$
  1. On the axes provided, show these constraints and label the feasible region \(R\). [5]
The objective is to minimise \(C = 2x + 5y\).
  1. Solve this problem, making your method clear. Give, as fractions, the value of \(C\) and the amount of each type of food that should be produced. [4]
Another objective (for the same constraints given above) is to maximise \(P = 3x + 2y\), where the variables must take integer values.
  1. Solve this problem, making your method clear. State the value of \(P\) and the amount of each type of food that should be produced. [4]
Edexcel D1 2004 January Q8
14 marks Moderate -0.8
\includegraphics{figure_4} A trainee at a building company is using critical path analysis to help plan a project. Figure 4 shows the trainee's activity network. Each activity is represented by an arc and the number in brackets on each arc is the duration of the activity, in hours.
  1. Find the values of \(x\), \(y\) and \(z\). [3]
  2. State the total length of the project and list the critical activities. [2]
  3. Calculate the total float time on
    1. activity \(N\),
    2. activity \(H\). [3]
The trainee's activity network is checked by the supervisor who finds a number of errors and omissions in the diagram. The project should be represented by the following precedence table.
ActivityMust be preceded by:Duration
\(A\)\(-\)4
\(B\)\(-\)3
\(C\)\(-\)5
\(D\)\(B\)2
\(E\)\(A, D\)8
\(F\)\(B\)2
\(G\)\(C\)2
\(H\)\(C\)3
\(I\)\(F, G\)4
\(J\)\(F, G\)2
\(K\)\(F, G\)7
\(L\)\(E, I\)9
\(M\)\(H, J\)3
\(N\)\(E, I, K, M\)3
\(P\)\(E, I\)6
\(Q\)\(H, J\)5
\(R\)\(Q\)7
  1. By adding activities and dummies amend the diagram in the answer book so that it represents the precedence table. (The durations of activities \(A\), \(B\), ..., \(N\) are all correctly given on the diagram in the answer book.) [4]
  2. Find the total time needed to complete this project. [2]
Edexcel D1 2005 January Q1
6 marks Moderate -0.8
\includegraphics{figure_1} The bipartite graph in Figure 1 shows a mapping between six people, Andy (\(A\)), David (\(D\)), Joan (\(J\)), Preety (\(P\)), Sally (\(S\)) and Trevor (\(T\)), and six tasks 1, 2, 3, 4, 5 and 6. The initial matching is \(A\) to 2, \(D\) to 1, \(J\) to 3 and \(P\) to 4.
  1. Indicate this initial matching in a distinctive way on the bipartite graph drawn in the answer book. [1]
  2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating paths you use. [5]
Edexcel D1 2005 January Q2
7 marks Moderate -0.3
The precedence table for activities involved in producing a computer game is shown below.
ActivityMust be preceded by
\(A\)\(-\)
\(B\)\(A\)
\(C\)\(B\)
\(D\)\(A, C\)
\(E\)\(A\)
\(F\)\(E\)
\(G\)\(E\)
\(H\)\(G\)
\(I\)\(D, F\)
\(J\)\(G, I\)
\(K\)\(G, I\)
\(L\)\(H, K\)
An activity on arc network is to be drawn to model this production process.
  1. Explain why it is necessary to use at least two dummies when drawing the activity network. [2]
  2. Draw the activity network using exactly two dummies. [5]
Edexcel D1 2005 January Q3
8 marks Easy -1.2
\includegraphics{figure_2} The network in Figure 2 shows the distances, in metres, between 10 wildlife observation points. The observation points are to be linked by footpaths, to form a network along the arcs indicated, using the least possible total length.
  1. Find a minimum spanning tree for the network in Figure 2, showing clearly the order in which you selected the arcs for your tree, using
    1. Kruskal's algorithm, [3]
    2. Prim's algorithm, starting from \(A\). [3]
    Given that footpaths are already in place along \(AB\) and \(FI\) and so should be included in the spanning tree,
  2. explain which algorithm you would choose to complete the tree, and how it should be adapted. (You do not need to find the tree.) [2]
Edexcel D1 2005 January Q4
11 marks Easy -1.3
\(650 \quad 431 \quad 245 \quad 643 \quad 455 \quad 134 \quad 710 \quad 234 \quad 162 \quad 452\)
  1. The list of numbers above is to be sorted into descending order. Perform a Quick Sort to obtain the sorted list, giving the state of the list after each pass, indicating the pivot elements. [5]
The numbers in the list represent the lengths, in mm, of some pieces of wood. The wood is sold in one metre lengths.
  1. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from the minimum number of one metre lengths. (You should ignore wastage due to cutting.) [4]
  2. Determine whether your solution to part (b) is optimal. Give a reason for your answer. [2]
Edexcel D1 2005 January Q5
11 marks Moderate -0.5
\includegraphics{figure_3} Figure 3 shows a network of paths. The number on each arc gives the distance, in metres, of that path.
  1. Use Dijkstra's algorithm to find the shortest distance from \(A\) to \(H\). [5]
  2. Solve the route inspection problem for the network shown in Figure 3. You should make your method and working clear. State a shortest route, starting at \(A\), and find its length. [The total weight of the network is 1241] [6]
Edexcel D1 2005 January Q6
14 marks Moderate -0.8
\includegraphics{figure_4} Figure 4 shows a capacitated directed network. The number on each arc is its capacity.
  1. State the maximum flow along
    1. \(SADT\),
    2. \(SCET\),
    3. \(SBFT\). [2]
  2. Show these maximum flows on Diagram 1 in the answer book. [1]
Take your answer to part (b) as the initial flow pattern.
    1. Use the labelling procedure to find a maximum flow from \(S\) to \(T\). Your working should be shown on Diagram 2 in the answer book. List each flow-augmenting route you use, together with its flow. [5]
    2. Draw your final flow pattern on Diagram 3 in the answer book. [2]
    3. Prove that your flow is maximal. [3]
  2. Give an example of a practical situation that could have been modelled by the original network. [1]
Edexcel D1 2005 January Q7
18 marks Standard +0.3
Flatland UK Ltd makes three types of carpet, the Lincoln, the Norfolk and the Suffolk. The carpets all require units of black, green and red wool. For each roll of carpet, the Lincoln requires 1 unit of black, 1 of green and 3 of red, the Norfolk requires 1 unit of black, 2 of green and 2 of red, and the Suffolk requires 2 units of black, 1 of green and 1 of red. There are up to 30 units of black, 40 units of green and 50 units of red available each day. Profits of £50, £80 and £60 are made on each roll of Lincoln, Norfolk and Suffolk respectively. Flatland UK Ltd wishes to maximise its profit. Let the number of rolls of the Lincoln, Norfolk and Suffolk made daily be \(x\), \(y\) and \(z\) respectively.
  1. Formulate the above situation as a linear programming problem, listing clearly the constraints as inequalities in their simplest form, and stating the objective function. [4]
This problem is to be solved using the Simplex algorithm. The most negative number in the profit row is taken to indicate the pivot column at each stage.
  1. Stating your row operations, show that after one complete iteration the tableau becomes
    Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
    \(r\)\(\frac{1}{2}\)0\(1\frac{1}{2}\)1\(-\frac{1}{2}\)010
    \(y\)\(\frac{1}{2}\)1\(\frac{1}{2}\)0\(\frac{1}{2}\)020
    \(t\)2000\(-1\)110
    \(P\)\(-10\)0\(-20\)04001600
    [4]
  2. Explain the practical meaning of the value 10 in the top row. [2]
    1. Perform one further complete iteration of the Simplex algorithm.
    2. State whether your current answer to part (d)(i) is optimal. Give a reason for your answer.
    3. Interpret your current tableau, giving the value of each variable. [8]
Edexcel D1 2006 January Q1
7 marks Moderate -0.8
\includegraphics{figure_1} A taxi firm has six taxis \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\), available for six journeys, 1, 2, 3, 4, 5 and 6, which are booked for 9 a.m. tomorrow. The bipartite graph shown in Figure 1 shows the possible matchings. Initially \(A\), \(B\), \(C\) and \(D\) are matched to 5, 2, 3 and 6 respectively, as indicated in Figure 2.
  1. Explain why it is necessary to perform the maximum matching algorithm twice in order to try to obtain a complete matching. [1]
  2. Use the maximum matching algorithm twice to obtain a complete matching. List clearly the alternating paths you use. [6]
Edexcel D1 2006 January Q2
15 marks Easy -1.3
\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)
\(A\)\(-\)4811792\(-\)\(-\)\(-\)
\(B\)48\(-\)\(-\)\(-\)\(-\)6355
\(C\)117\(-\)\(-\)28\(-\)\(-\)85
\(D\)92\(-\)28\(-\)58132\(-\)
\(E\)\(-\)\(-\)\(-\)58\(-\)124\(-\)
\(F\)\(-\)63\(-\)132124\(-\)\(-\)
\(G\)\(-\)5585\(-\)\(-\)\(-\)\(-\)
The table shows the lengths, in metres, of the paths between seven vertices \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) and \(G\) in a network N.
  1. Use Prim's algorithm, starting at \(A\), to solve the minimum connector problem for this table of distances. You must clearly state the order in which you selected the edges of your tree, and the weight of your final tree. Draw your tree using the vertices given in Diagram 1 in the answer book. [5]
  2. Draw N using the vertices given in Diagram 2 in the answer book. [3]
  3. Solve the Route Inspection problem for N. You must make your method of working clear. State a shortest route and find its length. (The weight of N is 802.) [7]
Edexcel D1 2006 January Q3
9 marks Easy -1.2
\includegraphics{figure_3} An algorithm is described by the flow chart shown in Figure 3.
  1. Complete the table in the answer book recording the results of each step as the algorithm is applied. (Notice that values of \(A\), \(B\), \(C\) and \(D\) are to be given to 3 decimal places, and the values of \(E\) to 1 significant figure.) [8]
  2. Write down the output from the algorithm. [1]
Edexcel D1 2006 January Q4
11 marks Moderate -0.8
  1. Define the terms
    1. cut,
    2. minimum cut,
    as applied to a directed network flow. [2]
\includegraphics{figure_4} Figure 4 shows a capacitated directed network and two cuts \(C_1\) and \(C_2\). The number on each arc is its capacity.
  1. State the values of the cuts \(C_1\) and \(C_2\). [3]
Given that one of these two cuts is a minimum cut,
  1. Find a maximum flow pattern by inspection, and show it on the diagram in the answer book. [3]
  2. Find a second minimum cut for this network. [1]
In order to increase the flow through the network it is decided to add an arc of capacity 100 joining \(D\) either to \(E\) or to \(G\).
  1. State, with a reason, which of these arcs should be added, and the value of the increased flow. [2]
Edexcel D1 2006 January Q5
15 marks Moderate -0.8
\includegraphics{figure_5} The network in Figure 5 shows the activities involved in a process. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, taken to complete the activity.
  1. Calculate the early time and late time for each event, showing them on the diagram in the answer book. [4]
  2. Determine the critical activities and the length of the critical path. [2]
  3. On the grid in the answer book, draw a cascade (Gantt) chart for the process. [4]
Each activity requires only one worker, and workers may not share an activity.
  1. Use your cascade chart to determine the minimum numbers of workers required to complete the process in the minimum time. Explain your reasoning clearly. [2]
  2. Schedule the activities, using the number of workers you found in part \((d)\), so that the process is completed in the shortest time. [3]