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

3 marks · Medium difficulty · Trace Table

Complete the trace table for the given algorithm that traverses array-based data structures representing a tree using a binary string input.

Practise this question

Question

Question 01 displays Figure 1 containing three parallel arrays indexed from 0 to 26: Letter (containing letters A to Z), L (containing integer indices for left branches), and R (containing integer indices for right branches). Figure 2 shows an algorithm: M is set to "1001", Current to 0. A FOR loop runs i from 0 to 3, assigning Symbol = M[i], then if Symbol is "0", Current = L[Current], else Current = R[Current]. After the loop, it outputs Letter[Current]. Students are instructed to complete Table 1, a trace table with columns M, i, Symbol, Current, and Output, where initial row has M = "1001" and Current = 0.
Question text

01 Figure 1 shows the data structures Letter, L and R used by the algorithm shown

in Figure 2.

Figure 1

Letter L R

[0] [0] 5 [0] 20

[1] A [1] 18 [1] 23

[2] B [2] -1 [2] -1

[3] C [3] -1 [3] -1

[4] D [4] 2 [4] 24

[5] E [5] 9 [5] 1

[6] F [6] -1 [6] -1

[7] G [7] 26 [7] 17

[8] H [8] -1 [8] -1

[9] I [9] 19 [9] 21

[10] J [10] -1 [10] -1

[11] K [11] 3 [11] 25

[12] L [12] -1 [12] -1

[13] M [13] 7 [13] 15

[14] N [14] 4 [14] 11

[15] O [15] -1 [15] -1

[16] P [16] -1 [16] -1

[17] Q [17] -1 [17] -1

[18] R [18] 12 [18] -1

[19] S [19] 8 [19] 22

[20] T [20] 14 [20] 13

[21] U [21] 6 [21] -1

[22] V [22] -1 [22] -1

[23] W [23] 16 [23] 10

[24] X [24] -1 [24] -1

[25] Y [25] -1 [25] -1

[26] Z [26] -1 [26] -1

Figure 2

M ← "1001"

Current ← 0

FOR i ← 0 TO 3

Symbol ← M[i]

IF Symbol = "0" THEN

Current ← L[Current]

ELSE

Current ← R[Current]

ENDIF

ENDFOR

OUTPUT Letter[Current]

Complete Table 1 by hand-tracing the algorithm in Figure 2.

The strings are zero index based. For example, the character with index 0 in the

string "ABCD" is "A".

You may not need to use all the rows in Table 1.

The first row of Table 1 has already been completed for you.

Table 1

M i Symbol Current Output

"1001" 0

Copy the contents of all the unshaded cells in Table 1 into your Electronic

Answer Document.

[3 marks]

Mark scheme

Show the mark scheme Mark scheme for Question 01 with a completed trace table. Columns: i has values 0, 1, 2, 3; Symbol has values 1, 0, 0, 1; Current has values 20, 14, 4, 24; Output has value 'X'. One mark is awarded for each correct group: i and Symbol values (0, 1; 1, 0; 2, 0; 3, 1), Current values (20, 14, 4, 24), and Output ('X'). Notes state to ignore presence or absence of quotes around values, case in Output, with a maximum of 2 marks if any errors are present.

Qu Marks

01 3 marks for AO2 (application) 3

M i Symbol Current Output

"1001" 0

01 20

10 14

20 4

31 24 X

1 mark for each correct set of values in the correct sequence (boxed in red)

I. presence/absence of quotation marks around values in all columns and case in

Output column

Max 2 if any errors

How to answer it

AQA AS Level Computer Science • Paper 1

Tracing a Tree Traversal Algorithm

What this question tests

  • Hand-tracing pseudocode: Executing a deterministic algorithm line by line using a structured trace table.
  • 0-indexed data structures: Correctly accessing character elements from string M using 0-based indexing.
  • Pointer-based array representation: Interpreting parallel 1D arrays ( L , R , Letter ) functioning as a binary tree with left and right child pointers.
  • Definite iteration and conditional branching: Updating variable states across fixed loop iterations based on boolean comparisons.

Question 01 Hand-Trace Solution

Total Marks: 3 (AO2 Application)

✅ Completed Trace Table (Table 1)

M i Symbol Current Output
"1001" 0
0 1 20
1 0 14
2 0 4
3 1 24 X
Mark Allocation (3 Marks Total):
  • 1 Mark: Correct values in the correct sequence for columns i and Symbol ( 0/1, 1/0, 2/0, 3/1 ).
  • 1 Mark: Correct values in the correct sequence for column Current ( 20, 14, 4, 24 ).
  • 1 Mark: Correct value in the Output column ( X ) on the final completed row.
  • Note: Ignore presence/absence of quotation marks around values. Ignore case for the output letter (e.g. "X" , 'x' , or x are all accepted). Max 2 marks if any errors are present.

📐 Step-by-Step Iteration Walkthrough

Initial state: M = "1001" , Current = 0 .

  1. Iteration i = 0:
    • Symbol ← M[0] which is "1"
    • Symbol = "0" is False
    • Go to ELSE : Current ← R[0] = 20
  2. Iteration i = 1:
    • Symbol ← M[1] which is "0"
    • Symbol = "0" is True
    • Go to THEN : Current ← L[20] = 14
  3. Iteration i = 2:
    • Symbol ← M[2] which is "0"
    • Symbol = "0" is True
    • Go to THEN : Current ← L[14] = 4
  4. Iteration i = 3:
    • Symbol ← M[3] which is "1"
    • Symbol = "0" is False
    • Go to ELSE : Current ← R[4] = 24
  5. After Loop (Output):
    • Loop ends as i reaches 3.
    • Execute OUTPUT Letter[24] : Index 24 of array Letter is "X".

💡 Key Knowledge: Array-Based Binary Trees

This algorithm implements a classic Huffman / Binary Tree decoding traversal using three parallel arrays:

  • L array: Stores indices of left children (followed when the bit is "0" ).
  • R array: Stores indices of right children (followed when the bit is "1" ).
  • Letter array: Stores character payloads stored at each node. Leaves often contain alphabet characters; internal nodes contain empty or null values.
  • Values of -1 in L and R indicate a null pointer (a leaf node).

🧠 Exam Technique: Trace Table Discipline

  • Row matching: Only record a new value when a variable changes. In a for-loop trace, each complete iteration typically maps neatly to one table row.
  • Scope of Output: Notice that OUTPUT Letter[Current] sits outside the ENDFOR block. Only one single output is produced after all four loop iterations finish.
  • Unused rows: The prompt specifies "You may not need to use all the rows in Table 1." Never feel forced to fill empty rows at the bottom.

❌ Common Student Traps

  • 1-based string indexing: Taking M[0] as nothing and starting with index 1 (which would incorrectly read characters starting from the second character).
  • Swapping L and R: Looking up pointer values in array L when Symbol == "1" instead of array R .
  • Premature output: Writing letters into the Output column at each iteration rather than waiting until the loop has terminated.
  • Re-reading old node pointers: Looking up indices using the original node index (0) instead of updating to the new value of Current .

Topics

4.1 Fundamentals of programming · 4.2 Fundamentals of data structures · 4.4 Theory of computation · 4.1.1 Programming · 4.2.1 Data structures and abstract data types · 4.4.1 Abstraction and automation

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