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 2005 June Q3
7 marks Moderate -0.3
\includegraphics{figure_2} Figure 2 models a network of roads which need to be inspected to assess if they need to be resurfaced. The number on each arc represents the length, in km, of that road. Each road must be traversed at least once and the length of the inspection route must be minimised.
  1. Starting and finishing at \(A\), solve this route inspection problem. You should make your method and working clear. State the length of the shortest route. (The weight of the network is 77 km.) [5]
Given that it is now permitted to start and finish the inspection at two distinct vertices,
  1. state which two vertices you should choose to minimise the length of the route. Give a reason for your answer. [2]
(Total 7 marks)
Edexcel D1 2005 June Q4
7 marks Moderate -0.8
The precedence table shows the activities involved in a project.
ActivityImmediately preceding activities
\(A\)--
\(B\)--
\(C\)--
\(D\)\(A\)
\(E\)\(A\)
\(F\)\(B\)
\(G\)\(B\)
\(H\)\(C, D\)
\(I\)\(E\)
\(J\)\(F, H\)
\(K\)\(G, J\)
\(L\)\(G\)
\(M\)\(L\)
\(N\)\(L\)
  1. Draw the activity network for this project, using activity on arc and using two dummies. [4]
  2. Explain why each of the two dummies is necessary. [3]
(Total 7 marks)
Edexcel D1 2005 June Q5
8 marks Moderate -0.8
\includegraphics{figure_3} \includegraphics{figure_4} A film critic, Verity, must see five films A, B, C, D and E over two days. The films are being shown at five special critics' preview times: \begin{align} 1 &\text{ (Monday 4 pm),}
2 &\text{ (Monday 7 pm),}
3 &\text{ (Tuesday 1 pm),}
4 &\text{ (Tuesday 4 pm),}
5 &\text{ (Tuesday 7 pm).} \end{align} The bipartite graph in Figure 3 shows the times at which each film is showing. Initially Verity intends to see \begin{align} &\text{Film A on Monday at 4 pm,}
&\text{Film B on Tuesday at 4 pm,}
&\text{Film C on Tuesday at 1 pm,}
&\text{Film D on Monday at 7 pm.} \end{align} This initial matching is shown in Figure 4. Using the maximum matching algorithm and the given initial matching,
  1. find two distinct alternating paths and complete the matchings they give. [6]
Verity's son is very keen to see film D, but he can only go with his mother to the showing on Monday at 7 pm.
  1. Explain why it will not be possible for Verity to take her son to this showing and still see all five films herself. [2]
(Total 8 marks)
Edexcel D1 2005 June Q6
10 marks Easy -1.2
\includegraphics{figure_5} Figure 5 shows a network of roads. The number on each arc represents the length of that road in km.
  1. Use Dijkstra's algorithm to find the shortest route from \(A\) to \(J\). State your shortest route and its length. [5]
  2. Explain how you determined the shortest route from your labelled diagram. [2]
The road from \(C\) to \(F\) will be closed next week for repairs.
  1. Find the shortest route from \(A\) to \(J\) that does not include \(CF\) and state its length. [3]
(Total 10 marks)
Edexcel D1 2005 June Q7
15 marks Moderate -0.3
Polly has a bird food stall at the local market. Each week she makes and sells three types of packs \(A\), \(B\) and \(C\). Pack \(A\) contains 4 kg of bird seed, 2 suet blocks and 1 kg of peanuts. Pack \(B\) contains 5 kg of bird seed, 1 suet block and 2 kg of peanuts. Pack \(C\) contains 10 kg of bird seed, 4 suet blocks and 3 kg of peanuts. Each week Polly has 140 kg of bird seed, 60 suet blocks and 60 kg of peanuts available for the packs. The profit made on each pack of \(A\), \(B\) and \(C\) sold is £3.50, £3.50 and £6.50 respectively. Polly sells every pack on her stall and wishes to maximise her profit, \(P\) pence. Let \(x\), \(y\) and \(z\) be the numbers of packs \(A\), \(B\) and \(C\) sold each week. An initial Simplex tableau for the above situation is
Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)4510100140
\(s\)21401060
\(t\)12300160
\(P\)\(-350\)\(-350\)\(-650\)0000
  1. Explain the meaning of the variables \(r\), \(s\) and \(t\) in the context of this question. [2]
  2. Perform one complete iteration of the Simplex algorithm to form a new tableau \(T\). Take the most negative number in the profit row to indicate the pivotal column. [5]
  3. State the value of every variable as given by tableau \(T\). [3]
  4. Write down the profit equation given by tableau \(T\). [2]
  5. Use your profit equation to explain why tableau \(T\) is not optimal. [1]
Taking the most negative number in the profit row to indicate the pivotal column,
  1. identify clearly the location of the next pivotal element. [2]
(Total 15 marks)
Edexcel D1 2005 June Q8
16 marks Standard +0.3
\includegraphics{figure_6} Figure 6 shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow through the network. Take this as the initial flow.
  1. On Diagram 1 and Diagram 2 in the answer book, add a supersource \(S\) and a supersink \(T\). On Diagram 1 show the minimum capacities of the arcs you have added. [2]
Diagram 2 in the answer book shows the first stage of the labelling procedure for the given initial flow.
  1. Complete the initial labelling procedure in Diagram 2. [2]
  2. Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow, and state the maximal flow. [6]
  3. Show a maximal flow pattern on Diagram 3. [2]
  4. Prove that your flow is maximal. [2]
  5. Describe briefly a situation for which this network could be a suitable model. [2]
(Total 16 marks)
Edexcel D1 2006 June Q1
4 marks Easy -1.8
52 48 50 45 64 47 53 The list of numbers above is to be sorted into descending order. Perform a bubble sort to obtain the sorted list, giving the state of the list after each completed pass. [4]
Edexcel D1 2006 June Q2
7 marks Easy -1.2
  1. Define the term 'alternating path'. [2]
  2. \includegraphics{figure_1} The bipartite graph in Figure 1 shows the films that six customers wish to hire this Saturday evening. The shop has only one copy of each film. The bold lines indicate an initial matching. Starting from this initial matching use the maximum matching algorithm twice to obtain a complete matching. You should clearly state the alternating paths you use. [5]
Edexcel D1 2006 June Q3
7 marks Moderate -0.8
\includegraphics{figure_2} Figure 2 shows the network of pipes represented by arcs. The length of each pipe, in kilometres, is shown by the number on each arc. The network is to be inspected for leakages, using the shortest route and starting and finishing at A.
  1. Use the route inspection algorithm to find which arcs, if any, need to be traversed twice. [4]
  2. State the length of the minimum route. [The total weight of the network is 394 km.] [1]
It is now permitted to start and finish the inspection at two distinct vertices.
  1. State, with a reason, which two vertices should be chosen to minimise the length of the new route. [2]
Edexcel D1 2006 June Q4
12 marks Easy -1.3
  1. Explain what is meant by the term 'path'. [2]
\includegraphics{figure_3} Figure 3 shows a network of cycle tracks. The number on each edge represents the length, in miles, of that track. Mary wishes to cycle from A to I as part of a cycling holiday. She wishes to minimise the distance she travels.
  1. Use Dijkstra's algorithm to find the shortest path from A to I. Show all necessary working in the boxes in Diagram 1 in the answer book. State your shortest path and its length. [6]
  2. Explain how you determined the shortest path from your labelling. [2]
Mary wants to visit a theme park at E.
  1. Find a path of minimal length that goes from A to I via E and state its length. [2]
Edexcel D1 2006 June Q5
15 marks Moderate -0.8
\includegraphics{figure_4} An engineering project is modelled by the activity network shown in Figure 4. 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 time.
  1. Calculate the early time and late time for each event. Write these in boxes in Diagram 1 in the answer book. [4]
  2. State the critical activities. [1]
  3. Find the total float on activities D and F. You must show your working. [3]
  4. On the grid in the answer book, draw a cascade (Gantt) chart for this project. [4]
The chief engineer visits the project on day 15 and day 25 to check the progress of the work. Given that the project is on schedule,
  1. which activities must be happening on each of these two days? [3]
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)