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

Describe the process that should be followed to add an item to a circular queue implemented as a static data structure using an array.

Your method should deal appropriately with any issues which could arise.

Figure 1 shows a logic puzzle.

Figure 1

The following five coloured shapes are placed on a table.

Image of coloured shapes not reproduced here due to third party copyright restrictions.

Tabitha secretly chooses one of the coloured shapes and:

• tells Walter the colour of the shape she has chosen (pink, yellow or blue)

• tells Lionel the type of shape she has chosen (triangle, circle or square).

Lionel and Walter both know what coloured shapes are on the table.

Lionel knows that Walter has been told the colour chosen by Tabitha. Walter knows that Lionel has been told the type of shape chosen by Tabitha. They do not know what the other has been told.

Tabitha first asks Walter and Lionel if they know which coloured shape she has chosen. They both answer at the same time and say “No”.

Tabitha then asks them again if they know which coloured shape she has chosen. They both answer at the same time and say “No” again.

Tabitha asks them a third time if they know which coloured shape she has chosen and they both answer at the same time and say “Yes”.

After they have both replied to Tabitha’s first question, what does Lionel now know about Tabitha’s choice because Walter said “No”?

After they have both replied to Tabitha’s first question, what does Walter now know about Tabitha’s choice because Lionel said “No”?

Which coloured shape had Tabitha chosen?

A binary tree is a type of data structure.

State two characteristics that make a tree a binary tree.

There are similarities in how the binary tree search and the binary search algorithms work.

State the big-O time complexity of the binary search algorithm.

Explain why the binary search algorithm has the time complexity stated in your answer for 03.3.

Explain why searching for an item in a list or tree is a tractable problem.

Heuristics can be used when working with an intractable problem.

Explain what heuristics are.

Explain what is meant by constant time complexity.

Complete Table 2 to show which of the languages in Figure 4 are regular languages.

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

Show that the language defined by the union of the sets {bⁿ | n > 0} and {a, ab} is a regular language by writing a regular expression for the language.

Explain what is meant by the cardinality of a set.

Complete the unshaded cells of Table 3 to show the result of tracing the computation of this Turing machine for the first 20 steps only.

Show the contents of the tape, the current position of the read/write head and the current state as the input is processed. The top row of the table shows the initial state, the initial position of the read/write head and the starting contents of the tape.

Table 3

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

Describe two circumstances when the transition function for this Turing machine will not correctly count the number of zeros between two # symbols on the tape.

You should assume that:

the read/write head starts immediately to the right of a cell containing a #

there is a cell containing a # symbol somewhere on the tape to the right of the read/write head’s initial position

there are exactly two # symbols on the tape.

Explain what a Universal Turing machine is.

State one reason why there are some problems that no real computer can solve that the Universal Turing Machine could solve.

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 gets the user to enter a string. It should keep getting the user to enter a string until they enter a valid string. Each time they enter a string an appropriate message should be displayed telling them whether the string they entered is valid or not.

For a string to be valid:

it must be between five and seven characters in length (inclusive)

it must consist only of uppercase letters

it must contain only unique characters (ie no character appears in the string more than once)

the sum of the ASCII codes of the characters in the string must be between 420 and 600 (inclusive).

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 PlayGame method in the Dastan class.

Complete the unshaded cells of Table 4 to show which statements are true and which statements are false about the PlayGame method.

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

If the PlayGame method was altered to allow the user to select any move option from their queue, what is the maximum amount their score could decrease by after making a move?

The Skeleton Program uses overriding. When a derived class overrides a method from the base class, the base class method could be either a virtual method or an abstract method.

Describe two differences between a virtual method and an abstract method.

This question is about the MoveOptionQueue class.

Explain how this class uses information hiding.

The data structure Queue has not been implemented as a first-in first-out (FIFO) queue.

Explain why the MoveItemToBack method in the MoveOptionQueue class does not use the Queue data structure as a FIFO queue.

State the identifier of a method in the MoveOptionQueue class that does use the Queue data structure as a FIFO queue.

This question is about the CheckIfGameOver method in the Dastan class.

Explain why the first selection structure is needed.

Figure 6 shows a pseudo-code representation of part of the CheckIfGameOver method.

Figure 6

NOT (Player1HasMirza AND Player2HasMirza) Rewrite the code in Figure 6 so that it has the same functionality but uses OR and NOT Boolean operations only, instead of the AND and NOT Boolean operations.

1 1

State the name of an identifier for a user-defined method that uses string concatenation.

State the name of an identifier for a class that has a constructor that takes three integer parameters.

Explain why a value of-1 is used in the CreateMoveOptions method in the Dastan class.

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

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

You must save this document at regular intervals.

These questions require you to load the Skeleton Program and to make programming changes to it.

This question refers to the method UseMoveOptionOffer in the Dastan class.

The program is to be changed so that it checks the choice made by the player about which move option to replace is valid. A choice is valid if it is between 1 and 5 inclusive.

The program should keep getting the player to enter a value until a valid choice has been made. Each time an invalid value is entered an appropriate error message should be displayed.

What you need to do

Task 1 Modify the method UseMoveOptionOffer so it checks that the value entered by the player is valid. An appropriate error message should be displayed if an invalid value is entered and the user should be made to enter another value.

You may assume that the user will only enter a single numeric digit.

Task 2 Test that the changes you have made work:

run the Skeleton Program

enter 9

enter 6

enter 4

This question extends the Skeleton Program by allowing a player to choose a bhukampa (earthquake).

After choosing a bhukampa the player can then choose a move option, choose to use the move option offer or choose a bhukampa again.

When a bhukampa is chosen the following steps are repeated five times:

two different squares are randomly selected

the positions on the board of those two squares are swapped.

The player’s score is then reduced by 15 and the new state of the game is displayed.

What you need to do

Task 1 Create a new method in the Dastan class called ProcessBhukampa that swaps the squares in the way described.

Task 2 Modify the PlayGame method in the Dastan class so that if the player enters 8 when asked for their move option, the new method ProcessBhukampa is called, the current player’s score is reduced by 15 and the new game state is displayed.

Task 3 Test that the changes you have made work:

run the Skeleton Program

enter 8

The results of your test should show at least one piece or kotla now being in a different location. If your test does not show this (because all the squares randomly selected by your program were empty), then keep doing this test until that is not the

This question extends the Skeleton Program so that there is a new type of square – a gacaka (trap).

When a player makes a move that means a piece moves into a gacaka, the value of PointsIfCaptured of the piece is increased by 2 and a message saying " Trap! " is displayed. A player who has a piece in a gacaka has their score decreased by 3 each turn until the piece is moved out of the gacaka.

The location of the gacaka is not shown on the board.

What you need to do

Task 1 Create a new class called Gacaka that is a subclass of the Square class. Create two methods SetPiece and GetPointsForOccupancy in the Gacaka class that allow a gacaka to work in the way described.

The method SetPiece in the Gacaka class should override the method from the Square class. The method GetPointsForOccupancy in the Gacaka class should override the method from the Square class.

Task 2 Modify the CreateBoard method in the Dastan class so that row four, column four is a gacaka instead of a square.

Task 3 Test that the changes you have made work:

run the Skeleton Program

enter 3

enter 24

enter 44

enter 1

enter 54

enter 44

This question extends the program by telling the player how many legal moves they have in the current state of the game.

A legal move is when, using one of the first three move options in their move option queue, a player’s piece will move to a square that contains an opponent’s piece or to a square that does not contain a piece. There are 45 legal moves at the start of the game for the first player.

When answering this question, you should ignore the option to use the move option offer and the option to use a bhukampa (from Question 14) as these do not count as moves.

What you need to do

Task 1 Create a new method called GetNoOfPossibleMoves in the Player class that takes Board as a parameter and returns the total number of possible legal moves for that player based on the contents of the squares in the Board list.

Task 2 Modify the DisplayState method in the Dastan class so that it displays the value returned by a call to GetNoOfPossibleMoves for the current player.

Task 3 Test that the changes you have made work:

run the Skeleton Program

enter 1

enter 22

enter 12