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 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
AQA D1 2011 January Q1
7 marks Easy -1.2
Six people, \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake. \includegraphics{figure_1}
  1. Represent this information in an adjacency matrix. [2]
  2. Initially, \(B\) is assigned to task 5, \(D\) to task 2, \(E\) to task 4 and \(F\) to task 3. Demonstrate, by using an algorithm from this initial matching, how each person can be allocated to a task. [5]
AQA D1 2011 January Q2
6 marks Easy -1.8
A student is using a quicksort algorithm to rearrange a set of numbers into ascending order. She uses the first number in each list (or sublist) as the pivot. Her correct solution for the first three passes is as follows. Initial list: 10, 7, 4, 22, 13, 16, 19, 5 After 1st pass: 7, 4, 5, 10, 22, 13, 16, 19 After 2nd pass: 4, 5, 7, 10, 13, 16, 19, 22 After 3rd pass: 4, 5, 7, 10, 13, 16, 19, 22
  1. State the pivots used for the 2nd pass. [2]
  2. Write down the number of comparisons on each of the three passes. [3]
  3. Explain whether the student has completed the algorithm. [1]
AQA D1 2011 January Q3
9 marks Moderate -0.8
The following network shows the lengths, in miles, of roads connecting nine villages, \(A\), \(B\), ..., \(I\). \includegraphics{figure_3}
    1. Use Prim's algorithm starting from \(E\), showing the order in which you select the edges, to find a minimum spanning tree for the network. [4]
    2. State the length of your minimum spanning tree. [1]
    3. Draw your minimum spanning tree. [2]
  2. On a particular day, village \(B\) is cut off, so its connecting roads cannot be used. Find the length of a minimum spanning tree for the remaining eight villages. [2]
AQA D1 2011 January Q4
10 marks Moderate -0.3
The network below shows some paths on an estate. The number on each edge represents the time taken, in minutes, to walk along a path.
    1. Use Dijkstra's algorithm on the network to find the minimum walking time from \(A\) to \(J\). [6]
    2. Write down the corresponding route. [1]
  2. A new subway is constructed connecting \(C\) to \(G\) directly. The time taken to walk along this subway is \(x\) minutes. The minimum time taken to walk from \(A\) to \(G\) is now reduced, but the minimum time taken to walk from \(A\) to \(J\) is not reduced. Find the range of possible values for \(x\). [3]
\includegraphics{figure_4}
AQA D1 2011 January Q5
8 marks Moderate -0.3
Norris delivers newspapers to houses on an estate. The network shows the streets on the estate. The number on each edge shows the length of the street, in metres. Norris starts from the newsagents located at vertex \(A\), and he must walk along all the streets at least once before returning to the newsagents. \includegraphics{figure_5} The total length of the streets is 1215 metres.
  1. Give a reason why it is not possible to start at \(A\), walk along each street once only, and return to \(A\). [1]
  2. Find the length of an optimal Chinese postman route around the estate, starting and finishing at \(A\). [5]
  3. For an optimal Chinese postman route, state:
    1. the number of times that the vertex \(F\) would occur; [1]
    2. the number of times that the vertex \(H\) would occur. [1]
AQA D1 2011 January Q6
5 marks Easy -1.2
  1. The complete graph \(K_n\) has every one of its \(n\) vertices connected to each of the other vertices by a single edge.
    1. Find the total number of edges in the graph \(K_5\). [1]
    2. State the number of edges in a minimum spanning tree for the graph \(K_5\). [1]
    3. State the number of edges in a Hamiltonian cycle for the graph \(K_5\). [1]
  2. A simple graph \(G\) has six vertices and nine edges, and \(G\) is Eulerian. Draw a sketch to show a possible graph \(G\). [2]
AQA D1 2011 January Q7
10 marks Moderate -0.8
Fred delivers bread to five shops, \(A\), \(B\), \(C\), \(D\) and \(E\). Fred starts his deliveries at shop \(B\), and travels to each of the other shops once before returning to shop \(B\). Fred wishes to keep his travelling time to a minimum. The table shows the travelling times, in minutes, between the shops. $$\begin{array}{c|ccccc} & A & B & C & D & E \\ \hline A & - & 3 & 11 & 15 & 5 \\ B & 3 & - & 18 & 12 & 4 \\ C & 11 & 18 & - & 5 & 16 \\ D & 15 & 12 & 5 & - & 10 \\ E & 5 & 4 & 16 & 10 & - \end{array}$$
  1. Find the travelling time for the tour \(BACDEB\). [1]
  2. Use the nearest neighbour algorithm, starting at \(B\), to find another upper bound for the travelling time for Fred's tour. [3]
  3. By deleting \(C\), find a lower bound for the travelling time for Fred's tour. [4]
  4. Sketch a network showing the edges that give you the lower bound in part (c) and comment on its significance. [2]
AQA D1 2011 January Q8
7 marks Easy -1.2
A student is tracing the following algorithm with positive integer values of \(A\) and \(B\). The function INT gives the integer part of a number, eg INT(2.3) = 2 and INT(3.8) = 3. Line 10: Let \(X = 0\) Line 20: Input \(A\), \(B\) Line 30: If INT\((A/2) = A/2\) then go to Line 50 Line 40: Let \(X = X + B\) Line 50: If \(A = 1\) then go to Line 90 Line 60: Let \(A =\) INT\((A/2)\) Line 70: Let \(B = 2 \times B\) Line 80: Go to Line 30 Line 90: Print \(X\) Line 100: End
  1. Trace the algorithm in the case where the input values are \(A = 20\) and \(B = 8\). [4]
  2. State the purpose of the algorithm. [1]
  3. Another student changed Line 50 to Line 50: If \(A = 1\) then go to Line 80 Explain what would happen if this algorithm were traced. [2]
AQA D1 2011 January Q9
13 marks Moderate -0.3
Herman is packing some hampers. Each day, he packs three types of hamper: basic, standard and luxury. Each basic hamper has 6 tins, 9 packets and 6 bottles. Each standard hamper has 9 tins, 6 packets and 12 bottles. Each luxury hamper has 9 tins, 9 packets and 18 bottles. Each day, Herman has 600 tins and 600 packets available, and he must use at least 480 bottles. Each day, Herman packs \(x\) basic hampers, \(y\) standard hampers and \(z\) luxury hampers.
  1. In addition to \(x \geqslant 0\), \(y \geqslant 0\) and \(z \geqslant 0\), find three inequalities in \(x\), \(y\) and \(z\) that model the above constraints, simplifying each inequality. [4]
  2. On a particular day, Herman packs the same number of standard hampers as luxury hampers.
    1. Show that your answers in part (a) become \(x + 3y \leqslant 100\) \(3x + 5y \leqslant 200\) \(x + 5y \geqslant 80\) [2]
    2. On the grid opposite, draw a suitable diagram to represent Herman's situation, indicating the feasible region. [4]
    3. Use your diagram to find the maximum total number of hampers that Herman can pack on that day. [2]
    4. Find the number of each type of hamper that Herman packs that corresponds to your answer to part (b)(iii). [1]
AQA D1 2010 June Q1
4 marks Easy -1.2
  1. Draw a bipartite graph representing the following adjacency matrix. [2 marks] $$\begin{array}{c|ccccc} & 1 & 2 & 3 & 4 & 5 \\ \hline A & 1 & 0 & 0 & 0 & 1 \\ B & 0 & 1 & 1 & 1 & 0 \\ C & 0 & 1 & 1 & 1 & 0 \\ D & 1 & 0 & 0 & 0 & 1 \\ E & 1 & 0 & 0 & 0 & 1 \\ \end{array}$$
  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 2010 June Q2
9 marks Easy -1.8
    1. Use a bubble sort to rearrange the following numbers into ascending order, showing the list of numbers after each pass. 6 \quad 2 \quad 3 \quad 5 \quad 4 [3 marks]
    2. Write down the number of comparisons on the first pass. [1 mark]
    1. Use a shuttle sort to rearrange the following numbers into ascending order, showing the list of numbers after each pass. 6 \quad 2 \quad 3 \quad 5 \quad 4 [4 marks]
    2. Write down the number of comparisons on the first pass. [1 mark]
AQA D1 2010 June Q3
11 marks Easy -1.2
The network shows 10 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. \includegraphics{figure_3}
  1. Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the 10 towns. [6 marks]
  2. State the length of your minimum spanning tree. [1 mark]
  3. Draw your minimum spanning tree. [3 marks]
  4. If Prim's algorithm, starting at \(B\), had been used to find the minimum spanning tree, state which edge would have been the final edge to complete the minimum spanning tree. [1 mark]
AQA D1 2010 June Q4
14 marks Moderate -0.3
The network below shows 13 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. The total of all the times is 384 minutes.
  1. Use Dijkstra's algorithm on the network below, starting from \(M\), to find the minimum time to travel from \(M\) to each of the other towns. [7 marks]
    1. Find the travelling time of an optimum Chinese postman route around the network, starting and finishing at \(M\). [6 marks]
    2. State the number of times that the vertex \(F\) would appear in a corresponding route. [1 mark]
\includegraphics{figure_4}
AQA D1 2010 June Q5
10 marks Moderate -0.8
Phil, a squash coach, wishes to buy some equipment for his club. In a town centre, there are six shops, \(G\), \(I\), \(N\), \(R\), \(S\) and \(T\), that sell the equipment. The time, in seconds, to walk between each pair of shops is shown in the table. Phil intends to check prices by visiting each of the six shops before returning to his starting point. $$\begin{array}{c|cccccc} & G & I & N & R & S & T \\ \hline G & - & 81 & 82 & 86 & 72 & 76 \\ I & 81 & - & 80 & 82 & 68 & 73 \\ N & 82 & 80 & - & 84 & 70 & 74 \\ R & 86 & 82 & 84 & - & 74 & 70 \\ S & 72 & 68 & 70 & 74 & - & 64 \\ T & 76 & 73 & 74 & 70 & 64 & - \\ \end{array}$$
  1. Use the nearest neighbour algorithm starting from \(S\) to find an upper bound for Phil's minimum walking time. [4 marks]
  2. Write down a tour starting from \(N\) which has a total walking time equal to your answer to part (a). [1 mark]
  3. By deleting \(S\), find a lower bound for Phil's minimum walking time. [5 marks]
AQA D1 2010 June Q6
17 marks Standard +0.3
Phil is to buy some squash balls for his club. There are three different types of ball that he can buy: slow, medium and fast. He must buy at least 190 slow balls, at least 50 medium balls and at least 50 fast balls. He must buy at least 300 balls in total. Each slow ball costs £2.50, each medium ball costs £2.00 and each fast ball costs £2.00. He must spend no more than £1000 in total. At least 60% of the balls that he buys must be slow balls. Phil buys \(x\) slow balls, \(y\) medium balls and \(z\) fast balls.
  1. Find six inequalities that model Phil's situation. [4 marks]
  2. Phil decides to buy the same number of medium balls as fast balls.
    1. Show that the inequalities found in part (a) simplify to give $$x \geq 190, \quad y \geq 50, \quad x + 2y \geq 300, \quad 5x + 8y \leq 2000, \quad y \leq \frac{1}{3}x$$ [2 marks]
    2. Phil sells all the balls that he buys to members of the club. He sells each slow ball for £3.00, each medium ball for £2.25 and each fast ball for £2.25. He wishes to maximise his profit. On Figure 1 on page 14, draw a diagram to enable this problem to be solved graphically, indicating the feasible region and the direction of an objective line. [7 marks]
    3. Find Phil's maximum possible profit and state the number of each type of ball that he must buy to obtain this maximum profit. [4 marks]
AQA D1 2010 June Q7
6 marks Easy -1.2
A student is testing a numerical method for finding an approximation for \(\pi\). The algorithm that the student is using is as follows. Line 10 \quad Input \(A\), \(B\), \(C\), \(D\), \(E\) Line 20 \quad Let \(A = A + 2\) Line 30 \quad Let \(B = -B\) Line 40 \quad Let \(C = \frac{B}{A}\) Line 50 \quad Let \(D = D + C\) Line 60 \quad Let \(E = (D - 3.14)^2\) Line 70 \quad If \(E < 0.05\) then go to Line 90 Line 80 \quad Go to Line 20 Line 90 \quad Print '\(\pi\) is approximately', \(D\) Line 100 \quad End Trace the algorithm in the case where the input values are $$A = 1, \quad B = 4, \quad C = 0, \quad D = 4, \quad E = 0$$ [6 marks]
AQA D1 2010 June Q8
4 marks Moderate -0.8
A simple connected graph has six vertices.
  1. One vertex has degree \(x\). State the greatest and least possible values of \(x\). [2 marks]
  2. The six vertices have degrees $$x - 2, \quad x - 2, \quad x, \quad 2x - 4, \quad 2x - 4, \quad 4x - 12$$ Find the value of \(x\), justifying your answer. [2 marks]
OCR D1 2008 January Q1
6 marks Easy -1.8
Five boxes weigh 5 kg, 2 kg, 4 kg, 3 kg and 8 kg. They are stacked, in the order given, with the first box at the top of the stack. The boxes are to be packed into bins that can each hold up to 10 kg.
  1. Use the first-fit method to put the boxes into bins. Show clearly which boxes are packed in which bins. [2]
  2. Use the first-fit decreasing method to put the boxes into bins. You do not need to use an algorithm for sorting. Show clearly which boxes are packed in which bins. [2]
  3. Why might the first-fit decreasing method not be practical? [1]
  4. Show that if the bins can only hold up to 8 kg each it is still possible to pack the boxes into three bins. [1]
OCR D1 2008 January Q2
5 marks Moderate -0.8
A puzzle involves a 3 by 3 grid of squares, numbered 1 to 9, as shown in Fig. 1a below. Eight of the squares are covered by blank tiles. Fig. 1b shows the puzzle with all of the squares covered except for square 4. This arrangement of tiles will be called position 4. \includegraphics{figure_1} A move consists of sliding a tile into the empty space. From position 4, the next move will result in position 1, position 5 or position 7.
  1. Draw a graph with nine vertices to represent the nine positions and arcs that show which positions can be reached from one another in one move. What is the least number of moves needed to get from position 1 to position 9? [3]
  2. State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is. [2]
OCR D1 2008 January Q3
11 marks Moderate -0.8
Answer this question on the insert provided. \includegraphics{figure_2}
  1. This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight. [5]
  2. Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex \(G\), and all the arcs joined to \(G\), removed. Hence find a lower bound for the travelling salesperson problem on the original network. [3]
  3. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the travelling salesperson problem on the original network. [3]
OCR D1 2008 January Q4
12 marks Moderate -0.8
Answer this question on the insert provided. Jenny needs to travel to London to arrive in time for a morning meeting. The graph below represents the various travel options that are available to her. \includegraphics{figure_3} It takes Jenny 120 minutes to drive from her home to the local airport and check in (arc \(JA\)). The journey from the local airport to Gatwick takes 80 minutes. From Gatwick to the underground station takes 60 minutes, and walking from the underground station to the meeting venue takes 15 minutes. Alternatively, Jenny could get a taxi from Gatwick to the meeting venue; this takes 80 minutes. It takes Jenny 15 minutes to drive from her house to the train station. Alternatively, she can walk to the bus stop, which takes 5 minutes, and then get a bus to the train station, taking another 20 minutes. From the train station to Paddington takes 300 minutes, and from Paddington to the underground station takes a further 20 minutes. Alternatively, Jenny could walk from Paddington to the meeting venue, taking 30 minutes. Jenny can catch a coach from her local bus stop to Victoria, taking 400 minutes. From Victoria she can either travel to the underground station, which takes 10 minutes, or she can walk to the meeting venue, which takes 15 minutes. The final option available to Jenny is to drive to a friend's house, taking 240 minutes, and then continue the journey into London by train. The journey from her friend's house to Waterloo takes Jenny 30 minutes. From here she can either go to the underground station, which takes 20 minutes, or walk to the meeting venue, which takes 40 minutes.
  1. Weight the arcs on the graph in the insert to show these times. Apply Dijkstra's algorithm, starting from \(J\), to give a permanent label and order of becoming permanent at each vertex. Stop when you have assigned a permanent label to vertex \(M\). Write down the route of the shortest path from \(J\) to \(M\). [9]
  2. What does the value of the permanent label at \(M\) represent? [1]
  3. Give two reasons why Jenny might choose to use a different route from \(J\) to \(M\). [2]