AQA A Level Computer Science Paper 1: On-screen exam June 2025 question paper 7517/1

Two data structures that can be used to store a collection of data records are a hash table and a sorted list.

Explain why a record in a hash table can normally be found more quickly than a record in a sorted list.

Describe the steps involved in adding a new record to a hash table.

Explain why the time taken to find a specific record in a hash table can increase when lots of records are stored in the table.

Linear search and binary search are two algorithms that could be used to find a record in a sorted list.

Explain why the linear search algorithm has time complexity of O(n).

Explain why the binary search algorithm has time complexity of O(log n).

State one advantage of a linear search compared to a binary search.

If the list of records was unsorted, a bubble sort algorithm or a merge sort algorithm could be used to sort the records.

Explain why both these sorting algorithms are tractable.

After how many passes is bubble sort guaranteed to have sorted any list of 100 items?

Define the term decomposition.

Dijkstra’s algorithm is an example of a breadth-first traversal algorithm.

State the purpose of Dijkstra’s algorithm.

Figure 1 shows a graph containing seven nodes.

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

Complete the unshaded cells in Table 1 to show how the graph in Figure 1 could be represented as an adjacency matrix.

Copy the contents of the unshaded cells in Table 1 into the table in your Electronic Answer Document.

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.

Write a program that uses a transposition cipher to encrypt a string entered by the user.

After the user enters the string to encrypt, they enter the number of columns to use. Different numbers of columns result in different encrypted versions of the same string.

Any non-alphabetic characters in the string entered by the user are ignored and will not appear in the encrypted text.

To encrypt the string, the characters from the user’s input are written into a grid (left to right, top to bottom) of cells which has the number of columns specified by the user. The characters are then read from the grid in a different order (top to bottom, left to right).

Example 1

If the user enters the string hypothetically and 3 for the number of columns, then the encrypted version of that string will be hoeclyttayphil

Example 2

If the user enters the string hypothetically and 5 for the number of columns, then the encrypted version of that string will be hhayelptloiytc

Example 3

If the user enters the string How many, how rarely? and 4 for the number of columns, then the encrypted version of that string will be Haoronwewyrlmhay

The spaces and punctuation characters have been removed in the encrypted string.

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

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

You must save this document at regular intervals.

These questions refer to the Preliminary Material and the Skeleton Program, but do not require any additional programming.

Refer either to the Preliminary Material issued with this question paper or your electronic copy.

This question is about the ConvertToRPN subroutine.

Describe two advantages of using Reverse Polish Notation (RPN) instead of infix notation to represent expressions.

A dictionary is used to store the precedence of the allowed operators.

Explain the concept of a dictionary.

State the type of data structure that has been represented using the Operators list.

This question is about the CheckIfUserInputValid subroutine.

Figure 5 shows a finite state machine (FSM) represented as a state transition diagram. The FSM is equivalent to the regular expression in the CheckIfUserInputValid subroutine.

Complete the unshaded cells in Table 3 to represent the FSM in Figure 5 as a state transition table.

Part of the first row has been completed for you.

Copy the contents of the unshaded cells in Table 3 into the table in your Electronic Answer Document.

Figure 6 and Figure 7 show two attempts to represent the regular expression in the CheckIfUserInputValid subroutine using a state transition diagram. There are errors in both diagrams, as the FSM will either accept some strings that do not match the regular expression or not accept some strings that do match the regular expression.

Explain which strings accepted by the FSM in Figure 5 are not accepted by the FSM in Figure 6.

Explain which strings accepted by the FSM in Figure 7 are not accepted by the FSM in Figure 5.

Explain the purpose of the metacharacter $ in the regular expression in the CheckValidNumber subroutine.

Explain the difference between the metacharacters * and ? in regular expressions.

A regular expression can be used to describe a set.

State two properties of sets that do not have to be true for a list.

Infix expressions can normally use brackets.

The infix expressions entered by the user in the Skeleton Program cannot use brackets.

Explain why a regular expression could not be used to check if an infix expression entered by the user was valid if the infix expression was allowed to contain brackets.

This question is about the EvaluateRPN subroutine.

Describe an infix expression that:

would cause the subroutine CheckIfUserInputValid to return True and

could be successfully converted to RPN by the ConvertToRPN subroutine

but that would not be evaluated correctly by the EvaluateRPN subroutine.

Explain the purpose of the final selection structure in the EvaluateRPN subroutine.

Your explanation should include a description of what the possible values returned by the subroutine represent.

This question extends the Skeleton Program by allowing the player to use exponentiation in the expressions they enter.

The player will be allowed to use the ^ symbol to denote exponentiation in an expression they enter. Exponentiation has higher precedence than the other operators.

The four operators currently allowed in expressions are left-associative.

The exponentiation operator will be right-associative.

What you need to do

Task 1 Modify the CheckIfUserInputValid, ConvertToRPN and EvaluateRPN subroutines so the exponentiation operator is allowed and works correctly.

Note: you will be able to achieve most of the marks for this question if you implement the exponentiation operator as left-associative.

Task 2 Test that the changes you have made work:

run the Skeleton Program

select the training game

enter 512/2^3^2+8

enter 3^2

This question extends the Skeleton Program by telling the player all the values that appear more than once in the list of targets.

Before displaying the current score, the program should display an additional list containing all the values that appear more than once in the list of targets. In this additional list, each value should only be displayed once.

What you need to do

Task 1 Create a new subroutine called DisplayTargetMultiples that will display all the values that appear more than once in the targets shown to the player.

Task 2 Modify the DisplayState subroutine so that it calls the subroutine DisplayTargetMultiples immediately before the current score is displayed.

Task 3 Test that the changes you have made work:

run the Skeleton Program

select the training game.

This question extends the Skeleton Program so that the program will tell the player if they can make one of the targets using an expression that contains exactly three of the values from the numbers available.

Your program does not need to work with the exponentiation operator from Question 10.

What you need to do

Task 1 Create a new subroutine called CanGetATargetUsingThreeNumbers that will return True if it is possible to create an expression using exactly three of the values in NumbersAllowed that matches any of the targets shown to the player. Otherwise, it should return False.

Task 2 Modify the DisplayState subroutine so that it calls the subroutine CanGetATargetUsingThreeNumbers and then displays an appropriate message saying if it is possible or not to make one of the targets using exactly three of the values from the available numbers.

Task 3 Test that the changes you have made work:

run the Skeleton Program

select the training game

enter 3+8–2