AS June 2025 Q1

EdexcelAS paperCurrent spec7 marksAlgorithms Minimum Spanning Trees

The list of ten numbers above is to be sorted into ascending order.

(a) Carry out a bubble sort, starting at the left-hand end of the list, to produce the sorted list. You should only give the state of the list after each pass. (3)

Figure 1: weighted network on vertices A to F with arcs AB 13, AC 10, AD 30, BC 12, BE 22, BF 23, CF 20, CD 28, DF 25, EF 16 — Figure 1

(b) Use Prim’s algorithm, starting at A, to find the minimum spanning tree for the network in Figure 1. You must list the arcs in the order in which you select them. (2)

(c)

(i) Draw the minimum spanning tree on Diagram 1 in the answer book.

Diagram 1: the vertices A to F of Figure 1 with no arcs — Diagram 1

(ii) Find the weight of the minimum spanning tree. (2)

Mark scheme (a)

Scheme

Marks

16	10	25	30	13	12	28	22	23	20
10	16	25	13	12	28	22	23	20	30

1.1b

10	16	13	12	25	22	23	20	28	30
10	13	12	16	22	23	20	25	28	30

1.1b

10	12	13	16	22	20	23	25	28	30
10	12	13	16	20	22	23	25	28	30
10	12	13	16	20	22	23	25	28	30

(sort complete)

A1CSO

1.1b

(3)

Notes

a1M1: Bubble sort using all 10 numbers (condone one error or omission). Consistent direction, end number (30) in place and list beginning with correct three numbers (10, 16, 25).
Quick sort scores M0.

a1A1: First, second and third passes correct – so end three numbers (25, 28, 30) in place.

a2A1: CSO (previous two marks must have been awarded in this part). Must state either ‘sort/algorithm complete’ or show 6^th pass showing no swaps/changes.

SC: Bubble sort from right hand end of list:

16	10	25	30	13	12	28	22	23	20
10	16	12	25	30	13	20	28	22	23
10	12	16	13	25	30	20	22	28	23
10	12	13	16	20	25	30	22	23	28
10	12	13	16	20	22	25	30	23	28
10	12	13	16	20	22	23	25	30	28
10	12	13	16	20	22	23	25	28	30
10	12	13	16	20	22	23	25	28	30

M1 Consistent direction, end number (10) in place and list ending with correct three numbers (28,22,23).
A1 First, second and third passes correct – so first three numbers (10,12,13) in place.
A1 CSO (previous two marks must have been awarded in this part). Must state either ‘sort complete’ or show 7^th pass showing no swaps/changes.

SC: If the candidate sorts into descending order from left hand side they can score M1 only for a fully correct sort (even if reversed). (see below)

Descending from left-hand side (maximum M1A0A0)

16	10	25	30	13	12	28	22	23	20
16	25	30	13	12	28	22	23	20	10
25	30	16	13	28	22	23	20	12	10
30	25	16	28	22	23	20	13	12	10
30	25	28	22	23	20	16	13	12	10
30	28	25	23	22	20	16	13	12	10
30	28	25	23	22	20	16	13	12	10

Mark scheme (b)

Scheme	Marks	AO
AC (10), BC (12), CF (20), EF (16), DF (25)	M1 A1	1.1b 1.1b
	(2)

Notes

b1M1: First three arcs correctly chosen in order. Any rejection seen implies M0.

b1A1: All 5 arcs correctly chosen in order.

SC: All 6 nodes written in the correct order ACBFED scores M1A0

Scheme	Marks	AO
(i)	B1	2.2a
(ii) 83	B1	2.2a
	(2)
	(7 marks)