Algorithms and graph theory questions

Practice questions covering algorithms and graph theory from this specification. Attempt the questions below; real-paper references for this topic are being imported.

Questions to attempt

6 questions on Algorithms and graph theory, each with its mark scheme and worked method. Reveal the answer when you have had a go.

D1-1.1 · The general ideas of algorithms and the implementation of an algorithm given by a flow chart or text.
Q1
ORIGINAL
Year 1
Year 1: this is the AS subject content the exam board publishes, which is what most schools teach in Year 12.
1.
A flow chart is described as follows. Box 1: input $N$ . Box 2: is $N=0$ ? If yes, output the count and stop. Box 3: replace $N$ by the integer part of $N\div2$ , add $1$ to the count, and return to Box 2. The count starts at $0$ . Trace the algorithm for $N=100$ , listing every value of $N$ , and state the output.
(4)
(Total for Question 1 is 4 marks)
D1-1.1 · The general ideas of algorithms and the implementation of an algorithm given by a flow chart or text.
Q2
ORIGINAL
Year 1
Year 1: this is the AS subject content the exam board publishes, which is what most schools teach in Year 12.
2.
An algorithm is given in text form. Step 1: let $A=1$ and $B=1$ . Step 2: let $C=A+B$ . Step 3: let $A=B$ and then $B=C$ . Step 4: if $B\leqslant50$ go to Step 2, otherwise stop. Trace the algorithm and state the final values of $A$ and $B$ , and how many times Step 2 is carried out.
(4)
(Total for Question 2 is 4 marks)
D1-1.2 · Bin packing, bubble sort and quick sort.
Q3
ORIGINAL
Year 1
Year 1: this is the AS subject content the exam board publishes, which is what most schools teach in Year 12.
3.
Items of size $4, 7, 3, 6, 5, 2, 8, 5$ are to be packed into bins of capacity $10$ . Apply the first-fit decreasing algorithm and state, with a reason, whether your packing is optimal. You may use the lower bound of $4$ bins.
(5)
(Total for Question 3 is 5 marks)
D1-1.2 · Bin packing, bubble sort and quick sort.
Q4
ORIGINAL
Year 1
Year 1: this is the AS subject content the exam board publishes, which is what most schools teach in Year 12.
4.
Items of size $4, 7, 3, 6, 5, 2, 8, 5$ are to be packed into bins of capacity $10$ . Calculate a lower bound for the number of bins, then apply the first-fit algorithm to the list in the order given.
(5)
(Total for Question 4 is 5 marks)
D1-1.3 · Use of the order of the nodes to determine whether a graph is Eulerian, semi-Eulerian or neither.
Q5
ORIGINAL
Year 1
Year 1: this is the AS subject content the exam board publishes, which is what most schools teach in Year 12.
5.
A connected graph has vertices $A$ , $B$ , $C$ , $D$ , $E$ , $F$ and edges $AB$ , $AC$ , $AE$ , $BC$ , $BD$ , $CD$ , $DF$ , $EF$ . Write down the order of each vertex, classify the graph, and state the smallest number of edges that would have to be added to make it Eulerian.
(5)
(Total for Question 5 is 5 marks)
D1-1.4 · The planarity algorithm for planar graphs.
Q6
ORIGINAL
Year 2
Year 2: this is content the exam board adds beyond the AS subject content, for the full A-level.
6.
A graph has the Hamiltonian cycle $ABCDEFA$ and the additional edges $AC$ , $BD$ , $CE$ and $DF$ . Use the planarity algorithm to determine whether the graph is planar, listing the conflicts and giving a labelling.
(6)
(Total for Question 6 is 6 marks)

Progress is saved on this device for guests and accounts right now; cross-device account sync is not live yet.

Printable question pack — D1-1 Algorithms and graph theoryAll 40 questions across 4 specification points — 34 more than the 6 above — with the full mark scheme. Guest accessible · browser print.

D1-1 Algorithms and graph theory revision notes

Real-paper references

Real-paper references for this module are being imported — the questions above are the site's own, exam-faithful, marked.

Reference rows contain series, paper, question number, marks and classification metadata only. Pearson's question papers open on Pearson's own website.

Questions to attempt

Stuck on algorithms and graph theory?