AQA A-Level Computer Science 2027 Predicted Practice Paper — Paper 1

Answer ALL questions. Write your answers in the spaces provided. You must write down all the stages in your working.

Section A

Programming fundamentals. Answer all questions in the Electronic Answer Document.

• 1

  Question SECTION-A1 (7 marks)

  A delivery firm stores each parcel's weight in kilograms in a one-dimensional array called Weights, indexed from 1. The array currently holds the values [4, 9, 2, 7, 5]. Using AQA-style pseudocode, write a subroutine FindHeaviest that takes the array Weights and its length n as parameters and RETURNS the value of the heaviest parcel. Your subroutine must use a single pass through the array (a linear search for the maximum) and must NOT use any built-in max function. State clearly what value your subroutine returns for the given data.

  (Total for Question SECTION-A1 is 7 marks)
• 2

  Question SECTION-A2 (7 marks)

  Explain the difference between a WHILE loop and a REPEAT...UNTIL loop in AQA-style pseudocode. Your answer must cover: (a) when the loop condition is tested in each; (b) the minimum number of times the loop body can execute in each; and (c) give one short, original pseudocode example of a situation where a REPEAT...UNTIL loop is the more natural choice than a WHILE loop, and justify why.

  (Total for Question SECTION-A2 is 7 marks)
• 3

  Question SECTION-A3 (6 marks)

  A pseudocode subroutine is intended to convert a whole number of seconds into whole hours, whole minutes and remaining seconds using integer division (DIV) and modulo (MOD). A student writes: SUBROUTINE Convert(totalSeconds) hours <- totalSeconds DIV 3600 minutes <- totalSeconds DIV 60 seconds <- totalSeconds MOD 60 OUTPUT hours, minutes, seconds ENDSUBROUTINE (a) Explain the logic error in the calculation of minutes. (b) Rewrite the two affected lines correctly using DIV and MOD so that, for an input of 3725, the subroutine outputs 1 hour, 2 minutes and 5 seconds. (c) Show the corrected values the subroutine outputs for the input 3725.

  (Total for Question SECTION-A3 is 6 marks)

Section B

Data structures and algorithms. Answer all questions in the Electronic Answer Document.

• 1

  Question SECTION-B1 (8 marks)

  A stack is implemented using a fixed-size array Data of capacity 5 (indices 1 to 5) and an integer TopPointer, where TopPointer = 0 indicates an empty stack. Starting from an empty stack, the following operations are performed in order: PUSH(12), PUSH(7), PUSH(20), POP, PUSH(3), PUSH(9), PUSH(15). (a) State the value returned by the POP operation. (b) State the final value of TopPointer after all operations. (c) List the contents of the stack from bottom to top after all operations. (d) Explain, referring to TopPointer and the capacity, what a well-written PUSH subroutine should do when a PUSH is attempted on a full stack, and identify the term for this condition.

  (Total for Question SECTION-B1 is 8 marks)
• 2

  Question SECTION-B2 (8 marks)

  Consider the following recursive subroutine written in AQA-style pseudocode: SUBROUTINE Mystery(n) IF n <= 1 THEN RETURN 1 ELSE RETURN n * Mystery(n - 1) ENDIF ENDSUBROUTINE (a) State what mathematical function Mystery computes. (b) Identify the base case and the general (recursive) case. (c) Trace the sequence of calls and the returned values for Mystery(4), showing the value returned at each level. (d) Explain what would happen if the base case condition were mistakenly written as IF n = 0 THEN and Mystery were called with a negative argument, naming the run-time problem that results.

  (Total for Question SECTION-B2 is 8 marks)
• 3

  Question SECTION-B3 (9 marks)

  An algorithm searches a sorted array of n elements using a binary search, and a second algorithm searches the same array using a linear search. (a) State the worst-case time complexity of each algorithm using Big-O notation. (b) A sorted array contains 1024 elements. State the maximum number of comparisons a binary search makes in the worst case, and show the reasoning that leads to this number. (c) Explain ONE precondition that binary search requires but linear search does not. (d) A colleague claims that because binary search is O(log n) it is 'always faster' than linear search. Give ONE concrete reason why this claim is not always true in practice.

  (Total for Question SECTION-B3 is 9 marks)

Section C

Theory of computation. Answer all questions in the Electronic Answer Document.

• 1

  Question SECTION-C1 (7 marks)

  A regular language over the alphabet {a, b} consists of all strings that start with the letter a and end with the letter b (the string must be at least two characters long). (a) Write a regular expression that describes this language, using standard notation where * means zero or more repetitions. (b) State whether each of the following strings is ACCEPTED or REJECTED by your expression, giving a one-line reason for each: (i) ab (ii) aab (iii) ba (iv) a. (c) Explain what is meant by saying a language is 'regular', with reference to the type of abstract machine that can recognise it.

  (Total for Question SECTION-C1 is 7 marks)
• 2

  Question SECTION-C2 (7 marks)

  A finite state machine (FSM) is designed to accept binary strings (over the alphabet {0, 1}) that contain an EVEN number of 1s (zero 1s counts as even). The machine has two states: S0 (start state, also the accepting state, representing 'even number of 1s so far') and S1 (representing 'odd number of 1s so far'). (a) Describe the four transitions of this FSM (for each state, what happens on input 0 and on input 1). (b) State which state is the accepting state and why. (c) Trace the machine on the input string 10110, listing the state after each symbol is read, and state whether the string is ACCEPTED or REJECTED.

  (Total for Question SECTION-C2 is 7 marks)
• 3

  Question SECTION-C3 (6 marks)

  (a) Explain what is meant by the term 'Turing machine', identifying its essential components. (b) Explain what is meant by a problem being 'computable'. (c) The Halting Problem asks whether a general algorithm can decide, for any program and any input, whether that program will eventually halt or run forever. State whether such a general algorithm exists, and give a one-sentence description of the significance of this result for computer science.

  (Total for Question SECTION-C3 is 6 marks)

Section D

Skeleton program and systematic problem solving. Answer all questions in the Electronic Answer Document.

• 1

  Question SECTION-D1 (12 marks)

  A library management system needs an algorithm to identify the FIRST duplicate book ID in a list of scanned book IDs, where a 'duplicate' is the first ID that has already appeared earlier in the list. The list may contain up to 100000 integer IDs. (a) Describe, in structured English or pseudocode, a naive nested-loop algorithm that solves this problem, and state its time complexity in Big-O notation. (b) Describe a more efficient algorithm that uses a hash table (set) of seen IDs, and state its time complexity, explaining why it improves on the naive approach. (c) Write AQA-style pseudocode for the efficient algorithm, using a set data structure with operations Add(x) and Contains(x). Your algorithm should RETURN the first duplicate ID, or return -1 if there are no duplicates. (d) Explain one trade-off (other than time) that the hash-table approach introduces compared with the naive approach.

  (Total for Question SECTION-D1 is 12 marks)
• 2

  Question SECTION-D2 (12 marks)

  A courier company models its delivery network as a weighted graph: nodes are depots and edge weights are travel times in minutes. The company wants to find the shortest travel time from a central hub to every other depot. (a) Name an appropriate algorithm for finding the shortest paths from a single source when all edge weights are non-negative, and state the data structure that makes an efficient implementation possible. (b) Describe, step by step in structured English, how this algorithm proceeds from the source until all nodes have their shortest distances finalised. (c) Consider a small network with hub H and depots A, B, C, with edges: H-A = 4, H-B = 2, B-A = 1, A-C = 5, B-C = 8 (all undirected, minutes). Work through the algorithm from H and state the final shortest travel time from H to each of A, B and C, briefly justifying the value for A. (d) Explain why this algorithm is not guaranteed to give correct results if some edge weights are negative.

  (Total for Question SECTION-D2 is 12 marks)
• 3

  Question SECTION-D3 (11 marks)

  A stock-control system must compute, for a range of order quantities, the minimum number of standard boxes needed to pack exactly q items, where boxes come in three sizes holding 1, 4 and 9 items. Assume an unlimited supply of each box size. (a) Show that a greedy algorithm (always choosing the largest box that fits, then repeating) can fail to give the minimum number of boxes, by working through the case q = 12 and comparing the greedy result with the true optimum. (b) Explain how dynamic programming with memoisation can solve this 'minimum coins/boxes' problem correctly, describing the recurrence relation used. (c) Using your recurrence, compute the minimum number of boxes needed for q = 6, showing the values you build up for q = 0, 1, 2, 3, 4, 5, 6. (d) State the time complexity of the dynamic programming solution in terms of q and the number of box sizes k, and briefly justify it.

  (Total for Question SECTION-D3 is 11 marks)