D1 January 2008 Q2
2.
(a)
| 18 | 20 | 11 | 7 | 17 | 15 | 14 | 21 | 23 | 16 | 9 |
The list of numbers shown above is to be sorted into ascending order. Apply quick sort to obtain the sorted list. You must make your pivots clear. (5)
Figure 3 represents a network of paths in a park. The number on each arc represents the length of the path in metres.
(b) Using your answer to part (a) and Kruskal’s algorithm, find a minimum spanning tree for the network in Figure 3. You should list the arcs in the order in which you consider them and state whether you are adding it to your minimum spanning tree. (4)
(c) Find the total weight of the minimum spanning tree. (1)
| Scheme | Marks |
|---|---|
E.g. | M1 A1 A1ft A1ft A1 |
| (5) |
Notes
Q2(a) 1M1 Pivot chosen & 2 sublists, one < pivot, one > pivot
1A1 1st pass correct, all of the next set of pivots chosen, and done so consistently (condone 1 term lists)
1A1ft as above for 2nd pass.
1A1ft All correct, follow through, pivots must be chosen consistently
Alternative correct solutions
Misreads – loose last 2 A marks earned (NOTE: Reversing list at end removes MR)
| Scheme | Marks |
|---|---|
| CF ✓ | |
| GI ✓ | M1 |
| { BC or BF – accept one, reject one { CD ✓ | A1 |
| EF ✓ | |
| DF ✗ | A1 |
| HI ✓ | |
| BE ✗ | |
| AB ✓ | |
| AC ✗ | A1 |
| EG ✓ | |
| Tree complete | |
| (4) |
Notes
(b) 1M1 Using Kruskal – CF then GI
1A1 First 4 arcs chosen correctly
2A1 All arcs chosen correctly (condone lack of rejection here)
3A1 All correct including rejections
| Scheme | Marks |
|---|---|
| 107 m | B1 |
| (1) | |
| (10 marks) |
Notes
(c) B1 cao