A Level Paper 1: Algorithms and Data Structures
Covers linear data structures, trees and graphs, searching and sorting algorithms, algorithmic complexity, and writing and tracing programs.
Questions
Question 1 [3 marks]
Programming: Trace, Write and Explain
The following pseudocode is executed:
total = 0
FOR i = 1 TO 4
total = total + i * 2
NEXT i
OUTPUT total
Complete a trace of the value of total after each iteration of the loop, and state the value output.
Question 2 [4 marks]
Searching and Sorting Algorithms
The list [15, 8, 42, 3, 27, 19] is searched using a linear search for the value 3, checking each element in turn starting from index 0.
State the number of comparisons made before the target is found (counting the comparison that finds it), and state the index at which it is found.
Question 3 [4 marks]
Linear Data Structures
A circular queue uses an array of fixed capacity, with front identifying the next item to remove and rear identifying the next position for insertion. The indices wrap modulo capacity; no separate count, empty flag or reserved unused slot is used.
Explain why the condition front = rear is ambiguous in this implementation, and explain how keeping a separate count variable resolves the ambiguity.
Question 4 [4 marks]
Trees and Graphs
A directed graph has vertices P, Q, R, S with directed edges P->Q, Q->R, R->P, R->S.
State the in-degree and out-degree of vertex R, where in-degree is the number of edges pointing into a vertex and out-degree is the number of edges pointing out of it.
Question 5 [4 marks]
Algorithmic Complexity
A recursive function to compute factorial(n) calls itself n times before returning, with each call adding a new stack frame.
An iterative version uses a single loop and one accumulator variable.
State the space complexity of each version, in terms of n, and explain the difference. Use auxiliary space, assume fixed-size arithmetic, and assume recursive stack frames are retained without tail-call elimination.
Question 6 [5 marks]
Searching and Sorting Algorithms
The list [6, 2, 8, 1] is sorted using selection sort, which repeatedly finds the minimum value in the unsorted part of the list and swaps it into the correct position, working from the start of the list.
Show the contents of the list after each of the three passes needed to fully sort a 4-element list.
Question 7 [5 marks]
Trees and Graphs
A binary heap is stored in an array, indexed from 0. For a node at index i, its left child is at index (2i + 1), its right child is at index (2i + 2), and its parent is at index floor((i - 1) / 2).
The array [1, 3, 6, 5, 9, 8] represents a binary heap.
State the value of the left child and the right child of the node at index 1, and state the value of the parent of the node at index 4.
Question 8 [5 marks]
Algorithmic Complexity
A sorting algorithm that creates a brand new array to hold the sorted result, the same size as the input, requires extra space proportional to n. A sorting algorithm that rearranges elements within the original array needs only a small, fixed number of extra variables.
State the space complexity of each approach, in terms of n, using Big O notation, and give the name of one sorting algorithm that typically needs an additional array rather than sorting in place.
Question 9 [5 marks]
Trees and Graphs
A graph has vertices W, X, Y, Z with undirected edges W-X, W-Z, X-Y, Y-Z.
An adjacency matrix represents a graph as a grid where a 1 in row P column Q means an edge exists between P and Q, and a 0 means no edge.
State the value in the adjacency matrix for the pairs (W, Y) and (X, Z), and explain why an adjacency matrix for an undirected graph is always symmetrical about its diagonal.
Question 10 [5 marks]
Linear Data Structures
A doubly linked list stores each node as a value, a pointer to the next node and a pointer to the previous node. The list currently holds, in order, 4 <-> 9 <-> 15 <-> 22, with a head pointer to the node holding 4.
Describe, as a sequence of steps, how the node holding 15 is removed so the list becomes 4 <-> 9 <-> 22. You do not need to write code.
Question 11 [4 marks]
Programming: Trace, Write and Explain
A student writes the following pseudocode, intended to output every element of a list, values, which has 6 elements (indices 0 to 5):
FOR i = 1 TO 6: OUTPUT values[i] ; NEXT i
Explain why this code either misses an element or causes an error, and rewrite the FOR line so the code works correctly for a list of any length.
Question 12 [6 marks]
Linear Data Structures
A stack can be implemented using two queues, queue1 and queue2. To push a value: enqueue it onto queue2, then dequeue every item from queue1 and enqueue each one onto queue2 in turn, then treat queue2 as the new queue1 and queue1 as the new (empty) queue2. To pop a value: dequeue from queue1.
Starting with both queues empty, the operations push(A), push(B), pop(), push(C), pop() are performed in order.
State the value returned by each pop() call.
Question 13 [6 marks]
Algorithmic Complexity
A program contains the following pseudocode, where n is a positive integer:
count = 0
FOR i = 1 TO n
FOR j = 1 TO i
count = count + 1
NEXT j
NEXT i
Show that the total number of times count is incremented is n(n + 1) / 2, and hence state the time complexity of this code in Big O notation.
Model solutions
| Question 1[3 marks] | |
|---|---|
| Answer or working | Marks |
| total values 2 and 6 after iterations 1 and 2 | M1 |
| total values 12 and 20 after iterations 3 and 4 | M1 |
| output 20 | A1 |
| Final answer: total after iterations: 2, 6, 12, 20; output 20. | |
| Question 2[4 marks] | |
|---|---|
| Answer or working | Marks |
| checking index 0 (15), index 1 (8) and index 2 (42) in turn, none matching | M1 |
| finding a match at index 3, value 3 | A1 |
| stating the target is found after 4 comparisons | A1 |
| stating the index found is 3 Award all 4 marks for the complete correct requested answer: 4 comparisons; found at index 3. Accept equivalent valid notation and explanations. Intermediate method evidence below is optional and may be inferred from a correct requested result; do not require unasked states or extra explanations. | A1 |
| Final answer: 4 comparisons; found at index 3. | |
| Question 3[4 marks] | |
|---|---|
| Answer or working | Marks |
| equal front and rear representing an empty queue under the printed next-insertion convention | B1 |
| also representing a full queue after a complete wrap. | B1 |
| count tracking the number of stored items | B1 |
| empty at count=0 and full at count=capacity. Accept equivalent correct explanations. | B1 |
| Final answer: With rear as the next insertion position, equal indices can mean empty or full after wrapping. A separate count tracks stored items: empty when count=0, full when count=capacity. | |
| Question 4[4 marks] | |
|---|---|
| Answer or working | Marks |
| correctly identifying the incoming count as the in-degree | B1 |
| its value 1. Award both marks for in-degree 1 alone. | B1 |
| correctly identifying the outgoing count as the out-degree | B1 |
| its value 2. Award both marks for out-degree 2 alone. Award all 4 marks for in-degree 1 and out-degree 2 alone. Naming edges is optional evidence; accept equivalent valid notation. | B1 |
| Final answer: In-degree 1; out-degree 2. | |
| Question 5[4 marks] | |
|---|---|
| Answer or working | Marks |
| stating the recursive version has space complexity O(n) | B1 |
| explaining this is because each recursive call adds a stack frame that remains until the call returns | B1 |
| stating the iterative version has space complexity O(1) | B1 |
| explaining this is because it reuses the same variables on each loop iteration rather than growing the call stack | B1 |
| Final answer: Recursive: O(n) because each call adds a stack frame; iterative: O(1) because it reuses the same variables | |
| Question 6[5 marks] | |
|---|---|
| Answer or working | Marks |
| identifying the minimum of the whole list, 1, in pass one, and swapping it into index 0 | M1 |
| the list reading 1, 2, 8, 6 after pass one | A1 |
| identifying the minimum of the remaining unsorted part (2, 8, 6) as 2, which is already in its correct position (index 1), so no swap occurs | M1 |
| the list remaining 1, 2, 8, 6 after pass two | A1 |
| pass three swapping the minimum of the last two elements, 6, into index 2, giving the fully sorted list 1, 2, 6, 8 Award all 5 marks for a complete correct answer to the requested task. Accept equivalent valid explanations and notation. Method details not explicitly requested may be inferred from the correct requested results. All three pass states are requested; finding minima and describing self-swaps are optional working. Award all 5 marks for the complete correct requested answer: Pass 1: [1,2,8,6]. Pass 2: [1,2,8,6]. Pass 3: [1,2,6,8]. Accept equivalent valid notation and explanations. Intermediate method evidence below is optional and may be inferred from a correct requested result; do not require unasked states or extra explanations. | A1 |
| Final answer: Pass 1: [1,2,8,6]. Pass 2: [1,2,8,6]. Pass 3: [1,2,6,8]. | |
| Question 7[5 marks] | |
|---|---|
| Answer or working | Marks |
| using left-child index 3 | M1 |
| left-child value 5. Both may be inferred from the correctly identified left-child value. | A1 |
| using right-child index 4 | M1 |
| right-child value 9. Both may be inferred from the correctly identified right-child value. | A1 |
| parent value 3. Award all 5 marks for the three correct values, clearly associated with the requested relationships; no index arithmetic is required. | A1 |
| Final answer: Left child of index 1 is value 5 (index 3); right child is value 9 (index 4); parent of index 4 is value 3 (index 1). | |
| Question 8[5 marks] | |
|---|---|
| Answer or working | Marks |
| stating the new-array approach has auxiliary space complexity O(n); no reason is required This row begins a shared allocation of 2 marks for the same requested result or explanation. | B1 |
| mark 2 of the same 2-mark allocation above. A complete response meeting that allocation earns every mark in the group; this row adds no separate requirement. Retain the partial-credit guidance stated in the first row of the group. | B1 |
| stating the fixed-variable approach has auxiliary space complexity O(1); no reason is required This row begins a shared allocation of 2 marks for the same requested result or explanation. | B1 |
| mark 2 of the same 2-mark allocation above. A complete response meeting that allocation earns every mark in the group; this row adds no separate requirement. Retain the partial-credit guidance stated in the first row of the group. | B1 |
| a valid sorting algorithm typically needing an additional array, such as standard array merge sort | B1 |
| Final answer: New-array approach: O(n); in-place approach: O(1); merge sort is a common example needing an additional array | |
| Question 9[5 marks] | |
|---|---|
| Answer or working | Marks |
| identifying no edge exists between W and Y | M1 |
| the adjacency matrix entry for (W, Y) being 0 | A1 |
| identifying no edge exists between X and Z | M1 |
| the adjacency matrix entry for (X, Z) being 0 | A1 |
| explaining the matrix is symmetrical because an undirected edge P-Q means Q-P also exists, so the entry at [P][Q] always matches [Q][P] Award all 5 marks for a complete correct answer to the requested task. Accept equivalent valid explanations and notation. Method details not explicitly requested may be inferred from the correct requested results. Both entries and a reason for symmetry are requested. Absence of each edge is directly evidenced by its zero entry. | B1 |
| Final answer: (W,Y)=0 and (X,Z)=0. In an undirected graph an edge P-Q is also the connection Q-P, so matrix entries at row P column Q and row Q column P are equal. | |
| Question 10[5 marks] | |
|---|---|
| Answer or working | Marks |
| identifying 9 and 22 as the neighbours of 15. | M1 |
| setting 9.next to 22 | A1 |
| setting 22.previous to 9. | A1 |
| bypassing the removed node in both directions | B1 |
| a valid completed deletion sequence. Accept equivalent pointer descriptions and automatic memory reclamation. No comparison with singly linked lists is required. | B1 |
| Final answer: Set 9.next to 22 and 22.previous to 9, bypassing 15 in both directions. The list is 4 <-> 9 <-> 22. Reclaim 15 if required; equivalent valid descriptions need no explicit manual deallocation. | |
| Question 11[4 marks] | |
|---|---|
| Answer or working | Marks |
| explaining that index 0 is omitted | B1 |
| explaining that index 6 is out of bounds | B1 |
| starting the corrected loop at index 0 | M1 |
| ending the corrected loop at LEN(values) - 1, or an equivalent length-dependent bound | A1 |
| Final answer: Index 0 is omitted and index 6 is outside 0..5. Replace the FOR line with FOR i = 0 TO LEN(values) - 1. | |
| Question 12[6 marks] | |
|---|---|
| Answer or working | Marks |
| push(A): A is enqueued onto queue2, queue1 is empty so nothing is moved, and the queues swap roles so queue1 holds A | M1 |
| push(B): B is enqueued onto queue2, then A is moved from queue1 into queue2 giving queue2 = B, A, and the queues swap so queue1 holds B, A | M1 |
| the first pop() dequeuing from the front of queue1, returning B | A1 |
| push(C): C is enqueued onto queue2, then A (queue1's remaining item) is moved into queue2 giving queue2 = C, A, and the queues swap so queue1 holds C, A | M1 |
| the second pop() dequeuing from the front of queue1, returning C | A1 |
| explaining this gives correct LIFO behaviour, since each push re-builds queue1 so the most recently pushed value is always at its front Award all 6 marks for the complete correct requested answer: The pop values are B, then C. Accept equivalent valid notation and explanations. Intermediate method evidence below is optional and may be inferred from a correct requested result; do not require unasked states or extra explanations. | A1 |
| Final answer: The pop values are B, then C. | |
| Question 13[6 marks] | |
|---|---|
| Answer or working | Marks |
| recognising that the inner loop runs i times for each outer value i | M1 |
| expressing the total as 1+2+...+n or an equivalent recurrence | M1 |
| valid reasoning deriving or evaluating that total, such as pairing, induction or applying the arithmetic-series formula. Either a complete derivation or a correct formula application earns both marks; no particular method or name for the sum is required. Award M1 for correct incomplete reasoning. This row begins a shared allocation of 2 marks for the same requested result or explanation. | M1 |
| mark 2 of the same 2-mark allocation above. A complete response meeting that allocation earns every mark in the group; this row adds no separate requirement. Retain the partial-credit guidance stated in the first row of the group. | M1 |
| obtaining n(n+1)/2 increments | A1 |
| stating O(n^2); no explicit polynomial expansion is required | A1 |
| Final answer: count is incremented n(n + 1) / 2 times in total; this is O(n^2) | |