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

The shaded row of Table 1 contains a list of numbers.

A bubble sort algorithm could be used to sort the list of numbers into ascending order.

Complete the unshaded cells of Table 1 to show the results of completing three passes through the list using a bubble sort algorithm.

You should state the values at the end of each pass.

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

Figure 1 shows a binary tree containing seven nodes. Figure 2 shows how the binary tree in Figure 1 could be represented using three one-dimensional arrays: Data, Dir1 and Dir2.

Define the term binary tree.

The output of a post-order traversal algorithm used to print the data item at each node in the binary tree shown in Figure 1 would be E, H, I, Y, Q, B, C.

State the output that would be produced by an in-order traversal algorithm.

Explain what is meant by a base case for a recursive subroutine.

If the subroutine shown in Figure 3 had been written using recursion, a stack frame would have been stored each time a recursive subroutine call was made.

State two components of a stack frame.

Explain what is meant by procedural decomposition.

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

State two advantages of using Reverse Polish Notation (RPN) instead of infix notation to represent an expression.

Describe how a single stack could be used to evaluate an RPN expression.

An FSM can also be represented as a state transition table.

Complete the state transition table, Table 3, so that it represents the parts of the state transition diagram shown in Figure 4 that involve state S2.

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

Regular expressions can be used to recognise the same strings as FSMs without output.

Write a regular expression that will recognise the same set of strings that are accepted by the FSM shown in Figure 4.

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.

A Harshad number is a positive integer which is exactly divisible by the sum of its digits. The first twelve Harshad numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12 and 18

36 is a Harshad number. The digits of 36 are 3 and 6; the sum of these digits is 9

300 is a Harshad number. The digits of 300 are 3, 0 and 0; the sum of these digits

15 is not a Harshad number. The digits of 15 are 1 and 5; the sum of these digits is 6 as 1 + 5 = 6 and 15 is not exactly divisible by 6

Write a program that asks the user to enter a number, n, and will then calculate and display the n th Harshad number.

Example

If the user enters the number 12 then the program should calculate and display the twelfth Harshad number. The twelfth Harshad number is 18

You may assume that the number that the user enters will be a positive integer.

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

Type your answers to Section C into 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.

To specify which tile to use when entering a command, a player enters the index of the tile in the Tiles list. Instead of using this index the player could have been asked to enter the x, y and z coordinates for the tile.

Figure 5 shows the coordinates and indices for each of the tiles in the default game.

In the default game the tile with an index of 18 is in a straight line with the tile which has an index of 0. It is also in a straight line with the tile which has an index of 7 and in a straight line with the tile which has an index of 2.

Explain how you can tell from the coordinates of two tiles if they are in a straight line with each other.

Describe the modifications that would need to be made to the CheckMoveCommandFormat subroutine so that the move command could use coordinates instead of indices for the two tiles.

This question is about the different types of piece in the game.

Explain why the FuelCostOfMove attribute in the Piece class could not have been a private attribute.

Describe the circumstances when there could be no baron pieces on the grid but more commands would still have to be entered.

In object-oriented programming, what is meant by polymorphism?

The LoadGame subroutine uses exception handling to prevent potential runtime errors. An example of an event that could cause a runtime error when executing the LoadGame subroutine would be trying to open a file that does not exist.

Describe another event that could cause a runtime error when executing the LoadGame subroutine.

State the identifier of another subroutine that uses exception handling.

This question is about the GetDistanceToTileT subroutine in the Tile class.

Explain how this subroutine calculates the distance between two tiles.

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 subroutine DestroyPiecesAndCountVPs in the HexGrid class.

The victory point scoring system for the game is to be changed so that at the end of each turn both players gain additional victory points based on how many LESS pieces they have on the board.

What you need to do

Task 1 Modify the subroutine DestroyPiecesAndCountVPs so that if a piece has not been destroyed it checks to see if it is a LESS piece. If it is a LESS piece the number of victory points awarded to the player to whom that piece belongs should be increased by one.

Task 2 Test that the changes you have made work:

run the Skeleton Program

choose to load a game

enter the filename game1.txt

keep pressing the Enter key until both players have had a turn and the grid has been shown at the start of Player One’s second turn.

This question adds a new type of piece to the game, a ranger, that moves differently to the other pieces.

A ranger can move in the same way as a standard (serf) piece but can also move directly to any available forest tile in the grid if the ranger is currently in a forest tile. The cost of making this type of move is one fuel.

What you need to do

Task 1 Create a new class called RangerPiece that is a subclass of the Piece class. The constructor for this new class should make a call to the constructor of the Piece class and then set the value of PieceType to R.

Task 2 Create a subroutine CheckMoveIsValid in the new RangerPiece class that overrides the subroutine from the base class and allows a ranger piece to move in the way described.

Task 3 Modify the subroutine AddPiece in the HexGrid class so that it creates a new RangerPiece if TypeOfPiece is Ranger.

Task 4 Modify the subroutine SetupDefaultGame so that Player One has a ranger piece in tile 8 instead of a serf piece.

Task 5 Test that the changes you have made work:

run the Skeleton Program

choose the default game

enter the command move 8 12

enter the command move 12 2

enter the command move 2 3

then press the Enter key so that the grid is displayed showing the results of these commands.

This question extends the Skeleton Program by adding a new command to the game that allows a player to burn lumber to turn it into fuel.

If a player uses the burn command when they have lumber in their supply a random integer between one and the amount of lumber they have in their supply is generated. The amount of lumber in their supply is decreased by this random integer with the amount of fuel in their supply being increased by the same amount.

If a player uses the burn command when they do not have any lumber in their supply the message Cannot burn lumber is displayed and no fuel is created.

What you need to do

Task 1 Modify the CheckCommandIsValid subroutine so that it returns True if the command was burn.

Task 2 Modify the ExecuteCommand subroutine in the HexGrid class so that when a player chooses the burn command it returns the string Cannot burn lumber if the player does not have any lumber in their supply.

If the player does have lumber in their supply it:

generates a random integer between one and the amount of lumber in the player’s supply

decreases the amount of lumber in the player’s supply by the random number generated

increases the amount of fuel in the player’s supply by the random number generated

returns the string Command executed.

Task 3 Test that the changes you have made work:

run the Skeleton Program

choose the default game

enter the command burn

press the Enter key twice.

A new feature called ‘fog of war’ is to be added to the Skeleton Program. Fog of war means that each player will only be shown the location of a piece belonging to their opponent if that piece is near one of their own pieces. A piece is near another piece if it is two or fewer cells away on the grid.

The player will still be shown the terrain that is in all the tiles.

Figures 7 to 11 show an example of how the fog of war feature should work.

Figure 7 shows the current positions of Player One’s pieces.

In Figure 8 the shaded tiles are those that are two or fewer cells away from Player One’s baron piece.

In Figure 9 the shaded tiles are those that are two or fewer cells away from Player One’s serf piece.

Figure 10 shows the positions of Player One’s pieces and the positions of Player

Two’s pieces.

Figure 11 shows what Player One should see when they are shown the grid when the fog of war feature has been implemented.

Player Two’s baron piece can be seen because it is within two cells of Player One’s serf piece.

Player Two’s LESS piece can be seen because it is within two cells of both Player One’s serf piece and Player One’s baron piece.

Player Two’s serf piece can be seen because it is within two cells of Player One’s baron piece.

Player Two’s PBDS piece cannot be seen because it is not within two cells of any of Player One’s pieces.

What you need to do

Task 1 Create a new subroutine GetFogOfWar in the HexGrid class.

The new subroutine should take the index of a tile in Tiles and return False if the player whose turn it is has any piece which is two or fewer cells away from that tile as the tile is not hidden because of fog of war. Otherwise, it should return True as this tile is hidden because of fog of war.

Task 2 Modify the GetPieceTypeInTile subroutine in the HexGrid class so that it uses the GetFogOfWar subroutine to determine if this tile is affected by fog of war.

If the contents of this tile would be hidden because of fog of war, it should return the string consisting of a single space character.

If the contents would not be hidden because of fog of war, the existing functionality of the GetPieceTypeInTile subroutine should not be changed.

Task 3 Test that the changes you have made work:

run the Skeleton Program

choose to load a game

enter the filename game1.txt

keep pressing the Enter key until the grid has been shown at the start of Player Two’s first turn.