Questions — Edexcel D1 (505 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 2006 June Q6
16 marks Moderate -0.8
The tableau below is the initial tableau for a maximising linear programming problem.
Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)710101003600
\(s\)69120103600
\(t\)2340012400
\(P\)\(-35\)\(-55\)\(-60\)0000
  1. Write down the four equations represented in the initial tableau above. [4]
  2. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use. [9]
  3. State the values of the objective function and each variable. [3]
Edexcel D1 2006 June Q7
14 marks Moderate -0.3
\includegraphics{figure_5} Figure 5 shows a capacitated, directed network. The capacity of each arc is shown on each arc. The numbers in circles represent an initial flow from S to T. Two cuts \(C_1\) and \(C_2\) are shown on Figure 5.
  1. Write down the capacity of each of the two cuts and the value of the initial flow. [3]
  2. Complete the initialisation of the labelling procedure on Diagram 1 by entering values along arcs AC, CD, DE and DT. [2]
  3. Hence use the labelling procedure to find a maximal flow through the network. You must list each flow-augmenting path you use, together with its flow. [5]
  4. Show your maximal flow pattern on Diagram 2. [2]
  5. Prove that your flow is maximal. [2]
Edexcel D1 2007 June Q1
Easy -1.8
Explain what is meant by a planar graph. (Total 2 marks)
Edexcel D1 2007 June Q2
7 marks Easy -1.2
\includegraphics{figure_1} \includegraphics{figure_2} Six workers, Annie, Emma, Hannah, Jerry, Louis and Morand, are to be assigned to five tasks, 1,2,3,4 and 5. For safety reasons, task 1 must be done by two people working together. A bipartite graph showing the possible allocations of the workers is given in Figure 1 and an initial matching is given in Figure 2. The maximum matching algorithm will be used to obtain a complete matching.
  1. Although there are five tasks, six vertices have been created on the right hand side of each bipartite graph. Explain why this is necessary when applying this algorithm. [2]
  2. Find an alternating path and the complete matching it gives. [3]
Hannah is now unable to do task 5 due to health reasons.
  1. Explain why a complete matching is no longer possible. [2]
(Total 7 marks)
Edexcel D1 2007 June Q3
9 marks Easy -1.2
\includegraphics{figure_3} An algorithm is described by the flow chart shown in Figure 3.
  1. Given that \(x = 54\) and \(y = 63\), complete the table in the answer book to show the results obtained at each step when the algorithm is applied. [7]
  2. State what the algorithm achieves. [2]
(Total 9 marks)
Edexcel D1 2007 June Q4
7 marks Moderate -0.3
\includegraphics{figure_4} Figure 4 models a network of underground tunnels that have to be inspected. The number on each arc represents the length, in km, of each tunnel. Joe must travel along each tunnel at least once and the length of his inspection route must be minimised. The total weight of the network is 125 km. The inspection route must start and finish at A.
  1. Use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear. [5]
Given that it is now permitted to start and finish the inspection at two distinct vertices,
  1. state which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer. [2]
(Total 7 marks)
Edexcel D1 2007 June Q5
7 marks Easy -1.3
$$\begin{array}{c|c|c|c|c|c} & M & A & B & C & D & E \\ \hline M & - & 215 & 170 & 290 & 210 & 305 \\ \hline A & 215 & - & 275 & 100 & 217 & 214 \\ \hline B & 170 & 275 & - & 267 & 230 & 200 \\ \hline C & 290 & 100 & 267 & - & 180 & 220 \\ \hline D & 210 & 217 & 230 & 180 & - & 245 \\ \hline E & 305 & 214 & 200 & 220 & 245 & - \end{array}$$ The table shows the cost, in pounds, of linking five automatic alarm sensors, \(A,B,C,D\) and \(E\), and the main reception, \(M\).
  1. Use Prim's algorithm, starting from \(M\), to find a minimum spanning tree for this table of costs. You must list the arcs that form your tree in the order that they are selected. [3]
  2. Draw your tree using the vertices given in Diagram 1 in the answer book. [1]
  3. Find the total weight of your tree. [1]
  4. Explain why it is not necessary to check for cycles when using Prim's algorithm. [2]
(Total 7 marks)
Edexcel D1 2007 June Q6
15 marks Moderate -0.8
\includegraphics{figure_5} The network in Figure 5 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc. The number in brackets is the duration of the activity in days. The early and late event times are to be shown at each vertex and some have been completed for you.
  1. Calculate the missing early and late times and hence complete Diagram 2 in your answer book. [3]
  2. List the two critical paths for this network. [2]
  3. Explain what is meant by a critical path. [2]
The sum of all the activity times is 110 days and each activity requires just one worker. The project must be completed in the minimum time.
  1. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working. [2]
  2. List the activities that must be happening on day 20. [2]
  3. Comment on your answer to part (e) with regard to the lower bound you found in part (d). [1]
  4. Schedule the activities, using the minimum number of workers, so that the project is completed in 30 days. [3]
(Total 15 marks)
Edexcel D1 2007 June Q7
18 marks Moderate -0.3
The tableau below is the initial tableau for a linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\). $$\begin{array}{c|c|c|c|c|c|c|c} \text{basic variable} & x & y & z & r & s & t & \text{Value} \\ \hline r & 12 & 4 & 5 & 1 & 0 & 0 & 246 \\ \hline s & 9 & 6 & 3 & 0 & 1 & 0 & 153 \\ \hline t & 5 & 2 & -2 & 0 & 0 & 1 & 171 \\ \hline P & -2 & -4 & -3 & 0 & 0 & 0 & 0 \end{array}$$ Using the information in the tableau, write down
  1. the objective function, [2]
  2. the three constraints as inequalities with integer coefficients. [3]
Taking the most negative number in the profit row to indicate the pivot column at each stage,
  1. solve this linear programming problem. Make your method clear by stating the row operations you use. [9]
  2. State the final values of the objective function and each variable. [3]
One of the constraints is not at capacity.
  1. Explain how it can be identified. [1]
(Total 18 marks)
Edexcel D1 2007 June Q8
10 marks Moderate -0.3
\includegraphics{figure_6} Figure 6 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.
  1. State the value of the initial flow. [1]
  2. State the capacities of cuts \(C_1\) and \(C_2\). [2]
Diagram 3 in the answer book shows the labelling procedure applied to the above network.
  1. Using Diagram 3, increase the flow by a further 19 units. You must list each flow-augmenting path you use, together with its flow. [5]
  2. Prove that the flow is now maximal. [2]
(Total 10 marks)
Edexcel D1 2010 June Q1
8 marks Easy -1.8
HajraVickyLeishamAliceNickyJuneSharonTomPaul
(H)(V)(L)(A)(N)(J)(S)(T)(P)
The table shows the names of nine people.
  1. Use a quick sort to produce the list of names in ascending alphabetical order. You must make your pivots clear. [4]
  2. Use the binary search algorithm on your list to locate the name Paul. [4]
(Total 8 marks)
Edexcel D1 2010 June Q2
9 marks Easy -1.3
\includegraphics{figure_1} Figure 1 represents the distances, in metres, between eight vertices, A, B, C, D, E, F, G and H, in a network.
  1. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. [3]
  2. Complete Matrix 1 in your answer book, to represent the network. [2]
  3. Starting at A, use Prim's algorithm to determine a minimum spanning tree. You must clearly state the order in which you considered the vertices and the order in which you included the arcs. [3]
  4. State the weight of the minimum spanning tree. [1]
(Total 9 marks)
Edexcel D1 2010 June Q3
9 marks Easy -1.3
41 28 42 31 36 32 29 The numbers in the list represent the weights, in kilograms, of seven statues. They are to be transported in crates that will each hold a maximum weight of 60 kilograms.
  1. Calculate a lower bound for the number of crates that will be needed to transport the statues. [2]
  2. Use the first-fit bin packing algorithm to allocate the statues to the crates. [3]
  3. Use the full bin algorithm to allocate the statues to the crates. [2]
  4. Explain why it is not possible to transport the statues using fewer crates than the number needed for part (c). [2]
(Total 9 marks)
Edexcel D1 2010 June Q4
10 marks Moderate -0.3
\includegraphics{figure_2} [The total weight of the network is 73.3 km] Figure 2 models a network of tunnels that have to be inspected. The number on each arc represents the length, in km, of that tunnel. Malcolm needs to travel through each tunnel at least once and wishes to minimise the length of his inspection route. He must start and finish at A.
  1. Use the route inspection algorithm to find the tunnels that will need to be traversed twice. You should make your method and working clear. [5]
  2. Find a route of minimum length, starting and finishing at A. State the length of your route. [3] A new tunnel, CG, is under construction. It will be 10 km long. Malcolm will have to include the new tunnel in his inspection route.
  3. What effect will the new tunnel have on the total length of his route? Justify your answer. [2]
(Total 10 marks)
Edexcel D1 2010 June Q5
8 marks Easy -1.2
\includegraphics{figure_3} \includegraphics{figure_4} Figure 3 shows the possible allocations of six people, Amelia, Charlie, Ellie, Gemma, Jimmy and Saskia, to six tasks, 1, 2, 3, 4, 5 and 6. Figure 4 shows an initial matching.
  1. Use the maximum matching algorithm once to find an improved matching. You must state the alternating path used and your improved matching. [3]
  2. Explain why a complete matching is not possible. [2] After training, Jimmy can be assigned to tasks 4 or 5 and Ellie to tasks 2, 3, 5 or 6.
  3. Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching. You must state the alternating path used and your final matching. [3]
(Total 8 marks)
Edexcel D1 2010 June Q6
9 marks Easy -1.2
\includegraphics{figure_5} Figure 5 shows a network of cycle tracks within a national park. The number on each arc represents the time taken, in minutes, to cycle along the corresponding track.
  1. Use Dijkstra's algorithm to find the quickest route from S to T. State your quickest route and the time it takes. [6]
  2. Explain how you determined your quickest route from your labelled diagram. [2]
  3. Write down the quickest route from E to T. [1]
(Total 9 marks)
Edexcel D1 2010 June Q7
11 marks Moderate -0.8
\includegraphics{figure_6} Keith organises two types of children's activity, 'Sports Mad' and 'Circus Fun'. He needs to determine the number of times each type of activity is to be offered. Let \(x\) be the number of times he offers the 'Sports Mad' activity. Let \(y\) be the number of times he offers the 'Circus Fun' activity. Two constraints are $$x \leq 15$$ and $$y > 6$$ These constraints are shown on the graph in Figure 6, where the rejected regions are shaded out.
  1. Explain why \(y = 6\) is shown as a dotted line. [1] Two further constraints are $$3x \geq 2y$$ and $$5x + 4y \geq 80$$
  2. Add two lines and shading to Diagram 1 in the answer book to represent these inequalities. Hence determine the feasible region and label it R. [3] Each 'Sports Mad' activity costs £500. Each 'Circus Fun' activity costs £800. Keith wishes to minimise the total cost.
  3. Write down the objective function, C, in terms of \(x\) and \(y\). [2]
  4. Use your graph to determine the number of times each type of activity should be offered and the total cost. You must show sufficient working to make your method clear. [5]
(Total 11 marks)
Edexcel D1 2010 June Q8
11 marks Moderate -0.8
\includegraphics{figure_7} A project is modelled by the activity network shown in Figure 7. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
  1. Complete Diagram 2 in the answer book to show the early and late event times. [4]
  2. State the critical activities. [1]
  3. On Grid 1 in the answer book, draw a cascade (Gantt) chart for this project. [4]
  4. Use your cascade chart to determine a lower bound for the number of workers needed. You must justify your answer. [2]
(Total 11 marks) TOTAL FOR PAPER: 75 MARKS END
Edexcel D1 Q1
6 marks Standard +0.3
  1. Draw the complete graph \(K_5\). [1 mark]
  2. Demonstrate that no planar drawing is possible for \(K_5\). [2 marks]
  3. Draw the complete graph \(K_{3,3}\). [1 mark]
  4. Demonstrate that no planar drawing is possible for \(K_{3,3}\). [2 marks]
Edexcel D1 Q2
7 marks Moderate -0.8
A project consists of 11 activities, some of which are dependent on others having been completed. The following precedence table summarises the relevant information.
ActivityDepends onDuration (hours)
\(A\)\(-\)5
\(B\)\(A\)4
\(C\)\(A\)2
\(D\)\(B, C\)11
\(E\)\(C\)4
\(F\)\(D\)3
\(G\)\(D\)8
\(H\)\(D, E\)2
\(I\)\(F\)1
\(J\)\(F, G, H\)7
\(K\)\(I, J\)2
Draw an activity network for the project. You should number the nodes and use as few dummies as possible. [7 marks]
Edexcel D1 Q3
9 marks Easy -1.2
A machinist has to cut the following seven lengths (in centimetres) of steel tubing. $$150 \quad 104 \quad 200 \quad 60 \quad 184 \quad 84 \quad 120$$
  1. Perform a quick sort to put the seven lengths in descending order. [4 marks]
The machinist is to cut the lengths from rods that are each 240 cm long. You may assume that no waste is incurred during the cutting process.
  1. Explain how to use the first-fit decreasing bin-packing algorithm to find the minimum number of rods required. Show that, using this algorithm, five rods are needed. [4 marks]
  2. Find if it is possible to cut additional pieces with a total length of 300 cm from the five rods. [1 mark]
Edexcel D1 Q4
10 marks Moderate -0.5
This question should be answered on the sheet provided. \includegraphics{figure_1} Figure 1 above shows distances in miles between 10 cities. Use Dijkstra's algorithm to determine the shortest route, and its length, between Liverpool and Hull. You must indicate clearly:
  1. the order in which you labelled the vertices,
  2. how you used your labelled diagram to find the shortest route. [10 marks]
Edexcel D1 Q5
12 marks Moderate -0.5
This question should be answered on the sheet provided. \includegraphics{figure_2} In Figure 2 the weight on each arc represents the cost in pounds of translating a certain document between the two languages at the nodes that it joins. You may assume that the cost is the same for translating in either direction.
  1. Use Kruskal's algorithm to find the minimum cost of obtaining a translation of the document from English into each of the other languages on the network. You must show the order in which the arcs were selected. [4 marks]
  2. It is decided that a Greek translation is not needed. Find the minimum cost if:
    1. translations to and from Greek are not available,
    2. translations to and from Greek are still available. [3 marks]
  3. Comment on your findings. [1 mark]
Another document is to be translated into 60 languages. It is now also necessary to take into account the fact that the cost of a translation between two languages depends on which language you start from.
  1. How would you overcome the problem of having different costs for reverse translations? [1 mark]
  2. What algorithm would be suitable to find a computerised solution. [1 mark]
  3. State another assumption you have made in answering this question and comment on its validity. [2 marks]
Edexcel D1 Q6
13 marks Standard +0.3
This question should be answered on the sheet provided. There are 5 computers in an office, each of which must be dedicated to a single application. The computers have different specifications and the following table shows which applications each computer is capable of running.
ComputerApplications
\(E\)Animation
\(F\)Office, Data
\(G\)Simulation
\(H\)Animation, Office
\(I\)Data, CAD, Simulation
  1. Draw a bipartite graph to model this situation. [1 mark]
Initially it is decided to run the Office application on computer \(F\), Animation on computer \(H\), and Data on computer \(I\).
  1. Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied. [9 marks]
  2. Computer \(H\) is upgraded to allow it to run CAD. Find an alternative matching to that found in part (b). [3 marks]
Edexcel D1 Q7
18 marks Standard +0.3
An engineer makes three components \(X\), \(Y\) and \(Z\). Relevant details are as follows: Component \(X\) requires 6 minutes turning, 3 minutes machining and 1 minute finishing. Component \(Y\) requires 15 minutes turning, 3 minutes machining and 4 minutes finishing. Component \(Z\) requires 12 minutes turning, 1 minute machining and 4 minutes finishing. The engineer gets access to 185 minutes turning, 30 minutes machining and 60 minutes finishing each day. The profits from selling components \(X\), \(Y\) and \(Z\) are £40, £90 and £60 respectively and the engineer wishes to maximise the profit from her work each day. Let the number of components \(X\), \(Y\) and \(Z\) the engineer makes each day be \(x\), \(y\) and \(z\) respectively.
  1. Write down the 3 inequalities that apply in addition to \(x \geq 0\), \(y \geq 0\) and \(z \geq 0\). [3 marks]
  2. Explain why it is not appropriate to use a graphical method to solve the problem. [1 mark]
It is decided to use the simplex algorithm to solve the problem.
  1. Show that a possible initial tableau is:
    Basic Variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
    \(r\)61512100185
    \(s\)33101030
    \(t\)14400160
    \(P\)\(-4\)\(-9\)\(-6\)0000
    [2 marks]
It is decided to increase \(y\) first.
  1. Perform sufficient complete iterations to obtain a final tableau and explain how you know that your solution is optimal. You may assume that work in progress is allowed. [9 marks]
  2. State the number of each component that should be made per day and the total daily profit that this gives, assuming that all items can be sold. [1 mark]
  3. If work in progress is not practicable, explain how you would obtain an integer solution to this problem. You are not expected to find this solution. [2 marks]