AQA A-Level Computer Science Paper 1, June 2025: Question 3

12 marks · Medium difficulty · Trace Table

State the purpose of Dijkstra's algorithm, explain why a graph is not a tree, complete an adjacency matrix, describe a recursive base case, and trace a depth-first pathfinding algorithm.

Practise this question

Question

Question 3 includes five sub-questions. Part 03.1 asks to state the purpose of Dijkstra's algorithm. Part 03.2 presents Figure 1, an undirected graph with disconnected components (nodes 1, 2, 3, 6, 7 forming cycles, and separate nodes 4 and 5 connected to each other), asking for two reasons why Figure 1 is not a tree. Part 03.3 asks to complete an empty 7 by 7 adjacency matrix (Table 1). Figure 2 displays the graph as an adjacency list. Figure 3 provides pseudo-code for subroutines IsPath and recursive subroutine Traverse. Part 03.4 asks for one base case of the recursive subroutine Traverse. Part 03.5 asks students to complete a trace table (Table 2) with columns j, Subroutine call to Traverse, i, and array V elements 1 through 7 for the call IsPath(3, 7).
Question text

03.1 State the purpose of Dijkstra’s algorithm.

[1 mark]

Figure 1 shows a graph containing seven nodes.

Figure 1

03.2 State both the reasons why the graph in Figure 1 is not a tree.

[2 marks]

03.3 Complete the unshaded cells in Table 1 to show how the graph in Figure 1 could be

represented as an adjacency matrix.

Table 1

12 3 4 5 6 7

Copy the contents of the unshaded cells in Table 1 into the table in your

Electronic Answer Document. 4

[2 marks]

Figure 2 shows the graph in Figure 1 represented as an adjacency list, called AL.

An adjacency list is a list of lists.

Figure 2

Node Index

12 3

12 3 7

21 6

31 6 7

62 3

71 3

AL[1][3] is equal to 7 as it refers to the 3rd position in the list for node 1

LENGTH(AL[6]) is equal to 2 as there are two items in the list for node 6

Figure 3 contains pseudo-code for an algorithm that finds out if there is a path

between two nodes in the graph represented by the adjacency list AL. Both

subroutines in the algorithm make use of an array V.

Figure 3

SUBROUTINE IsPath(start, end)

FOR j = 1 TO LENGTH(AL)

V[j] = 0

END FOR

FOR j = 1 TO LENGTH(AL)

IF V[j] = 0 THEN

IF Traverse(start, end) = True THEN

RETURN True

END IF

END IF

END FOR

RETURN False

END SUBROUTINE

SUBROUTINE Traverse(start, end)

IF start = end THEN

RETURN True

END IF

V[start] = 1

FOR i = 1 TO LENGTH(AL[start])

IF V[AL[start][i]] = 0 THEN

IF Traverse(AL[start][i], end) = True THEN

RETURN True

END IF

END IF 5

END FOR

RETURN False

03.4 DescribeEND SUBROUTINEoneof the base cases for the recursive subroutine Traverse.

[1 mark]

Figure 4 shows a trace table for the subroutine call Traverse(1, 6)

The subroutine call will return a value of True as there is a path from node 1 to

node 6 in the graph shown in Figure 1, on page 3.

Figure 4

V

Subroutine call to i

Traverse 1 2 3 4 5 6 7

00 0 0 0 0 0

Traverse(1, 6) 1

Traverse(2, 6) 1

Traverse(6, 6) 6

Figures 2 and 3 are repeated here to help you answer Question 03.5.

Figure 2

Node Index

12 3

12 3 7

21 6

31 6 7

62 3

71 3

Figure 3

SUBROUTINE IsPath(start, end)

FOR j = 1 TO LENGTH(AL)

V[j] = 0

END FOR

FOR j = 1 TO LENGTH(AL)

IF V[j] = 0 THEN

IF Traverse(start, end) = True THEN

RETURN True

END IF

END IF

END FOR

RETURN False

END SUBROUTINE

SUBROUTINE Traverse(start, end)

IF start = end THEN

RETURN True

END IF

V[start] = 1

FOR i = 1 TO LENGTH(AL[start])

IF V[AL[start][i]] = 0 THEN

IF Traverse(AL[start][i], end) = True THEN

RETURN True

END IF

END IF

END FOR

RETURN False 7

END SUBROUTINE

03.5 Complete the unshaded cells in Table 2 to show the result of tracing the algorithm

shown in Figure 3 using the adjacency list AL in Figure 2 for the subroutine call

IsPath(3, 7)

Table 2

V

j Subroutine call to i 1 2 3 4 5 6 7

Traverse

Copy the contents of the unshaded cells in Table 2 into the table in your

Electronic Answer Document.

Section B [6 marks]

You are advised to spend no more than 20 minutes on this section.

Enter your answers to Section B in your Electronic Answer Document.

You must save this document at regular intervals.

The question in this section asks you to write program code

starting from a new program/project/file.

You are advised to save your program at regular intervals.

Mark scheme

Show the mark scheme Mark scheme for Question 3 outlines marks per part: 03.1 awards 1 mark for finding the shortest/lowest-cost path between two nodes (or from one node to all others). 03.2 awards 2 marks for 'not connected' and 'it has cycles'. 03.3 awards 2 marks for correctly filling the adjacency matrix (with symmetric connections and 0s on the diagonal). 03.4 awards 1 mark for stating that start and end nodes are the same, or that no unvisited nodes can be reached from the start node. 03.5 awards 6 marks for accurately tracing IsPath(3, 7) through initialization of V, recursive calls to Traverse(3, 7), Traverse(1, 7), Traverse(2, 7), Traverse(6, 7), and Traverse(7, 7), tracking values of j, i, and array V.

Question Marks

03 1 Mark is for AO1 (knowledge) 1

Find the shortest path between two nodes (in a graph) //

find the shortest path from a node to all other nodes (in a graph) //

find the lowest cost (A. distance) path between two nodes (in a graph) //

find the lowest cost (A. distance) path from a node to all other nodes (in a graph);

03 2 All marks for AO2 (analyse) 2

Not connected;

It has cycles;

Max 1 if any additional incorrect answers eg directed

A. by example – A-LEVEL COMPUTER SCIENCE – –

03 3 All marks for AO2 (analyse) 2

12 3 4 5 6 7

10 1 1 0 0 0 1

20 0 0 0 1 0

30 0 0 1 1

40 1 0 0

50 0 0

60 0

Alternative answer

12 3 4 5 6 7

10 1 1 0 0 0 1

21 0 0 0 0 1 0

31 0 0 0 0 1 1

40 0 0 0 1 0 0

50 0 0 1 0 0 0

60 1 1 0 0 0 0

71 0 1 0 0 0 0

Alternative answer

12 3 4 5 6 7

21 0

31 0 0

40 0 0 0

50 0 0 1 0

60 1 1 0 0 0

71 0 1 0 0 0 0

Mark as follows:

1 mark: any three rows correct I. missing values for edges from node to itself A.

use of third symbol for edges from a node to itself

2 marks: correct table

A. any suitable indicators instead of 1 and 0

– A-LEVEL COMPUTER SCIENCE – –

Max 1 if more than two symbols used

03 4 Mark is for AO2 (analyse) 1

The start and end (nodes) are the same;

There are no unvisited nodes in the graph that can be reached from the start node;

NE. code without a description

Max 1

03 5 All marks AO2 (apply) 6

V

j Subroutine call to i 1 2 3 4 5 6 7

Traverse

1 Traverse(3, 7) 1

Traverse(1, 7) 1

Traverse(2, 7) 1

Traverse(6, 7) 1

Traverse(2, 7) 2

Traverse(1, 7) 1

Traverse(7, 7)

Traverse(1, 7) 3

Traverse(3, 7) 1

Mark as follows:

1. j has values 1 to 7 then 1

2. All values of V set to 0

3. First call to Traverse is Traverse(3,7), first value of i is 1 and V[3] is set

to 1 I. IsPath(3, 7)

4. Final values of columns 1 to 7 for V

5. Second and third calls to Traverse

6. Remaining calls to Traverse

– A-LEVEL COMPUTER SCIENCE – –

I. unnecessary repeated values in a column

Max 5 if any errors

I. missing parts in blue font

How to answer it

Graph Representations, Properties & Recursive DFS Traversal

📋 WHAT THIS QUESTION TESTS

AQA A-Level Computer Science — Paper 1 / Paper 2 Graph Theory & Algorithms

  • Dijkstra's Algorithm: Purpose, core functionality, and application to weighted graphs.
  • Tree Definition: Distinguishing general graphs from trees using graph theoretic properties (cycles and connectivity).
  • Graph Representations: Converting visual graph diagrams to symmetric adjacency matrices and interpreting adjacency lists.
  • Recursive Traversal: Identifying base cases and executing a rigorous, line-by-line trace of a recursive Depth-First Search (DFS) path-finding algorithm.
Question 03.1

Purpose of Dijkstra's Algorithm

1 Mark • Assessment Objective: AO1 (Knowledge)

✅ Mark Scheme Answer

Any one of the following:

  • Find the shortest path between two nodes (in a graph).
  • Find the shortest path from a node to all other nodes (in a graph).
  • Find the lowest cost (or lowest distance) path between two nodes / to all other nodes.

🧠 Exam Technique & Vocabulary

Always state what it minimises: use the terms "shortest path" or "lowest cost". Dijkstra's is a single-source shortest path algorithm.

Do not confuse this with Minimum Spanning Tree (MST) algorithms (such as Prim's or Kruskal's), which connect all vertices with minimal total weight.

Mark breakdown: 1 mark for explicitly stating shortest path / lowest cost between nodes or from one node to all others.
Question 03.2

Reasons Why the Graph is Not a Tree

2 Marks • Assessment Objective: AO2 (Analyse)

✅ Both Required Reasons

  • It is not connected (nodes 4 and 5 are completely disconnected from nodes 1, 2, 3, 6, 7).
  • It contains cycles / loops (e.g., cycle 1-2-6-3-1 or 1-3-7-1).

💡 Formal Definition of a Tree

A tree is an undirected, connected graph with no cycles.

For any connected graph with n vertices, a tree must have exactly n − 1 edges. Here, n = 7, edges = 7. Because it fails both the connectivity condition and the acyclic condition, you must state both distinct reasons.

❌ Common Errors & Pitfalls

  • Giving only one reason: The question asks for both reasons for 2 marks.
  • Adding incorrect properties: Stating that "it is directed" or "it has weights" loses marks (Max 1 mark if incorrect additional statements are made).
  • Vague phrasing: Stating "it doesn't have a root node" is not valid; unrooted trees are valid mathematical trees. Focus on connectivity and absence of cycles.
Mark breakdown: 1 mark for identifying that it is not connected; 1 mark for identifying that it has cycles. Max 1 if additional incorrect assertions are made.
Question 03.3

Adjacency Matrix Representation

2 Marks • Assessment Objective: AO2 (Analyse)

✅ Completed Adjacency Matrix (Table 1)

1234567
10110001
21000010
31000011
40000100
50001000
60110000
71010000

💡 Key Properties of Undirected Adjacency Matrices

  • Symmetry: For an undirected graph, the matrix is symmetric along the leading diagonal (e.g., cell [1,2] = cell [2,1] = 1).
  • Main Diagonal: Since there are no self-loops, all values along the leading diagonal ([1,1], [2,2], etc.) are 0.
  • Isolated Subgraph: Nodes 4 and 5 only connect to each other. Rows 4 and 5 only contain a single '1' at columns 5 and 4 respectively.

🧠 Acceptable Alternative Formats

The mark scheme accepts filling only the upper triangle (above the diagonal) or only the lower triangle (below the diagonal) since the graph is undirected and symmetric. Leaving leading diagonal elements blank or using a third consistent symbol (like '-') for self-edges is condoned, but standard practice is 1 for edge present, 0 for absent.

Mark breakdown: 1 mark for any 3 rows correct. 2 marks for full completely correct matrix. Max 1 mark if more than two symbols are used across the table.
Question 03.4

Base Case for Recursive Subroutine Traverse

1 Mark • Assessment Objective: AO2 (Analyse)

✅ Either of the Following Base Cases

  • The start and end nodes are the same ( start = end ), which returns True .
  • There are no unvisited neighbours / nodes that can be reached from the current start node (the loop completes without finding a path), which causes the subroutine to terminate and return False .

❌ Common Errors

Quoting code without explanation: Writing just IF start = end gets 0 marks. The mark scheme explicitly states: "NE. code without a description".

You must describe the condition in words, e.g., "When the current node is equal to the destination node".

Mark breakdown: 1 mark for a clear verbal description of either base condition.
Question 03.5

Trace Table for IsPath(3, 7)

6 Marks • Assessment Objective: AO2 (Apply)

📐 Execution Call Tree Analysis

We trace IsPath(3, 7) using AL (Adjacency List):

1. Initialisation: V[1..7] = 0. 2. j = 1: V[1] is 0, so call Traverse(3, 7). 3. Traverse(3, 7): - start != end (3 != 7). - V[3] = 1. - Neighbours of 3: AL[3] = [1, 6, 7] - i = 1: neighbour = 1. V[1] == 0 -> Call Traverse(1, 7) 4. Traverse(1, 7): - V[1] = 1. - Neighbours of 1: AL[1] = [2, 3, 7] - i = 1: neighbour = 2. V[2] == 0 -> Call Traverse(2, 7) 5. Traverse(2, 7): - V[2] = 1. - Neighbours of 2: AL[2] = [1, 6] - i = 1: neighbour = 1. V[1] == 1 (already visited, skip). - i = 2: neighbour = 6. V[6] == 0 -> Call Traverse(6, 7) 6. Traverse(6, 7): - V[6] = 1. - Neighbours of 6: AL[6] = [2, 3] - i = 1: neighbour = 2 (V[2]=1, skip). - i = 2: neighbour = 3 (V[3]=1, skip). - Loop ends; returns False. Unwinds to Traverse(2, 7). - In Traverse(2, 7), loop ends; returns False. Unwinds to Traverse(1, 7). - Back in Traverse(1, 7): - i = 2: neighbour = 3. V[3] == 1 (skip). - i = 3: neighbour = 7. V[7] == 0 -> Call Traverse(7, 7) 7. Traverse(7, 7): - start == end (7 == 7)! Returns True immediately! - Returns True up the call stack to Traverse(3, 7), which returns True to IsPath.

✅ Fully Completed Trace Table (Table 2)

j Subroutine call to Traverse i V
1234567
10
20
30
40
50
60
70
1Traverse(3, 7)1
1
Traverse(1, 7)1
1
Traverse(2, 7)1
1
2
Traverse(6, 7)1
1
2
Traverse(2, 7)2
Traverse(1, 7)1
2
3
Traverse(7, 7)
Traverse(1, 7)3
Traverse(3, 7)1

Note: Calls shown in grey italics represent returning to previous stack frames. The mark scheme condones or ignores omitting these repeat frame rows provided the sequence of values of i and calls is correct.

❌ Critical Pitfalls in Recursive Trace Tables

  • Forgetting the initialisation of V: The first loop sets V[1..7] = 0 . That accounts for 2 marks alone (one for j values 1 to 7 then 1; one for setting all V values to 0).
  • Setting V[7] to 1: Look closely at the code! Traverse(7, 7) hits IF start = end THEN RETURN True before executing V[start] = 1 . Therefore, V[7] is never set to 1!
  • Not tracking the backtrack: When Traverse(6, 7) finishes, control returns to Traverse(2, 7) which has finished its loop ( i = 2 ), then back to Traverse(1, 7) where i progresses from 1 to 2, then to 3.
Mark Breakdown (6 Marks):
  1. Mark 1: j has values 1 to 7 then 1.
  2. Mark 2: All values of V correctly initialised to 0.
  3. Mark 3: First call to Traverse is Traverse(3, 7) , first value of i is 1, and V[3] is set to 1.
  4. Mark 4: Final values of columns 1 to 7 for V are correct ( 1, 1, 1, 0, 0, 1, 0 ).
  5. Mark 5: Second and third calls to Traverse are Traverse(1, 7) and Traverse(2, 7) .
  6. Mark 6: Remaining calls to Traverse correctly entered ( Traverse(6, 7) then Traverse(7, 7) ).

Topics

4.1 Fundamentals of programming · 4.2 Fundamentals of data structures · 4.3 Fundamentals of algorithms · 4.4 Theory of computation · 4.1.1 Programming · 4.2.4 Graphs · 4.2.5 Trees · 4.3.6 Optimisation algorithms · 4.4.1 Abstraction and automation

Question and mark scheme from the AQA A-Level Computer Science examination, Paper 1, June 2025. QuestionVault is an independent revision resource; questions remain the copyright of the awarding body.